中南大学.ppt
《中南大学.ppt》由会员分享,可在线阅读,更多相关《中南大学.ppt(103页珍藏版)》请在三一文库上搜索。
1、数据结构 Data Structure,中南大学,中南大学信息院计科系,主讲人:王国军,郑瑾,csgjwang, http:/ 手机:13508486821 办公室:校本部计算机楼406-B,本PPT根据数据结构教材(清华大学)制作,仅供中南大学计算机科学与技术专业及相关专业11级本科生和任课老师使用。,第二章 线性表,提 纲,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,2.1 线性表的类型定义,1集合中必存在唯一的“第一个元素”;,2集合中必存在唯一
2、的 “最后一个元素”;,3除最后一个元素之外,均有 唯一的后继;,4除第一个元素之外,均有 唯一的前驱。,线性结构是一个数据元素的有序集。对非空有限集:,线性结构的基本特征:,线性表的定义,线性表是由n(n0)个类型相同的数据元素组成的有限序列。通常表示成下列形式: L=(a1, a2,.,ai-1,ai,ai+1,.,an) 其中: L为线性表的名称; ai为组成该线性表的数据元素,i为数据元素ai在线性表中的位序; n为线性表中数据元素的个数,称为线性表的长度。当n=0时,线性表为空,又称为空线性表。,抽象数据类型线性表的定义,ADT List ,数据对象:,D ai | ai ElemS
3、et, i=1,2,.,n, n0 ,数据关系:,R1 |ai-1, aiD, i=2,.,n ,基本操作:,InitList( &L ),操作结果:,构造一个空的线性表L。,初始化操作,结构销毁操作,DestroyList( &L ),初始条件: 操作结果:,线性表 L 已存在。,销毁线性表 L。,ListEmpty( L ),初始条件: 操作结果:,线性表 L 已存在。,若 L 为空表,则返回 TRUE,否则FALSE。,线性表判空操作,ListLength( L ),初始条件: 操作结果:,线性表 L 已存在。,返回 L 中数据元素的个数。,求线性表的长度,PriorElem( L, c
4、ur_e, &pre_e ),初始条件: 操作结果:,线性表 L 已存在。,若 cur_e 是 L 的元素,则用pre_e 返回它的前驱,否则操作失败,pre_e无定义。,求数据元素的前驱,NextElem( L, cur_e, &next_e ),初始条件: 操作结果:,线性表 L 已存在。,若 cur_e 是 L 的元素,则用next_e 返回它的后继,否则操作失败,next_e无定义。,求数据元素的后继,GetElem( L, i, &e ),初始条件: 操作结果:,线性表 L 已存在,,用 e 返回 L 中第 i 个数据元素的值。,求线性表中某个数据元素,并且 1iListLength
5、(L) 。,LocateElem( L, e, compare( ) ),初始条件: 操作结果:,线性表 L 已存在,e 为给定值, compare( ) 是元素判定函数。,返回 L 中第 1 个与 e 满足关系 compare( ) 的元素的位序。 若这样的元素不存在,则返回值为 0。,定位函数,ListTraverse(L, visit( ),初始条件: 操作结果:,线性表 L 已存在。 visit( ) 为某个访问函数。,依次对 L 中每个元素调用 函数visit( )。一旦 visit( )失败,则操作失败。,遍历线性表,ClearList( &L ),初始条件: 操作结果:,线性表
6、L 已存在。,将 L 重置为空表。,线性表置空,PutElem( &L, i, &e ),初始条件: 操作结果:,线性表 L 已存在,,L 中第 i 个元素赋值 e 。,改变数据元素的值,并且 1iListLength(L) 。,ListInsert( &L, i, e ),初始条件: 操作结果:,线性表 L 已存在,,在 L 中的第 i 个元素之前插入 新的元素 e,L 的长度增1。,插入数据元素,且 1iListLength(L)+1 。,ListDelete(&L, i, &e ),初始条件: 操作结果:,线性表 L 已存在并且非空,,删除 L中的第 i 个元素,并且用 e 返回其值,L
7、 的长度减1。,删除数据元素,且 1iListLength(L) 。, ADT List,利用上述定义的线性表类型,可以实现其它更为复杂的操作:,例 2-2,例 2-1,有两个集合 A 和 B,分别用两个线性表 LA 和 LB 表示,即:线性表中的数据元素即为集合中的成员。 求一个新的集合AAB。,例 2-1,要求对线性表作如下操作:扩大线性表 LA,将在线性表LB 中而不在线性表 LA 中的数据元素插入到线性表 LA 中去。,上述问题可转换为:,1从线性表 LB 中依次查看每个数据元素:,2依次在线性表 LA 中进行查访:,3若不存在,则插入之:,GetElem(LB, i, e),Loca
8、teElem(LA, e, equal( ),ListInsert(LA, n+1, e) ( n 表示线性表 LA 当前长度),操作步骤:,GetElem(Lb, i, e); / 取Lb中第i个数据元素赋给e if (!LocateElem(La, e, equal( ) ) ListInsert(La, +La_len, e); / La中不存在和 e 相同的数据元素,则插入之,La_len = ListLength(La); / 求线性表的长度 Lb_len = ListLength(Lb);, / union,void union(List &La, List Lb) ,for (i
9、=1; i=Lb_len; i+),/for,若线性表中的数据元素相互之间可以比较,并且数据元素在表中按值非递减或非递增有序排列,即 aiai-1 或 aiai-1(i = 2,3, n),则称该线性表为有序表(Ordered List)。,接下来,考虑用有序表表示集合:,则,归并两个“其数据元素按值非递减有序排列”的有序表 LA 和 LB,求得有序表 LC 也具有同样特性。,设 La = (a1, , ai, , an), Lb = (b1, , bj, , bm) Lc = (c1, , ck, , cm+n) 且已由(a1, , ai-1)和(b1, ,bj-1)归并得 (c1, , c
10、k-1),例 2-2,k = 1, 2, , m+n,1初始化 LC 为空表;,基本操作:,2分别从 LA和LB中取得当前元素 ai 和 bj;,3若 aibj,则将 ai 插入到 LC 中,否则将 bj 插入到 LC 中;,4重复 2 和 3 两步,直至 LA 或 LB 中元素 被取完为止;,5将 LA 表或 LB 表中剩余元素复制并插入到 LC 表中。,void MergeList(List La, List Lb, List &Lc) / 本算法将非递减的有序表 La 和 Lb 归并为 Lc,while (i = La_len) & (j = Lb_len) / La 和 Lb 均非空,
11、InitList(Lc); / 构造空的线性表 Lc i = j = 1; k = 0; / i,j,k分别用来指向La,Lb,Lc /当前操作的元素位置 La_len = ListLength(La); Lb_len = ListLength(Lb);,GetElem(La, i, ai); GetElem(Lb, j, bj); if (ai = bj) / 将 ai 插入到 Lc 中 ListInsert(Lc, +k, ai); +i; else / 将 bj 插入到 Lc 中 ListInsert(Lc, +k, bj); +j; ,while (i = La_len) / 当La不
12、空时 GetElem(La, i+, ai); ListInsert(Lc, +k, ai); / 插入 La 表中剩余元素,while (j = Lb_len) / 当Lb不空时 GetElem(Lb, j+, bj); ListInsert(Lc, +k, bj); / 插入 Lb 表中剩余元素, / merge_list,O(ListLength(La) + ListLength(Lb),算法的时间复杂度为:,最简单的一种顺序映象方法是: 令 y 的存储位置和 x 的存储位置相邻。,2.2 线性表的顺序表示和实现,一、线性表的顺序表示,定义:用一组地址连续的存储单元依次存储线性表的数据元
13、素,称为线性表的顺序存储结构。,线性表的起始地址, 也称为线性表的基地址。,元素地址(存储位置)计算方法: LOC(ai)=LOC(a1)+(i-1)*m 其中:m一个元素占用的存储单元个数 LOC(ai)线性表第i个元素的地址 LOC(a1)线性表首址,又称为基址,顺序表的特点: 实现逻辑上相邻物理地址相邻 实现随机存取,#define LIST_INIT_SIZE 100 /线性表存储空间的初始分配量 #define LISTINCREMENT 10 /线性表存储空间的分配增量 typedef struct ElemType *elem; /存储空间基址 int length; /当前长度
14、 int listsize; /当前分配的存储容量,初始化时等于LIST_INIT_SIZE SqList;,顺序表的表示,线性表的动态分配顺序存储结构,#define M 100 typedef struct ElemType elemM; int length; SqList;,数据元素不是简单类型时,可定义结构体数组。,例: typedef struct card int num; char name20; char author10; char publisher30; float price; LibraryM;,线性表的基本操作在顺序表中的实现,InitList(&L) / 结构初
15、始化,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_SIZE* sizeof(ElemType); if (!L.elem) exit(OVERFLOW);,L.length = 0; L.listsize = LIST_INIT_SIZE; return
16、OK;,int LocateElem_Sq(SqList L, ElemType e, Status (*compare)(ElemType, ElemType) / 在顺序表中查询第一个满足判定条件的数据元素, / 若存在,则返回它的位序,否则返回 0 / LocateElem_Sq,O(L.length),if (i = L.length) return i; else return 0;,算法的时间复杂度为:,i = 1; / i 的初值为第 1 个元素的位序 p = L.elem; / p 的初值为第 1 个元素的存储位置,while (i = L.length ,/找到满足条件的元素
17、,/ 没有找到满足条件的元素,线性表操作 ListInsert(&L, i, e)的实现:,首先分析:,插入元素时, 线性表的逻辑结构发生什么变化?,(a1, , ai-1, ai, , an) 改变为, ,(a1, , ai-1, e, ai, , an),Status ListInsert_Sq(SqList ,q = / ListInsert_Sq,算法时间复杂度为:,O(L.length),考虑移动元素的平均情况,假设在第 i 个元素之前插入的概率为 , 则在长度为n 的线性表中插入一个元素所需移动元素次数的期望值为:,假设在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素次
18、数的期望值为:,线性表操作 ListDelete(&L, i, &e)的实现:,首先分析:,删除元素时, 线性表的逻辑结构发生什么变化?,(a1, , ai-1, ai, ai+1, , an) 改变为,ai+1,an, ,表的长度减少1,(a1, , ai-1, ai+1, , an),Status ListDelete_Sq(SqList &L, int i, ElemType &e) / ListDelete_Sq,for ( +p; p = q; +p ) *(p-1) = *p; / 被删除元素之后的元素左移 -L.length; / 表长减1 return OK;,算法时间复杂度为
19、:,O(L.length),p = / 表尾元素的位置,if (i L.length) return ERROR; / 删除位置不合法,考虑移动元素的平均情况,假设删除第 i 个元素的概率为 , 则在长度 为 n 的线性表中删除一个元素所需移动元素次数的期望值为:,假设在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素次数的期望值为:,算法时间复杂度为:,O (n),顺序存储结构的优缺点,逻辑相邻,物理相邻 可随机存取任一元素 存储空间使用紧凑,插入、删除操作需要移动大量的元素 预先分配空间需按最大空间分配,利用不充分,缺点:,优点:,2.3 线性表的链式表示和实现,一、单链表(线性
20、链表),二、结点和单链表的 C 语言描述,三、线性表的操作在单链表中的实现,四、循环链表,五、双向链表,用一组地址任意的存储单元存放线性表中的数据元素。,一、单链表,以元素(数据元素的映象) + 指针(指示后继元素的存储位置) = 结点 (表示数据元素及关系的映象),以“结点的序列”表示线性表 称作链表,以线性表中第一个数据元素 的存储地址作为线性表的地址,称作线性表的头指针。,头结点,头指针,头指针,有时为了操作方便,在第一个数据元素结点之前增加一个“虚”的“头结点”,并且以指向头结点的指针作为链表的头指针。,空指针,线性表为空表时, 头结点的指针域为空,typedef struct LNo
21、de ElemType data; / 数据域 struct LNode *next; / 指针域 LNode, *LinkList;,二、结点和单链表的 C 语言描述,LinkList L; / L 为单链表的头指针,三、单链表操作的实现,GetElem(L, i, &e) / 取第i个数据元素,ListInsert(&L, i, e) / 插入数据元素,ListDelete(&L, i, &e) / 删除数据元素,ClearList(&L) / 重置线性表为空表,CreateList(&L, n) / 生成含 n 个数据元素的链表,线性表的操作 GetElem(L, i, &e),单链表是
22、一种顺序存取的存储结构,为找第 i 个数据元素,先要找到第 i-1 个数据元素。,因此,查找第 i 个数据元素的基本操作为:移动指针,比较 j 和 i 。,令指针 p 始终指向线性表中第 j 个数据元素。,Status GetElem_L(LinkList L, int i, ElemType &e) / L是带头结点的链表的头指针,以 e 返回第 i 个元素 / GetElem_L,算法时间复杂度为:,O(ListLength(L),p = L-next; j = 1; /p指向第一个结点,j为计数器,while (p / 顺指针向后查找,直到 p 指向第 i 个元素或 p 为空,if (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 中南 大学
链接地址:https://www.31doc.com/p-3371322.html