《隐藏信息检测与还原技术课件》由会员分享，可在线阅读，更多相关《隐藏信息检测与还原技术课件（48页珍藏版）》请在金锄头文库上搜索。
1、1Ch.2 线性表线性表22.1 线性表的逻辑结构线性表的逻辑结构n线性表线性表 由由n(n0)个结点个结点a1, , an组成的有限序列组成的有限序列v记作：记作：L = (a1, a2, , an)v属性：长度属性：长度n ，结点数目，结点数目 n=0时为空表时为空表vai：一般是同一类型：一般是同一类型32.1 线性表的逻辑结构线性表的逻辑结构n逻辑特征逻辑特征当当L时，时，有有且且仅仅有有1个个开开始始结结点点a1和和1个个终终端端结结点点an，a1仅有一直接后继，仅有一直接后继，an仅有一直接前驱仅有一直接前驱内内部部结结点点ai（2in-1）均均有有一一直直接接前前驱驱ai-1和和
2、一直接后继一直接后继ai+1结结点点之之间间的的逻逻辑辑关关系系是是由由位位置置次次序序决决定定的的，ai处处在在表表的的第第i个个位位置置。该该关关系系为为线线性性(全全序序)的的，故称故称L为为线性表线性表。42.1 线性表的逻辑结构线性表的逻辑结构n举例举例v英文字母表英文字母表(A, B, , Z)v扑克牌点数扑克牌点数(2, 3, , 10, J, Q, K, A)v学生成绩表学生成绩表 等等ai-抽象符号。具体应用可能是一个结构类型的对象抽象符号。具体应用可能是一个结构类型的对象n基本运算基本运算InitList(L), ListLength(L), GetNode(L, i) 等
3、等复杂运算可通过基本运算去构造复杂运算可通过基本运算去构造52.2 线性表的顺序存储结构线性表的顺序存储结构2.2.1 顺序表顺序表n定义：定义：将线性表中结点按逻辑次序依次存储在将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里。由此存储的一组地址连续的存储单元里。由此存储的L称称为顺序表。为顺序表。n地址计算地址计算设结点大小为设结点大小为ll个单元，其中第个单元，其中第1个单元为该结点地址个单元为该结点地址Loc(ai) = Loc(a1) + (i-1) * l lL的基地址的基地址2.2.1 顺序表顺序表n特征特征随机存储随机存储只需存储结点。无需用只需存储结点。无需用辅助空
4、间存储逻辑关系。辅助空间存储逻辑关系。但空闲大小不易确定，但空闲大小不易确定，易浪费空间易浪费空间静态分配（当用向量实静态分配（当用向量实施时）亦可动态申请空施时）亦可动态申请空间，但间，但copy成本大成本大（扩充表时）。（扩充表时）。672.2.1 顺序表顺序表n实现：实现：用向量实现用向量实现#define ListSize 100; /假定假定typedef int DataType; /依具体使用定依具体使用定typedef struct DataTypedataListSize; /存放结点存放结点 int length; /当前表长当前表长n Seqlist;82.2.2 顺序表
5、上实现的基本运算顺序表上实现的基本运算1.插入插入n基本思想基本思想在在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表长加表长加192.2.2 顺序表上实现的基本运算顺序表上实现的基本运算n算法算法void InsertList(SeqList *L, DataType x, int i) in
6、t 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-data j+1 = L-data j; /结点后移结点后移 L-datai-1 = x; /插入插入x L-length+; /长度加长度加1;102.2.2 顺序表上实现的基本运算顺序表上实现
7、的基本运算n分析分析循环后移，移动节点数为循环后移，移动节点数为n-i+1，时间与，时间与 相关相关最好情况：最好情况：当当i=n+1，不移动，不移动 O(1) 常数时间解释常数时间解释 O(n0)与与n无关无关最坏情况：最坏情况：当当i=1，全部后移，全部后移 O(n)平均性能平均性能设任何合法位置上插入的概率相等：设任何合法位置上插入的概率相等： (位置位置i插入的概率插入的概率)当位置当位置i确定时，后移次数亦确定：确定时，后移次数亦确定：n-i+1. 故表中平均移动结点为：故表中平均移动结点为：即插入时，平均移动表中一半结点即插入时，平均移动表中一半结点112.2.2 顺序表上实现的基
8、本运算顺序表上实现的基本运算2.删除删除n基本思想基本思想在在L中删除中删除ith结点结点 (1 i n)。(a1, , ai-1, ai, ai+1, , an) (a1, , ai-1, ai+1, , an-1)为保持物理与逻辑顺序一致，须：为保持物理与逻辑顺序一致，须：前移：将前移：将ai+1, , an依次前移依次前移1位，填补删除位，填补删除ai留下留下的空间的空间表长减表长减1122.2.2 顺序表上实现的基本运算顺序表上实现的基本运算n算法算法void DeleteList(SeqList *L, int i) int j， n=L-length; if (in) Error(
9、“Position error!”); /非法位置非法位置 for ( j = i; jdata j-1 = L-data j; /结点后移结点后移 L-length-; /长度减长度减1;132.2.2 顺序表上实现的基本运算顺序表上实现的基本运算n分析分析前移次数与前移次数与n和和i相关，移动节点数相关，移动节点数n-i。最好情况：最好情况：当当i=n，不移动，不移动 O(1)最坏情况：最坏情况：当当i=1，前移，前移n-1次次 O(n)平均性能：平均性能：142.3 线性表的链式存储结构线性表的链式存储结构n顺序表顺序表v缺点：缺点：移动节点，不利于动态插入和删除移动节点，不利于动态插入
10、和删除v优点：优点：随机存取，得到第随机存取，得到第i个结点的时间为个结点的时间为O(1)与与表长和位置无关表长和位置无关2.3.1 单链表（线性链表）单链表（线性链表）n存储方法存储方法用一组任意存储单元来存放结点（可连续，亦可不连续）用一组任意存储单元来存放结点（可连续，亦可不连续）为表示逻辑关系，须存储后继或前驱信息为表示逻辑关系，须存储后继或前驱信息152.3.1 单链表（线性链表）单链表（线性链表）n结点结构结点结构数据域数据域 指针域（链域）指针域（链域）next指向该结点的后继（的地址）指向该结点的后继（的地址）n表示表示开始结点无前驱，用头指针表示开始结点无前驱，用头指针表示终
11、端结点无后继，终端结点无后继，next域为空（域为空（NULL）162.3.1 单链表（线性链表）单链表（线性链表） 逻辑状态逻辑状态头指针唯一确定一个单链表头指针唯一确定一个单链表存储状态存储状态 见图见图2.5n特征特征顺序存取顺序存取用指针表示结点间逻辑关系用指针表示结点间逻辑关系动态分配动态分配172.3.1 单链表（线性链表）单链表（线性链表）n实现实现typedef struct node /结点类型定义结点类型定义 DataType data; /数据域数据域 struct node *next; /指针域指针域 ListNode ;typedef ListNode *LinkL
12、ist ; /链表类型定义链表类型定义ListNode *p; /结点定义结点定义LinkList head; /链表头指针定义链表头指针定义182.3.1 单链表（线性链表）单链表（线性链表）v结点变量和指针变量结点变量和指针变量指针变量指针变量p：值为结点地址：值为结点地址结点变量结点变量*p：值为结点内容：值为结点内容动态申请，垃圾收集动态申请，垃圾收集192.3.1 单链表（线性链表）单链表（线性链表）1.建立单链表建立单链表n头插法头插法v从空表开始，重复：从空表开始，重复： 读入数据，申请新结点，插入表头读入数据，申请新结点，插入表头 直至输入结束。直至输入结束。v表次序与输入次序
13、相反。表次序与输入次序相反。v处理自然简单处理自然简单202.3.1 单链表（线性链表）单链表（线性链表）n尾插法尾插法设尾指针设尾指针r指向当前链尾（初值为指向当前链尾（初值为NULL）申请新结点申请新结点s将读入数据写入将读入数据写入新结点链到表尾（应注意边界条件）新结点链到表尾（应注意边界条件）修改尾指针修改尾指针r21为简便起见，设结点数据类型为简便起见，设结点数据类型DataType为为char，输入字符，换行符结束，输入字符，换行符结束LinkList CreateList(void) /ch, head, r为局部量为局部量 head = r = NULL; /开始为空表开始为空
14、表 while (ch = getchar() != n) s = (ListNode*)malloc(sizeof(ListNode); / s-data = ch; / if (head = NULL) /插入空表插入空表 head = s; /新结点插入空表（边界），新结点插入空表（边界），r为空为空 else r-next = s; /endif r = s; / /endwhile if (r != NULL) r-next = NULL; /非空表，终端结点无后继非空表，终端结点无后继 return head；/endcreatelist222.3.1 单链表（线性链表）单链表（线
15、性链表） v边界条件处理边界条件处理空表和非空表处理不一致空表和非空表处理不一致简化方法：简化方法：引入头结点（哨兵），其中引入头结点（哨兵），其中data域可做它用（如表长度）域可做它用（如表长度）232.3.1 单链表（线性链表）单链表（线性链表）LinkList CreateList(void) /用尾插法建立带头结点的单链表用尾插法建立带头结点的单链表 char ch； LinkList head = (Linklist)malloc(sizeof(ListNode);/生成头结点生成头结点 ListNode *s, *r; r = head; /尾指针初值指向头结点尾指针初值指向头结
16、点 while (ch = getchar() != n) s = (ListNode*)malloc(sizeof(ListNode);s-data = ch; r-next = s;r = s; r-next = NULL; /终端结点指针置空，或空表时头结点指针置空终端结点指针置空，或空表时头结点指针置空 return head;242.3.1 单链表（线性链表）单链表（线性链表） Note：为简化起见，申请结点时不判是否申请到：为简化起见，申请结点时不判是否申请到v时间：时间： O(n)252.3.1 单链表（线性链表）单链表（线性链表）2.查找查找按值查找按值查找找链表中关键字为找链
17、表中关键字为k的结点的结点按序号查找按序号查找合法位置合法位置 1in. 头结点可看作第头结点可看作第0个结点个结点返回第返回第i个结点的地址，即找到第个结点的地址，即找到第i-1个结点，返回其个结点，返回其next域域思想：思想：顺链扫描顺链扫描p-当前扫描到的结点，初始指向头结点当前扫描到的结点，初始指向头结点j-计数器。累加扫描到的结点数，初始值为计数器。累加扫描到的结点数，初始值为0，每次，每次 加加1，直至，直至 j=i为止，为止，p指向指向ith结点结点算法算法26ListNode *GetNode(LinkList head, int i) /在带头结点链表中查找在带头结点链表中
18、查找ith结点结点 ，找到，找到(0in)则返回该结点则返回该结点 /的存储位置，否则返回的存储位置，否则返回NULL int j; ListNode *p; p = head; j = 0; /从头结点开始扫描从头结点开始扫描 while (p-next & jnext为空或为空或j=i为止为止p = p-next; j+; if (i = j) return p; /找到找到 else return NULL; /当当in时未找到时未找到时间分析时间分析循环终止条件是搜索到表尾或循环终止条件是搜索到表尾或j=i。复杂度最多为。复杂度最多为i，与查找位置，与查找位置相关。相关。 /i=0，找
19、头结点，找头结点272.3.1 单链表（线性链表）单链表（线性链表）3.插入插入n思思想想：将将值值为为x的的结结点点插插到到表表的的第第i个个结结点点位位置置上上。即即在在ai-1和和ai之之间间插插入入。故故须须找找到到第第ai-1个个结结点点的的地地址址p，然后生成新结点，然后生成新结点*s，将其链到，将其链到ai-1之后，之后，ai之前。之前。 前插改后插前插改后插n算法算法28void InsertList (LinkList head, DataType x, int i) /带头结点带头结点 1in+1 ListNode *p; p = GetNode(head, i-1); /
20、寻找第寻找第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; /思考：思考：若无头结点，边界如何处理？若无头结点，边界如何处理？n时间：时间：主要是主要是GetNode O(n) 合法位置合法位置 1in+1 GetNode： 0in292.3.1 单链表（线性链表）单链表（线性链表）4.删除删除删删ith结点，首先找结点，首先找ai-1。302
21、.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); / 释放释放ai312.3.1 单链表（线性链表）单链表（线性链表）n正确性分析正确性分析i1时，时，GetNode
22、中的参数中的参数next为空为空in+1时，时，GetNode返回返回p为空为空n时间时间 O(n)结论：链表上插、删无须移动结点，仅需修改指针结论：链表上插、删无须移动结点，仅需修改指针322.3.2 循环链表（单）循环链表（单）n首尾相接：首尾相接：不增加存储量，只修改连接方式不增加存储量，只修改连接方式n优点：优点：从任一结点出发可访问到表中任一其它从任一结点出发可访问到表中任一其它结点，如找前驱（结点，如找前驱（O(n)）n遍历表的终止方式遍历表的终止方式p为空或为空或p-next为空为空 p=head或或p-next=head 332.3.2 循环链表（单）循环链表（单）n仅设尾指针
23、更方便仅设尾指针更方便 访问开始结点和终端结点的时间均为访问开始结点和终端结点的时间均为O(1)。例如：合并两个单循环链表的时间为例如：合并两个单循环链表的时间为O(1)，但用头，但用头指针表示时：指针表示时：T(m,n)=O(max(m,n)或或O(min(m,n)342.3.3 双链表（循环）双链表（循环）单单链链表表只只有有后后向向链链，找找一一结结点点的的后后继继时时间间为为O(1)，但但找找前前驱驱费费时时，若若经经常常涉涉及及找找前前驱驱和和后后继继，则则可可选双链表。选双链表。352.3.3 双链表（循环）双链表（循环）n结构特征结构特征对称结构：若对称结构：若p不空，则不空，则
24、p-prior-next = p = p-next-priorn优点优点找一结点前驱和找一结点后继同样方便找一结点前驱和找一结点后继同样方便前插和后插一样方便前插和后插一样方便删删*p本身和删本身和删*p的后继同样方便的后继同样方便362.3.3 双链表（循环）双链表（循环）n例例1：前插：前插n例例2：删：删*ps-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);37nEx. 2.11, 2.13,
25、2.19, 2.21, 2,22382.3.4 静态链表静态链表上述链表是由指针实现的，其中结点分配上述链表是由指针实现的，其中结点分配和回收是由系统实现的，系统提供了和回收是由系统实现的，系统提供了malloc和和free动态执行，故称为动态执行，故称为动态链表动态链表。v动态动态-程序执行时系统动态分配和回收程序执行时系统动态分配和回收v静态链表静态链表-先分配大空间作为备用结点空间（即存储池）先分配大空间作为备用结点空间（即存储池）用下标（亦称游标用下标（亦称游标cursor）模拟指针，自定义）模拟指针，自定义分配和释放结点函数分配和释放结点函数392.3.4 静态链表静态链表1.定义定
26、义#define nil 0 /空指针空指针#define MaxSize 1000 /可容纳的结点数可容纳的结点数typedef struct DataType data;int next;node, NodePoolMaxSize;typedef int StaticList;402.3.4 静态链表静态链表2.基本操作（模拟动态链表）基本操作（模拟动态链表）初始化初始化将整个表空间链成一个备用链表，只做一次。将整个表空间链成一个备用链表，只做一次。void Initiate(NodePool space) /备用链表的头结点位置为备用链表的头结点位置为space0 for (i=0; inext结点后继位置结点后继位置spaceptr.next2.4 顺序表和链表之比较：略顺序表和链表之比较：略EX.2.38
