C++数据结构 大作业课程设计正文

《C++数据结构 大作业课程设计正文》由会员分享，可在线阅读，更多相关《C++数据结构 大作业课程设计正文（60页珍藏版）》请在装配图网上搜索。

1、C++数据结构 大作业课程设计正文 第一篇：C++数据结构 大作业课程设计 C++/数据结构 大作业/课程设计——【校园导游咨询】【停车场管理】娃娃们可以收着以后用 绝对纯手工打造 内含类模块/一维指针数组（谨以此程序供大家参考。运行结果后面有贴图） 目录 【1】校园导游咨询 程序设计源代码 及 截图 【2】停车场管理——方案一 程序设计源代码 及 截图 【3】停车场管理——方案二 程序设计源代码 及 截图 【1】【【校园导游咨询】】 ###### (ps:该校园导游咨询系统没有输入值，所有信息是都在class MGraph的构造函数中传输的，且校园景点信息皆为【【上海电力学院】

2、】景点信息。请大家注意，直接从文章copy到visual stutio中会出现中文字符，注意删除，推荐大家在一行语句的分号后面，点出光标，按一下delete键，然后按一下enter键，完成visual stutio的自动对齐，这样程序看起来一目了然，更易于操作和更改) 【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。 【基本要求】 (1)设计你所在学校的校园平面图，所含景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 (2)为来访客人提供图中任意景点相关信息的查询。 (3)为来访客人提供图中任意景点的

3、问路查询，即查询任意两个景点之间的一个最短的简单路径。 【选作内容】 (6)扩充每个景点的邻接景点的方向等信息，使得路径查询结果能提供详尽的导向信息。 **************************【以下为类的定义】******************************** #include #include using namespace std; const int MaxSize=18; const int INFINITY=65535;//最大值无穷 class direction; template class MGraph; template class Verte

4、xNode//定义头结点 { friend class MGraph; public: int vex;//顶点名称 T vexname;//顶点名称 T vexinf;//顶点信息 direction dir;//存放顶点方位信息的direction类的dir。 }; class direction { public: int ln;//存放在方向图中的横坐标，表示东西 int col;//存放在方向图中的纵坐标，表示南北 }; template class MGraph//定义无向图的邻接矩阵 { public: MGraph(); //构造函数，初始化具有n个顶点的图 voi

5、d printvexname();//显示所有景点及景点代号 void printvexinf(int i);//显示代号为i景点的名称及信息 void printroad(int i,int j);//显示景点i~j的最短路径方案信息 void printdir(int i,int j);//显示景点i到j的方向信息，如“向东100m，向南2021” VertexNode adjlist[MaxSize]; //存放景点全部信息的 景点类数组 int vertexNum,arcNum; //图的顶点数和边数 void Root(int p,int q);//递归寻找pq间的最短路径

6、 int Path[MaxSize][MaxSize],Dist[MaxSize][MaxSize];//创建Path和Dist分别存放两点间最短路径的前驱节点，两点间最短路径长度 int Line[MaxSize];//Line存放路径 int kkk;//Line[]数组的标记 private: T vertex[MaxSize]; //存放图中顶点的数组 int arc[MaxSize][MaxSize];//存放图中边的数组 }; *************************【以下为类的实现 即类函数的定义】*********************************

7、** template MGraph::MGraph()//a[]为景点代号，b[]为景点名称，c[]为景点信息，d[]为景点方位信息的横坐标，e[]为景点方位信息的纵坐标 //s[]为存放景点邻接矩阵信息的一维数组，根据其对称性可以用公式赋值给二维数组arc[][] { int s[]={0, 1,0, 0,2,0, 0,0,2,0, 0,0,2,3,0, 0,0,0,4,2,0, 0,0,0,0,2,3,0, 0,0,0,0,2,3,1,0, 0,0,2,0,2,0,0,2,0, 4,0,2,0,0,0,0,0,1,0, 0,0,0,0,0,0,0,0,0,2,0, 1,0,0,0,0,

8、0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,3,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0, 0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,2,0, 0,0,0,0,0,0,0,0,0,0,0,0,4,4,0,0,2,0}; int a[]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17}; char* b[]={"南门","实验楼","南图","大活","睿思楼"

9、,"大礼堂", "南4教","知行楼","国交楼","南3教","南2教","南1教", "北图","北3教","北4教","北2教","北1教","北门"}; char* c[]={"南校区正门","物理实验楼","南校区图书馆","大学生活动中心", "教师办公楼、医务室及留学生公寓","大礼堂，用于举办各种文艺演出","南校区第4教学楼","实习基地，计算机房等", "国际交流中心，教职工餐厅","南校区第3教学楼","南校区第2教学楼","南校区第1教学楼", "北校区图书馆","北校区第3教学楼","北校区第4教学楼","北校区第2教学楼", "北校区第1教学楼","北校区正门"};

10、 int d[]={8,6,4,4,1,0,0,1,3,4,6,8,4,3,2,3,5,8}; int e[]={8,8,8,10,8,10,7,6,6,6,6,6,3,1,0,0,0,2}; int i,j; vertexNum=18; arcNum=30; for(i=0;i for (j=0; j void MGraph::printvexname() { int i; for(i=0;i template void MGraph::printvexinf(int i) { cout0)//即j在i的东边 cout0) { Root(p,Path[p][q]); Root(Pa

11、th[p][q],q); } else { Line[kkk]=q; kkk++; } } template void MGraph::printroad(int i,int j) { int p,q,m,k,item1,item2; for(p=0;p0) for(q=0;q0) if (((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)) { Dist[p][q]=Dist[p][k]+Dist[k][q]; Path[p][q]=k; } cout""choice; return choice; } voi

12、d main() { MGraph mg; int funcchoice(); int fc; while(1) { fc=funcchoice(); if(fc==1) { int i; for(i=0;i>i; mg.printvexinf(i); } else if(fc==3) { int i,j; mg.printvexname(); cout>i>>j; mg.printroad(i,j); } else if(fc==4) break; else couti) stemp.s[++(stemp.top)]=cs.s[(cs.top)--];//出栈的元素数组逐个赋给临时栈 pop

13、stacknumber=p.number;//将这个车牌号信息传给int popstacknumber() popstacktime=p.time;//将该车的时间信息传给double popstacktime() cs.top--;//栈顶指针回到原来位置 while(stemp.top>=0) cs.s[++(cs.top)]=stemp.s[(stemp.top)--];//临时栈出栈的元素逐个赋给原栈，完成先退再进的工作 } int parkingmanagement::pushqueue(carqueue &cq,int cnum,double ctime)//入队,队内进行调整，

14、返回队内位置 { car *p,*countp; int count(1);//count用于记录车在过道上的位置信息，因队列为链式的，所以进行循环累加 p=new car;//创建一个car类型的指针 p->number=cnum; p->time=ctime; p->next=NULL;//首先将指向存放car类型元素的数组初始地址置空 if (cq.front==NULL)//第一次入队要判断头结点是否为空 { cq.front=cq.rear=p; } else {//尾插法插入元素 p->next=(cq.rear)->next; (cq.rear)->next=p; cq.re

15、ar=(cq.rear)->next; } countp=(cq.front)->next; while(countp!=NULL) { count++; countp=countp->next; }//count即车在过道上的位置，【从1开始计！！！】 return count; } int parkingmanagement::popqueue(carqueue &cq)//出队,队内进行调整，返回汽车车牌号 { car p; p.number=((cq.front)->next)->number;//cq队里，从cq.front开始指向下一个元素的车牌号赋给car类型的车信息 p.ti

16、me=((cq.front)->next)->time;//cq队里，从cq.front开始指向下一个元素的时刻 //赋给car类型的车信息 p.next=((cq.front)->next)->next;//cq队里，从cq.front开始指向下一个元素的指针 //赋给car类型的车信息的下一个元素的指针 return p.number; cq.front=(cq.front)->next; } void parkingmanagement::arrival(carstack &cs,carqueue &cq,int cnum,double ctime) //车辆到达，根据输入的车牌号、到

17、达时间，变更函数参数；并cout车位信息 { int pos; if(!(cs.full()))//如果栈未满，车辆停入停车场 { int fl(0),i;//定义一个从0开始的标记fl for(i=0;inext; if(p->number==cnum)//在过道中找到要出去的车，则在队列中删除该car。 //后面的车辆依然顺序排列，补足空位 { deletequeue(cq,count); if(count>Max) { coutnext) coutnext; p->next=q->next; delete q; } } *******************************【以

18、下是主程序】************************************ void print() { coutacc>>carnum>>cartime; if(acc=='A') park.arrival(cars,carq,carnum,cartime); else if(acc=='D') park.leave(cars,carq,carnum,cartime); else if(acc=='E') break; else coutcarnum=cnum; s->next=NULL; if(front==NULL)//空队列，【【【新结点既是队头，又是队尾】】】关键是！fro

19、nt指向第一个结点 { front=rear=s; } else { rear->next=s;//将结点s插入到队尾 rear=s; } p=front; while(p!=NULL) { i++; p=p->next; }//i即车在过道上的位置，【从1开始计！！！】 return i; } template T carQueue::DeQueue() { Node *p; if (front==NULL) coutnext;//将队头元素所在结点摘链 } return p->carnum; delete p;//将出队进栈的车从队列里删除 } template bool carQ

20、ueue::Empty()//判断是否为空，为空则返回1，不为空则返回0 { return front==NULL; } template carStack::carStack()//构造栈算法 :top(-1) {//建立一个最大尺寸为size的空栈 S=new carinfo[MaxSize];//创建存储栈的数组 if(S==NULL) //分配不成功 { cerri) Stemp.S[++Stop]=S[top--]; hour=outctime-S[top].cartime; return hour; top--; while(Stop>=0) S[++top]=Stemp.

21、S[Stop--]; } template bool carStack::full() { return top==MaxSize-1; } template void carQueue::deletequeue(int i) { Node *p,*q; int j(1); p=front; while(p && jnext; j++; }//找到第i-1个结点(结点位置从1开始) if(!p||!p->next) coutnext=q->next; delete q; } } ******************************【以下为主函数】********************

22、******************* void outputpark()//系统功能选择页面，输入泊车信息 { cout>arrive>>carnum>>cartime; if(arrive=='A') { if(cs.top!=MaxSize-1)//停车场内有空位可以驶入 { cs.Pushcar(carnum,cartime); coutcarnum==carnum) { flagde=1; break; } pos++; p=p->next; } if(flagde) { coutdata);//输出学生信息和成绩信息 pNodeScore=pNodeScore->next;

23、 } } void Add() { p_node_score pNodeScore; // 定义一个节点 pNodeScore=(p_node_score)malloc(sizeof(node_score));//为节点分配存储空间 printf("请输入学号："); scanf("%s",pNodeScore->data.Number); printf("请输入姓名："); scanf("%s",pNodeScore->data.Name); printf("请输入语文成绩："); scanf("%s",pNodeScore->data.Chinese); printf("请输入英语成

24、绩："); scanf("%s",pNodeScore->data.English); printf("请输入高数成绩："); scanf("%s",pNodeScore->data.Math); if(headScore==NULL) { //如果头结点为空 headScore=pNodeScore; pNodeScore->next=NULL; } else { //如果头结点不为空 pNodeScore->next=headScore; headScore=pNodeScore;//将头结点新结点 } } void Input() { int n,i; printf("输入几

25、个学生的数据："); scanf("%d",&n); for(i=0;i Add(); printf("输入成功！"); } int Delete() { p_node_score pNodeScore,p1; //p1为pNodeScore的前驱 p1=headScore; if(p1==NULL) { printf("成绩表中没有数据！请先添加数据！\n"); return 0; } char DeleteNumber[2021 printf("请数入要删除的学生学号:"); scanf("%s",DeleteNumber); if(strcmp(p1->data.Number,

26、DeleteNumber)==0) { //如果要删除的结点在第一个 headScore=p1->next; pNodeScore=p1; printf("学号为%s的学生信息已经删除！\n",DeleteNumber); return 0; } else { pNodeScore=p1->next; while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,DeleteNumber)==0) { p1->next=pNodeScore->next; printf("学号为%s的学生信息已经删除！\n",D

27、eleteNumber); return 0; } else { //否则，结点向下一个，p1仍为pNodeScore的前驱 p1=pNodeScore; pNodeScore=pNodeScore->next; } } } printf("没有此学号的学生！"); } int Change() { p_node_score pNodeScore; pNodeScore=headScore; if(pNodeScore==NULL) { printf("成绩表中没有数据！请先添加数据！\n"); return 0; } char EditNumber[2021 prin

28、tf("请输入你要修改的学生学号："); scanf("%s",EditNumber); while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,EditNumber)==0) { //用strcmp比较两字符串是否相等，相等则返回0 printf("原来的学生成绩信息如下：\n"); //输出原来的成绩信息 printf(" 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩\n"); PrintScore(pNodeScore->data); printf("语文新成绩:"); scanf("%s"

29、,pNodeScore->data.Chinese); printf("英语新成绩:"); scanf("%s",pNodeScore->data.English); printf("高数新成绩:"); scanf("%s",pNodeScore->data.Math); printf("成绩已经修改！"); return 0; } pNodeScore=pNodeScore->next; //如果不相等，pNodeScore则指向下一个结点 } printf("没有此学号的学生！\n"); //如果找到最后都没有，则输出没有此学号的学生 } int Find() { p

30、_node_score pNodeScore; pNodeScore=headScore; if(pNodeScore==NULL) { printf("成绩表中没有数据！请先添加数据！\n"); return 0; } char FindNumber[2021 printf("请输入你要查找的学生学号："); scanf("%s",FindNumber); while(pNodeScore!=NULL) { if(strcmp(pNodeScore->data.Number,FindNumber)==0) { printf("你要查找的学生成绩信息如下：\n"); printf

31、(" 学号 | 姓名 | 语文成绩 | 英语成绩| 高数成绩\n"); PrintScore(pNodeScore->data); return 0; } pNodeScore=pNodeScore->next; } printf("没有此学号的学生！\n"); } int main() //主函数 { int choice=0; headScore=NULL; int c; do { system("color 2f"); //运行环境背景颜色. printf("\n\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\n\t

32、\t"); printf("\n\t\t\t 学生成绩管理系统 \t\t\t"); printf("\n\n\t\t*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=*=\n\t\t"); printf("\n\t\t\t1.输入成绩信息\n\t\t\t2.输出成绩信息\n\t\t\t3.添加成绩信息\n\t\t\t"); printf("4.修改成绩信息\n\t\t\t5.删除成绩信息\n\t\t\t6.查询成绩信息\n\t\t\t7.退出"); printf("\n\n\t\t\t请选择:"); scanf("%d",&c); switch(c)

33、{ case 1:system("cls");Input();break; case 2:system("cls");View();break; case 3:system("cls");Add();break; case 4:system("cls");Change();break; case 5:system("cls");Delete();break; case 6:system("cls");Find();break; case 7:system("cls");exit(0); } }while(1); return 0; } 运行界面如下： 第三篇：数据结构课程

34、设计 二○一三 ～二○一四 学年第 二 学期 信息科学与工程学院 综合设计报告书 课程名称： 数据结构课程设计 班 级： 学 号： 姓 名： 指导教师： 二○一四 年 六 月 一、实验内容 (一)、单链表：将若干城市的信息存入一个带头的单链表中，结点中城市信息包括城市的位置坐标，要求：给定一个城市名，返回其位置坐标；给定一个位置坐标P和一个距离D，返回所有与P的距离小于等于D的城市。 （二）、回文判断：试写出一个算法，判断依次读入的一个以@为结束符的字母序列，是否形如“序列1&序列2”模式的字符序列。其中序列1和序列2中都不含有字符“&”，且序列2是序列1的逆序列。例如，“a+

35、b&b+a”是属于该模式的字符序列。 （三）、树和二叉树：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序，中序，后序）。打印输出遍历结果。 二、实验过程 （一）、城市信息 1、根据题目，我们认为我们所编的程序需要实现以下功能： （1）、创建一个城市链表，能够输入城市信息，即城市名和城市位置坐标； （2）、能够根据城市名查询其位置坐标； （3）、根据离中心坐标距离查询城市名； （4）、能够插入城市信息； （5）、能够删除城市信息； （6）、能够更新城市信息； （7）、执行完毕，退出程序。 2、演示程序以用户和计算机的对话方式执行，即在在计算机终端上显示“提示信息”之后，由用户

36、在键盘上输入演示程序中规定的运算命令；输入相应的数据（滤去输入中非法字符），运算结果显示在其后。`测试数据 1）、输入”1”调用函数 Create()； 新建城市信息: fujian(1.1,2.2) beijing(3.3,4.4) shanghai(5,6) tianjing(7,8) nanjing(910，910) hangzhou(11,12) 输入END键,退出. 2）、输入”2”,调用函数FindCity()； 当键入城市名时,返回其城市坐标: 如：键入城市名”fujian”，返回坐标：1.10.2.2021）、输入“3”调用函数 FindCityDistance()

37、; 如：当给定坐标P（3.3，4.4）时,距离5时,就输出所有与P的距离小于等于5的城市信息。 4）、输入”4”,调用函数Insert().进行插入新城市信息操作； 如:插入城市信息:hainan(5,8)，当进行查找时,能看到插入城市的信息.证明插入成功. 5）、输入”5”,调用函数Delete(),进行删除操作： 6）、输入”6”,调用函数UpdateCity(Store),进行更新操作； 7）、输入”7”,退出. 3、源程序代码： void Init(CityList *LHead) { LHead->Next = NULL; } //建立一个带头结点的单链线性表，LHead指向

38、头结点。 void Insert(CityList *LHead) { CityList* newNode; //定义指针结构为cityList型 char m; newNode = (CityList*)malloc(sizeof(CityList)); //生成新结点 if(newNode == NULL) //验证空间申请是否成功 { printf("内存分配失败\n"); return; //若分配内存不成功，则返回继续分配。 } printf("请输入城市名\n"); scanf("%s",newNode->CityName);//指针的数据域 printf("请输入城

39、市坐标x,y\n"); scanf("%f%c%f",&newNode->X,&m,&newNode->Y); //将城市信息填入新节点中 while(LHead->Next != NULL) { LHead = LHead->Next; }//如果非空，HLead指针的位置向后移 newNode->Next = LHead->Next; LHead->Next = newNode; } //将新节点插入链表 void Delete(CityList *LHead) { char delCity[10]; printf("请输入要删除的城市名\n"); scanf("%s",delCit

40、y); while(strcmp(LHead->Next->CityName,delCity ))//从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。 { LHead = LHead->Next; //不相等则指针LHead下移，继续查找 } LHead ->Next = LHead->Next->Next; //相等则删除此节点 } void Create(CityList *LHead) { char sign[2021 //定义输入信息类型及长度 printf("输入END退出,输入其余值继续\n"); //当输入END时，在任意输入，则退出此操作

41、 scanf("%s",sign); while(strcmp(sign,"END")) ////当输入END时，再任意输入，则退出此操作 { Insert(LHead); printf("输入END退出,输入其余值继续\n"); scanf("%s",sign); } } void FindCity(CityList* LHead) { char CityName[30]; int j=0; printf("请输入您要搜索的城市名\n"); scanf("%s",CityName); while(LHead->Next != NULL && strcmp(LHead->Next-

42、>CityName,CityName)) { LHead = LHead->Next; } if(LHead->Next == NULL) { printf("您要搜索的城市不存在\n"); return; } printf("城市坐标为%.2f,%.2f\n",LHead->Next->X,LHead->Next->Y); } void UpdateCity(CityList* LHead) { char CityName[10]; printf("请输入您要更新的城市名\n"); scanf("%s",CityName); while(strcmp(LHead->Next->Cit

43、yName,CityName)) //从LHead指向得头结点的下一个结点开判断结点中的城市名与输入城市名是否相等。 { LHead = LHead->Next; // 当不相等则指针LHead下移，继续查找 } printf("请输入城市新信息:\n"); printf("请输入城市新名\n"); scanf("%s",LHead->Next->CityName); printf("请输入城市新坐标\n"); scanf("%f",&LHead->Next->X); scanf("%f",&LHead->Next->Y); } //输入城市新信息 void FindCityDista

44、nce(CityList* LHead) { char m; float x; float y; float distance; printf("请输入中心坐标x,y\n"); scanf("%f%c%f",&x,&m,&y); printf("请输入距离:"); scanf("%f",&distance); LHead = LHead->Next; while(LHead != NULL) { if((x-LHead->X)*(x-LHead->X) + (y-LHead->Y)*(y-LHead->Y)CityName); printf("城市坐标为%.2f,%.2f\n",LHead

45、->X,LHead->Y); } LHead = LHead->Next; }} void main() { CityList* LHead; CityList* Store; char choice[3] = {1,2,3}; LHead = (CityList*)malloc(sizeof(CityList)); Init(LHead);//建立空表 Store = LHead; while(strcmp(choice,"7")){ //当所选择等于7时，进行以下操作 printf("***************************\n"); printf("*******

46、********************\n"); printf(" 欢迎使用本系统 \n"); printf("***************************\n"); printf("***************************\n"); printf("1.创建城市链表\n"); printf("2.根据城市名查询城市\n"); printf("3.根据离中心坐标距离查询城市\n"); printf("4.插入新城市信息\n"); printf("5.删除城市信息\n"); printf("6.更新城市信息\n"); printf("7.退出\n"); //以上相当于

47、一个选择菜单，皆为提示信息 printf("==========================\n"); printf("请输入:"); scanf("%s",&choice); switch(choice[0]){ case '1': //相当于选择1 Create(Store); //构造并创建城市信息链表 break; case '2': FindCity(Store);//根据城市名查找城市位置 break; case '3': FindCityDistance(Store);//根据所给中心坐标和距离值，返回小于等于所给距离值得节点信息。 break; ca

48、se '4': Insert(Store);//插入新结点 break; case '5': Delete(Store);//删除结点 break; case '6': UpdateCity(Store);//更新结点信息 break; case '7'://退出 break; default: printf("输入错误,请重新输入\n"); break; } } system("PAUSE"); return ; } （二）、回文判断 1、需求分析： （1）输入测试数据组数，接着分组输入字符串，以@结尾。 （2）输入序列总长不超过 (MAX_N = 1000

49、5)/2 个。将序列1先入栈，接着处理序列2，同时出栈判断。 （3）将序列1全部入栈，接着输入序列2，同时出栈判断。 （4）如果序列满足题目要求，则输出“回文序列”；否则，输出“非回文序列”。 12 a+b&b+a@ a&b@ a&a@ 2、（1）数据结构： typedef struct Stack{ int top,size; char str[MAX_N>>1]; }; 使用结构体，内部定义数组模拟栈。top为栈顶指针，指向当前元素的下一个位置，size表示栈内的元素个数。 （2）函数介绍： void st_init(Stack *st); //栈的初始化 bool s

50、t_push(Stack *st,const char *temp); //入栈 bool st_top(Stack *st,char *temp); //出栈 3、源程序代码： #include #include #include const int MAX_N = 10005; typedef struct Stack{ int top,size; char str[MAX_N>>1]; }; void st_init(Stack *st) { st->size=MAX_N>>1; st->top=0; } bool st_push(Stack *st,const char *t

51、emp) { if( st->top>st->size ) return false; st->str[st->top++] = *temp; return true; } bool st_pop(Stack *st) { if( st->top==0 ) return false; st->top--; return true; } bool st_top(Stack *st,char *temp) { if( st->top==0 ) return false; *temp = st->str[st->top-1]; return true; } int main() { char

52、str[MAX_N],c; int i,j,cas,len; Stack st; bool flag; // freopen("pal.txt","r",stdin); printf("请输入测试组数：\n"); scanf("%d",&cas); getchar(); j=0; while( cas-- ) { ++j; printf("\n第 %d 组数据„„\n",j); printf("\n请输入数据（字符串1&字符串2@）：\n"); for( i=0; 1; i++ ) { str[i]=getchar(); if( str[i]=='@' ) { str[i]='\0';

53、 break; } } getchar(); flag = true; len = strlen(str); st_init(&st); if( !len&1 ) flag = false; else { for( i=0; i if( str[i]=='&' ) break; st_push(&st,&str[i]); } for( ++i; i st_top(&st,&c); flag = st_pop(&st); if( c!=str[i] || !flag) { flag = false; break; } } if( st.top>0 ) flag = fals

54、e; } printf("\nCase : %d\n",j); if( flag ) printf("回文序列。\n"); else printf("非回文序列。\n"); printf("\n"); } printf("输入结束。By changning.huang"); // while( true ); return 0; } （三）、二叉树 1、算法思想： 定义二叉树结构体类型时，也定义了一个顺序栈结构体类型，用以辅助完成二叉树的非递归遍历。 由键盘输入二叉树先序序列，用扩展线序序列函数接受并创建二叉链表。 遍历前先判断二叉树是否为空，若为空，执行空操作；否则依次执行各

55、遍历函数相应操作。 先序遍历，先访问根节点，然后按先序遍历左子树，再按先序遍历右子树。 中序遍历，先按中序遍历左子树，再访问根节点，然后按中序访问右子树。 后序遍历，先按后序遍历左子树，接着按中序遍历右子树，然后访问根节点。 2、测试数据： ABCффDEфGффFффф（其中ф表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA 3、源程序代码： #include #include typedef struct tnode { char data; struct tnode *lchild; struct tnode *rchild;

56、}tnode; tnode *Tree_creat(tnode *t) { char ch; ch=getchar(); if(ch==' ') t=NULL; else { if(!(t=(tnode *)malloc(sizeof(tnode)))) printf("Error!"); t->data=ch;//printf("[%c]",t->data); t->lchild=Tree_creat(t->lchild); t->rchild=Tree_creat(t->rchild); } return t; } void preorder(tnode *t) { if(t!=NULL

57、) { printf("%c ",t->data); preorder(t->lchild); preorder(t->rchild); } } void main() { tnode *t=NULL; t=Tree_creat(t); preorder(t); } 三、心得体会： 数据结构实验是大一学过c语言实验的深化，难度增加了很多。但本次实验三个部分主要涉及单链表、栈、队列的知识。我觉得这些计算机中的线性存储结构原理比较好理解，但是当自己来编写程序的时候难度大大增加了，这其中涉及到一些指针、结构体等c语言基础的东西。开始做实验的时候，由于对上述知识不太熟悉，感觉很困难，后来通过复

58、习c语言相关内容和上网查阅资料，逐步理解代码，一点点掌握了技巧。 总之，这次实验自己感觉对用c语言写程序的掌握又进一步强化了，实验中遇到的困难也都解决了，能力得到了锻炼。 第四篇：数据结构课程设计 课 程 设 计 任 务 书 信息 学院 信息管理与信息系统 专业 09级1班 班 孙鹏 一、 二、 课程设计题目： 迷宫求解、一元多项式 课程设计主要参考资料： 数据结构（C语言版） 严蔚敏、吴伟民 编著 数据结构题集（C语言版） 严蔚敏、吴伟民、米宁 编著 数据结构课件 三、 设计应解决下列各主要问题： 1.实现迷宫的路径求解，并输出最终路径，标记走过却未选择的路径和最终选择

59、的路径 2.对一元多项式实现加法，减法，乘法，求导的计算，并按指数由大到小排序输出 四、 课程设计相关附件（如：图纸、软件等）： 五、命题发出日期：2021-3-15 设计应完成日期： 2021-6-2021 设计指导教师（签章）： 系主任（签章）： 指导教师对课程设计的评语 指导教师（签章）： 年 月 日 山东科技大学学生课程设计 课程设计1 迷宫问题 一、 需求分析： 1. 2. 3. 4. 以二维数组Maze[][]表示迷宫 用户输入迷宫的数据：构建迷宫，行数m，列数n 迷宫的入口位置和出口位置可由用户随时设定 若设定的迷宫存在通路，则以长方阵形式将迷宫及其通

60、路输出到标准输出文件（即终端）上，其中，字符“#”表示障碍，字符“*”表示路径上的位置，字符“@”表示“死胡同”，即曾经途径然而不能到达出口的位置，余者用空格符印出。若设定的迷宫不存在通路，则报告相应信息。 5. 本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数做小量修改，便可求得全部路径。 二、 概要设计： 抽象数据类型线性表的定义如下： ⒈ 设计栈的抽象数据类型定义： ADT Stack { 数据对象：D={ai:|ai∈PositionSet,i=1„n,n≥0} 数据关系：R1={|ai-1,ai∈d,i=2,„n} 基本操作： 的初始化S GetTop(S,&e)

61、素 Push(&S,e) Pop(&S,e) 返回其值 }ADT Stack； ⒉ 迷宫的抽象数据类型定义： ADT Maze{ 数据对象：D：={aij,Start,end|aij,Start,end∈{} 0≤i≤m+2,0≤j≤n+2,m,n≥0} 数据关系：R={ROW.COL} Row={|ai-1,aij∈D i=1,„,m+2,j=1,„,n+2} 第1页 操作结果 构造一个空栈，完成栈用e返回栈S的栈顶元将新的元素e压入栈顶 删除栈顶元素，并用eInitStack(&S) 山东科技大学学生课程设计 Col={|aijaij-1∈D} 基本操作: masepa

62、th (int i,int j,int m,int n,sqstack &s) 初始条件：已知目前迷宫状态, 传过起始位置，和终止位置 操作结果：搜索迷宫，用sqstack s返回搜索所得路径。如不存在，返回2 }ADT MAZE 三、 详细设计： #include #include #include #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define STACK_INIT_SIZE 100 //存储空间初始量 #define STACK_INCREMENT 10//

63、存储空间初始增量 typedef int Status; typedef struct { int r; int c; }PostType;//坐标位置 迷宫的r行c列 typedef struct { int ord;//通道块在路径上的序号 PostType seat;//通道块的当前坐标位置 int di;//通道块指向下一通道块的方向 }SElemType;//栈元素的类型 typedef struct { SElemType *base;//栈底指针 SElemType *top;//栈顶指针 int stacksize;//栈的最大容量 }Stack;//栈的类型

64、第2页 山东科技大学学生课程设计 Status InitStack(Stack &S)//初始化栈 { S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) exit(OVERFLOW);//存储分配失败; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; }//InitStack Status StackEmpty(Stack S) //判断栈是否为空,如果为空返回TRUE,否则返回FALSE { if(S.top==S.base)

65、 return TRUE; return FALSE; }//StackEmpty Status Push(Stack &S,SElemType e) //插入元素为e的栈顶元素 { if(S.top-S.base>=S.stacksize) { S.base=(SElemType*)realloc(S.base,(S.stacksize+STACK_INCREMENT)*sizeof(SElemType)); if(!S.base) exit(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACK_INCREMENT; }

66、 *S.top++=e; return OK; }//Push Status Pop(Stack &S,SElemType &e) //删除栈顶元素存入e { if(S.top==S.base) return ERROR; e=*--S.top; 第3页 山东科技大学学生课程设计 return OK; }//Pop Status DestroyStack(Stack &S) //销毁栈 { free(S.base); S.top=S.base; return OK; }//DestroyStack //maze.cpp #define MAXLEN 2021迷宫包括外墙最大行列数目 typedef struct{ int r; int c; char adr[MAXLEN][MAXLEN];//可取' ''*' '@' '#' }MazeType; //迷宫类型 Status InitMaze(MazeType &maze){ //初始化迷宫若成功返回TRUE,否则返回FALSE int m,n,i,j,k=1; printf("输入迷口的行数和列数: ");