第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例.

Presentation on theme: "第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例."— Presentation transcript:

1 第2章 线性表 线性表抽象数据类型 顺序表 主要知识点 单链表 循环单链表 循环双向链表 静态链表 设计举例

2 2.1 线性表抽象数据类型 1.线性表的定义 线性表是一种可以在任意位置插入和删除数据元素操作、由n(n≥0)个相同类型数据元素a0, a1,…, an-1组成的线性结构。 线性结构:

3 2.线性表抽象数据类型 数据:｛ a0, a1, … , an-1 ｝, ai的数据类型为DataType
(1) ListInitiate(L) 初始化线性表 (2) ListLength(L) 求当前数据元素个数 (3) ListInsert(L,i,x) 插入数据元素 操作: (4) ListDelete(L,i,x) 删除数据元素 (5) ListGet(L,i,x) 取数据元素 ｛ a0, a1, … , an-1 ｝表示数据元素有次序关系,简称序列。

4 2.2 线性表的顺序表示和实现 顺序存储结构的线性表称作顺序表 1.顺序表的存储结构
实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元中，这样线性表中逻辑上相邻的数据元素在物理存储地址上也相邻。数据元素间的逻辑上的前驱、后继逻辑关系就表现在数据元素的存储单元的物理前后位置上。 顺序表的存储结构如图所示

5 list a0 a1 a2 a3 a4 a5 … 1 2 3 4 5 6 size=6 MaxSize-1
1 2 3 4 5 6 size=6 MaxSize-1 其中a0 ,a1, a2等表示顺序表中存储的数据元素，list表示顺序表存储数据元素的数组，MaxSize表示存储顺序表的数组的最大存储单元个数，size表示顺序表当前存储的数据元素个数。 typedef struct { DataType list[MaxSize]; int size; } SeqList;

6 2.顺序表操作的实现 （1）初始化ListInitiate(L) void ListInitiate(SeqList *L)
{ L->size = 0; /*定义初始数据元素个数*/ } （2）求当前数据元素个数ListLength(L) int ListLength(SeqList L) { return L.size; }

7 （3）插入数据元素ListInsert(L, i, x)
int ListInsert(SeqList *L, int i, DataType x) { int j; for(j = L->size; j > i; j--) L->list[j] = L->list[j-1]; /*依次后移*/   L->list[i] = x; /*插入x*/ L->size ++; /*元素个数加1*/ return 1; }

8

9 （4）删除数据元素ListDelete(L, i, x)
int ListDelete(SeqList *L, int i, DataType *x) { int j; *x = L->list[i]; /*保存删除的元素到x中*/   for(j = i +1; j <= L->size-1; j++) L->list[j-1] = L->list[j]; /*依次前移*/ L->size--; /*数据元素个数减1*/ return 1; }

10

11 int ListGet(SeqList L, int i, DataType *x)
（5）取数据元素ListGet(L, i, x) int ListGet(SeqList L, int i, DataType *x) { if(i < 0 || i > L.size-1) { printf("参数i不合法! \n"); return 0; } else { *x = L.list[i]; return 1;

12 3.顺序表操作的效率分析 时间效率分析: 算法时间主要耗费在移动元素的操作上，因此计算时间复杂度的基本操作(最深层语句频度) T(n)= O(移动元素次数) 而移动元素的个数取决于插入或删除元素的位置i. 若i=size，则根本无需移动（特别快）； 若i=0，则表中元素全部要后移（特别慢）； 应当考虑在各种位置插入（共n+1种可能）的平均移动次数才合理。

13 同理可证:顺序表删除一元素的时间效率为:
设Pi是在第i个存储位置插入一个数据元素的概率，顺序表中的数据元素个数为n,当在顺序表的任何位置上插入数据元素的概率相等时，有Pi=1/(n+1),则 插入时的平均移动次数为: n(n+1)/2÷（n+1）＝n/2≈O(n) 同理可证:顺序表删除一元素的时间效率为: T（n)=(n-1)/2 ≈O(n)

14 顺序表中的其余操作都和数据元素个数n无关，因此，在顺序表中插入和删除一个数据元素的时间复杂度为O(n),其余操作的时间复杂度都为O(1)
主要优点是算法简单，空间单元利用率高； 主要优缺点 主要缺点是需要预先确定数据元素的最大个数，插入和删除时需要移动较多的数据元素。

15 4.顺序表应用举例 例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用顺序表实现，假设该顺序表的数据元素个数在最坏情况下不会超过100个。

16 实现方法： 1、采用直接编写一个主函数实现。 2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList
实现方法： 1、采用直接编写一个主函数实现。 2、利用已设计实现的抽象数据类型模块。（存放在头文件名为SeqList.h中，通过 #include “SeqList.h” ） 程序设计如下： #include <stdio.h> #define MaxSize 100 typedef int DataType; #include "SeqList.h"

17 程序运行结果： 1 2 3 4 6 7 8 9 10 void main(void) { SeqList myList;
int i , x; ListInitiate(&myList); for(i = 0; i < 10; i++) ListInsert(&myList, i, i+1); ListDelete(&myList, 4, &x); for(i = 0; i < ListLength(myList); i++) ListGet(myList, i, &x); } 程序运行结果：

18 2.3 线性表的链式表示和实现 1.单链表的结构 (1)单链表中构成链表的结点只有一个指向直接后继结点的指针域。其结构特点：逻辑上相邻的数据元素在物理上不一定相邻。

19 或 数据域：存储元素数值数据 指针域：存储直接后继的存储位置
结点结构如图示： 指针域 数据域 next data 或 数据域：存储元素数值数据 指针域：存储直接后继的存储位置

20 (2)头指针、头结点和首元结点的区别 示意图如下： a0 head a1 … an ^ 头指针 头结点 首元结点

21 头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；
头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。 首元结点是指链表中存储线性表第一个数据元素a０的结点。 (3)带头结点单链表和不带头结点单链表的比较

22 1).在带头结点单链表第一个数据元素前插入结点
p a0 a1 an-1 ∧ … head data next x s (a) 插入前 p a0 a1 an-1 ∧ … head data next x s (b) 插入后

23 2).删除带头结点单链表第一个数据元素结点 p a0 a1 an-1 ∧ … head data next

24 3).在不带头结点单链表第一个数据元素前插入结点
a0 a1 an-1 ∧ … head x s (a) 插入前 a0 a1 an-1 ∧ … head x s (b) 插入后

25 4).在不带头结点单链表其他数据元素前插入结点
p ai-1 a0 ai an-1 ∧ … head data next x s ×

26 5).删除不带头结点单链表第一个数据元素结点
a0 a1 an-1 ∧ … head data next × 6).删除不带头结点单链表其他数据元素结点 p ai-1 a0 ai an-1 ∧ … head data next × ai+1

27 结论： （1）带头结点单链表无论在第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样 （2）删除操作和插入操作类似 （3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数 （4）因此，带头结点单链表的算法设计简单

28 2.单链表的操作实现 结点定义： typedef struct Node
{ DataType data; struct Node *next; } SLNode （1）初始化ListInitiate(head) void ListInitiate(SLNode **head) { *head = (SLNode *)malloc(sizeof(SLNode)); (*head)->next = NULL; }

29 （2）求当前数据元素个数ListLength(head)
int ListLength(SLNode *head) { SLNode *p = head; int size = 0; while(p->next != NULL) { p = p->next; size ++; } return size;

30

31 （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 && j < i - 1) { p = p->next; j++; } if(j != i - 1) { printf(“插入位置参数错！”); return 0; q = (SLNode *)malloc(sizeof(SLNode)); q->data = x; q->next = p->next; p->next = q; return 1;

32

33 说明：①要在带头结点的单链表第i（0 ≤ i ≤ size）个结点前插入一个存放数据元素x的结点，首先要在单链表中寻找到第i-1个结点并由指针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结点。

34 （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 && p->next->next!= NULL && j < i - 1) { p = p->next; j++; } if(j != i - 1) { printf(“插入位置参数错！”); return 0;   s = p->next; *x = s->data; p->next = p->next->next; free(s); return 1; } 

35 说明：要在带头结点的单链表中删除第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所示。图中的①对应算法中的删除语句。

36 （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 && j < i) { p = p->next; j++; }   if(j != i) { printf(“取元素位置参数错！”); return 0;   *x = p->data; return 1;

37 （6）撤消单链表Destroy(head)
void Destroy(SLNode **head) { SLNode *p, *p1;   p = *head; while(p != NULL) { p1 = p; p = p->next; free(p1); } *head = NULL;

38 4.单链表操作的效率分析 单链表的插入和删除操作不需移动数据元素，只需比较数据元素。因此，当在单链表的任何位置上插入数据元素的概率相等时，在单链表中插入一个数据元素时比较数据元素的平均次数为： 删除一个数据元素时比较数据元素的平均次数为： 另外，单链表求数据元素个数操作的时间复杂度为O(n)。

39 和顺序表相比 主要优点是不需要预先确定数据元素的最大 个数，插入和删除操作不需要移动数据元素； 单链表 主要缺点是查找数据元素时需要顺序进行，不能像顺序表那样随机查找任意一个数据元素。另外，每个结点中要有一个指针域，因此空间单元利用率不高。而且单链表操作的算法也较复杂。 和顺序表相比，单链表的优点和缺点正好相反。

40 5.单链表应用举例 例：编程实现如下任务:建立一个线性表，首先依次输入数据元素1，2，3，…，10，然后删除数据元素5，最后依次显示当前线性表中的数据元素。要求采用单链表实现。 #include <stdio.h> #include <stdlib.h> #include <malloc.h> typedef int DataType; #include "LinList.h"

41 程序运行结果： 1 2 3 4 6 7 8 9 10 void main(void) { SLNode *head; int i , x;
ListInitiate(&head);  for(i = 0; i < 10; i++) ListInsert(head, i, i+1) ; ListDelete(head, 4, &x) ; for(i = 0; i < ListLength(head); i++) { ListGet(head, i, &x) == 0) ; printf(“%d ”, x); } Destroy(&head); 程序运行结果：

42 2.4 循环单链表 循环单链表是单链表的另一种形式，其结构特点是链表中最后一个结点的指针域指向整个链表的第一个结点，从而使链表形成一个环。它的优点是从链尾到链头比较方便。循环单链表也有带头结点和不带头结点两种结构。 一个带头结点的循环单链表如下图示：

43 P->next!=NULL 改为 p- >next != head
an-1 … head (a) 空链表 (b) 非空链表 程序设计： p!=NULL 改为 p!=head P->next!=NULL 改为 p- >next != head

44 2.5 双向链表 双向链表是每个结点除后继指针域外还有一个前驱指针域，它有带头结点和不带头结点，循环和非循环结构，双向链表是解决查找前驱结点问题的有效途径。 prior data next 结点结构如图示： 下图是带头结点的循环双向链表的结构，可见，其前驱指针和后继指针各自构成自己的循环单链表。

45 a0 a1 an-1 head (b) 非空链表 … head (a) 空链表 在双向链表中: 设指针p指向第i个数据元素结点，则p->next指向第i+1个数据元素结点，p->next->prior仍指向第i个数据元素结点，即p->next->prior=p;同样p->prior->next=p。

46 a0 ai an-1 head … x s ai-1 × ④ ① ② ③ p 循环双向链表的插入过程如图示：

47 ai+1 ai an-1 head … ai-1 × ① ② p 删除过程如图示：

48 2.6 静态链表 在数组中增加一个(或两个)指针域用来存放下一个(或上一个)数据元素在数组中的下标，从而构成用数组构造的单链表。因为数组内存空间的申请方式是静态的，所以称为静态链表，增加的指针称做仿真指针。结构如下： A B C E ∧ head D (a) 常规链表

49 (b) 静态链表1 (b) 静态链表2 A 1 B 2 C 3 D 4 E -1 ┇ data next maxSize-1 A 2 E
maxSize-1 A 2 E -1 B 4 D 1 C 3 ┇ (b) 静态链表2 data next maxSize-1

50 2.7 设计举例 例2-4 设计一个顺序表的删除函数，把顺序表L中的数据元素x删除。
算法思想：首先，找到要删除元素的位置，然后，从这个位置到最后一个元素，逐个前移，最后，把元素个数减1。

51 int ListDataDelete(SeqList *L, DataType x)
{ int i, j; for(i = 0; i < L->size; i++) if(x == L->list[i]) break;  if(i == L->size) return 0; else { for(j = i; j < L->size; j++) L->list[j] = L->list[j+1]; L->size--; return 1; }

52 例2-5 构造一个顺序表的删除算法，把顺序表L中所有值相同的数据元素x全部删除。

53 int ListMoreDataDelete(SeqList *L, DataType x)
{ int i, j; int tag = 0; for(i = 0; i < L->size; i++) { if(x == L->list[i]) { for(j = i; j < L->size-1; j++) L->list[j] = L->list[j+1]; L->size--; i--; tag = 1; } }  return tag;

54 例2-6 设头指针为head，并设带头结点单链表中的数据元素递增有序，编写算法将数据元素x插入到带头结点单链表的适当位置上，要求插入后保持单链表数据元素的递增有序。
算法思想：从链表的第一个数据元素结点开始，逐个比较每个结点的data域值和x的值，当data小于等于x时，进行下一个结点的比较；否则就找到了插入结点的合适位置，此时申请新结点把x存入，然后把新结点插入；当比较到最后一个结点仍有data小于等于x时，则把新结点插入单链表尾。

55 void LinListInsert(SLNode *head, DataType x)
{ SLNode *curr, *pre, *q; curr = head->next; pre = head; while(curr != NULL && curr->data <= x) { pre = curr; curr = curr->next; } q = (SLNode *)malloc(sizeof(SLNode)); q->data = x; q->next = pre->next; pre->next = q;

56 算法设计说明： （1）在循环定位插入位置时，循环条件必须首先是curr != NULL，然后是curr->data <= x。如果次序颠倒，则当curr为空（即等于链表结束标记NULL）时,将因为curr->data不存在而出错；次序不颠倒时，当curr等于NULL时将退出循环，不会进行后边条件curr->data <= x的比较。 （2）当比较到最后一个结点仍有data小于等于x时，此时有pre指向最后一个结点，curr等于NULL，则上述算法把新结点插入到了单链表尾作为了单链表新的表尾结点。

57 例2-7 设head为单链表的头指针，并设单链表带有头结点，编写算法将单链表中的数据元素按照数据元素的值递增有序的顺序进行就地排序。
算法思想：在例2-6算法的基础上，再增加一重循环即可实现全部数据元素的排序。由于此时的排序过程没有申请新的结点空间，所以这样的排序算法满足就地排序，即不增加新的内存空间的设计要求。

58 具体实现过程是：把头指针head所指单链表置空（即初始时head所指单链表仅包含一个头结点），把去掉头结点的原单链表（设由头指针p指示）中的数据元素逐个重新插入head所指单链表中。每次插入从head所指单链表的第一个数据元素结点开始，逐个比较head所指单链表每个结点的data域值和p所指单链表的当前第一个数据元素结点的data域值，当前者小于或等于后者时，用head所指单链表的下一个结点进行比较；否则就找到了插入结点的合适位置，从p所指单链表中取下当前第一个数据元素结点插入到head所指单链表的合适位置。这样的过程一直进行到p所指单链表为空时结束。

59 void LinListSort(SLNode *head)
{ SLNode *curr, *pre, *p, *q; p = head->next; head->next = NULL; while(p != NULL) { curr = head->next; pre = head; while(curr != NULL && curr->data <= p->data) { pre = curr; curr = curr->next; } q = p; p = p->next; q->next = pre->next; pre->next = q;

60 作业 1) 习题2-1，2-2 ，2-3 习题2-4，2-10，2-14 2) 习题2-16 3) 习题2-5，2-6，2-15 4)习题2-20，2-21 5)习题2-18，2-22