C语言_链表PPT

}
单链表的插入
9
3、链表的插入(头指针的情况下）
对于插入有以下几种情况 在一个空链表上插入一个元素。 （即要插入位置前方和后方均无元素） 从链表表头处插入一个元素 （即要插入的位置前方无元素，后方有元素） 从链表结尾处处插入一个元素 （即要插入的位置后方五元素，前方有元素） 从链表的中间插入 （即要插入的位置前方和后方均有元素） 其中第三种情况可以按照第四种情况处理，但有一定特殊性所以将 其分开 注意：产生新的节点必须用malloc或者calloc开辟空间
... NULL
4、链表的建立
链表的建立就是链表从无到有的过程 建立一个头节点，并指向NULL，就建立了一个空的链 表
建立有n个元素的链表有三个阶段 建立头节点并指向NULL（建立了一个空的链表） 插入第一个元素（插入的第一种情况） 在表头或者表尾连续插入其他n-1个元素 （反复执行插入的第二，第三种情况）
在空链表上插入一个元素
p
data
h
p
h
data
NULL
实现的语句：
p->next=NULL; h=p;
在链表的表头插入一个元素
p
data
h
... NULL
p
data
h
... NULL
p
data
h
... NULL
完成插入后 表头指针要指向新的表头节点 实现的语句：
p->next=h; h=p;
在链表结尾出插入一个元素
在链表结尾出插入一个元素
p
data
首先要用一个循环语句找到q
q
q=h;
h
...
NULL
while(q->next!=NULL)
q=q->next;
p
然后执行插入语句：
data
p->next=NULL;
q
q->next=p;
h
...
NULL
p
data
q
h
...
NULL
在链表中间插入一个元素
pห้องสมุดไป่ตู้
data
指针字段，数据字段表示元素的本身信息，指针字段指明下个元素的 位置。单链表用来表示线性结构。例如线性表（a1,a2,…,an)可以表 示为：
head
a1
a2
……
an /\
C语言定义链表的结构如下 typedef struct Node {
int data; struct Node * next; }NODE;
科学 和谐 创新 自主
C语言链表
王艳春
单链表
2
单链表
单链表的定义 单链表的基本操作
遍历（递归和非递归遍历） 插入（插入4种情况，重点） 建立 删除 将一个链表排序 将两个有序链表合并 将一个链表逆置 约瑟夫问题
1、单链表的定义
最简单的是单链表，单链表中每个节点由两个字段组成：数据字段和
q
o
h ...
p
data
q
o
h ...
p
data
q h ...
... NULL ... NULL
假如被插入位置的后方特征是
数据项为x 则可以执行循环语句
q=h; while(q->next->data!=x) {
q=q-next; } 确保找到被插入地方的前方节点q ,然后执行插入语句： p->next=q->next; q->next=p; 注意语句顺序
建立带有单独头节点的链表，先建立头节点
struct Node* create() { struct Node *head,*p,*q; int n; head=(struct Node *)malloc(sizeof(struct Node)); head->next=NULL; //第一阶段，建立一个头节点，并指向NULL p=head; while(1) { printf("请输入一个正整数,0代表结束:"); scanf("%d",&n); if (n<=0) break; else { q=(struct Node *) malloc(sizeof(struct Node)); q->data=n;//产生要插入的节点 p->next=q;//执行插入的过程，第一次插入的时候p=head所以就是head>next=q; q->next=NULL; p=q; } } return head;
void lprint (NODE *head) { if(head!=NULL) { printf(“%d\t”,head->data); lprint(head->next);
} 许多问题中，有时候为了操作方便，需要在第一个节点之前增加一个
特殊的节点，称为头节点，它的data字段不含信息或根据问题的需 要存放特殊信息。
h
q
... p
data
h
q
...
p
data
h
q
...
这种情况不涉及头节点的变动 假如被插入位置的后方特征是 数据项为x 则可以执行循环语句 ... NULL q=h; while(q->next->data!=x) {
q=q-next; } 确保找到被插入地方的前方节点q ... NULL ,然后执行插入语句： p->next=q->next; q->next=p; 注意语句顺序
2、链表的遍历（显示链表）
一个非递归算法
以下函数disp()用于显示头节点为*h的链表的所有节点 数据域。
void disp(struct Node *h) { struct Node *p=h; printf("输出链表:"); if(p==NULL) printf("空表\n"); else { while (p->next!=NULL) { printf("%4d",p->data); p=p->next; } printf("%4d\n",p->data); }
带有头节点的单链表
一般各种资料表示链表有两种，一种是带头节点的，一种 是使用头指针的（不带头节点的）。
带头节点的 就是有一个专门的头节点h，它的后继指向链表的第一 个元素。
使用头指针的 没有专门的头节点，只有一个指针h指向链表的第一个 元素
单链表的遍历
6
2、链表的遍历（显示链表）
设head为链表的头指针，首先从head所指的节点开始打印，沿着链 的方向向右遍历，直到到最后一个节点，下面是一个打印链表的递归 函数。
... NULL
3、链表的插入(有单独头节点的情况下）
由于增加了表头节点，不用象没有头节点的情况时， 区分是否插入点在表头，所以对于插入只有两种情况 从链表结尾处处插入一个元素 （即要插入的位置后方五元素，前方有元素） 从链表的中间插入 （即要插入的位置前方和后方均有元素） 其中第一种情况可以按照第二种情况处理，但有一定 特殊性（语句的顺序可以换）所以将其分开
p
data
h
q
...
NULL
p
data
h
q
...
NULL
不涉及头节点的变动 首先要用一个循环语句找到q q=h; while(q->next!=NULL)
q=q->next; 然后执行插入语句：
q->next=p; p->next=NULL;
p
data
NULL
h
q
...
在链表中间插入一个元素
p
data