资源简介

(共24张PPT)
C 语言程序设计
2023
翻转课堂实用教程
10.4 链表
1
2
3
链表的链式存储
链表的节点
链表的组织形式
链表的基本操作
知识点
链表案例分析
案例分析
链表相关练习题
练习题
前面章节中，学生会候选人、应届毕业生的信息采用什么方式存储？
若进行删除、插入的操作，会涉及到非常多移动的操作，降低了程序执行的效率。
C 语言提供了一种采用动态存储分配的构造数据类型——链表，大大提高了程序解决此类问题的时间效率。
10.4.1链表知识点
结构体数组的存储方式
优点：便于对信息进行查询、修改、输出操作。
如何更好解决删除、插入的问题？
链条示意图
10.4.1链表知识点
先看下链条：
由多个金属环串联在一起的
前一个金属环扣住下一个金属环。
链表就是一种链式存储的结构，
由多个相同结构体类型的节点串联一起
节点之间相互关联
链表分为单向链表和双向链表，本节只讲解单向链表。
10.4.1链表知识点
每个节点都是一个结构体类型的变量，两部分组成：
① 节点本身的数据部分，称为数据域；
② 指向下一个节点的指针，称为指针域。
以保存29 47 84 90这4个数据为例。
链表的组织形式——节点
10.4.1链表知识点
例如：定义struct node结构体类型作为链表节点的类型名，定义如下：
typedef struct node{
int data; //数据域的值
struct node* next; //指针域的值，next指向下一个链表节点
}Node;
typedef用法？
next指针的类型？
链表的组织形式——节点
data
next
10.4.1链表知识点
（1）头指针，链表一般使用头指针head来表示，方便后续对链表的访问和操作。
（2）节点，节点分为第一个节点和其他节点。
无头节点的单向链表：
带头节点的单向链表：
涉及的概念：
第一个节点，为头结点。
存储第一个实际数据的节点，为首元节点。
最后一个节点称为尾节点，尾节点后续没有节点，其指针域的值为NULL。
链表包括头指针和节点
10.4.1链表知识点
（1）malloc和free函数
链表中的节点，逻辑上：连续的，
物理上：是随机存放的。
每个节点的内存空间，通过动态存储分配的。使用stdlib.h头文件中函数。
malloc：动态分配内存空间
free：释放用malloc动态分配的内存空间
链表的基本操作
10.4.1链表知识点
（1）malloc和free函数
malloc函数原型如下：
void *malloc(unsigned int size);
在动态存储区分配一个大小为size字节的连续空间。
成功：返回分配好的存储空间的首地址；
失败：返回值NULL
链表的基本操作
举例：
double *pd = (double *)malloc( sizieof (double));
1、增加程序可移植性
2、强制转化为需要的类型
10.4.1链表知识点
（1）malloc和free函数
free函数原型如下：
void free(void* p);
释放掉指针p指向的内容空间。free函数要和malloc函数成对使用。
链表的基本操作
举例：
struct node *curNode = (struct node *)malloc( sizieof (struct node));
…
free(curNode);
maloc函数申请的空间，不会自动释放。
必须由free函数来释放。
10.4.1链表知识点
（2）单向链表的新建
链表的基本操作
创建单链表，保存29 47 84 90这4个数据。
头结点
head
rear
29
首元结点
curNode
rear->next
47
rear->next
10.4.1链表知识点
//生成含头节点的单向链表
for (i=0; i//创建新节点curNode，为其动态分配存储空间
Node *curNode =(Node*)malloc(sizeof(struct node));
curNode->data=array[i];
//此时rear指向当前链表的尾节点
rear->next=curNode; //将新节点curNode加入到链表中
//curNode成为了新的尾节点 ，更新rear指向curNode
rear=curNode;
}
rear->next = NULL;
return head; // 将头指针返回
}
typedef struct node{
int data; //存储数据域的值
struct node* next; //存储指针域的值，next指向下一个链表节点
}Node;
#define N 4
Node * initLink(){
int i=0;
int array[N] = {29,47,84,90};
//创建头结点
Node * head=(Node*)malloc(sizeof(struct node));
//声明一个rear指针，指向链表的尾节点
Node * rear=head;
（2）单向链表的新建，代码段
10.4.1链表知识点
（3）判断单向链表是否为空
带头结点单向链表只有头节点，没有后续节点时，被认为单向链表为空
int emptyLink(Node *head)
{
return (head->next==NULL);
}
链表的基本操作
NULL
head
data
next
头结点
10.4.1链表知识点
（4）单项链表的插入
两个节点A和B间插入一个新节点C时，让C与A和B分别建立逻辑联系。
步骤如下：
将C节点的next指针指向B节点
将A节点的next指针指向C节点
链表的基本操作
head
84
29
A结点
90
47
头结点
B结点
35
C结点
第一步
第二步
节点间是如何建立逻辑联系？
通过前节点next指针指向下一个节点，建立逻辑联系
NULL
10.4.1链表知识点
//在第position个位置处插入数据newData,position从1开始计数
Node *insertLink(Node *head,int newData,int position){
//因为插入数据时，需要知道插入位置的前一个节点，定义p为前一个节点指针
Node *p = head,*newNode;
int i = 1;
//先找到插入位置的前一个节点
while(i < position) {
p=p->next;
if (p == NULL) {
printf("插入位置无效\n");
return head;
}
i++;
}
//找到插入位置，此时p为插入位置的前一个节点
newNode = (Node*)malloc(sizeof(struct node));
newNode->data = newData;
newNode->next = p->next;
p->next = newNode;
return head;
}
（4）单向链表的插入，代码段
头节点的存在，不管新插入的节点，是在首元节点前、还是中间的位置，还是在尾节点后，操作步骤都是一样的。
10.4.1链表知识点
（5）单项链表的遍历
从链表头开始，依次访问单向链表中的每个节点，并将节点的数据值输出，直到链表尾。
链表的基本操作
head
84
29
90
47
NULL
p
void displayLink(Node *head){
Node *p = head->next; //p指向首元节点
while(p!=NULL){ //当p不为空，则没有到达链表尾
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
10.4.1链表知识点
（6）单项链表的删除
假设其前驱节点为A节点，则对C节点的删除，需要三步操作步骤：
①遍历单向链表，找到需要删除的节点C，并记录前驱节点A。
② A节点的next指针指向C节点的next指针
③ 删除C节点
链表的基本操作
head
84
29
A结点
90
47
头结点
35
C结点
第一步
第二步
NULL
第②、 ③ 步能颠倒吗？
第三步
不能！
10.4.1链表知识点
//删除链表中数据值为delData的节点。
void delNode(Node *head,int delData){
Node *p = head,*curNode= head->next; //curNode指向首元节点
while(curNode!=NULL){
if(delData == curNode->data){ //此时p指向A节点，curNode指向C节点
p->next = curNode->next;
free(curNode);
curNode = p->next;
}else{
p = curNode;
curNode=p->next;
}
}
}
（6）单向链表的删除，代码段
10.4.1链表知识点
（7）单向链表的查找
遍历单向链表的过程中，比较某个节点的值是否和被查找数据一致，直到找到或者遍历到链表尾（某个节点NULL）结束。
链表的基本操作
//在链表中查找数据值为needData的节点，找到了则返回该节点的地址，否则返回NULL
Node *searchNode(Node *head,int needData){
Node *p = head,*curNode= head->next; //p指向首元节点
while(curNode!=NULL){
if(nee dData == curNode->data){
return curNode;
}
p = curNode;
curNode=p->next;
}
return NULL;
}
10.4.1链表知识点
（8）单向链表的修改
链表的基本操作
/*在链表中查找数据值为oldData的节点，找到后修改成newData，
找到了则返回该节点的地址，否则返回NULL */
Node *modifyNode(Node *head,int oldData,int newData){
Node *p = head,*curNode= head->next;
while(curNode!=NULL){
if(oldData == curNode->data){
curNode->data = newData;
return curNode;
}
p = curNode;
curNode=p->next;
}
return NULL;
}
10.4.1链表案例分析
案例10.4.1用链表结构来存储候选人信息，根据学号查看某个候选人的信息，
再修改指定候选人的票数。
要求：输入候选人的信息，包括学号、姓名、班级、得票数，直到输入一个-1结束输入。再输入一个候选人学号，编写函数，查询该候选人的信息，发现该候选人的票数不对，再根据这个候选人的学号修改其得票数。
10.4.3链表课堂练习题
课堂练习题10.4.1：创建一个整型链表，保存3 5 1 9 7 6 8 2 0 4这十个数据，并将这些数据输出。
课堂练习题10.4.2：在案例10.4.1的基础上，对功能进行扩展，编写根据学号删除候选人的函数、编写根据学号查找候选人信息的函数。
课堂练习题10.4.3：现有一个递增的整数序列，再给定一个整数x，若整数序列中不存在
x，则将x插入到整数序列中，并保证插入后，序列仍然时递增的。
谢谢观看
程序设计基础

展开更多......

收起↑