《数据结构与算法》PPT课堂课件-第2章-表.ppt

《《数据结构与算法》PPT课堂课件-第2章-表.ppt》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第2章-表.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、12023/3/23第二章第二章 表表 理解表是由同一类型的元素组成的有限序列的概念。熟悉定义在抽象数据类型表上的基本运算。掌握实现抽象数据类型的一般步骤。掌握用数组实现表的步骤和方法。掌握用指针实现表的步骤和方法。掌握用间接寻址技术实现表的步骤和方法。掌握用游标实现表的步骤和方法。掌握单循环链表的实现方法和步骤。掌握双链表的实现方法和步骤。22023/3/23第二章第二章 表表2.1 ADT表 线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合中的每个数据元素

2、均只有一个后继32023/3/23定义：一个线性表是n个数据元素的有限序列例 英文字母表（A,B,C,.Z)是一个线性表特征：n元素个数n表长度，n=0空表n1itable=（ListItem）malloc(size*sizeof(ListItem);/*分配空间*/L-maxsize=size;L-n=0;/*将当前线性表长度置0*/return L;/*成功，返回L*/82023/3/232、判断表是否为空及求表长函数（1）判断线性表L是否为空 int ListEmpty(List L)if(L-n=0)return TRUE;else return FALSE;（2）求表长int Get

3、Length(List L)return L-n;return L-n=0;以上两个程序的时间复杂性均为：O(1)92023/3/233、元素x定位函数 返回元素x在表中的位置位置，当元素x不在表中时返回0。int ListLocate(LISTItem x,List L)int i;for(i=0;in;i+)if(L-tablei=x)return +i;？return 0;此算法所用时间与元素x所在位置有关。假设x存在于第i个位置，则找到x需要比较i次。故在最坏情况下，时间性能为O(n)。102023/3/234、获取线性表L中的某个数据元素内容的函数ListItem ListRetri

4、eve(int k,List L)if(kL-n)return ERROR;/*判断k值是否合理，若不合理，返回ERROR*/return L-tablek-1;时间复杂性O(1)112023/3/235、表元素插入运算void ListInsert(k,x,L)n定义：线性表的插入是指在第k（0k n）个元素之之后后插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1n+1的线性表 需将第i+1至第n共（n-k)n-k)个元素后移122023/3/23内存a1a2ak+1ak+2an01kV数组下标n-1k+1n12k+1元素序号k+2nn+1内存a1a2ak+1ak+2an01k-

5、1V数组下标n-1kn12k元素序号k+1nn+1an-1x132023/3/23int ListInsert(int k,ListItem x,List L)int i;if(L-n=L-maxsize)return ERROR;/*检查是否有剩余空间*/if(kL-n)return ERROR;/*检查k值是否合理*/for(i=L-n-1;i=k;i-)L-tablei+1=L-tablei;/*将线性表第k个元素之后的所有元素向后移动 L-tablek=x;/*将新元素的内容放入线性表的第k+1个位置*/L-n+;142023/3/23n算法时间复杂度T(n)设Pk是在第k个元素之后插

6、入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：若假设在表中任何合法位置插入元素的机会是均等的，则：152023/3/236、表元素删除运算n定义：线性表的删除是指将第k（1i n）个元素删除，使长度为n的线性表 变成长度为n-1n-1的线性表 需将第k+1至第n共（n-k)n-k)个元素前移162023/3/23内存a1a2akak+1an01k-1V数组下标n-1kn12k元素序号k+1nn+1内存a1a2ak+1V数组下标01k-1n-2kn-112k元素序号k+1n-1nanak+2172023/3/23n算法评价设Qi是删除第i个元素的概率，则

7、在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。182023/3/237、输出顺序表中所有元素的运算void PrintList(List L)int i;for(i=0;in;i+)ItemShow(L-tablei);/*此函数用以输出元素*/时间复杂性：O(n)192023/3/232.2.4顺序存储结构的优缺点n优点逻辑相邻，物理相邻无须为表示表中元素之间的顺序关系增加额外的存储空间可随机存取任一元素存储空间使用紧凑n缺点插入、删除操作需要移动大量的元素（除操作在表尾的位置进行外）预先分配空间

8、需按最大空间分配，利用不充分表容量难以扩充202023/3/23n2.3 用指针实现表2.3.1 用指针实现表的特点：n用一组任意的存储单元存储线性表的数据元素n利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素n每个数据元素ak，除存储本身信息外，还需存储其直接后继的信息n结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点212023/3/23例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)4313103771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331firs

9、t第一个元素指针ZHAOQIANSUNLIZHOUWUZHENGWANG0first222023/3/23n实现typedef struct node*link;typedef struct node ListItem element;link next;Node;datalinkp结点（*p）(*p)表示p所指向的结点(*p).datap-data表示p指向结点的数据域(*p).linkp-link表示p指向结点的指针域2.3.2 单链表的数据类型n定义：结点中只含一个指针域的链表，也叫线性链表232023/3/23h空表ha1a2an 头结点头结点：在单链表第一个结点前附设一个结点叫头结点

10、头结点指针域为空表示线性表为空据此可定义用指针实现表的结构List如下：typedef struct llist *List;typedef struct llist link first;Llist;242023/3/232.3.3 单链表的基本运算1、创建一个空表List ListInit()List L=malloc(sizeof*L);L-first=NULL;return L;2、判断当前表L是否为空表Int ListEmpty(List L)return L-first=NULL;252023/3/233、求表长函数Int ListLength(List L)int len=0;l

11、ink p;p=L-first;while(p)/*通过对表L进行线性扫描计算*/len+;p=p-next;return len;时间复杂性为：O(n)思考？：如何改进使得时间复杂性降为O(1)262023/3/234、从表首开始逐个元素向后进行线性扫描直至找到L中第k个元素ListItem ListRetrieve(int k,List L)int i;link p;if(kfirst;i=1;while(inext;i+;return p-element;时间复杂性为：O(k)272023/3/235、定位元素x(查找运算)查找单链表中是否存在结点X，若有则返回X结点的位置；否则返回0；

12、int ListLocate(ListItem x,List L)int i=1;link p;p=L-first;while(p&p-element!=x)p=p-next;i+;return p?i:0;/如果p为空，说明x不存在返回0；否则返回其位置i282023/3/23While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n算法评价292023/3/236 6、在位置在位置k后后插入元素插入元素x 函数的运算步骤是：函数的运算步骤是：先扫描链表找到插入位置先扫描链表找到插入位置p，然后建立一然后建立一个存储待插入元素个存储待插入元素x x的新结点的新结点y，再将结点再将

13、结点y插入到结点插入到结点p之后。之后。插入的插入的示意图如下：示意图如下：yyy-next=first;y-next=first;firstfirst=y;first=y;py-next=p-next;y-next=p-next;p-next p-next=y=y;302023/3/23Void LsitInsert(int k,ListItem x,List L)link p,y;int i；if(k first;/找插入位置 for (i=1;i next;y=NewNode();y-element=x;if(k)y-next=p-next;/在位置p处插入 p-next=y;else

14、y-next=first;first=y;/在表首插入需要特殊处理（若引入表头结点则可纳入 一般情况）其时间复杂性为O(k)算法的主要计算时间用于寻找正确的插入位置，故312023/3/237 7、删除、删除位置位置k k处的元素处的元素给给x x 函数的运算步骤是：依次处理以下函数的运算步骤是：依次处理以下3 3种情况。种情况。（）k1k1k1。其删除的示意图如下其删除的示意图如下p=q-next;q-next=p-next;q-next=p-next;Free p;Free p;给出越界信息；给出越界信息；直接修改表首指针直接修改表首指针first，删除表首元素删除表首元素322023/3

15、/23ListItme ListDelete(int k,List L)link p,q;ListItem x;int i;if(k first)Error(OutOfBounds);p=L-first;if(k=1)/删除表首元素需要特殊处理 L-first=pnext;else/找表中第k-1个元素所在结点q q=L-first;for(i=1;i next;p=q-next;/让p指向 第k个元素所在结点 q-next=p-next;/删除结点p x=p-element;/第k个元素存入x并释放结点p free(p);return x;算法主要时间用于寻找待删除元素所在结点，故其所需时间

16、为O(k)332023/3/237、输出链表中所有元素、输出链表中所有元素:void PrintList(List L)link p;for(p=L-first;p;p=p-next)ItemShow(p-element);时间复杂性时间复杂性 O（n）342023/3/23动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法评价h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0352023/3/232.3.4单链表特点优点优点它是一种动态结构动态结构，整个存储空间为多个链表共用不需预先分配不需预先分配空间

17、（动态生成链表）避免了数组要求连续的存储单元的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。(当元素的粒度很大时，移动元素是很费时的。)缺点缺点指针占用额外额外存储空间不能随机存取不能随机存取，查找速度慢362023/3/232.4 用间接寻址方法实现表2.4.1 用间接寻址方法实现表的原因及实现用间接寻址方法实现表的原因及实现原因：综合数组和指针实现两者的优点。原因：综合数组和指针实现两者的优点。实实现现：将将数数组组和和指指针针两两种种实实现现方方式式结结合合起起来来，让让数数组组中中原原来来存储元素的地方改为存储指向元素的指针。存储元素的地方改为存储指向元素的指

18、针。其结构图如下：其结构图如下：372023/3/23List ListInit(int size)List L=(List)malloc(sizeof*L);L-n=0;L-maxsize=size;L-table=(addr*)malloc(size*sizeof(addr);return L;382023/3/23int ListEmpty(List L)return L-n=0;int ListLength(List L)return L-n;392023/3/23ListItem ListRetrieve(int k,List L)if(kL-n)Error(out of bound

19、s);return*L-tablek-1;int ListLocate(Listitem x,List L)int i;for (i=0;in;i+)if(*L-tablei=x)return+i;return 0;402023/3/23void ListInsert(int k,ListItem x,List L)int i;if(kL-n)Error(“out of bounds”);if(L-n=L-maxsize)Error(“out of memory”);for(i=L-n-1;i=k;i-)L-tablei+1=L-tablei;L-tablek=NewNode();*L-tab

20、lek=x;L-n+;412023/3/23ListItem ListDelete(int k,List L)int i;ListItem x;addr p;if(kL-n)Error(“out of bounds”);p=L-tablek-1;x=*p for(i=k;in;i+)L-tablei-1=L-tablei;L-n-;free(p);return x;422023/3/23void PrintList(List L)int i;for(i=0;in;i+)ItemShow(*L-tablei);432023/3/232.4.2 用间接寻址实现表的优缺点用间接寻址实现表的优缺点优点

21、：(1)与用数组实现一样，可以方便地随机存取表中任一位置的元素。(2)与用指针实现一样，在执行插入或删除运算时，不需要移动元素来腾出空间或填补空缺。缺点：(1)与用数组实现一样，需要预先确定table的大小。当表 长变化很大时，这比较难。(2)与用指针实现一样，需要额外的存储空间，即额外的 指针数组table。442023/3/232.5 用游标实现表用游标实现表2.5.1 2.5.1 用游标实现表原因及实现用游标实现表原因及实现原因：对于有多个同类表的应用，希望通原因：对于有多个同类表的应用，希望通 过自主调济内存资源，达到资源的更过自主调济内存资源，达到资源的更 有效合理的利用。有效合理的

22、利用。实现：从操作系统申请一个较大的实现：从操作系统申请一个较大的数组数组S S，然然后自主地支配后自主地支配S S中的单元，在中的单元，在S S中用游标模拟中用游标模拟指针实现表，并让指针实现表，并让多个同类的表共享这个数多个同类的表共享这个数组，组，如右图。数组如右图。数组S12S12存放着相同类型的存放着相同类型的两个表两个表A A和和B,B,其中表其中表A A含有含有3 3个元素；表个元素；表B B含有含有2 2个元素。个元素。如图：如图：first1first1指示指示S S中尚未被使用的子段的起中尚未被使用的子段的起始单元；始单元；first2first2指示指示S S中被使用过、

23、但目前处于闲置中被使用过、但目前处于闲置的单元组成的一条可管理的链。让其中的单的单元组成的一条可管理的链。让其中的单元优先于元优先于first1first1指示的子段中的单元满足应指示的子段中的单元满足应用的需要。用的需要。452023/3/232.5.2 用游标实现表的优缺点用游标实现表的优缺点优点优点:可实现多个同类的表共享同一片连续存储可实现多个同类的表共享同一片连续存储 空间，给用户予资源调济的自主权。空间，给用户予资源调济的自主权。缺点缺点:应该向操作系统申请多大的连续存储空间应该向操作系统申请多大的连续存储空间 依赖于具体的应用，不容易把握。依赖于具体的应用，不容易把握。46202

24、3/3/232.6 循环链表2.6.1 单循环链表 循环链表是表中最后一个结点的指针指向表首结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p-next=first(a)非空表非空表 (b)空表空表因此，找最后元素只需O(1),找首元素仍只需O(1)。前提？472023/3/232 2.7.7 用用双链双链实现表实现表2.7.1 2.7.1 双向链表双向链表原因：无论用指针实现表还是用单循环链表实现表时，对于表中任一元素x,都不可能在O(1)时间里找到它的前驱。为了能在O(1)时间里既能

25、找到前驱又能找到后继，提出了双链表。在用指针实现表的每一个结点中增加一个指向前驱的指针。结构如下图。pp-left-right=p=p-right-left;482023/3/232.7.2 双向循环链表L空双向循环链表：非空双向循环链表：LABpp-left-right=p=p-right-left;492023/3/23p-left-right=p-right;p-right-left=p-left;free(p);n删除算法描述算法评价：T(n)=O(1)p-left-right=p-right;p-right-left=p-left;bcap502023/3/23 s-left=p-l

26、eft;p-left-right=s;s-right=p;p-left=s;算法描述算法评价：T(n)=O(1)xSbaPn插入512023/3/23n2.8 线性表的应用举例 一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表522023/3/23单链表的结点定义coefexpnext-1A7 0 3 1 9 8 5 17 -1B8 1 22 7 -9 8 -1C7 0 11 1 22 7 5 17 一元多项式相加typedef struct node int coef,

27、exp;struct node *next;JD;532023/3/23设p,q分别指向A,B中某一结点，p,q初值是第一结点0：从A表中删去p,p,q后移p-exp exp:p结点是和多项式中的一项 p后移,q不动0：修改p系数域,p,q后移比较p-exp与q-expp-exp q-exp:q结点是和多项式中的一项 将q插在p之前,q后移,p不动p-exp=q-exp:系数相加直到p或q为NULL 若q=NULL，结束 若p=NULL，将B中剩余部分连到A上即可运算规则542023/3/23q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7

28、0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre q-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq=NULL-1pa7 0 11 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppre-1pa7 0 11 1 22 7 5 17 算法描述552023/3/23作业上机作业1、P50 2.3 2、设计一个程序，能删除数列中重复的数。例对(1,2,1,3,5,6,5)操作结束后得到数列 (1，2，3，5,6)3、实现例题