数据结构试验报告格式.doc

数据结构实验指导书实验一（实验题目：顺序表。实验时间：11月5日）一、 实验目的1、 掌握使用Turbo C2.0上机调试线性表的基本方法；2、 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、 实验要求1、 认真阅读和掌握本实验的程序。2、 上机运行本程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、 实验内容程序1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。 程序如下：#include #include /*顺序表的定义：*/#define ListSize 100typedef structint dataListSize;/*向量data用于存放表结点*/int length;/*当前的表长度*/SeqList;void main()void CreateList(SeqList *L,int n);void PrintList(SeqList *L,int n);int LocateList(SeqList *L,int x);void InsertList(SeqList *L,int x,int i);void DeleteList(SeqList *L,int i); SeqList L;int i,x;int n=10;/*THE LENGTH OF LIST*/L.length=0;clrscr();CreateList(&L,n);/*CREAT THE LIST*/PrintList(&L,n);/*PRINT THE LIST*/printf(INPUT THE RESEARCH ELEMENT);scanf(%d,&x);i=LocateList(&L,x);printf(the research position is %dn,i);/*顺序表查找*/printf(input the position of insert:n);scanf(%d,&i);printf(input the value of insertn);scanf(%d,&x);InsertList(&L,x,i);/*顺序表插入*/PrintList(&L,n);/*打印顺序表*/printf(input the position of deleten);scanf(%d,&i);DeleteList(&L,i);/*顺序表删除*/PrintList(&L,n);getch();/*打印顺序表*/*顺序表的建立：*/void CreateList(SeqList *L,int n)int i;printf(please input n numbersn);for(i=1;idatai);L-length=n;/*顺序表的打印：*/void PrintList(SeqList *L,int n)int i;printf(the sqlist isn);for(i=1;idatai);/*顺序表的查找：*/int LocateList(SeqList *L,int x)int i;for(i=1;idatai)=x) return(i); else return(0);/*顺序表的插入：*/void InsertList(SeqList *L,int x,int i)int j;for(j=L-length;j=i;j-)L-dataj+1=L-dataj;L-datai=x;L-length+;/*顺序表的删除：*/void DeleteList(SeqList *L,int i) int j;for(j=i;jlength)-1;j+)L-dataj=L-dataj+1;五、调试心得。实验二 单链表操作（实验题目：链表。实验时间：11月12日）一、 实验目的1 掌握握单链表的基本操作：插入、删除、查找等运算。二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下： #includetypedef struct node int data; struct node *next; NODE;/*/NODE *Create()NODE *p,*head;int x;head=(NODE *)malloc(sizeof(NODE);head-next=NULL;printf(Input data,-1 to End!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);/*/void Output(NODE *head) NODE *p; p=head; printf(Begin to dump the LinkList.n); while(p-next!=NULL) printf(-%d,p-next-data); p=p-next; printf(nThe LinkList ended!n);/*/int Listlen(NODE *head) int i=0; NODE *p=head; while(p-next!=NULL) i+; p=p-next; return(i);/*/int Get(NODE *head,int i)int j=0;NODE *p=head;while(p-next&jnext;if(!p-next|ji) return(0);else return(p-data);/*/void Del(NODE *head,int i)NODE *p=head;int j=0;while(p-next&jnext;if(!p-next|ji-1) printf(the position is wrongn);elsep-next=p-next-next;/*/void Ins(NODE *head,int i,int e)NODE *p=head,*q;int j=0;while(p-next&jnext;if(!p-next&ji-1) printf(Wrong positionn );else q=(NODE *)malloc(sizeof(NODE); q-data=e; q-next=p-next; p-next=q;/*/main() NODE *head; int length; int i,element; clrscr(); head=Create(); Output(head); length=Listlen(head); printf(the length of the link is %dn,length); printf(input the order :n); scanf(%d,&i); element=Get(head,i); printf(the element of the order is %dn,element); printf(input the del position n); scanf(%d,&i); Del(head,i); Output(head); printf(Input the insert posion and element:n); scanf(%d%d,&i,&element); Ins(head,i,element); Output(head); getch(); 四、调试心得。实验三 栈的基本操作（实验题目：栈的基本操作。实验时间：11月19日）一、 实验目的掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要不为重复做下列动作将入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素参考程序：#define MAXSIZE 100#includestruct stack int dataMAXSIZE; int top;void init(struct stack *s) s-top=-1;int empty(struct stack *s) if(s-top=-1) return 1; else return 0; void push(struct stack *s,int i) if(s-top=MAXSIZE-1) printf(Stack is fulln); return; s-top+; s-datas-top=i;int pop(struct stack *s) if(empty(s) printf(stack is empty); return -1; return(s-datas-top-);void trans(int num) struct stack s; int k; init(&s); while(num) k=num%16; push(&s,k); num=num/16; while(!empty(&s) k=pop(&s); if(k10) printf(%d,k); else printf(%c,k+55); printf(n);main() int num; clrscr(); printf(Input a num,-1 to quit:n); scanf(%d,&num); while(num!=-1) trans(num); scanf(%d,&num); 四、调试心得。实验四 队列的基本操作（实验题目：队列的基本操作。实验时间：11月26日）一、 实验目的掌握队列的基本操作：初始化队列、判队列为空、出队列、入队列等运算。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容利用队列的基本操作实现杨辉三角的输出算法如下：void out_number(int n);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);参考程序如下typedef structint *data;int front;int rear;sqqueue;main()int i,j,m,s1=0,s2=1;sqqueue q;clrscr();q.data=(int *)malloc(100*sizeof(int);q.rear=q.front=0;q.dataq.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.dataq.front;q.front+;printf(%d ,s2);q.dataq.rear=s1+s2;q.rear+;s1=s2;printf(%dn,1);q.dataq.rear=1+s2;q.rear+;四、调试心得。实验五 数组的基本操作（实验题目：数组的基本操作。实验时间：12月3日）一、 实验目的回顾c语言中数组的定义和基本应用二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。 三、 实验内容有M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩参考程序：#define M 5#define N 4#include stdio.hmain() int i,j; static float scoreM+1N+1=78,85,83,65, 88,91,89,93, 72,65,54,75,86,88,75,60, 69,60,50,72; for(i=0;iM;i+) for(j=0;jN;j+) scoreiN += scoreij; scoreMj += scoreij; scoreiN /= N; for(j=0;jN;j+) scoreMj /= M; clrscr();printf(学生编号 课程1 课程2 课程3 课程4 个人平均n);for(i=0;iM;i+) printf(学生%dt,i+1); for(j=0;jN+1;j+) printf(%6.1ft,scoreij); printf(n); for(j=0;j8*(N+2);j+) printf(-); printf(n课程平均); for(j=0;jdata=ch;a-left=Create(a-left);a-right=Create(a-right);return(a);void inc(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();实验数据：abc00de0g00f000(0表示空格)四、调试心得。实验七 图的操作（实验题目：图的操作。实验时间：12月24日，12月31日）一实验目的1 掌握图的基本存储方法。2 掌握有关图的操作算法并用高级语言编程实现；3 熟练掌握图的两种搜索路径的遍历方法。二实验要求1 认真阅读和掌握本实验的算法 。2 上机将本算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对图的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三实验内容以邻接矩阵和邻接表的方式存储连通图。然后分别用深度优先算法遍历邻接矩阵方式存储的图和邻接表方式存储的图。算法 如下：深度优先遍历的递归算法 （1）深度优先遍历算法 int visitedMaxVertexNum； /访问标志向量是全局量void DFSTraverse(ALGraph *G) /深度优先遍历以邻接表表示的图G，而以邻接矩阵表示G时，算法完全与此相同int i；for(i=0;in;i+)visitedi=FALSE； /标志向量初始化for(i=0;in；i+)if(!visitedi) /vi未访问过DFS(G，i)； /以vi为源点开始DFS搜索/DFSTraverse（2）邻接表表示的深度优先搜索算法void DFS(ALGraph *G，int i) /以vi为出发点对邻接表表示的图G进行深度优先搜索EdgeNode *p；printf(visit vertex：c，G-adjlisti.vertex)；/访问顶点vivisitedi=TRUE； /标记vi已访问p=G-adjlisti.firstedge； /取vi边表的头指针while(p)/依次搜索vi的邻接点vj，这里j=p-adjvexif (!visitedp-adjvex)/若vi尚未被访问DFS(G，p-adjvex);/则以Vj为出发点向纵深搜索p=p-next； /找vi的下一邻接点/DFS#define MaxVertexNum 5#define m 5#define NULL 0typedef struct node int adjvex;struct node *next;JD;typedef struct tnode int vexdata; JD *firstarc;TD;typedef structTD agm;int n;ALGRAPH;void DFS(ALGRAPH *G,int i);void creat(ALGRAPH *G)int i,m1,j;JD *p,*p1;printf(please input the number of graphn);scanf(%d,&G-n);for(i=0;in;i+)printf(please input the info