数据结构(c语言版)_严蔚敏版_第2章_线性表_信大(第2讲)讲解

1、绪论要点回顾 数据结构定义数据结构定义指互相有关联的数据元素的集合，用指互相有关联的数据元素的集合，用 D_S=( D, S ) 数据结构是相互之间存在着一种或多种特定关系的数据元素数据结构是相互之间存在着一种或多种特定关系的数据元素 的集合。的集合。 数据数据结构结构内容内容数据的数据的逻辑逻辑结构、结构、存储存储结构和结构和运算运算 算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率 数据结构课程的内容 逻辑结构唯一逻辑结构唯一 存储结构不唯一存储结构不唯一 运算的实现依赖运算的实现依赖 于存储结构于存储结构 近期 上课 内容 第第2 2章章 线性表线性表 第第3 3章章 栈和队

2、列栈和队列 第第4 4章章 串串 第第5 5章章 数组和广义表数组和广义表 线性结构 (逻辑、存储和运算) 若结构是非空有限集，则有且仅有一个开始结 点和一个终端结点，并且所有结点都最多只有一个 直接前趋和一个直接后继。 可表示为：(a1 , a2 , , an) 线性结构的定义： 线性结构的特点： 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱和一 个直接后继。个直接后继。 线性结构包括线性表、堆栈、队列、字符串、数 组等等，其中，最典型、最常用的是- 简言之，线性结构反映结点间的逻辑关系是 一对一 的 第二

3、章线性表 第第2章章 线性表线性表 2.1 线性表的类型定义线性表的类型定义 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 线性表的链式表示和实现线性表的链式表示和实现 图图2.1 线性表的逻辑结构线性表的逻辑结构 2.1 线性表的类型定义线性表的类型定义 2.1.1 线性表的逻辑结构线性表的逻辑结构 （a1, a2, ai-1， ，ai, ai1 ， ，, an） 线性表的定义：线性表的定义：是是n个数据元素的个数据元素的有限序列有限序列 n=0时称为时称为 数据元素数据元素 表头表头ai的直接的直接前趋前趋ai的直接的直接后继后继 下标，下标，是元素的是元素的 序号，表示元

4、素序号，表示元素 在表中的位置在表中的位置 n为元素总个为元素总个 数，即表长数，即表长 空表空表 表尾表尾 例例1 1 分析分析26 26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z） 学号学号姓名姓名性别性别年龄年龄班级班级 541407010126541407010126于春梅于春梅女女 18 1820142014级计科 级计科1 1班班26 26号 号 541407010127541407010127何仕鹏何仕鹏男男 18 1820142014级计科 级计科1 1班班27 27号 号 541407010128541407010128 王王 爽 爽

5、女女 18 1820142014级计科 级计科1 1班班28 28号 号 541407010129541407010129王亚武王亚武男男 18 1820142014级计科 级计科1 1班班29 29号 号 ： ： 例例2 分析学生情况登记表分析学生情况登记表 数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性 数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性 同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性 线性表的特点可概括如下：线性表的特点可概括如下： 同一性同一性 有穷性有穷性 有序性有序性 线性表是最常见的数据结构，因为矩阵、

6、数组、字符串、线性表是最常见的数据结构，因为矩阵、数组、字符串、 堆栈、堆栈、 队列等都符合线性条件。队列等都符合线性条件。 练：判断下列叙述的正误： 1. 数据的逻辑结构是指数据元素之间的逻辑关系，数据的逻辑结构是指数据元素之间的逻辑关系， 是用户按使用需要建立的。是用户按使用需要建立的。 2. 线性表的逻辑结构定义是唯一的，不依赖于计线性表的逻辑结构定义是唯一的，不依赖于计 算机。算机。 3. 数据结构是指相互之间存在一种或多种关系的数据结构是指相互之间存在一种或多种关系的 数据元素的全体。数据元素的全体。 4. 线性结构反映结点间的逻辑关系是一对一的。线性结构反映结点间的逻辑关系是一对一

7、的。 5. 一维向量是线性表，但二维或一维向量是线性表，但二维或N维数组不是。维数组不是。 6. “同一数据逻辑结构中的所有数据元素都具有相同一数据逻辑结构中的所有数据元素都具有相 同的特性同的特性”是指数据元素所包含的数据项的个是指数据元素所包含的数据项的个 数都相等。数都相等。 例例2-1 两个集合两个集合La和和Lb的合并的合并 假设两个集合假设两个集合La7,2,3Lb8,4,5,6怎样将他们合并呢？怎样将他们合并呢？ 1，首先知道，首先知道La的长度是的长度是3和和Lb的长度是的长度是4 2，之后把，之后把Lb集合中的元素依次和集合中的元素依次和La中的元素进行比对中的元素进行比对

8、形成一个循环，首先形成一个循环，首先Lb中的中的8与与La的元素依次比对，的元素依次比对，8与所有与所有La中中 元素不同，将元素不同，将8插入插入La中，中， 3，2与与2相同进入相同进入Lb的下一个元素，都不相同，的下一个元素，都不相同， 之后将元素合并到之后将元素合并到La中，中， 例例2-2 两个非递减有序的线性表两个非递减有序的线性表La和和Lb的合并的合并 如如La2,4,6Lb4,7,9,10合并合并 1，定义，定义Lc,长度是长度是La长度长度+Lb长度长度 2，La中中2与与Lb中中4，把小，把小La中的中的2的插入的插入Lc，La进入下一个进入下一个 元素元素 3, La中

9、中4与与Lb中中4比较，把比较，把La的的4插入插入Lc,LaLb都下一个元素都下一个元素 4,La中中6与与Lb中中7比较，把小的比较，把小的La中的中的6的插入的插入Lc，La进入下进入下 一个元素，无元素了一个元素，无元素了 5，就将，就将Lb中剩余元素依次加入中剩余元素依次加入Lc中中 47910 246La Lb Lc 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 用一组地址连续的存储单元依次用一组地址连续的存储单元依次 存储线性表的元素，可通过存储线性表的元素，可通过数组数组来实现。来实现。 把逻辑上相邻的数据元素存储在

10、物把逻辑上相邻的数据元素存储在物 理上理上相邻相邻的存储单元中的存储结构。的存储单元中的存储结构。 顺序存储定义：顺序存储定义： 顺序存储方法：顺序存储方法： 简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻 线性表顺序存储特点： 1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻； 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利 用数组下标）。计算方法是：用数组下标）。计算方法是： 设首元素设首元素a1的存放地址为的存放地址为LOC(a1)（称为首地址），设每

11、个元素占用存储空称为首地址），设每个元素占用存储空 间（地址长度）为间（地址长度）为L字节，字节，则表中任一数据元素的则表中任一数据元素的存放地址存放地址为：为： LOC(ai) = LOC(a1) + L *(i-1) LOC(ai+1) = LOC(ai)+L 它是一种它是一种随机存取随机存取的数据结构。的数据结构。 注意：C语言中的数组的下标从0开始， 即：Vn的有效范围是V0Vn-1 线性表的顺序存储结构示意图线性表的顺序存储结构示意图 a a1 1 a a2 2 a ai i a ai+1 i+1 a an n 地址地址 内容内容 元素在表中的位序元素在表中的位序 1 1 i i 2

12、 2 n n 空闲区空闲区 i+1i+1 L b=LOC(a1) b + + L L b +(i-1)+(i-1)L L b +(n-1)+(n-1)L L 一个一维数组，下标的范围是到，每个数组一个一维数组，下标的范围是到，每个数组 元素用相邻的元素用相邻的个字节个字节存储。存储器按字节编址，设存储存储。存储器按字节编址，设存储 数组元素数组元素 的第一个字节的地址是的第一个字节的地址是9898，则，则 的第的第 一个字节的地址是一个字节的地址是 113 例1 1 因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113 解：解：地址计算通式为：地址计算通式为： LOC(ai)

13、 = LOC(a1) + L *（i-1） 用数组V V来存放2626个英文字母组成的线 性表(a(a，b b，c c，z)z)，写出在顺序结构上生 成和显示该表的C C语言程序。 void build() /*字母线性表的生成，即建表操作*/ int i; V0=a; for(i=1;i=n-1;i+) Vi=Vi-1+1; 核心语句： 法1 Vi= Vi-1+1; 法2 Vi=a+i; 法3 Vi=97+i; 例2 void build(); void display(); #define n 26 int Vn; void main(void) /*主函数，字母线性表的生成和输出*/ b

14、uild(); display(); void display() /*字母线性表的显示，即读表操作*/ int i; for(i=0;i=n-1;i+) printf(%c,Vi); printf(n); 执行结果： a b c d e f g h i j k l m n o p q r s t u v w x y z 2626个字母 另一种写法 #include int main() int i; for(i=0;i=i;j-) aj+1=aj; ai=x; n+; / 元素后移一个位置 / 插入x / 表长加1 4. 删除操作删除操作 指将表的第指将表的第i(1in)个元素删去，使长度为

15、个元素删去，使长度为n的线性表的线性表(e1，, ei-1，ei，ei+1，en)变成长度为变成长度为n-1的线性表的线性表(e1，, ei-1， ei+1，en)。 实现步骤：实现步骤： 将第将第i +1至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。 注意：注意：事先需要判断，事先需要判断，删除位置删除位置i 是否合法是否合法? 图图2.4 顺序表中删除元素顺序表中删除元素 例如：线性表例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第删除第5 个元素，则需将第个元素，则需将第6个元素到第个元素到第10个元素依次

16、向前移动个元素依次向前移动 一个位置，如图一个位置，如图2.4所示。所示。 for (j=i+1;jdata=a; p-next=q; 方式3：先让指针变量p指向该结点的首地址，然后用： (*p).data=a； (*p).nextq 单链表可以由头指针唯一确定单链表可以由头指针唯一确定。 单链表的存储结构描述如下：单链表的存储结构描述如下： typedeftypedef structstruct LNodeLNode ElemType ElemType data;data; struct struct LNodeLNode * *next;next; LNode ,*LinkList; /*

17、 LinkList为结构指针类型为结构指针类型*/ 假设假设L是是LinkList型的变量，则型的变量，则L是一个结构指针，即单链表的是一个结构指针，即单链表的 头指针，它指向表中第一个结点。头指针，它指向表中第一个结点。 若若L=NULL（对于带头结点的单链表为（对于带头结点的单链表为L-next=NULL），）， 则表示单链表为一个空表，其长度为则表示单链表为一个空表，其长度为0。 若不是空表，对于带头结点的单链表若不是空表，对于带头结点的单链表L，p=L-next指向指向 表中的第一个结点表中的第一个结点a1，即，即p-data=a1，而，而p-next-data=a2。 其余依此类推。

18、其余依此类推。 1. 查找查找 算法描述：算法描述： 查找第查找第i个结点，从头指针个结点，从头指针L出发，顺着链域扫描。出发，顺着链域扫描。 用指针用指针p指向当前扫描到的结点，用指向当前扫描到的结点，用j做计数器，累计当前扫做计数器，累计当前扫 描过的结点数。描过的结点数。 当当j = i时，指针时，指针p所指的结点就是要找的第所指的结点就是要找的第i个结点。个结点。 2.3.2 单链表上的基本运算单链表上的基本运算 2. 单链表插入操作单链表插入操作 算法描述：算法描述： 要在第要在第i个位置插入元素个位置插入元素e，需要找到第，需要找到第i-1个结点并由指个结点并由指 针针p指示，然后

19、申请一个新的结点并由指针指示，然后申请一个新的结点并由指针s指示，其数据域指示，其数据域 的值为的值为e。 修改第修改第i-1个结点的指针使其指向个结点的指针使其指向s，使，使s结点的指针域指结点的指针域指 向原第向原第i个结点。个结点。 插入：插入：s-next=p-next; p-next=s; 在链表中插入一个元素的示意图如下：在链表中插入一个元素的示意图如下： x x s b ba a p a ab b p 插入步骤（即核心语句）：插入步骤（即核心语句）： Step 1Step 1：s-next=p-next; Step 2Step 2：p-next=s ； p-next s-next

20、 元素元素x x结点应预先生成：结点应预先生成： s=(LinkList)malloc(m);s=(LinkList)malloc(m); s-data=x;s-data=x; s-next=p-next;s-next=p-next; p-next=s;p-next=s; 3. 3. 删除 在链表中删除某元素的示意图如下：在链表中删除某元素的示意图如下： c ca ab b p 删除步骤（即核心语句）：删除步骤（即核心语句）： q = p-next; /保存保存b的指针，靠它才能指向的指针，靠它才能指向c p-next=q-next; /a、c两结点相连两结点相连 free(q) ； /删除删

21、除b结点，彻底释放结点，彻底释放 p-next 思考：思考： 省略省略free(q)语句语句行不行？行不行？ (p-next) - next 4. 建立单链表建立单链表 图图2.10 头插法建立单链表图示头插法建立单链表图示 2） 尾插法建表尾插法建表 图图2.11 尾插法建表图示尾插法建表图示 rs；r 始终指向单链表的表尾 L (a) 建空表 c1 s s 指向新申请的结点空间 sdatac 1 (b) 申请新结点并赋值 Lc1 s (c) 插入第一个结点 Lc2c1 r r r nexts； (d) 插入第二个结点 sr 5.5.应用举例：两个链表的归并应用举例：两个链表的归并( (教材

22、教材P31)P31) 算法要求： 已知：线性表 A、B，分别由单链表 LA , LB 存储， 其中数据元素按值非递减有序排列， 要求：将 A ，B 归并为一个新的线性表C , C 的数据 元素仍按值非递减排列 。设线性表 C 由单链表 LC 存储。 假设：A=(3，5，8，11)，B=(2，6，8，9，11) 预测：合并后 C =( 2 , 3 , 5 , 6 , 8 , 8 , 9 , 11，11 ) 用链表可表示为： 3 3 5 511 11 / 8 8 La 2 2 6 611 11 / 8 8 Lb 9 9 2 2 3 3 6 6 5 5 Lc 8 8 811 / 911 头结点 算法

23、分析： 算法主要包括：搜索、比较、插入三个操作： 搜索：需要两个指针搜索两个链表； 比较：比较结点数据域中数据的大小； 插入：将两个结点中数据小的结点插入新链表。 La 3 5 8 11 Lb 2 6 8 119 Pa Pb Pa Pb Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点 Lc Pa 3 Pc Pa 5 Pc 11 Pc 2 Pb Pc Pa 思考： 1、不用Lc，直接把La表插到Lb表中；或者把Lb表 插到La表中，如何编程？ 2、要求不能有重复的数据元素，如何编程？ 6 6，其他形式的链表 讨论1： 用一维数组也能存放链表吗？怎样实现？ 答：能。只要定义一个结构类型(含

24、数据域和指示域)数 组，就可以完全描述链表，这种链表称为静态链表。 注：数据域含义与前面相同，指示域相当于前面的指针 域。 静态链表的插入与删除操作与普通链表一样， 不需要移动元素，只需修改指示器就可以了。 具体实现过程见教材P31-34。 讨论讨论2 2： 链表能不能首尾相连？怎样实现？链表能不能首尾相连？怎样实现？ 答：能。只要将表中最后一个结点的指针域指向头结 点即可 (P-next=head;) 。这种形成环路的链表称 为循环链表。 特别：带头结点的 空循环链表样式 H 参见教材P35 特点： 图图2.13 循环链表循环链表 L a1ai 1aian L (a) 带头结点的空循环链表

25、(b) 带头结点的循环单链表的一般形式 a1ai 1aian rear rear *(rearnext) * (c) 采用尾指针的循环单链表的一般形式 讨论讨论3 3： 单链表只能查找结点的直接后继，单链表只能查找结点的直接后继， 能不能查找直接前驱？如何实现？能不能查找直接前驱？如何实现？ 答：能。只要把单链表再多开一个指针域即可(例 如用*next和*prior;) 。 双向链表在非线性结构(如树结构)中将大量使用。 priordatanext 这种有两个指针的链表称为双向链表。其特点是 可以双向查找表中结点。参见教材P3539。 特别：带头结点的空双向链表样式： / 图图2.14 双向链

26、表的结点结构双向链表的结点结构 priordatanext 前驱指针域数据域后继指针域 由于在双向链表中既有前向链又有后向链，寻找任一由于在双向链表中既有前向链又有后向链，寻找任一 个结点的直接前驱结点与直接后继结点变得非常方便。个结点的直接前驱结点与直接后继结点变得非常方便。 设指针设指针p指向双链表中某一结点，则有下式成立：指向双链表中某一结点，则有下式成立： p-prior-next = p = p-next-prior 图图2.15 双向循环链表图示双向循环链表图示 L a1a2a3 L (a) 空的双向循环链表 (b) 非空的双向循环链表 1. 双向链表的前插操作双向链表的前插操作

27、图图2.16 双向链表插入操作双向链表插入操作 ab s p c 2. 双向链表的删除操作双向链表的删除操作 算法描述：算法描述： 图图2.17 双向链表的删除操作双向链表的删除操作 abc p 要点回顾 1. 链表的表示(包括有关术语、结构数据类型等) 2. 链表的实现(建表、输出、修改、插入、删除) 了解：其它链表形式了解：其它链表形式 静态链表 循环链表 双向链表 提问： 怎样读取头结点数据域中的信息？ 链表的操作要用指针？ 用L-data 仅两个作用：找位置 和改地址！ 顺序表和链表的比较顺序表和链表的比较 1. 基于空间的考虑基于空间的考虑 在链表中的每个结点，除了数据域外，还要额外

28、设置指针在链表中的每个结点，除了数据域外，还要额外设置指针 （或光标）域，（或光标）域，从存储密度来讲，这是不经济的从存储密度来讲，这是不经济的。所谓存储密度。所谓存储密度 (Storage Density), 是指结点数据本身所占的存储量和整个结点结是指结点数据本身所占的存储量和整个结点结 构所占的存储量之比，构所占的存储量之比， 即即 存储密度存储密度=结点数据本身所占的存储量结点数据本身所占的存储量/结点结构所占的存储总结点结构所占的存储总 量量 一般地，存储密度越大，存储空间的利用率就越高。显一般地，存储密度越大，存储空间的利用率就越高。显 然，顺序表的存储密度为然，顺序表的存储密度为1，而链表的存储密度小于，而链表的存储密度小于1。 由此可知，由此可知，当线性表的长度变化不大，易于事先确定其当线性表的长度变化不大，易于事先确定其 大小时，为了节约存储空间，宜采用顺序表作为存储结构。大小时，为了节约存储空间，宜采用顺序表作为存储结构。 2. 基于时间的考虑基于时间的考虑 顺序表是由向量实现的，它是一种随机存取结构，对表中任顺序表是由向量实现的，它是一种随机存取结构，对表中任 一结点都可以在一结点都可以在O(1)时间内直接地存取，而链表中的结点，需从时间内直接地存取，而链表中的结点，需