链表：
链表是C语言中另外一个难点。牵扯到结点、动态分配空间等等。用结构作为链表的结点是非常适合的，例如：
| struct node { int data; struct node *next; }; |
其中next是指向自身所在结构类型的指针，这样就可以把一个个结点相连，构成链表。 数据挖掘研究院
链表结构的一大优势就是动态分配存储，不会像数组一样必须在定义时确定大小，造成不必要的浪费。用malloc和free函数即可实现开辟和释放存储单元。其中，malloc的参数多用sizeof运算符计算得到。
链表的基本操作有：正、反向建立链表；输出链表；删除链表中结点；在链表中插入结点等等，都是要熟练掌握的，初学者通过画图的方式能比较形象地理解建立、插入等实现的过程。
| typedef struct node { char data; struct node *next; }NODE; /*结点*/ 正向建立链表： NODE *create() { char ch="a"; NODE *p,*h=NULL,*q=NULL; while(ch<"z") { p=(NODE *)malloc(sizeof(NODE)); /*强制类型转换为指针*/ p->data=ch; if(h==NULL) h=p; else q->next=p; ch++; q=p; } q->next=NULL; /*链表结束*/ return h; } |
逆向建立：
| NODE *create() { char ch="a"; NODE *p,*h=NULL; while(ch<="z") { p=(NODE *)malloc(sizeof(NODE)); p->data=ch; p->next=h; /*不断地把head往前挪*/ h=p; ch++; } return h; } |
用递归实现链表逆序输出：
| void output(NODE *h) { if(h!=NULL) { output(h->next); printf("%c",h->data); } } |
插入结点（已有升序的链表）：
| NODE *insert(NODE *h,int x) { NODE *new,*front,*current=h; while(current!=NULL&&(current->data<x)) /*查找插入的位置*/ { front=current; current=current->next; } new=(NODE *)malloc(sizeof(NODE)); new->data=x; new->next=current; if(current==h) /*判断是否是要插在表头*/ h=new; else front->next=new; return h; } |
删除结点：
NODE *delete(NODE *h,int x){
NODE *q,*p=h;
while(p!=NULL&&(p->data!=x))
{
q=p;
p=p->next;
}
if(p->data==x) /*找到了要删的结点*/
{
if(p==h) /*判断是否要删表头*/
h=h->next;
else q->next=p->next;
free(p); /*释放掉已删掉的结点*/
}
return h;
}
