《《数据结构与算法》PPT课堂课件-第2章-表》由会员分享，可在线阅读，更多相关《《数据结构与算法》PPT课堂课件-第2章-表（55页珍藏版）》请在金锄头文库上搜索。
1、12021/6/13第第二二章章 表表 理解表是由同一类型的元素组成的有限序列的概念。 熟悉定义在抽象数据类型表上的基本运算。 掌握实现抽象数据类型的一般步骤。 掌握用数组实现表的步骤和方法。 掌握用指针实现表的步骤和方法。 掌握用间接寻址技术实现表的步骤和方法。 掌握用游标实现表的步骤和方法。 掌握单循环链表的实现方法和步骤。 掌握双链表的实现方法和步骤。22021/6/13第第二二章章 表表2.1 ADT表 线性结构特点：在数据元素的非空有限集中存在唯一的一个被称作“第一个”的数据元素存在唯一的一个被称作“最后一个”的数据元素除第一个外，集合中的每个数据元素均只有一个前驱除最后一个外，集合
2、中的每个数据元素均只有一个后继32021/6/13定义：一个线性表是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*/ 82021/6/132、判断表是否为空及求表长函数（1）判断线性表L是否为空 int ListEmpty(List L) if (L-n=0) return TRUE; else return
3、 FALSE; （2）求表长int GetLength(List L) return L-n; return L-n=0;以上两个程序的时间复杂性均为：O(1)92021/6/133、元素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)。102021/6/134、获取
4、线性表L中的某个数据元素内容的函数ListItem ListRetrieve(int k, List L) if (kL-n) return ERROR; /*判断k值是否合理，若不合理，返回ERROR*/ return L-tablek-1; 时间复杂性O(1)112021/6/135、表元素插入运算void ListInsert (k, x, L)n定义：线性表的插入是指在第k（0k n）个元素之之后后插入一个新的数据元素x，使长度为n的线性表 变成长度为n+1n+1的线性表 需将第i+1至第n共（n-k)n-k)个元素后移122021/6/13内存a1a2ak+1ak+2an01kV数组
5、下标n-1k+1n12k+1元素序号k+2nn+1内存a1a2ak+1ak+2an01k-1V数组下标n-1kn12k元素序号k+1nn+1an-1x132021/6/13int 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; /*将
6、新元素的内容放入线性表的第k+1个位置*/ L-n+; 142021/6/13n算法时间复杂度T(n)设Pk是在第k个元素之后插入一个元素的概率，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：若假设在表中任何合法位置插入元素的机会是均等的，则：152021/6/136、表元素删除运算n定义：线性表的删除是指将第k（1i n）个元素删除，使长度为n的线性表 变成长度为n-1n-1的线性表 需将第k+1至第n共（n-k)n-k)个元素前移162021/6/13内存a1a2akak+1an01k-1V数组下标n-1kn12k元素序号k+1nn+1内存a1a2ak+1V数组下标
7、01k-1n-2kn-112k元素序号k+1n-1nanak+2172021/6/13n算法评价设Qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素所需移动的元素次数的平均次数为：故在顺序表中插入或删除一个元素时，平均移动表的一半元素，当n很大时，效率很低。182021/6/137、输出顺序表中所有元素的运算void PrintList(List L) int i; for(i=0;in;i+) ItemShow(L-tablei); /*此函数用以输出元素*/ 时间复杂性：O(n)192021/6/132.2.4顺序存储结构的优缺点n优点逻辑相邻，物理相邻无须为表示表中元素之间的
8、顺序关系增加额外的存储空间可随机存取任一元素存储空间使用紧凑n缺点插入、删除操作需要移动大量的元素（除操作在表尾的位置进行外）预先分配空间需按最大空间分配，利用不充分表容量难以扩充202021/6/13n2.3 用指针实现表2.3.1 用指针实现表的特点：n用一组任意的存储单元存储线性表的数据元素n利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素n每个数据元素ak，除存储本身信息外，还需存储其直接后继的信息n结点数据域：元素本身信息指针域：指示直接后继的存储位置数据域 指针域结点212021/6/13例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)43
9、13103771925数据域指针域LIQIANSUNWANGWUZHAOZHENGZHOU存储地址1713192531374331first第一个元素指针ZHAOQIANSUNLIZHOUWUZHENGWANG0first222021/6/13n实现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
10、定义：结点中只含一个指针域的链表，也叫线性链表232021/6/13h空表ha1a2an 头结点头结点：在单链表第一个结点前附设一个结点叫头结点头结点指针域为空表示线性表为空据此可定义用指针实现表的结构List如下：typedef struct llist *List;typedef struct llist link first;Llist;242021/6/132.3.3 单链表的基本运算1、创建一个空表List ListInit() List L=malloc(sizeof*L); L-first=NULL; return L;2、判断当前表L是否为空表Int ListEmpty(Lis
11、t L) return L-first=NULL; 252021/6/133、求表长函数Int ListLength(List L) int len=0; link p; p=L-first; while(p) /*通过对表L进行线性扫描计算*/ len+; p=p-next; return len; 时间复杂性为：O(n)思考？： 如何改进使得时间复杂性降为O(1)262021/6/134、从表首开始逐个元素向后进行线性扫描直至找到L中第k个元素ListItem ListRetrieve(int k,List L) int i; link p; if(kfirst; i=1; while(i
12、next; i+; return p-element; 时间复杂性为：O(k) 272021/6/135、定位元素x (查找运算) 查找单链表中是否存在结点X，若有则返回X结点的位置；否则返回0；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；否则返回其位置i282021/6/13While循环中语句频度为若找到结点X，为结点X在表中的序号否则，为n算法评价292021/6/136
13、6、在在位位置置k后后插插入入元元素素x 函函数数的的运运算算步步骤骤是是：先先扫扫描描链链表表找找到到插插入入位位置置p，然然后后建建立立一一个个存存储储待待插插入入元元素素x x的的新新结结点点y，再再将将结结点点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; ;302021/6/13Void LsitInsert(int k, ListItem
14、 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 y-next = first; first = y; /在表首插入需要特殊处理（若引入表头结点则可纳入 一般情况） 其时间复杂性为O(k)算法的主要计算时间用于寻找正确的插入位置，故312021/6/137 7、删删除除位位置置k k处处的的元元素素给给x x 函函数数的的运运算算步步骤骤是是：
15、依依次次处处理理以以下下3 3种种情情况况。（）k1k1k1。其其删删除除的的示示意意图图如如下下p=q-next;q-next = p-next;q-next = p-next;Free p;Free p;给给出出越越界界信信息息；直直接接修修改改表表首首指指针针first，删删除除表表首首元元素素322021/6/13ListItme ListDelete(int k, List L) link p, q; ListItem x; int i; if (k first) Error(OutOfBounds ); p = L-first; if (k = 1) / 删除表首元素需要特殊处理
16、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; 算法主要时间用于寻找待删除元素所在结点，故其所需时间为O(k)332021/6/137、输输出出链链表表中中所所有有元元素素:void PrintList (List L) link p; for (p = L-first; p; p =
17、p-next) ItemShow(p-element); 时时间间复复杂杂性性 O（n）342021/6/13动态建立单链表算法：设线性表n个元素已存放在数组a中，建立一个单链表，h为头指针算法评价h头结点an 0h头结点an-10an a2.h头结点an-10an ha1a2头结点an .0h头结点0352021/6/132.3.4单链表特点优优点点它是一种动动态态结结构构，整个存储空间为多个链表共用不不需需预预先先分分配配空间（动态生成链表）避免了数组要求连续的存储单元的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。 (当元素的粒度很大时，移动元素是很费时的。)缺
18、缺点点指针占用额额外外存储空间不不能能随随机机存存取取，查找速度慢362021/6/132.4 用间接寻址方法实现表2.4.1 用用间间接接寻寻址址方方法法实实现现表表的的原原因因及及实实现现原原因因：综综合合数数组组和和指指针针实实现现两两者者的的优优点点。实实现现：将将数数组组和和指指针针两两种种实实现现方方式式结结合合起起来来，让让数数组组中中原原来来存存储储元元素素的的地地方方改改为为存存储储指指向向元元素素的的指指针针。 其其结结构构图图如如下下：372021/6/13List ListInit(int size) List L= (List)malloc(sizeof *L); L
19、-n=0; L-maxsize=size; L-table = (addr *)malloc(size*sizeof(addr); return L;382021/6/13int ListEmpty(List L) return L-n=0;int ListLength(List L) return L-n;392021/6/13ListItem ListRetrieve(int k,List L) if (kL-n) Error(out of bounds); return *L-tablek-1;int ListLocate(Listitem x,List L) int i; for (i
20、=0;in;i+) if (*L-tablei = x) return +i; return 0;402021/6/13void 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-tablek=x; L-n+;412021/6/13ListItem ListDelet
21、e(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;422021/6/13void PrintList(List L) int i; for (i=0;in;i+) ItemShow(*L-tablei);432021/6/132.4.2 用用间间接接寻寻址址实实现现表表的的优优缺缺点点优点： (1)与用数组实现一样，可以方便地随机存
22、取表中任一位置的元素。 (2)与用指针实现一样，在执行插入或删除运算时，不需要移动元素来腾出空间或填补空缺。 缺点： (1)与用数组实现一样，需要预先确定table的大小。当表 长变化很大时，这比较难。 (2)与用指针实现一样，需要额外的存储空间，即额外的 指针数组table 。442021/6/132.5 用用游游标标实实现现表表2.5.1 2.5.1 用用游游标标实实现现表表原原因因及及实实现现原原因因：对对于于有有多多个个同同类类表表的的应应用用，希希望望通通 过过自自主主调调济济内内存存资资源源，达达到到资资源源的的更更 有有效效合合理理的的利利用用。实实现现：从从操操作作系系统统申申
23、请请一一个个较较大大的的数数组组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中中被被使使用用过过、但但目目前前处处于于闲闲置置的的单单元元组组成
24、成的的一一条条可可管管理理的的链链。让让其其中中的的单单元元优优先先于于first1first1指指示示的的子子段段中中的的单单元元满满足足应应用用的的需需要要。 452021/6/132.5.2 用用游游标标实实现现表表的的优优缺缺点点优优点点: :可可实实现现多多个个同同类类的的表表共共享享同同一一片片连连续续存存储储 空空间间，给给用用户户予予资资源源调调济济的的自自主主权权。缺缺点点: :应应该该向向操操作作系系统统申申请请多多大大的的连连续续存存储储空空间间 依依赖赖于于具具体体的的应应用用，不不容容易易把把握握。462021/6/132.6 循环链表2.6.1 单循环链表 循环链表
25、是表中最后一个结点的指针指向表首结点，使链表构成环状n特点：从表中任一结点出发均可找到表中其他结点，提高查找效率n操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p-next=first(a)非非空空表表 (b)空空表表因此，找最后元素只需O(1),找首元素仍只需O(1)。前提？472021/6/132 2.7 .7 用用双双链链实实现现表表2.7.1 2.7.1 双双向向链链表表原因： 无论用指针实现表还是用单循环链表实现表时，对于表中任一元素x,都不可能在O(1)时间里找到它的前驱。为了能在O(1)时间里既能找到前驱又能找到后继，提出了双链表。 在用指针实现表的每
26、一个结点中增加一个指向前驱的指针。结构如下图。pp-left-right = p = p-right-left;482021/6/132.7.2 双向循环链表L空双向循环链表：非空双向循环链表： LABpp-left-right = p = p-right-left;492021/6/13p-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;bcap502021/6/13 s-left=p-left; p-left-right=
27、s; s-right=p; p-left=s;算法描述算法评价：T(n)=O(1)xSbaPn插入512021/6/13n2.8 线性表的应用举例 一元多项式的表示及相加一元多项式的表示：可用线性表P表示但对S(x)这样的多项式浪费空间一般其中用数据域含两个数据项的线性表表示其存储结构可以用顺序存储结构，也可以用单链表522021/6/13单链表的结点定义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,exp; struct nod
28、e *next;JD;532021/6/13设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上即可运算规则542021/6/13q-1pa7 0 3 1 9 8 5 17 -1pb8 1 22 7 -9 8 ppreq-1pa7 0 3 1 9 8
29、 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 算法描述552021/6/13作业上机作业1、P50 2.3 2、设计一个程序，能删除数列中重复的数。 例对 (1,2,1,3,5,6,5 ) 操作结束后得到数列 ( 1，2，3，5 ,6 )3、实现例题
