双链表课程设计

1、课 程 设 计 报 告课程名称 数据结构 课题名称 双链表创建演示 专 业 计算机科学与技术 班 级 计算机1202班 学 号 29 姓 名 陈润同 指导教师 陈淑红 李珍辉 李杰君 2014年 6 月 16 日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 双链表创建演示 专业班级 计算机科学与技术 学生姓名 陈润同 学 号 29 指导老师 陈淑红 李珍辉 李杰君 审 批 任务书下达日期 2014 年 6 月 16 日任务完成日期 2014年 6 月 29 日课程设计报告任务书1设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌，用户利用扑

2、克牌的数字及运算符号“+”、“”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。1.1.2 迷宫探索随机生成一个迷宫图，迷宫大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择

3、二维数组来存储。数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。1.1.3 二叉树遍历演示演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访

4、问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.1.4 拓扑排序演示演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。1.1.5 图的遍历演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.1.6 双链表创建演示建立一个递增有序的双链表。功能是随机生成8个结点数据，每

5、生成一个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二演示插入过程中指针的变化，第三步显示插入后的链表结果。1.1.7公园导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。1.1.8 最小生成树算法演示随机生成一个网，并用图形展示，然后依据Prim算法或Kruskal算法求该图的最小生成树，并用图形展示相应的过程步骤。1.2 选题方案所选题目根据

6、学号确定，学号模8加1，即（学号%8+1）。如你的学号为13，则所选题目号为：13%8+1（题目6）。注意，所有的课题都要求用图形方式演示步骤和结果。1.3设计要求1.3.1 课程设计报告规范（1）需求分析a. 程序的功能。b. 输入输出的要求。（2）概要设计a. 程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b. 课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a. 采用C语言定义相关的数据类型。b. 写出各模块的类C码算法。c. 画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a

7、. 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。 （6）书写格式a. 设计报告要求用A4纸打印成册：b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录a. 源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位

8、同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3 课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排第 17 周：星期一 8：0012：00 上课 星

9、期二 14：0018：00 上机星期三 14：0018：00 上机 星期四 14：0018：00 上机第 18 周：星期一14：0018：00 上机 星期二 14：0018：00 上机 星期四 14：0018：00 上机 附：课程设计报告装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗, 三级标题用小四号宋体加粗，正文用小四号宋体;行距为22。正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序

10、的原代码，要求对程序写出必要的注释）。正文总字数要求在5000字以上（不含程序原代码）。III目录课程设计任务书I1设计内容与设计要求I2 进度安排IV课程设计报告11.需求分析1 1.1 程序的功能1 1.2 输入输出的要求12.概要设计1 2.1 主要程序功能模块图1 2.2 抽象数据类型（ADT）23详细设计3 3.1 C语言定义的相关数据类型3 3.2 主要模块的伪码算法33.2.1 建立并插入双链表的类C算法33.2.2指针变化演示类C算法43.2.3 输出已排序双链表类C代码5 3.3 画出各函数的调用关系图、主要函数的流程63.3.1 各函数的调用关系图.63.3.2 主函数ma

11、in的流程图.73.3.3 输出链表函数PrLink的流程图.73.3.4 插入指针变化函数DrawChange的流程图.74.调试分析以及设计体会11 4.1测试数据11 4.2调试分析11 4.3程序调试中遇到的问题以及解决问题的方法15 4.4课程设计过程经验教训、心得体会17.使用说明18.参考文献187.附件19课程设计报告1. 需求分析1.1 程序的功能建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二步则演示插入过程中指针的变化

12、，第三步显示插入后的双链表结果。1.2 输入输出的要求在菜单中输入数据为任意键，输入数据是由随机函数随机产生的，输出函数用图形文本显示,主要是在屏幕显示指针变化的情况和结点插入后的结果，具体输出过程为输出首先生成的结点，然后显示对已生成结点的排序，再演示出指针变化，指针以弯折的箭头表示，最后输出排序后的链表，直箭头表示双链表的前驱后继。2. 概要设计2.1 主要程序功能模块图 本程序由于仅需实现双链表的创建演示，所以程序结构比较简单，主要由三部分模块函数组成，即创建双链表,链表插入的指针变化，输出链表。创建链表指针变化输出链表主函数main() 图2.1主要程序功能模块图2.2 抽象数据类型（

13、ADT）ADT DList 数据对象：D=ai | ai1,100，i=0,8 数据关系：R=<ai-1, ai > | ai-1, aiD, i=0,8 基本操作： Init(void)操作结果：完成图形的初始化。Close(void)初始条件:图形初始化完成。操作结果：关闭图形。InitList(void)操作结果：创建双链表。PrLink(linky p,int n)初始条件：链表已存在。操作结果：插入后输出链表。DrawChange(int data,int i,int n)初始条件：链表已存在。操作结果：链表插入时的指针变化。ListInsert (DLinkList &

14、amp;L, int i, ElemType e)初始条件：链表已存在，1iListLength(L)+1。操作结果：在L中的第i个位置之前插入新数据元素e,L的长度加1。ListDelete (DLinkList &L, int i, ElemType &e)初始条件：链表已存在且非空，1iListLength(L)。操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。ListLength(DLinkList &L)初始条件：链表已存在。操作结果：返回L中数据元素个数。LocateELem (DLinkList &L, ElemType e, co

15、mpare()初始条件：链表已存在,compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位 序。若这样的数据元素不存在，则返回值为0 ListEmpty(DListLink &L)初始条件：链表已存在。操作结果：若L为空表，则返回TRUE,否则返回FALSE。ClearList(DLinkList &L)初始条件：链表已存在。操作结果：将L重置为空表。DestroyList（DLinkList &L）初始条件：链表已存在。操作结果：销毁L。 ADT DList3详细设计3.1 C语言定义的相关数据类型typedef s

16、truct Link /*双链表结点定义*/ int data; struct Link *next; struct Link *prior; int num; /*给链表加序号,为了演示时计算正确位置*/linkx,*linky;3.2 主要模块的伪码算法3.2.1 建立并插入双链表的类C算法 void InitList(void) srand(unsigned)time(NULL); 将产生的随机数字转换成字符串并输出； PrLink(head,n); /*显示只有头节点的链表*/ n+; while(n!=8) s->data=rand()%100+1; if(s->data

17、<=head->data) /*小于头结点，插在头*/ q=head->next; q->num+; /*节点数加1；*/ 显示具体插入过程； else /其他情况/ if(p=NULL) /*这个数是当前最大的数，插在尾部*/ 显示插入的具体过程； else /*随即产生的数排在表中*/ while(s!=NULL) s->num+;s=s->next; 显示插入的具体过程； 3.2.2指针变化演示类C算法void DrawChange(int data,int i,int n) 判断插入结点的位置： if(i!=-1) 不是插在头，画新结点的前驱指针线；

18、 if(i!=n-1)不是插在尾，画新结点的后继指针线；去除插入位置的后继指针线；if(i!=-1)不是插在头，画新结点前驱结点的后继指针线；去除插入位置的前驱指针线；if(i!=n-1) 不是插在尾，画新结点后继结点的前驱指针线；if(i!=n-1&&i!=-1) 既不是头指针也不是尾指针时： 画前驱指针线； 画后继指针线； 擦掉所画的指针线；3.2.3 输出已排序双链表类C代码 void PrLink(linky p,int n) while(p!=NULL) 输出随机产生的数据；if(p->prior!=NULL) 画前驱指针； if(p->next!=NUL

19、L) 画后继指针； p=p->next; 3.3 画出各函数的调用关系图、主要函数的流程3.3.1各函数的调用关系图本次课程设计由六个基本函数模块组成，依次为主函数mian(void)，图形驱动函数Init(void)，图形关闭函数Close(void)，双链表的创建函数InitList(void)，双链表的指针变化演示函数DrawChange(int data,int i,int n)以及双链表的输出显示函数PrLink(linky p,int n)。他们之间的函数调用关系为：由主函数mian(void)首先调用图形驱动函数Init(void)，以驱动图形界面的建立；接着主函数mian

20、(void)会调用双链表的创建函数InitList(void)，利用该函数，我们会得到由8个随机数据结点生成的一个双链表，其建立的过程是一个一个的结点依次产生，而后对当前双链表进行遍历，找到新生成的数据结点所需要插入的位置，然后调用双链表的指针变化演示函数DrawChange(int data,int i,int n)，对其插入过程进行显示，然后调用双链表的输出显示函数PrLink(linky p,int n)，对每次插入后的双链表进行输出显示；待完成8个数据结点的插入与演示之后，程序返回主函数mian(void)当中，由主函数mian(void)调用图形关闭函数Close(void)，整个程

21、序运行结束。如图3.1所示。 main(void)Init(void)InitList(void)Close(void)PrLink(linky p,int n)DrawChange(int data,int i,int n) 图3.1 各函数的调用关系图3.3.2主函数main（void）主要思路：由主函数mian(void)首先调用图形驱动函数Init(void)，以驱动图形界面的建立；接着主函数mian(void)会调用双链表的创建函数InitList(void)，利用该函数，我们会得到由8个随机数据结点生成的一个双链表，其建立的过程是一个一个的结点依次产生，而后对当前双链表进行遍历，找

22、到新生成的数据结点所需要插入的位置，然后调用双链表的指针变化演示函数DrawChange(int data,int i,int n)。其调用过程需要根据s->data与head->data的大小来判断，如果s->data<=head->data，表示所要插入的结点数据小于双链表的头结点数据，这时，程序将调用调用函数DrawChange(s->data,-1,n)，对其进行头部插入操作；如果s->data>head->data并且p!=NULL,表示所要插入的数据结点既不在双链表的头部也不在双链表的尾部，而是要在双链表的中间对其进行插入操作，

23、这时，程序将调用函数DrawChange(s->data,n-1,n)，对其进行双链表的中间插入操作；如果s->data<=head->data并且p=NULL，表示所要插入新的结点数据大于双链表的尾部结点数据，这时，程序将会调用函数DrawChange(s->data,q->num,n)，对其进行双链表的尾部插入操作。然后调用双链表的输出显示函数PrLink(linky p,int n)，对每次插入后的双链表进行输出显示，；待完成8个数据结点的插入与演示之后，程序返回主函数mian(void)当中，由主函数mian(void)调用图形关闭函数Close(v

24、oid)，整个程序运行结束。如图3.2所示。3.3.3输出链表函数PrLink（linky p,int n）主要思路：p开始时指向头结点，如果p!=NULL，表示当前存在数据结点，这时就需要对其进行输出，如果p->prior!=NULL，表示当前结点存在左指针，这时就需要画出他的左指针线，如果p->next!=NULL，表示当前结点存在右指针，这时就需要画出他的右指针线，之后p=p->next，表示指针移向双链表的下一个位置，直到p=NULL为之，此时表示双链表已没有下一个数据结点，所有的数据结点已经完全输出。如图3.3所示。3.3.4插入指针变化函数DrawChange（i

25、nt data,int i,int n）主要思路：该函数是画链表插入的具体过程，其中data是所要插入的数据，i为插入结点的前驱结点序号，n为当前双链表中的所有结点个数。先将所要插入结点的前驱和后继的指针线加上，在这里需要用到EasyX中的画线函数line（），然后删除新结点所要插入位置的后继指针线，这里需要用到EasyX中的画矩形函数bar()，使其来覆盖原图形中的线条图形，以达到删除指针的功能。之后对前驱指针的操作也如此进行。然后便是要擦掉插入过程的指针线，同样也用bar（）函数操作。如图3.4所示。用函数InitList(void)调用函数PrLink(p,n)s- > data

26、<=head- > datap=NULL调用函数DrawChange(s->data,n-1,n)调用函数DrawChange(s->data,-1,n)调用函数DrawChange(s->data,q->num,n)调用函数PrLink(head,n)调用函数Close(void)调用函数Init(void)开始结束 N Y Y NY 图3.2 主函数的流程图 开始函数PrLink(p,n) p!=NULLp->prior=NULL 画左指针线p->next=NULL 画右指针线 结束 Y NN 图3.3 输出链表函数PrLink()的流程图

27、开始 i!=-1bar结点的前驱指针线bar结点的前驱指针线 i!=n-1line新结点前驱结点的后继指针线line新结点的前驱指针线bar结点的后继指针线 i!=n-1line新结点后继结点的前驱指针线 (i!=n-1&&i!=-1）line前驱和后继指针线bar插入过程的指针线 结束 图3.4 插入指针变化函数流程图4.调试分析以及设计体会4.1测试数据：测试数据是由随机函数srand(unsigned)time(NULL)生成的介于1100之间的整数。4.2调试分析：进入程序界面，程序会弹出对话框，由用户进行选择操作数字，数字1表示进入程序，数字2表示退出程序。具体程序代

28、码为：InputBox(s, 10, "Please make choice: 1 Enter 2 Exit")；如图4.1所示： 图4.1 程序初始界面对话框在对话框中输入数字1后，进入程序运行界面，可以看到第一行的提示，按任意键继续；第二行是数据结点，并且已经产生第一个随机数据；第三行是双链表的插入演示过程。具体程序代码为：outtextxy(50,10,"Press any key to continue"); outtextxy(50,40,"NodeData:"); outtextxy(50,60,"DoubleL

29、inks:");如图4.2所示： 图4.2 进入程序运行界面操作将继续进行，这时出现第三个数据结点62，结点62要插在46和91这两个数据结点的中间。其过程是，先将62结点的前驱与后继指针线分别指向数据结点46和数据结点91；然后将数据结点46的后继指针指向数据结点62，同时删除46指向91的指针。如图4.3所示： 图4.3 结点在链表中间插入1操作继续进行，将结点62的后继指针指向结点91，同时去掉它的结点91到46的前驱指针。以上过程的具体程序代码为：s->next=q->next;s->prior=q;q->next->prior=s;q->

30、next=s;如图4.4所示： 图4.4 结点在链表中间插入2操作继续进行，结点的插入操作完成，形成一条新的双链表。具体程序代码为： while(p!=NULL) p=p->next;如图4.5所示: 图4.5 双链表的显示操作继续进行，出现新结点100，其按照顺序需插在双链表的最后。首先要将新结点100的前驱结点的指向结点91。如图4.6所示： 图4.6 新结点在双链表尾部插入1操作继续进行，结点91的后继指针指向新结点100。以上过程的具体代码为s->prior=q;s->next=NULL;q->next=s;如图4.7所示: 图4.7 新结点在双链表尾部插入2

31、继续操作的执行，当八个数据都插入双链表后，形成一条从小到大的双链表，如图4.8所示： 图4.8 双链表演示程序完成按任意键后退出操作的执行。4.3程序调试中遇到的问题以及解决问题的方法在编写结点插入双链表中的指针变化演示函数DrawChange时，一开始所要删除指针的位置总是找不到正确的位置。我的解决方法是，请教老师和同学，经过仔细的检查，发现原来是对所要插入结点的前驱指针和后继指针的删除顺序出现了错误，经过一番修改之后，新结点便可以正确的插入到双链表中了。如图4.9所示。在编写双链表的显示函数PrLink时，程序有时不能将当前工作状态下的所有结点显示出来。我的解决方法是，请教老师，在老师的建

32、议下，我为程序创建双链表时的创建函数InitList加上了头指针结点，之后经过修改，程序便可以正常的输出所有数据结点了。如图4.10所示。 图 4.9 指针线无法正确的删除 图 4.10 双链表无法正确显示4.4课程设计过程经验教训、心得体会在本次课程设计中，我的课题是完成双链表创建演示的程序设计。这也是我第一次利用EasyX软件在VC6.0的软件平台上做图形演示程序，对此，我感到既新鲜又有一点担心，新鲜的是我以前从没考虑过在VC6.0上也可以做出一系列的图形，例如，画圆形，画矩形，画线条等，这使我觉得很新鲜，激发了我的好奇性与渴望以最好的程序界面来完成课程设计的课题；担心的是毕竟我对C语言的

33、图形编程不是很熟悉，在课程设计的第一周心里很是担心，甚至想过用Turboc的软件平台来进行答辩，但后来经过老师和同学的热心帮助，以及自己的认真调试，我最终在VC6.0的软件平台上成功的将程序调试了出来。本次数据结构的课程设计不同于以往C语言的课程设计，给我最大的感受就是，以往的C语言编程，我只需要考虑该课程设计需要实现多少个功能，功能对应几个函数模块以及这几个函数模块之间是怎样的调用关系便可，之后便是对各个功能函数的具体实现，只要做到这些思索，程序的设计基本上就完成了；但本次数据结构的课程设计不单单只是按照C语言的课程设计方法来编程就可以完成的，它需要我对程序有更加深入与细致的了解，当然对图形

34、界面的显示与操作也要有必要的了解，所以，我在图书馆中查阅了一些关于图形界面处理方法的图书资料。在本次程序设计的过程中，遇到问题是在所难免的，但我并没有逃避问题，我积极的请教老师和同学，在老师和同学的帮助下，我成功的解决了问题，调试出了程序。在此，我要衷心的感谢陈老师以及帮助我的同学。通过本次为期两周的课程设计，加深了我对数据结构知识尤其是双链表插入部分内容的理解与记忆，提高了我的动手操作能力，使我有机会将数据结构的理论知识与实践操作可以结合起来，做到灵活运用所学的知识。同时，我也了解了一款在处理图形界面很有效率的软件，那就是EasyX，这款软件使VC6.0较好的处理图形界面成为了现实。 最后我

35、意识到作为一个计算机系的学生，正确掌握一门程序语言和数据结构的重要性，想要在程序设计上面做出成绩，必须要有扎实的编程语言基础和良好的数据结构算法知识，同时我也认识到，单靠自己的力量来死扣程序是很没有效率的，因为你会在一个死区里不停的打转，但当你请教他人的时候，很多的时候你会豁然开朗，对问题有了清晰的解决方案，所以，我们要学会善于请教他人。.使用说明本程序是演示程序，在运行后按任意键即执行演示过程，可直观的看到程序运行时双链表指针的变化情况，等待所有过程结束后出现一个笑脸图形然后再退出。当进入程序界面后，按任意键出现数据结点，当插入新结点的时候，按任意键可以显示指针变化的全过程，直到双链表满8个

36、结点的时候，按任意键输出笑脸，再按任意键退出。.参考文献1严蔚敏，吴伟民数据结构，北京：清华大学出版社，201342李春葆数据结构教程，北京：清华大学出版社，201313李春葆上机实验指导，北京：清华大学出版社，201314谭浩强. C程序设计，北京：清华大学出版社，201065 6 7.附件#include "stdio.h"#include "time.h"#include "stdlib.h"#include "graphics.h"#include "conio.h"typedef st

37、ruct Link/*双链表结点定义*/int data;struct Link *prior;struct Link *next;int num;/*给链表加序号,为了演示时计算正确位置*/linkx,*linky;void Init(void);/*图形驱动*/void Close(void);/*图形关闭*/void InitList(void);/*建立双链表,边建立边插入数据结点*/void PrLink(linky p,int n);/*每次插入后输出链表*/void DrawChange(int data,int i,int n);/*画链表插入的指针变化*/void main(

38、void)int i; char s5; Init();/*图形驱动*/ InputBox(s, 10, "Please make choice: 1 Enter 2 Exit"); sscanf(s,"%d",&i); if(i=1)InitList();/*建立双链表*/Close();else Close();/*图形关闭*/ exit(0);void InitList(void)/*建立双链表,边建立边插入数据结点*/linky head,p,q,s;int n=0;char str5; srand(unsigned)time(NULL)

39、;/*随机数发生机*/head=s=(linky)malloc(sizeof (linkx);s->data=rand()%100+1;/*随机生成100以内的数字*/ s->num=n;sprintf(str,"%d",s->data);/*将数字转换成字符串并输出*/ setfont(16,0,"宋体");/* 设置当前字体为高 16 像素的“宋体”*/ setcolor(BLUE);outtextxy(50,10,"Press any key to continue"); outtextxy(50,40,&qu

40、ot;NodeData:"); outtextxy(50,60,"DoubleLinks:"); setcolor(RED);outtextxy(155+n*35,40,str);/*显示数据*/ getch(); s->prior=NULL; s->next=NULL;PrLink(head,n);/*每次插入新数字后都显示当前链表*/ n+; while(n!=8)s=(linky)malloc(sizeof(linkx);s->data=rand()%100+1;/*随机生成1到100以内的数字*/s->num=n;sprintf(s

41、tr,"%d",s->data);/*将数字转换成字符串并输出*/setcolor(RED);outtextxy(155+n*35,40,str);getch();p=head;/*每生成一个结点，将该结点插入到有序双链表中*/if(s->data<=head->data)/*小于头结点，插在头*/DrawChange(s->data,-1,n);/*显示插入的具体过程*/s->next=head;s->prior=NULL;s->num=0;head->prior=s;head=s;q=head->next;/*

42、后面所有数的序号都加1，相当于数据后移*/while(q!=NULL)q->num+;q=q->next;else/*其他情况*/while(p!=NULL&&s->data>p->data) q=p; p=p->next;if(p=NULL)/*这个数是当前最大的数，插在尾部*/DrawChange(s->data,n-1,n);/*显示插入的具体过程*/s->prior=q;s->next=NULL;q->next=s;s->num=n;else /*结点插入位置位于两数之间，q之后插入*/s->nex

43、t=q->next;s->prior=q;q->next->prior=s;q->next=s;s->num=q->num+1;DrawChange(s->data,q->num,n);/*显示插入的具体过程*/s=s->next;while(s!=NULL)/*后面所有数的序号都加1*/s->num+;s=s->next;PrLink(head,n);/*每次插入新数据后都显示新链表*/n+;/*画链表插入的具体过程，data是要插入的数据，i为插入结点前驱结点序号，n为当前结点个数，先将前驱结点和后继之间的指针线擦除，

44、显示新结点插入过程，插入后擦除插入过程，恢复删除的前驱结点的指针线*/void DrawChange(int data,int i,int n) char str5; setcolor(BLACK);/*插入链表的新数据用黑色显示*/ sprintf(str,"%d",data); outtextxy(55+70*i+35,100+n*50,str);/*输出插入的位置*/ /bar(50+70*i+35,100+(n-1)*50-20,50+70*i+65,100+(n-1)*50+20); setcolor(BLUE); if(i!=-1) /*不是插在头，新结点的前驱

45、指针线*/ line(50+70*i+34,100+n*50,50+70*i+30,100+n*50); line(50+70*i+30,100+n*50,50+70*i+30,100+n*50-25); line(50+70*i+30,100+n*50-25,50+70*i+27,100+n*50-22); line(50+70*i+30,100+n*50-25,50+70*i+33,100+n*50-22); getch(); if(i!=n-1)/*不是插在尾，新结点的后继指针线*/ line(50+70*i+61,100+n*50,50+70*i+65,100+n*50); line(

46、50+70*i+65,100+n*50,50+70*i+65,100+n*50-25); line(50+70*i+65,100+n*50-25,50+70*i+62,100+n*50-22); line(50+70*i+65,100+n*50-25,50+70*i+68,100+n*50-22); getch(); setcolor(RED); bar(50+70*i+35,100+(n-1)*50+5,50+70*i+65,100+(n-1)*50+20);/*去除插入位置的后继指针线*/ if(i!=-1)/*不是插在头，新结点前驱结点的后继指针线*/ line(50+70*i+20,100+n*50-25,50+70*i+20,110+n*50); line(50+70*i+20,110+n*50,50+70*i+34,110+n*50); line(50+70*i+34,110+n*50,50+70*i+31,110+n*50-3); line(50+70*i+34,110+n*50,50+70*i+