循环链表实例(猴子选大王).ppt

1 循环链表 2 循环链表 例 猴子选大王 n只猴子围成一圈 顺时针方向从1到n编号 之后从1号开始沿顺时针方向让猴子从1 2 m依次报数 凡报到m的猴子 都让其出圈 取消候选资格 然后不停地按顺时针方向逐一让报出m者出圈 最后剩下一个就是猴王 3 起始位置 猴王 1 2 3 4 5 6 7 8 3 6 1 5 2 8 4 猴子被淘汰的顺序 演示 n 8 m 3 4 说明 如图1所示有8只猴子围成一圈 m 3 从1 猴的位置开始 顺时针1至3报数 第一个出圈的是3 第二个出圈的是6 第3个出圈的是1 第4个出圈的是5 第5个是2 第6个是8 第7个是4 最后剩下一个是7 它就是猴王 我们用循环链表来模拟这个选择过程 5 1 定义一个名为mon的结构structmon intnum 整数 表示猴子的编号structmon next 指针 指向相邻的下一只猴子 2 将链表的头指针head定义为全局变量 structmon head 3 主函数用键盘输入猴子数n 输入数m 调用函数create建立一个循环链表 模拟众猴围成一圈的情况 该函数的实参为n 调用函数select 模拟1至m报数 让n 1只猴子逐一出列的过程 即在具有n个结点的循环链表按报数m删除结点的过程 该函数的实参为m 最后输出猴王的编号 6 4 建立循环链表的函数create intnn 其中nn为形式参数 要从编号1到编号nn 思路是 1 先做第1个结点 让其中的数据域p num赋值为1 让指针域赋值为null 之后让链头指针head指向第1个结点 利用指针q记住这个结点 以便让指针p去生成下面的结点 2 利用一个计数循环结构 做出第2个结点到第nn个结点 并将相邻结点一个接一个链接到一起 3 最后一个结点要和头结点用下一语句链接到一起tail q tail next head head tail q 7 5 删结点的函数select intmm mm为形式参数 从1至m报数 凡报到mm者删除其所在的结点 设计两个指针p和q 一开始让q指向链表的尾部q tail 让p指向q的下一个结点 开始时让p指向1 猴所在的结点 用一个累加器x 初始时x 0 从1 猴所在结点开始让x x 1 1 如果mm是1的话 1 猴所在的p结点就要被删除 有三条语句printf 被删掉的猴子号为 d号 n p num q next p next free p head tail q p 演示 8 这里free p 是释放p结点所占用的内存空间的语句 如果mm不是1而是3 程序会在do while循环中 让x加两次1 q和p一起移动两次 p指向3 所在结点 q指向2 所在结点 之后仍然用上述三条语句删去3 所在的结点 head q p q p p q 演示 9 这个do while循环的退出条件是q q next 即当只剩下一个结点时才退出循环 当然猴王非其莫属了 这时 让头指针head指向q head是全局变量 在主程序最后输出猴王时要用head num 参考程序如下 head q 10 include 预编译命令 include 内存空间分配 definenull0 定义空指针常量 定义常量 表示结构长度 defineLENsizeof structmon structmon 结构声明 intnum 整型数 用于记录猴子号structmon next mon结构指针 structmon head tail mon结构指针 全局变量 11 voidcreate intnn 被调用函数 函数体开始inti 整型变量i 用于计数structmon p q 声明mon结构指针p q 为p分配内存空间p structmon malloc LEN p num 1 初始化p结点num域为1p next null 初始化p结点next域为空head p 链表头指针head赋值为pq p q赋值为p 12 for i 2 inum i 初始化p结点num域为i 表示猴子号q next p 将p结点加到链表尾部q p 让q指向链表尾部结点p next null 链表尾部指向空 循环体结束tail q 链表尾tail next head 链表尾部指向链表头 形成循环链表 函数体结束 13 被调用函数select mm表示结点删除间隔voidselect intmm 函数体开始intx 0 声明整型值x 并初始化为0structmon p q 声明结构指针p qq tail q赋值为tail 指向循环链表尾部do 直到型循环 用于循环删除指定间隔的结点 循环体开始p q next p赋值为q相邻的下一个结点x x 1 x加1if x mm 0 x是否整除mm 表示是否跳过指定间隔 输出被删掉的猴子号printf 被删掉的猴子号为 d号 n p num q next p next 删除此结点free p 释放空间 elseq p q指向相邻的下一个结点p while q q next 剩余结点数不为1 则继续循环head q head指向结点q q为链表中剩余一个结点 函数体结束 14 voidmain 主函数开始 函数体开始intn m 声明整型变量n mhead null 初始化head为空printf 请输入猴子数 n 提示信息scanf d 输出猴王 函数体结束