教你掌握C++

计算概论 之 程序设计基础计算概论 之 程序设计基础 链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 黄罡 北京大学信息科学技术学院北京大学信息科学技术学院 上一讲内容回顾 结构是不同类型数据的集合结构是不同类型数据的集合 数组是相同类型数据的集合 结构和数组的每个元素都“独占”结构和数组的每个元素都“独占” 一段内存 连续存储连续存储 每个元素需对齐，元素地址%  sizeof(元素)= =0sizeof(元素)   0 结构的成员变量都可用 ʹ.ʹ 访问 结构指针还可以采用 ʹ‐>ʹ 访问结构指针还可以采用 ‐>  访问 结构作函数参数是值传递 其指针和引用作函数参数是地其指针和引用作函数参数是地 址传递 2 结构与文件 将结构数组存入文件，将结构数组存入文件， 然后从文件中读出并存 入另一个数组 3 结构与文件 ostream & write(const char *buffer, int len); istream & read(char *buffer, int len);istream & read(char buffer, int len); 4 链表（chained / linked list） 数组占有固定的内存空间，因此， 通过数组批量处理的数据的数量存在上限通过数组批量处理的数据的数量存在上限 如果未达到上限，则浪费了内存 链表能够更灵活地批量处理数据链表能够更灵活地批量处理数据 利用动态内存分配来按需分配和释放内存空间 如何管理动态增加或删除的内存数据块？ 5 链表（chained / linked list） 数组占有固定的内存空间，因此， 通过数组批量处理的数据的数量存在上限通过数组批量处理的数据的数量存在上限 如果未达到上限，则浪费了内存 链表能够更灵活地批量处理数据链表能够更灵活地批量处理数据 利用动态内存分配来按需分配和释放内存空间 link data 6 链表（chained / linked list） 数组批量处理占用固定内存的同类型数据数组批量处理占用固定内存的同类型数据 链表批量处理动态占用内存的同类型数据链表批量处理动态占用内存的同类型数据 链表是一种数据结构，利用 结构定义每个节点的数据类型 struct linker{ 数据变量1;结构定义每个节点的数据类型 指针定义节点之间的链接关系 动态内存分配按需创建和删除节点 数据变量1; ... 数据变量N; li k *动态内存分配按需创建和删除节点 next struct linker *next; } data next 7 链表的建立 链表是 种数据结构 利用链表是一种数据结构，利用  结构定义每个节点的数据类型  指针定义节点之间的链接关系 指针定义节点之间的链接关系  动态内存分配按需创建和删除节点 链表建立三部曲链表建立三部曲  1）定义每个节点存储的数据 • 例如 学号和成绩• 例如，学号和成绩 • 指向节点结构的指针next next data 8 链表的建立 链表是 种数据结构 利用链表是一种数据结构，利用  结构定义每个节点的数据类型  指针定义节点之间的链接关系 指针定义节点之间的链接关系  动态内存分配按需创建和删除节点 链表建立三部曲链表建立三部曲  2）利用动态内存分配命令new创建 第一个节点（头节点head）第 个节点（头节点head） • 节点存储数据赋初值 • 指向下一个节点的指针next赋空 next next NULL 实例化 head data data (1,90) 9 链表的建立 链表是 种数据结构 利用链表是一种数据结构，利用  结构定义每个节点的数据类型  指针定义节点之间的链接关系 指针定义节点之间的链接关系  动态内存分配按需创建和删除节点 链表建立三部曲链表建立三部曲  2）利用动态内存分配命令new创建 余下节点：节点存储数据赋初值余下节点：节点存储数据赋初值 • 指向下一个节点的指针next赋空  3）上一个节点的next指向本节点 d 1 link next NULL 实例化 head next node1 NULL data data (1,90) data (2,85) 10 链表的建立 链表是 种数据结构 利用链表是一种数据结构，利用  结构定义每个节点的数据类型  指针定义节点之间的链接关系 指针定义节点之间的链接关系  动态内存分配按需创建和删除节点 链表建立三部曲链表建立三部曲  2）利用动态内存分配命令new创建 余下节点：节点存储数据赋初值余下节点：节点存储数据赋初值 • 指向下一个节点的指针next赋空  3）上一个节点的next指向本节点 d 1 d 2 next NULLhead node1 NULL next node2 NULLnext data (1,90) data (2,85) data (3,95) 11 链表的建立 指针nodeXXX是多余的 可以省去指针nodeXXX是多余的，可以省去 因为上一个节点的指针next指向同一个节点地址 若要创建第N个节点，需要连 续写N-1个“->next”！续写N 1个 >next ！ 如何简化？ 注意：head指针必须保持不变 //注意next的逐层指向的对应关系 注 指 须 持 变 ，否则找不到头节点 next NULLhead NULL next NULLnext data (1,90) data (2,85) data (3,95) 12 链表的建立 在链表建立过程中 总是在链表尾部创建新的节点在链表建立过程中，总是在链表尾部创建新的节点 因此，让一个指针tail始终指向链表的尾部，负责新节点的创建 tail next NULLhead NULL next NULLnext data (1,90) data (3,95) data (2,85) 13 链表建立函数 //必须返回静态变量的指针//必须返回静态变量的指针 //必须置空，否则链尾错 14 链表的遍历 方式1 head >next >next > >next方式1：head‐>next‐>next‐>...‐>next 方式2：利用一个指针从head移动到tail 与利用 il指针创建链表类似与利用tail指针创建链表类似 tailmove next NULLhead d t NULL next NULL datadata next data (1,90) data (3,95) data (2,85) 15 链表的遍历 16 链表的创建与遍历 创建过程中直接将当前节创建过程中直接将当前节 点的next赋给tail，是否 更简单？更简单？ 此时程序输出是多少？ 17 链表的创建与遍历 创建过程中直接将当前节 点的next赋给tail是错的点的next赋给tail是错的 tail next NULLhead NULL next NULL data(1,90) data(2,80) 18 链表元素的查找 与遍历类似 不同之处在于找到指定元素即可停止遍历与遍历类似，不同之处在于找到指定元素即可停止遍历 19 链表元素的删除 首先 利用mo e指针查找到待删除的元素首先，利用move指针查找到待删除的元素 如果待删除的元素是头节点，则将head指 向下一个节点 然后删除原来的头节点 next NULLhead NULL next NULLnext move 向下一个节点，然后删除原来的头节点 NULLhead NULL NULL 如果待删除的元素不是头节点，则将前一个节点的next指 向待删除节点的下一个节点，然后删除该节点 nexthead next NULLnext move NULL 20 链表元素的删除 删除头节点，需先将head指向下一个节 点 然后删除原头节点move点，然后删除原头节点move 删除其他节点，需先将前一个节点ahead 的next指向待删除节点move的下一个节 点 然后删除该节点点，然后删除该节点 21 链表元素的删除 删除头节点 需先将删除头节点，需先将 head指向下一个节点， 然后删除原头节点move 删除其他节点，需先将 前一个节点ahead的next 指向待删除节点move的指向待删除节点 的 下一个节点，然后删除 该节点 22 链表元素的插入 首先 创建需要插入的节点newnode首先，创建需要插入的节点newnode 然后，用指针move遍历链表确定插入的位置 如果插入的是头部 则如果插入的是头部，则 newnode‐>next=head; head=newnode;  next NULLhead next NULLnext move NULL next newnode 23 链表元素的插入 首先 创建需要插入的节点newnode首先，创建需要插入的节点newnode 然后，用指针move遍历链表确定插入的位置 如果插入的是中部（move之后），则如果插入的是中部（move之后），则 newnode‐>next=move‐>next; move‐>next=newnode; ; nexthead nextnext move next NULLhead next NULLnext next newnode 24 链表元素的插入 首先 创建需要插入的节点newnode首先，创建需要插入的节点newnode 然后，用指针move遍历链表确定插入的位置 如果插入的是尾部（move之后） 与中部相同如果插入的是尾部（move之后），与中部相同 newnode‐>next=move‐>next; move‐>next=newnode; ; nexthead nextnext move next NULLhead next NULLnext next NULL newnode NULL 25 链表元素的插入 26 链表元素的插入 //新节点每次都要重新创建 27 链表的操作 链表的建立 定义节点结构 赋初值 next指向下 个节点链表的建立：定义节点结构，赋初值，next指向下一个节点  tail‐>next=new linker; ...; tail=tail‐>next; 链表的遍历：利用move指针从头到尾逐个节点移动链表的遍历：利用move指针从头到尾逐个节点移动 move=head; move=move‐>next;  if(move==NULL) break; 此前的链表处理函数没 if(move NULL) break; 链表的查询：与遍历类似，找到即停止 链表的删除 有考虑实参head为NULL 的情况，课后思考！链表的删除 删除头节点，head=head‐>next; delete move; 删除其他节点，ahead‐>next=move‐>next; delete move; 链表的插入 插入头节点，newnode‐>next=head; head=newnode; 插入其他节点，newnode‐>next=move‐>next;  move‐>next=newnode; 28 双向链表 单向链表的缺陷 不能通过当前位置找到前不能通过当前位置找到前 面的元素. 双向链表存储 组数据 struct linker {双向链表存储一组数据， 但有两个链 struct linker { 数据变量1; ... 数据变量N一个指向前面的元素 一个指向后面的元素 数据变量N; struct linker *ahead; struct linker *next;  个指向后面的元素 next } ahead 29 双向链表 双向链表节点删除 找到待删除节点move 然后找到待删除节点move，然后 move‐>next‐>ahead = move‐>ahead;  h dmove‐>ahead‐>next = move‐>next; delete move; move = NULL; next ahead 30 双向链表 向链表节点插入双向链表节点插入 找到节点move，在其后插入新节点newnode  d t tnewnode‐>next=move‐>next; newnode‐>ahead=move; move‐>next‐>ahead=newnode;move >next >ahead newnode; move‐>next=newnode; 必须最后处理move‐>next newnode next ahead move X 31 链表例题：猴子选大王 有N 只猴子，从1 到N 进行编号。 它们按照编号的顺时针方向，排 成一个圆圈成 个圆圈 然后从第一只猴子开始报数。第 一只猴子报的第一个数字为1，以 后每只猴子报的数字都是它前面 猴子所报的数字加1。 如果 只猴子报的数字是M 则 N=8, M=3 如果一只猴子报的数字是M，则 该猴子出列，下一只猴子重新从1  开始报数 剩下的猴子继续排成一个圆圈报 数，直到全部的猴子都出列为止。 最后 个出列的猴子胜出最后一个出列的猴子胜出。 32 链表例题：猴子选大王 33 链表例题：猴子选大王 34 链表例题：猴子选大王 35