链表的基本概念.pptVIP

// 第三种情形，循环地查找正确的插入位置 q = head; p = head-next; while(p != NULL) { if(pNode-Weight = p-Weight) break; else { q = p; p = p-next; } } // 将pNode结点插入在正确的位置(q和p之间) pNode-next = p; q-next = pNode; } while(p != NULL) { if(pNode-Weight = p-Weight) break; else { q = p; p = p-next; } } 如果新结点的Weight大于所有结点？ 在这种情形下，当循环语句结束后，指针q是 指向链表的尾结点，而指针 p = NULL。 5 10 NULL 17 NULL 15 head pNode q 插入结点： pNode-next = p; q-next = pNode; p NULL NULL 6. 链表的释放 对于静态链表，它们所占用的内存空间是由系统自动来分配和释放的； 对于动态链表，必须由程序员自己来进行内存的分配与释放。 void Destroy( ) { struct Train_tag *p, *q; p = head; while(p != NULL) { q = p; p = p-next; free(q); } } head DX11089 玩具 5吨 从上海 到深圳 CY20011 电饭锅 8吨 从上海 到湖南 CZ21026 苹果 8吨 从山东 到福建 p q p q p q head = NULL; 9.4.3 环形链表 环形链表：一种特殊的链表，其尾结点的 next指针，又指向了链表的首结点，从而形 成了一个圆环。 从环形链表的任何一个结点出发，都可以遍 历整个的链表。 学校给高一（三）班分配了一个名额，去参加奥运会的开幕式。每个人都争着要去，可是名额只有一个，怎么办？班长想出了一个办法，让班上的所有同学围成一圈，按照顺时针方向进行编号。然后随便选定一个数m，并且从1号同学开始按照顺时针方向依次报数，1, 2…m，凡报到m的同学，都要主动退出圈子。然后不停地按顺时针方向逐一让报出m者出圈，最后剩下的那个人就是去参加开幕式的人。 问题描述： 1 2 3 4 5 6 7 8 3 6 1 5 2 8 4 退出圈子的顺序： 演示：n=8, m=3 起始位置 幸运儿！ 定义一个名为STUDENT的结构体类型 struct STUDENT{ int number; // 表示同学的编号 struct STUDENT *next; // 指向下一位同学} struct STUDENT *head, *tail, *p, *prev; int n, m, i, j; 数据结构 模块1：输入学生的个数 n 和不吉利的数字m, 然后验证它们的有效性； 模块2：创建一个环形链表，模拟众同学围成 一圈的情形； 模块3：进入循环淘汰环节，模拟从1到m报数, 让n-1个同学逐一退出圈子的过程； 模块4：输出结果。 基本思路 模块2，创建环形链表 （1）动态地为每一个结点分配内存空间，并 顺序地进行编号； （2）把各个结点按照编号顺序链接成一条环 形链表； （3）用head指向链表的第一个结点，用 tail