動態鏈表

鎖定

/*線性表的單鏈表存儲結構*/
typedef struct LNode
{
    ElemType data;
    struct LNode *next;
} LNode, *LinkList;

/*帶有頭結點的單鏈表的基本操作(12個)*/
void InitList(LinkList *L)
{
    /* 操作結果：構造一個空的線性表L */
  	*L=(LinkList)malloc(sizeof(struct LNode));
  	/* 產生頭結點，並使L指向此頭結點 */
  	if(!*L) /* 存儲分配失敗 */
      	exit(OVERFLOW);
    (*L)->next=NULL; /* 指針域為空 */
}
void DestroyList(LinkList *L)
{
    /* 初始條件：線性表L已存在。操作結果：銷燬線性表L */
  	LinkList q;
    while(L)
    {
        q=(*L)->next;
        free(L);
        *L=q;
    }
}
void ClearList(LinkList L) /* 不改變L */
{
    /* 初始條件：線性表L已存在。操作結果：將L重置為空表 */
  	LinkList p,q;
    p=L->next; /* p指向第一個結點 */
  	while(p) /* 沒到表尾 */
    {
        q=p->next;
        free(p);
        p=q;
    }
    L->next=NULL; /* 頭結點指針域為空 */
}
Status ListEmpty(LinkList L)
{
    /* 初始條件：線性表L已存在。操作結果：若L為空表，則返回TRUE，否則返回FALSE */
  	if(L->next) /* 非空 */
      	return FALSE;
    else
      	return TRUE;
}
int ListLength(LinkList L)
{
    /* 初始條件：線性表L已存在。操作結果：返回L中數據元素個數 */int i=0;
    LinkList p=L->next; /* p指向第一個結點 */
  	while(p) /* 沒到表尾 */
    {
        i++;
        p=p->next;
    }
    return i;
}
Status GetElem(LinkList L,int i,ElemType *e) /* 算法2.8 */
{
    /* L為帶頭結點的單鏈表的頭指針。當第i個元素存在時，其值賦給e並返回OK，否則返回ERROR */
  	int j=1; /* j為計數器 */
  	LinkList p=L->next; /* p指向第一個結點 */
  	while(p&&j < i) /* 順指針向後查找，直到p指向第i個元素或p為空 */
    {
        p=p->next;
        j++;
    }
    if(!p||j>i) /* 第i個元素不存在 */
      	return ERROR;
    *e=p->data; /* 取第i個元素 */
  		return OK;
}
int LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
    /* 初始條件: 線性表L已存在，compare()是數據元素判定函數(滿足為1，否則為0) *//* 操作結果: 返回L中第1個與e滿足關係compare()的數據元素的位序。 *//* 若這樣的數據元素不存在，則返回值為0 */int i=0;
    LinkList p=L->next;
    while(p)
    {
        i++;
        if(compare(p->data,e)) /* 找到這樣的數據元素 */
        return i;
        p=p->next;
    }
    return 0;
}
Status PriorElem(LinkList L,ElemType cur_e,ElemType *pre_e)
{
    /* 初始條件: 線性表L已存在 *//* 操作結果: 若cur_e是L的數據元素，且不是第一個，則用pre_e返回它的前驅， *//* 返回OK；否則操作失敗，pre_e無定義，返回INFEASIBLE */LinkList q,p=L->next; /* p指向第一個結點 */while(p->next) /* p所指結點有後繼 */
    {
        q=p->next; /* q為p的後繼 */
      	if(q->data==cur_e)
        {
            *pre_e=p->data;
            return OK;
        }
        p=q; /* p向後移 */
    }
    return INFEASIBLE;
}
Status NextElem(LinkList L,ElemType cur_e,ElemType *next_e)
{
    /* 初始條件：線性表L已存在 */
  	/* 操作結果：若cur_e是L的數據元素，且不是最後一個，則用next_e返回它的後繼， */
  	/* 返回OK;否則操作失敗，next_e無定義，返回INFEASIBLE */
  	LinkList p=L->next; /* p指向第一個結點 */
  	while(p->next) /* p所指結點有後繼 */
    {
        if(p->data==cur_e)
        {
            *next_e=p->next->data;
            return OK;
        }
        p=p->next;
    }
    return INFEASIBLE;
}
Status ListInsert(LinkList L,int i,ElemType e) /* 算法2.9。不改變L */
{
    /* 在帶頭結點的單鏈線性表L中第i個位置之前插入元素e */
  	int j=0;
    LinkList p=L,s;
    while(p&&j < i-1) /* 尋找第i-1個結點 */
    {
        p=p->next;
        j++;
    }
    if(!p||j>i-1) /* i小於1或者大於表長 */return ERROR;
    s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新結點 */s->data=e; /* 插入L中 */s->next=p->next;
    p->next=s;
    return OK;
}
Status ListDelete(LinkList L,int i,ElemType *e) /* 算法2.10。不改變L */
{
    /* 在帶頭結點的單鏈線性表L中，刪除第i個元素，並由e返回其值 */
  	int j=0;
    LinkList p=L,q;
    while(p->next&&j< i-1) /* 尋找第i個結點，並令p指向其前嶇 */
    {
        p=p->next;
        j++;
    }
    if(!p->next||j>i-1) /* 刪除位置不合理 */
      	return ERROR;
    q=p->next; /* 刪除並釋放結點 */
  	p->next=q->next;
    *e=q->data;
    free(q);
    return OK;
}
void ListTraverse(LinkList L,void(*vi)(ElemType))  /* vi的形參類型為ElemType，與bo2-1.c中相應函數的形參類型ElemType&不同 */
{
    /* 初始條件：線性表L已存在。操作結果：依次對L的每個數據元素調用函數vi() */
  	LinkList p=L->next;
    while(p)
    {
        vi(p->data);
        p=p->next;
    }
    printf("\n");
}

參考資料

• 1.    C語言如何建立動態鏈表問題  ．腳本之家[引用日期2024-01-01]