第02章 第02章 线性表

序言

1. 内容介绍

本章详细介绍了线性表的定义及其两种存储结构、l顺序表的增删查改，和链表的增删查改

2. 理论目标

• 掌握线性表的定义及其两种存储结构，，
• 掌握顺序表(线性表的顺序存储结构)的增删查改
• 掌握链表(线性表的链式存储结构)的增删查改

3. 实践目标

• 顺序表和链表增删查改的代码实现

4. 实践案例

无

5. 内容目录

• 1.线性表的定义及其两种存储结构
• 2.顺序表的增删查改
• 3.链表的增删查改

第1节 线性表的定义及其两种存储结构

1.1 线性表的定义

线性表是信息表的一种形式，表中数据元素之间满足线性关系，是一种最基本、最简单的数据结构类型。

线性表的特征：

1. 对非空表,a0是表头,无前驱；

2. an-1是表尾,无后继；

3. 其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。

线性表的例子

设有一个线性表L={1,2,3,4,5,6};

使用二元组描述L=(D,R),则

D={1 , 2 , 3 , 4 , 5 , 6}(n=6)

R={<1,2> , <2,3> , ❤️,4> , <4,5> , <5,6>}

设线性表 L=(a0,a1, ……,an-1)，对 L的基本

算法有：

建立一个空表、判断表是否为空、求表长、取表中某个元素、插入、删除等。

1.2 顺序表的简介

线性表作为一种基本的数据结构类型，在计算机存储器中的映象（或表示）一般有两种形式，一种是顺序存储，一种是链式存储。

顺序存储结构特点：

(1)逻辑上相邻的元素 ai, ai+1，其存储位置也是相邻的；

(2)对数据元素ai的存取为随机存取或按地址存取。

(3)存储密度高。存储密度D=(数据结构中元素 所占存储空间)/（整个数据结构所占空间）。

顺序存储结构的不足：

对表的插入和删除等运算的时间复杂度较差；要求系统提供一片较大的连续存储空间。

在C语言中，一维数组的元素也是存放于一块连续的存储空间中，故可借助于C语言中一维数组类型来描述线性表的顺序存储结构。

1.3 链式表的简介

线性表的链式存储结构，叫链表。

将线性表L=(a0,a1,……,an-1)中各元素分布在存储器的不同存储块，称为结点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表中元素ai的结点形式如图：

结点的数据域(data)存放数据元素ai，而指针域(next) 是一个指针，指向ai的直接后继ai+1所在的结点。于是，线性表L=( a0,a1,……,an-1)的结构如图：

第2节 顺序表的增删查改

2.1 如何实现顺序表

一次考试后,成绩表中漏掉了张三的成绩，该怎么办？

观察下图

–分配固定长度的数组空间：最大长度为MAXSIZE

–顺序表的长度：length

顺序表结构体代码实现如下

顺序表需要的三个属性

存储空间的起始位置：数组data

顺序表的最大存储容量：数组长度MAXSIZE

顺序表的当前长度：length

顺序表的优点

节省空间，方便随机存储

2.2 如何实现线性表的插入

如果插入位置不合理，抛出异常

如果顺序表已满，抛出异常

如果插入位置合理，从最后一个位置开始

向前遍历到要插入的位置，将这些元素

都向后移动一个位置

插入元素

表长加1

第 1 步：如果插入位置不合理，抛出异常

第 2 步：如果顺序表已满，抛出异常

第 3 步：如果插入位置合理，逐步向后移动

第 3 步：如果插入位置合理，逐步向后移动

第 4 步：插入元素

第 5 步：表长加1

使用顺序表存储5个数，在第3个位置插入数据6

使用顺序表存储10个学生的成绩，在第3个位置插入一个学生的成绩100

2.3顺序表插入的时间复杂度

平均移动次数

• 如果表为空，或者查找位置不

合理，抛出异常

• 查找位置合理，取出查找元素

第 1 步：如果表为空，或者查找位置不合理，抛出异常

第 2 步：取出查找的元素

顺序表查找的应用

使用顺序表存储5个数，获取第3个数

2.4顺序表查找的时间复杂度

2.5如何实现顺序表的删除

•如果表为空，或者删除位置不合理，抛出异常

• 删除位置合理，取出删除元素

• 从删除元素的下一个位置开始遍历到最后一个位置，将这些元素都向前移动一个位置

•表长减1

第 1 步：如果表为空，或者删除位置不合理，抛出异常

第 2 步：删除位置合理，取出删除元素

第 3 步：逐步移动元素

第 4 步：表长减1

定义一个存储有5个元素的顺序表，删除第2个元素

•使用顺序表存储10个学生的成绩，删除第3个学生的成绩

  

•定义一个存储5个元素的顺序表，使用函数删除用户指定元素

思考：为什么没有实现删除功能？

   

使用顺序表存储10个学生的成绩，调用函数删除用户指定同学的成绩

2.6 顺序表删除操作的时间复杂度

平均移动次数

2.7 如何实现顺序表的修改

顺序表的修改是指修改表中的第 position 个元素

第 1 步：如果表为空，或者修改位置不合理，抛出异常

第 2 步：修改位置合理，直接修改该元素

定义一个存储有5个元素的顺序表，将第1个元素的值修改为100

使用顺序表存储10个学生的成绩，将第3个学生的成绩修改为73

•定义一个存储有5个元素的顺序表，调用函数将用户指定元素修改为用户指定的值

•

•使用顺序表存储10个学生的成绩，调用函数将用户指定学生的成绩修改为用户指定的值

2.8顺序表修改操作的时间复杂度

2.8 线性表顺序存储结构的优缺点

优点

开始实验

第3节

缺点

第4节 链表的增删查改

本章案例：使用单链表制作一个成绩表，完成插入和查找功能

3.1 为什么使用结点

如何把数据元素和连接关系存储在一起呢？

3.2 什么是结点

除数据元素外：有一个或多个成员用来存储连接关系

定义:结点是用来把数据元素和连接关系存储在一起的结构类型变量

3.3 如何使用结点

定义结点结构类型: 告诉计算机数据元素类型是什么

创建结点: 告诉计算机为结点分配空间

结点的初始化、赋值和连接: 向结点存放数据并连接

结点的插入删除: 不影响其它结点

3.4 结点的作用

定义结点结构类型: 告诉计算机数据元素类型是什么

创建结点: 告诉计算机为结点分配空间

结点的初始化、赋值和连接: 向结点存放数据并连接

结点的插入删除: 不影响其它结点

•1•结点可以把数据元素按逻辑顺序连接起来

•2•结点间连接关系变动只影响直接相连的结点，不影响其它结点

3.5 什么是链表

链表的内涵

1逻辑相邻，物理不必相邻

2用结点存储数据元素和连接关系

  

定义:链表是采用链式存储结构存储的线性表

约定

•1•我们后面统一以带头结点的链表来举例。

•2•结点编号从1开始，也就是第一个正常结点编号为1

•3•头结点是个虚设的结点，编号0，数据域用来存储链表长度

3.6 什么是单链表

定义:单链表是只能从第一个结点开始单向访问其后继结点的链表

单链表的基本操作有创建、遍历、插入、删除、查找、修改、清空等

3.7 单链表的创建和初始化

链表的创建和初始化: 创建长度为0的单链表

单链表的遍历: 从头开始，逐个访问每一个结点

n案例：成绩表的创建和遍历

n案例效果

案例要求

1.创建一个用来存储学生成绩的单链表

2.把长度初始化为0

3.写出遍历这个单链表的函数并调用

3.8 单链表的插入

单链表的定位插入: 实现

案例：添加成绩和查看成绩表

案例效果

案例要求

1.创建一个数据元素为int类型的单链表

2.用定位插入的方式插入5个成绩

3.遍历输出单链表中的成绩

  

3.9 单链表的查找

单链表的定位查找: 探索

单链表的定位查找: 实现

案例：查找成绩表中第三位同学的成绩

案例效果

案例要求

1.创建一个数据元素为int类型的单链表

2.查找成绩表中第三位同学的成绩并输出

3.10 单链表的删除

使用单链表制作一个成绩表，完成删除和修改功能

    

第 1 步：如果链表无效或删除位置pos无效，终止操作

第 2 步：如果删除位置pos有效，则从头开始查找到第pos-1个结点

第 3 步：将第pos个结点指针域的值赋值给第pos-1个结点的指针域（★）

第 4 步：释放第pos个结点，链表长度减1

•实例：删除单链表L中的第3个结点

案例分析

1.通过调用初始化单链表函数、定位插入新结点函数来创建含有6个结点的单链表

2.调用遍历函数输出单链表中的数据元素

3.调用删除函数删除单链表中的第3个结点并遍历输出删除后的单链表

  

•删除成绩表中第二位同学的成绩

案例分析

1.依次调用初始化单链表函数、定位插入新结点函数、遍历函数、删除函数、遍历函数

2.注意：可以在上一单元的代码基础上继续完成本案例

3.11 单链表的修改

•实例：将单链表L中第3个结点的数据域修改为33

案例分析
1.通过调用初始化单链表函数、定位插入新结点函数来创建含有6个结点的单链表
2.调用遍历函数输出单链表中的数据元素
3.调用修改函数修改单链表中的第3个结点并遍历输出修改后的单链表

效果图

案例要求

将成绩表中的第2位同学的成绩修改为99

  

总结

什么是单链表的整表创建？

头插法思路

尾插法思路

尾插法代码演示

什么是单链表的整表删除

整表删除思路

代码演示

     

开始实验