数据结构ch02学习教案

1、数据结构数据结构(sh j ji u) ch02第一页，共77页。 线性表（Linear list）是最简单且最常用的一种数据结构。这种结构具有(jyu)下列特点：存在一个唯一的没有前驱的（头）数据元素；存在一个唯一的没有后继的（尾）数据元素；此外，每一个数据元素均有一个直接前驱和一个直接后继数据元素。 通过本章的学习，读者应能掌握线性表的逻辑结构和存储结构，以及线性表的基本运算以及实现算法。 第1页/共77页第二页，共77页。 线性表由一组具有相同属性的数据元素构成。数据元素的含义广泛(gungfn)，在不同的具体情况下，可以有不同的含义。 1 . 线性表的定义 线性表L是n（n0）个具有相

2、同属性的数据元素a1，a2，a3，an组成的有限序列，其中序列中元素的个数n称为线性表的长度。 当n=0时称为空表，即不含有任何元素。 常常将非空的线性表(n0)记作： (a1，a2，an) 这里的数据元素 ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。第2页/共77页第三页，共77页。例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z） 例例2、从、从1978年到年到1983年各种型号的计算机拥有量的变化年各种型号的计算机拥有量的变化(binhu)情情况。况。 （6，17，28，50，92，188）例例3、第3页/共77页第四页，共77页。从以上

3、例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是： 在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它没有直接，它没有直接前趋，而仅有一个直接后继前趋，而仅有一个直接后继a2； 有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而仅有一个，它没有直接后继，而仅有一个直接前趋直接前趋a n-1； 其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1和一个直接后继和一个直接后继a i+1。 线性表是一种典型的线性结构。线性表是一种典型的线性结构。 数据的运算是定义在逻辑结构上的，而运算的具体实

4、现则数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储是在存储(cn ch)结构上进行的。结构上进行的。第4页/共77页第五页，共77页。2 . 线性表的基本运算 数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现则是建立在存储结构上的。 (1) 初始化线性表Initlist(L) 将线性表L置为空表。(2) 求线性表的长度Getlen(L) 求解并返回线性表所含元素的个数n。若线性表为空，则返回整数0。(3) 按序号取元素Getelem(L,i) 读取线性表L第i个数据元素，要求(yoqi)满足1iGetlen(L)。第5页/共77页第六页，共77页。第6页/共77页第七页，共

5、77页。 线性表有两种基本的存储(cn ch)结构：顺序存储(cn ch)结构和链式存储(cn ch)结构。 1.线性表的顺序存储结构(jigu) 第7页/共77页第八页，共77页。第8页/共77页第九页，共77页。第9页/共77页第十页，共77页。第10页/共77页第十一页，共77页。 这样，一个线性表的顺序存储结构需要两个分量。为体现数组这样，一个线性表的顺序存储结构需要两个分量。为体现数组data和和length之间的内在联系，通常将它们定义在一个结构类型中。此处的元素之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用类型用ElemType来表示。来表示。 综上所述，在综上

6、所述，在C语言中，可用下述类型定义来描述顺序表：语言中，可用下述类型定义来描述顺序表： #define MaxLen 100 /线性表的容量线性表的容量 typedef int ElemType /在实际应用中，将在实际应用中，将ElemType定义成实际类定义成实际类型型 typedef struct ElemType dataMaxLen; /定义存储表中元素的数组定义存储表中元素的数组 int length; /线性表的实际长度线性表的实际长度(chngd) sqList; sqList L; /定义表结构的变量定义表结构的变量第11页/共77页第十二页，共77页。第12页/共77页第十

7、三页，共77页。第13页/共77页第十四页，共77页。 5顺序表的插入顺序表的插入(ch r)算法算法inselem(L,i,x)的实现的实现 顺序表的插入顺序表的插入(ch r)是指在表的第是指在表的第 i个位置上插入个位置上插入(ch r)一个值为一个值为 x的新元素，插入的新元素，插入(ch r)后使原表长为后使原表长为 n的表：的表：(a1，a2， ，ai-1，ai，ai+1， ，an)，成为表长为，成为表长为 n+1的表：的表： 由算法可知，对于表长为由算法可知，对于表长为n n的顺序表，在查找过程中，数据的顺序表，在查找过程中，数据元素元素(yun s)(yun s)比较次数最少为

8、比较次数最少为1 1，最多为，最多为 n n，元素，元素(yun s)(yun s)比比较次数的平均值为较次数的平均值为 (n+1)/2 (n+1)/2，时间复杂度为，时间复杂度为 O(n) O(n)。第14页/共77页第十五页，共77页。 序序号号 元元素素(yun s) 0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num an um 序序号号 元元素素(yun s) 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 n umanum 插插入入x插入前插入前插入后插入后第15页/共77页第十六页，共77页。

9、第16页/共77页第十七页，共77页。)1(11inpEniiin11112) 1(11) 1(Eniniiinninninp假设假设(jish)(jish)表中任何位置插入概率是均等的表中任何位置插入概率是均等的, ,即即Pi=1/ (n+1) ,Pi=1/ (n+1) ,则：则： 该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置 i和表的长度和表的长度n。所以可以用数据元素的移动操作来估计算法的时间复杂度。所以可以用数据元素的移动操作来估计算法的时间复杂度。在第在第 i个位置上插入个位置上插入 x ，共需要移动，共需要

10、移动 n-i+1个元素，个元素， i 的取值范围为的取值范围为 ：1i n+1，即有，即有 n+1个位置可以插入。个位置可以插入。 当当i=n+1时，不需要移动结点；当时，不需要移动结点；当i=1时需要移动时需要移动n个结点个结点 。由此可以。由此可以看出，算法在最好看出，算法在最好(zu ho)的情况下时间复杂性为的情况下时间复杂性为O(1)，最坏的时间复杂，最坏的时间复杂性是性是O(n)。 由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素由于插入的位置是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第的平均值。设在第i个位置上作插入的概率为个位置上作插入的概率为Pi

11、，则平均移动数据元素的次，则平均移动数据元素的次数：数：第17页/共77页第十八页，共77页。第18页/共77页第十九页，共77页。第19页/共77页第二十页，共77页。第20页/共77页第二十一页，共77页。niideinp1)(E11121)(1)(Eniniideninninp 删除算法的时间性能分析：删除算法的时间性能分析： 与插入运算相同，删除运算的时间也主要与插入运算相同，删除运算的时间也主要(zhyo)消耗在移动表中消耗在移动表中数据元素上，删除第数据元素上，删除第i个元素时，其后面的元素个元素时，其后面的元素 ai+1an 都要向前移动都要向前移动一个位置，共移动了一个位置，共

12、移动了 n-i 个元素，所以在等概率的情况下，在线性表中个元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：为： 由此可以看出，在线性表上删除数据元素时大约需要移动表中一半由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的元素，显然该算法(sun f)的时间复杂度为的时间复杂度为(n)。 通常情况下，我们认为在线性表中任何位置删除通常情况下，我们认为在线性表中任何位置删除(shnch)元素元素是等概率的，即是等概率的，即pi =1/ n，则：，则：第2

13、1页/共77页第二十二页，共77页。第22页/共77页第二十三页，共77页。第23页/共77页第二十四页，共77页。第24页/共77页第二十五页，共77页。2) 3() 1() 21(22nniinini 本算法中，有两重循环，外循环执行n-1次，内循环中元素(yun s)的移动次数与当前数据的大小有关，当第i个元素(yun s)小于a1时，要移动它上面的i-1个元素(yun s)，再加上前面结点的保存及置入，所以移动i-1+2次，在最坏情况下，a1后面的结点都小于a1，故总的移动次数为：第25页/共77页第二十六页，共77页。 线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因

14、此(ync)顺序存储结构的线性表是可以随机存取其中的任意元素。 但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；（2）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。（3）存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢”错误。第26页/共77页第二十七页，共77页。 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关

15、线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，故可以随机存取表中的任一结点；但在插入和删除操作时需移动大量的结点。系，故可以随机存取表中的任一结点；但在插入和删除操作时需移动大量的结点。 为避免大量结点的移动，介绍线性表的另一种存储方式为避免大量结点的移动，介绍线性表的另一种存储方式: 链式存储结构，简称链式存储结构，简称链表链表(Linked List)。 线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部线性表的数据

16、元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放分用于存放(cnfng)数据元素值，称为数据域；另一部分用于存放数据元素值，称为数据域；另一部分用于存放(cnfng)直直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结点。 链式存储方式可用于表示线性结构，也可用于表示非线性结构。链式存储方式可用于表示线性结构，也可用于表示非线性结构。第27页/共77页第二十八页，共77页。第28页/共77页第二十九页，共77页。 在此结构中，用数据域在此结构中，用数据域data存储线性表中数据元素存储线

17、性表中数据元素 。指针域。指针域next，它，它给出下一个结点的存储地址。结点的指针域将所有结点按线性表的逻辑次序给出下一个结点的存储地址。结点的指针域将所有结点按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表中第一个结点没有链接成一个整体，形成一个链表。由于链表中第一个结点没有(mi yu)直直接前驱，所以必须设置一个头指针接前驱，所以必须设置一个头指针head存储第一个结点的地址。最后一个存储第一个结点的地址。最后一个结点没有结点没有(mi yu)直接后继，其指针域应为空指针，直接后继，其指针域应为空指针，C语言用语言用NULL或或0来来表示，在图中表示为表示，在图中表示为“”。

18、假设有一个线性表为（假设有一个线性表为（A,B,C,D,E），存储空间具有），存储空间具有10个存储结点，该个存储结点，该线性表在存储空间中的存储情况如图线性表在存储空间中的存储情况如图2-7(a)所示。所示。 第29页/共77页第三十页，共77页。第30页/共77页第三十一页，共77页。第31页/共77页第三十二页，共77页。 在图2-7所示的链表中，每个结点只有一个(y )指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。 单链表分为带头结点和不带头结点两种类型。 对于空链表，头结点的指针域为空。图2-8是

19、带头结点的链表示方式：图图2-8（a）为带头）为带头(di tu)结点的空链结点的空链 (b)为带头为带头(di tu)结点的单结点的单链表链表第32页/共77页第三十三页，共77页。 由于链表是一种(y zhn)动态管理的存储结构，每个结点需动态产生。1初始化链表initlist(L)的实现 建立一个空的带头结点的单链表。所谓空链表就是指表长为0的表。在这种情况下，链表中没有元素结点。但应有一个头结点，其指针域为空。void initlist(LinkList void initlist(LinkList * *L)L) * *L=(LNode L=(LNode * *)malloc(siz

20、eof(LNode);)malloc(sizeof(LNode); ( (* *L)-next=NULL;L)-next=NULL; 在函数调用时，指针在函数调用时，指针L指向的内容发生了变化，为使得指向的内容发生了变化，为使得(sh de)调用函数中头指针变量调用函数中头指针变量head获得头获得头结点地址，需传递头指针变量的地址给结点地址，需传递头指针变量的地址给initlist()函数，而函数中定义二级指针变量函数，而函数中定义二级指针变量L接受该地址值，从而接受该地址值，从而返回改变后的值。返回改变后的值。第33页/共77页第三十四页，共77页。第34页/共77页第三十五页，共77页。

21、第35页/共77页第三十六页，共77页。第36页/共77页第三十七页，共77页。第37页/共77页第三十八页，共77页。上述指针进行上述指针进行(jnxng)相互赋值的语句顺序不能颠倒。相互赋值的语句顺序不能颠倒。第38页/共77页第三十九页，共77页。第39页/共77页第四十页，共77页。第40页/共77页第四十一页，共77页。 q=q-next;q=q-next; pos+; pos+; p=q-next; p=q-next; q-next=p-next; q-next=p-next; free(p); free(p); void Delelem(LinkList L,int i)void

22、 Delelem(LinkList L,int i) int pos=1; int pos=1; LNode LNode * *q=L,q=L,* *p;p; if(iGetlen(L) exit(1); if(iGetlen(L) exit(1); while(posi) while(posnext，并将，并将head-next置空，然后依次置空，然后依次将将p所指链表的结点顺序摘下，插入到所指链表的结点顺序摘下，插入到head之后即可。具体算法如下：之后即可。具体算法如下：void reverse(LinkList L) LNode *p,*q; if(L-next!=NULL) /至少有

23、两个元素至少有两个元素 p=L-next; L-next=NULL; while(p!=NULL) 第45页/共77页第四十六页，共77页。第46页/共77页第四十七页，共77页。2.3.3 循环链表循环链表 在单链表中，最后在单链表中，最后(zuhu)一个结点的指针域为空（一个结点的指针域为空（NULL）。访问单链表中任何数据只能从链表头开始顺序访问，而不能进行任何位置的随机查询访问。如要查询的结点在链表的尾部也需遍历整个链表。所以单链表的应用受到一定的限制。）。访问单链表中任何数据只能从链表头开始顺序访问，而不能进行任何位置的随机查询访问。如要查询的结点在链表的尾部也需遍历整个链表。所以单

24、链表的应用受到一定的限制。 循环链表循环链表(Circular Linked List)是另一种形式的链式存储结构。它将单链表中最后是另一种形式的链式存储结构。它将单链表中最后(zuhu)一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形。这样，从链表中任一结点出发，顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量，只是简单地改变一下最后一个结点的指针指向链表的头结点，使整个链表头尾相接形成一个环形。这样，从链表中任一结点出发，顺着指针链都可找到表中其它结点。循环链表的最大特点是不增加存储量，只是简单地改变一下最后(zuhu)一个结点的指针指向，就可以使操作更加方便

25、灵活。图一个结点的指针指向，就可以使操作更加方便灵活。图2-13是循环链表的存储结构示意图。是循环链表的存储结构示意图。第47页/共77页第四十八页，共77页。 图图 2-13 循环循环(xnhun)链表结链表结构示意图构示意图 带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似，差别仅在于算法中的循环条件不同。在循环单链表上实现上述基本运算带头结点的单循环链表的操作算法和带头结点的单链表的操作算法很相似，差别仅在于算法中的循环条件不同。在循环单链表上实现上述基本运算(yn sun)的改动如下：的改动如下： 1初始化链表初始化链表initlist(L)创建的头结点指针域创建的头结

26、点指针域next不为空，而是指向自身，不为空，而是指向自身，L-next=L第48页/共77页第四十九页，共77页。第49页/共77页第五十页，共77页。图图2-14 两个两个(lin )循环链表首尾相接进行合并循环链表首尾相接进行合并 第50页/共77页第五十一页，共77页。第51页/共77页第五十二页，共77页。 双向链表结点的定义双向链表结点的定义(dngy)如下：如下： typedef struct DNode ElemType data; struct DNode *prior; struct DNode *next; Dnode,*DuLinkList;结点的结构如图结点的结构如图

27、2-15所示。所示。 单链表只有一个指向后继的指针来表示结点间的逻辑关系。故从任一结点开始找其后继结点很方便，但要找前驱(qinq)结点则比较困难。双向链式是用两个指针表示结点间的逻辑关系。即增加了一个指向其直接前驱(qinq)的指针域，这样形成的链表有两条不同方向的链，前驱(qinq)和后继，因此称为双链表。在双链表中，根据已知结点查找其直接前驱(qinq)结点可以和查找其直接后继结点一样方便。这里也仅讨论带头结点的双链表。仍假设数据元素的类型为ElemType。第52页/共77页第五十三页，共77页。图图2-16 带头带头(di tu)结点的双向链表结点的双向链表 在图2-16中，如果某指

28、针变量p指向了一个结点，则通过该结点的指针p可以直接访问(fngwn)它的后继结点，即由指针p-next所指向的结点；也可以直接访问(fngwn)它的前驱结点，由指针p-prior指出。这样在需要查找前驱的操作中，就不必再从头开始遍历整个链表。这种结构极大地简化了某些操作。 在双向链表中也可采用与单链表类似的方法，用头指针标识链表的开头，也可以带头结点。在双向链表中，每个结点都有一个指向直接(zhji)前驱结点和一个指向直接(zhji)后继结点的指针。链表中第一个结点的前驱指针和最后一个结点的后继指针可以为空，不做任何指向，这是简单的双向链表。第53页/共77页第五十四页，共77页。图图2-1

29、7 双链表插入双链表插入(ch r)结点示意图结点示意图第54页/共77页第五十五页，共77页。 图2-18 双链表的删除结点示意图在双向链表中找到删除位置的前一个结点，由p指向它，q指向要删除的结点。删除操作如下：将*p的next域改为指向待删结点*q的后继结点；若*q不是指向最后的结点，则将*q之后结点的prior域指向*p。 注意：在双向链表中进行插入和删除时，对指针的修改(xigi)需要同时修改(xigi)结点的前驱指针和后继指针的指向。 第55页/共77页第五十六页，共77页。第56页/共77页第五十七页，共77页。图图2-19 2-19 带头结点带头结点(ji din)(ji di

30、n)且有且有n n个结点个结点(ji din)(ji din)的循环双链表的循环双链表第57页/共77页第五十八页，共77页。第58页/共77页第五十九页，共77页。第59页/共77页第六十页，共77页。第60页/共77页第六十一页，共77页。第61页/共77页第六十二页，共77页。第62页/共77页第六十三页，共77页。图2-20 静态链表结构 从图2-20中可以看出(kn ch)，表头结点一般在第0个位置。它的next指针指向链表中第一个结点。链表中最后一个结点的next指针为-1，表示链表结束。第63页/共77页第六十四页，共77页。第64页/共77页第六十五页，共77页。coefexp

31、nnext 其中，coef数据域存放序数ci；expn数据域存放指数ei；next域是一个链域，指向下一个结点。由此，一个多项式可以表示成由这些结点链接而成的单链表(假设该单链表是带头结点的单链表)。 在计算机中，多项式可用一个线性表listP来表示：listP=（p0，p1，p2，pn）。但这种表示无法分清每一项的系数和指数。所以可以采用另一种表示一元多项式的方法：listP=（a0，e0），(a1，e1)，(a2，e2)，(an，en) 。在这种线性表描述中，各个结点包括两个数据域，对应(duyng)的类型描述为：第65页/共77页第六十六页，共77页。 在顺序存储结构中，采用基类型为在顺

32、序存储结构中，采用基类型为polynode的数组表示多项式中的各项。如的数组表示多项式中的各项。如pi.coef和和pi.expn分别表示多项式中第分别表示多项式中第i项的系数和指数。但多项式中，其中一些项的系项的系数和指数。但多项式中，其中一些项的系数会为数会为0。如多项式。如多项式A(x)=a0+a1x+a2x2+ a6x6+ a9x9+a15x15 中包括中包括16项，其中只有项，其中只有6项项系数不为系数不为0。顺序存储结构可以使多项式相加算法变得简单。但是，当多项式中存在大量的。顺序存储结构可以使多项式相加算法变得简单。但是，当多项式中存在大量的零系数时，这种表示方式就会浪费大量的存

33、储空间。为了有效利用存储空间，可用链式存零系数时，这种表示方式就会浪费大量的存储空间。为了有效利用存储空间，可用链式存储结构表示多项式。储结构表示多项式。 在链式存储结构中，多项式中每一个非零项构成链表中的一个结点在链式存储结构中，多项式中每一个非零项构成链表中的一个结点(ji din)，而对于系，而对于系数为零的项则不需要表示。数为零的项则不需要表示。 （注意：表示多项式的链表应该是有序链表）（注意：表示多项式的链表应该是有序链表） 第66页/共77页第六十七页，共77页。2.4.2 一元多项式相加一元多项式相加 假设假设(jish)用单链表表示多项式：用单链表表示多项式：A(x)=12+7

34、x+8x10+5x17 ，B(x)=8x+15x7-6x10，头指针，头指针Ah与与Bh分别指向这两个链表，如图分别指向这两个链表，如图2-21所示：所示： 对两个多项式进行相加运算，其结果为对两个多项式进行相加运算，其结果为C(x)= 12+15x+15 x7+2x10+5x17。如图。如图2-22所示。所示。图图2-21 合并合并(hbng)以前的以前的链表链表 图 2-22 合并(hbng)以后的链表第67页/共77页第六十八页，共77页。第68页/共77页第六十九页，共77页。第69页/共77页第七十页，共77页。第70页/共77页第七十一页，共77页。 本章介绍了线性表的逻辑结构本章介绍了线性表的逻辑结构(jigu)(jigu)及它的两种存储结构及它的两种存储结构(jigu)(jigu)：顺序表和链表。这两种表各有短长，在实际应用中应根：顺序表和链表。这两种表各有短长，在实际应用中应根据问题的要求和性质来选择使用。通过前面的讨论可知：顺序存储据问题的要求和性质来选择使用。通过前面的讨论可知：顺序存储有三个优点：有三个优点：(1) (1) 方法简单，各种高级语言中都有数组，容易实现；方法简单