1. 链表的定义

由结点链接形成链表。结点类型是一种特殊的结构类型，在这种类型中包含有指向自身结构类型的指针域。

若每个结点只有一个指针域，则链接起来形成单链表。

struct IntNode {

int data;　　　　　　　　//值域

struct IntNode* next; //指针域

};

符号常量NULL的值为0。在stdio.h中定义。

具有值为48、56、72和83等4个结点的单链表。

表头结点：链表中第1个结点。

表头指针：指向链表中第1个结点的指针。

表尾结点：链表中最后一个结点。表尾结点的指针域的值为NULL。

后继结点：next域所指向的结点

前驱结点：一个结点的前（上、左）一个结点。

2. 链表的建立

struct IntNode *p1, *p2;

p1=malloc(sizeof(struct IntNode));

p2=malloc(sizeof(struct IntNode));

p1->data=10; p1->next=p2; p2->data=20; p2->next=0;

在p1结点前插入值为5的新结点。

struct IntNode *p;

p=malloc(sizeof(struct IntNode));

p->data=5; p->next=p1;

3．建立一个链表的算法

struct IntNode* createList() {

　int x;

　int n=sizeof(struct IntNode);

　struct IntNode *f, *p;

　f=p=malloc;　　　　　　//建立附加结点

　printf("输入一批整数(-1止)\n");

　while(1) {

　　scanf("%d",&x)

　　if(x==-1) break;

　　p=p->next=malloc; //向表尾插入一个新结点

　　p->data=x;

}

p->next=NULL;

return f->next;

}

链表的示意简图表示：f->next->25 ->36 ->12 ->48 ->20 0

4. 链表的遍历

从表头指针所指的第一个结点开始，输出每个结点的data域的值，由当前结点的next域得到下一个结点。

void travList(struct IntNode* f){
  while(f) {
    printf("%d ",f->data);
    f=f->next;
  }
  printf("\n");
}

上机调试建立和遍历链表算法的程序

#include
#include
struct IntNode {  //结点类型定义
  int data;
  struct IntNode* next;
};
struct IntNode* createList(); 
void travList(struct IntNode* f);

void main() {
  struct IntNode *p1;
  p1=createList();
  travList(p1);
}
    25 36 48 12 60 -1  //输入
    25 36 48 12 60     //输出

5. 对链表的数据处理

int CountList(struct IntNode* f)
{  //统计链表f的长度
  int c=0;  //用c作为统计变量
  while(f) {
    c++;
    f=f->next;
  }
  return c;
}       // CountList(p1)返回5