链表：
链表是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;
}
