Microsoft PowerPoint - DS_Ch2.ppt [兼容模式]

Size: px

Start display at page:

Download "Microsoft PowerPoint - DS_Ch2.ppt [兼容模式]"

欧有荀
5 years ago
Views:

1 数据结构 Ch.2 线性表计算机学院肖明军线性表的逻辑结构线性表 : 由 n(n 0) 个结点 a 1,, a n 组成的有限序列记作 :L = (a 1, a 2,, a n ), 属性 : 长度 ---- 结点数目 n,n=0 时为空表 a i ---- 一般是同一类型线性表的逻辑结构逻辑特征当 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 为线性表线性表的逻辑结构举例 : 英文字母表 (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 线性表的顺序存储结构顺序表定义 : 将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里由此存储的 L 称为顺序表地址计算 : 设结点大小为 l 个单元, 其中第 i 个单元为该结点地址 Loc(a i ) = Loc(a 1 ) + (i-1) * l L 的基地址顺序表特征 : 1 随机存储 2 只需存储结点无需用辅助空间存储逻辑关系但空闲大小不易确定, 易浪费空间 3 静态分配 ( 当用向量实施时 ) 亦可动态申请空间, 但 copy 成本大 ( 扩充表时 ) 顺序表实现 : 用向量实现 #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

3 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) 与表长和位置无关单链表 ( 线性链表 ) 存储方法 : 用一组任意存储单元来存放结点 ( 可连续, 亦可不连续 ); 为表示逻辑关系, 须存储后继或前驱信息结点结构数据域指针域 ( 链域 ) next 指向该结点的后继 ( 的地址 ) 表示 1 开始结点无前驱, 用头指针表示 2 终端结点无后继,next 域为空 (NULL) 17 逻辑状态头指针唯一确定一个单链表存储状态见图特征 1 非顺序存取 2 用指针表示结点间逻辑关系 3 动态分配 18 3

实现 : typedef struct node{ // 结点类型定义 DataType data; // 数据域 struct node *next; // 指针域 ListNode; typedef ListNode *LinkList; // 链表类型定义 ListNode *p; // 结点定义 LinkList head; // 链表头指针定义结点变量和指针变量指针变量 p:

4 实现 : typedef struct node{ // 结点类型定义 DataType data; // 数据域 struct node *next; // 指针域 ListNode; typedef ListNode *LinkList; // 链表类型定义 ListNode *p; // 结点定义 LinkList head; // 链表头指针定义结点变量和指针变量指针变量 p: 值为结点地址结点变量 *p: 值为结点内容动态申请, 垃圾收集建立单链表 (1) 头插法 : 从空表开始, 重复读入数据 : 申请新结点插入表头, 直至输入结束表次序与输入次序相反处理自然简单 (2) 尾插法 : 设为指针 r 指向当前链尾 ( 初值为 NULL) 1 申请新结点 s 2 将读入数据写入 3 新结点链到表尾 ( 应注意边界条件 ) 4 修改尾指针 r 为简便起见, 设结点数据类型 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

5 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) 查找 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, 找头结点插入问题 : 将值为 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

6 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 正确性分析 1 i<1 时,GetNode 中的参数 <0 此时返回 p 为空 2 i=n+1 时,GetNode 中参数 =n 返回终端结点, 此时 p->next 为空 3 i>n+1 时,GetNode 返回 p 为空时间 O(n) 结论 : 链表上插删无须移动结点, 仅需修改指针循环链表 ( 单 ) 首尾相接 : 不增加存储量, 只修改连接方式优点 : 从任一结点出发可访问到表中任一其它结点, 如找前驱 (O(n)) 遍历表的终止方式 : p 为空或 p->next 为空 p=head 或 p->next=head 循环链表 ( 单 ) 仅设尾指针更方便 : 访问开始结点和终端结点的时间均为 O(1) 例如 : 合并两个单循环链表的时间为 O(1), 但用头指针表示时 : T(mn)=O(max(mn)) T(m,n)=O(max(m,n)) 或 O(min(m,n)) n)) 双链表 ( 循环 ) 单链表只有后向链, 找一结点的后继时间为 O(1), 但找前驱费时, 若经常涉及找前驱和后继, 则可选双链表

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;

程序执行时系统动态分配和回收静态链表 ---- 先分配大空间作为备用结点空间 ( 即存储池 ) 用下标 ( 亦称游标 cursor) 模拟指针, 自定义分配和释放结点函数 1.

7 2.3.3 双链表 ( 循环 ) 结构特征对称结构 : 若 p 不空, 则 p->prior->next = p = p->next->prior 优点 : 1 找一结点前驱和找一结点后继同样方便 2 删 *p 本身和删 *p 的后继同样方便双链表 ( 循环 ) 例 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); 上述链表是由指针实现的, 其中结点分配和回收是由系统实现的, 系统提供了 malloc 和 free 动态执行, 故称为动态链表动态 ---- 程序执行时系统动态分配和回收静态链表 ---- 先分配大空间作为备用结点空间 ( 即存储池 ) 用下标 ( 亦称游标 cursor) 模拟指针, 自定义分配和释放结点函数 1. 定义 #define nil 0 // 空指针 #define MaxSize 1000 // 可容纳的结点数 typedef struct { DataType data; int next; node, NodePool[MaxSize]; typedef int StaticList; 基本操作 ( 模拟动态链表 ) 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 时失效

space[ptr].next = space[0].next; space[0].

在带头结点的静态链表 L 的第 i 个结点 a i 之前插入新结点 x p = Locate(space, L, i-1); // 找 L 中 a i 的前驱 1 if (p

); // 位置错 S = AllocNode(space); // 申请结点 2 if (s == nil) Error( Overflow ); // 申请失败,

next = s; // 5 44 2 删除 void Delete(NodePool space, StaticList L, int i) { p =

8 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; // 删除 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 的下标在 spce 中可能有多个链表, 若再建立一个链表 head, 头结点在哪个位置?

9 静态链表特点 : 没有指针类型的语言可以使用亦可有双链表循环链表等对比 : 动态链表静态链表指针变量 ptr 下标 ptr 结点变量 *ptr 结点 space[ptr] 结点后继位置 ptr->next 结点后继位置 space[ptr].next 2.4 顺序表和链表之比较作业 1. 为什么在单循环链表中设置尾指针比设置头指针更好? 2. 写一个算法将单链表中值重复的结点删除, 使所得的结果表中各结点值均不相同 49 9

Microsoft Word - 专升本练习2：线性表.doc

Microsoft Word - 专升本练习2：线性表.doc 第二章线性表一选择题 1. 线性表是 ( ) A. 一个有限序列, 可以为空 B. 一个有限序列, 不能为空 C. 一个有限序列, 可以为空 D. 一个无序序列, 不能为空 2. 对顺序存储的线性表, 设其长度为 n, 在任何位置上插入或删除操作都是等概率插入一个元素时大约要移动表中的 ( ) 个元素, 删除一个元素时大约要移动表中的 ( ) 个元素 A. n/2 B. (n+1)/2 C.