数据结构实验报告

1、实验报告手册课程名称： 数据结构 指导教师： 专业： 计算机科学与技术 20 年20 年第 学期姓名： 学号： 年级： 级 班级： 实验报告内容实验题目：线性表及其应用 实验目的：掌握线性表的定义，掌握不同存储结构及基本运算 实验要求： 实现约瑟夫(Joseph)问题描述：约瑟夫(Joseph)问题描述为：编号为1，2，3，n的n个人按顺时针方向围坐一圈，从第s个人开始从1报数，数到第m的人出列；然后从它在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。设计一个程序求出列顺序。 实验器材：计算机 实验电路图/程序流程图：（1）利用链表（2）利用数组实验步骤/程序源代码

2、：/利用链表#include<stdio.h> #include<stdlib.h>#include<malloc.h>typedef 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(&quo

3、t;从第m个人开始数起，请输入m:"); scanf("%d",&m); printf("数到第k个人，该人出列，请输入k:"); scanf("%d",&k); head = use = (SLL *) malloc(sizeof(SLL);/建立链表，形成链表头 head->data = 1; for (i = 2; i <= n; i+)/形成其余的n-1个 use->next = (SLL *) malloc(sizeof(SLL); use = use->next; use-

4、>data = i;/第i个置编号i use->next = head;/末首相连，形成环 printf("人员序号为："); /输出人员的序号 temp=head; for(i=0;i<n;i+) printf("%d ",temp->data); temp=temp->next; printf("n"); for(i=0;i<m-1;i+)/use指向第m-1个，为了从m位开始数 use=use->next; printf("人员出列顺序为：");while (n) f

5、or (i = 1; i < k; i+)/掠过k1个 use = use->next; temp = use->next;/temp指向第k个 use->next = temp->next;/第k个从环中脱钩 printf("%d ", temp->data); free(temp);/释放第k个表元占用的空间 n-;printf("n"); return 0;/利用数组#include<stdio.h>#include<stdlib.h> int main() int i,k,m,n,num

6、50,*p; printf("输入总人数n：n = "); scanf("%d",&n); p=num; for(i=0;i<n;i+) *(p+i)=i+1;/从1到n给每个人编号 i=0;/i为每次循环时计数变量 k=0;/k为按1,2,3报数时的计数变量 m=0;/m为退出时的人数 while(m<n-1)/当退出人数比n-1少时执行循环体 if(*(p+i)!=0) k+; if(k=3) printf("出局人序号:%dn",*(p+i); *(p+i)=0;/将退出时的人的编号置为0 k=0;/k报道3

7、后，重置为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分） 教师签名： 年 月 日 实验报告内容实验题目：

8、 栈和队列及其应用 实验目的： 掌握栈和队列的定义、存储结构及基本运算，理解栈与递归的应用 实验要求： 设计一个程序，演示用算符优先法对算术表达式求值的过程。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include <stdio.h> #include <stdlib.h> #include <string.h> #define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */

9、 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

10、*)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->

11、;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->

12、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

13、 p=*(s.top-1); return p; /* 判断运算符优先权，返回优先权高的 */ char Precede(char c1,char c2) int i=0,j=0; static char array49='>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<'

14、;, '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<

15、', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '=' switch(c1) /* i为下面arr

16、ay的横标 */ 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=

17、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 '-' : re

18、turn (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(*(p

19、tr-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 '<': Push(&OPTR,c); c = *ptr+; break; case '=': x=Pop(&OPTR); c = *ptr+; break; case '>': theta=Pop(&OPTR); b=Pop2(&OPND); a=

20、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("表

21、达式结果为:%dn", EvalExpr();return 0; 实验结果分析： 实验日期：2017年9月22日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 串及其应用 实验目的： 掌握串的应用 实验要求： 试写一统计某文本中某些字符串的出现次数和位置。涉及到串的模式匹配算法。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include <stdio.h>#include <string.h>int main(

22、) 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 ("出现的

23、次数：%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分） 教师签名： 年 月 日 实验报告内容实验题目： 图及其应用 实验目的： 掌握树和图在实际中的应用 实验要求： 设计一个校园导游程序，为来访的客人提供各种信息查询服

24、务。运用图的存储结构，和最短路径知识来解决。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include<process.h>#include<stdio.h> #define INT_MAX 10000 /定义符号常量#define n 10 /定义符号常量/*定义全局变量*/ int costnn;/边的值int shortestnn;/两点间的最短距离int pathnn;/ 经过的景点 /*自定义函数原型说明*/ void introduce(); int shortestdistance(); void floyed(); void d

25、isplay(int i,int j); /个人分工 （1）景点信息查询 2）两景点的最短距离 3）两个景点之间的路径 int main() /*主函数*/ int i,j; char k; for(i=0;i<=n;i+) for(j=0;j<=n;j+) costij=INT_MAX; cost12=cost21=300; cost23=cost32=100; cost34=cost43=2000; cost35=cost53=60; cost15=cost51=45; cost25=cost52=40; cost45=cost54=30; cost14=cost41=150;

26、 cost45=cost54=1500; cost11=cost22=cost33=cost44=cost55=0; while(1) printf("nttt *欢迎使用哈师大校园导游程序*n"); printf("ttt1.景点最短路径查询请按 s 键n"); printf("ttt2.退出系统请按 e 键n"); printf("nttt *下面是景点列表*n");printf("tttt1.行知楼n"); printf("tttt2.崇师楼n"); printf(&q

27、uot;tttt3.图书馆n"); printf("tttt4.理工楼n "); printf("tttt5.体育馆n"); printf("tttt请选择服务:n"); scanf("n%c",&k); switch(k) case 's': printf("进入最短路径查询:"); shortestdistance(); break; case 'e': exit(0); default: printf("输入信息错误！n请输入字母

28、s或e.n"); break; /*main*/ void introduce() /*景点介绍*/ int a; printf("请输入想查询的景点编号:"); scanf("%d",&a); getchar(); printf("n"); switch(a) case 1: printf("行知楼:学校主楼，各行政办公室所在处，学校日常事务办公点，师大的标志性建筑。建筑中西结合，行知楼背后为每届毕业班照相处。nn");break;case 2: printf("崇师楼：为红白四方环形

29、建筑，外观华美。共六层，分A、B、C、D四区，教学重地。nn");break; case 3: printf("图书馆：学校的标志湖泊，分一为三。有情人桥伫立其上，荷花，黑天鹅在下。 nn");break; case 4: printf("理工楼：位于路，分为理工一、李工二、理工三 三栋楼，主要为理工科学生上课重地。nn");break; case 5: printf("体育馆：是师大全校最大设施最先进齐全的运动馆，平时各类室内体育比赛都在这里进行。nn");break; default: printf("景点编号

30、输入错误！请输入1->5的数字编号！nn"); break; /*introduce*/ int shortestdistance() /*要查找的两景点的最短距离*/ int i,j; printf("请输入要查询的两个景点的编号(1->5的数字编号并用'-'间隔):"); scanf("%d-%d",&i,&j); if(i>n|i<=0|j>n|j<0) printf("输入信息错误！nn"); printf(" 请输入要查询的两个景点的编号

31、(1->5的数字编号并用','间隔):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+) fo

32、r(j=1;j<=n;j+) if(shortestij>(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(i<j) /pri

33、ntf("%d",b); while(pathij!=0) /* 把i到j的路径上所有经过的景点按逆序打印出来*/ /printf("<-%d",pathij); if(i<j) j=pathij; else i=pathji; /printf("<-%d",a); printf("nn"); printf("(%d->%d)最短距离是:%d米nn",a,b,shortestab); else printf("%d",a); while(pathij!

34、=0) /* 把i到j的路径上所有经过的景点按顺序打印出来*/ /printf("->%d",pathij); if(i<j) j=pathij; else i=pathji; printf("->%d",b); printf("nn"); printf("(%d->%d)最短距离是:%5d米nn",a,b,shortestab); else printf("输入错误！不存在此路！nn"); printf("n"); /*display*/实验结果分析

35、： 实验日期：2017年11月3日 成绩评定： 优秀（100-90分） 良好（89-80分） 中等（79-70分） 及格（69-60分） 不及格（60-0分） 教师签名： 年 月 日 实验报告内容实验题目： 树、存储管理、查找和排序 实验目的： 理解树、查找和排序的定义，掌握查找和排序的基本运算 实验要求： 利用二叉排序树实现动态查找。 实验器材： 计算机 实验电路图/程序流程图：实验步骤/程序源代码：#include <stdio.h>#include <stdlib.h>#define ENDKEY 0typedef int KeyType;typedef stru

36、ct 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

37、; else if (key < (*bst)->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!=ENDKE

38、Y) /*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 bs

39、t, 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;