《数据结构C语言 版第 二章课件》由会员分享，可在线阅读，更多相关《数据结构C语言 版第 二章课件（93页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性表,教学要求： 理解线性表的概念 掌握线性表的抽象数据类型和应具有的基本操作 掌握线性表的顺序存储结构的实现方法 掌握线性表的链表存储结构的实现方法 掌握线性表的简单应用,教学重点： 线性表的抽象数据类型 线性表的顺序存储结构 线性表的链式存储结构 线性表的简单应用,教学难点： 线性表算法的设计与实现,线性结构的基本特征为:,1集合中必存在唯一的一个“第一元素”；,2集合中必存在唯一的一个 “最后元素” ；,3除最后元素在外，均有 唯一的后继；,4除第一元素之外，均有 唯一的前驱。,线性结构 是 一个数据元素的有序（次序）集,线性表是一种最简单的线性结构,2.1 线性表的类型定义,
2、线性表：线性表是n个元素的有序序列，是最常用且最简单的一种数据结构。,（a0, a1, ai-1，ai, ai1 ，, an-1）,线性表的逻辑结构：,n=0时称为,数据元素,线性起点,ai的直接前趋,ai的直接后继,下标，是元素的序号，表示元素在表中的位置,n为元素总个数，即表长。n0,空表,线性终点,（ A, B, C, D, , Z）,例2 分析学生情况登记表是什么结构。,分析：数据元素都是同类型（记录），元素间关系是线性的。,分析： 数据元素都是同类型（字母）， 元素间关系是线性的。,注意：同一线性表中的元素必定具有相同特性 ！,例1 分析26 个英文字母组成的英文表是什么结构。,综上
3、例： 线性表中的数据元素可以是各种各样的 但同一个表中的元素必须具有相同的特性 相邻数据元素之间存在序偶关系 线性表中每一个元素都有确定的位置，如a1是第一个数据元素，ai是第i个数据元素,抽象数据类型线性表的定义如下：,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 在线性表中的位序。,基本操作：,结构初始化操作,结构销毁操作,引用型操作
4、,加工型操作, ADT List,InitList( &L ),操作结果：,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList( &L ),初始条件： 操作结果：,线性表 L 已存在。,销毁线性表 L。,ListEmpty( L ),ListLength( L ),PriorElem( L, cur_e, &pre_e ),NextElem( L, cur_e, &next_e ),GetElem( L, i, &e ),LocateElem( L, e, compare( ) ),ListTraverse(L, visit( ),引用型操作:,加工型操作,ClearLi
5、st( &L ),ListInsert( &L, i, e ),ListDelete(&L, i, &e),利用上述定义的线性表 可以实现其它更复杂的操作,例 2-2,例 2-1,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示，即：线性表中的数据元素即为集合中的成员。 现要求一个新的集合AAB。,例 2-1,要求对线性表作如下操作： 扩大线性表 LA，将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可演绎为：,1从线性表LB中取出一个数据元素;,2依值在线性表LA中进行查访;,3若不存在，则插入之。,GetElem(LB, i
6、)e,LocateElem(LA, e, equal( ),ListInsert(LA, n+1, e),操作步骤：,4重复上述过程，直到访问到LB中所有元素。,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素，则插入之,void union(List ,for (i = 1; i = Lb_len; i+) , / union,已知一个非纯集合 B，试构造一个纯集合 A，使 A中只包含 B 中所有值各不相 同
7、的数据元素。,仍选用线性表表示集合。,例 2-2,集合 B,集合 A,从集合 B 取出物件放入集合 A 要求集合A中同样物件不能有两件以上,因此，算法的策略应该和例2-1相同,void union(List / union,GetElem(Lb, i, e); / 取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,2.2 线
8、性表类型 的实现-顺序映象,最简单的一种顺序映象方法是： 令 y 的存储位置和 x 的存储位置相邻。,顺序映象, 以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。,用一组地址连续的存储单元 依次存放线性表中的数据元素,a1 a2 ai-1 ai an,线性表的起始地址 称作线性表的基地址,以“存储位置相邻”表示有序对 即：LOC(ai) = LOC(ai-1) + C 一个数据元素所占存储量,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) = LOC(a1) + (i-1)C 基地址,在C语言中，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组
9、实现线性表的顺序存储。,顺序映像的 C 语言描述,typedef struct SqList; / 俗称 顺序表,ElemType *elem; / 存储空间基址,int length; / 当前长度,int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位),typedef struct ElemType listMaxSize; int size; SqList; /* MaxSize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size MaxSize，SqList是该结构体的名字。*/
10、,线性表的基本操作在顺序表中的实现,InitList(&L) / 结构初始化,LocateElem(L, e, compare() / 查找,ListInsert(&L, i, e) / 插入元素,ListDelete(&L, i) / 删除元素,Status InitList_Sq( SqList& L ) / 构造一个空的线性表 / InitList_Sq,算法时间复杂度：,O(1),L.elem = (ElemType*) malloc (LIST_ INIT_SIZEsizeof (ElemType); if (!L.elem) exit(OVERFLOW);,L.length = 0
11、; L.listsize = LIST_INIT_SIZE return OK;,线性表操作 LocateElem(L, e, compare() 的实现,先看一下查找的过程:,例如：顺序表,e =,38,i,1,2,3,4,1,8,50,可见，基本操作是： 将顺序表中的元素 逐个和给定值 e 相比较。,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素， / 若存在，则返回它的位序，否则返回 0 / LocateElem_Sq,O( List
12、Length(L) ),算法的时间复杂度为：,i = 1; / i 的初值为第 1 元素的位序 p = L.elem; / p 的初值为第 1 元素的存储位置,while (i = L.length ,if (i = L.length) return i; else return 0;,(*compare)(*p+, e),线性表操作 ListInsert(&L, i, e)的实现：,首先分析:,插入元素时， 线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, , an) 改变为 (a1, , ai-1, e, ai, , an), ,例如：ListInsert_Sq(L, 5,
13、 66),L.length-1,0,87,56,42,66,q = ,Status ListInsert_Sq(SqList &L, int i, ElemType e) / 在顺序表L的第 i 个元素之前插入新的元素e, / i 的合法范围为 1iL.length+1 / ListInsert_Sq,算法时间复杂度为:,O( ListLength(L) ),q = ,元素右移,考虑移动元素的平均情况:,假设在第 i 个元素之前插入的概率为 ， 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行插入的概率都是相等的，则移动元素的期望值为：,线性
14、表操作 ListDelete(&L, i, &e)的实现：,首先分析：,删除元素时， 线性表的逻辑结构发生什么变化？,(a1, , ai-1, ai, ai+1, , an) 改变为 (a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,L.length-1,0,87,56,p = ,例如：ListDelete_Sq(L, 5, e),Status ListDelete_Sq (SqList &L, int i, ElemType &e) / ListDelete_Sq,for (+p; p = q; +p) *(p-1) = *p; / 被删除元素之后的元素左移
15、 -L.length; / 表长减1 return OK;,算法时间复杂度为:,O( ListLength(L),p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,元素左移,考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的期望值为：,若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：,问题： 、在顺序表中，第个元素前面插入一个元素，要移动多少个元素？ 、在顺序表中，要删除第个元素，要移动多少个元素？,作业: 用C语言编写代码,实现顺序表里面所有的操作。,2.3 线性表类型 的实现-链式映象,一、单链表,二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、静态链表,五、其它形式的链表,主要内容:,一、单链表,二、线性表的操作在单链表中的实现,重点:,线性表的操作在单链表中的实现: 包括在单链表中查找、插入、删除 一个元素以及生成一个单链表的算法,难点:,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象) + 指针(指示后继元素存储位置) = 结
