数据结构实验指导书

数据结构实验指导书适用所有数据结构实验独立设课的专业雷文编写

概述一、课程目的《数据结构》是一门实践性很强的软件基础课程，为了学好这门课，每个学生必须完成一定数量的上机作业。通过本课程的上机作业，要求在数据结构的选择和应用、算法的设计及实现等方面加深对课程基础内容的理解，同时，实验题中的问题比平时的练习题要复杂，也更接近实际，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。本课程实验的目的是旨在使学生进一步巩固课堂上所学的理论知识；深化理解和灵活掌握教学内容；培养学生算法设计的能力和解决实际问题的程序设计的能力。二、实验名称与学时分配序号实验名称学时数实验类型1线性表顺序存储结构2验证2链表应用2验证3利用栈实现递归2验证4链队列应用2验证5二叉树遍历4综合6图的遍历4综合三、实验要求⒈问题分析充分地分析和理解问题本身，弄清要求做什么，包括功能要求、性能要求、设计要求和约束以及基本数据特性，数据间的联系等。⒉数据结构设计针对要求解决的问题，考虑各种可能的数据结构，并且力求从中出最佳方案(必须连同算法一起考虑)，确定主要的数据结构及全程变量。对引入的每种数据结构和全程变量要详细说明其功能、初值和操作特点。⒊算法设计算法设计分概要设计和详细设计，概要设计着重解决程序的模块设计问题，这包括考虑如何把被开发的问题程序自顶向下分解成若干顺序模块，并决定模块的接口，即模块间的相互关系以及模块之间的信息交换问题.详细设计则要决定每个模块内部的具体算法，包括输入、处理和输出，采用类C语言描述。⒋测试用例设计准备典型测试数据和测试方案，测试数据要有代表性、敏感性，测试方案包括模块测试和模块集成测试。⒌上机调试对程序进行编译，纠正程序中可能出现的语法错误，测试前，先运行一遍程序看看究竟将会发生什么，如果错误较多，则根据事先设计的测试方案并结合现场情况进行错误跟踪，包括打印执行路径或输出中间变量值等手段。三、实验考核每次实验结束后，均应上交实验报告。数据结构课程实验成绩单独考核，占1个学分。实验报告应包括如下内容：1、问题描述：简述题目要解决的问题是什么。2、设计：包括存储结构设计、主要算法设计等。用类C语言或用框图描述。3、调试报告：调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4、算法分析与改进：算法的时间复杂度和空间复杂度分析；算法改进的设想。5、经验和体会附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则结果要包含这些测试数据和运行输出，当然还可以含有其它测试数据和运行输出（有时需要多组数据）。四、实验时间16学时。

实验一线性表顺序存储结构一、实验目的1、掌握使用TurboC2.0/C++/VC环境上机调试线性表的基本方法；2、掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。二、实验要求1、认真阅读和掌握本实验的程序。2、上机运行本程序。3、保存和打印出程序的运行结果，并结合程序进行分析。4、按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、实验内容实验题目1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。程序如下(Turbo2.0环境下程序示例)：#include<stdio.h>#include<stdlib.h>//顺序表的定义#defineListSize100typedefstruct{ intdata[ListSize]; /*向量data用于存放表结点*/ intlength; /*当前的表长度*/}SeqList;voidmain(){ voidCreateList(SeqList*L,intn); voidPrintList(SeqList*L,intn); intLocateList(SeqList*L,intx); voidInsertList(SeqList*L,intx,inti); voidDeleteList(SeqList*L,inti);SeqListL; inti,x; intn=10; /*THELENGTHOFLIST*/ L.length=0; clrscr(); CreateList(&L,n); /*CREATTHELIST*/ PrintList(&L,n); /*PRINTTHELIST*/ printf("INPUTTHERESEARCHELEMENT"); scanf("%d",&x); i=LocateList(&L,x); printf("theresearchpositionis%d\n",i); /*顺序表查找*/ printf("inputthepositionofinsert:\n"); scanf("%d",&i); printf("inputthevalueofinsert\n"); scanf("%d",&x); InsertList(&L,x,i); /*顺序表插入*/ PrintList(&L,n); /*打印顺序表*/ printf("inputthepositionofdelete\n"); scanf("%d",&i); DeleteList(&L,i); /*顺序表删除*/ PrintList(&L,n); getch();/*打印顺序表*/}/*顺序表的建立：*/voidCreateList(SeqList*L,intn){inti;printf("pleaseinputnnumbers\n");for(i=1;i<=n;i++){scanf("%d",&L->data[i]);}L->length=n;}/*顺序表的打印：*/voidPrintList(SeqList*L,intn){inti;printf("thesqlistis\n");for(i=1;i<=n;i++)printf("%d",L->data[i]);}/*顺序表的查找：*/intLocateList(SeqList*L,intx){inti;for(i=1;i<=10;i++)if((L->data[i])==x)return(i);elsereturn(0);}/*顺序表的插入：*/voidInsertList(SeqList*L,intx,inti){intj;for(j=L->length;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->length++;}/*顺序表的删除：*/voidDeleteList(SeqList*L,inti){intj;for(j=i;j<=(L->length)-1;j++)L->data[j]=L->data[j+1];}实验题目2：集合求并说明：分别用两个线性表对集合进行表示，将其中一个集合并到另一个集合。程序如下（C＋＋/VC环境）#defineINITSIZE10#defineINCREASEMENT2#defineOVERFLOW-1#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#include"iostream.h"#include"stdio.h"#include"stdlib.h"#include"malloc.h"typedefintStatus;typedefcharElemType;typedefstruct{ ElemType*elem;intlength; intlistsize;}SqList;StatusInitList(SqList&L){ L.elem=(ElemType*)malloc(INITSIZE*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.length=0; L.listsize=INITSIZE; returnOK;}//InitListStatusListInsert(SqList&L,inti,ElemTypee){ if(L.length>=L.listsize){ L.elem=(ElemType*)realloc(L.elem,(L.listsize+INCREASEMENT)*sizeof(ElemType)); if(!L.elem)exit(OVERFLOW); L.listsize=L.listsize+INCREASEMENT; } L.elem[i]=e; L.length++; returnOK;}//ListInsertStatusCreateList(SqList&L){ ElemTypee; cin>>e; while(e!='!'){ L.elem[L.length++]=e; cin>>e; } returnOK;}//CreateListStatusGetElem(SqListL,inti,ElemType&e){ if(i<1||i>L.length)returnERROR; e=L.elem[i-1]; returnOK;}Statusequal(ElemTypea,ElemTypeb){ if(a==b)returnTRUE; elsereturnERROR;}//equalStatusElemLocate(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){ inti; for(i=1;i<=L.length;i++) if((*compare)(e,L.elem[i-1]))returnTRUE; returnERROR;}//ElemLocatevoidUnion(SqListLa,SqListLb,SqList&Lc){ inti,j,k; i=j=k=0; ElemTypea,b; while(i<La.length){ GetElem(La,i+1,a);i++; ListInsert(Lc,k++,a); } while(j<Lb.length){ GetElem(Lb,j+1,b);j++; if(!(ElemLocate(La,b,equal))) ListInsert(Lc,k++,b); } return;}voidmain(void){ SqListLa,Lb,Lc; InitList(La); InitList(Lb); InitList(Lc); cout<<"PleaseCreateListA:\n"; CreateList(La); cout<<"ShowtheendA:\n"; inti; for(i=0;i<La.length;i++) cout<<La.elem[i]<<''; cout<<'\n'; cout<<"PleaseCreateListB:\n"; CreateList(Lb); cout<<"ShowtheendB:\n"; for(i=0;i<Lb.length;i++) cout<<Lb.elem[i]<<''; cout<<"\n"; Union(La,Lb,Lc); cout<<"ShowtheendC:\n"; for(i=0;i<Lc.length;i++) cout<<Lc.elem[i]<<''; cout<<"\n";getchar(); return;}//main实验题目3：报数问题编号为1，2，···，n的n个人围坐在一圆桌旁，从第s个人开始报数，报到第m的人退席，下一个人又重新从1开始报数，依此重复，直至所有的人都退席。例如，设s=1，m=4，n=8，则退席的人的编号依次为4，8，5，2，1，3，7，6。1、存储结构（1）以顺序表为存储结构（2）以循环链表为存储结构typedefstructlnode{intdata;structlnode*next;}lnode；2、算法设计（1）voidjosephus_1(intp[],intm,intn){inti,j,t;for(i=0;i<=n-1;i++)p[i]=i+1;//p[0]..p[n-1]：n个人t=0;//第一次报数的位置(第一人的位置)for(i=n;i>=1;i--){t=(t+m-1)%i;//t：定位于第m人，i：当前圆桌上的人数，%：实现环（圆桌）的处理cout<<p[t]<<"";//输出第m人信息（第m人报数）for(j=t+1;j<=i-1;j++)p[j-1]=p[j];//元素前移（第m人退席，删除第m人）}}（2）voidjosephus_2(lnode*r,intm,intn){//r：（不带头结点的）单向循环链表的尾指针Lnode*p=r;//p：指向尾指针

for(i=1;i<=n;++i){for(j=1;j<=m-1;++j)p=p->next;//p后移m-1次，定位于m-1处（要退席的人之前）s=p->next;//s定位于m人（要退席的人）cout<<p->data<<"";//第m人报数p->next=s->next;deletes;//第m人退席，删除第m人 }}

实验二链表应用一、实验目的1．掌握握单链表的基本操作：插入、删除、查找等运算。二、实验要求1．认真阅读和掌握本实验的程序。2．上机运行本程序。3．保存和打印出程序的运行结果，并结合程序进行分析。4．按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、实验内容实验题目1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下：#include<malloc.h>typedefstructnode{intdata;structnode*next;}NODE;/******************************************/NODE*Create(){ NODE*p,*head; intx; head=(NODE*)malloc(sizeof(NODE)); head->next=NULL; printf("Inputdata,-1toEnd!\n"); scanf("%d",&x); while(x!=-1){ p=(NODE*)malloc(sizeof(NODE)); p->data=x; p->next=head->next; head->next=p; scanf("%d",&x); } return(head);}/******************************************/voidOutput(NODE*head){NODE*p;p=head;printf("BegintodumptheLinkList...\n");while(p->next!=NULL){ printf("->%d",p->next->data); p=p->next;}printf("\nTheLinkListended!\n");}/******************************************/intListlen(NODE*head){inti=0;NODE*p=head;while(p->next!=NULL){i++;p=p->next;}return(i);}/******************************************/intGet(NODE*head,inti){intj=0;NODE*p=head;while(p->next&&j<i){j++;p=p->next;}if(!p->next||j>i)return(0);elsereturn(p->data);}/******************************************/voidDel(NODE*head,inti){NODE*p=head;intj=0;while(p->next&&j<i-1){j++;p=p->next;}if(!p->next||j>i-1)printf("thepositioniswrong\n");elsep->next=p->next->next;}/******************************************/voidIns(NODE*head,inti,inte){NODE*p=head,*q;intj=0;while(p->next&&j<i-1){j++;p=p->next;}if(!p->next&&j>i-1)printf("Wrongposition\n");else{q=(NODE*)malloc(sizeof(NODE));q->data=e;q->next=p->next;p->next=q;}}/******************************************/main(){NODE*head;intlength;inti,element;clrscr();head=Create();Output(head);length=Listlen(head);printf("thelengthofthelinkis%d\n",length);printf("inputtheorder:\n");scanf("%d",&i);element=Get(head,i);printf("theelementoftheorderis%d\n",element);printf("inputthedelposition\n");scanf("%d",&i);Del(head,i);Output(head);printf("Inputtheinsertposionandelement:\n");scanf("%d%d",&i,&element);Ins(head,i,element);Output(head);getch();}}实验题目2：线性表归并的链式表示实现（C＋＋/VC环境）#defineOK1#defineERROR0#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"iostream.h"typedefintstatus;typedefintElemType;typedefstructLNode{ ElemTypedata; structLNode*next;}LNode,*LinkList;statusInitList(LinkList&L){L=(LinkList)malloc(sizeof(LNode)); if(!L)exit(-2); L->next=NULL; returnOK;}//InitListvoidCreateList(LinkList&L,intn){ inti;LNode*p,*q; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL;q=L; for(i=0;i<n;++i){ p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=p; }q->next=NULL;}//CreateListstatusMergesort(LinkList&A,LinkList&B,LinkList&C){ LNode*Pa,*Pb;Pa=A->next;Pb=B->next;while(Pa&&Pb){if(Pa->data<Pb->data){A->next=Pa->next;//把Pa结点从链表A中删除Pa->next=C->next;C->next=Pa;//把*Pa逆位序加入链表CPa=A->next;//取链表A的下一个结点}else{B->next=Pb->next;//把Pb结点从链表B中删除Pb->next=C->next;C->next=Pb;//把*Pb逆位序加入链表CPb=B->next;//取链表B的下一个结点}}while(Pa){A->next=Pa->next;//把Pa结点从链表A中删除Pa->next=C->next;C->next=Pa;//把*Pa逆位序加入链表CPa=A->next;//取链表A的下一个结点}while(Pb){B->next=Pb->next;//把Pb结点从链表B中删除Pb->next=C->next;C->next=Pb;//把*Pb逆位序加入链表CPb=B->next;//取链表B的下一个结点}free(A);free(B);returnOK;}voidmain(void){ LinkListLa,Lb,Lc; LNode*p; InitList(La); InitList(Lb); InitList(Lc); cout<<"InputListA:\n"; CreateList(La,5); cout<<"InputListB:\n"; CreateList(Lb,3); Mergesort(La,Lb,Lc); p=Lc->next; while(p){ cout<<p->data<<''; p=p->next; }getchar();//等待，查看结束敲任意键。}实验题目3：一元多项式四则算数运算有两个指数递减的一元多项式，写一程序先求这两个多项式的和，再求它们的积。提示：用带表头结点的单链表作为多项式的存储表示；要建立两个单链表；多项式相加就是要把一个单链表中的结点插入到另一个单链表中去，要注意插入、删除操作中指针的正确修改。

实验三利用栈实现递归一、实验目的掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求1．认真阅读和掌握本实验的算法。2．上机将本算法实现。3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容实验题目1:进制转换利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要Ｘ不为０重复做下列动作将Ｘ％Ｒ入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素参考程序1（Turbo2.0环境）：#defineMAXSIZE100#include<stdlib.h>structstack{intdata[MAXSIZE];inttop;};voidinit(structstack*s){s->top=-1;}intempty(structstack*s){if(s->top==-1)return1;elsereturn0;}voidpush(structstack*s,inti){if(s->top==MAXSIZE-1){printf("Stackisfull\n");return;}s->top++;s->data[s->top]=i;}intpop(structstack*s){if(empty(s)){printf("stackisempty"); return-1;}return(s->data[s->top--]);}voidtrans(intnum){structstacks;intk;init(&s);while(num){k=num%16;push(&s,k);num=num/16;}while(!empty(&s)){k=pop(&s);if(k<10)printf("%d",k);elseprintf("%c",k+55);}printf("\n");}main(){intnum;clrscr();printf("Inputanum,-1toquit:\n");scanf("%d",&num);while(num!=-1){trans(num);scanf("%d",&num);}}参考程序2：（C＋＋/VC环境）#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineOVERFLOW-1#defineOK1#defineSTACKINCREMENT10//存储空间分配增量#defineERROR0#defineTRUE1#defineFALSE0#include"stdio.h"#include"stdlib.h"#include"malloc.h"#include"iostream.h"typedefintstatus;typedefcharSElemType;typedefstruct{//顺序栈的定义SElemType*base;SElemType*top;intstacksize;}SqStack;statusInitStack(SqStack&S){//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}statusPush(SqStack&S,SElemTypee){ //插入元素e为新世界的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}statusPop(SqStack&S,SElemType&e){ //若栈不空，则删除S的栈顶元素，用e反回其值，并返回OK；否则返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}statusStackEmpty(SqStackS){//判断栈S是否已满if(S.top==S.base)returnTRUE;elsereturnFALSE;}voidconversion(){ //对于输入的任意一个非负十进制整数，打印输出与其等值的对应的进制数SqStackS;intN,d;SElemTypex,e;intys;InitStack(S);//构造空栈cin>>N;//输入一个任意的非负十进制数cin>>d;//输入要打印出的进制while(N){//输出相应的符号ys=N%d;//求余 if(ys<=9)x=ys+'0';elsex=ys-10+'A';Push(S,x);N=N/d;}while(!StackEmpty(S)){//显示结果Pop(S,e);cout<<e;}}voidmain(){conversion();}实验题目2：魔王语言解释问题描述有一个魔王总是使用自已的一种非常精练而抽象的语言讲话，没有人能听得懂。但他的语言是可以逐步解释成人能懂的语言的，因为他的语言是由以下两种形式的规则由人的语言逐步抽象上去的：（1）α→β1β2…βm（2）(θβ1β2…βm)→(θβm…β2θβ1θ)在这两种形式中，从左到右均表示解释；从右到左均表示抽象。写一个魔王解释程序，将魔王的话解释成人能听懂的话。基本要求：设大写字母表示魔王语言的词汇，小写字母表示人的词汇，希腊字母表示可以用大写字母或小写字母代换的变量。用下述两种规则和下述规则（2）实现。(1)B→tAdA(2)A→sae测试数据：B(einxgz)BB(einxgz)B=>tAdA(einxgz)tAdA=>tsaedsae(einxgz)tsaedsae=>tsaedsaeezegexeneietsaedsae字母-汉字对应表:tdsaezgxni天在上一个鹅追赶下蛋恨则魔王说的是：“天上一个鹅地上一个鹅鹅追鹅赶鹅下鹅蛋鹅恨鹅天上一个鹅地上一个鹅”。提示：该题中涉及栈、队列和线性表。（１）利用队列处理B：tsaedsae（由B→tAdA,A→sae得）（2）利用栈处理：(θβ1β2…βm)→(θβm…β2θβ1θ)（３）利用线性表（字母-汉字对应表）进行魔王语言解释。实验题目3：迷宫最短路径1、问题描述：从一个迷宫的入口到出口找出一条最短路经。用一个二维数组MAZE(1：m，1：n)模拟迷宫，数组元素为0表示该位置可以通过，数组元素为1表示该位置不可以通行。MAZE(1，1)和MAZE(m，n)分别为迷宫的入口和出口。2、基本要求输入数据输入迷宫的大小m行和n列，两者为整数由随机数产生0或1，建立迷宫。输出数据首先输出模拟迷宫的二维数组，若存在最短路经，则由出口回朔到入口打印这一条路径，如下所示：(m，n)，……，(I，j)，……，(1，1)如无通道，则打印：THEREISNOPATH.3、实现提示数据结构a）为了在程序中判断方便，把迷宫扩展成为MAZE(0：m+1，0：n+1)，扩展部分的元素设置为1，相当于在迷宫周围布上一圈不准通过的墙，这样，在迷宫的任一位置(I，j)上都有八个可以移动的方向。b）用二维数组MOVE(1：8，1：2)存放八个方向上的位置量，如图所示：(I+MOVE[1，1]，j+MOVE[1，2])(I+MOVE[8，1]，j+MOVE[8，2])(I+MOVE[1，1]，j+MOVE[1，2])(I+MOVE[7，1]，j+MOVE[7，2])(I+MOVE[3，1]，j+MOVE[3，2])(I+MOVE[6，1]，j+MOVE[6，2])(I+MOVE[4，1]，j+MOVE[4，2])(I+MOVE[5，1]，j+MOVE[5，2])MOVE的设置情况Ij121-102-1130141151061-170-18-1-1为了标志已经通过的位置，采用一个标志数组MARK（1..m，1..n）初值为0，在寻找路径的过程中，若通过了位置（I，j），则将MARK（I，J）置为为1。为了记录查找过程中到达位置及其前一位置，建立一个Q（1..m*n-1，0..2）数组，对于某一个数组元素Q(P)，其中，Q(P，0)和Q(P，1)记下到达位置I和j，Q(P，2)记下其出发点在Q数组中的下标。（2）算法基本思想将入口（1，1）作为第一个出发点，依次在八个反方向上搜索可通行的位置，形成第一层新的出发点，然后对第一层中各个位置分别搜索他所在八个方向上的可通行位置，形成第二层新的出发点，…，如此进行下去，直至达到出口(m，n)或者迷宫所有位置都搜索完毕为止。具体实施：从(m，n)开始，将其记入Q数组，比如记入Q(1)，以它作为第一个出发点，依次对八个方向进行搜索，若下一个位置(I，j)可通行并且尚未经过（即MAZE(I，j)=0且MARK(I，j)=0），则记入Q数组，如记在Q(P)，则在Q(P，2)中要记下其出发点在Q数组中的下标1，在八个方向上都搜索过以后，根据先进先出的原则Q从数组中重新取出一个位置作为新的出发点（这里，我们实际上把Q数组作为一个顺序表示的队列），重复以上过程，若能达到位置(m，n)，表示找到最短路径；若Q数组中已经没有位置可以作为新的出发点了，则表示迷宫没有通路。

实验四链队列应用一、实验目的掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。二、实验要求1．认真阅读和掌握本实验的算法。2．上机将本算法实现。3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容实验题目1：利用队列的基本操作实现杨辉三角的输出算法如下：voidout_number(intn);{init_queue(Q);printf(1);en_queue(Q,s1+s2);for(I=2;I<=n;I++){s1=0;for(j=1;j<=I-1;j++){s2=out_queue(Q);printf(s2);en_queue(q,s1+s2);s1=s2;}printf(1);en_queue(Q,1+s2);}参考程序如下typedefstruct{int*data;intfront;intrear;}sqqueue;main(){inti,j,m,s1=0,s2=1;sqqueueq;clrscr();q.data=(int*)malloc(100*sizeof(int));q.rear=q.front=0;q.data[q.rear]=s2;q.rear++;printf("%40d",s2);for(i=2;i<=8;i++){s1=0;for(m=1;m<=40-i;m++)printf("%c",'');for(j=1;j<=i-1;j++){s2=q.data[q.front];q.front++;printf("%d",s2);q.data[q.rear]=s1+s2;q.rear++;s1=s2;}printf("%d\n",1);q.data[q.rear]=1+s2;q.rear++;}}

实验五数组的基本操作（不属实验大纲要求内容）一、实验目的回顾c语言中数组的定义和基本应用二、实验要求1．认真阅读和掌握本实验的程序。2．上机运行本程序。3．保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容有M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩参考程序：#defineM5 #defineN4 #include"stdio.h"main(){inti,j;staticfloatscore[M+1][N+1]={{78,85,83,65},{88,91,89,93},{72,65,54,75},{86,88,75,60},{69,60,50,72}};for(i=0;i<M;i++){for(j=0;j<N;j++) {score[i][N]+=score[i][j]; score[M][j]+=score[i][j]; }score[i][N]/=N;}for(j=0;j<N;j++)score[M][j]/=M; clrscr();printf("学生编号课程1课程2课程3课程4个人平均\n");for(i=0;i<M;i++){printf("学生%d\t",i+1);for(j=0;j<N+1;j++)printf("%6.1f\t",score[i][j]);printf("\n");}for(j=0;j<8*(N+2);j++)printf("-");printf("\n课程平均");for(j=0;j<N;j++)printf("%6.1f\t",score[M][j]);printf("\n");getch();}

实验六二叉树遍历一、实验目的1．进一步掌握指针变量的含义。2．掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3．掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1．认真阅读和掌握本实验的程序。2．上机运行本程序。3．保存和打印出程序的运行结果，并结合程序进行分析。4．按照你二叉树的操作需要，重新改写主程序以及完成相应遍历运算并运行，打印出文件清单和运行结果三、实验内容程序1：按先序次序输入二叉树中结点的值（一个字符），`ø`表示空树，生成二叉树的二叉链表存储结构，a为指向根结点的指针。然后按中序顺序遍历二叉树。算法思想：先访问左子树,再访问根结点,最后访问右子树参考程序如下：#defineNULL0typedefstructstu{chardata;structstu*left,*right;}sn;sn*Create(sn*a){charch;scanf("%c",&ch);if(ch=='')a=NULL;else{a=(sn*)malloc(sizeof(sn));if(!a)printf("yuguyuy");a->data=ch;a->left=Create(a->left);a->right=Create(a->right);}return(a);}voidinc(sn*b){if(b){inc(b->left);printf("%c",b->data);inc(b->right);}}main(){sn*t,*q;q=NULL;t=Create(q);inc(t);printf("\n");getch();}实验数据：abcøødeøgøøføøø(ø表示空格)

实验七图的遍历一．实验目的1．掌握图的基本存储方法。2．掌握有关图的操作算法并用高级语言编程实现；3．熟练掌握图的两种搜索路径的遍历方法。二．实验要求1．认真阅读和掌握本实验的算法。2．上机将本算法实现。3．保存和打印出程序的运行结果，并结合程序进行分析。4．按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三．实验内容实验题目1：简单图遍历以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。算法如下：深度优先遍历的递归算法（1）深度优先遍历算法intvisited[MaxVertexNum]；//访问标志向量是全局量voidDFSTraverse(ALGraph*G){//深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同inti；for(i=0;i<G->n;i++)visited[i]=FALSE；//标志向量初始化for(i=0;i<G->n；i++)if(!visited[i])//vi未访问过DFS(G，i)；//以vi为源点开始DFS搜索}//DFSTraverse（2）邻接表表示的深度优先搜索算法voidDFS(ALGraph*G，inti){//以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode*p；printf("visitvertex：％c"，G->adjlist[i].vertex)；//访问顶点vivisited[i]=TRUE；//标记vi已访问p=G->adjlist[i].firstedge；//取vi边表的头指针while(p){//依次搜索vi的邻接点vj，这里j=p->adjvexif(!visited[p->adjvex])//若vi尚未被访问DFS(G，p->adjvex);//则以Vj为出发点向纵深搜索p=p->next；//找vi的下一邻接点}}//DFS#defineMaxVertexNum5#definem5#defineNULL0typedefstructnode{intadjvex;structnode*next;}JD;typedefstructtnode{intvexdata;JD*firstarc;}TD;typedefstruct{TDag[m];intn;}ALGRAPH;voidDFS(ALGRAPH*G,inti);voidcreat(ALGRAPH*G){inti,m1,j;JD*p,*p1;printf("pleaseinputthenumberofgraph\n");scanf("%d",&G->n);for(i=0;i<G->n;i++){printf("pleaseinputtheinfoofnode%d",i);scanf("%d",&G->ag[i].vexdata);printf("pleaseinputthenumberofarcswhichadjto%d",i);scanf("%d",&m1);printf("pleaseinputtheadjvexpositionofthefirstarc\n");p=(JD*)malloc(sizeof(JD));scanf("%d",&p->adjvex);p->next=NULL;G->ag[i].firstarc=p;p1=p;for(j=2;j<=m1;j++){printf("pleaseinputthepositionofthenextarcvexdata\n");p=(JD*)malloc(sizeof(JD));scanf("%d",&p->adjvex);p->next=NULL;p1->next=p;p1=p;}}}intvisited[MaxVertexNum];voidDFSTraverse(ALGRAPH*G){inti;for(i=0;i<G->n;i++)visited[i]=0;for(i=0;i<G->n;i++)if(!visited[i])DFS(G,i);}/*DFSTraverse*/voidDFS(ALGRAPH*G,inti){JD*p;printf("visitvertex:%d->",G->ag[i].vexdata);visited[i]=1;/*标记vi已访问*/p=G->ag[i].firstarc;/*取vi边表的头指针*/while(p){/*依次搜索vi的邻接点vj，这里j=p->adjvex*/if(!visited[p->adjvex])/*若vi尚未被访问*/DFS(G,p->adjvex);/*则以Vj为出发点向纵深搜索*/p=p->next;}}/*DFS*/main(){ALGRAPH*G;printf("下面以临接表存储一个图；\n");creat(G);printf("下面以深度优先遍历该图\n");DFSTraverse(G);getch();}实验题目2：交通问题系统问题描述：已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：（1）是否有公共汽车到达指定的目的地?（2）若有，告诉乘车路线。如需中途换车，应指示在哪里换车1、基本要求：数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。其中，a[I，j].go>0表示第i条线路上，向站j去方向的下一站号；a[i，j].back>0表示第i条线路上，站j回来的下一站号。若站j不在第i条线路上，a[i，j].go和a[i，j].back均为0。另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。对所采用的算法进行算法分析实现提示假定顶点编号为1..n，数据结构采用连接结构。设置表头数组为head[1..n]，head[i]包含站i的名字和一指针，该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域：一个站号域，两个指针域。一个指针指向i的下一个邻接顶点，另一个指针指向从i到该结点的所有线路号组成的链表。(2)如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。

附参考实验报告附1《数据结构》实验报告规范1．实验内容实验具体题目及需要完成的主要内容及功能。2．实验目的通过本次实验，主要完成对什么知识及内容的掌握和领会，主要学会什么技术以及知识应用。3．需求分析以无歧义的陈述说明程序设计的任务，强调的是程序要做什么？并明确规定：(1)输入的形式和输入值的范围；(2)输出的形式；(3)程序所能达到的功能；(4)测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。4．概要设计说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。5．详细设计实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；画出函数和过程的调用关系图。6．调试分析内容包括：a．调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；b．算法的时空分析(包括基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想；c．经验和体会等。7．用户使用说明说明如何使用你编写的程序，详细列出每一步的操作步骤。8．测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。附录带注释的源程序。如果提交源程序软盘，可以只列出程序文件名的清单。值得注意的是，实习报告的各种文档资料，如：上述中的前三部分要在程序开发的过程中逐渐充实形成，而不是最后补写。附2实验报告范例一实验内容编写一个程序，采用一棵二叉树表示一个家谱关系。要求程序具有如下功能：1：用括号表示法输出家谱二叉树，2：查找某人的所有儿子，3：查找某人的所有祖先。二实验目的1：进一步掌握指针变量的含义及应用。2：掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3：掌握用指针类型描述、访问和处理二叉树的运算。三需求分析该实验由主函数、家谱建立函数、家谱输出函数、儿子查找函数、祖先查找函数、结点定位函数、选择界面函数七个函数共同组成。其功能描述如下：主函数：统筹调用各个函数以实现相应功能家谱建立函数：与用户交互建立家族成员对应关系家谱输出函数：用括号表示法输出家谱，其形式为：父和母（子1和子妻1（孙1），子2和子妻2（孙2））儿子查找函数：在家谱中查找到某人所有的子女并输出，同时也能辨别出其是否为家族成员与是否有子女祖先查找函数：在家谱中查找到某人所有的祖先并输出，同时也能辨别出其是否为家族中成员。结点定位函数：在家谱中找到用户输入人名所对应的结点。选择界面函数：为便于编写程序，将用户选择部分独立为此函数。四概要设计数据结构与存储关系图根据题目要求，采用二叉树型存储结构。其结点定义为：typedefstructSNODE{charname[MAX];//人名structSNODE*left;//指向配偶结点structSNODE*right;//指向兄弟或子女结点}FNODE;为了能够用二叉树表示配偶、子女、兄弟三种关系，特采用以下存储关系，则能在二叉树上实现家谱的各项运算。1voidInitialFamily(FNODE*&head)//家谱建立函数2voidPrintFamily(FNODE*head)//家谱输出函数3FNODE*findnode(FNODE*b,charp[])//结点定位函数4voidFindSon(FNODE*b,charp[])//儿子查找函数5intFindAncestor(FNODE*head,charson[])//祖先查找函数五详细设计（注：此部分请用类C语言完成）（一）voidInitialFamily(FNODE*&head)//家谱建立函数1：首先建立当前人的信息，将其左右结点置为空，2：然后让用户确定其是否有配偶，如果没有配偶，则当前程序结束，3：如果有则建立其配偶信息，并将配偶结点赋给当前人的左结点；4：再让用户确定其是否有子女，如果有则递归调用家谱建立函数建立子女结点，并将其赋给配偶结点的下一个右结点。5：如无，则程序结束（二）voidPrintFamily(FNODE*head)//家谱输出函数1：首先判断当前结点是否为空，如果为空则结束程序；2：如果不为空，则输出当前结点信息，3：然后判断其左结点（配偶结点）是否为空，如不为空则输出“和配偶信息。4：再判断配偶结点的右结点是否为空，如不为空则递归调用输出其子女信息，最后输出“）”；5：当配偶结点为空时，则判断其右结点（兄弟结点）是否为空6：如果不为空，则输出“，”，并递归调用输出兄弟信息7程序结束（三）FNODE*findnode(FNODE*b,charp[])//结点定位函数1：当前结点是否为空，为空则返回空；2：如果和查找信息相同，则返回当前结点；3：如不然，则先后递归访问其左结点，再不是则递归访问右结点（四）voidFindSon(FNODE*b,charp[])//儿子查找函数1：在家谱中定位到要查找的结点，如无则输出“查找不到此人”2：判断其配偶结点与子女结点是否为空，为空则输出“无子女”3：不为空则输出其配偶结点的所有右结点（子女结点）。（五）intFindAncestor(FNODE*head,charson[])//祖先查找函数1：先在家谱中定位到要查找的结点，如为空输出“不存在此人”，程序结束2：先将父母结点入栈，当栈为空时程序结束，3：栈不为空时，判断栈顶元素是否已访问过，4：访问过，再判断是否为查找结点，如是则输出栈中保存的其祖先结点，并滤过其兄弟结点不输出；不是查找结点，则退栈一个元素5：未访问过，则取当前栈顶元素，置访问标志——1，同时取其右结点6：栈不为空或当前所取结点不为空时，转到2；六调试分析（略）七用户使用说明（略）八实验测试结果及结果分析1测试结果2结果分析（略）附录实验程序代码程序定义部分：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAX20typedefstructSNODE{charname[MAX];//人名structSNODE*left;//指向配偶结点structSNODE*right;//指向兄弟或子女结点}FNODE;//家谱建立函数voidInitialFamily(FNODE*&head){FNODE*s,*r,*q;inttag;q=(FNODE*)malloc(sizeof(FNODE)); q=NULL; s=(FNODE*)malloc(sizeof(FNODE)); printf("输入姓名:\n"); scanf("%s"，,s->name); s->left=s->right=NULL; head=r=s; printf("%s是否有配偶?有1,无0\n",head->name);//建立配偶结点 scanf("%d",&tag); if(tag) { s=(FNODE*)malloc(sizeof(FNODE)); printf("输入其配偶姓名:\n"); scanf("%s",s->name); s->left=s->right=NULL;r->left=s; r=s; do{//递归调用建立孩子结点 printf("%s是否还有子女?有1,无0\n",head->name); scanf("%d",&tag); if(tag) { InitialFamily(q); r->right=q; r=q; } }while(tag); }}//家谱输出部分voidPrintFamily(FNODE*head){FNODE*s; if(head!=NULL) { printf("%s",head->name);//不为空时输出当前结点 if(head->left!=NULL)//输出配偶结点 {s=head->left; printf("和%s(",s->name); PrintFamily(s->right);