数据结构课程设计-数据结构设计

上海应用技术学院课程设计报告课程名称数据结构课程设计设计题目 猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统;院系计算机科学与信息工程专业计算机科学与技术班级姓名学号_指导教师日期一. 目的与要求1. 巩固和加深对常见数据结构的理解和掌握2. 掌握基于数据结构进行算法设计的基本方法3. 掌握用高级语言实现算法的基本技能4. 掌握书写程序设计说明文档的能力5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力二. 课程设计内容说明1. 项目一(1) 对设计任务内容的概述学生成绩管理* 任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。(2) 详细设计LinkList *create()：输入学生成绩记录函数；void print(LinkList *head)：显示全部记录函数LinkList * Dele te(LinkLis t *head):删除记录函数LinkLis t *1 nser t( LinkLis t * head):插入记录函数void menu_select()： 菜单选择void ScoreManageO：函数界面(3) 程序流程图44插入学生记录(4) 程序模块及其接口描述 该程序可以分为以下几个模块：1、菜单选择：void menu_select();提供五种可以选择的操作，在 main 函数中通过 switch 语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。2、输入功能:LinkList *create();通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链 表。3、输出功能:void prin t(LinkLis t * head);通过一个while的循环控制语句，在指针p!二NULL时，完成全部学生记录的显示。 知道不满足循环语句，程序再次回到菜单选择功能界面。4、删除功能：LinkLis t *Dele te(LinkList * head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成， 如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释 放，最后完成对某个学生记录进行删除，并重新存储。5、插入功能:LinkLis t *I nser t( LinkLis t * head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生 记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。(5) 程序的输入与输出描述输入：调用LinkList *create()函数，输入学生的姓名、学号、三门功课的成 绩；输出：调用void prin t(LinkLis t *head)函数，输出学生的记录。(6) 程序测试主菜单：成绩管理系统的主界面:学生成绩记录的输入:输出学生成绩记录:学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）(7) 尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是 有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的 文件保存以及按学号、姓名等的查询也是缺少的。还有就是，对于多个学生成绩 的操作也是不够的。改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也 应修改系统，让它更为人性化、简单化，被广大用户所接受。(8) 对软件的使用说明该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输 入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不 方便性，但由于时间的缘故，无法将软件做到尽善尽美。2.项目二(1)对设计任务内容的概述各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法，将用户随机输入的一列数 按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。(2) 功能描述 该函数有以下几个功能：1) 对RO.n-l按递增有序进行直接插入排序2) 对R0.n-1按递增有序进行冒泡排序3) 对R0.n-1按递增有序进行直接选择排序4) 排序后的输出5) 调用所有排序，实现排序(3) 程序流程图(4) 详细设计void InsertSort(RecType R,int n)：对R0.n-1按递增有序进行直接插入排序 void BubbleSort(RecType R,int n)：对 R0.n-1按递增有序进行冒泡排序 void SelectSort(RecType R,int n)：对 R0.n-1按递增有序进行直接选择排 序void disp(RecType R,int n)：排序后的输出void Sort():调用所有排序，实现排序(5) 程序模块及其接口描述该程序分为五个模块:1. 输入功能：void Sort()建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数， 对关键字进行排序。2. 直接插入排序功能:void InsertSort(RecType R,int n)将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数 字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适 位置，使有序表仍然有序。3冒泡排序功能:void BubbleSort(RecType R,int n)在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法 判断是否完成排序，为了解决这一不足，可设置一个标志位exchange，将其初 始值设置为非 0，表示被排序的表是一个无序的表，每一次排序开始前设置 exchange值为0,在进行数据交换时，修改exchange为非0。在新一轮排序开 始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序； 否则进行排序。4.直接选择排序功能：void SelectSort(RecType R,int n)在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置 上的数字交换。5输出功能:void disp(RecType R,int n)(6) 程序的输入与输出描述输入：要求是 10 个为数字的关键字； 输出：排序后新的序列。(7) 程序测试输入关键字，调用各种排序函数i叮注主程序.轄丘输入您的远择CL嗚;戈 3 ? fl M 24 庙 B9|v 1 | 1直接插人推序:1冒泡推序=1 2亘接选择徘序=1青输入琳序曲关龍字W卜魏刊H9 3 2 1 56 7 8 34 55 18系树厶 理序氏的二表 成各建有退 1 2 3 4 5(8) 尚未解决的问题或改进方向改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程， 这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它 们的不同。(9) 对软件的使用说明用户只需根据提示，在键盘上输入要排序的10个关键字。3.项目三(1)对设计任务内容的概述有序表的合并要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功 能，并输出合并后的信息。(2)功能描述该程序有如下几个功能：1) 初始化顺序表2) 初始化链表3) 建立顺序表4) 尾插法建表5) 输出合并后的顺序表6) 输出合并后的单链表7) 合并顺序表8) 合并单链表9) 调用以上的函数，实现有序表的合并(3) 概要设计或程序流程图(4) 详细设计void InitList(SqList *&L):初始化顺序表void InitList1(LinkList1 *&L):初始化链表void CreateList(SqList *&L,ElemType a, int n)： 建立顺序表void CreateListR(LinkListl *&L,ElemType a, int n)： 尾插法建表 void DispList(SqList *L):输出合并后的顺序表void DispLis t1(LinkLis t1 *L)：输出合并后的单链表void UnionList(SqList *LA,SqList *LB,SqList *&LC):合并顺序表void UnionList1 (LinkList1 *LA,LinkList1 *LB,LinkList1 *&LC):合并 单链表void Union():调用以上的函数，实现有序表的合并。(5) 程序模块及其接口描述程序有以下几个模块：1) 初始化、建立顺序表2) 初始化、建立链表3) 输出合并后的表4) 合并表(6) 调试分析或程序测试有序表的合并:(7)尚未解决的问题或改进方向不足：不能重复使用程序。(8)对软件的使用说明用户只需根据界面的提示，采用对应的操作。4. 项目四(1)对设计任务内容的概述建立二叉树，层序、先序、中序、后序遍历(用递归或非递归的方法都可 以)*任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别 建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序 列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；(2)功能描述1) 建立二叉树2) 输出二叉树3) 先序遍历非递归算法： 不为空时，访问根-左-右，采用递归的方法。4) 中序遍历非递归算法： 不为空时，访问左-根-右，采用递归的方法。5) 后序遍历非递归算法： 不为空时，访问左-右-根，采用递归的方法。6) 层序遍历： 运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。7) 调用以上函数实现二叉树的各种遍历(3)概要设计或程序流程图(4)详细设计void Crea teBTNode(BTNode * & b,char *str)：建立二叉树 void DispBTNode(BTNode *b):输出二叉树void PreOrder(BTNode *b):先序遍历非递归算法void InOrder(BTNode *b):中序遍历非递归算法void PostOrder(BTNode *b):后序遍历非递归算法void LevelOrder(BTNode *b):层序遍历(5)程序模块及其接口描述(6)程序的输入与输出描述输入二叉树的按层结点值；输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序;输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序;(7) 调试分析或程序测试用户从键盘上输入要创建的二叉树结点:(8) 尚未解决的问题或改进方向改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。(9) 对软件的使用说明用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。5. 项目五(1)对设计任务内容的概述猴子选大王*任务：一堆猴子都有编号，编号是1, 2, 3 .m，这群猴子(m个)按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这 样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,n m,n为整数，nm输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子 是几号，建立一个函数来实现此功能2）需求分析或功能描述为猴子编号out,编号out二pass （pass为密码值），该猴子离圈，次数st ep+。 剩下的猴子继续次操作，直到次数step=猴子monkey时结束。3，概要设计或程序流程图输入猴子的数量和密码值N次数=猴子数Y结束编号=密码值，猴子出列，次数自增开始（ 4，详细设计或源代码说明为猴子编号out,编号out二pass（pass为密码值），该猴子离圈，次数step+。 剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数int Monkey （）实现了这一功能。（ 5 ，程序模块及其接口描述运用队列（环形队列），编号二密码值入队；为猴子编号out,编号out=pass （pass为密码值），该猴子离圈，次数step+。剩下的猴子继续次操作，直到次 数step=猴子monkey时结束。函数int Monkey （）实现了这一功能。（6）程序的输入与输出描述输入数据：输入m,n m,n为整数，nm输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子 是几号，建立一个函数来实现此功能。小-E:Sfc据结构课程设计k主程序.肛甘：疾一ji生尢壬 KKMKKKMKJfMKWMXXWWXIC wtrxw WMXW XMWW W 审盲打 MW 余百几只濮了： B思码数字：爭（7）调试分析或程序测试猴子数量8,密码值9 （猴子数密码值）统 并 系树合 理疗X的羔 f序 成答建有12 3 4ttttttttUUUUUUUUO丄0 0 0 0 0 0 03 6 4 5 2 7 8 D D INNINNINNIN（8）尚未解决的问题或改进方向不足：不能重复使用程序，如果数字大的话，输出繁琐。（9）对软件的使用说明用户只需根据软件界面的提示进行相关操作。三. 结论及体会本学期，我学会了常用数据结构：数组（连续空间），栈（先进后出），队列（先进先出），链表（指针），树（前驱、后继，根、叶子,）图（点、边），堆（特 殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存 储，常用的排序算法。在这一周里，自己用了 CFree做了一个程序，分别实现了学生成绩管理系 统、各种排序、有序表的合并、二叉树的建立及遍历以及猴子选大王，通过本次 数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、 链表等知识。在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、 图书馆查阅资料、问老师的方式，最终还是解决多数，虽然最后的程序不是很完 美，但是因为是通过自己的努力完成的，还是感觉很满意，也收获很大东西。 经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说 是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很 是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高，其实现在 想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多 心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一 些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力 去学习，就会灵活的去应用它。总之，通过这次的课程设计，我们收获匪浅，首先由衷感谢老师提供这样的 一个机会锻炼自己，感受到学来的知识不只是用来完成试卷的。一向习惯独立思 考的自己学会了积极的与别人交流，取长补短，共同进步。课程设计使自己发现 考试不是最重要的，最重要的是能运用所学的知识。在整个课程设计的学习过程 中，不再是学到知识解题，而是在实际运用时遇到什么学什么，重在把知识应用 于实际。附录 1：参考文献1 数据结构教程（第3 版），李春葆，清华大学出版社，2010 2数据结构，杨剑，清华大学出版社，2011数据结构（C语言版），严蔚敏 吴伟民，清华大学出版社，19974Data Structures Using C 数据结构（C 语言版），R Krishnamoorthy、G Indirani Kumaravel, 清华大学出版社，2009-9C+数据结构与程序设计（美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译， 清华大学出版社，20046计算机算法设计与分析（第2 版），王晓东， 电子工业出版社， 2004附录 2：部分源代码清单#include #include #include#include #include #define LEN sizeof(LinkList)#define MaxSize 50/成绩管理系统typedef struct LNode/*定义单链表结点类型*/char name10; /姓名char num10; /学号int score3;struct LNode *next; LinkList;LinkList *init()return NULL;/*返回空指针*/LinkList *create() int i,s,k;int j=0;LinkList *head=NULL,*p; /* 定义函数.此函数带回一个指向链表头的指针 */system(cls);printf(n 请输入您想输入的学生个数：);scanf(%d,&k);for(j=0;jnum);printf(输入姓名:);scanf(%s,p-name);printf(请分别输入语文、数学、英语的分数d scoresn,3);/*开始输入*/for(i=0;iscorei);if(p-scoreiscorei100) /*确保成绩在 0100 之间*/ printf(Data error,please enter again.n);while(p-scoreiscorei100);p-next=head;/*将头结点做为新输入结点的后继结点*/head=p;/*新输入结点为新的头结点*/return(head);/* 显示全部记录函数*/void print(LinkList *head)LinkList *p;system(cls);p=head;/*初值为头指针*/ j*X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* *X* I 1 v iOKinrTi ti不不不不不不不不不不不不不不不不不不不不不不不不ink iqt不不不不不不不不不不不不不printf(n);printf(| 学号 | 姓名 | 语文 | 数学 | 英语 | n);printf(n);while(p!=NULL)printf(| %4s | %-4s | %3d | %3d | %3d |n, p-num,p-name,p-score0,p-score1,p-score2);p=p-next;n);printf(printf(*END*n);/*删除记录函数*/LinkList *Delete(LinkList *head)LinkList *pl,*p2; /*pl为查找到要删除的结点指针，p2为其前驱指针*/char c,s6;/*s用来存放学号,c用来输入字母*/system(cls);printf（请输入要删除的学生的学号：）;scanf(%s,s);pl=p2=head;/*给pl和p2赋初值头指针*/while(strcmp(pl-num,s) & pl != NULL)/*当记录的学号不是要找的，或指针不为空时*/ p2=pl;/*将pl指针值赋给p2作为pl的前驱指针*/p1=p1-next;/*将 p1 指针指向下一条记录*/if(strcmp(p1-num,s)=0)/*学号找到了*/printf(*FOUND*n);n);printf(printf(| 学号 | 姓名 | 语文 | 数学 | 英语 |n);n);printf(printf(| %4s |%4s | %3d | %3d | %3d|n,p1-num,p1-name,p1-score0,p1-score1,p1-score2);n);printf( JX 11、k T I fOK!nrri 不不不不不不不不不不不不不不不不不不不不不不不不不不” | i 不不不不不不不不不不不不不不不不不不不不不不不不不不x）*printf（您确定要删除该学生的记录吗Y/N ?）; /*提示是否要删除，输入Y删除,N则退出*/for(;)*/scanf(%c,&c);if(c=n|c=N) break;if(c=y|c=Y)if(p1=head)head=p1-next; elsep2-next=p1-next;/*如果不删除,则跳出本循环*/*若pl=head,说明被删结点是首结点/*把第二个结点地址赋予 head*/free（pl）;/*否则将一下结点地址赋给前一结点地址*/printf（n学号为%s的学生记录已被删除.n,s）;break;/*删除后就跳出循环*/elseprintf(n找不到学号为s的学生记录.n,s); /*找不到该结点*/ return(head);/插入LinkList *Insert(LinkList *head)int k;/在表中第 k 个位置插入printf(请输入插入的位置：)； scanf(%d,&k);int j=0,i=0;LinkList *pl,*p2; /*p1为查找到要删除的结点指针，p2为其前驱指针*/ char N10,s10;/*s10用来存放姓名,N10用来存放学号*/int score3;system(cls);printf(输入学号:)；scanf(%s,N);printf(输入姓名:)；scanf(%s,s);printf(请分别输入语文、数学、英语的分数d scoresn,3);/*开始输入*/ for(i=0;i3;i+)/*3 门课程循环3 次*/do printf(score%d:,i+1); scanf(%d,&scorei);if(scorei100) /*确保成绩在0100之间*/ printf(Data error,please enter again.n);while(scorei100);p1=head;/*给 p1 赋初值头指针*/while(jnext;/*将 p1 指针指向下一条记录*/if(p1=NULL) return 0;else p2=(LinkList *)malloc(sizeof(LinkList);strcpy(p2-num,N);strcpy(p2-name,s);for(i=0;iscorei=scorei;p2-next=p1-next;p1-next=p2;void menu_select() printf(nnn);. J X 11 I f XT TWT Tf T t(彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、 -*-printf(tWelcome ton);printf(tThe student score manage systemn);printf(*MENU*n);printf(ttl.输入学生记录n);/*输入学生成绩记录*/printf(tt2.输出学生记录n);/*显示*/printf(tt3.删除学生记录n);/*删除*/*插入*/printf（tt4.插入一个新的学生记录n）;printf(tt5.退出n);/*退出 */*主函数界面*/void ScoreManage() LinkList *head,New;int i,n;head=init();/*链表初始化,使 head 的值为 NULL*/menu_select();doprintf(ntt 输入您的选择(15):); scanf(%d,&n);while(n5);for(;)/*循环无限次*/ switch(n)case 1:head=create();break;case 2:print(head);break;case 3:head=Delete(head);break;case 4:head=Insert(head);break;case 5:return;/*如菜单返回值为 9 则程序结束*/menu_select();printf(nttt 输入您的选择(15):);scanf(%d,&n);/ /Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki Ki/ /彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、/各种排序typedef int KeyType;/*定义关键字类型*/ typedef char InfoType10;typedef struct/*记录类型*/KeyType key; /*关键字项*/InfoType data;/*其他数据项,类型为 InfoType*/ RecType;/* 排序的记录类型定义 */ void InsertSort(RecType R,int n) /*对 R0.n-l按递增有序进行直接插入排序*/int i,j;RecType tmp;for (i=l;i=0 & tmp.keyRj.key)Rj+1=Rj； /*将关键字大于Ri.key的记录后移*/j-;Rj+1=tmp；/*在 j+1 处插入 Ri*/void BubbleSort(RecType R,int n) int i,j,exchange;RecType tmp; for(i=0;ii;j-) if(Rj.keyRj-1.key) tmp=Rj;Rj=Rj-1;Rj-1=tmp; exchange=1;if(exchange=0) return ;void SelectSort(RecType R,int n) int i,j,k;RecType tmp; for(i=0;in-1;i+) k=i;for(j=i+1;jn;j+) if(Rj.keyRk.key) k=j;if(k!=i) tmp=Ri;Ri=Rk;Rk=tmp;void disp(RecType R,int n) int i;for (i=0;in;i+)printf(%d ,Ri.key);void Sort()int i,n=10,k;RecType RMaxSize;KeyType a10;printf(“请输入排序的关键字(10个数字)n);for (i=0;in;i+)scanf(%d,&ai);for (i=0;idata=ch;p-lchild=p-rchild=NULL;if (b=NULL) /*p 为二叉树的根 结点*/b=p;else/*已建立二叉树根结点*/switch(k)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break; j+; ch=strj;void DispBTNode(BTNode *b)if (b!=NULL) printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL) printf();/* 有孩子结点时才输出 (*/DispBTNode(b-lchild);/*递归处理左子树*/if (b-rchild!=NULL) printf(,); /*有右孩子结点时才输出,*/DispBTNode(b-rchild);/*递归处理右子树*/printf();/*有孩子结点时才输出)*/先序遍历非递归算法 void PreOrder(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if(b!=NULL)top+; Sttop=b; while(top-1) p=Sttop;top-; printf(%c,p-data); if(p-rchild!=NULL) top+;Sttop=p-rchild; if(p-lchild!=NULL) top+;Sttop=p-lchild;printf(%c,b);printf(n);/中序遍历非递归算法 void InOrder(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if(b!=NULL)p=b;while(top-1|p!=NULL)while(p!=NULL)top+;Sttop=p; p=p-lchild;if(top-1)p=Sttop;top-; printf(%c,p-data); p=p-rchild; printf(n); /后序遍历非递归算法 void PostOrder(BTNode *b)BTNode *StMaxSize,*p; int flag,top=-1;if(b!=NULL)dowhile(b!=NULL)top+;Sttop=b;b=b-lchild;p=NULL;flag=1;while(top!=-1&flag)b=Sttop;if(b-rchild=p)printf(%c,b-data);top-;p=b;elseb=b-rchild;flag=0;while(top!=-1);printf(n);/层序遍历void LevelOrder(BTNode *b) BTNode *p;BTNode *quMaxSize;int front,rear;front=rear=-1;rear+;qurear=b;while(front!=rear) front=(front+1)%MaxSize; p=qufront;printf(%c,p-data);if(p-lchild!=NULL) rear=(rear+1)%MaxSize; qurear=p-lchild;if(p-rchild!=NULL) rear=(rear+1)%MaxSize; qurear=p-rchild;void BTtree()BTNode *b;char str100;printf(输入你要建立二叉树的结点：);scanf(%s,str);CreateBTNode(b,str);printf(nn 建立二叉树为：)；DispBTNode(b);printf(nn二叉树b的先序遍历序列”); PreOrder(b);printf(nn二叉树b的中序遍历序列”);InOrder(b);printf(nn二叉树b的后序遍历序列”); PostOrder(b);printf(nn二叉树b的层次遍历序列”);LevelOrder(b);printf(nn);/ / /彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、彳、/有序表的合并 typedef char ElemType;typedef struct/*存放顺序表的长度*/*顺序表的类型定义*/*定义单链表结点类型*/ ElemType dataMaxSize;/*存放顺序表元素*/int length; SqList;typedef struct LNode1ElemType data;struct LNode1 *next;/*指向后继结点*/ LinkList1;void InitList(SqList *&L)L=(SqList *)malloc(sizeof(SqList); /*分配存放线性表的空间*/ L-length=0;void InitList1(LinkList1 *&L)L=(LinkList1 *)malloc(sizeof(LinkList1);/*创建头结点*/L-next=NULL;void CreateList(SqList *&L,ElemType a,int n)/*建立顺序表*/int i;for (i=0;idatai=ai;L-length=n;void CreateListR(LinkList1 *&L,ElemType a,int n) /*尾插法建立单链表*/LinkList1 *s,*r;int i;L=(LinkList1 *)malloc(sizeof(LinkList1);/*创建头结点*/L-next=NULL;r=L; /*r 始终指向终端结点,开始时指向头结点*/ for (i=0;idata=ai;r-next=s;/*将*$ 插入*r 之后*/r=s;r-next=NULL;/*终端结点 next 域置为 NULL*/void DispList(SqList *L)int i;if (L-length=0) return;for (i=0;ilength;i+) printf(%c ,L-datai);printf(n);void DispListl(LinkListl *L)LinkListl *p=L-next;while (p!=NULL) printf(%c ,p-data);p=p-next;printf(n);/顺序表存放有序表void UnionList(SqList *LA,SqList *LB,SqList *&LC)int i=0,j=0,k=0; /*i、j、k 分别作为 LA、LB、LC 的下标*/LC=(SqList *)malloc(sizeof(SqList);LC-length=0;while (ilength & jlength)if (LA-dataidataj)LC-datak=LA-datai;i+;k+;else /*LA-dataiLB-dataj*/LC-datak=LB-dataj;j+;k+;while (ilength)/*LA 尚未扫描完,将其余元素插入 LC 中*/LC-datak=LA-datai;i+;k+;while (jlength) /*LB 尚未扫描完,将其余元素插入 LC 中*/LC-datak=LB-dataj;j+;k+;LC-length=k;/单链表存放有序表void UnionList1(LinkList1 *LA,LinkList1 *LB,LinkList1 *&LC)LinkList1 *pa=LA-next,*pb=LB-next,*pc,*s;LC=(LinkList1 *)malloc(sizeof(LinkList1);/*创建 LC 的头结点*/pc=LC;/*pc始终指向LC的最后一个结点*/while (pa!=NULL & pb!=NULL)if (pa-datadata)s=(LinkListl *)malloc(sizeof(LinkListl);/*复制*pa 结点*/ s-data=pa-data;pc-next=s;pc=s;/*采用尾插法将*s插入到LC的最后*/pa=pa-next; elses=(LinkList1 *)malloc(sizeof(LinkList1);/*复制*pb 结点*/ s-data=pa-data;pc-next=s;pc=s;/*采用尾插法将*s插入到LC的最后*/pa=pa-next;while (pa!=NULL)s=(LinkListl *)malloc(sizeof(LinkListl); /*复制*pa 结点*/ s-data=pa-data;pc-next=s;pc=s;/*采用尾插法将*s插入到LC的最后*/pa=pa-next;while (pb!=NULL)s=(LinkList1 *)malloc(sizeof(LinkList1); /*复制*pa 结点*/ s-data=pb-data;pc-next=s;pc=s;/*采用尾插法将*s插入到LC的最后*/pb=pb-next;pc-next=NULL;void Union()SqList *L1,*L2,*L3;LinkList1 *L4,*L5,*L6;ElemType a5;ElemType b5;printf(a=:);scanf(%s,a); printf(b=:);scanf(%s,b);printf(顺序表存放有序表的合并n);InitList(L1);InitList(L2);InitList(L3);CreateList(L1,a,3);printf(L1:);DispList(L1);CreateList(L2,b,4);printf(L2:);DispList(L2);printf(“ 归并 n);UnionList(L1,L2,L3);printf(L3:);DispList(L3);printf(单链表存放有序表的合并n);InitList1(L4);InitList1(L5);InitList1(L6);CreateListR(L4,a,3);printf(L4:);DispList1(L4);CreateListR(L5,b,4);printf(L5:);DispList1(L5);printf(归并 n);