数据结构实验指导书实验一（实验题目：顺序表。实验时间：11月 5 日）一、 实验目的1、 掌握使用 Turbo C2.0 上机调试线性表的基本方法；2、 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、 实验要求1、 认真阅读和掌握本实验的程序。2、 上机运行本程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照你对线性表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、 实验内容程序 1：线性表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。程序如下：#include #include /*顺序表的定义：*/ #define ListSize 100 typedef struct int 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*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - - - - - - - - - /*顺序表的插入：*/ 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; 五、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 实验二单链表操作（实验题目：链表。实验时间：11 月 12 日）一、 实验目的1 掌握握单链表的基本操作：插入、删除、查找等运算。二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序 1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下： #include typedef 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 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+; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - 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); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - else p-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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - - - - - - - - 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(); 四、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - 实验三 栈的基本操作（实验题目：栈的基本操作。实验时间：11 月 19 日）一、 实验目的掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数 X 和 R 作为形参初始化栈只要不为重复做下列动作将入栈X=X/R 只要栈不为空重复做下列动作栈顶出栈输出栈顶元素参考程序：#define MAXSIZE 100 #include struct stack int dataMAXSIZE; int top; ; void init(struct stack *s) s-top=-1; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 21 页 - - - - - - - - - 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-); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 21 页 - - - - - - - - - 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(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - printf(Input a num,-1 to quit:n); scanf(%d,&num); while(num!=-1) trans(num); scanf(%d,&num); 四、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 21 页 - - - - - - - - - 实验四 队列的基本操作（实验题目：队列的基本操作。实验时间：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 struct int *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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - 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+; 四、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - - - - - - 实验五数组的基本操作（实验题目：数组的基本操作。实验时间：12 月 3 日）一、 实验目的回顾 c 语言中数组的定义和基本应用二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。三、 实验内容有 M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩参考程序：#define M 5 #define N 4 #include stdio.h main() 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( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - sn *t,*q; q=NULL; t=Create(q); inc(t); printf(n); getch(); 实验数据： abc00de0g00f000(0 表示空格 ) 四、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 实验七图的操作（实验题目：图的操作。实验时间：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)；/ 访问顶点vi visitedi=TRUE； /标记 vi 已访问p=G-adjlisti.firstedge； / 取 vi 边表的头指针while(p)/依次搜索 vi 的邻接点 vj ，这里 j=p-adjvex if (!visitedp-adjvex)/若 vi 尚未被访问DFS(G ，p-adjvex);/则以 Vj 为出发点向纵深搜索p=p-next ； / 找 vi 的下一邻接点 /DFS #define MaxVertexNum 5 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - #define m 5 #define NULL 0 typedef struct node i n ta d j v e x; struct node *next; JD; typedef struct tnode int vexdata; JD *firstarc; TD; typedef struct TD 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 of node %d,i); scanf(%d,&G-agi.vexdata); printf(please input the number of arcs which adj to %d,i); scanf(%d,&m1); printf(please input the adjvex position of the first arcn); p=(JD *)malloc(sizeof(JD); scanf(%d,&p-adjvex); p-next=NULL; G-agi.firstarc=p; p1=p; for(j=2 ;jadjvex); p-next=NULL; p1-next=p; p1=p; int visitedMaxVertexNum; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - void DFSTraverse(ALGRAPH *G) int i; for(i=0;in;i+) visitedi=0; for(i=0;in;i+) if(!visitedi) DFS(G,i); /*DFSTraverse */ void DFS(ALGRAPH *G,int i) JD *p; printf(visit vertex:%d-,G-agi.vexdata); visitedi=1; /*标记 vi 已访问 */ p=G-agi.firstarc; /*取 vi 边表的头指针 */ while(p)/*依次搜索 vi 的邻接点 vj ，这里 j=p-adjvex*/ if (!visitedp-adjvex)/*若 vi 尚未被访问 */ DFS(G,p-adjvex);/*则以 Vj 为出发点向纵深搜索 */ p=p-next; /*DFS */ main() ALGRAPH *G; printf(下面以临接表存储一个图；n); creat(G); printf(下面以深度优先遍历该图 n); DFSTraverse(G); getch(); 四、调试心得。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -