数据结构 Ch.2 线性表 计算机学院 肖明军 Email: xiaomj@ustc.edu.cn http://staff.ustc.edu.cn/~xiaomj 2.1 线性表的逻辑结构 线性表 : 由 n(n 0) 个结点 a 1,, a n 组成的有限序列 记作 :L = (a 1, a 2,, a n ), 属性 : 长度 ---- 结点数目 n,n=0 时为空表 a i ---- 一般是同一类型 2 2.1 线性表的逻辑结构 逻辑特征当 L Ф 时, 1 有且仅有 1 个开始结点 a 1 和 1 个终端结点 a n, a 1 仅有一直接后继,a n 仅有一直接前驱 2 内部结点 a i (2 i n-1) 均有一直接前驱 a i-1 和一直接后继 a i+1 结点之间的逻辑关系是由位置次序决定的,a i 出在表的第 i 个位置 该关系是线性的 ( 全序的 ), 故称 L 为线性表 3 2.1 线性表的逻辑结构 举例 : 英文字母表 (A, B,, Z) 扑克牌点数 (2, 3,, 10, J, Q, K, A) 学生成绩表等 a i ---- 抽象符号 具体应用可能是一个结构类型的对象 线性表是一种相当灵活的数据结构, 其长度可根据需要增长或缩短 基本运算 : InitList(L), ListLength(L), GetNode(L, i) 等复杂运算可通过基本运算去构造 4 Ch.2 线性表 线性表的抽象数据类型定义 ADT List{ 数据对象 :D = { ai ai ElemSet, i=1,2,,n, n 0 数据关系 :R={<ai-1 = {<ai-1, ai> ai-1, ai D, i=2,3,,n 基本操作 : InitList( &L ) 操作结果 : 构造一个空的线性表 L; ListLength( L ) 初始条件 : 线性表 L 已存在 ; 操作结果 : 若 L 为空表, 则返回 TRUE, 否则返回 FALSE; Ch.2 线性表. 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 1
2.2 线性表的顺序存储结构 2.2.1 顺序表 定义 : 将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里 由此存储的 L 称为顺序表 地址计算 : 设结点大小为 l 个单元, 其中第 i 个单元为该结点地址 Loc(a i ) = Loc(a 1 ) + (i-1) * l L 的基地址 7 2.2.1 顺序表 特征 : 1 随机存储 2 只需存储结点 无需用辅助空间存储逻辑关系 但空闲大小不易确定, 易浪费空间 3 静态分配 ( 当用向量实施时 ) 亦可动态申请空间, 但 copy 成本大 ( 扩充表时 ) 8 2.2.1 顺序表 实现 : 用向量实现 #define ListSize 100; // 假定 typedef int DataType; // 依具体使用定 typedef struct { DataType data[listsize]; // 存放结点 int length; // 当前表长 n Seglist; 9 1. 插入 基本思想 : 在 L 的第 i 个位置上插入一新结点 x(1 i n+1) x (a 1,, a i-1, a i, a i+1,, a n ) (a 1,, a i-1, x, a i,, a n+1 ) 为保持结点的物理顺序和逻辑顺序一致, 须 : 1 将 a n,, a i 依次后移 1 位, 空出 ith 位置 2 插入 x 3 表长加 1 10 算法 : 分析 : 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]; // 结点后移 循环后移, 移动节点数为 n-i+1, 时间与 1 最好情况 : 当 i=n+1, 不移动 O(1) 常数时间解释 O(n 0 ) 与 n 无关 2 最坏情况 : 当 i=1, 全部后移 O(n) 相关 3 平均性能 : 设任何合法位置上插入的概率相等 : ( 位置 i 插入的概率 ) 当位置 i 确定是, 后移次数亦确定 :n-i+1. 故表中平均移动结点为 : L->data[i-1] = x; // 插入 x L->length++; // 长度加 1 ; 11 即插入式, 平均移动表中一半结点 12 2
2. 删除 基本思想 : 在 L 中删除 ith 结点 (1 i n) (a 1,, a i-1, a i, a i+1,, a n ) (a 1,, a i-1, a i+1,, a n-1 ) 为保持物理与逻辑顺序一致, 须 : 1 前移 : 将 a i+1,, a n 依次前移 1 位, 填补删除 a i 留下的空间 2 表长减 1 13 算法 : 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 ; 14 分析 : 前移次数与 n 和 i 相关, 移动节点数 n-i 1 最好情况 : 当 i=n, 不移动 O(1) 2 最坏情况 : 当 i=1, 前移 n-1 次 O(n) 3 平均性能 : 2.3 线性表的链式存储结构 顺序表 缺点 : 移动节点, 不利于动态插入和删除 优点 : 随机存取, 得到第 i 个结点的时间为 O(1) 与表长和位置无关 2.3.1 31 单链表 ( 线性链表 ) 存储方法 : 用一组任意存储单元来存放结点 ( 可连续, 亦可不连续 ); 为表示逻辑关系, 须存储后继或前驱信息 15 16 结点结构 数据域指针域 ( 链域 ) next 指向该结点的后继 ( 的地址 ) 表示 1 开始结点无前驱, 用头指针表示 2 终端结点无后继,next 域为空 (NULL) 17 逻辑状态头指针唯一确定一个单链表存储状态见图 25 2.5 特征 1 非顺序存取 2 用指针表示结点间逻辑关系 3 动态分配 18 3
实现 : typedef struct node{ // 结点类型定义 DataType data; // 数据域 struct node *next; // 指针域 ListNode; typedef ListNode *LinkList; // 链表类型定义 ListNode *p; // 结点定义 LinkList head; // 链表头指针定义 结点变量和指针变量指针变量 p: 值为结点地址结点变量 *p: 值为结点内容动态申请, 垃圾收集 19 20 1. 建立单链表 (1) 头插法 : 从空表开始, 重复读入数据 : 申请新结点 插入表头, 直至输入结束 表次序与输入次序相反 处理自然简单 (2) 尾插法 : 设为指针 r 指向当前链尾 ( 初值为 NULL) 1 申请新结点 s 2 将读入数据写入 3 新结点链到表尾 ( 应注意边界条件 ) 4 修改尾指针 r 21 22 为简便起见, 设结点数据类型 DataType 为 char, 输入字符, 换行符结束 LinkList CreateList(void){ //ch, head, r 为局部量 head = r = NULL; // 开始为空表 while ((ch = getchar())!= \n ){ s = (ListNode*)malloc(sizeof(ListNode)); s->data = ch; // 2 if (head == NULL) // 插入空表 head = s; // 1 // 新结点插入空表 ( 边界 ),r 为空 23 else r->next = s; // 3 r = s; // 4 if (r!= NULL) r->next = NULL; return head; 边界条件处理 : // 非空表, 终端结点指针为空无后继 空表和非空表处理不一致简化方法 : 引入头结点 ( 哨兵 ), 其中 data 域可做它用 ( 如表长度 ) 24 4
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; // 生成头结点 25 r->next = s; r = s; r->next = NULL; // 终端结点指针置空, 或空表时头结点指针置空 return head; Note: 为简化起见,, 申请结点时不判是否申请到 时间 : O(n) 26 2. 查找 1 按值查找 找链表中关键字为 k 的结点 2 按序号查找 合法位置 1 i n. 头结点可看作第 0 个结点 返回第 i 个结点的地址, 即找到第 i-1 个结点, 返回其 next 域 思想 : 顺链扫描 :p---- 当前扫描到的结点, 初始指向头结点 j---- 计算器 累加扫描到的结点, 初始值为 0 每次加 1, 直至 j=i 为止,p 指向 ith 结点 27 算法 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, 找头结点 28 3. 插入 问题 : 将值为 x 的结点插到表的第 i 个结点位置上 即在 a i-1 和 a i 之间插入 故须找到第 a i-1 个结点的地址 p, 然后生成新结点 *s, 将其链到 a i-1 之后,a i 之前 29 void InsertList (LinkList head, DataType x, int i) { // 带头结点 1 i n+1 ListNode *p; p = GetNode(head, i-1); // 寻找第 i-1 个结点 1 if (p== NULL) // i<1 或 i>n+1 时插入位置 i 有错 Error("position error"); s = (ListNode *)malloc(sizeof (ListNode)); //2 s->data=x; //3 s->next=p->next; //4 p->next=s; //5 思考 : 若无头结点, 边界如何处理? 时间 : 主要是 GetNode O(n) 合法位置 1 i n+1 GetNode: 0 i n 30 5
4. 删除 删 ith 结点 首先找 a i-1 void DeleteList (LinkList head, int i){ // 合法位置是 1 i n p = GetNode (head, i-1); //1 if (!p!(p->next)) // i<1 或 i>n 时删除位置有错 Error("position (p error"); r = p->next; //2 令 r 指向被删结点 a i p->next = r->next; // 3 将 a i 从链上摘下 free(r); // 4 释放 a i 31 32 正确性分析 1 i<1 时,GetNode 中的参数 <0 此时返回 p 为空 2 i=n+1 时,GetNode 中参数 =n 返回终端结点, 此时 p->next 为空 3 i>n+1 时,GetNode 返回 p 为空 时间 O(n) 结论 : 链表上插 删无须移动结点, 仅需修改指针 33 2.3.2 循环链表 ( 单 ) 首尾相接 : 不增加存储量, 只修改连接方式 优点 : 从任一结点出发可访问到表中任一其它结点, 如找前驱 (O(n)) 遍历表的终止方式 : p 为空或 p->next 为空 p=head 或 p->next=head 34 2.3.2 循环链表 ( 单 ) 仅设尾指针更方便 : 访问开始结点和终端结点的时间均为 O(1) 例如 : 合并两个单循环链表的时间为 O(1), 但用头指针表示时 : T(mn)=O(max(mn)) T(m,n)=O(max(m,n)) 或 O(min(m,n)) n)) 2.3.3 双链表 ( 循环 ) 单链表只有后向链, 找一结点的后继时间为 O(1), 但找前驱费时, 若经常涉及找前驱和后继, 则可选双链表 35 36 6
2.3.3 双链表 ( 循环 ) 结构特征 对称结构 : 若 p 不空, 则 p->prior->next = p = p->next->prior 优点 : 1 找一结点前驱和找一结点后继同样方便 2 删 *p 本身和删 *p 的后继同样方便 2.3.3 双链表 ( 循环 ) 例 1: 前插 s->data=x; // 2 s->prior=p->prior; // 3 s->next=p; // 4 p->prior->next=s; // 5 p->prior=s; // 6 例 2: 删 *p p->prior->next=p->next; p->next->prior=p->prior; free(p); 37 38 上述链表是由指针实现的, 其中结点分配和回收是由系统实现的, 系统提供了 malloc 和 free 动态执行, 故称为动态链表 动态 ---- 程序执行时系统动态分配和回收 静态链表 ---- 先分配大空间作为备用结点空间 ( 即存储池 ) 用下标 ( 亦称游标 cursor) 模拟指针, 自定义分配和释放结点函数 1. 定义 #define nil 0 // 空指针 #define MaxSize 1000 // 可容纳的结点数 typedef struct { DataType data; int next; node, NodePool[MaxSize]; typedef int StaticList; 39 40 2. 基本操作 ( 模拟动态链表 ) 1 初始化将整个表空间链成一个备用链表, 只做一次 void Initiate(NodePool space) { // 备用链表的头结点位置为 space[0] for (i=0; i<maxsize-1; i++) space[i].next = i+1; space[maxsize-1].next = nil; 2 分配结点在备用链表上申请一个结点, 返回非空 ( 不等于 0) 成功, 否则失败 int AllocNode(NodePool space) { i = space[0].next; // 取备用链表上开始结点, 位置为 i, 即 space 的第 i 个分量 if (i) // 开始结点非空 space[0].next = space[i].next; // 将开始结点从备用链表上摘下 return i; // 为 nil 时失效 41 42 7
3 释放结点 3. 一般操作 将释放结点收还到备用链表的头上 void FreeNode(NodePool space, int ptr) { // 将 ptr 所指结点回收到备用链表头结点之后 space[ptr].next = space[0].next; space[0].next = ptr; 43 1 插入 void Insert(NodePool space, StaticList L, DataType x, int i) { // 在带头结点的静态链表 L 的第 i 个结点 a i 之前插入新结点 x p = Locate(space, L, i-1); // 找 L 中 a i 的前驱 1 if (p == nil) Error( Position error! ); // 位置错 S = AllocNode(space); // 申请结点 2 if (s == nil) Error( Overflow ); // 申请失败, 空间不足判定 space[s].data = x; // 3 space[s].next = space[p].next; // 4 space[p].next = s; // 5 44 2 删除 void Delete(NodePool space, StaticList L, int i) { p = Locate(space, L, i-1); // 找 L 中 a i 的前驱 1 if (p == nil space[p].next == nil) Error( Position error! ); // 位置错 q = space[p].next; // q 指向被删结点 a i 2 space[p].next = space[q].next; // 将 a i 摘下 3 FreeNode(space, q); // 4 注意 : 链表头指针实际上整数, 即 space 的下标 45 46 在 spce 中可能有多个链表, 若再建立一个链表 head, 头结点在哪个位置? 47 48 8
静态链表特点 : 没有指针类型的语言可以使用 亦可有双链表 循环链表等 对比 : 动态链表静态链表指针变量 ptr 下标 ptr 结点变量 *ptr 结点 space[ptr] 结点后继位置 ptr->next 结点后继位置 space[ptr].next 2.4 顺序表和链表之比较 作业 1. 为什么在单循环链表中设置尾指针比设置头指针更好? 2. 写一个算法将单链表中值重复的结点删除, 使所得的结果表中各结点值均不相同 49 9