数据结构课件第2章线性表A.ppt

1、1上堂课要点回顾上堂课要点回顾数据结构课程数据结构课程涉及数学、计算机硬件和计涉及数学、计算机硬件和计算机软件算机软件数据结构定义数据结构定义指互相有关联的数据元素的指互相有关联的数据元素的集合，用集合，用D_S=( D, S ) 表示。数据结构内容数据结构内容数据的逻辑结构、存储结构数据的逻辑结构、存储结构和运算和运算 算法效率指标算法效率指标时间效率和空间效率时间效率和空间效率 2数据结构课程的内容数据结构课程的内容逻辑结构唯一逻辑结构唯一存储结构不唯一存储结构不唯一运算的实现依赖运算的实现依赖于存储结构于存储结构3近近3周周上课上课内容内容第第2 2章章 线性表线性表第第3 3章章 栈和

2、队列栈和队列第第4 4章章 串串第第5 5章章 数组和广义表数组和广义表 线性结构线性结构若结构是非空有限集，则有且仅有一个开始结若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。直接前趋和一个直接后继。可表示为可表示为：（：（a1 , a2 , , an） 线性结构的定义：线性结构的定义：（逻辑、存储（逻辑、存储和运算）和运算）4第二章第二章 线性表线性表 学习指南学习指南【学习目标【学习目标】1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储

3、结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表顺序表，用后者表示的线性表简称为链表链表。2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。3. 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。4. 结合线性表类型的定义增强对抽象数据类型的理解。 5【重点和难点【重点和难点】链表是本章的重点和难点。扎实的指针操作针操作和内内存动态分配存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。【知识点【知识

4、点】线性表、顺序表、链表【学习指南【学习指南】 本章建议完成的算法设计题为：2.11，2.21，2.19，2.22，2.24，2.27，2.28，2.38 第二章第二章 线性表线性表 学习指南学习指南(续)6线性结构的特点：线性结构的特点： 只有一个首结点和尾结点；只有一个首结点和尾结点； 除首尾结点外，其他结点只有一个直接前驱和一除首尾结点外，其他结点只有一个直接前驱和一个直接后继。个直接后继。线性结构表达式：（线性结构表达式：（a1 , a2 , , an） 线性结构包括线性表、堆栈、队列、字符串、数线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型、最常用的是组等等，其中，最

5、典型、最常用的是-线性表线性表简言之，线性结构反映结点间的逻辑关系是简言之，线性结构反映结点间的逻辑关系是 一对一一对一 的的见第见第2章章7第二章第二章 线性表线性表 2.1 2.1 线性表的类型定义线性表的类型定义 2.2 2.2 线性表的顺序表示和实现线性表的顺序表示和实现 2.3 2.3 线性表的链式表示和实现线性表的链式表示和实现 2.3.1 2.3.1 线性链表线性链表 2.3.2 2.3.2 循环链表循环链表 2.3.3 2.3.3 双向链表双向链表 2.4 2.4 一元多项式的表示及相加一元多项式的表示及相加8线性表：线性表：由一组数据组成，线性表或者是一个空表，由一组数据组成

6、，线性表或者是一个空表，或者可以写成（或者可以写成（a a1 1,a,a2 2, ,a ai i, ,a an n）, ,其中其中a ai i是取自某个是取自某个集合集合S S的元素。当的元素。当1in1in时，数据元素时，数据元素a ai-1i-1称为数据元素称为数据元素a ai i的直接前驱，而称的直接前驱，而称a ai+1i+1为为a ai i的直接后继。线性表中数的直接后继。线性表中数据元素的个数称为该线性表的长度。据元素的个数称为该线性表的长度。2.1 线性表的类型定义线性表的类型定义 9（a1, a2, ai-1，ai, ai1 ，, an）1. 线性表的定义：线性表的定义：用数据

7、元素的有限序列表示用数据元素的有限序列表示n=0时称为时称为数据元素数据元素线性起点线性起点ai的直接前趋的直接前趋ai的直接后继的直接后继下标，下标，是元素的是元素的序号，表示元素序号，表示元素在表中的位置在表中的位置n为元素总个为元素总个数，即表长数，即表长空表空表线性终点线性终点10形式化定义：形式化定义：Linearlist = (D, R)其中：其中：1, 2 , 1,|,0, 1, 1 , 0,|0110niDaaaaRnniDaaDiiiiiiD0为某个数据对象的集合为某个数据对象的集合N为线性表长度为线性表长度11线性表的主要操作 初始化 求长度 取元素 定位 插入 删除12对

8、线性表可进行如下基本运算：对线性表可进行如下基本运算： InitList(&LInitList(&L) )：构造一个空的线性表构造一个空的线性表L L。ListLength(&LListLength(&L) )：返回返回L L数据元素的个数。数据元素的个数。GetElem(L,i,&eGetElem(L,i,&e) )：用用e e返回返回L L中第中第i i个数据元素的值。个数据元素的值。ListInsert(&L,i,eListInsert(&L,i,e) )：在在L L中第中第i i个位置前插入新的数据元素个位置前插入新的数据元素e e，L L的长度加的长度加1 1。ListDelete(

9、&L,i,&eListDelete(&L,i,&e) )：删去删去L L中第中第i i个元素，用个元素，用e e返回其值，返回其值，L L的长度减的长度减1 1。 PriorElem(L,cur_e,&pre_ePriorElem(L,cur_e,&pre_e) )：用用pre_epre_e返回数据元素返回数据元素cur_ecur_e的前驱，如果存在的前驱，如果存在的话。的话。 NextElem(L,cur_e,&next_eNextElem(L,cur_e,&next_e) )：用用next_enext_e返回数据元素返回数据元素cur_ecur_e的后继，如果存在的后继，如果存在的话。的话

10、。 LocateElem(L,e,compareLocateElem(L,e,compare()()：返回返回L L中第一个与中第一个与e e满足关系满足关系compare()compare()的数据元的数据元素的位序。素的位序。0 0表示这种元素不存在。表示这种元素不存在。13例例1 分析分析26 个英文字母组成的英文表个英文字母组成的英文表 （ A, B, C, D, , Z）学号学号姓名姓名性别性别年龄年龄班级班级2001011810205于春梅于春梅女女 182001级电信级电信016班班2001011810260何仕鹏何仕鹏男男 182001级电信级电信017班班2001011810

11、284王王 爽爽女女 182001级通信级通信011班班2001011810360王亚武王亚武男男 182001级通信级通信012班班： ：例例2 分析学生情况登记表分析学生情况登记表数据元素都是记录数据元素都是记录; 元素间关系是线性元素间关系是线性数据元素都是字母数据元素都是字母; 元素间关系是线性元素间关系是线性同一线性表中的元素必定具有相同特性同一线性表中的元素必定具有相同特性14例3、学生健康情况登记表如下：姓 名学 号性 别年龄 健康情况王小林790631 男 18 健康陈 红790632 女 20 一般刘建平790633 男 21 健康张立立790634 男 17 神经衰弱 .

12、. .15例4、一副扑克的点数 （2，3，4，J，Q，K，A） 16从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a a1 1，它，它没有直接前趋，而仅有一个直接后继没有直接前趋，而仅有一个直接后继a a2 2；有且仅有一个终端结点有且仅有一个终端结点a an n，它没有直接后继，而，它没有直接后继，而仅有一个直接前趋仅有一个直接前趋a a n-1n-1；其余的内部结点其余的内部结点a ai i(2in-1)(2in-1)都有且仅有一个都有且仅有一个直接前趋直接前趋a a i-1i-1和一个直接后

13、继和一个直接后继a a i+1i+1。 17 线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。的具体实现则是在存储结构上进行的。抽象数据类型的定义为：抽象数据类型的定义为：P P191918 算法2.1 例2-1 利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。 void union(List &La，List Lb) La-len=ListLength(La); Lb-len=ListLength(Lb); for(I=1;I=Lb-len;I+)

14、 GetElem(Lb，I，e); if(!LocateElem(La，e，equal) ListInsert(La，+La-len，e) / for 19 算法2.2 p21 例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。 此问题的算法如下： 20void MergeList(list la，list lb，list &lc) InitList(lc); I=j=1;k=0; La-len=ListLength(la); Lb-len=ListLength(lb); while(I=la-l

15、en)&(j=lb-len) GetElem(la，I，ai);getelem(lb，j，bj); if(ai=bj)listinsert(lc，+k，ai);+I; elselistinsert(lc，+k，bj);+j; / while 21 while(I=la-len) getelem(la，I+，ai);listinsert(lc，+k，ai); /while 处理la表 while(j=lb-len) getelem(lb，j+，bj);listinsert(lc，+k，bi); / while 处理lb表 / MergeList22练：判断下列叙述的正误：练：判断下列叙述的正误：

16、1. 数据的逻辑结构是指数据元素之间的逻辑关系，数据的逻辑结构是指数据元素之间的逻辑关系，是用户按使用需要建立的。是用户按使用需要建立的。2. 线性表的逻辑结构定义是唯一的，不依赖于计线性表的逻辑结构定义是唯一的，不依赖于计算机。算机。3. 数据结构是指相互之间存在一种或多种关系的数据结构是指相互之间存在一种或多种关系的数据元素的全体。数据元素的全体。4. 线性结构反映结点间的逻辑关系是一对一的。线性结构反映结点间的逻辑关系是一对一的。5.一维向量是线性表，但二维或一维向量是线性表，但二维或N维数组不是。维数组不是。6.“同一数据逻辑结构中的所有数据元素都具有同一数据逻辑结构中的所有数据元素都

17、具有相同的特性相同的特性”是指数据元素所包含的数据项的是指数据元素所包含的数据项的个数都相等。个数都相等。232.2 线性表的顺序表示和实现线性表的顺序表示和实现2.2.1 顺序表的表示顺序表的表示2.2.2 顺序表的实现顺序表的实现2.2.3 顺序表的运算效率分析顺序表的运算效率分析本节小结本节小结作作 业业242.2.1 顺序表的表示顺序表的表示用一组用一组地址连续地址连续的存储单元依次的存储单元依次存储线性表的元素，可通过存储线性表的元素，可通过数组数组VnVn来实现来实现。把逻辑上相邻的数据元素存储在物把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。理上相邻的存储单元中的

18、存储结构。线性表的顺序表示又称为线性表的顺序表示又称为顺序存储结构顺序存储结构或或顺序映像顺序映像。顺序存储定义：顺序存储定义：顺序存储方法：顺序存储方法：简言之，逻辑上相邻，物理上也相邻简言之，逻辑上相邻，物理上也相邻25线性表顺序存储特点：线性表顺序存储特点：1. 逻辑上相邻的数据元素，其物理上也相邻；逻辑上相邻的数据元素，其物理上也相邻；2. 若已知表中首元素在存储器中的位置，则其他元若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（素存放位置亦可求出（利用数组下标利用数组下标）。计算方法）。计算方法是（是（参见存储结构示意图参见存储结构示意图）：）：设首元素设首元素a1的存

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

20、容 元素在表中的位序元素在表中的位序1 1i i2 2n n空闲区空闲区i+1i+1Lb=LOC(a1)b + + L Lb +(i-1)+(i-1)L Lb +(n-1)+(n-1)L Lb +(max-1)+(max-1)L L27一个一维数组，下标的范围是到一个一维数组，下标的范围是到，每个数组元素用相邻的，每个数组元素用相邻的个字节个字节存储。存储。存储器按字节编址，设存储数组元素存储器按字节编址，设存储数组元素 的第一个字节的地址是的第一个字节的地址是，则，则 的第一个字节的地址是的第一个字节的地址是 113例例1因此：因此：LOC( M3 ) = 98 + 5 (3-0) =113

21、解：解：地址计算通式为：地址计算通式为：LOC(ai) = LOC(a1) + L *（i-1）28用数组用数组V来存放来存放26个英文字母组成个英文字母组成的线性表（的线性表（a，b，c，z），写出在顺），写出在顺序结构上序结构上生成生成和和显示显示该表的该表的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;例例229void main(void) /

22、*主函数主函数，字母线性表的生成和输出，字母线性表的生成和输出*/ n=26; /* n是表长，是数据元素的个数，而不是是表长，是数据元素的个数，而不是V的的 实际下标实际下标*/build();display();void display() /*字母线性表的显示，即字母线性表的显示，即读表操作读表操作*/ int i;for(i=0;i=i;j-)for (j=n;j=i;j-) aj+1=aj; aj+1=aj; ai ai=x; =x; n+; n+;/ / 元素后移一个位置元素后移一个位置/ / 插入插入x x / / 表长加表长加1 1 核心语句：核心语句：32由于C语言中的一维数

23、组也是采用顺序存储表示，故可以用数组类型来描述顺序表。用结构类型来定义顺序表类型。 # define ListSize 100 typedef int DataType; typedef struc DataType dataListSize; int length; Sqlist;33 线性表的插入运算是指在表的第I(1in+1)个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an) 变成长度为n+1的线性表 (a1，a i-1，x，ai，an)34算法2.3 P23Void InsertList(Sqlist*L，DataType x，int I) int j;

24、if(Il.length+1) printf(“Position error”); return ERROR ; 35 if(L.length=ListSize) printf(“overflow”); exit(overflow); for(j=L.length-1;j=I-1;j-) L.dataj+1=L.dataj; L.dataI-1=x; L.length+;36在线性表的第在线性表的第i i个位置前插入一个元素的示意图如下：个位置前插入一个元素的示意图如下：121321242830427712132124252830427712345678123456789插入插入252537实

25、现步骤：实现步骤： 将第将第i 至第至第n 位的元素向前移动一个位置；位的元素向前移动一个位置； 表长减表长减1。注意：注意：事先需要判断，事先需要判断，删除位置删除位置i 是否合法是否合法?应当有应当有1in 或或 i=1, n3)3)删除删除 删除删除线性表的第线性表的第i i个位置上的元素个位置上的元素for (j=i+1;j=n;j+)for (j=i+1;jdata=a; p-next=q; 方式方式3：先让指针变量：先让指针变量p指向该结点的首地址，然后用：指向该结点的首地址，然后用： (*p).data=a； (*p).nextq65设设p p为指向链表的第为指向链表的第i i个

26、元素的指针个元素的指针, ,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。至此应可看懂教材P28对于单链表的抽象描述，和教材教材P22关于顺序表的关于顺序表的抽象抽象定义。定义。练习：练习：p-dataai的值的值p-nextai+1的地址的地址66附2：教材教材P22关于顺序表的关于顺序表的抽象抽象定义：定义：Typedef struct /若后面不再用，可省略结构名若后面不再用，可省略结构名 ElemType *elem; /表基址表基址 int length; /表长（特指元素个数）表长（特指元素个数） int listsize; /表当前存储容量（字节

27、数）表当前存储容量（字节数）SqList;Typedef struct Lnode ElemType data; /数据域 struct Lnode *next; /指针域Lnode, *LinkList; / *LinkList为Lnode类型的指针附1：教材P28对于单链表的抽象描述:67补充：结构类型的补充：结构类型的C语言表示法语言表示法 介绍三个有用的库函数（都在介绍三个有用的库函数（都在 中）：中）：sizeof(x)计算变量计算变量x的长度；的长度；malloc(m) 开辟开辟m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p) 释放指针释放指针p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。问问1：自定义结构类型变量自定义结构类型变量test的长度的长度m是多少？是多少？问问2：结构变量结构变量test的首地址的首地址(指针指针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量test？只能借助其指针删除！？只能借助其指针删除！*nextdatatest，长度为长度为m字节字节pmsizeof(test)p(test*)malloc(m)free(p)