《C语言工程设计3-2_线性表精编版》由会员分享,可在线阅读,更多相关《C语言工程设计3-2_线性表精编版(61页珍藏版)》请在金锄头文库上搜索。
1、线性表,主要知识点,线性表抽象数据类型,顺序表,循环单链表,循环双向链表,静态链表,设计举例,1,2.1 线性表抽象数据类型,1.线性表的定义,线性表是一种可以在任意位置插入和删除数据元素操作、由n(n0)个相同类型数据元素a0, a1, an-1组成的线性结构。 线性结构:,2,2.线性表抽象数据类型,数据: a0, a1, , an-1 , ai的数据类型为DataType,操作:,(1) ListInitiate(L) 初始化线性表,(2) ListLength(L) 求当前数据元素个数,(3) ListInsert(L,i,x) 插入数据元素,(4) ListDelete(L,i,x)
2、 删除数据元素,(5) ListGet(L,i,x) 取数据元素, a0, a1, , an-1 表示数据元素有次序关系,简称序列。,3,2.2 线性表的顺序表示和实现,1.顺序表的存储结构,实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中,这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。,顺序表的存储结构如图所示,顺序存储结构的线性表称作顺序表,4,a0,a1,a2,a3,a4,a5,list,size=6,MaxSize-1,0,1,2,3,4,5,6,其中a
3、0 ,a1, a2等表示顺序表中存储的数据元素,list表示顺序表存储数据元素的数组,MaxSize表示存储顺序表的数组的最大存储单元个数,size表示顺序表当前存储的数据元素个数。 typedef struct DataType listMaxSize; int size; SeqList;,5,2.顺序表操作的实现,(1)初始化ListInitiate(L) void ListInitiate(SeqList *L) L-size = 0;/*定义初始数据元素个数*/ ,(2)求当前数据元素个数ListLength(L) int ListLength(SeqList L) return L
4、.size; ,6,(3)插入数据元素ListInsert(L, i, x) int ListInsert(SeqList *L, int i, DataType x) int j; for(j = L-size; j i; j-) L-listj = L-listj-1; /*依次后移*/ L-listi = x; /*插入x*/ L-size +; /*元素个数加1*/ return 1; ,7,8,(4)删除数据元素ListDelete(L, i, x) int ListDelete(SeqList *L, int i, DataType *x) int j; *x = L-listi;
5、/*保存删除的元素到x中*/ for(j = i +1; j size-1; j+) L-listj-1 = L-listj; /*依次前移*/ L-size-;/*数据元素个数减1*/ return 1; ,9,10,(5)取数据元素ListGet(L, i, x) int ListGet(SeqList L, int i, DataType *x) if(i L.size-1) printf(参数i不合法! n); return 0; else *x = L.listi; return 1; ,11,3.顺序表操作的效率分析,时间效率分析:,算法时间主要耗费在移动元素的操作上,因此计算时间
6、复杂度的基本操作(最深层语句频度) T(n)= O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i.,若i=size,则根本无需移动(特别快); 若i=0,则表中元素全部要后移(特别慢); 应当考虑在各种位置插入(共n+1种可能)的平均移动次数才合理。,12,设Pi是在第i个存储位置插入一个数据元素的概率,顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时,有Pi=1/(n+1),则 插入时的平均移动次数为: n(n+1)/2(n+1)n/2O(n),同理可证:顺序表删除一元素的时间效率为: T(n)=(n-1)/2 O(n),13,顺序表中的其余操作都和
7、数据元素个数n无关,因此,在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1),主要优点是算法简单,空间单元利用率高;,主要缺点是需要预先确定数据元素的最大个数,插入和删除时需要移动较多的数据元素。,主要优缺点,14,4.顺序表应用举例,例:编程实现如下任务:建立一个线性表,首先依次输入数据元素1,2,3,10,然后删除数据元素5,最后依次显示当前线性表中的数据元素。要求采用顺序表实现,假设该顺序表的数据元素个数在最坏情况下不会超过100个。,15,实现方法:1、采用直接编写一个主函数实现。2、利用已设计实现的抽象数据类型模块。(存放在头文件名为SeqLis
8、t.h中,通过 #include “SeqList.h” ) 程序设计如下: #include #define MaxSize 100 typedef int DataType; #include SeqList.h,16,void main(void) SeqList myList; int i , x; ListInitiate( 程序运行结果: 1 2 3 4 6 7 8 9 10,17,2.3 线性表的链式表示和实现,1.单链表的结构,(1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点:逻辑上相邻的数据元素在物理上不一定相邻。,18,结点结构如图示:,数据域:存储
9、元素数值数据,指针域:存储直接后继的存储位置,19,(2)头指针、头结点和首元结点的区别,头指针,头结点,首元结点,示意图如下:,20,头指针是指向链表中第一个结点(或为头结点、或为首元结点)的指针; 头结点是在链表的首元结点之前附设的一个结点;数据域内只放空表标志和表长等信息,它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a的结点。,(3)带头结点单链表和不带头结点单链表的比较,21,1).在带头结点单链表第一个数据元素前插入结点,22,2).删除带头结点单链表第一个数据元素结点,23,3).在不带头结点单链表第一个数据元素前插入结点,24,4).在不带头结点单链表其他数据元素
10、前插入结点,25,5).删除不带头结点单链表第一个数据元素结点,6).删除不带头结点单链表其他数据元素结点,26,结论: (1)带头结点单链表无论在第一个数据元素结点前插入,还是在其他结点前插入,操作方法一样;而不带头结点单链表在第一个数据元素结点前插入,和在其他结点前插入,操作方法不一样 (2)删除操作和插入操作类似 (3)设计带头结点单链表的算法时,头指针参数可设计成输入型参数;设计不带头结点单链表的算法时,头指针参数必须设计成输出型参数 (4)因此,带头结点单链表的算法设计简单,27,结点定义: typedef struct Node DataType data; struct Node
11、 *next; SLNode;,2.单链表的操作实现,(1)初始化ListInitiate(head) void ListInitiate(SLNode *head) *head = (SLNode *)malloc(sizeof(SLNode); (*head)-next = NULL; ,28,(2)求当前数据元素个数ListLength(head) int ListLength(SLNode *head) SLNode *p = head; int size = 0; while(p-next != NULL) p = p-next; size +; return size; ,29,3
12、0,(3)插入ListInsert(head, i, x) int ListInsert(SLNode *head, int i, DataType x) SLNode *p, *q; int j; p = head; j = -1; while(p-next != NULL ,31,32,说明:要在带头结点的单链表第i(0 i size)个结点前插入一个存放数据元素x的结点,首先要在单链表中寻找到第i-1个结点并由指针p指示,然后动态申请一个结点存储空间并由指针q指示,并把数据元素x的值赋予新结点的数据元素域(即q-data = x),最后修改新结点的指针域指向ai结点(即q-next =
13、p-next),并修改ai-1结点的指针域指向新结点q(即p-next = q)。 循环条件由两个子条件逻辑与组成,其中子条件p-next != NULL保证指针所指结点存在,子条件j i - 1保证最终让指针p指向ai-1结点。,33,(4)删除ListDelete(head, i, x) int ListDelete(SLNode *head, int i, DataType *x) SLNode *p, *s; int j; p = head; j = -1; while(p-next != NULL ,34,说明:要在带头结点的单链表中删除第i(0 i size - 1)个结点,首先要
14、在单链表中寻找到第i-1个结点并由指针p指示,然后让指针s指向ai结点(即s = p-next),并把数据元素ai的值赋予x(即*x = s-data),最后把ai结点脱链(即p-next = p-next-next),并动态释放ai结点的存储空间(即free(s))。删除过程如图2-14所示。图中的对应算法中的删除语句。,35,(5)取数据元素ListGet(head, i, x) int ListGet(SLNode *head, int i, DataType *x) SLNode *p; int j; p = head; j = -1; while(p-next != NULL ,36
15、,(6)撤消单链表Destroy(head) void Destroy(SLNode *head) SLNode *p, *p1; p = *head; while(p != NULL)/free(null) 不可以 p1 = p; p = p-next; free(p1); *head = NULL; ,37,4.单链表操作的效率分析 单链表的插入和删除操作不需移动数据元素,只需比较数据元素。因此,当在单链表的任何位置上插入数据元素的概率相等时,在单链表中插入一个数据元素时比较数据元素的平均次数为:,删除一个数据元素时比较数据元素的平均次数为:,另外,单链表求数据元素个数操作的时间复杂度为O(n)。,38,和顺序表相比,主要优点是不需要预先确定数据元素的最大 个数,插入和删除操作不需要移动数据元素;,主要缺点是查找数据元素时需要顺序进行,不能像顺序表那样随机查找任意一个数据元素。另外,每个结点中要有一个指针域,因此空间单元利用率不高。而且单链表操作的算法也较复杂。,单链表,和顺序表相比,单链表的优点和缺点正好相反。,39,5.单链表应用举例,例:编程实现如下任务:建立一个线性表,首先依次输入数据元素1,2,3,10,然后删除数据元素5,最后依次显示当前线性表中的数据元素。要求采用单