电子2-3线性表.ppt

1、学时数：48（3216） 学 分： 3 教 材：严蔚敏等，数据结构（C语言版），清华大学出版社，1997年4月 （配题集） 参考书： 1 殷人昆等，数据结构（用面向对象方法与C+描述），清华大学出版社，1999年7月。￥26 2 殷人昆等，数据结构习题解析，清华大学出版社，2002年4月。￥26 3 李春保，数据结构习题与解析（C语言篇），清华大学出版社，2001年1月。￥28 4 丁宝康等，数据结构自学考试指导，清华大学出版社， 2001年5月。￥23,内 容 安 排,实验：课内上机（16规定内容）+课外上机（24平时作业中编程题验证）,数据结构课程的内容,逻辑结构唯一 存储结构不唯一 运算

2、的实现依赖于存储结构,线性结构的定义：,若结构是非空有限集，则有且仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。 可表示为：（a1 , a2 , , an）,简言之，线性结构反映结点间的逻辑关系是 的。,特点 只有一个首结点和尾结点； 特点 除首尾结点外，其他结点只有一个直接前驱和一个直接后继。,线性结构包括：线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是-,线性表,一对一 (1:1),第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,（a1, a2, ai-1，ai, a

3、i1 ，, an）,2.1 线性表的逻辑结构,线性表的定义：用数据元素的有限序列表示,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析： 数据元素都是同类型（字母）， 元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性 ！,例1 分析26 个英文字母组成的英文表是什么结构。,“同一数据逻辑结构中的所有数据元素都具有相同的特性”是指数据元素所包含

4、的数据项的个数都相等。,是指各元素具有相同的数据类型,试判断下列叙述的正误：,2.2 线性表的顺序表示和实现,2.2.1 顺序表的表示 2.2.2 顺序表的实现 2.2.3 顺序表的运算效率分析,2.2.1 顺序表的表示,用一组地址连续的存储单元依次存储线性表的元素。,把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。,线性表的顺序表示又称为顺序存储结构或顺序映像。,顺序存储定义：,顺序存储方法：,特点：,逻辑上相邻的元素，物理上也相邻,可以利用数组Vn来实现,注意：在C语言中数组的下标是从0开始，即： Vn的有效范围是从 V0Vn-1,1. 逻辑上相邻的数据元素，其物理上也相邻；

5、 2. 若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组Vn的下标）。,设首元素a1的存放地址为LOC(a1)（称为首地址）， 设每个元素占用存储空间（地址长度）为L字节， 则表中任一数据元素的存放地址为： LOC ( ai+1 ) = LOC( ai ) + L LOC ( ai ) = LOC( a1 ) + L *（i -1）,对上述公式的解释如图所示,线性表顺序存储特点：,地址 内容 元素在表中的位序,1,i,2,n,空闲区,i+1,L,b=LOC(a1),b + L,b +(i-1)L,b +(n-1)L,b +(max-1)L,LOC ( ai ) = LOC

6、( a1 ) + L *（i -1）,线性表的顺序存储结构示意图,设有一维数组，下标的范围是到，每个数组元素用相邻的个字节存储。存储器按字节编址，设存储数组元素的第一个字节的地址是，则的第一个字节的地址是多少？,113,但此题要注意下标起点略有不同： LOC( M3 ) = 98 + 5 (4-1) =113,解：已知地址计算通式为：,LOC(ai) = LOC(a1) + L *（i-1）,例1,课堂讨论：,顺序表的“宏观”算法该如何书写？ 采用抽象数据类型来表示,顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？ 采用动态分配的一维数组,线性表的定义（见教材P19）,

7、ADT List 数据对象：D=ai | aiElemSet, i=1,2,n,n0 数据关系：R1= | ai 1, ai D, i=2,n 基本操作：,初始化、撤销、清空、判空； 求表长、表头、表尾、前趋、后继； 读元素、查找（含定位）、遍历； 插入、删除, ADT List,线性表的基本操作如何表示？ （见教材P19）,InitList( / “看”表中全部元素（遍历）,初始化、撤销、清空、判空； 求表长、表头、表尾、前趋、后继； 读元素、查找（含定位）、遍历； 插入、删除,动态数组如何实现（见教材P22和P24）,#define List_Init_Size 100 /初始空间 #de

8、fine List_Increment 10 /分配增量 L.listsize= List_Init_Size; If(L.length=L.listsize) L.listsize=List_Increment; ;,P23的malloc()函数与P24的realloc()函数有什么不同？,动态数组简介,先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。,#define LIST_INIT_SIZE 100 /存储空间的初始分配量 #define LISTINCREMENT 10/存储空间的分配增量 Typedef struct ElemTy

9、pe *elem; /表基址(用指针*elem表示） int length; /表长度（表中有多少个元素） int listsize; /当前分配的表尺寸（字节单位） SqList;,注：三个分量可简写为：L.elem L.length L.listsize,存储结构描述如下（见教材P22）：,sizeof(x)算符的意思是：计算变量x的长度(字节数),malloc (m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。,Status InitList_Sq( SqList /InitList_Sq,动态创建一个空顺序表的算法：,2.2.2 顺序表的实现（或操作）,数据结

10、构的基本运算： 插入、删除、查找、排序,realloc (*p, newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。,动态顺序表的插入算法 Status ListInsert_Sq(SqList / 检验i 值的合法性,if ( L.length L.listsize ) /若表长超过表尺寸则要增加尺寸 newbase = ( ElemType* ) realloc ( L.elem , (L.listsize + LISTINCREMENT )* sizeof ( ElemType ) );,if (newbase=NULL )ex

11、it( OVERFLOW ) ; /分配失败则退出并报错 L.elem = newbase ; /重置新基址 L.listsize = L.listsize + LISTINCREMENT ; /增加表尺寸,q = /插入e,+L.length ; /增加1个数据元素，则表长+1,return OK ; /ListInsert_Sq,动态数组的核心是realloc(void *ptr, newsize)函数！,在线性表的第i个位置前插入一个元素的示意图如下：,插入25,动态顺序表的删除算法 Status ListDelete_Sq(SqList / i 值不合法，返回,p= /被删除元素的值赋

12、给 e,q=L.elem+L.length-1; / q 是表尾的位置 for(+p; p=q; p+) *(p-1) = *p; /待删元素后面的统统前移,-L.length; /表长 - 1,return OK; /ListDelete_Sq,删除顺序表中某个指定的元素的示意图如下：,顺序表插入和删除的完整程序请同学们自编。,链式存储结构,2.2节小结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素。 解决问题的思路：改用另一种线性存储方式：,顺序表操作的典型例子（自学）,

13、教材例2-1：求两个线性表的“并”，即： LA U LB = ?,算法至少有两种： LA和LB都是无序表，则从LB中取元素逐一与LA中所有元素比较，相同则不插入LA； 若LA和LB已经是有序表，则“归并”的时间效率可以大大提高。,2.2.3 顺序表的运算效率分析,算法时间主要耗费在移动元素的操作上，因此 计算时间复杂度的基本操作（最深层语句频度） T(n)= O (移动元素次数) 而移动元素的个数取决于插入或删除元素的位置.,思考：若插入在尾结点之后，则根本无需移动（特别快）； 若插入在首结点之前，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。

14、,讨论1：若在长度为 n 的线性表的第 i 位前 插入一个元素，则向后移动元素的次数f(n)为: f(n) =,n i + 1,时间效率分析:,推导：假定在每个元素位置上插入x的可能性都一样（即概率P相同），则应当这样来计算平均执行时间： 将所有位置的执行时间相加，然后取平均。 若在首结点前插入，需要移动的元素最多，后移n次； 若在a1后面插入，要后移n-1个元素，后移次数为n-1; 若在an-1后面插入，要后移1个元素； 若在尾结点an之后插入，则后移0个元素； 所有可能的元素移动次数合计： 0+1+n = n(n+1)/2,故插入时的平均移动次数为：n(n+1)/2（n+1）n/2O(n)

15、,共有多少种插入形式?连头带尾有n+1种!,同理可证：顺序表删除一元素的时间效率为: T（n)=(n-1)/2 O(n),想一想： 顺序表插入、删除算法的平均空间复杂度为多少？,插入效率：,删除效率：,教材P25算法2.5也是对执行效率的推导：,因为没有占用辅助空间！,含义：对于顺序表， 插入、删除操作平均需要移动一半元素( n / 2 ),O(1),即插入、删除算法的平均时间复杂度为 O(n),链式存储结构,本节小结,线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻； 优点：可以随机存取表中任一元素，方便快捷； 缺点：在插入或删除某一元素时，需要移动大量元素。 解决问题

16、的思路：改用另一种线性存储方式：,第2章 线性表,2.1 线性表的逻辑结构 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.4 应用举例,2.3 线性表的链式表示和实现,2.3.1 线性链表的表示 1.链表的表示 2.链表的实现 3.链表的运算效率分析 2.3.2 循环链表 2.3.3 双向链表,链式存储结构特点： 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。,如何实现？,通过指针来实现！,让每个存储结点都包含两部分：数据域和指针域,数据域：存储元素数值数据,指针域：存储直接后继或者直接前驱的存储位置,设计思想：牺牲空间效率换取时间效率,1 链

17、表的表示,例：请画出26 个英文字母表的链式存储结构。,该字母表在内存中链式存放的样式举例如下：,解：该字母表的逻辑结构为：（ a, b, ,y, z）,链表存放示意图如下：,讨论1 ：每个存储结点都包含两部分：数据域和 。,讨论2：在单链表中，除了首元结点外，任一结点的存储位置 由 指示。,其直接前驱结点的链域的值,指针域(链域),1）结点：数据元素的存储映像。由数据域和指针域两部分组成； 2）链表： n 个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。 3）单链表、双链表、多链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表； 有两个指针域的链

18、表，称为双链表（但未必是双向链表）； 有多个指针域的链表，称为多链表； 首尾相接的链表称为循环链表。,循环链表示意图：,head,(2) 与链式存储有关的术语：,4）头指针、头结点和首元结点的区别,头指针,头结点,首元结点,头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针； 头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a1的结点。,示意图如下：,答：,讨论1. 在链表中设置头结点有什么好处？,讨论2. 如何表示空表？,头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也

19、可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。,答：,无头结点时，当头指针的值为空时表示空表；,有头结点时，当头结点的指针域为空时表示空表。,头结点不计入链表长度！,一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？,答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。,31,称：头指针H的值是31,（3）举例 例1：,上例链表的逻辑结构示意图有以下两种形式：,区别： 无头结点 有头结点,头结点不计入

20、链表长度！,线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L=23，17，47，05，31， 若它以链接方式存储在下列100119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。,其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？,100,119,104,108,116,112,116,NULL(0),100,108,112,答：X= Y= Z= , 首址= 末址= 。,例2：,讨论: 链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？,因每个结点至少有两个分量，且数据类型通常不一致

21、，所以要采用结构数据类型。,答：,以26个字母的链表为例，每个结点都有两个分量：,设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？,方式1： 直接表示为 node.dataa；node.next=q 方式2：p指向结点首地址，然后 p-data=a; p-next=q; 方式3： p指向结点首地址，然后 (*p).data=a； (*p).nextq,设p为指向链表的第i个元素的指针,则第i个元素的 数据域写为 ，指针域写为 。,练习：,p-data,ai的值,p-next,ai+1的地址,单链表的抽象数据类型描述如下（参见教材P28）

22、：,Typedef struct Lnode ElemType data; /数据域 struct Lnode *next; /指针域 Lnode, *LinkList; / *LinkList为Lnode类型的指针,至此应可看懂教材P22关于顺序表动态分配的存储结构。 其特点是：用结构类型和指针来表示顺序结构，更灵活。,如何具体编程来建立和访问链表？ 链表的实现,第2章作业： 习题2,2 链表的实现,（1） 单链表的建立和输出 （2） 单链表的修改 （3） 单链表的插入 （4） 单链表的删除,（1） 单链表的建立和输出,例：用单链表结构来存放26个英文字母组成的线性表（a，b，c，z）,请写

23、出C语言程序。,实现思路：先开辟头指针，然后陆续为每个结点开辟存储空间并及时赋值，后继结点的地址要提前送给前面的指针。,#include #include typedef struct node char data; struct node *next; node;,将全局变量及函数提前说明：,node *p,*q,*head; /一般需要3个指针变量 int n ; / 数据元素的个数 int m=sizeof(node); /*结构类型定义好之后，每个node类型的长度就固定了，m求一次即可*/,新手特别容易忘记！, int i; head=(node*)malloc(m); /m=siz

24、eof(node) 前面已求出 p=head; for( i=1; idata=i+a-1; / 第一个结点值为字符a p-next=(node*)malloc(m); /为后继结点准备空间 p=p-next； /让指针变量P指向后一个结点 p-data=i+a-1; /最后一个元素要单独处理 p-next=NULL ; /单链表尾结点的指针域要置空！,void build( ) /字母链表的生成。要一个个慢慢链入,p=head; while (p) /当指针不空时循环（仅限于无头结点的情况） printf(%c,p-data); p=p-next; /让指针不断“顺藤摸瓜” ,讨论：要统计链

25、表中数据元素的个数，该如何改写？,sum+;,sum=0;,void display() /*字母链表的输出*/,（2） 单链表的修改(或读取）,思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，然后才能执行p-data=new_value 。,修改第i个数据元素的操作函数可写为：,Status GetElem_L(LinkList L, int i, ElemType / GetElem_L,缺点：想寻找单链表中第i个元素，只能从头指针开始逐一查询（顺藤摸瓜），无法随机存取 。,Status含义见P10,在链表中插入一个元素X 的示意图如下：,链表插入的核心语句：,Step

26、1：s-next=p-next; Step 2：p-next=s ；,p-next,s-next,思考：Step1和2能互换么？,X 结点的生成方式： s=(node*)malloc(m); s-data=X ; s-next= ?,（3） 单链表的插入,在链表中删除某元素b的示意图如下：,删除动作的核心语句（要借助辅助指针变量q）：,q = p-next; /首先保存b的指针，靠它才能找到c； p-next=q-next; /将a、c两结点相连，淘汰b结点； free(q) ； /彻底释放b结点空间,p-next,思考： 省略free(q)语句行不行？,(p-next) - next,q,（

27、4） 单链表的删除,3 链表的运算效率分析,（1） 查找 因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。,时间效率分析,（2） 插入和删除 因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。,但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。,空间效率分析,链表中每个结点都要增加一个指针空间，相当于总共增加了n 个整型变量，空间复杂度为 O(n)。,在n个结点的单链表中要删除已知结点*P，需找到它的 ，其时间复杂度为 。,前驱结点的地址/指针,O(n),练习：,2.3.2 循环链表,循环链表

28、示意图：,head,单链表中查找只能从前往后，而不能从后往前查。为了查找方便，提高查找速度，可以在结点上增加一个指针域，用来存结点的直接前驱，这样的链表，称为双向链表。其结点的结构为：,typedef struct DuLNode ElemType data; /数据域 struct DuLNode *prior; /前驱指针域 struct DuLNode *next; /后继指针域 DuLNode , *DuLinkList ;,双向链表类型的定义如下：,2.3.3 双向链表（在双向链表中如何实现插入和删除运算？）,双向链表的插入操作：,设p已指向第 i 元素，请在第 i 元素前插入元素

29、x, ai-1的后继从 ai ( 指针是p)变为 x（指针是s) : s-next = p ; p-prior-next = s ; ai 的前驱从 ai-1 ( 指针是p-prior)变为 x ( 指针是s); s-prior = p -prior ; p-prior = s ;,注意：要修改双向指针！,指针域的变化：,指针域的变化： 后继方向：ai-1的后继由 ai ( 指针p)变为 ai+1(指针 p -next ); p -prior-next = p-next ; 前驱方向：ai+1 的前驱由 ai ( 指针p)变为ai-1 (指针 p - prior ); p-next-prior

30、 = p -prior ;,双向链表的删除操作： 设p指向第 i 个元素，删除第 i 个 元素,注意：要修改双向指针！,2.4 应用举例,算法要求： 已知：线性表 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）,例1：两个链表的归并（教材P31例）,重点是链表,链表示意图：,头结点,算法设计：,算法主要包括搜索、比较、插入三个操作： 搜索：需要设立三个指针来指向La 、Lb和Lc链表； 比较：比较La和Lb表中结点数据的大小； 插入：将La和Lb表中数据较小的结点插入新链表Lc 。,请注意链表的特点，仅改变指针便可实现数据的移动,即 “数据不动，指针动”,Pa、Pb用于搜索La和Lb， Pc指向新链表当前结点。 归并过程示意如下：,Lc=La,Pb,Pa,Pa,Pb,typedef struct Lnode /结点类型 Elemtype data; struct Lnode