數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)--圖-資料下載頁
2024-11-15 22:14本頁面
【正文】 end,int L[]){ int left=first,right=end,key。key=L[first]。while(left{ while((left=key))right。if(leftL[left++]=L[right]。while((leftleft++。if(leftL[left]=key。return left。}quick_sort(int L[],int first,int end){ int split。if(endfirst){ split=quick(first,end,L)。quick_sort(L,first,split1)。quick_sort(L,split+1,end)。}} void kuaisu(){int a[7],i。printf(“快速排序n”)。printf(“請輸入個(gè)您想排序的數(shù)據(jù):n”)。for(i=0。iscanf(“%d”,amp。a[i])。quick_sort(a,0,9)。printf(“排序成功:”)。for(i=0。iprintf(“ %d”,a[i])。printf(“n”)。} 五﹑實(shí)驗(yàn)結(jié)果：六﹑實(shí)驗(yàn)心得體會：排序的功能是將一個(gè)數(shù)據(jù)元素（或記錄）的任意序列，從新排成按關(guān)鍵字有序的序列；直接插入排序的穩(wěn)定性比快速排序高，且算法較簡單。本次實(shí)驗(yàn)運(yùn)用到的是插入排序和快速排序。第五篇：數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)報(bào)告實(shí)習(xí)報(bào)告題 目 : 實(shí)現(xiàn)一個(gè)約瑟夫環(huán)程序班級：031021姓名：王帥學(xué)號：03102076一、需求分析1． 本演示程序中，利用單向循環(huán)鏈表存儲結(jié)構(gòu)存儲約瑟夫環(huán)數(shù)據(jù)（即n個(gè)人的編號和密碼）。2． 演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中需要輸入的數(shù)據(jù)，運(yùn)算結(jié)果顯示在其后。3． 程序執(zhí)行的命令包括：1)構(gòu)造單向循環(huán)鏈表；2）進(jìn)行數(shù)值的輸入，并作判斷分析；3）約瑟夫算法的實(shí)現(xiàn)與結(jié)果輸出；4）結(jié)束。4． 測試數(shù)據(jù)m 的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，（正確的出列順序?yàn)?，1，4，7，2，1，3，5）。二、概要設(shè)計(jì)1．單向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：ADT List｛數(shù)據(jù)對象：D=｛ai | ai?正整數(shù)，I=1，2，......，n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛ ai1，ai |，ai1，ai?D,I=1，2，......，n｝基本操作：Init List(amp。L)操作結(jié)果：構(gòu)造一個(gè)空的線性表L。List Insert(amp。L,i,e)初始條件：線性表L已存在，1≤i≤List Length(L)+：在L中第i個(gè)位置之前插入新的數(shù)據(jù)元素e，L長度加1。List Delete(amp。L,i,amp。e)初始條件：線性表L存在非空，1≤i≤List Length(L).操作結(jié)果：刪除L的第i個(gè)元素，并用e返回其值，L長度減1。2． 程序包含四個(gè)模塊：1）主程序模塊：void main(){初始化；for（。）{}while（命令=開始）{接受命令；處理命令；}for（。）{ }}2）有序表單元模塊——實(shí)現(xiàn)有序表的抽象數(shù)據(jù)類型；3）節(jié)點(diǎn)結(jié)構(gòu)單元模塊——定義有序表的節(jié)點(diǎn)結(jié)構(gòu)；4）數(shù)據(jù)輸入分析模塊——判斷輸入數(shù)據(jù)正確有效；各模塊之間的調(diào)用關(guān)系如下：主程序模塊↓有序表結(jié)構(gòu)模塊↓節(jié)點(diǎn)結(jié)構(gòu)單元模塊↓數(shù)據(jù)輸入分析模塊三、詳細(xì)設(shè)計(jì)結(jié)點(diǎn)類型，指針類型TypedefstructLNode{int code,date。//code 為人所在位置 date為人持有的密碼 struct LNode *next。}。// 結(jié)點(diǎn)類型，指針類型構(gòu)造單向循環(huán)鏈表struct LNode *p,*head,*q。//定義頭節(jié)點(diǎn)，和指針for(i=2。i{struct LNode *s=(struct LNode *)malloc(sizeof(struct LNode))。//分配新結(jié)點(diǎn)空間scode=i。input(sdate)。pnext=s。p=pnext。}pnext=head。//根據(jù)輸入的人數(shù)，進(jìn)行單項(xiàng)循環(huán)鏈表的創(chuàng)建，p指向最后一個(gè)結(jié)點(diǎn)，并與頭節(jié)點(diǎn)鏈接，形成單項(xiàng)循環(huán)鏈表約瑟夫環(huán)的程序?qū)崿F(xiàn)部分while(n!=1)//判斷輸入人數(shù)，如為1則直接輸出結(jié)果，不循環(huán){for(i=1，m=m%n。i{p=pnext。}q=pnext。//找到要?jiǎng)h除節(jié)點(diǎn)pnext=qnext。//找到要?jiǎng)h除節(jié)點(diǎn)的后繼，并連接新環(huán)m=qdate。//找到下一個(gè)密碼printf(“%d”,qcode)。free(q)。//釋放已刪除節(jié)點(diǎn)空間n。//鏈表長度減一}printf(“%d”,pcode)。//約瑟夫環(huán)的結(jié)果輸出其他函數(shù)代碼數(shù)值的輸入限制int input(){int y,k,z=0。char c。//元素類型char a[4]。//數(shù)組初始化if(!z)//輸入判斷，確定位數(shù)字或控制字符且位置和密碼不為零 {for(y=0。y{c=getch()。if(c=48amp。amp。c{a[y]=c。putch(c)。}else{y。if(c==39。r39。)//確定輸入為控制字符 即回車或者刪除break。elseif(c==8){a[y]=39。n39。y。}continue。}}k=atoi(a)。//確定最終輸入數(shù)字的值printf(“n”)。z=k。if(z==0)printf(“ERROR!The number couldn39。t be 0!n”)。// 輸入為零，重新輸入 }return(k)。//數(shù)值的返回函數(shù)的調(diào)用關(guān)系圖反映程序?qū)哟谓Y(jié)構(gòu)Main→input四、調(diào)試分析早期程序只寫了約瑟夫環(huán)的實(shí)現(xiàn)部分，沒有對輸入數(shù)據(jù)進(jìn)行篩選，調(diào)試的時(shí)候會經(jīng)常出錯(cuò)。比如是輸入字母，或者輸入0，大于32767溢出；早期的循環(huán)過程中沒有進(jìn)行優(yōu)化，導(dǎo)致循環(huán)次數(shù)過多，浪費(fèi)時(shí)間；為了輸出時(shí)美觀，分別在input和main函數(shù)主體內(nèi)做了兩次，輸入非零的判斷，浪費(fèi)了資源；算法的時(shí)空分析為了限制在輸入過程中不會上溢，只在輸入中限定為四個(gè)不全為零的數(shù)字，但是做的是do……while循環(huán)，復(fù)雜度為o（1）。當(dāng)n大于1時(shí)：在數(shù)據(jù)輸入中，鏈表的創(chuàng)建是for循環(huán)，時(shí)間復(fù)雜度為o（n1）在約瑟夫環(huán)實(shí)現(xiàn)程序中，為for循環(huán)。時(shí)間復(fù)雜度為o（m%n1）當(dāng)n=1時(shí)，復(fù)雜度為o（1）。五、用戶手冊用戶根據(jù)提示，先輸入起始密碼m，然后輸入人數(shù)n，再根據(jù)人數(shù)，分別輸入每個(gè)人的密碼date，數(shù)值均不能為0，否則會提示重新輸入，輸入為字母則自動(dòng)丟棄，輸入錯(cuò)誤可用刪除鍵進(jìn)行修改，輸入完成后按回車鍵確定本次輸入完畢（若輸入數(shù)字大于9999，則第五位自動(dòng)轉(zhuǎn)換為下一個(gè)數(shù)字的起始位，依此類推）。當(dāng)n個(gè)數(shù)字全部輸入完畢，則自動(dòng)顯示結(jié)果，按任意鍵則退出本程序。六、測試結(jié)果第一組：m 的初值為20；n=7，7個(gè)人的密碼依次為：3，1，7，2，4，8，4，出列順序?yàn)?，1，4，7，2，1，3，5。第二組： m 的初值為30；n=8，7個(gè)人的密碼依次為：5，1，6，9，4，7，2，3，出列順序?yàn)?，5，2，3，7，1，4，8。第三組 : m 的初值為15；n=6，7個(gè)人的密碼依次為：5，3，4，7，6，9，出列順序?yàn)?，1，2，6，4，5。七、附錄源程序頭文件名清單：include “”//內(nèi)存空間分配頭文件include “”//輸入輸出函數(shù)頭文件include “”//input函數(shù)中字符串轉(zhuǎn)短整形函數(shù)的頭文件 include “”//最后顯示結(jié)果、清屏函數(shù)頭文件
公司管理相關(guān)推薦
鄂ICP備17016276號-1