2024年數(shù)據(jù)結(jié)構(gòu)實驗報告

試驗匯報手冊課程名稱：數(shù)據(jù)構(gòu)造指導教師：專業(yè)：計算機科學與技術(shù)20年—20年第學期姓名：學號：年級：級班級：

試驗匯報內(nèi)容試驗題目：線性表及其應用試驗目的：掌握線性表的定義，掌握不一樣存儲構(gòu)造及基本運算試驗規(guī)定：實現(xiàn)約瑟夫(Joseph)問題描述：約瑟夫(Joseph)問題描述為：編號為1，2，3，…，n的n個人按順時針方向圍坐一圈，從第s個人開始從1報數(shù)，數(shù)到第m的人出列；然後從它在順時針方向上的下一種人開始重新從1報數(shù)，如此下去，直至所有人所有出列為止。設計一種程序求出列次序。試驗器材：計算機試驗電路圖/程序流程圖：（1）運用鏈表（2）運用數(shù)組試驗環(huán)節(jié)/程序源代碼：//運用鏈表#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("請輸入總?cè)藬?shù)n：");scanf("%d",&n);printf("從第m個人開始數(shù)起，請輸入m:");scanf("%d",&m);printf("數(shù)到第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;//末首相連，形成環(huán)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位開始數(shù){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個從環(huán)中脫鉤printf("%d",temp->data);free(temp);//釋放第k個表元占用的空間n--;}printf("\n");return0;}//運用數(shù)組#include<stdio.h>#include<stdlib.h>intmain(){inti,k,m,n,num[50],*p;printf("輸入總?cè)藬?shù)n：n=");scanf("%d",&n);p=num;for(i=0;i<n;i++)*(p+i)=i+1;//從1到n給每個人編號i=0;//i為每次循環(huán)時計數(shù)變量k=0;//k為按1,2,3報數(shù)時的計數(shù)變量m=0;//m為退出時的人數(shù)while(m<n-1)//當退出人數(shù)比n-1少時執(zhí)行循環(huán)體{if(*(p+i)!=0)k++;if(k==3){printf("出局人序號:%d\n",*(p+i));*(p+i)=0;//將退出時的人的編號置為0k=0;//k報道3後，重置為0m++;//退出時的人數(shù)加1}i++;if(i==n)i=0;//報數(shù)到n後，i恢復為0}while(*p==0)p++;//假如p指向的值等于0，就執(zhí)行p++讓它指向下一種元素，直到不為0printf("留下的人的編號是:%d\n",*p);//p指向的編號就是最終留下來的人system("pause");}試驗成果分析：運用鏈表（2）運用數(shù)組試驗曰期：9月8曰成績評估：□優(yōu)秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師簽名：年月曰試驗匯報內(nèi)容試驗題目：棧和隊列及其應用試驗目的：掌握棧和隊列的定義、存儲構(gòu)造及基本運算，理解棧與遞歸的應用試驗規(guī)定：設計一種程序，演示用算符優(yōu)先法對算術(shù)體現(xiàn)式求值的過程。試驗器材：計算機試驗電路圖/程序流程圖：試驗環(huán)節(jié)/程序源代碼：#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;/*定義操作數(shù)棧*/charexpr[255]="";/*寄存體現(xiàn)式串*/char*ptr=expr;intInitStack(Stack*s)//構(gòu)造運算符棧{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)//構(gòu)造操作數(shù)棧{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)//操作數(shù)棧插入ch為新的棧頂元素{*s->top=ch;s->top++;return0;}charPop(Stack*s)//刪除運算符棧s的棧頂元素，用p返回其值{charp;s->top--;p=*s->top;returnp;}intPop2(Stack2*s)//刪除操作數(shù)棧s的棧頂元素，用p返回其值{intp;s->top--;p=*s->top;returnp;}charGetTop(Stacks)//用p返回運算符棧s的棧頂元素{charp=*(s.top-1);returnp;}intGetTop2(Stack2s)//用p返回操作數(shù)棧s的棧頂元素{intp=*(s.top-1);returnp;}/*判斷運算符優(yōu)先權(quán)，返回優(yōu)先權(quán)高的*/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]);/*返回運算符*/}/*操作函數(shù)*/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)//返回操作數(shù)的長度{charp[10]; itoa(n,p,10);//把整型轉(zhuǎn)換成字符串型 n=strlen(p); returnn;}intEvalExpr()//重要操作函數(shù){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);//取字符串前面的數(shù)字段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("請輸入對的的體現(xiàn)式以'#'結(jié)尾:");do{gets(expr);}while(!*expr);InitStack(&OPTR);/*初始化運算符棧*/Push(&OPTR,'#');/*將#壓入運算符棧*/InitStack2(&OPND);/*初始化操作數(shù)棧*/printf("體現(xiàn)式成果為:%d\n",EvalExpr());return0;}試驗成果分析：試驗曰期：9月22曰成績評估：□優(yōu)秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師簽名：年月曰試驗匯報內(nèi)容試驗題目：串及其應用試驗目的：掌握串的應用試驗規(guī)定：試寫一記錄某文本中某些字符串的出現(xiàn)次數(shù)和位置。波及到串的模式匹配算法。試驗器材：計算機試驗電路圖/程序流程圖：試驗環(huán)節(jié)/程序源代碼：#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("出現(xiàn)的次數(shù)：%d\n",flag);for(i=0;i<flag;i++){//對位置進行輸出，用循環(huán)printf("出現(xiàn)過的位置：%d",b[i]);}printf("\n");}return0;}試驗成果分析：試驗曰期：10月20曰成績評估：□優(yōu)秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師簽名：年月曰試驗匯報內(nèi)容試驗題目：圖及其應用試驗目的：掌握樹和圖在實際中的應用試驗規(guī)定：設計一種校園導游程序，為來訪的客人提供多種信息查詢服務。運用圖的存儲構(gòu)造，和最短途徑知識來處理。試驗器材：計算機試驗電路圖/程序流程圖：試驗環(huán)節(jié)/程序源代碼： #include<process.h> #include<stdio.h> #defineINT_MAX10000//定義符號常量 #definen10//定義符號常量 /*定義全局變量*/ intcost[n][n];//邊的值 intshortest[n][n];//兩點間的最短距離 intpath[n][n];//通過的景點 /*自定義函數(shù)原型闡明*/ voidintroduce(); intshortestdistance(); voidfloyed(); voiddisplay(inti,intj);//個人分工（1）景點信息查詢2）兩景點的最短距離3）兩個景點之間的途徑 intmain() {/*主函數(shù)*/ 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.退出系統(tǒng)……………請按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("行知樓:學校主樓，各行政辦公室所在處，學校平常事務辦公點，師大的標志性建筑。建筑中西結(jié)合，行知樓背後為每屆畢業(yè)班攝影處。\n\n");break; case2: printf("崇師樓：為紅白四方環(huán)形建筑，外觀華美。共六層，分A、B、C、D四區(qū)，教學重地。\n\n");break; case3: printf("圖書館：學校的標志湖泊，分一為三。有情人橋佇立其上，荷花，黑天鵝在下。\n\n");break; case4: printf("理工樓：位于路，分為理工一、李工二、理工三三棟樓，重要為理工科學生上課重地。\n\n");break; case5: printf("體育館：是師大全校最大設施最先進齊全的運動館，平時各類室內(nèi)體育比賽都在這裏進行。\n\n");break; default:printf("景點編號輸入錯誤！請輸入1->5的數(shù)字編號！\n\n");break; } }/*introduce*/ intshortestdistance() {/*要查找的兩景點的最短距離*/ inti,j; printf("請輸入要查詢的兩個景點的編號(1->5的數(shù)字編號并用'-'間隔):"); scanf("%d-%d",&i,&j); if(i>n||i<=0||j>n||j<0) { printf("輸入信息錯誤！\n\n"); printf("請輸入要查詢的兩個景點的編號(1->5的數(shù)字編號并用','間隔):\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的前驅(qū)景點的序號*/ 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曰成績評估：□優(yōu)秀（100-90分）□良好（89-80分）□中等（79-70分）□及格（69-60分）□不及格（60-0分）教師簽名：年月曰試驗匯報內(nèi)容試驗題目：樹、存儲管理、查找和排序試驗目的：理解樹、查找和排序的定義，掌握查找和排序的基本運算試驗規(guī)定：運用二叉排序樹實現(xiàn)動態(tài)查找。試驗器材：計算機試驗電路圖/程序流程圖：試驗環(huán)節(jié)/程序源代碼：#include<stdio.h>#include<stdlib.h>#defineENDKEY0typedefintKeyType;typedefstructnode{KeyTypekey;/*關鍵字的值*/structnode*lchild,*rchild;/*左右指針*/}BSTNode,*BSTree;voidInsertBST(BSTree*bst,KeyTypekey)/*若在二叉排序樹中不存在關鍵字等于key的元素，插入該元素*/{BSTrees;if(*bst==NULL)/*遞歸結(jié)束條件*/{s=(BSTree)malloc(sizeof(BSTNode));/*申請新的結(jié)點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)/*從鍵盤輸入元素的值，創(chuàng)立對應的二叉排序樹*/{KeyTypekey;*bst=NULL;scanf("%d",&key);while(key!=ENDKEY)/*ENDKEY為自定義常量*/{InsertBST(bst,key);scanf("%d",&key);}}voidPreOrder(BSTreeroot)/*先序遍歷二叉樹,root為指向二叉樹根結(jié)點的指針*/{if(root!=NULL){printf("%d",root->key);/*輸出結(jié)點*/PreOrder(root->lchild);/*先序遍歷左子樹*/PreOrder(root->rchild);/*先序遍歷右子樹*/}}/*BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指針bst所指二叉排序樹中，遞歸查找某關鍵字等于key的元素，若查找成功，返回指向該元素結(jié)點指針，否則返回空指針*/{if(!bst)returnNULL;elseif(bst->key==key)returnbst;/*查找成功*/elseif(bst->key>key)returnSearchBST(bst->lchild,key);/*在左子樹繼續(xù)查找*/elsereturnSearchBST(bst->rchild,key);/*在右子樹繼續(xù)查找*/}*/BSTreeSearchBST(BSTreebst,KeyTypekey)/*在根指針bst所指二叉排序樹bst上，查找關鍵字等于key的結(jié)點，若查找成功，返回指向該元素結(jié)點指針，否則返回空指針*/{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的結(jié)點*/{BSTNode*p,*f,*s,*q;p=t;f=NULL;while(p)/*查找關鍵字為k的待刪結(jié)點p*/{if(