最近，从新复习了一下数据结构中比较重要的几个部分，现在把自己的成果记录下来，主要就是仿照严蔚敏的《数据结构》（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;
}

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;
}

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;
}

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;
}

复制代码 代码如下:

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;

}

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;
}

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;
}

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;
}

Status ListTraverse(struct LNode *L,void (*vi)(ElemType))
{
LinkList *p = L->next;
while(p)
{
vi(p->data);
p = p->next;
}
printf("\n");
return OK;
}