2024年数据结构实验报告

试验汇报手册課程名称：数据构造指导教師：专业：计算机科學与技术20年—20年第學期姓名：學号：年级：级班级：

试验汇报内容试验題目：线性表及其应用试验目的：掌握线性表的定义，掌握不一样存储构造及基本运算试验规定：实現约瑟夫(Joseph)問題描述：约瑟夫(Joseph)問題描述為：编号為1，2，3，…，n的n個人按顺時针方向围坐一圈，從第s個人開始從1报数，数到第m的人出列；然後從它在顺時针方向上的下一种人開始重新從1报数，如此下去，直至所有人所有出列為止。设计一种程序求出列次序。试验器材：计算机试验電路图/程序流程图：（1）运用链表（2）运用数组试验环节/程序源代码：//运用链表#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefintElemType;typedefstructSingleNode{ElemTypedata;structSingleNode*next;}SLL,*LinkList;intmain(){SLL*head,*use,*temp;inti,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<=n;i++)//形成其他的n-1個{use->next=(SLL*)malloc(sizeof(SLL));use=use->next;use->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){for(i=1;i<k;i++)//擦過k－1個use=use->next;temp=use->next;//temp指向第k個use->next=temp->next;//第k個從环中脱钩printf("%d",temp->data);free(temp);//释放第k個表元占用的空间n--;}printf("\n");return0;}//运用数组#include<stdio.h>#include<stdlib.h>intmain(){inti,k,m,n,num[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("出局人序号:%d\n",*(p+i));*(p+i)=0;//将退出時的人的编号置為0k=0;//k报道3後，重置為0m++;//退出時的人数加1}i++;if(i==n)i=0;//报数到n後，i恢复為0}while(*p==0)p++;//假如p指向的值等于0，就执行p++让它指向下一种元素，直到不為0printf("留下的人的编号是:%d\n",*p);//p指向的编号就是最终留下来的人system("pause");}试验成果分析：运用链表（2）运用数组试验曰期：9月8曰成绩评估：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師签名：年月曰试验汇报内容试验題目：栈和队列及其应用试验目的：掌握栈和队列的定义、存储构造及基本运算，理解栈与递归的应用试验规定：设计一种程序，演示用算符优先法對算术体現式求值的過程。试验器材：计算机试验電路图/程序流程图：试验环节/程序源代码：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineNULL0#defineOK1#defineERROR-1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT20/*定义字符类型栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;/*定义整型栈*/typedefstruct{intstacksize;int*base;int*top;}Stack2;/*-----------------全局变量---------------*/StackOPTR;/*定义运算符栈*/Stack2OPND;/*定义操作数栈*/charexpr[255]="";/*寄存体現式串*/char*ptr=expr;intInitStack(Stack*s)//构造运算符栈{s->base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!s->base)returnERROR;s->top=s->base;s->stacksize=STACK_INIT_SIZE;returnOK;}intInitStack2(Stack2*s)//构造操作数栈{s->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!s->base)returnERROR;s->stacksize=STACK_INIT_SIZE;s->top=s->base;returnOK;}intIn(charch)//判断字符与否是运算符，运算符即返回1{return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#');}intPush(Stack*s,charch)//运算符栈插入ch為新的栈顶元素{*s->top=ch;s->top++;return0;}intPush2(Stack2*s,intch)//操作数栈插入ch為新的栈顶元素{*s->top=ch;s->top++;return0;}charPop(Stack*s)//删除运算符栈s的栈顶元素，用p返回其值{charp;s->top--;p=*s->top;returnp;}intPop2(Stack2*s)//删除操作数栈s的栈顶元素，用p返回其值{intp;s->top--;p=*s->top;returnp;}charGetTop(Stacks)//用p返回运算符栈s的栈顶元素{charp=*(s.top-1);returnp;}intGetTop2(Stack2s)//用p返回操作数栈s的栈顶元素{intp=*(s.top-1);returnp;}/*判断运算符优先权，返回优先权高的*/charPrecede(charc1,charc2){inti=0,j=0;staticchararray[49]={'>','>','<','<','<','>','>','>','>','<','<','<','>','>','>','>','>','>','<','>','>','>','>','>','>','<','>','>','<','<','<','<','<','=','!','>','>','>','>','!','>','>','<','<','<','<','<','!','='};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(array[7*i+j]);/*返回运算符*/}/*操作函数*/intOperate(inta,charop,intb){switch(op){case'+':return(a+b);case'-':return(a-b);case'*':return(a*b);case'/':return(a/b);}return0;}intnum(intn)//返回操作数的長度{charp[10]; itoa(n,p,10);//把整型转换成字符串型 n=strlen(p); returnn;}intEvalExpr()//重要操作函数{charc,theta,x;intn,m;inta,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++;}elseswitch(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=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b));break;}}returnGetTop2(OPND);}intmain(){printf("請输入對的的体現式以'#'結尾:");do{gets(expr);}while(!*expr);InitStack(&OPTR);/*初始化运算符栈*/Push(&OPTR,'#');/*将#压入运算符栈*/InitStack2(&OPND);/*初始化操作数栈*/printf("体現式成果為:%d\n",EvalExpr());return0;}试验成果分析：试验曰期：9月22曰成绩评估：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師签名：年月曰试验汇报内容试验題目：串及其应用试验目的：掌握串的应用试验规定：试写一记录某文本中某些字符串的出現次数和位置。波及到串的模式匹配算法。试验器材：计算机试验電路图/程序流程图：试验环节/程序源代码：#include<stdio.h>#include<string.h>intmain(){chara[80]="abcdefghab\0";charch;inti,m,b[80];intflag=0;printf("請输入要查找的子串");ch=getchar();//获取一种字符m=strlen(a);//记录主串的長度for(i=0;i<m;i++){if(a[i]==ch){//找到了，直接判断与否相等b[flag]=i+1;//记录位置flag+=1;}}if(flag==0)printf("主串中没有這個子串");else{printf("出現的次数：%d\n",flag);for(i=0;i<flag;i++){//對位置進行输出，用循环printf("出現過的位置：%d",b[i]);}printf("\n");}return0;}试验成果分析：试验曰期：10月20曰成绩评估：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師签名：年月曰试验汇报内容试验題目：图及其应用试验目的：掌握树和图在实际中的应用试验规定：设计一种校园导游程序，為来访的客人提供多种信息查询服务。运用图的存储构造，和最短途径知识来处理。试验器材：计算机试验電路图/程序流程图：试验环节/程序源代码： #include<process.h> #include<stdio.h> #defineINT_MAX10000//定义符号常量 #definen10//定义符号常量 /*定义全局变量*/ intcost[n][n];//边的值 intshortest[n][n];//两點间的最短距离 intpath[n][n];//通過的景點 /*自定义函数原型阐明*/ voidintroduce(); intshortestdistance(); voidfloyed(); voiddisplay(inti,intj);//個人分工（1）景點信息查询2）两景點的最短距离3）两個景點之间的途径 intmain() {/*主函数*/ inti,j; chark; for(i=0;i<=n;i++) for(j=0;j<=n;j++) cost[i][j]=INT_MAX; cost[1][2]=cost[2][1]=300; cost[2][3]=cost[3][2]=100; cost[3][4]=cost[4][3]=; cost[3][5]=cost[5][3]=60; cost[1][5]=cost[5][1]=45; cost[2][5]=cost[5][2]=40; cost[4][5]=cost[5][4]=30; cost[1][4]=cost[4][1]=150; cost[4][5]=cost[5][4]=1500; cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0; while(1) { printf("\n\t\t\t********欢迎使用哈師大校园导游程序*********\n"); printf("\t\t\t1.景點最短途径查询…請按s键\n"); printf("\t\t\t2.退出系统……………請按e键\n"); printf("\n\t\t\t**************下面是景點列表*************\n"); printf("\t\t\t\t1.行知楼\n"); printf("\t\t\t\t2.崇師楼\n"); printf("\t\t\t\t3.图書馆\n"); printf("\t\t\t\t4.理工楼\n"); printf("\t\t\t\t5.体育馆\n"); printf("\t\t\t\t請选择服务:\n"); scanf("\n%c",&k); switch(k) { case's': printf("進入最短途径查询:"); shortestdistance(); break; case'e': exit(0); default: printf("输入信息錯误！\n請输入字母s或e.\n"); break; } } }/*main*/ voidintroduce() {/*景點简介*/ inta; printf("請输入想查询的景點编号:"); scanf("%d",&a); getchar(); printf("\n"); switch(a) { case1: printf("行知楼:學校主楼，各行政办公室所在处，學校平常事务办公點，師大的標志性建筑。建筑中西結合，行知楼背後為每届毕业班摄影处。\n\n");break; case2: printf("崇師楼：為紅白四方环形建筑，外观华美。共六层，分A、B、C、D四区，教學重地。\n\n");break; case3: printf("图書馆：學校的標志湖泊，分一為三。有情人桥伫立其上，荷花，黑天鹅在下。\n\n");break; case4: printf("理工楼：位于路，分為理工一、李工二、理工三三栋楼，重要為理工科學生上課重地。\n\n");break; case5: printf("体育馆：是師大全校最大设施最先進齐全的运動馆，平時各类室内体育比赛都在這裏進行。\n\n");break; default:printf("景點编号输入錯误！請输入1->5的数字编号！\n\n");break; } }/*introduce*/ intshortestdistance() {/*要查找的两景點的最短距离*/ inti,j; printf("請输入要查询的两個景點的编号(1->5的数字编号并用'-'间隔):"); scanf("%d-%d",&i,&j); if(i>n||i<=0||j>n||j<0) { printf("输入信息錯误！\n\n"); printf("請输入要查询的两個景點的编号(1->5的数字编号并用','间隔):\n"); scanf("%d,%d",&i,&j); } else { floyed(); display(i,j); } return1; }/*shortestdistance*/ voidfloyed() {/*用floyed算法求两個景點的最短途径*/ inti,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) { shortest[i][j]=cost[i][j]; path[i][j]=0; } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {/*用path[][]记录從i到j的最短途径上點j的前驱景點的序号*/ shortest[i][j]=shortest[i][k]+shortest[k][j]; path[i][j]=k; path[j][i]=k; } }/*floyed*/ voiddisplay(inti,intj) {/*打印两個景點的途径及最短距离*/ inta,b; a=i; b=j; printf("您要查询的两景點间最短途径是:\n\n"); if(shortest[i][j]!=INT_MAX) { if(i<j) { //printf("%d",b); while(path[i][j]!=0) {/*把i到j的途径上所有通過的景點按逆序打印出来*/ //printf("<-%d",path[i][j]); if(i<j) j=path[i][j]; else i=path[j][i]; } //printf("<-%d",a); printf("\n\n"); printf("(%d->%d)最短距离是:%d米\n\n",a,b,shortest[a][b]); } else { printf("%d",a); while(path[i][j]!=0) {/*把i到j的途径上所有通過的景點按次序打印出来*/ //printf("->%d",path[i][j]); if(i<j) j=path[i][j]; else i=path[j][i]; } printf("->%d",b); printf("\n\n"); printf("(%d->%d)最短距离是:%5d米\n\n",a,b,shortest[a][b]); } } else printf("输入錯误！不存在此路！\n\n"); printf("\n"); }/*display*/试验成果分析：试验曰期：11月3曰成绩评估：□优秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師签名：年月曰试验汇报内容试验題目：树、存储管理、查找和排序试验目的：理解树、查找和排序的定义，掌握查找和排序的基本运算试验规定：运用二叉排序树实現動态查找。试验器材：计算机试验電路图/程序流程图：试验环节/程序源代码：#include<stdio.h>#include<stdlib.h>#defineENDKEY0typedefintKeyType;typedefstructnode{KeyTypekey;/*关键字的值*/structnode*lchild,*rchild;/*左右指针*/}BSTNode,*BSTree;voidInsertBST(BSTree*bst,KeyTypekey)/*若在二叉排序树中不存在关键字等于key的元素，插入该元素*/{BSTrees;if(*bst==NULL)/*递归結束条件*/{s=(BSTree)malloc(sizeof(BSTNode));/*申請新的結點s*/s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;}elseif(key<(*bst)->key)InsertBST(&((*bst)->lchild),key);/*将s插入左子树*/elseif(key>(*bst)->key)InsertBST(&((*bst)->rchild),key);/*将s插入右子树*/}voidCreateBST(BSTree*bst)/*從键盘输入元素的值，创立對应的二叉排序树*/{KeyTypekey;*bst=NULL;scanf("%d",&key);while(key!=ENDKEY)/*ENDKEY為自定义常量*/{InsertBST(bst,key);scanf("%d",&key);}}voidPreOrder(BSTreeroot)/*先序遍历二叉树,root為指向二叉树根結點的指针*/{if(root!=NULL){printf("%d",root->key);/*输出結點*/PreOrder(root->lchild);/*先序遍历左子树*/PreOrder(root->rchild);/*先序遍历右子树*/}}/*BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指针bst所指二叉排序树中，递归查找某关键字等于key的元素，若查找成功，返回指向该元素結點指针，否则返回空指针*/{if(!bst)returnNULL;elseif(bst->key==key)returnbst;/*查找成功*/elseif(bst->key>key)returnSearchBST(bst->lchild,key);/*在左子树继续查找*/elsereturnSearchBST(bst->rchild,key);/*在右子树继续查找*/}*/BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指针bst所指二叉排序树bst上，查找关键字等于key的結點，若查找成功，返回指向该元素結點指针，否则返回空指针*/{BSTreeq;q=bst;while(q){if(q->key==key)returnq;/*查找成功*/if(q->key>key)q=q->lchild;/*在左子树中查找*/elseq=q->rchild;/*在右子树中查找*/}returnNULL;/*查找失败*/}/*SearchBST*/BSTNode*DelBST(BSTreet,KeyTypek)/*在二叉排序树t中删去关键字為k的結點*/{BSTNode*p,*f,*s,*q;p=t;f=NULL;while(p)/*查找关键字為k的待删結點p*/{if(