数据结构 第2章 线性表.ppt

数据结构 与 算法 第三讲：线性表（二） 内容提要 v线性表的顺序存储结构回顾 v单链表 v循环链表 v双向链表 v静态链表 *2 线性表的顺序存储结构回顾（1） *3 a1 0 a2 1 ai-1 i-2 ai i-1 an i-1 空闲空间 下标： 数组的长度MAXSIZE 线性表的当前长度length(=n) data 即 LOC(a1) / 线性表顺序存储的结构代码 #define MAXSIZE 20 typedef int ElemType; typedef struct ElemType dataMAXSIZE; int length; SqList; 三个属性： 存储空间的起始地址：data 线性表的最大存储容量：MAXSIZE 线性表的当前长度：length c (i-1)*c LOC(ai) 存储位置地址计算公式： LOC(ai)=LOC(a1)+(i-1)*c 其中c为每个数据元素占用的字节长度 线性表的顺序存储结构回顾（2） *4 / 插入算法的思路（参数：线性表L，插入位置i，插入元素e） 1. 如果插入位置i不合理，提示异常； 2. 如果线性表长度大于等于数组长度MAXSIZE，提示异常或动态增加容量； 3. 从最后一个元素开始向前遍历到第i个位置，分别将它们都向后移动一个位置 ； 4. 将要插入元素e填入位置i处； 5. 表长加1 。 ABCDEFGH 空闲空间 ABCDEFGH 空闲空间 插入前： 插入后： 线性表的顺序存储结构回顾（3） *5 / 删除算法的思路（参数：线性表L，删除位置i，用来存放被删除元素的变量e ） 1. 如果删除位置i不合理，提示异常； 2. 取出删除元素，存放在e中； 3. 从删除位置i开始遍历到最后一个元素位置，分别将他们都向前移动一个位置 ； 4. 表长减1 。 删除前： 删除后：ABCDEFGH空闲空间 ABCDEFGH 空闲空间 实验1：顺序存储结构线性表 *6 vFTP地址：4 v用 户：zheng_stu v密 码：123456 v目 录：/student/数据结构/实验1 v文 件：sqlist_todo.cpp v任 务：在程序中标有/*ADD YOUR CODE HERE*/的地方加入自己的代码使程 序功能完整，且能够正确运行。 线性表顺序存储结构的优缺点 *7 顺序存储结构不足的解决办法 v思路(链式存储）： q元素可以散落在任何位置， 不必相邻 q让每个元素知道它的下一个 元素在哪里 q我们只需要知道第一个元素 的位置 q插入删除不再需要移动元素 而是需要修改元素间的关系 *8 1 2 3 4 5 6 234561 线性表链式结构的存储示意 假设我们有一个线性表(a1,a2,an) *9 ai0500ai+10800 地址0500 数据信息 结结点 指针针 数据域指针针域 a10700anNULL 第一个结结点 地址0900 0900 头头指针针 指针针指向空 最后一个结结点 图a：链表中的相邻元素 图b：一个完整的链表 【注意】有没有不大协调的地方？ 头结点与头指针 *10 a10700anNULL 第一个结结点 地址0900 0900 头头指 针针 指针针指向空 最后一个结结点 0500 可存线线性表长长度等公共数据，地址0500 头结头结点 图c：一个带头结点的完整链表 【注意】接下去的讨论都基于带头结点的链表 另一种图示与单链表的C语言定义 *11 / 单链表的结构代码 typedef int ElemType; typedef struct Node ElemType data; struct Node *next; Node; typedef Node *LinkList; a1a2an 头头指针针 数据域 指针针域 数据元素 头结头结点后继继指针针地址结结点 头头指针针 空链表 aiai+1 p-datap-next-data *p 假设我们定义：Node *p; *p-next pp-next 单链表的读取 v单链表的第i个元素的地址在哪？ q算法思路： 1.声明一个结点指针 p 指向链表的第一个结点，初 始化整型变量 j 从1开始； 2.当 jnext; /* 让p指向链表L的第一个结点 */ 6. j = 1; /* j为计数器 */ 7. while (p /* 让p指向下一个结点 */ 10. +j; 11. 12. if (!p | ji) 13. return ERROR; /* 第i个元素不存在 */ 14. *e = p-data; /* 取第i个元素的数据 */ 15. return OK; 16. *13 是不是很麻烦？有失必有得，接下来我们看看如何实现“插入”和“删除”。 单链表的结点插入 v假设存储元素 e 的结点为 s，要插入到结点 p 和 p-next 之间 *14 aiai+1 *p*p-next pp-next ai s *s ? 正确的做法： s-next=p-next; p-next=s; 错误的做法： p-next=s; s-next=p-next; p-next p-next s-next aiai+1 *p*p-next p e s *s s-next p-next p-next s-next aiai+1 *p*p-next p e s *s s-next 单链表第i个位置结点的插入 v算法思想： （参数：单链表L，插入位置i，插入元素e） 1.声明一结点指针p指向链表头结点，初始化j从1开始； 2.当jdata ; 6.使用刚才的插入语句(s-next=p-next; p-next=s;)把s插入链表中; 7.返回成功。 *15 【注意】有了头结点，在链表的头尾处插入结点并没有什么不同之处。 s-next a1 *L 头头指针针 L e s *s an e s *s 实现在单链表第i个位置插入元素的代码 /* 初始条件：单链表L已存在，1next; 10. +j; 11. 12. if(!p | ji) 13. return ERROR; /* 第i个元素不存在 */ 14. s = (Node*)malloc(sizeof(Node); /* 生成新结点 */ 15. s-data = e; /* 将s的后继指针指向p的后继 */ 16. s-next = p-next; /* 将p的后继指针指向s */ 17. p-next = s; 18. return OK; 19. *16 单链表的结点删除 v假设要删除单链表中 q 指向的结点，其中 p 是 q 的前继结点 *17 ai-1ai *p*q 即*p-next p 正确的做法：p-next = p-next-next; 或者：q = p-next; p-next = q-next; ai+1 *q-next 即*p-next-next ? ai *q 即*p-next ai-1 *p p ai+1 *q-next 即*p-next-next 单链表第i个结点的删除 v算法思想（参数：单链表L，删除位置i，用来存放被删除元素的变量e） 1.声明一结点指针p指向链表头结点，初始化j从1开始； 2.当jnext结点； 5.使用刚才的删除语句(p-next = q-next;)把该结点从链表中 摘除; 6.将q结点中的数据赋值给e，作为一个返回值； 7.释放q结点； 8.返回成功。 *18 实现删除单链表第i个元素的代码 /* 初始条件：单链表L已存在，1next 10. +j; 11. 12. if(!(p-next) | ji) 13. return ERROR; /* 第i个元素不存在 */ 14. q = p-next; 15. p-next = q-next; /* 将p的后继指针指向q的后继 */ 16. *e = q-data; /* 将q指向结点的数据赋给e */ 17. free(q); /* 让系统回收此结点，释放内存 */ 18. return OK; 19. *19 【思考】单链表的插入和删除的时间复杂度是多少? 单链表的整表创建 算法思路： 1.声明一结点指针p和计数器变量i； 2.初始化一空链表L； 3.让L的头结点指针指向NULL，即建立一个带头结点的单链 表； 4.循环： o生成一新结点，用p指向该结点； o随机生成一个100以内的数字赋值给p结点的数据域p-data; o将p插入（头插法：到头结点与前一新结点之间；尾插法：到末尾 结点之后）。 *20 实现单链表整表创建的代码（头插法） *21 /* 随机产生n个元素的值，建立带头结点的单链表L（头插法）*/ 1.void CreateListHead(LinkList 4. int i; 5. srand(time(0); /* 初始化随机数种子 */ 6. L = (Node*)malloc(sizeof(Node);/* 先建立一个带头结点的空链表 */ 7. L-next = NULL; 8. for (i=0; idata = rand()%100+1; /* 随机生成100以内的数字 */ 12. p-next = L-next; /* 插入到表头 */ 13. L-next = p; 14. 15. p-next ai-1 *L 头头指针针 L ai p *p a1 *L-next 实现单链表整表创建的代码（尾插法） *22 /* 随机产生n个元素的值，建立带头结点的单链表L（尾插法）*/ 1.void CreateListTail(LinkList 4. int i; 5. srand(time(0); /* 初始化随机数种子 */ 6. L = (Node*)malloc(sizeof(Node);/* 先建立一个带头结点的空链表 */ 7. r = L; /* r为指向末尾结点的指针 */ 8. for (i=0; idata = rand()%100+1; /* 随机生成100以内的数字 */ 12. r-next = p; /* 插入到表尾 */ 13. r = p; /* 把r指向表尾结点 */ 14. 15. r-next = NULL; 16. aiai-1 *r r *p aiai-1 *r r *p aiai-1 r *p pp *r-next*r 单链表的整表删除 v算法思路： q声明结点指针p和q； q将p指向第一个结点； q循环： o将q指向p的下一个结点； o释放p； o将q赋值给p； *23 /* 初始条件：单链表L已存在 */ /* 操作结果：将L重置为空表 */ 1.Status ClearList(LinkList 4. p = L-next; 5. while (p) /* p指向第一个结点 */ 6. 7. q = p-next; 8. free(p); 9. p = q; 10. 11. L-next = NULL; 12. return OK; 13. 【思考】只使用指针p而不使用指针q 行不行？ 单链表结构和顺序存储结构的对比 *24 【思考】游戏设计中，存储用户注册信息用什么结构？存储玩家的 装备或武器列表用什么结构？ 单链表结构的尴尬 v假设我们的校园只有单行道 v保安沿这条路线巡逻，需要查遍所有地点。有一天， 保安先从主楼群出发，想把以上地点走一遍，此时主 管告诉他，不行，你必须从北门开始走。 *25 事实上，把主校门和北门连接起来，形成一个环路，就解决了这个问题。 循环链表 v将单链表中末尾结点的指针端由空指针改为指向头结 点，就使整个单链表形成一个环，这种头尾相接的单 链表成为循环链表（circular linked list）。 *26 a1an 头头指针针 【和单链表的主要区别】判断遍历结束的条件，原来是判断p-next是否 为空，现在则是p-next是否等于头结点。 a1a2an 尾指针针 【思考】为什么用尾指针表示循环链表更方便？（提示：我们经常需要访 问的结点是头结点和末尾结点） 头头指针针 两个循环链表的合并 *27 a1a2an rearA *rearA-next b1b2bm rearB *rearB-next*rearB-next-next (1) p = rearA-next; (2) q = rearB-next; (3) rearA-next = rearB-next-next; (4) rearB-next = p; (5) free(q); a1a2an rearA *rearA-next b1b2bm rearB *rearB-next-next *p p q (1) (3) (4) (2) (5) 双向链表 v终于有一天，保安在感叹：如果我们有双行道该多好啊！ v双向链表（double linked list）是在单链表的每个 结点中，再设置一个指向其前驱结点的指针域。 *28 / 双向链表的结构代码 typedef struct DulNode ElemType data; Struct DulNode *prior; struct DulNode *next; DulNode; typedef DulNode *DuLinkList; 【注意】对双向链表中的某结点p，它 的后继结点的前驱，以及前驱结点 的后继都是它自己。即 p-next-prior 等价于 p-prior-next 等价于 p 【思考】对求链表长度，查找元素的 操作，多一个指针有帮助吗？ 双向循环链表 *29 头头指针针 v双向的带头结点的循环链表空链表： v双向的带头结点的循环链表非空链表： 头头指针针 a1a2an 双向链表的插入 *30 ai+1 *p e *s *p-next ai (1) (2) (3) (4) s-prior = p; /* 把p赋值给s的前驱，如图中(1) */ s-next = p-next; /* 把p-next赋值给s的后继，如图中(2) */ p-next-prior = s; /* 把s赋值给p-next 的前驱，如图中(3) */ p-next = s; /* 把s赋值给p的后继，如图中(4) */ v假设存储元素e的结点为s，要将s插入到p和p-next之间 双向链表的删除 *31 ai+1 *p*p-next ai p-prior-next = p-next; /* 把p-next赋值给p-prior的后继，如图中(1) */ p-next-prior = p-prior; /* 把p-prior赋值给p-next的前驱，如图中(2) */ free(p) /* 释放结点，如图中(3) */ ai-1 *p-prior (1) (2) (3) v假设要删除图中的结点p 静态链表 v不用指针而用数组描述的链表叫做静态链表。 *32 01下标： 12 23 34 45 56 67 78 8 9 999 0 数组组第一个元素的cur用来存放 备备用链链表第一个结结点的下标标cur data 数组组最后一个元素的cur用来存放第一个 插入元素的下标标，相当于头结头结点 / 静态链表的结构代码 #define MAXSIZE 1000 typedef struct ElemType data; int cur; Component,StaticLinkListMAXSIZE; /* 将一维数组space中各分量连成备用链表，*/ /* space0.cur为头指针，“0”表示空指针 */ 1. Status InitList(StaticLinkList space) 2. 3. int i; 4. for (i=0; iListLength(L)+1) 6. return ERROR; 7. j = Malloc_SL