数 据 结 构 Ch.2 线性表 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj.

Presentation on theme: "数 据 结 构 Ch.2 线性表 计 算 机 学 院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj."— Presentation transcript:

1 数 据 结 构 Ch.2 线性表 计 算 机 学 院 肖明军

2 §2.1 线性表的逻辑结构 线性表：由n(n≥0)个结点a1, …, an组成的有限序列 记作：L = (a1, a2, …, an),
ai----一般是同一类型

3 §2.1 线性表的逻辑结构 逻辑特征 当L≠Ф时， 有且仅有1个开始结点a1和1个终端结点an，a1仅有一直接后继，an仅有一直接前驱 内部结点ai(2≤i≤n-1)均有一直接前驱ai-1和一直接后继ai+1 结点之间的逻辑关系是由位置次序决定的，ai出在表的第i个位置。该关系是线性的(全序的)，故称L为线性表。

4 §2.1 线性表的逻辑结构 举例： ai----抽象符号。具体应用可能是一个结构类型的对象 基本运算： 英文字母表(A, B, …, Z)
扑克牌点数(2, 3, … , 10, J, Q, K, A) 学生成绩表 等 ai----抽象符号。具体应用可能是一个结构类型的对象 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短 基本运算： InitList(L), ListLength(L), GetNode(L, i) …等 复杂运算可通过基本运算去构造

5 §Ch.2 线性表 线性表的抽象数据类型定义 ADT List{
数据对象：D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系：R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n } 基本操作： InitList( &L ) 操作结果：构造一个空的线性表L； ListLength( L ) 初始条件：线性表L已存在； 操作结果：若L为空表，则返回TRUE，否则返回FALSE；

6 §Ch.2 线性表 … } ADT List …. GetElem( L, i, &e )
初始条件：线性表L已存在，1≦i≦ListLength(L)； 操作结果：用e返回L中第i个数据元素的值； ListInsert ( L, i, &e ) 初始条件：线性表L已存在，1≦i≦ListLength(L) ； 操作结果：在线性表L中的第i个位置插入元素e； … } ADT List

7 §2.2 线性表的顺序存储结构 §2.2.1 顺序表 定义：将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里。由此存储的L称为顺序表。 地址计算： 设结点大小为l个单元，其中第i个单元为该结点地址 Loc(ai) = Loc(a1) + (i-1) * l L的基地址

8 §2.2.1 顺序表 特征： 随机存储 只需存储结点。无需用辅助空间存储逻辑关系。但空闲大小不易确定，易浪费空间
静态分配（当用向量实施时）亦可动态申请空间，但copy成本大（扩充表时）。

9 §2.2.1 顺序表 实现：用向量实现 #define ListSize 100; //假定
typedef int DataType; //依具体使用定 typedef struct { DataType data[ListSize]; //存放结点 int length; //当前表长n }Seglist;

10 §2.2.2 顺序表上实现的基本运算 1.插入 基本思想： 在L的第i个位置上插入一新结点x(1 ≤ i ≤ n+1)。 x
(a1, …, ai-1, ai, ai+1, …, an) → (a1, …, ai-1, x, ai, …, an+1) 为保持结点的物理顺序和逻辑顺序一致，须： 将an, …, ai依次后移1位，空出ith位置 插入x 表长加1

11 §2.2.2 顺序表上实现的基本运算 算法： void InsertList(SegList *L, DataType x, int i){
int j; //注意c数组1st位置的下标为0. ai的位置是data[i-1]. if (i<1 || i>L->length+1) //1≤i≤n+1是合法插入位置 Error(“Position error!”); if (L->length >= ListSize) Error (“Overflow”); //溢出 for (j = L->length-1; j>=i-1; j--) L->data[j+1] = L->data[j]; //结点后移 L->data[i-1] = x; //插入x L->length++; //长度加1 };

12 §2.2.2 顺序表上实现的基本运算 分析： 循环后移，移动节点数为n-i+1，时间与 相关 最好情况：当i=n+1，不移动 O(1)
常数时间解释 O(n0)与n无关 最坏情况：当i=1，全部后移 O(n) 平均性能： 设任何合法位置上插入的概率相等： (位置i插入的概率) 当位置i确定是，后移次数亦确定：n-i+1. 故表中平均移动结点为： 即插入式，平均移动表中一半结点

13 §2.2.2 顺序表上实现的基本运算 2.删除 基本思想： 在L中删除ith结点 (1 ≤ i ≤ n)。 为保持物理与逻辑顺序一致，须：
(a1, …, ai-1, ai, ai+1, …, an) → (a1, …, ai-1, ai+1, …, an-1) 为保持物理与逻辑顺序一致，须： 前移：将ai+1, …, an依次前移1位，填补删除ai留下的空间 表长减1

14 §2.2.2 顺序表上实现的基本运算 算法： void DeleteList(SegList *L, int i){
int j， n=L->length; if (i<1 || i>n) Error(“Position error!”); //非法位置 for (j = i; j<=n-1; j++) L->data[j-1] = L->data[j]; //结点后移 L->length--; //长度减1 };

15 §2.2.2 顺序表上实现的基本运算 分析： 前移次数与n和i相关，移动节点数n-i。 最好情况：当i=n，不移动 O(1)
最坏情况：当i=1，前移n-1次 O(n) 平均性能：

16 §2.3 线性表的链式存储结构 顺序表 §2.3.1 单链表（线性链表） 存储方法： 缺点：移动节点，不利于动态插入和删除
优点：随机存取，得到第i个结点的时间为O(1)与表长和位置无关 §2.3.1 单链表（线性链表） 存储方法： 用一组任意存储单元来存放结点（可连续，亦可不连续）； 为表示逻辑关系，须存储后继或前驱信息

17 §2.3.1 单链表（线性链表） 结点结构 表示 数据域 指针域（链域） next指向该结点的后继（的地址） 开始结点无前驱，用头指针表示
终端结点无后继，next域为空（NULL）

18 §2.3.1 单链表（线性链表） 特征 逻辑状态 头指针唯一确定一个单链表 存储状态 见图2.5 非顺序存取 用指针表示结点间逻辑关系
存储状态 见图2.5 特征 非顺序存取 用指针表示结点间逻辑关系 动态分配

19 §2.3.1 单链表（线性链表） 实现： typedef struct node{ //结点类型定义
DataType data; //数据域 struct node *next; //指针域 }ListNode; typedef ListNode *LinkList; //链表类型定义 ListNode *p; //结点定义 LinkList head; //链表头指针定义

20 §2.3.1 单链表（线性链表） 结点变量和指针变量 指针变量p：值为结点地址 结点变量*p：值为结点内容 动态申请，垃圾收集

21 §2.3.1 单链表（线性链表） 1.建立单链表 （1）头插法： 从空表开始，重复读入数据：申请新结点、插入表头，直至输入结束。
表次序与输入次序相反。 处理自然简单

22 §2.3.1 单链表（线性链表） （2）尾插法： 设为指针r指向当前链尾（初值为NULL） 申请新结点s 将读入数据写入
新结点链到表尾（应注意边界条件） 修改尾指针r

23 §2.3.1 单链表（线性链表） 为简便起见，设结点数据类型DataType为char，输入字符，换行符结束
LinkList CreateList(void){ //ch, head, r为局部量 head = r = NULL; //开始为空表 while ((ch = getchar()) != ‘\n’){ s = (ListNode*)malloc(sizeof(ListNode)); // ① s->data = ch; // ② if (head == NULL) //插入空表 head = s; //新结点插入空表（边界），r为空

24 §2.3.1 单链表（线性链表） 边界条件处理： 空表和非空表处理不一致 简化方法：引入头结点（哨兵），其中data域可做它用（如表长度）
else r->next = s; // ③ r = s; // ④ } if (r != NULL) r->next = NULL; //非空表，终端结点指针为空无后继 return head； 边界条件处理： 空表和非空表处理不一致 简化方法：引入头结点（哨兵），其中data域可做它用（如表长度）

25 §2.3.1 单链表（线性链表） LinkList CreateList(void){ //用尾插法建立带头结点的单链表 char ch；
LinkList head = (Linklist)malloc(sizeof(ListNode)); //生成头结点 ListNode *s, *r; r = head; //为指针初始指向头结点 while () { s = (ListNode*)malloc(sizeof(ListNode)); s->data = ch;

26 §2.3.1 单链表（线性链表） Note：为简化起见，，申请结点时不判是否申请到 时间： O(n) r->next = s;
r = s; } r->next = NULL; //终端结点指针置空，或空表时头结点指针置空 return head; Note：为简化起见，，申请结点时不判是否申请到 时间： O(n)

27 §2.3.1 单链表（线性链表） 2.查找 按值查找 找链表中关键字为k的结点 按序号查找 思想： 算法
合法位置 1≤i≤n. 头结点可看作第0个结点 返回第i个结点的地址，即找到第i-1个结点，返回其next域 思想： 顺链扫描：p----当前扫描到的结点，初始指向头结点 j----计算器。累加扫描到的结点，初始值为0 每次加1，直至 j=i为止，p指向ith结点 算法

28 §2.3.1 单链表（线性链表） 时间分析 循环终止条件是搜索到表尾或j=i。复杂度最多为i，与查找位置相关。 //i=0，找头结点
ListNode *GetNode(LinkList head, int i){ //在链表（有头结点）中查找ith结点 找到(0≤i≤n)则返回该结点的存储 //位置，否则返回NULL int j; ListNode *p; p = head; j = 0; //头结点开始扫描 while (p->next && j<i) {//顺链扫描，至p->next为空或j=i为止 p = p->next; j++; } if (i == j) return p; //找到 else return NULL; //当i<0或i>n时未找到 时间分析 循环终止条件是搜索到表尾或j=i。复杂度最多为i，与查找位置相关。 //i=0，找头结点

29 §2.3.1 单链表（线性链表） 3.插入 问题：将值为x的结点插到表的第i个结点位置上。即在ai-1和ai之间插入。故须找到第ai-1个结点的地址p，然后生成新结点*s，将其链到ai-1之后，ai之前。

30 §2.3.1 单链表（线性链表） 思考：若无头结点，边界如何处理？ 时间：主要是GetNode O(n) 合法位置 1≤i≤n+1
void InsertList (LinkList head, DataType x, int i) { //带头结点 1≤i≤n+1 ListNode *p; p = GetNode(head, i-1); //寻找第i-1个结点① if (p== NULL) // i<1或i>n+1时插入位置i有错 Error("position error"); s = (ListNode *)malloc(sizeof (ListNode)); //② s->data=x; //③ s->next=p->next; //④ p->next=s; //⑤ } 思考：若无头结点，边界如何处理？ 时间：主要是GetNode O(n) 合法位置 1≤i≤n+1 GetNode： 0≤i≤n

31 §2.3.1 单链表（线性链表） 4.删除 删ith结点。首先找ai-1。

32 §2.3.1 单链表（线性链表） void DeleteList (LinkList head, int i){
p = GetNode (head, i-1); //① if (!p || !(p->next)) // i<1或i>n时删除位置有错 Error("position error"); r = p->next; //② 令r指向被删结点ai p->next = r->next; // ③ 将ai从链上摘下 free(r); // ④ 释放ai }

33 §2.3.1 单链表（线性链表） 正确性分析 时间 O(n) 结论：链表上插、删无须移动结点，仅需修改指针
i<1时，GetNode中的参数<0。此时返回p为空 i=n+1时，GetNode中参数=n。返回终端结点，此时p->next为空 i>n+1时，GetNode返回p为空 时间 O(n) 结论：链表上插、删无须移动结点，仅需修改指针

34 §2.3.2 循环链表（单） 首尾相接：不增加存储量，只修改连接方式 优点：从任一结点出发可访问到表中任一其它结点，如找前驱（O(n)）
遍历表的终止方式： p为空或p->next为空 p=head或p->next=head

35 §2.3.2 循环链表（单） 仅设尾指针更方便：访问开始结点和终端结点的时间均为O(1)。
T(m,n)=O(max(m,n))或O(min(m,n))

36 §2.3.3 双链表（循环） 单链表只有后向链，找一结点的后继时间为O(1)，但找前驱费时，若经常涉及找前驱和后继，则可选双链表。

37 §2.3.3 双链表（循环） 结构特征 优点： 对称结构：若p不空，则
p->prior->next = p = p->next->prior 优点： 找一结点前驱和找一结点后继同样方便 删*p本身和删*p的后继同样方便

38 §2.3.3 双链表（循环） 例1：前插 例2：删*p s->data=x; // ②
s->prior=p->prior; // ③ s->next=p; // ④ p->prior->next=s; // ⑤ p->prior=s; // ⑥ p->prior->next=p->next; p->next->prior=p->prior; free(p);

39 §2.3.4 静态链表 上述链表是由指针实现的，其中结点分配和回收是由系统实现的，系统提供了malloc和free动态执行，故称为动态链表。
动态----程序执行时系统动态分配和回收 静态链表---- 先分配大空间作为备用结点空间（即存储池） 用下标（亦称游标cursor）模拟指针，自定义分配和释放结点函数

40 §2.3.4 静态链表 1.定义 #define nil 0 //空指针 #define MaxSize 1000 //可容纳的结点数
typedef struct { DataType data; int next; }node, NodePool[MaxSize]; typedef int StaticList;

41 §2.3.4 静态链表 2.基本操作（模拟动态链表） 初始化 将整个表空间链成一个备用链表，只做一次。
void Initiate(NodePool space) { //备用链表的头结点位置为space[0] for (i=0; i<MaxSize-1; i++) space[i].next = i+1; space[MaxSize-1].next = nil; }

42 §2.3.4 静态链表 分配结点 在备用链表上申请一个结点，返回非空（不等于0）成功，否则失败。
int AllocNode(NodePool space) { i = space[0].next; //取备用链表上开始结点，位置为i，即space的第i个分量 if (i) //开始结点非空 space[0].next = space[i].next; //将开始结点从备用链表上摘下 return i; //为nil时失效 }

43 §2.3.4 静态链表 释放结点 将释放结点收还到备用链表的头上。
void FreeNode(NodePool space, int ptr) { //将ptr所指结点回收到备用链表头结点之后 space[ptr].next = space[0].next; space[0].next = ptr; }

44 §2.3.4 静态链表 3.一般操作 插入 void Insert(NodePool space, StaticList L, DataType x, int i) { // 在带头结点的静态链表L的第i个结点ai之前插入新结点x p = Locate(space, L, i-1); //找L中ai的前驱① if (p == nil) Error(“Position error!”); //位置错 S = AllocNode(space); //申请结点② if (s == nil) Error(“Overflow”); //申请失败，空间不足判定 space[s].data = x; // ③ space[s].next = space[p].next; // ④ space[p].next = s; // ⑤ }

45 §2.3.4 静态链表 注意：链表头指针实际上整数，即space的下标 删除
void Delete(NodePool space, StaticList L, int i) { p = Locate(space, L, i-1); // 找L中ai的前驱 ① if (p == nil || space[p].next == nil) Error(“Position error!”); // 位置错 q = space[p].next; // q指向被删结点ai ② space[p].next = space[q].next; // 将ai摘下 ③ FreeNode(space, q); // ④ } 注意：链表头指针实际上整数，即space的下标

46 §2.3.4 静态链表

47 §2.3.4 静态链表

48 §2.3.4 静态链表 在spce中可能有多个链表，若再建立一个链表head，头结点在哪个位置？

49 §2.3.4 静态链表 静态链表特点： §2.4 顺序表和链表之比较 没有指针类型的语言可以使用。亦可有双链表。循环链表等。 对比：
动态链表 静态链表 指针变量ptr 下标ptr 结点变量*ptr 结点space[ptr] 结点后继位置ptr->next 结点后继位置space[ptr].next §2.4 顺序表和链表之比较

50 作业 为什么在单循环链表中设置尾指针比设置头指针更好？ 写一个算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。