制作崔广才wwwcmscusteducnppt课件.ppt
《制作崔广才wwwcmscusteducnppt课件.ppt》由会员分享,可在线阅读,更多相关《制作崔广才wwwcmscusteducnppt课件.ppt(84页珍藏版)》请在三一文库上搜索。
1、制作:崔广才 ,第二章 线性表,2.1 线性表的类型定义 2.2 线性表的顺序表示和实现 2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表 2.4 一元多项式的表示及相加,线性表(Linear List) : 由n(n0)个数据元素(结点)a1,a2,an组成的有限序列. 数据元素的个数n定义为表的长度。当n=0时称为空表 常常将非空的线性表(n0)记作:(a1,a2,ai,an) 这里的数据元素ai(1in)只是一个抽象的符号,其具体含义在不同的情况下可以不同。 同一个线性表中的元素必须属于同一种数据类型.,2.1 线性表的类型定义,例1、26
2、个大写英文字母组成的字母表 (A,B, Z),例2、某校从1978年到1983年各种型号的计算机拥有量的变 化情况。 (6,17,28,50,92,188),例3、学生健康情况登记表如下:,2.1 线性表的类型定义,例4、一副扑克的点数 (2,3,4,J,Q,K,A),线性表的逻辑特征: 1)在非空的线性表,有且仅有一个开始结点a1,它没 有直接前趋,而仅有一个直接后继a2 2)有且仅有一个终端结点an,它没有直接后继,而仅 有一个直接前趋an-1; 3)其余的内部结点ai(2in-1)都有且仅有一个直接 前趋a i-1和一个直接后继ai+1。 线性表的逻辑结构是一种典型的线性结构。,2.1
3、线性表的类型定义,2.1 线性表的类型定义,抽象数据类型线性表的定义如下:,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 在线性表中的位序。,基本操作:,InitList( &L ),操作结果:,构造一个空的线性表L,DestroyList( &L ),初始条件: 操作结果:,线性表 L 已存在,销毁线性表 L,基本操作:,基本操作
4、:,ListInsert( &L, i, e ),初始条件: 操作结果:,线性表L已存在, 且 1iLengthList(L)+1,在L的第i个元素上插入新的元素e, L的长度增1。,(插入数据元素),基本操作:,ListDelete(&L, i, &e),初始条件: 操作结果:,线性表L已存在且非空, 1iLengthList(L),删除L的第i个元素,并用e返回其值,L的长度减1。,(删除数据元素),基本操作:,ListTraverse(L, Visit( ),(遍历线性表),初始条件: 操作结果:,线性表L已存在。Visit() 为某个访问函数。,依次对L的每个元素调用函数Visit(
5、)。一旦visit( )失败,则操作失败。, ADT List,基本操作:,利用上述定义的线性表,可以实现其它复杂的操作,假设:有两个集合 A 和 B 分别用两个线性表 LA 和 LB 表示,即:线性表中的数据元素即为集合中的成员。 现要求生成一个新的集合AAB。,例 2-1,上述问题可演绎为: 要求对线性表作如下操作: 扩大线性表 LA,将存在于线性表LB 中而不存在于线性表 LA 中的数据元素插入到线性表 LA 中去。,void union(List /在逻辑结构上的算法实现 算法2.1,例2-2 巳知线性表LA和线性表LB中的数据元素按值非递减有序排列, 现要求将LA和LB归并为一个新的
6、线性表LC,且LC中的元素仍按 值非递减有序排列。 如 LA=(3, 5, 8, 11) LB=(2, 6, 8, 9, 11, 15, 20) 则LC=(2, 3, 5, 6, 8, 8, 9, 11, 11, 15, 20),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
7、 /end while,while(i=la-len) GetElem(la,i+, ai); ListInsert(lc,+k, ai); / 插入 La 表中剩余元素 while(j=lb-len) GetElem(lb,j+, bj); ListInsert(lc,+k, bj); /end mergelist 算法2.2,一、顺序表 把线性表的元素按逻辑顺序依次存放在一组地址连续的存储单元里,用这种方法存储的线性表简称顺序表。,2.2 线性表的顺序表示和实现,a1 a2 ai-1 ai an,线性表的起始地址, 称作线性表的基地址,以“存储位置相邻”表示有序对 即:LOC(ai) =
8、LOC(ai-1) + L,所有数据元素的存储位置均取决于 第一个数据元素的存储位置 LOC(ai) =LOC(a1) + (i-1)L,一个数据元素所占存储量,2.2 线性表的顺序表示和实现,基地址,#define LIST_INIT_SIZE 100 / 线性表存储空间的初始分配量 #define LISTINCREMENT 10 typedef struct ElemType *elem; / 存储空间基址 int length; / 当前数据元素的个数(即线性表的长度) int listsize; / 当前分配的存储容量 / (以sizeof(ElemType)为单位) Sqlist;
9、,2.2 线性表的顺序表示和实现,二、顺序表上实现的基本操作 注意:C语言中的数组下标从“0”开始,因此,若L是Sqlist 类型的顺序表,则表中第i个元素是L.elemi-1。,2.2 线性表的顺序表示和实现,1、初始化 Status InitList_sq(SqList /end of InitList_sq,算法时间复杂度:,O(1),L.elem,L.length=0 L.listsize= LIST-INIT-SIZE,LIST-INIT-SIZE-1,0 1 2 3 4 5 6 ,2.2 线性表的顺序表示和实现,2、插入算法 线性表的插入操作是指在表的第i-1个数据元素和第i个数据
10、元素之间插入一个新的数据元素x,使长度为n的线性表.,2.2 线性表的顺序表示和实现,(a1, , ai-1, ai, , an) 改变为(a1, , ai-1, e, ai, , an), ,Status ListInsert_Sq(SqList / ListInsert_Sq,算法时间复杂度为:,O( L.length ),void *realloc(ptr, newsize)功能: 把由ptr所指向的已分配的内存大小变为由newsize所确定的新的大小. newsize值可以小于或大于原先的值,若分配成功,函数返回新分配的内存的首址,并把原先块的内容拷贝到新块中,信息不会丢失;否则,函数
11、将返回空指针.,例如:ListInsert_Sq(L, 5, 66),L:,q = / q 指示插入位置,例如:ListInsert_Sq(L, 5, 66),21 18 30 75 42 56 87,0 1 2 3 4 5 L.length-1,L:,for (p = ,例如:ListInsert_Sq(L, 5, 66),21 18 30 75 42 56,0 1 2 3 4 5 L.length-1,L:,87,for (p = ,例如:ListInsert_Sq(L, 5, 66),for (p = ,考虑移动元素的平均情况:,假设在第 i 个元素上插入的概率为 , 则在长度为n 的线
12、性表中插入一个元素所需移动元素次数的为:,若假定在线性表中任何一个位置上进行插入的概率都是相等的,则移动元素的次数为:,3、删除(算法2.5),2.2 线性表的顺序表示和实现,(a1, , ai-1, ai, ai+1, , an) 改变为(a1, , ai-1, ai+1, , an),ai+1,an, ,表的长度减少,Status ListDelete_sq(Sqlist /end ListDelete_sq,2.2 线性表的顺序表示和实现,算法时间复杂度为:,O( ListLength(L),元素左移,L.length-1,0,87,56,p = ,例如:ListDelete_Sq(L,
13、 5, e),考虑移动元素的平均情况:,假设删除第 i 个元素的概率为 , 则在长度为n 的线性表中删除一个元素所需移动元素次数的为:,若假定在线性表中任何一个位置上进行删除的概率都是相等的,则移动元素的为:,2.2 线性表的顺序表示和实现,4、定位 (算法2.6) Status LocateElem_sq(SqList L,ElemType e) i=1; p=L.elem; while(i=L.length /end LocateElem_sq,O( ListLength(L) ),算法的时间复杂度为:,例如:顺序表(定位),e =,38,i,1,2,3,4,1,8,50,4,0,5、顺序
14、表的合并(算法2.7) void MergeList_Sq(SqlList La,SqlList Lb,SqlList /end MergeList_Sq,算法的时间复杂度为 O(La.length+Lb.length),顺序表的优点: 1)无须为表示数据元素之间的关系而增加额外存储空间。 2)可方便地随机存取表中任一元素。 顺序表的缺点: 插入和删除时需移动大量元素。,2.2 线性表的顺序表示和实现,2.3.1 线性链表 用一组任意的存储单元来依次存放线性表的数据元素,这组存储单元既可以是连续的,也可以是不连续的。 为了能正确表示数据元素间的逻辑关系,在存储每个元素自身信息的同时,还必须存储
15、指示其直接后继的信息(即存储位置),这个信息称为指针(pointer)或链(link)。这两部分组成了链表中的结点结构。 按指针域,线性链表分为单链表、循环链表和双向链表。,2.3 线性表的链式表示和实现,一、单链表 每一个结点只有一个指针域。 整个单链表可有头指针唯一确定。,2.3 线性表的链式表示和实现,例、线性表(bat,cat,eat, fat,hat,jat,lat,mat) 的单链表。,空指针,1、单链表的存储结构定义 typedef struct LNode Elemtype data; struct LNode *next; Lnode, *LinkList;,2.3 线性表的
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 制作 崔广才 wwwcmscusteducnppt 课件
链接地址:https://www.31doc.com/p-2789334.html