数据结构实验报告.doc

_实验报告手册课程名称： 数据结构 指导教师： 专业： 计算机科学与技术 20 年20 年第 学期姓名： 学号： 年级： 级 班级： 实验报告内容实验题目：线性表及其应用 实验目的：掌握线性表的定义，掌握不同存储结构及基本运算 实验要求： 实现约瑟夫(Joseph)问题描述：约瑟夫(Joseph)问题描述为：编号为1，2，3，n的n个人按顺时针方向围坐一圈，从第s个人开始从1报数，数到第m的人出列；然后从它在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出列顺序。 实验器材：计算机 实验电路图/程序流程图：（1）利用链表（2）利用数组实验步骤/程序源代码：/利用链表#include #include#includetypedef int ElemType;typedef struct SingleNode ElemType data; struct SingleNode *next;SLL,*LinkList;int main() SLL *head ,*use,*temp; int i,n,m,k,a=0; printf(请输入总人数n：); scanf(%d,&n); printf(从第m个人开始数起，请输入m:); scanf(%d,&m); printf(数到第k个人，该人出列，请输入k:); scanf(%d,&k); head = use = (SLL *) malloc(sizeof(SLL);/建立链表，形成链表头 head-data = 1; for (i = 2; i next = (SLL *) malloc(sizeof(SLL); use = use-next; use-data = i;/第i个置编号i use-next = head;/末首相连，形成环 printf(人员序号为：); /输出人员的序号 temp=head; for(i=0;idata); temp=temp-next; printf(n); for(i=0;inext; printf(人员出列顺序为：);while (n) for (i = 1; i next; temp = use-next;/temp指向第k个 use-next = temp-next;/第k个从环中脱钩 printf(%d , temp-data); free(temp);/释放第k个表元占用的空间 n-;printf(n); return 0;/利用数组#include#include int main() int i,k,m,n,num50,*p; printf(输入总人数n：n = ); scanf(%d,&n); p=num; for(i=0;in;i+) *(p+i)=i+1;/从1到n给每个人编号 i=0;/i为每次循环时计数变量 k=0;/k为按1,2,3报数时的计数变量 m=0;/m为退出时的人数 while(mn-1)/当退出人数比n-1少时执行循环体 if(*(p+i)!=0) k+; if(k=3) printf(出局人序号:%dn,*(p+i); *(p+i)=0;/将退出时的人的编号置为0 k=0;/k报道3后，重置为0 m+;/退出时的人数加1 i+; if(i=n) i=0;/报数到n后，i恢复为0 while(*p=0) p+;/如果p指向的值等于0，就执行p+让它指向下一个元素，直到不为0 printf(留下的人的编号是:%dn,*p);/p指向的编号就是最后留下来的人 system(pause); 实验结果分析：（1） 利用链表（2）利用数组 实验日期：2017年9月8日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 栈和队列及其应用 实验目的： 掌握栈和队列的定义、存储结构及基本运算，理解栈与递归的应用 实验要求： 设计一个程序，演示用算符优先法对算术表达式求值的过程。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include #include #include #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef struct int stacksize; char *base; char *top; Stack;/* 定义整型栈 */ typedef struct int stacksize; int *base; int *top; Stack2;/* - 全局变量- */ Stack OPTR;/* 定义运算符栈*/Stack2 OPND; /* 定义操作数栈 */ char expr255 = ; /* 存放表达式串 */ char *ptr = expr; int InitStack(Stack *s) /构造运算符栈 s-base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!s-base) return ERROR; s-top=s-base; s-stacksize=STACK_INIT_SIZE;return OK; int InitStack2(Stack2 *s) /构造操作数栈 s-base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s-base) return ERROR; s-stacksize=STACK_INIT_SIZE; s-top=s-base; return OK; int In(char ch) /判断字符是否是运算符，运算符即返回1 return(ch=+|ch=-|ch=*|ch=/|ch=(|ch=)|ch=#); int Push(Stack *s,char ch) /运算符栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; int Push2(Stack2 *s,int ch)/操作数栈插入ch为新的栈顶元素 *s-top=ch; s-top+; return 0; char Pop(Stack *s) /删除运算符栈s的栈顶元素，用p返回其值 char p;s-top-; p=*s-top; return p; int Pop2(Stack2 *s)/删除操作数栈s的栈顶元素，用p返回其值 int p;s-top-; p=*s-top; return p;char GetTop(Stack s)/用p返回运算符栈s的栈顶元素 char p=*(s.top-1); return p; int GetTop2(Stack2 s) /用p返回操作数栈s的栈顶元素 int p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char Precede(char c1,char c2) int i=0,j=0; static char array49=, , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , !, , , , , , , , !, =; switch(c1) /* i为下面array的横标 */ case + : i=0;break; case - : i=1;break; case * : i=2;break; case / : i=3;break; case ( : i=4;break; case ) : i=5;break; case # : i=6;break; switch(c2) /* j为下面array的纵标 */ case + : j=0;break; case - : j=1;break; case * : j=2;break; case / : j=3;break; case ( : j=4;break; case ) : j=5;break; case # : j=6;break; return (array7*i+j); /* 返回运算符 */ /*操作函数 */ int Operate(int a,char op,int b) switch(op) case + : return (a+b); case - : return (a-b); case * : return (a*b); case / : return (a/b); return 0; int num(int n)/返回操作数的长度 char p10;itoa(n,p,10);/把整型转换成字符串型n=strlen(p);return n;int EvalExpr()/主要操作函数 char c,theta,x; int n,m;int a,b; c = *ptr+; while(c!=#|GetTop(OPTR)!=#) if(!In(c) if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/取字符串前面的数字段n=num(m); Push2(&OPND,m); ptr=ptr+n;c=*ptr+; else switch(Precede(GetTop(OPTR),c) case : theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND); Push2(&OPND,Operate(a,theta,b);break; return GetTop2(OPND); int main( ) printf(请输入正确的表达式以#结尾:); do gets(expr); while(!*expr); InitStack(&OPTR); /* 初始化运算符栈 */ Push(&OPTR,#); /* 将#压入运算符栈 */ InitStack2(&OPND); /* 初始化操作数栈 */ printf(表达式结果为:%dn, EvalExpr();return 0; 实验结果分析： 实验日期：2017年9月22日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 串及其应用 实验目的： 掌握串的应用 实验要求： 试写一统计某文本中某些字符串的出现次数和位置。涉及到串的模式匹配算法。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include #include int main() char a80 = abcdefghab0; char ch; int i, m, b80; int flag = 0; printf(请输入要查找的子串); ch = getchar();/获取一个字符 m = strlen(a);/统计主串的长度 for (i = 0; i m; i+) if (ai = ch)/找到了，直接判断是否相等 bflag = i+1;/记录位置 flag += 1; if (flag = 0)printf (主串中没有这个子串); else printf (出现的次数：%dn, flag); for (i = 0; i flag; i+)/对位置进行输出，用循环 printf (出现过的位置：%d , bi); printf (n); return 0;实验结果分析： 实验日期：2017年10月20日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 图及其应用 实验目的： 掌握树和图在实际中的应用 实验要求： 设计一个校园导游程序，为来访的客人提供各种信息查询服务。运用图的存储结构，和最短路径知识来解决。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include#include #define INT_MAX 10000 /定义符号常量#define n 10 /定义符号常量/*定义全局变量*/ int costnn;/边的值int shortestnn;/两点间的最短距离int pathnn;/ 经过的景点 /*自定义函数原型说明*/ void introduce(); int shortestdistance(); void floyed(); void display(int i,int j); /个人分工 （1）景点信息查询 2）两景点的最短距离 3）两个景点之间的路径 int main() /*主函数*/ int i,j; char k; for(i=0;i=n;i+) for(j=0;j5的数字编号！nn); break; /*introduce*/ int shortestdistance() /*要查找的两景点的最短距离*/ int i,j; printf(请输入要查询的两个景点的编号(1-5的数字编号并用-间隔):); scanf(%d-%d,&i,&j); if(in|in|j5的数字编号并用,间隔):n); scanf(%d,%d,&i,&j); else floyed(); display(i,j); return 1; /*shortestdistance*/ void floyed() /*用floyed算法求两个景点的最短路径*/ int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /*用path记录从i到j的最短路径上点j的前驱景点的序号*/ shortestij=shortestik+shortestkj; pathij=k; pathji=k; /*floyed*/ void display(int i,int j) /* 打印两个景点的路径及最短距离 */ int a,b; a=i; b=j; printf(您要查询的两景点间最短路径是:nn); if(shortestij!=INT_MAX) if(ij) /printf(%d,b); while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ /printf(-%d,pathij); if(ij) j=pathij; else i=pathji; /printf(%d)最短距离是:%d米nn,a,b,shortestab); else printf(%d,a); while(pathij!=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ /printf(-%d,pathij); if(i%d,b); printf(nn); printf(%d-%d)最短距离是:%5d米nn,a,b,shortestab); else printf(输入错误！不存在此路！nn); printf(n); /*display*/实验结果分析： 实验日期：2017年11月3日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 树、存储管理、查找和排序 实验目的： 理解树、查找和排序的定义，掌握查找和排序的基本运算 实验要求： 利用二叉排序树实现动态查找。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include #include #define ENDKEY 0typedef int KeyType;typedef struct node KeyType key ; /*关键字的值*/ struct node *lchild,*rchild;/*左右指针*/BSTNode, *BSTree;void InsertBST(BSTree *bst, KeyType key)/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/ BSTree s; if (*bst = NULL)/*递归结束条件*/ s=(BSTree)malloc(sizeof(BSTNode);/*申请新的结点s*/ s- key=key; s-lchild=NULL; s-rchild=NULL; *bst=s; else if (key key) InsertBST(&(*bst)-lchild), key);/*将s插入左子树*/ else if (key (*bst)-key) InsertBST(&(*bst)-rchild), key); /*将s插入右子树*/void CreateBST(BSTree *bst)/*从键盘输入元素的值，创建相应的二叉排序树*/ KeyType key; *bst=NULL; scanf(%d, &key); while (key!=ENDKEY) /*ENDKEY为自定义常量*/ InsertBST(bst, key); scanf(%d, &key); void PreOrder(BSTree root) /*先序遍历二叉树, root为指向二叉树根结点的指针*/ if (root!=NULL) printf(%d ,root-key); /*输出结点*/ PreOrder(root-lchild); /*先序遍历左子树*/ PreOrder(root-rchild); /*先序遍历右子树*/ /*BSTree SearchBST(BSTree bst, KeyType key)/ *在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素结点指针，否则返回空指针* / if (!bst) return NULL; else if (bst-key = key) return bst;/ *查找成功* / else if (bst-key key) return SearchBST(bst-lchild, key);/ *在左子树继续查找* / else return SearchBST(bst-rchild, key);/ *在右子树继续查找* /*/BSTree SearchBST(BSTree bst, KeyType key)/*在根指针bst所指二叉排序树bst上，查找关键字等于key的结点，若查找成功，返回指向该元素结点指针，否则返回空指针*/ BSTree q; q=bst; while(q) if (q-key = key) return q; /*查找成功*/ if (q-key key) q=q-lchild; /*在左子树中查找*/ else q=q-rchild; /*在右子树中查找*/ return NULL; /*查找失败*/*SearchBST*/BSTNode * DelBST(BSTree t, KeyType k) /*在二叉排序树t中删去关键字为k的结点*/ BSTNode *p, *f,*s ,*q; p=t; f=NULL; while(p) /*查找关键字为k的待删结点p*/ if(p-key=k ) break; /*找到则跳出循环*/ f=p; /*f指向p结点的双亲结点*/ if(p-keyk) p=p-lchild; else p=p-rchild; if(p=NU