最近，從新復習了一下數據結構中比較重要的幾個部分，現在把自己的成果記錄下來，主要就是仿照嚴蔚敏的《數據結構》（C 語言版），中的例子和後面的習題進行改編的。首先，是單鏈表的各種實現，其中，包含了一些常考的知識點。例如，單鏈表的逆置，單鏈表的合並，找到單鏈表的中間節點等的算法實現。
下面這個是單鏈表的結構體的定義：
代碼如下：
typedef struct LNode
{
ElemType data;
struct LNode *next;
}LinkList;
下面的基本的單鏈表的操作：其中，有一些宏，沒有給出他們的一些定義，者可以通過，嚴蔚敏的《數據結構》（C 語言版），查看得到。
代碼如下：
/* 功能：構建一個空的帶頭節點的單鏈表*/
Status InitList (struct LNode **L)
{
(*L) = (struct LNode *)malloc(sizeof(struct LNode)); //產生頭節點
if(!*L)
exit(OVERFLOW);
(*L)->next = NULL;
return OK;
}
/*銷毀線性表*/
Status DestroyList(struct LNode *L)
{
struct LNode *q;
while(L)
{
q = L->next;
free(L);
L = q;
}
return OK;
}
/*將L重置為空表*/
Status ClearList(struct LNode *L)
{
LinkList *p,*q;
p = L->next;
while(p)
{
q = p->next;
free(p);
p = q;
}
L->next = NULL;
return OK;
}
/*判斷鏈表是否為空表*/
Status ListEmpty(LinkList *L)
{
if(L->next)
{
return FALSE;
}
else
{
return TRUE;
}
}
/*返回單鏈表中元素的個數*/
int ListLength(struct LNode *L)
{
int i=0;
LinkList *p = L->next;
while(p)
{
i++;
p = p->next;
}
return i;
}
/* L為帶頭節點的單鏈表的頭指針，當第i個元素存在時，其值賦給e,並返回OK */
Status GetElem(struct LNode *L,int i,ElemType *e)
{
int j=1;
LinkList *p = L->next;
while(p && j<i)
{
p = p->next;
j++;
}
if(!p || j>i)
return ERROR;
*e = p->data;
return OK;
}
/*返回L中第一個與e滿足關系compare()的數據元素的位序，
若給存在返回值為0，compare()是數據元素的判定函數*/
int LocateElem(struct LNode *L,ElemType e,Status(*compare) (ElemType,ElemType))
{
int i =0;
LinkList *p = L->next;
while(p)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
代碼如下：
/*所cur_e是L中的數據元素，且給就第一個，則用pre_e返回它的前驅*/
Status PriorElem(struct LNode *L,ElemType cur_e,ElemType *pre_e)
{
LinkList *q,*p=L->next;
while(p->next)
{
q = p->next;//q指向p的後繼
if(q->data == cur_e)
{
*pre_e = p->data;
return OK;
}
p = q;
}
return INFEASIBLE;
}
/* 若cur_e是L中的數據元素，且不是最後一個，則用next_e返回它的後繼*/
Status NextElem(struct LNode *L,ElemType cur_e,ElemType *next_e)
{
LinkList *p;
p = L->next;
while(p->next)
{
if(p->data == cur_e)
{
* next_e = p->next->data;
return OK;
}
p = p->next;
}
return INFEASIBLE;
}
/* 在帶頭節點的單鏈表L中的第i個位置之前插入元素e*/
Status ListInsert(struct LNode *L,int i,ElemType e)
{
int j =0;
struct LNode *p=L,*s=NULL;
while(p && j<i-1)
{
p=p->next;
j++;
}
if(!p || j>i-1)
return ERROR;
s = (struct LNode *)malloc(sizeof(struct LNode));
if(!s)
printf("malloc error~\n");
// p->next = s;
s->data = e;
// p->next = s;
s->next = p->next;
p->next = s;
//s->next = NULL;
// p = s;
return OK;
}
/*在帶頭節點的單鏈表中刪除第i個元素，並有e返回其值*/
Status ListDelete(LinkList *L,int i,ElemType *e)
{
LinkList *p=L,*q;
int j=0;
while(p->next && j< i-1)
{
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;
}
/* 依次對L的每個元素調用vi(),打印輸出語句*/
Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
LinkList *p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
return OK;
}
