1
typedef struct Node {
DataType data;
struct Node *next;
}SLNode,*LinkList;
教材 P37对于线性表的单链
表存储结构描述,
教材问题讨论：
问 1,第一行的 Node 与最后一行的 SLNode是不是一回事？
答 1,不是。前者 Node是结构名，后者 SLNode是对整个
struct类型的一种, 缩写,,是一种, 新定义名,,它只
是对现有类型名的补充，而不是取代。
请注意,typedef不可能创造
任何新的数据类型，而仅仅是
在原有的数据类型中命名一个
新名字，其目的是使你的程序
更易阅读和移植。
2
Typedef struct Lnode {
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
注意,student和 student同名但不同意。同名是为了表述起
来方便。
例如，若结构名为 student，其新定义名缩写也最好写成
student，因为描述的对象相同，方便阅读和理解。
问 2：结构体中间的那个 struct Node是何意？
答 2：在, 缩写, SLNode还没出现之前，只能用原始的
struct Node来进行变量说明。此处说明了指针分量的数据
类型是 struct Node。
typedef struct student {
char name;
int age;
}student,*pointer;
3
例,单链表的建立和输出
例：用单链表结构来存放 26个英文字母组成的线
性表（ a,b,c,…, z）,请写出 C语言程序。
实现思路,先开辟头指针，然后陆续为每个结点开辟存储
空间并及时赋值，后继结点的地址要 提前 送给前面的指针。
先挖, 坑,,后种, 萝
卜, ！
4
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
char data;
struct node *next;
}node;
将全局变量及函数提前说明：
node *p,*q,*head; //一般需要 3个指针变量
int n ; // 数据元素的个数
int m=sizeof(node); /*结构类型定义好之后,每个 node类型 的长
度就固定了,m求一次即可 */
5
新手特别容易忘记！！
{ int i;
head=(node*)malloc(m); //m=sizeof(node) 前面已求出
p=head;
for( i=1; i<26; i++) //因尾结点要特殊处理, 故 i≠26
{ p->data=i+‘a’-1; // 第一个结点值为字符 a
p->next=(node*)malloc(m); //为后继结点, 挖坑, ！
p=p->next； } //让指针变量 P指向后一个结点
p->data=i+‘a’-1; //最后一个元素要单独处理
p->next=NULL ;} //单链表尾结点的指针域要置空 ！
void build( ) //字母链表的生成 。 要一个个慢慢链入
6
{p=head;
while (p) //当指针不空时循环 （ 仅限于 无头结点 的情况 ）
{printf("%c",p->data);
p=p->next; //让指针不断, 顺藤摸瓜,
}
}
讨论：要统计链表中数据元素的个数，该如何改写？
sum++;
sum=0;
void display() /*字母链表的输出 */
7
void main( )
{
build( );
display( );
}
问：上述建立的单链表带头结点吗？
8
二、单链表的操作实现
定义单链表结点的结构体如下,
typedef struct Node
{
DataType data;
struct Node *next;
}SLNode;
１、初始化
void ListInitiate(SLNode **head) ／ *初始化 */
{ /*如果有内存空间，申请头结点空间并使头指针 head指向头
结点 */
if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL)
exit(1);
(*head)->next = NULL; /*置链尾标记 NULL */
}
9
２、求单链表中数据元素的个数
int ListLength(SLNode *head)
{
SLNode *p = head; /*p指向头结点 */
int size = 0; /*size初始为 0*/
while(p->next != NULL) /*循环计数 */
{
p = p->next;
size ++;
}
return size;
}
10
在链表中插入一个元素 X 的示意图如下：
Xq
a b
p
链表插入的核心语句：
Step 1,q->next=p->next;
Step 2,p->next=q ；
p->next s->next
思考,Step1和 2能互换么？
X 结点的生成方式：
m=sizeof(SLNode);
q=(SLNode *)malloc(m);
q->data=X ;
q->next=?
ba
p
插 入 X
３、向单链表中插入一个元素
11
int ListInsert(SLNode *head,int i,DataType x)
{ SLNode *p,*q; int j; p = head; j = -1;
while(p->next != NULL && j < i - 1) {
(1) p = p->next; j++; }
if(j != i - 1){
printf("插入位置参数错！ "); return 0; }
(2) if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL)
exit(1);
q->data = x;
(3) q->next = p->next; p->next = q; (4)
return 1; } 注：此单链表是带头结点的
12
在链表中删除某元素 b的示意图如下：
ca b
p
删除动作的核心语句 （要借助辅助指针变量 q）：
q = p->next; //首先保存 b的指针，靠它才能找到 c；
p->next=q->next; //将 a,c两结点相连，淘汰 b结点；
free(q) ； //彻底释放 b结点空间
p->next
思考,省略 free(q)语句 行不行？
(p->next) -> next
× ×
q
４、从 单链表中删除一个元素
13
int ListDelete(SLNode *head,int i,DataType *x)
{ SLNode *p,*s; int j;
(1) p = head; j = -1;
while(p->next != NULL && p->next->next!= NULL
&& j < i - 1)
{ p = p->next; j++; }
if(j != i - 1)
{ printf(“插入位置参数错！, ); return 0; }
(2) s = p->next;
*x = s->data;
(3) p->next = p->next->next;
free(s);
return 1;
}
14
三、单链表的操作效率分析
（ 1） 查找
因线性链表只能顺序存取，即在查找时要从头指针找起，
查找的时间复杂度为 O(n)。
时间效率分析
（ 2） 插入和删除
因线性链表不需要移动元素，只要修改指针，仅就插入或删
除而言，时间复杂度为 O(1)。
但是，如果要在单链表中进行在某结点 前 插或删除操作，
因为要 从头查找前驱 结点，所以一般情况下,单链表插
入和删除操作 的时间复杂度是 O(n)（同顺序表）。
15
四、应用举例
例１、编程实现：建立一个单链表，首先依次输入数
据元素１,２,…,10,然后删除数据元素５，最后依次
显示当前表中的数据元素。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int DataType;
#include "LinList.h"
重点是链表
16
void main(void)
{ SLNode *head;
int i,x;
ListInitiate(&head);
for(i=0;i<10;i++){
if(ListInsert(head,i,i+1) == 0)
{ printf("错误 ! \n"); return; }
}
if(ListDelete(head,4,&x) == 0) {
printf("错误 ! \n");
return;
}
17
for(i = 0; i < ListLength(head); i++)
{
if(ListGet(head,i,&x) == 0)
{ printf("错误 ! \n");
return; }
else printf("%d ",x);
}
Destroy(&head);
}
18
五、循环单链表
xhead a0 an……
循环链表 示意图：
循环单链表是单链表的另一种形式，其结构特点是链表中
的最后一个结点的指针域不再是结束标记，而是指向整个链表
的第一个结点，从而使链表形成一个环。
问：带头结点的循环单链表的插入、删除算法如何写？
head
19
例 2,试用 C语言编写一个算法，将一循环单链表就
地逆置。
操作前：（ a1,a2,… ai-1,ai,ai+1, …,a n）
操作后：（ an,… ai+1, ai,ai-1, …,a 2,a1 ）
20
q=head;
p=head->next; //有头结点
while(p!=head) //循环单链表
{ r=p->next;
p->next=q; //前驱变后继
q=p;
p=r; } //准备处理下一结点
head->next=q; // 以 an为首
q=head;
p=head->next; //有头结点
while(p!=head) //循环单链表
{ s=q;
q=p;
p=p->next;
q->next=s;} //准备处理下一结点
p->next=q; // 以 an为首
（要求同学们根据下面算法的核心语句，编写一
个完整算法）
算法的核心语句
A 或 B
21
例 3,试写一算法，实现顺序表的就地逆置，即利用原表
的存储空间将线性表（ a1,a2,……,.,an）逆置为（ an，
an-1,……,,a1）。
参考程序：
void inverse (SeqList *L )
{ DataType temp; int i;
for ( int i=0; i<=( L->size-1)/2;i++ )
{ //循环次数为表长的一半
temp=L->list[i]; L->list[i]= L->list[L->size-i-1];
L->list[L->size-i-1]=temp;
}
}
22
作业
P55 2-7,2-9,2-17
typedef struct Node {
DataType data;
struct Node *next;
}SLNode,*LinkList;
教材 P37对于线性表的单链
表存储结构描述,
教材问题讨论：
问 1,第一行的 Node 与最后一行的 SLNode是不是一回事？
答 1,不是。前者 Node是结构名，后者 SLNode是对整个
struct类型的一种, 缩写,,是一种, 新定义名,,它只
是对现有类型名的补充，而不是取代。
请注意,typedef不可能创造
任何新的数据类型，而仅仅是
在原有的数据类型中命名一个
新名字，其目的是使你的程序
更易阅读和移植。
2
Typedef struct Lnode {
ElemType data;
struct Lnode *next;
}Lnode,*LinkList;
注意,student和 student同名但不同意。同名是为了表述起
来方便。
例如，若结构名为 student，其新定义名缩写也最好写成
student，因为描述的对象相同，方便阅读和理解。
问 2：结构体中间的那个 struct Node是何意？
答 2：在, 缩写, SLNode还没出现之前，只能用原始的
struct Node来进行变量说明。此处说明了指针分量的数据
类型是 struct Node。
typedef struct student {
char name;
int age;
}student,*pointer;
3
例,单链表的建立和输出
例：用单链表结构来存放 26个英文字母组成的线
性表（ a,b,c,…, z）,请写出 C语言程序。
实现思路,先开辟头指针，然后陆续为每个结点开辟存储
空间并及时赋值，后继结点的地址要 提前 送给前面的指针。
先挖, 坑,,后种, 萝
卜, ！
4
#include<stdio.h>
#include<stdlib.h>
typedef struct node{
char data;
struct node *next;
}node;
将全局变量及函数提前说明：
node *p,*q,*head; //一般需要 3个指针变量
int n ; // 数据元素的个数
int m=sizeof(node); /*结构类型定义好之后,每个 node类型 的长
度就固定了,m求一次即可 */
5
新手特别容易忘记！！
{ int i;
head=(node*)malloc(m); //m=sizeof(node) 前面已求出
p=head;
for( i=1; i<26; i++) //因尾结点要特殊处理, 故 i≠26
{ p->data=i+‘a’-1; // 第一个结点值为字符 a
p->next=(node*)malloc(m); //为后继结点, 挖坑, ！
p=p->next； } //让指针变量 P指向后一个结点
p->data=i+‘a’-1; //最后一个元素要单独处理
p->next=NULL ;} //单链表尾结点的指针域要置空 ！
void build( ) //字母链表的生成 。 要一个个慢慢链入
6
{p=head;
while (p) //当指针不空时循环 （ 仅限于 无头结点 的情况 ）
{printf("%c",p->data);
p=p->next; //让指针不断, 顺藤摸瓜,
}
}
讨论：要统计链表中数据元素的个数，该如何改写？
sum++;
sum=0;
void display() /*字母链表的输出 */
7
void main( )
{
build( );
display( );
}
问：上述建立的单链表带头结点吗？
8
二、单链表的操作实现
定义单链表结点的结构体如下,
typedef struct Node
{
DataType data;
struct Node *next;
}SLNode;
１、初始化
void ListInitiate(SLNode **head) ／ *初始化 */
{ /*如果有内存空间，申请头结点空间并使头指针 head指向头
结点 */
if((*head = (SLNode *)malloc(sizeof(SLNode))) == NULL)
exit(1);
(*head)->next = NULL; /*置链尾标记 NULL */
}
9
２、求单链表中数据元素的个数
int ListLength(SLNode *head)
{
SLNode *p = head; /*p指向头结点 */
int size = 0; /*size初始为 0*/
while(p->next != NULL) /*循环计数 */
{
p = p->next;
size ++;
}
return size;
}
10
在链表中插入一个元素 X 的示意图如下：
Xq
a b
p
链表插入的核心语句：
Step 1,q->next=p->next;
Step 2,p->next=q ；
p->next s->next
思考,Step1和 2能互换么？
X 结点的生成方式：
m=sizeof(SLNode);
q=(SLNode *)malloc(m);
q->data=X ;
q->next=?
ba
p
插 入 X
３、向单链表中插入一个元素
11
int ListInsert(SLNode *head,int i,DataType x)
{ SLNode *p,*q; int j; p = head; j = -1;
while(p->next != NULL && j < i - 1) {
(1) p = p->next; j++; }
if(j != i - 1){
printf("插入位置参数错！ "); return 0; }
(2) if((q = (SLNode *)malloc(sizeof(SLNode))) == NULL)
exit(1);
q->data = x;
(3) q->next = p->next; p->next = q; (4)
return 1; } 注：此单链表是带头结点的
12
在链表中删除某元素 b的示意图如下：
ca b
p
删除动作的核心语句 （要借助辅助指针变量 q）：
q = p->next; //首先保存 b的指针，靠它才能找到 c；
p->next=q->next; //将 a,c两结点相连，淘汰 b结点；
free(q) ； //彻底释放 b结点空间
p->next
思考,省略 free(q)语句 行不行？
(p->next) -> next
× ×
q
４、从 单链表中删除一个元素
13
int ListDelete(SLNode *head,int i,DataType *x)
{ SLNode *p,*s; int j;
(1) p = head; j = -1;
while(p->next != NULL && p->next->next!= NULL
&& j < i - 1)
{ p = p->next; j++; }
if(j != i - 1)
{ printf(“插入位置参数错！, ); return 0; }
(2) s = p->next;
*x = s->data;
(3) p->next = p->next->next;
free(s);
return 1;
}
14
三、单链表的操作效率分析
（ 1） 查找
因线性链表只能顺序存取，即在查找时要从头指针找起，
查找的时间复杂度为 O(n)。
时间效率分析
（ 2） 插入和删除
因线性链表不需要移动元素，只要修改指针，仅就插入或删
除而言，时间复杂度为 O(1)。
但是，如果要在单链表中进行在某结点 前 插或删除操作，
因为要 从头查找前驱 结点，所以一般情况下,单链表插
入和删除操作 的时间复杂度是 O(n)（同顺序表）。
15
四、应用举例
例１、编程实现：建立一个单链表，首先依次输入数
据元素１,２,…,10,然后删除数据元素５，最后依次
显示当前表中的数据元素。
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int DataType;
#include "LinList.h"
重点是链表
16
void main(void)
{ SLNode *head;
int i,x;
ListInitiate(&head);
for(i=0;i<10;i++){
if(ListInsert(head,i,i+1) == 0)
{ printf("错误 ! \n"); return; }
}
if(ListDelete(head,4,&x) == 0) {
printf("错误 ! \n");
return;
}
17
for(i = 0; i < ListLength(head); i++)
{
if(ListGet(head,i,&x) == 0)
{ printf("错误 ! \n");
return; }
else printf("%d ",x);
}
Destroy(&head);
}
18
五、循环单链表
xhead a0 an……
循环链表 示意图：
循环单链表是单链表的另一种形式，其结构特点是链表中
的最后一个结点的指针域不再是结束标记，而是指向整个链表
的第一个结点，从而使链表形成一个环。
问：带头结点的循环单链表的插入、删除算法如何写？
head
19
例 2,试用 C语言编写一个算法，将一循环单链表就
地逆置。
操作前：（ a1,a2,… ai-1,ai,ai+1, …,a n）
操作后：（ an,… ai+1, ai,ai-1, …,a 2,a1 ）
20
q=head;
p=head->next; //有头结点
while(p!=head) //循环单链表
{ r=p->next;
p->next=q; //前驱变后继
q=p;
p=r; } //准备处理下一结点
head->next=q; // 以 an为首
q=head;
p=head->next; //有头结点
while(p!=head) //循环单链表
{ s=q;
q=p;
p=p->next;
q->next=s;} //准备处理下一结点
p->next=q; // 以 an为首
（要求同学们根据下面算法的核心语句，编写一
个完整算法）
算法的核心语句
A 或 B
21
例 3,试写一算法，实现顺序表的就地逆置，即利用原表
的存储空间将线性表（ a1,a2,……,.,an）逆置为（ an，
an-1,……,,a1）。
参考程序：
void inverse (SeqList *L )
{ DataType temp; int i;
for ( int i=0; i<=( L->size-1)/2;i++ )
{ //循环次数为表长的一半
temp=L->list[i]; L->list[i]= L->list[L->size-i-1];
L->list[L->size-i-1]=temp;
}
}
22
作业
P55 2-7,2-9,2-17
