南方醫(yī)科大學(xué)生物醫(yī)學(xué)工程學(xué)院__電子信息工程___系數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告PAGEPAGE4姓名王浩文學(xué)號(hào)113200880200010專業(yè)年級(jí)08電子信息工程單元第2章內(nèi)容線性表日期2010-5-21實(shí)驗(yàn)題目實(shí)驗(yàn)一線性結(jié)構(gòu)（綜合性實(shí)驗(yàn)3學(xué)時(shí)）實(shí)驗(yàn)?zāi)康谋敬螌?shí)習(xí)的主要目的在于熟悉線性表的基本運(yùn)算在兩種存儲(chǔ)結(jié)構(gòu)上的實(shí)現(xiàn)，其中以熟悉各種鏈表的操作為側(cè)重點(diǎn)。通過本次實(shí)習(xí)還可復(fù)習(xí)高級(jí)語言的使用方法。實(shí)驗(yàn)內(nèi)容一、必做題：二、選做題：[問題描述]約瑟夫（Joeph）問題的一種描述是：編號(hào)為1,2,…,n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)。報(bào)m的人出列，將他的密碼作為新的m值，從他在順時(shí)針方向上的下一個(gè)人開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止。試設(shè)計(jì)一個(gè)程序求出出列順序。[基本要求]利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序印出各人的編號(hào)。[測試數(shù)據(jù)]m的初值為20；密碼：3，1，7，2，4，8，4（正確的結(jié)果應(yīng)為6，1，4，7，2，3，5）。實(shí)驗(yàn)要求及討論（本次實(shí)驗(yàn)的要求是否達(dá)到，有何問題，是怎么解決的）抄寫自己所選擇的題目。寫出算法設(shè)計(jì)思路。編寫代碼，調(diào)試運(yùn)行，實(shí)現(xiàn)題目要求（提示：考慮到插入和刪除的位置是否超出范圍等可能出現(xiàn)的異常問題）。

四、寫出算法設(shè)計(jì)、編程和調(diào)試運(yùn)行的體會(huì)。抄寫自己所選擇的題目。1、已知一順序表A，其元素非遞減有序排列，編寫一個(gè)算法，刪除順序表中值相同多余的元素（相同值保留一個(gè)）。2、已知帶頭結(jié)點(diǎn)的單鏈表L中的節(jié)點(diǎn)是按整數(shù)值遞增排序的，試寫一算法，將值為x的節(jié)點(diǎn)插入到表L中，使得表L仍然有序。分析算法的時(shí)間復(fù)雜度。寫出算法設(shè)計(jì)思路。1．建立一個(gè)順序表用于存儲(chǔ)一組非遞減排序的整形數(shù)據(jù)，對(duì)順序表中的每個(gè)元素與其下一個(gè)元素進(jìn)行比較操作。用指針記錄當(dāng)前所比較的元素，如果相等則對(duì)當(dāng)前指針?biāo)赶虻脑剡M(jìn)行刪除操作，并將它后面的數(shù)據(jù)前移，再與下一個(gè)元素比較，如果還相等就繼續(xù)刪除操作，否則指向下個(gè)元素，再比較直至無重復(fù)的元素。2.建立一個(gè)帶頭節(jié)點(diǎn)的單鏈表，其節(jié)點(diǎn)按整數(shù)值遞增排序。創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并由鍵盤輸入節(jié)點(diǎn)的值。將其與鏈表中原有的節(jié)點(diǎn)（頭節(jié)點(diǎn)不參與比較）按順序作比較，并用指針指向當(dāng)前的位置，若不大于當(dāng)前節(jié)點(diǎn)，則在當(dāng)前位置這前作插入操作，否則在最后作插入操作。三、編寫代碼，調(diào)試運(yùn)行，實(shí)現(xiàn)題目要求（提示：考慮到插入和刪除的位置是否超出范圍等可能出現(xiàn)的異常問題）。解1．法I:#include"stdio.h"#include"conio.h"#defineSIZE10main(){intSqList_A[SIZE]={23,3,45,65,23,44,5,7,89,0};inti,j,n,m,l=SIZE;for(i=0;i<l;i++)printf("%d",*(SqList_A+i));printf("\nThenewoneis:\n");for(i=0;i<(l-1);i++)for(j=0;j<(l-1);j++)if(SqList_A[i]==SqList_A[j])if(i!=j){n=i;m=i+1;for(;m<l;n++,m++)SqList_A[n]=SqList_A[m];l=l-1;}for(i=0;i<l;i++)printf("%d",*(SqList_A+i));printf("\n\n");getch();}法II：#include"stdio.h"#include"conio.h"#defineSIZE18#defineERROR0#defineOK1intlength;/*定義宏觀變量*/typedefintstatus;typedefstruct{int*elem;intlength;intlistsize;}SqList;statusListDelete(SqList*L){/*刪除順序表L中值相同多余的元素（相同值保留一個(gè)）*/inti=0,j,n=0;SqList*p=L;if(!p)returnERROR;while(i<p->length){if(*(p->elem+i)==*(p->elem+i+1)){/*刪除相同多余的元素*/for(j=i;j<p->length;j++)*(p->elem+j)=*(p->elem+j+1);n++;p->length--;}if(!(*(p->elem+i)==*(p->elem+i+1)))/*判斷第i個(gè)數(shù)是否任和下一個(gè)數(shù)相同*/i++;}length=SIZE-n;returnn;}main(){inta[SIZE]={1,2,2,5,6,7,7,12,13,13,13,18,19,20,21,24,24,39},t;intn,m;SqListA;A.elem=a;for(n=0;n<SIZE;n++)printf("%d",a[n]);A.length=A.listsize=SIZE;t=ListDelete(&A);if(!t)printf("ListDeleteERROR!\n");else{printf("\nThenewoneis:\n");for(n=0;n<length;n++)printf("%d",a[n]);}getch();}解2.#include"stdio.h"#include"conio.h"#defineSIZE10#defineERROR0#defineNULL0#defineOK1inta[SIZE]={1,3,5,8,10,12,14,17,19,26},i;typedefintstatus;typedefstructnod{intdata;structnod*next;}node;statusCreatList(node*L){/*建立一個(gè)帶頭結(jié)點(diǎn)的節(jié)點(diǎn)按整數(shù)值遞增排序的單鏈表L*/node*p,*h=NULL;h=p=(node*)malloc(sizeof(node));if(!p)returnERROR;/*節(jié)點(diǎn)創(chuàng)建失敗*/p->data=a[i];for(i=1;i<SIZE;i++)/*創(chuàng)建整數(shù)值遞增排序鏈表*/{p->next=(node*)malloc(sizeof(node));p=p->next;p->data=a[i];}p->next=NULL;L->next=h;returnOK;}statusListInsert(node*L,intx){inti,k;for(i=0;i<SIZE;i++)if(x>=a[i]&&x<a[i+1])k=i+1;{for(i=SIZE-1;i>=k;i--)a[i+1]=a[i];a[k]=x;}}main(){node*L,*p;intt,x,i,k;printf("Pleaseinputthenumberyouwanttoinsertx:\n");scanf("%d",&x);printf("TheListis:\n");for(i=0;i<SIZE;i++)printf("%d",a[i]);printf("\nAfterinert,thenewoneis:\n");L=(node*)malloc(sizeof(node));if(!L){printf("ERROR!\n");return;}t=CreatList(L);/*創(chuàng)建鏈表*/if(!t){printf("ERROR!\n");return;}ListInsert(L,x);for(i=0;i<SIZE+1;i++)printf("%d",a[i]);getch();}時(shí)間復(fù)雜度為：O(n)寫出算法設(shè)計(jì)、編程和調(diào)試運(yùn)行的體會(huì)。經(jīng)過