1、算法与数据结构实习算法与数据结构实习指 导 书（黄海学院09级用）编写：唐仕喜2010年8月28日教学目的：通过该实习课程的实践教学，使学生强化C语言程序设计课程的知识，并着重培养以下几方面的能力：C语言程序的编写和调试能力；根据算法，进行结构化程序设计的能力；对一些典型的基本应用问题，进行算法设计的能力。教学要求：根据大纲要求，完成教材习题部分布置的实习题。学生应在每个实习前准备好源程序草稿；对必做题要求提交实验报告，实验报告应该给出算法主要部分的源程序；并且提交调试正确的完整程序文件以收集备案。 （选做题不要求提交实验报告）教学方式：实习课主要形式是上机实践，根据教学进度完成相应的实习题，
2、教师随实习课进行指导。考核方式：该实习课程的考核为考查，成绩为等级制，评分依据实验报告、实习题的源程序。实验一 抽象数据类型的定义与使用一、 实验目的1、 掌握使用Turbo C 2.0上机处理抽象数据类型的基本方法；2、 掌握抽象数据类型的定义与使用，能结合实例加以理解。二、 实验要求1、认真设计抽象数据类型，2、认真思考设计算法。三、 注意事项：在磁盘上创建一个目录，专门用于存储数据结构实验的程序。四、 实验内容1设计实现抽象数据类型“有理数”，基本操作包括有理数的加法、减法、乘法和除法，以及求有理数的分子、分母。提示：有理数看作一个对象，而有理数是有限小数或无限循环小数，其一般形式可以看
3、作由分子和分母两个数据项组成，因此可以用类似于表示复数的方法类表示它-即用一个结构体；对于有理数的加法和减法、还要注意通分。类推：由此，我们还可以处理类似的对象，例如，日期、时间等对象，具有类似的特性，其操作也具有各自的特点。同学们可以自行实现它们。实验二 顺序表的操作一、 实验目的1、 掌握使用Turbo C 2.0上机处理顺序表的基本方法；2、 掌握顺序表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算。二、 实验要求1、 认真阅读和掌握本实验的程序。2、 上机运行本程序。3、 保存和打印出程序的运行结果，并结合程序进行分析。4、 按照你对顺序表的操作需
4、要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1：顺序表基本操作的实现这个程序中演示了顺序表的创建、插入、删除和查找，请修改并完成。程序如下：#include #include /*顺序表的定义：*/#define ListSize 100typedef struct int dataListSize; /*向量data用于存放表结点*/ int length; /*当前的表长度*/SeqList;void main() void CreateList(SeqList *L,int n); void PrintList(SeqList *L,int n); int Loc
5、ateList(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);
6、 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
7、); /*顺序表删除*/ 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) 请完成代码/*顺序表的插入
8、：*/void InsertList(SeqList *L,int x, int i) 请完成代码/*顺序表的删除：*/void DeleteList(SeqList *L,int i) 请完成代码实验三 单链表操作一、 实验目的1 掌握握单链表的基本操作：插入、删除、查找等运算。二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你对单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1：单链表基本操作的实现这个程序中演示了单链表的创建、插入、删除和查找。程序如下： #includetyp
9、edef 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);/
10、*/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) 请完成代码/*/voi
11、d Del(NODE *head,int i) 请完成代码/*/void Ins(NODE *head,int i,int e)NODE *p=head,*q;int j=0;while(p-next&ji-1) 请完成代码/*/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); scan
12、f(%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();_ 实验四 栈的基本操作一、 实验目的掌握栈的基本操作：初始
13、化栈、判栈为空、出栈、入栈等运算。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。 3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：十进制整数X和R作为形参初始化栈只要不为重复做下列动作将入栈X=X/R只要栈不为空重复做下列动作栈顶出栈输出栈顶元素参考程序：#define MAXSIZE 100#includestruct stack int dataMAXSIZE; int to
14、p;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; 请完成代码int pop(struct stack *s) if(empty(s) printf(stack is empty); return -1; 请完成代码void trans(int num) struct sta
15、ck 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); 实验五 队列的基本操作一、实验目的掌握队列的基本操作：初始化队
16、列、判队列为空、出队列、入队列等运算。二、实验要求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);参考程序如下typede
17、f 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
18、.rear=s1+s2;q.rear+;s1=s2;printf(%dn,1);q.dataq.rear=1+s2;q.rear+;_实验六 数组的基本操作一、 实验目的回顾c语言中数组的定义和基本应用二、 实验要求1 认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。三、 实验内容有M个学生，学习N门课程，已知所有学生的各科成绩，编程：分别求每个学生的平均成绩和每门课程的平均成绩参考程序：#define M 5 #define N 4 #include stdio.hmain() int i,j; static float scoreM+1N
19、+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); p
20、rintf(n); for(j=0;j8*(N+2);j+) printf(-); printf(n课程平均); for(j=0;jN;j+) printf(%6.1ft,scoreMj); printf(n); getch(); 实验七 字符串处理一、实验目的1、理解字符串的基本概念，字符串的存贮2、掌握字符串的基本操作。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。3 保存和打印出程序的运行结果，并结合程序进行分析。三、实验内容定义字符串数组、实现字符串处理的基本操作#include #define MAXN 100typedef enum fail, success
21、status;typedef enum false, true boolean;char sMAXN, s1MAXN, s2MAXN;void scopy(char s1,char s2)int i=0;while(s2i!=0) s1i=s2i;i+;s1i=0;int strlen(char s ) int i;for (i=0; si!=0; i+ );return (i);status strcat(char s1,char s2)int i, j, k;if (i=strlen (s1) + (j=strlen (s2) )=MAXN)return (fail);for (k=0;
22、k=j; k+ )s1i+k=s2k;return (success);status strins(char s1, int i, char s2)int m, n, k;if (i(m=strlen(s1)|m+(n=strlen(s2)MAXN)return(fail); 请完成代码return(success);status strsub (sl, i, j, s2)char sl , s2 ;int i,j; int m, k;if (i= (m=strlen(sl)return (fail );if (jm)return (fail ); 请完成代码return (success )
23、; void main( ) int i;i=strlen(aassddd) ;printf(%dn,i);scopy(s1,abcd);scopy(s2,hijkl);printf(%sn,s1);printf(%sn,s2);strcat(s1,s2);printf(%sn,s1);printf(%sn,s2);strins(s1,4,s2);printf(%sn,s1);printf(%sn,s2);.实验八 二叉树操作一、 实验目的1 进一步掌握指针变量的含义。2 掌握二叉树的结构特征，以及各种存储结构的特点及使用范围。3 掌握用指针类型描述、访问和处理二叉树的运算。二、 实验要求1
24、认真阅读和掌握本实验的程序。2 上机运行本程序。3 保存和打印出程序的运行结果，并结合程序进行分析。4 按照你二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果三、 实验内容程序1： 按先序次序输入二叉树中结点的值（一个字符），0表示空树，生成二叉树的二叉链表存储结构， a为指向根结点的指针。然后按中序顺序遍历二叉树。算法思想：先访问左子树,再访问根结点,最后访问右子树参考程序如下：#define NULL 0typedef struct stuchar data;struct stu *left,*right;sn;sn *Create(sn *a)char ch;scanf(
25、%c,&ch);if(ch= )a=NULL;elsea=(sn *)malloc(sizeof(sn);if (!a) printf(yuguyuy);a-data=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表示空格)实验九 图的
26、操作一实验目的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)； /以v
