数据结构课程设计(附代码)-数据结构设计Word版

整理为word格式整理为word格式整理为word格式上海应用技术学院课程设计报告课程名称《数据结构课程设计》设计题目猴子选大王；建立二叉树；各种排序；有序表的合并；成绩管理系统；院系计算机科学与信息工程专业计算机科学与技术班级姓名学号指导教师日期目的与要求巩固和加深对常见数据结构的理解和掌握掌握基于数据结构进行算法设计的基本方法掌握用高级语言实现算法的基本技能掌握书写程序设计说明文档的能力提高运用数据结构知识及高级语言解决非数值实际问题的能力课程设计内容说明项目一对设计任务内容的概述学生成绩管理**任务：要求实现对学生资料的录入、浏览、插入和删除等功能。输入：设学生成绩以记录形式存储，每个学生记录包含的信息有：学号和各门课程的成绩，设学生成绩至少3门以上。存储结构：采用线性链式结构。详细设计LinkList*create()：输入学生成绩记录函数；voidprint(LinkList*head)：显示全部记录函数LinkList*Delete(LinkList*head)：删除记录函数LinkList*Insert(LinkList*head)：插入记录函数voidmenu_select()：菜单选择voidScoreManage()：函数界面程序流程图整理为word格式整理为word格式整理为word格式3．3．删除学生记录4．插入学生记录1．输入学生记录输入n（0<n<6）主界面2．输出学生记录退出学生成绩管理系统5．退出判断nn=5n=1、2、3、4程序模块及其接口描述该程序可以分为以下几个模块：1、菜单选择：voidmenu_select();提供五种可以选择的操作，在main函数中通过switch语句调用菜单menu_select()函数，进入不同的功能函数中完成相关操作。2、输入功能：LinkList*create();通过一个for循环语句的控制，可以一次完成无数条记录的输入。并将其存入链表。整理为word格式整理为word格式整理为word格式3、输出功能：voidprint(LinkList*head);通过一个while的循环控制语句，在指针p!=NULL时，完成全部学生记录的显示。知道不满足循环语句，程序再次回到菜单选择功能界面。4、删除功能：LinkList*Delete(LinkList*head);按想要删除的学生的学号首先进行查找，通过指针所指向结点的下移来完成，如果找到该记录，则完成前后结点的连接，同时对以查找到的结点进行空间的释放，最后完成对某个学生记录进行删除，并重新存储。5、插入功能：LinkList*Insert(LinkList*head)；输入你想插入的位置，通过指针所指向结点的下移，找到该位置，将该新的学生记录插入到该结点，并对该结点后面的指针下移。链表长度加一，重新存储。程序的输入与输出描述输入：调用LinkList*create()函数，输入学生的姓名、学号、三门功课的成绩；输出：调用voidprint(LinkList*head)函数，输出学生的记录。程序测试主菜单：整理为word格式整理为word格式整理为word格式成绩管理系统的主界面：学生成绩记录的输入：输出学生成绩记录：整理为word格式整理为word格式整理为word格式学生成绩记录的删除（删除学号是1101的学生记录）插入新的学生成绩记录（插入学号为1103的学生记录）整理为word格式整理为word格式整理为word格式尚未解决的问题或改进方向尚未解决的问题：该成绩管理系统还存在不少缺陷，而且它提供的功能也是有限的，只能实现学生成绩的输入、输出、删除、插入。对于，学生成绩记录的文件保存以及按学号、姓名等的查询也是缺少的。还有就是，对于多个学生成绩的操作也是不够的。改进的方向：在时间许可的条件下，尽量的完善该系统的各种功能，同时也应修改系统，让它更为人性化、简单化，被广大用户所接受。对软件的使用说明该软件是属于比较低级的软件，只是包含了课程设计的要求的几个功能：输入、输出、删除、插入。所以用户在使用的过程中肯定会受到一定的局限性、不方便性，但由于时间的缘故，无法将软件做到尽善尽美。项目二对设计任务内容的概述各种排序任务：用程序实现插入法排序、选择法排序、起泡法改进算法排序；利用插入排序、选择法排序和冒泡法的改进算法,将用户随机输入的一列数按递增的顺序排好。输入的数据形式为任何一个正整数，大小不限。输出的形式：数字大小逐个递增的数列。功能描述整理为word格式整理为word格式整理为word格式该函数有以下几个功能：对R[0..n-1]按递增有序进行直接插入排序对R[0..n-1]按递增有序进行冒泡排序对R[0..n-1]按递增有序进行直接选择排序排序后的输出5)调用所有排序，实现排序程序流程图直接插入排序InsertSort()直接插入排序InsertSort()退出排序Sort（）直接选择排序SelectSort()冒泡排序BubbleSort()详细设计voidInsertSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行直接插入排序voidBubbleSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行冒泡排序voidSelectSort(RecTypeR[],intn)：对R[0..n-1]按递增有序进行直接选择排序voiddisp(RecTypeR[],intn)：排序后的输出voidSort()：调用所有排序，实现排序整理为word格式整理为word格式整理为word格式程序模块及其接口描述该程序分为五个模块:1.输入功能：voidSort()建立一个数组存放用户在键盘上输入的关键字，在分别调用各种排序的函数，对关键字进行排序。2.直接插入排序功能：voidInsertSort(RecTypeR[],intn)将后一个数与前一个数比较，将其插入到第一个比它大的大的数前面，其余数字往后移一个位置。每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。3.冒泡排序功能：voidBubbleSort(RecTypeR[],intn)在排序过程中，执行完最后的排序后，虽然数据已全部排序完备，但程序无法判断是否完成排序，为了解决这一不足，可设置一个标志位exchange，将其初始值设置为非0，表示被排序的表是一个无序的表，每一次排序开始前设置exchange值为0，在进行数据交换时，修改exchange为非0。在新一轮排序开始时，检查此标志，若此标志为0，表示上一次没有做过交换数据，则结束排序；否则进行排序。4.直接选择排序功能：voidSelectSort(RecTypeR[],intn)在无序区里找最小的数，第i小的数字放在第i个位置上，与原来第i个位置上的数字交换。5.输出功能：voiddisp(RecTypeR[],intn)程序的输入与输出描述输入：要求是10个为数字的关键字；输出：排序后新的序列。程序测试输入关键字，调用各种排序函数整理为word格式整理为word格式整理为word格式尚未解决的问题或改进方向改进方向：虽然给出了它的各种排序的结果，但是没有它的箱子过程，这是我的改进的方向，希望能将每种排序的过程也能展示给用户，来体现它们的不同。对软件的使用说明用户只需根据提示，在键盘上输入要排序的10个关键字。项目三对设计任务内容的概述有序表的合并要求输入有序表的数据，利用顺序表和链表结构分布完成两个有序表合并功能，并输出合并后的信息。功能描述该程序有如下几个功能：初始化顺序表初始化链表建立顺序表尾插法建表输出合并后的顺序表输出合并后的单链表合并顺序表合并单链表整理为word格式整理为word格式整理为word格式调用以上的函数，实现有序表的合并概要设计或程序流程图开始开始初始化链表初始化顺序表初始化链表初始化顺序表建立顺序表尾插法建表建立顺序表尾插法建表合并顺序表合并单链表合并顺序表合并单链表输出输出结束结束详细设计voidInitList(SqList*&L)：初始化顺序表voidInitList1(LinkList1*&L)：初始化链表voidCreateList(SqList*&L,ElemTypea[],intn)：建立顺序表voidCreateListR(LinkList1*&L,ElemTypea[],intn)：尾插法建表voidDispList(SqList*L)：输出合并后的顺序表voidDispList1(LinkList1*L)：输出合并后的单链表voidUnionList(SqList*LA,SqList*LB,SqList*&LC)：合并顺序表voidUnionList1(LinkList1*LA,LinkList1*LB,LinkList1*&LC)：合并单链表voidUnion()：调用以上的函数，实现有序表的合并。程序模块及其接口描述程序有以下几个模块：初始化、建立顺序表初始化、建立链表整理为word格式整理为word格式整理为word格式输出合并后的表合并表调试分析或程序测试有序表的合并：尚未解决的问题或改进方向不足：不能重复使用程序。对软件的使用说明用户只需根据界面的提示，采用对应的操作。4．项目四(1)对设计任务内容的概述建立二叉树，层序、先序、中序、后序遍历（用递归或非递归的方法都可以）**任务：要求能够输入树的各个结点，并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数；(2)功能描述建立二叉树输出二叉树先序遍历非递归算法：整理为word格式整理为word格式整理为word格式不为空时，访问根--左--右，采用递归的方法。中序遍历非递归算法：不为空时，访问左--根--右，采用递归的方法。后序遍历非递归算法：不为空时，访问左--右--根，采用递归的方法。层序遍历：运用队列，队列不空时，有左孩子将其入队，有右孩子将其入队，同时出队。调用以上函数实现二叉树的各种遍历(3)概要设计或程序流程图开始开始输入二叉树的按层结点值输入二叉树的按层结点值层次遍历后序遍历中序遍历先序遍历层次遍历后序遍历中序遍历先序遍历结束结束(4)详细设计voidCreateBTNode(BTNode*&b,char*str)：建立二叉树voidDispBTNode(BTNode*b)：输出二叉树voidPreOrder(BTNode*b)：先序遍历非递归算法voidInOrder(BTNode*b)：中序遍历非递归算法voidPostOrder(BTNode*b)：后序遍历非递归算法voidLevelOrder(BTNode*b)：层序遍历(5)程序模块及其接口描述(6)程序的输入与输出描述输入二叉树的按层结点值；整理为word格式整理为word格式整理为word格式输出二叉树先序遍历访问结点的顺序；输出二叉树中序遍历访问结点的顺序；输出二叉树后序遍历访问结点的顺序；输出二叉树层次遍历访问结点的顺序；(7)调试分析或程序测试用户从键盘上输入要创建的二叉树结点：(8)尚未解决的问题或改进方向改进方向：希望能将系统改进的更为人性化，让界面更舒适，操作更简单。(9)对软件的使用说明用户只需按照界面的提示，采取相应的措施，到时界面会提醒用户键盘输入。5．项目五（1）对设计任务内容的概述猴子选大王**任务：一堆猴子都有编号，编号是1，2，3...m,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。要求：输入数据：输入m,nm,n为整数，n<m输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能整理为word格式整理为word格式整理为word格式（2）需求分析或功能描述为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。（3）概要设计或程序流程图开始开始输入猴子的数量和密码值输入猴子的数量和密码值编号=密码值，猴子出列，次数自增编号=密码值，猴子出列，次数自增NN次数=猴子数次数=猴子数YY结束结束（4）详细设计或源代码说明为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数intMonkey()实现了这一功能。（5）程序模块及其接口描述运用队列（环形队列），编号=密码值入队；为猴子编号out，编号out=pass（pass为密码值），该猴子离圈，次数step++。剩下的猴子继续次操作，直到次数step=猴子monkey时结束。函数intMonkey()实现了这一功能。整理为word格式整理为word格式整理为word格式（6）程序的输入与输出描述输入数据：输入m,nm,n为整数，n<m输出形式：中文提示按照m个猴子，数n个数的方法，输出为大王的猴子是几号，建立一个函数来实现此功能。（7）调试分析或程序测试猴子数量8,密码值9（猴子数>密码值）（8）尚未解决的问题或改进方向不足：不能重复使用程序，如果数字大的话，输出繁琐。（9）对软件的使用说明用户只需根据软件界面的提示进行相关操作。结论及体会本学期，我学会了常用数据结构：数组（连续空间），栈（先进后出），队列（先进先出），链表（指针），树（前驱、后继，根、叶子），图（点、边），堆（特殊的树，根节点的值最大或最小）还有线性表存储结构：顺序存储结构和链式存储，常用的排序算法。在这一周里，自己用了C—Free做了一个程序，分别实现了学生成绩管理系统、各种排序、有序表的合并、二叉树的建立及遍历以及猴子选大王，通过本次数据结构课程设计，我学习了很多课上没弄懂的动西，巩固了关于二叉树、栈、链表等知识。整理为word格式整理为word格式整理为word格式在设计程序时，虽然很用心的做，但还是遇到种种难题，通过上网查找资料、图书馆查阅资料、问老师的方式，最终还是解决多数，虽然最后的程序不是很完美，但是因为是通过自己的努力完成的，还是感觉很满意，也收获很大东西。经过了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开心。在这一段努力学习的过程中，我的编程设计有了明显的提高，其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格式。只要努力去学习，就会灵活的去应用它。总之，通过这次的课程设计，我们收获匪浅，首先由衷感谢老师提供这样的一个机会锻炼自己，感受到学来的知识不只是用来完成试卷的。一向习惯独立思考的自己学会了积极的与别人交流，取长补短，共同进步。课程设计使自己发现考试不是最重要的，最重要的是能运用所学的知识。在整个课程设计的学习过程中，不再是学到知识解题，而是在实际运用时遇到什么学什么，重在把知识应用于实际。附录1：参考文献[1]《数据结构教程（第3版）》，李春葆，清华大学出版社，2010[2]《数据结构》，杨剑，清华大学出版社，2011[3]《数据结构(C语言版)》，严蔚敏吴伟民，清华大学出版社，1997[4]《DataStructuresUsingC数据结构（C语言版）》，RKrishnamoorthy、GIndiraniKumaravel，清华大学出版社，2009-9[5]《C++数据结构与程序设计（美）RobertL.Kruse/AlexanderJ.Ryba著/钱丽萍译》，清华大学出版社，2004[6]《计算机算法设计与分析（第2版）》，王晓东，电子工业出版社，2004附录2：部分源代码清单#include<stdio.h>#include<malloc.h>#include<string.h>#include<iostream>#include<stdlib.h>整理为word格式整理为word格式整理为word格式#defineLENsizeof(LinkList)#defineMaxSize50//************************************************************//成绩管理系统typedefstructLNode /*定义单链表结点类型*/{ charname[10]; //姓名 charnum[10]; //学号 intscore[3];structLNode*next;}LinkList;LinkList*init(){ returnNULL;/*返回空指针*/}LinkList*create(){ inti,s,k; intj=0; LinkList*head=NULL,*p;/*定义函数.此函数带回一个指向链表头的指针*/ system("cls"); printf("\n请输入您想输入的学生个数："); scanf("%d",&k); for(j=0;j<k;j++) { p=(LinkList*)malloc(LEN);/*开辟一个新的单元*/整理为word格式整理为word格式整理为word格式 if(p==NULL)/*如果指针p为空*/ { printf("\n输出内存溢出.");/*输出内存溢出*/ return(head);/*返回头指针,下同*/ } printf("输入学号:"); scanf("%s",p->num); printf("输入姓名:"); scanf("%s",p->name); printf("请分别输入语文、数学、英语的分数%dscores\n",3);/*开始输入*/ for(i=0;i<3;i++)/*3门课程循环3次*/ { do{ printf("score%d:",i+1); scanf("%d",&p->score[i]); if(p->score[i]<0||p->score[i]>100)/*确保成绩在0~100之间*/ printf("Dataerror,pleaseenteragain.\n"); }while(p->score[i]<0||p->score[i]>100); } p->next=head;/*将头结点做为新输入结点的后继结点*/ head=p;/*新输入结点为新的头结点*/ } return(head);}/*显示全部记录函数*/voidprint(LinkList*head)整理为word格式整理为word格式整理为word格式{ LinkList*p; system("cls"); p=head;/*初值为头指针*/ printf("\n************************LinkList***************\n"); printf("-------------------------------------------------\n"); printf("|学号|姓名|语文|数学|英语|\n"); printf("-------------------------------------------------\n"); while(p!=NULL) { printf("|%4s|%-4s|%3d|%3d|%3d|\n", p->num,p->name,p->score[0],p->score[1],p->score[2]);p=p->next; } printf("-------------------------------------------------\n"); printf("***********************END***********************\n");}/*删除记录函数*/LinkList*Delete(LinkList*head){ LinkList*p1,*p2;/*p1为查找到要删除的结点指针，p2为其前驱指针*/ charc,s[6];/*s[6]用来存放学号,c用来输入字母*/ system("cls"); printf("请输入要删除的学生的学号:"); scanf("%s",s); p1=p2=head;/*给p1和p2赋初值头指针*/ while(strcmp(p1->num,s)&&p1!=NULL)/*当记录的学号不是要找的，或指针不为空时*/整理为word格式整理为word格式整理为word格式 { p2=p1;/*将p1指针值赋给p2作为p1的前驱指针*/ p1=p1->next;/*将p1指针指向下一条记录*/ } if(strcmp(p1->num,s)==0)/*学号找到了*/ { printf("***********************FOUND************************\n"); printf("-----------------------------------------------------------\n"); printf("|学号|姓名|语文|数学|英语|\n"); printf("-------------------------------------------------\n"); printf("|%4s|%4s|%3d|%3d|%3d|\n",p1->num,p1->name,p1->score[0],p1->score[1],p1->score[2]); printf("-----------------------------------------------------\n"); printf("**************************END**************************\n"); printf("您确定要删除该学生的记录吗Y/N?");/*提示是否要删除,输入Y删除,N则退出*/ for(;;) { scanf("%c",&c); if(c=='n'||c=='N')break;/*如果不删除,则跳出本循环*/ if(c=='y'||c=='Y') { if(p1==head)/*若p1==head，说明被删结点是首结点*/ head=p1->next;/*把第二个结点地址赋予head*/ else整理为word格式整理为word格式整理为word格式 p2->next=p1->next; free(p1); /*否则将一下结点地址赋给前一结点地址*/ printf("\n学号为%s的学生记录已被删除.\n",s); break;/*删除后就跳出循环*/ } } } else printf("\n找不到学号为%s的学生记录.\n",s);/*找不到该结点*/ return(head);}//插入LinkList*Insert(LinkList*head){ intk; //在表中第k个位置插入 printf("请输入插入的位置："); scanf("%d",&k); intj=0,i=0; LinkList*p1,*p2;/*p1为查找到要删除的结点指针，p2为其前驱指针*/ charN[10],s[10];/*s[10]用来存放姓名,N[10]用来存放学号*/ intscore[3]; system("cls"); printf("输入学号:"); scanf("%s",N); printf("输入姓名:"); scanf("%s",s); printf("请分别输入语文、数学、英语的分数%dscores\n",3);/*开始输入*/整理为word格式整理为word格式整理为word格式 for(i=0;i<3;i++)/*3门课程循环3次*/ { do{ printf("score%d:",i+1); scanf("%d",&score[i]); if(score[i]<0||score[i]>100)/*确保成绩在0~100之间*/ printf("Dataerror,pleaseenteragain.\n"); }while(score[i]<0||score[i]>100); } p1=head;/*给p1赋初值头指针*/ while(j<k-1&&p1!=NULL) { j++; p1=p1->next;/*将p1指针指向下一条记录*/ } if(p1==NULL)return0; else { p2=(LinkList*)malloc(sizeof(LinkList)); strcpy(p2->num,N); strcpy(p2->name,s); for(i=0;i<3;i++) p2->score[i]=score[i]; p2->next=p1->next; p1->next=p2; }}voidmenu_select()整理为word格式整理为word格式整理为word格式{ printf("\n\n\n"); printf("****************************************************\n"); printf("\tWelcometo\n"); printf("\tThestudentscoremanagesystem\n"); printf("**********************MENU**************************\n"); printf("\t\t1.输入学生记录\n");/*输入学生成绩记录*/ printf("\t\t2.输出学生记录\n");/*显示*/ printf("\t\t3.删除学生记录\n");/*删除*/ printf("\t\t4.插入一个新的学生记录\n");/*插入*/ printf("\t\t5.退出\n");/*退出*/ printf("****************************************************\n");}/*主函数界面*/voidScoreManage(){ LinkList*head,New; inti,n; head=init();/*链表初始化,使head的值为NULL*/ menu_select(); do{printf("\n\t\t输入您的选择(1~5):");scanf("%d",&n); }while(n<1||n>5); for(;;)/*循环无限次*/ { switch(n) { case1:head=create();break; case2:print(head);break; case3:head=Delete(head);break;整理为word格式整理为word格式整理为word格式 case4:head=Insert(head);break; case5:return;/*如菜单返回值为9则程序结束*/ } menu_select(); printf("\n\t\t\t输入您的选择(1~5):");scanf("%d",&n); }}//************************************************************//各种排序typedefintKeyType; /*定义关键字类型*/typedefcharInfoType[10];typedefstruct /*记录类型*/{ KeyTypekey; /*关键字项*/ InfoTypedata; /*其他数据项,类型为InfoType*/}RecType; /*排序的记录类型定义*/voidInsertSort(RecTypeR[],intn)/*对R[0..n-1]按递增有序进行直接插入排序*/{ inti,j; RecTypetmp; for(i=1;i<n;i++) { tmp=R[i]; j=i-1;/*从右向左在有序区R[0..i-1]中找R[i]的插入位置*/整理为word格式整理为word格式整理为word格式 while(j>=0&&tmp.key<R[j].key) { R[j+1]=R[j];/*将关键字大于R[i].key的记录后移*/ j--; } R[j+1]=tmp;/*在j+1处插入R[i]*/ }}voidBubbleSort(RecTypeR[],intn){ inti,j,exchange; RecTypetmp; for(i=0;i<n-1;i++) { exchange=0; for(j=n-1;j>i;j--) if(R[j].key<R[j-1].key) { tmp=R[j]; R[j]=R[j-1]; R[j-1]=tmp; exchange=1; } if(exchange==0)return; }}voidSelectSort(RecTypeR[],intn){ inti,j,k; RecTypetmp;整理为word格式整理为word格式整理为word格式 for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(R[j].key<R[k].key) k=j; if(k!=i) { tmp=R[i]; R[i]=R[k]; R[k]=tmp; } }}voiddisp(RecTypeR[],intn){ inti; for(i=0;i<n;i++) printf("%d",R[i].key);}voidSort(){ inti,n=10,k; RecTypeR[MaxSize]; KeyTypea[10]; printf("请输入排序的关键字(10个数字)\n"); for(i=0;i<n;i++) scanf("%d",&a[i]); for(i=0;i<n;i++)整理为word格式整理为word格式整理为word格式 R[i].key=a[i]; printf("\n\n直接插入排序:"); InsertSort(R,n); disp(R,n); printf("\n\n冒泡排序:"); BubbleSort(R,n); disp(R,n); printf("\n\n直接选择排序:"); SelectSort(R,n); disp(R,n);}//************************************************************//建立二叉树typedefcharElemType;typedefstructnode{ ElemTypedata; /*数据元素*/ structnode*lchild; /*指向左孩子结点*/ structnode*rchild; /*指向右孩子结点*/}BTNode;voidCreateBTNode(BTNode*&b,char*str){ BTNode*St[MaxSize],*p=NULL;整理为word格式整理为word格式整理为word格式 inttop=-1,k,j=0; charch; b=NULL; /*建立的二叉树初始时为空*/ ch=str[j]; while(ch!='\0') /*str未扫描完时循环*/ { switch(ch) { case'(':top++;St[top]=p;k=1;break; /*为左孩子结点*/ case')':top--;break; case',':k=2;break; /*为孩子结点右结点*/ default:p=(BTNode*)malloc(sizeof(BTNode)); p->data=ch;p->lchild=p->rchild=NULL; if(b==NULL) /**p为二叉树的根结点*/ b=p; else /*已建立二叉树根结点*/ { switch(k) { case1:St[top]->lchild=p;break; case2:St[top]->rchild=p;break; } } } j++; ch=str[j]; }}整理为word格式整理为word格式整理为word格式voidDispBTNode(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(")"); /*有孩子结点时才输出)*/ } }}//先序遍历非递归算法voidPreOrder(BTNode*b){ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL){ top++; St[top]=b; while(top>-1) { p=St[top]; top--; printf("%c",p->data); if(p->rchild!=NULL)整理为word格式整理为word格式整理为word格式 { top++; St[top]=p->rchild; } if(p->lchild!=NULL) { top++; St[top]=p->lchild; } } printf("%c",b); printf("\n"); }}//中序遍历非递归算法voidInOrder(BTNode*b){ BTNode*St[MaxSize],*p; inttop=-1; if(b!=NULL){ p=b; while(top>-1||p!=NULL) { while(p!=NULL) { top++; St[top]=p; p=p->lchild; }整理为word格式整理为word格式整理为word格式 if(top>-1) { p=St[top]; top--; printf("%c",p->data); p=p->rchild; } } printf("\n"); }}//后序遍历非递归算法voidPostOrder(BTNode*b){ BTNode*St[MaxSize],*p; intflag,top=-1; if(b!=NULL) { do { while(b!=NULL) { top++; St[top]=b; b=b->lchild; } p=NULL; flag=1; while(top!=-1&&flag)整理为word格式整理为word格式整理为word格式 { b=St[top]; if(b->rchild==p) { printf("%c",b->data); top--; p=b; } else { b=b->rchild; flag=0; } } }while(top!=-1); printf("\n"); }}//层序遍历voidLevelOrder(BTNode*b){ BTNode*p; BTNode*qu[MaxSize]; intfront,rear; front=rear=-1; rear++; qu[rear]=b; while(front!=rear) { front=(front+1)%MaxSize; p=qu[front];整理为word格式整理为word格式整理为word格式 printf("%c",p->data); if(p->lchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->lchild; } if(p->rchild!=NULL) { rear=(rear+1)%MaxSize; qu[rear]=p->rchild; } }}voidBTtree(){ BTNode*b; charstr[100]; printf("输入你要建立二叉树的结点："); scanf("%s",str); CreateBTNode(b,str); printf("\n\n建立二叉树为："); DispBTNode(b); printf("\n\n二叉树b的先序遍历序列"); PreOrder(b); printf("\n\n二叉树b的中序遍历序列"); InOrder(b); printf("\n\n二叉树b的后序遍历序列"); PostOrder(b); printf("\n\n二叉树b的层次遍历序列"); LevelOrder(b); printf("\n\n");整理为word格式整理为word格式整理为word格式}//************************************************************//有序表的合并typedefcharElemType;typedefstruct{ ElemTypedata[MaxSize]; /*存放顺序表元素*/ intlength; /*存放顺序表的长度*/}SqList; /*顺序表的类型定义*/typedefstructLNode1 /*定义单链表结点类型*/{ ElemTypedata; structLNode1*next; /*指向后继结点*/}LinkList1;voidInitList(SqList*&L){ L=(SqList*)malloc(sizeof(SqList)); /*分配存放线性表的空间*/ L->length=0;}voidInitList1(LinkList1*&L){ L=(LinkList1*)malloc(sizeof(LinkList1)); /*创建头结点*/ L->next=NULL;}voidCreateList(SqList*&L,ElemTypea[],intn)/*建立顺序表*/整理为word格式整理为word格式整理为word格式{ inti; for(i=0;i<n;i++) L->data[i]=a[i]; L->length=n;}voidCreateListR(LinkList1*&L,ElemTypea[],intn)/*尾插法建立单链表*/{ LinkList1*s,*r;inti; L=(LinkList1*)malloc(sizeof(LinkList1)); /*创建头结点*/ L->next=NULL; r=L; /*r始终指向终端结点,开始时指向头结点*/ for(i=0;i<n;i++) { s=(LinkList1*)malloc(sizeof(LinkList1));/*创建新结点*/ s->data=a[i]; r->next=s; /*将*s插入*r之后*/ r=s; } r->next=NULL; /*终端结点next域置为NULL*/}voidDispList(SqList*L){ inti; if(L->length==0)return; for(i=0;i<L->length;i++)整理为word格式整理为word格式整理为word格式 printf("%c",L->data[i]); printf("\n");}voidDispList1(LinkList1*L){ LinkList1*p=L->next; while(p!=NULL) { printf("%c",p->data); p=p->next; } printf("\n");}//顺序表存放有序表voidUnionList(SqList*LA,SqList*LB,SqList*&LC){ inti=0,j=0,k=0; /*i、j、k分别作为LA、LB、LC的下标*/ LC=(SqList*)malloc(sizeof(SqList)); LC->length=0; while(i<LA->length&&j<LB->length) { if(LA->data[i]<LB->data[j]) { LC->data[k]=LA->data[i]; i++;k++; } else /*LA->data[i]>LB->data[j]*/ { 整理为word格式整理为word格式整理为word格式 LC->data[k]=LB->data[j]; j++;k++; } } while(i<LA->length) /*LA尚未扫描完,将其余元素插入LC中*/ { LC->data[k]=LA->data[i]; i++;k++; } while(j<LB->length)/*LB尚未扫描完,将其余元素插入LC中*/ { LC->data[k]=LB->data[j]; j++;k++; } LC->length=k;}//单链表存放有序表voidUnionList1(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->data<pb->data) { s=(LinkList1*)malloc(sizeof(LinkList1));/*复制*pa结点*/整理为word格式整理为word格式整理为word格式 s->data=pa->data; pc->next=s;pc=s; /*采用尾插法将*s插入到LC的最后*/ pa=pa->next; }else { s=(LinkList1*)malloc(sizeof(LinkList1));/*复制*pb结点*/ s->data=pa->data; pc->next=s;pc=s; /*采用尾插法将*s插入到LC的最后*/ pa=pa->next; } } while(pa!=NULL) { s=(LinkList1*)malloc(sizeof(LinkList1)); /*复制*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;}voidUnion()整理为word格式整理为word格式整理为word格式{ SqList*L1,*L2,*L3; LinkList1*L4,*L5,*L6; ElemTypea[5]; ElemTypeb[5]; 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); Cr