《数据结构》实验报告.doc

数据结构（C语言版）实验报告 关宏新 089074114 计084班 姓名： 关宏新学号： 089074114班级： 计084班指导教师： 储岳中实验一线性表基本操作的实现一、 实验目的1、 掌握使用Turbo C2.0上机调试线性表的基本方法；2、 掌握线性表的基本操作：插入、删除、查找等运算在顺序存储结构和链式存储结构上的运算。二、实验要求1、 链表插入、删除和查找算法的代码；2、 程序运行结果及分析；3、 实验总结。三、实验内容1、 认真阅读和掌握本实验的参考程序。2、 上机运行本程序，并完善删除、查找等运算。3、 保存程序的运行结果，并结合程序进行分析。4、 按照你对链表操作需要，重新改写算法并运行，实现链表的插入、删除、查找等运算，并保存运行结果。四、程序流程图、算法及运行结果1-1#include stdio.h#include stdlib.h#define MAXSIZE 100struct SeqList int dataMAXSIZE; int length;typedef struct SeqList *PSeqList;PSeqList creaeNullList_seq() PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList); if(palist!=NULL) palist-length=0; return(palist); printf(Out of space!n); return NULL;int isNullList_seq(PSeqList palist) return (palist-length=0);int insertPre_seq(PSeqList palist,int p,int x) int q; if(palist-length=MAXSIZE) printf(overflow!n); return(0); if(ppalist-length) printf(Not exist!n); return(0); if(isNullList_seq(palist) palist-data0=x; palist-length=1; return(1); for(q=palist-length-1;q=p;q-) palist-dataq+1=palist-dataq ; palist-datap=x; palist-length= palist-length+1; return(1);void main() int i; PSeqList list; list=creaeNullList_seq(); printf(插入前的顺序表为：n ); for(i=0;idatai); insertPre_seq(list,5,55); printf(n插入后的顺序表为：n ); for(i=0;ilength;i+) printf( %d , list-datai); printf(n); getch();1-2#include stdio.h#include stdlib.h#define MAXSIZE 100struct SeqList int dataMAXSIZE; int length;typedef struct SeqList *PSeqList;PSeqList creaeNullList_seq() PSeqList palist=(PSeqList)malloc(sizeof(struct SeqList); if(palist!=NULL) palist-length=0; return(palist); printf(Out of space!n); return NULL;int isNullList_seq(PSeqList palist) return (palist-length=0);/* 插入 */int insertPre_seq(PSeqList palist,int p,int x) int q; if(palist-length=MAXSIZE) printf(overflow!n); return(0); if(ppalist-length) printf(Not exist!n); return(0); if(isNullList_seq(palist) palist-data0=x; palist-length=1; return(1); for(q=palist-length-1;q=p;q-) palist-dataq+1=palist-dataq ; palist-datap=x; palist-length= palist-length+1; return(1);/* 删除 */int deletePre_seq(PSeqList palist, int i)int j;if (!palist) printf(表不存在);return(-1); if(i palist - length) printf (删除位置不合法); return(0); for(j=i;j length;j+) palist -dataj-1= palist -dataj;palist - length -;return (1); /* 检索 ElementType */int locationPre_seq(PSeqList palist,int x) int i=0; if (!palist) printf(表不存在); return(-1); while (ilength & palist-datai!= x) i+; if (i=palist- length) return 0; else return (i + 1); void main() int i; PSeqList list; list=creaeNullList_seq(); printf(插入前的顺序表为:n ); for(i=0;idatai); insertPre_seq(list,5,55); printf(n插入后的顺序表为:n ); for(i=0;ilength;i+) printf( %d , list-datai); printf(n); printf(删除前的顺序表为:n ); for(i=0;idatai); deletePre_seq(list, 5); printf(n删除后的顺序表为:n ); for(i=0;idatai); printf(n); if(locationPre_seq(list,9)=0) printf(检索的内容不存在!); if(locationPre_seq(list,9)!=0&locationPre_seq(list,9)!=-1) printf(检索的内容下标为：%d,locationPre_seq(list,9); printf(n); getch();实验二 栈的基本操作一、 实验目的掌握栈的基本操作：初始化栈、判栈为空、出栈、入栈等运算。二、实验要求1 认真阅读和掌握本实验的算法。2 上机将本算法实现。 3 保存程序的运行结果，并结合程序进行分析。三、实验内容利用栈的基本操作实现将任意一个十进制整数转化为R进制整数算法为：1、定义栈的顺序存取结构2、分别定义栈的基本操作（初始化栈、判栈为空、出栈、入栈等）3、定义一个函数用来实现上面问题：(1)十进制整数X和R作为形参(2)初始化栈(3)只要X不为0重复做下列动作将X % R入栈, X=X/R(4)只要栈不为空重复做下列动作栈顶出栈 , 输出栈顶元素四、程序流程图、算法及运行结果2-1#include #include #include #define stack_init_size 100#define stackincrement 10typedef struct sqstack int *base; int *top; int stacksize; sqstack;int StackInit(sqstack *s) s-base=(int *)malloc(stack_init_size *sizeof(int); if(!s-base) return 0; s-top=s-base; s-stacksize=stack_init_size; return 1;int Push(sqstack *s,int e) if(s-top-s-base=s-stacksize) s-base=(int *)realloc(s-base,(s-stacksize+stackincrement)*sizeof(int); if(!s-base) return 0; s-top=s-base+s-stacksize; s-stacksize+=stackincrement; *(s-top+)=e; return e;int Pop(sqstack *s,int e) if(s-top=s-base) return 0; e=*-s-top; return e;int stackempty(sqstack *s) if(s-top=s-base) return 1; else return 0; int conversion(sqstack *s) int n,e=0,flag=0; printf(输入要转化的十进制数：n); scanf(%d,&n); printf(要转化为多少进制：2进制、8进制、16进制 填数字！n); scanf(%d,&flag); printf(将十进制数%d转化为%d进制是：n,n,flag); while(n) Push(s,n%flag); n=n/flag; while(!stackempty(s) e=Pop(s,e); switch(e) case 10: printf(A); break; case 11: printf(B); break; case 12: printf(C); break; case 13: printf(D); break; case 14: printf(E); break; case 15: printf(F); break; default: printf(%d,e); printf(n); return 0;int main() sqstack s; StackInit(&s); conversion(&s); return 0;2-2#include#define MAXSIZE 100struct 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 full.n); 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); getch();实验三 串的模式匹配一、 实验目的1 利用顺序结构存储串，并实现串的匹配算法。2 掌握简单模式匹配思想，熟悉KMP算法。二、 实验要求1认真理解简单模式匹配思想，高效实现简单模式匹配；2结合参考程序调试KMP算法，努力算法思想；3保存程序的运行结果，并结合程序进行分析。三、 实验内容1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置；2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。四、程序流程图、算法及运行结果3-1#include #include #define MAXSIZE 100int StrIndex_BF(char sMAXSIZE,char tMAXSIZE) int i=1,j=1; while (i=s0 & jt0) return (i-t0); else return -1;int main() char sMAXSIZE; char tMAXSIZE; int answer, i; printf(S String -n ); gets(s); printf(T String -n ); gets(t); printf(%d,StrIndex_BF(s,t); /*验证*/ if(answer=StrIndex_BF(s,t)=0) printf(n); printf(%sn, s); for (i = 0; i answer; i+) printf( ); printf(%s, t); printf(nnPattern Found at location:%dn, answer); else printf(nPattern NOT FOUND.n); getch(); return 0;3-2#include #include #define MAXSIZE 100void get_nextval(unsigned char pat,int nextval) int length = strlen(pat); int i=1; int j=0; nextval1=0; while(ilength) if(j=0|pati-1=patj-1) +i; +j; if(pati-1!=patj-1) nextvali=j; else nextvali=nextvalj; else j=nextvalj; int Index_KMP(unsigned char text, unsigned char pat,int nextval) int i=1; int j=1; int t_len = strlen(text); int p_len = strlen(pat); while(i=t_len&jp_len) return i-1-p_len; else return -1; int main() unsigned char textMAXSIZE; unsigned char patMAXSIZE; int nextvalMAXSIZE; int answer, i; printf(nBoyer-Moore String Searching Program); printf(n=); printf(nnText String - ); gets(text); printf( nPattern String - ); gets(pat); get_nextval(pat,nextval); if(answer=Index_KMP(text, pat,nextval)=0) printf(n); printf(%sn, text); for (i = 0; i answer; i+) printf( ); printf(%s, pat); printf(nnPattern Found at location %dn, answer); else printf(nPattern NOT FOUND.n); getch(); return 0;3-3#include stdio.hvoid GetNext1(char *t,int next) int i=1,j=0; next1=0; while(i=9) if(j=0|ti=tj) +i; +j; nexti=j; else j=nextj; void GetNext2(char *t , int next) int i=1, j = 0; next1= 0; while (i=1 & ti != tj ) j = nextj; i+; j+; if(ti=tj) nexti = nextj; else nexti = j; void main() char *p=abcaababc; int i,str10; GetNext1(p,str); printf(Put out:n); for(i=1;i10;i+) printf(%d,stri); GetNext2(p,str); printf(n); for(i=1;i=m) /* 无效结点 */ return NULL; p=(BinTree *)malloc(sizeof(BinTree);/* 生成新结点 */ p-data=stri; p-lchild=cre_tree(str,2*i+1,m);/* 创建新结点的左子树 */ p-rchild=cre_tree(str,2*i+2,m);/* 创建新结点的右子树 */ return p;void main() int i,n; char strmax; BinTree *root;/* 根结点 */ printf(请输入二叉树的结点数:); scanf(%d,&n); getchar();/* 输入数字 */ printf(请输入长度为 %d 的字符串 :,n); for(i=0;in;i+) scanf(%c,&stri); printf(n); root=cre_tree(str,0,n); printf(二叉树已成功创建! 结点序列为：); for(i=0;idata); if(t-lchild) printf(-); preorder(t-lchild); if(t-rchild) printf(-); preorder(t-rchild); void inorder(BinTree *t) if(t!=NULL) inorder(t-lchild); printf( %c ,t-data); inorder(t-rchild); void postorder(BinTree *t) if(t!=NULL) postorder(t-lchild); postorder(t-rchild); printf( %c ,t-data); int leafs(BinTree *b)/* 求叶子数 */ int num1,num2; if(b=NULL) return (0); else if(b-lchild=NULL & b-rchild=NULL) return (1); else num1=leafs(b-lchild); num2=leafs(b-rchild); return(num1+num2); int treedeep(BinTree *p)/* 求树的深度 */ int ldeep,rdeep,deep; if(p=NULL) deep=0; else ldeep=treedeep(p-lchild); rdeep=treedeep(p-rchild); deep=(ldeeprdeep?ldeep:rdeep)+1; return deep;BinTree *swap(BinTree *p)/* 交换二叉树的所有结点的左右子树 */ BinTree *stackmax; int k=0; stackk=NULL; if(p!=NULL) stack+k=p-lchild; p-lchild=p-rchild; p-rchild=stackk; p-lchild=swap(p-lchild); p-rchild=swap(p-rchild); return p;实验五 图的创建与遍历.一、 实验目的1掌握图的含义；2 掌握用邻接矩阵和邻接表的方法描述图的存储结构；3 理解并掌握深度优先遍历和广度优先遍历的存储结构。二、 实验要求1 认真阅读和掌握本实验的参考程序。2 按照对图的操作需要，在创建好图后再通过遍历算法验证创建结果。3 保存程序的运行结果，并结合程序进行分析。三、 实验内容 以下参考程序是按邻接表的方法创建图，然后用深度优先遍历方法遍历图。请认真理解程序，然后实现图的广度优先遍历。四、程序流程图、算法及运行结果5-1#include stdio.h#define maxsize 1024 /*假定线性表的最大长度为1024*/#define n 100 /* 图的顶点最大个数 */typedef int datatype; /*假定线性表元素的类型为整型*/typedef char VEXTYPE; /* 顶点的数据类型 */typedef float ADJTYPE; /* 权值类型 */typedef struct VEXTYPE vexsn ; /* 顶点信息数组 */ ADJTYPE arcsnn ; /* 边权数组 */ int num ; /* 顶点的实际个数 */ GRAPH;/* 1.置空图 */void GraphInit(GRAPH *L) L-num=0;/* 2.求结点数 */int GraphVexs(GRAPH *L) return(L-num);/* 3.创建图 */void GraphCreate(GRAPH *L) int i,j; GraphInit(L); printf(请输入顶点数目：); scanf(%d,&L-num); printf(请输入各顶点的信息(单个符号）：); for(i=0;inum;i+) fflush(stdin); scanf(%c,&L-vexsi); printf(请输入边权矩阵的信息：); for(i=0;inum;i+) for(j=0;jnum;j+) scanf(%f,&L-arcsij); printf(图已经创建完毕！);/* 4.图的输出 */void GraphOut(GRAPH L) int i,j; printf(n图的顶点数目为：%d,L.num); printf(n图的各顶点的信息为：n); for(i=0;iL.num;i+) printf(%c ,L.vexsi); printf(n图的边权矩阵的信息为：n); for(i=0;iL.num;i+) for(j=0;jL.num;j+) printf(%6.2f ,L.arcsij); printf(n); printf(图已经输出完毕！);/* 5.图的深度周游 */void DFS(GRAPH g,int qidian,int mark)/* 从第qidian个点出发深度优先周游图g中能访问的各个顶点 */ int v1; markqidian=1; printf(%c ,g.vexsqidian); for(v1=0;v1g.num;v1+) if(g.arcsqidianv1!=0&markv1=0) DFS(g,v1,mark); /* 6.图的深度周游 */void GraphDFS(GRAPH g)/* 深度优先周游图g中能访问的各个顶点 */ int qidian,v,v1,markmaxsize; printf(n深度周游：); printf(n请输入起点的下标：); scanf(%d,&qidian); for(v=0;vg.num;v+) markv=0; for(v=qidian;vfront=0; sq-rear=0;int QueueIsEmpty(SEQQUEUE sq)/* 如果顺序循环队列sq为空，成功返回1，否则返回0 */ if (sq.rear=sq.front) return(1); else return(0); int QueueFront(SEQQUEUE sq,DATATYPE *e)/* 将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0 */ if(QueueIsEmpty(sq) printf(queue is empty!n);return 0; else *e=sq.data(sq.front); return 1;int QueueIn (SEQQUEUE *sq,DATATYPE x)/* 将元素x入队列sq的队尾，成功返回1，失败返回0 */ if (sq-front=(sq-rear+1)%maxsize) printf(queue is full!n); return 0; else sq-datasq-rear=x; sq-rear=(sq-rear+1)%maxsize; return(1); int QueueOut(SEQQUEUE *sq)/* 将队列sq队首元素出队列，成功返回1,失败返回0 */ if(QueueIsEmpty(*sq) printf(queue is empty!n); return 0; else sq-front=(sq-front+1)%maxsize; return 1; /*