数据结构第二章.ppt

1、2020年9月22日星期二,第1页,第二章 线性表,2020年9月22日星期二,第2页,【课前思考】,数据对象、数据关系和基本操作三部分。,线性结构、树型结构、图状结构和集合四类。,如：0，1，2，9,A，B，C，Z。,2020年9月22日星期二,第3页,【学习目标】,1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。 2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。 3. 能够从时间和空间复杂度的角度综合比较线性表

2、两种存储结构的不同特点及其适用场合。 4. 结合线性表类型的定义增强对抽象数据类型的理解。,2020年9月22日星期二,第4页,【重点和难点】,链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求，分清链表中指针 p 和结点 *p 之间的对应关系，区分链表中的头结点、头指针和首元结点的不同所指以及循环链表、双向链表的特点等。,【知识点】,线性表、顺序表、链表、有序表.,2020年9月22日星期二,第5页,【学习指南】,正如课程概况中所提，学习数据结构的目标是为了编出质量更高的程序，因此重在“实践”。本章讨论的线性表是学习的第一种也是最简单的一种数据结构，是整个课程

3、的基础，特别是熟练掌握链表的操作对以后各章的学习将有很大帮助。本章要求必须完成的算法设计题为：2.11，2.19，2.21，2.22，2.24，2.27，2.28， 2.37， 2.38。其中 2.19 ，2.21和 2.37 要求书面作业完成。,2020年9月22日星期二,第6页,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是 一个数据元素的有序（次序）集,线性表是一种最简单的线性结构,2020年9月22日星期二,第7页,2.1 线性表的类型定

4、义,2.3 线性表类型的实现 链式映象,2.4 一元多项式的表示,2.2 线性表类型的实现 顺序映象,2020年9月22日星期二,第8页,2.1 线性表的类型定义,2020年9月22日星期二,第9页,抽象数据类型线性表的定义如下：,ADT List ,数据对象：,D ai | ai ElemSet, i=1,2,.,n, n0 称 n 为线性表的表长; 称 n=0 时的线性表为空表。,数据关系：,R1 |ai-1 ,aiD, i=2,.,n ,设线性表为 (a1，a2, . . . ，ai，. . . ，an), 称 i 为 ai 在线性表中的位序。,2020年9月22日星期二,第10页,基本

5、操作：,结构初始化操作,结构销毁操作,引用型操作,加工型操作, ADT List,2020年9月22日星期二,第11页,InitList( ,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB, i)e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),操作步骤：,2020年9月22日星期二,第30页,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e

6、相同的数据元素，则插入之,void union(List ,for (i = 1; i = Lb_len; i+) , / union,2020年9月22日星期二,第31页,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同的数据元素。,仍选用线性表表示集合。,例 2-2,2020年9月22日星期二,第32页,集合 B,集合 A,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,2020年9月22日星期二,第33页,void union(List / union,GetElem(Lb, i, e); / 取

7、Lb中第 i 个数据元素赋给 e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之,for (i = 1; i = Lb_len; i+) ,InitList(La); / 构造(空的)线性表LA,2020年9月22日星期二,第34页,若线性表中的数据元素相互之间可以比较，并且数据元素在线性表中依值非递减或非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称该线性表为有序表(Ordered List)。,我们再来看看有序表表示的集合。,2020

8、年9月22日星期二,第35页,例如： LA=(3,5,8,11) LB=(2,6,8,9,11,15,20),对集合LA和LB 而言， 值相同的数据元素必定相邻。,要求生成一个新表LC，使LC中的数据元素仍按值非递减有有序排列。,2020年9月22日星期二,第36页,void MergeList(List La, List Lb, List / 构造空的线性表 Lc i = j = 1; k = 0; La_len = ListLength(La); Lb_len = ListLength(Lb);,例 2-3,2020年9月22日星期二,第37页,while (i = La_len) / 当

9、La不空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素,While( (i = La_len)+j ,2020年9月22日星期二,第38页,2.2 线性表类型 的实现-顺序映象,2020年9月22日星期二,第39页,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。,顺序映象, 以 x 的存储位置和 y 的存储位置之间某种关

10、系表示逻辑关系。,2020年9月22日星期二,第40页,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,2020年9月22日星期二,第41页,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址,2020年9月22日星期二,第42页,顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,#define LIST_

11、INIT_SIZE 80 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 / 线性表存储空间的分配增量,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),2020年9月22日星期二,第43页,线性表的基本操作在顺序表中的实现,InitList( if (!L.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE return OK;,2020年9月2

12、2日星期二,第45页,例如：顺序表的查找操作,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。,2020年9月22日星期二,第46页,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq,O( ListLength(L) ),算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序 p = L.

13、elem; / p 的初值为第 1 元素的存储位置,while (i = L.length ,if (i = L.length) return i; else return 0;,(*compare)(*p+, e),2020年9月22日星期二,第47页,c 运算符优先表,运算符 结合性 - 最高() - . !+- (type)* if (!newbase) exit(OVERFLOW); / 存储分配失败 L.elem = newbase; / 新基址 L.listsize += LISTINCREMENT; / 增加存储容量 ,if (i L.length+1) return ERROR

14、; / 插入位置不合法,2020年9月22日星期二,第53页,例如：ListInsert_Sq(L, 5, 66),L.length-1,0,87,56,42,66,q = ,2020年9月22日星期二,第54页,线性表操作 ListDelete( p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,元素左移,2020年9月22日星期二,第57页,考虑

15、移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,2020年9月22日星期二,第58页,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(L, 5, e),2020年9月22日星期二,第59页,2.3 线性表类型 的实现-链式映象,2020年9月22日星期二,第60页,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、一个带头结点的单链表类型,五、其它形式的链表,六、有序表类型

16、,2020年9月22日星期二,第61页,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结点 (表示数据元素 或 数据元素的映象),以“结点的序列”表示线性表 称作链表,2020年9月22日星期二,第62页,以线性表中第一个数据元素 的存储地址作为线性表的地址，称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便，在第一个结点之前虚加一个“头结点”，以指向头结点的指针为链表的头指针。,空指针,线性表为空表时， 头结点的指针域为空,2020年9月22日星期二,第63页,Typedef struct LNode

17、 ElemType data; / 数据域 struct Lnode *next; / 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L； / L 为单链表的头指针,2020年9月22日星期二,第64页,三、单链表操作的实现,GetElem(L, i, e) / 取第i个数据元素,ListInsert( j = 1; / p指向第一个结点，j为计数器,while (p / 顺指针向后查找，直到 p 指向第 i 个元素 / 或 p 为空,if ( !p | ji ) return ERROR; / 第 i 个元素不存在 e = p-data; /

18、 取得第 i 个元素 return OK;,2020年9月22日星期二,第68页,线性表的操作 ListInsert( j = 0; while (p / i 大于表长或者小于1,2020年9月22日星期二,第71页,s = (LinkList) malloc ( sizeof (LNode); / 生成新结点 s-data = e; s-next = p-next; p-next = s; / 插入 return OK;,s,p,2020年9月22日星期二,第72页,线性表的操作ListDelete ( p-next = q-next; e = q-data; free(q);,p,q,20

19、20年9月22日星期二,第74页,Status ListDelete_L(LinkList L, int i, ElemType j = 0; while (p-next / 删除位置不合理,q = p-next; p-next = q-next; / 删除并释放结点 e = q-data; free(q); return OK;,2020年9月22日星期二,第75页,操作 ClearList(,算法时间复杂度：,O(ListLength(L),2020年9月22日星期二,第76页,如何从得到单链表？,链表是一个动态的结构，它不需要予分配空间，因此生成链表的过程是一个结点“逐个插入” 的过程。

20、,2020年9月22日星期二,第77页,例如：逆位序输入 n 个数据元素的值， 建立带头结点的单链表。(头插法),操作步骤：,一、建立一个“空表”；,二、输入数据元素an， 建立结点并插入；,三、输入数据元素an-1， 建立结点并插入；,an,an,an-1,四、依次类推，直至输入a1为止。,2020年9月22日星期二,第78页,void CreateList_L(LinkList L-next = NULL; / 先建立一个带头结点的单链表,for (i = n; i 0; -i) p = (LinkList) malloc (sizeof (LNode); scanf( / 插入 ,202

21、0年9月22日星期二,第79页,i=0,i=1,i=2,i=3,head,采用头插法建立单链表的过程,head,head,head,head,第1步:建头结点,第2步:i0,新建a结点,插入到头结点之后,第3步:i1,新建d结点,插入到头结点之后,第4步:i2,新建c结点,插入到头结点之后,第5步:i3,新建b结点,插入到头结点之后,2020年9月22日星期二,第80页,/尾插法生成单链表 (自学) void CreateListR(LinkList */*终端结点next域置为NULL*/ ,2020年9月22日星期二,第81页,i=0,i=1,i=2,i=3,head,头结点,采用尾插法建

22、立单链表的过程,2020年9月22日星期二,第82页,/算法2.12，实现两个有序表的合并 void MergeList ( LinkList 算法2.7和2.12的时间复杂度相同，但空间复杂度不同。,2020年9月22日星期二,第83页,例2.4 设C=a1,b1,a2,b2,an,bn为一线性表,采用带头结点的hc单链表存放,编写一个算法,将其拆分为两个线性表,使得: A=a1,a2,an,B=b1,b2,bn,解:设拆分后的两个线性表都用带头结点的单链表存放。先建立两个头结点*ha和*hb,它们用于存放拆分后的线性表A和B, ra和rb分别指向这两个单链表的表尾。 用p指针扫描单链表hc

23、,将当前结点*p链到ha未尾, p沿next域下移一个结点,若不为空, 则当前结点*p链到hb未尾, p沿next域下移一个结点, 如此这样, 直到p为空。最后将两个尾结点的next域置空。,2020年9月22日星期二,第84页,void fun(LinkList *hc, LinkList * /*rb始终指向hb的末尾结点*/,本算法实际上是采用尾插法建立两个新表。所以,尾插法建表算法是很多类似习题的基础！,2020年9月22日星期二,第85页,while (p!=NULL) ra-next=p; ra=p; /*将*p链到ha单链表未尾*/ p=p-next; if (p!=NULL)

24、rb-next=p; rb=p; /*将*p链到hb单链表未尾*/ p=p-next; ra-next=rb-next=NULL; /*两个尾结点的next域置空*/ ,2020年9月22日星期二,第86页,用上述定义的单链表实现线性表的操作时， 存在的问题：,改进链表的设置(教材p37-39),1单链表的表长是一个隐含的值；,1增加“表长”、“表尾指针” 和 “当前位置的 指针” 三个数据域；,2在单链表的最后一个元素之后插入元素时， 需遍历整个链表；,3在链表中，元素的“位序”概念淡化，结点的 “位置”概念加强。,2将基本操作中的“位序 i ”改变为“指针 p ”。,2020年9月22日星

25、期二,第87页,四、一个带头结点的线性链表类型,typedef struct LNode / 结点类型 ElemType data; struct LNode *next; *Link, *Position;,Status MakeNode( Link / 分配由 p 指向的值为e的结点，并返回OK， / 若分配失败，则返回 ERROR,void FreeNode( Link / 释放 p 所指结点,2020年9月22日星期二,第88页,typedef struct / 链表类型 Link head, tail; / 分别指向头结点和 / 最后一个结点的指针 int len; / 指示链表长度

26、 Link current; / 指向当前被访问的结点 /的指针，初始位置指向头结点 LinkList;,2020年9月22日星期二,第89页,链表的基本操作:,结构初始化和销毁结构,Status InitList( LinkList / 构造一个空的线性链表 L，其头指针、 / 尾指针和当前指针均指向头结点， / 表长为零。,Status DestroyList( LinkList / 销毁线性链表 L，L不再存在。,O(1),O(n),2020年9月22日星期二,第90页,引用型操作,Status ListEmpty ( LinkList L ); /判表空,int ListLength(

27、 LinkList L ); / 求表长,Status Prior( LinkList L ); / 改变当前指针指向其前驱,Status Next ( LinkList L ); / 改变当前指针指向其后继,ElemType GetCurElem ( LinkList L ); / 返回当前指针所指数据元素,O(1),O(1),O(n),O(1),O(1),2020年9月22日星期二,第91页,Status LocatePos( LinkList L, int i ); / 改变当前指针指向第i个结点,Status LocateElem (LinkList L, ElemType e, St

28、atus (*compare)(ElemType, ElemType); / 若存在与e 满足函数compare( )判定关系的元 / 素，则移动当前指针指向第1个满足条件的 / 元素的前驱，并返回OK; 否则返回ERROR,Status ListTraverse(LinkList L, Status(*visit)() ); / 依次对L的每个元素调用函数visit(),O(n),O(n),O(n),2020年9月22日星期二,第92页,加工型操作,Status ClearList ( LinkList / 重置 L 为空表,Status SetCurElem(LinkList / 更新当前

29、指针所指数据元素,Status Append ( LinkList / 在表尾结点之后链接一串结点,Status InsAfter ( LinkList / 将元素 e 插入在当前指针之后,Status DelAfter ( LinkList / 删除当前指针之后的结点,O(1),O(n),O(s),O(1),O(1),2020年9月22日星期二,第93页,Status InsAfter( LinkList / 否则返回ERROR。 / InsAfter,if ( ! L.current ) return ERROR; if (! MakeNode( s, e) ) return ERROR;

30、 s-next = L.current-next; L.current-next = s; if (L.tail = L.current) L.tail = s; L.current = s; return OK;,2020年9月22日星期二,第94页,Status DelAfter( LinkList 否则返回ERROR。 /DelAfter,if ( !(L.current ,2020年9月22日星期二,第95页,1. 双向链表,五、其它形式的链表,typedef struct DuLNode ElemType data; / 数据域 struct DuLNode *prior; / 指向

31、前驱的指针域 struct DuLNode *next; / 指向后继的指针域 DuLNode, *DuLinkList;,2020年9月22日星期二,第96页,最后一个结点的指针域的指针又指回第一个结点的链表,a1 a2 . an,2. 循环链表,和单链表的差别仅在于，判别链表中最后一个结点的条件不再是“后继是否为空”，而是“后继是否为头结点”。,2020年9月22日星期二,第97页,双向循环链表,空表,非空表,a1 a2 . an,2020年9月22日星期二,第98页,双向链表的操作特点：,“查询” 和单链表相同。,“插入” 和“删除”时需要同时修改两个方向上的指针。,2020年9月22日

32、星期二,第99页,s-next = p-next; p-next = s; s-next-prior = s; s-prior = p;,p,s,插入,2020年9月22日星期二,第100页,删除,p-next = p-next-next; p-next-prior = p;,p,2020年9月22日星期二,第101页,六、有序表类型,ADT Ordered_List 数据对象: S = xi|xi OrderedSet ， i=1,2,n, n0 ,集合中 任意两个 元素之间 均可以 进行比较,数据关系:R = | xi-1, xi S, xi-1 xi, i=2,3,n ,回顾例2-2的两个算法,2020年9月22日星期二,第102页,LocateElem( L, e, / 系数 int expn; / 指数 term, ElemType;,typedef OrderedLinkList polynomial; / 用带表头结点的有序链表表示多项式,结点的数据元素类型定义为:,2020年