数据结构Ch2 线性表.ppt

《数据结构Ch2 线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构Ch2 线性表.ppt（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数 据 结 构 Ch.2 线性表,计 算 机 学 院 肖明军 Email: ,2,2.1 线性表的逻辑结构,线性表：由n(n0)个结点a1, , an组成的有限序列 记作：L = (a1, a2, , an), 属性：长度-结点数目n，n=0时为空表 ai-一般是同一类型,3,2.1 线性表的逻辑结构,逻辑特征 当L时， 有且仅有1个开始结点a1和1个终端结点an，a1仅有一直接后继，an仅有一直接前驱 内部结点ai(2in-1)均有一直接前驱ai-1和一直接后继ai+1 结点之间的逻辑关系是由位置次序决定的，ai出在表的第i个位置。该关系是线性的(全序的)，故称L为线性表。,4,2.1 线性

2、表的逻辑结构,举例： 英文字母表(A, B, , Z) 扑克牌点数(2, 3, , 10, J, Q, K, A) 学生成绩表 等 ai-抽象符号。具体应用可能是一个结构类型的对象 线性表是一种相当灵活的数据结构，其长度可根据需要增长或缩短 基本运算： InitList(L), ListLength(L), GetNode(L, i) 等 复杂运算可通过基本运算去构造,Ch.2 线性表,线性表的抽象数据类型定义 ADT List 数据对象：D = ai | aiElemSet, i=1,2,n, n0 数据关系：R = | ai-1, aiD, i=2,3,n 基本操作： InitList(

3、/假定 typedef int DataType; /依具体使用定 typedef struct DataTypedataListSize; /存放结点 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) 为保持结点的物理顺序和逻辑顺序一致，须： 将an, , ai依次后移1位，空出ith位置 插入x 表长加1,11,2.2.2 顺序表上实现的基本运算,算法：

4、void InsertList(SegList *L, DataType x, int i) int j; /注意c数组1st位置的下标为0. ai的位置是datai-1. if (iL-length+1) /1in+1是合法插入位置 Error(“Position error!”); if (L-length = ListSize) Error (“Overflow”); /溢出 for (j = L-length-1; j=i-1; j-) L-dataj+1 = L-dataj; /结点后移 L-datai-1 = x; /插入x L-length+; /长度加1 ;,12,2.2.2

5、顺序表上实现的基本运算,分析： 循环后移，移动节点数为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) 为保持物理与逻辑顺序一致，

6、须： 前移：将ai+1, , an依次前移1位，填补删除ai留下的空间 表长减1,14,2.2.2 顺序表上实现的基本运算,算法： void DeleteList(SegList *L, int i) int j， n=L-length; if (in) Error(“Position error!”); /非法位置 for (j = i; jdataj-1 = L-dataj; /结点后移 L-length-; /长度减1 ;,15,2.2.2 顺序表上实现的基本运算,分析： 前移次数与n和i相关，移动节点数n-i。 最好情况：当i=n，不移动 O(1) 最坏情况：当i=1，前移n-1次 O

7、(n) 平均性能：,16,2.3 线性表的链式存储结构,顺序表 缺点：移动节点，不利于动态插入和删除 优点：随机存取，得到第i个结点的时间为O(1)与表长和位置无关 2.3.1 单链表（线性链表） 存储方法： 用一组任意存储单元来存放结点（可连续，亦可不连续）； 为表示逻辑关系，须存储后继或前驱信息,17,2.3.1 单链表（线性链表）,结点结构 数据域 指针域（链域） next指向该结点的后继（的地址） 表示 开始结点无前驱，用头指针表示 终端结点无后继，next域为空（NULL）,18,2.3.1 单链表（线性链表）,逻辑状态 头指针唯一确定一个单链表 存储状态 见图2.5 特征 非顺序存

8、取 用指针表示结点间逻辑关系 动态分配,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）

9、头插法： 从空表开始，重复读入数据：申请新结点、插入表头，直至输入结束。 表次序与输入次序相反。 处理自然简单,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 = (

10、ListNode*)malloc(sizeof(ListNode); / s-data = ch; / if (head = NULL) /插入空表 head = s; /新结点插入空表（边界），r为空,24,2.3.1 单链表（线性链表）,else r-next = s; / r = s; / if (r != NULL) r-next = NULL; /非空表，终端结点指针为空无后继 return head； 边界条件处理： 空表和非空表处理不一致 简化方法：引入头结点（哨兵），其中data域可做它用（如表长度）,25,2.3.1 单链表（线性链表）,LinkList CreateList

11、(void) /用尾插法建立带头结点的单链表 char ch； LinkList head = (Linklist)malloc(sizeof(ListNode); /生成头结点 ListNode *s, *r; r = head; /为指针初始指向头结点 while (ch = getchar() != n) s = (ListNode*)malloc(sizeof(ListNode); s-data = ch;,26,2.3.1 单链表（线性链表）,r-next = s; r = s; r-next = NULL; /终端结点指针置空，或空表时头结点指针置空 return head; No

12、te：为简化起见，申请结点时不判是否申请到 时间： O(n),27,2.3.1 单链表（线性链表）,2.查找 按值查找 找链表中关键字为k的结点 按序号查找 合法位置 1in. 头结点可看作第0个结点 返回第i个结点的地址，即找到第i-1个结点，返回其next域 思想： 顺链扫描：p-当前扫描到的结点，初始指向头结点 j-计数器。累加扫描到的结点，初始值为0 每次加1，直至 j=i为止，p指向ith结点 算法,28,2.3.1 单链表（线性链表）,ListNode *GetNode(LinkList head, int i) /在链表（有头结点）中查找ith结点 找到(0in)则返回该结点的存

13、储 /位置，否则返回NULL int j; ListNode *p; p = head; j = 0; /头结点开始扫描 while (p-next /当in时未找到 时间分析 循环终止条件是搜索到表尾或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 单链表（线性链表）,void InsertList (LinkList head, DataType x,

14、 int i) /带头结点 1in+1 ListNode *p; p = GetNode(head, i-1); /寻找第i-1个结点 if (p= NULL) / in+1时插入位置i有错 Error(position error); s = (ListNode *)malloc(sizeof (ListNode); / s-data=x; / s-next=p-next; / p-next=s; / 思考：若无头结点，边界如何处理？ 时间：主要是GetNode O(n) 合法位置 1in+1 GetNode： 0in,31,2.3.1 单链表（线性链表）,4.删除 删ith结点。首先找ai

15、-1。,32,2.3.1 单链表（线性链表）,void DeleteList (LinkList head, int i) /合法位置是1 i n p = GetNode (head, i-1); / if (!p | !(p-next) / in时删除位置有错 Error(position error); r = p-next; / 令r指向被删结点ai p-next = r-next; / 将ai从链上摘下 free(r); / 释放ai ,33,2.3.1 单链表（线性链表）,正确性分析 inext为空 in+1时，GetNode返回p为空 时间 O(n) 结论：链表上插、删无须移动结点

16、，仅需修改指针,34,2.3.2 循环链表（单）,首尾相接：不增加存储量，只修改连接方式 优点：从任一结点出发可访问到表中任一其它结点，如找前驱（O(n)） 遍历表的终止方式： p为空或p-next为空 p=head或p-next=head,35,2.3.2 循环链表（单）,仅设尾指针更方便：访问开始结点和终端结点的时间均为O(1)。 例如：合并两个单循环链表的时间为O(1)，但用头指针表示时： T(m,n)=O(max(m,n)或O(min(m,n),36,2.3.3 双链表（循环）,单链表只有后向链，找一结点的后继时间为O(1)，但找前驱费时，若经常涉及找前驱和后继，则可选双链表。,37,

17、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 静态链表,上述链表是由指针实现的，其中结点分配和回收是由系统实现的

18、，系统提供了malloc和free动态执行，故称为动态链表。 动态-程序执行时系统动态分配和回收 静态链表- 先分配大空间作为备用结点空间（即存储池） 用下标（亦称游标cursor）模拟指针，自定义分配和释放结点函数,40,2.3.4 静态链表,1.定义 #define nil 0 /空指针 #define MaxSize 1000 /可容纳的结点数 typedef struct DataType data; int next; node, NodePoolMaxSize; typedef int StaticList;,41,2.3.4 静态链表,2.基本操作（模拟动态链表） 初始化 将整个

19、表空间链成一个备用链表，只做一次。 void Initiate(NodePool space) /备用链表的头结点位置为space0 for (i=0; iMaxSize-1; i+) spacei.next = i+1; spaceMaxSize-1.next = nil; ,42,2.3.4 静态链表,分配结点 在备用链表上申请一个结点，返回非空（不等于0）成功，否则失败。 int AllocNode(NodePool space) i = space0.next; /取备用链表上开始结点，位置为i，即space的第i个分量 if (i) /开始结点非空 space0.next = spa

20、cei.next; /将开始结点从备用链表上摘下 return i; /为nil时失效 ,43,2.3.4 静态链表,释放结点 将释放结点收还到备用链表的头上。 void FreeNode(NodePool space, int ptr) /将ptr所指结点回收到备用链表头结点之后 spaceptr.next = space0.next; space0.next = ptr; ,44,2.3.4 静态链表,3.一般操作 插入 void Insert(NodePool space, StaticList L, DataType x, int i) / 在带头结点的静态链表L的第i个结点ai之前插

21、入新结点x p = Locate(space, L, i-1); /找L中ai的前驱 if (p = nil) Error(“Position error!”); /位置错 S = AllocNode(space); /申请结点 if (s = nil) Error(“Overflow”); /申请失败，空间不足判定 spaces.data = x; / spaces.next = spacep.next; / spacep.next = s; / ,45,2.3.4 静态链表,删除 void Delete(NodePool space, StaticList L, int i) p = Lo

22、cate(space, L, i-1); / 找L中ai的前驱 if (p = nil | spacep.next = nil) Error(“Position error!”); / 位置错 q = spacep.next; / q指向被删结点ai spacep.next = spaceq.next; / 将ai摘下 FreeNode(space, q); / 注意：链表头指针实际上整数，即space的下标,46,2.3.4 静态链表,47,2.3.4 静态链表,48,2.3.4 静态链表,在spce中可能有多个链表，若再建立一个链表head，头结点在哪个位置？,49,2.3.4 静态链表,静态链表特点： 没有指针类型的语言可以使用。亦可有双链表。循环链表等。 对比： 动态链表静态链表 指针变量ptr下标ptr 结点变量*ptr结点spaceptr 结点后继位置ptr-next结点后继位置spaceptr.next 2.4 顺序表和链表之比较 存储密度=结点数据所占的存储量/结点结构所占的存储量,作业,为什么在单循环链表中设置尾指针比设置头指针更好？ 写一个算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。,