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