《数据结构9[中小学堂].ppt》由会员分享，可在线阅读，更多相关《数据结构9[中小学堂].ppt（43页珍藏版）》请在三一文库上搜索。
1、第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 习题2,1,课堂特制,线性结构是一个数据元素的有序（次序）集 线性结构的基本特征: 1集合中必存在唯一的一个“第一元素”； 2集合中必存在唯一的一个“最后元素”； 3除最后元素在外，均有唯一的后继； 4除第一元素之外，均有唯一的前驱。,2,课堂特制,2.1 线性表的类型定义,线性表（linear_list）是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。 例如： （A,B,C,D,Z） （6,17,28,50,92,188） 在线性表中，一个数据元素可以由若干数
2、据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。,3,课堂特制,抽象数据类型线性表的定义如下： ADT List 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 /称n为线性表的表长; 称n=0时的线性表为空表。 数据关系：R1 |ai-1 ,aiD, i=2,.,n /设线性表为 (a1，a2,.，an), 称i为ai在线性表中的位序。 基本操作： InitList( GetElem(LB, i)e 2依值在线性表LA中进行查访; LocateElem(LA, e, equal( ) 3若不存在，
3、则插入之。 ListInsert(LA, n+1, e),9,课堂特制,void union(List / La中不存在和 e 相同的数据元素，则插入之 / union,10,课堂特制,2.2 线性表类型的实现 -顺序映象,用一组地址连续的存储单元依次存放线性表中的数据元素 线性表的起始地址，称作线性表的基地址 以“存储位置相邻”表示有序对 即：,所有数据元素的存储位置均取决于第一个数据元素的存储位置,11,课堂特制,顺序映像的C语言描述 /- 线性表的动态分配顺序存储结构 - #define LIST_INIT_SIZE 80 / 线性表存储空间的初始分配量 #define LISTINCR
4、EMENT 10 / 线性表存储空间的分配增量 typedef struct ElemType *elem; / 存储空间基址 int length; / 当前长度 int listsize; / 当前分配的存储容量(以sizeof(ElemType)为单位) SqList; / 俗称 顺序表,12,课堂特制,线性表的初始化在顺序映像中的实现 Status InitList_Sq(SqList / InitList_Sq,13,课堂特制,线性表操作ListInsert( / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList; 在单链表前增加一个结点，
5、称为表头结点。,20,课堂特制,带表头结点的单链表 (a) 空表；(b) 非空表,21,课堂特制,看下面的程序段： int i, *pi;/* 定义整型变量 i 和指向整型的指针变量pi */ pi= /* 输出 i 的当前值 10 */ 运行上面的程序段将显示：5，10。,22,课堂特制,指针定义和运算,23,课堂特制,单链表的插入和删除 在单链表的指定结点(设由指针变量p指示)后面插入新结点(由q指示)的方法很简单，只需使用指针赋值语句q-Next=p-Next;和p-Next=q;，即修改两个结点的指针域的值就可以了，如图所示。,24,课堂特制,单链表的插入 (a) 插入前；(b) 插入
6、后,25,课堂特制,线性表的操作ListInsert( / LinstInsert_L,26,课堂特制,删除操作如图所示。删除p所指示的结点时，只需修改一个指针：q-Next=p-Next，但还需使用free(p)语句回收结点占用的空间。这里，结点*q是结点*p的前驱结点(predecessor)。由此可见，在单链表中，为了删除一个结点，我们必须知道它的前驱结点。,27,课堂特制,单链表的删除 (a) 删除前；(b) 删除后,28,课堂特制,Status ListDelete_L(LinkList L, int pos, ElemType / ListDelete_L 算法的时间复杂度为:O(
7、ListLength(L),29,课堂特制,五、循环链表 另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如图为单链表的循环链表和带头结点的循环链表。 最后一个结点的指针域的指针又指回第一个结点的链表,30,课堂特制,单循环链表 (a) 空表；(b) 非空表,31,课堂特制,带表头结点的单循环链表 (a) 空表；(b) 非空表,32,课堂特制,六、双向链表 我们已经看到，在各种单链表中插入一个新结点时，需知道新结点插入位置的前驱结点，而当删除一个结点时也需知道该结点的前驱结点。常常为了得到前驱结点的地址，
8、必须从头开始查找，这一过程是费时的。此外，在实际应用中，有时需要逆向访问表中元素，这对单链表结构来说显然是困难的。为解决这类问题，可将链表设计成双向链表(doubly linked list)。,33,课堂特制,双向链表的每个结点包含三个域：Element、Prior和Next。其中，Element为元素域，Next域为指向后继结点的指针，新增的Prior域用以指向前驱结点。 双向链表也可以带表头结点，并且也可构成双向循环链表。此时，表头结点的Next和Prior分别指向双向循环链表的头结点(或表头结点)和尾结点。带表头结点的双向循环链表的结构示意图如图所示。,34,课堂特制,带表头结点的双向
9、循环链表 (a) 空表；(b) 非空表,35,课堂特制,/- 线性表的双向链表存储结构 - typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior;/ 指向前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,36,课堂特制,线性表顺序存储结构的优缺点： 1、优点 （1）结构简单 （2）可直接定位到表中任一元素，并可随机存取元素；连续存储速度快 2、缺点 （1）存储空间难于准确静态分配，大了浪费，小了不够 （2）插入、删除操作大不方便，需移动大量数据
10、元素，效率低,37,课堂特制,线性表链式存储结构的优缺点： 1、优点 （1）存储空间动态分配，可以按需使用 （2）插入、删除结点操作时通常只要修改指针，不必移动数据元素 2、缺点 （1）每一结点附加指针域 （2）非随机存取结构，查找定位操作需从头指针出发顺着链表扫描,38,课堂特制,习 题 2,21 定义一个结构类型，它包括年、月、日。用该结构类型定义一个结构变量。 22 设计一个算法，用来复制一个单链表 23 设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列。 24 设计一个算法，将一个单链表链接到另一个单链表的尾部。,39,课堂特制,25 设一维数组的每个元素具有前面
11、的年、月、日结构类型，设计一个函数Copy，用来实现数组的整体赋值。 26 编写一个函数NewArray，用来创建一个最多有MaxSize个元素的动态一维数组，设数组元素具有前面的年、月、日结构类型。此函数返回一个指针，指向动态一维数组的起始位置。 27 设有长度为n的一维整型数组A，设计一个算法，将该数组中所有的负数存放在数组的前部，而所有的正数存放在负数的后面。,40,课堂特制,28 设有长度为n的一维整型数组A，数组中元素各不相同。设计一个算法，该算法以数组的第一个元素为基准元素，对各元素在数组中的位置作重新调整，将所有比该基准元素小的元素存放在基准元素的前面部分，所有比基准元素大的元素
12、存放在基准元素后面部分。,41,课堂特制,212 设计一个算法，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。 213 设计一个函数，用以建立一个带表头结点的单循环链表。设表中元素的类型为整型，元素值从键盘输入。 214 设计一个函数，用以打印一个带表头结点的单循环链表。设表中元素的类型为整型。注意循环链表的结束判断。 215 设计一个函数，用来清空一个带表头结点的单循环链表。请注意带表头结点的单循环链表的空表形式。,42,课堂特制,216 单链表中每个结点存放一个字符。设计一个算法，将该单链表按字母、数字和其他字符拆成三个单循环链表(利用原来结点)。 217 设计一个算法，将一个带表头结点的双向循环链表链接到另一个带表头结点的双向循环链表的尾部。注意，新链表只需一个表头结点。 对习题中要求设计的所有算法，若不加特殊说明，都必须：(1) 写出相关数据结构的C语言类型说明；(2) 算法用C语言函数表示。 在设计链表操作的算法时，请考虑链表可能为空表的情况。,43,课堂特制,