實驗一 線性表的基本操作

PAGEPAGE4實驗一線性表的基本操作一、實驗目的與基本要求1．掌握數(shù)據(jù)結(jié)構(gòu)中的一些基本概念。數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)，以及它們之間的關(guān)系。了解數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)之間的區(qū)別與聯(lián)系；數(shù)據(jù)的運算與數(shù)據(jù)的邏輯結(jié)構(gòu)的關(guān)系。掌握線性表的基本操作：插入、刪除、查找以及線性表的合并等運算。掌握運用C語言上機調(diào)試線性表的基本方法。二、實驗條件硬件：一臺微機軟件：操作系統(tǒng)和C語言系統(tǒng)三、實驗方法確定存儲結(jié)構(gòu)后，上機調(diào)試實現(xiàn)線性表的基本運算。四、實驗內(nèi)容試編寫在無頭結(jié)點的單鏈表上實現(xiàn)線性表基本運算LOCATE（L，X），INSERT（L，X，1）和DELETE（L，1）的算法。假設(shè)有兩個按數(shù)據(jù)元素值遞增有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)。編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許值相同）排列的線性表C，并要求利用原表（即A表和B表）結(jié)點空間存放表C。將一個線性表中的值就地逆置。在線性表的順序存儲結(jié)構(gòu)的第一個位置上插入一個元素。五、實驗提示參考算法查找算法如下:voidlocate（lklistL，intx）{p=head；while（p->next!=NULL）{if（p->data==x）returnp;elsep=p->next;}if(p->data!=x)error(“無此結(jié)點”)}插入算法如下:voidinsert(lklistL,intx,inti){p=head;q=malloc(sizeof());q->data=x;if(i<0)error(“無此位置”)j=0;if(i=1){q->next=head;head=q;}while(j<i-1)&&(p->next!=NULL)j++;if(i==i-1){q->next=p->next;p->next=q;}elseerror(“i位置超出范圍”);}刪除算法如下:voiddelete(lklistL,inti){p=head;if(i<0)error(“無此位置”)j=0;if(i=1){q=head;head=head->next;free(q);}while(j<i-1)&&(p->next!=NULL)j++;if(j==i-1){q=p->next;p->next=q->next;free(q);}elseerror(“i位置超出范圍”);}參考算法voidconnectlink(lklistA,B,C){p=A;q=B;C=NULL;While(p->next!=NULL)&&(q->next!=NULL){if(p->data<q->data){m=p;A=A->next;p=A;}else{m=q;B=B->next;q=B;}m->next=C;C=m;}if(p->next!=NULL){m=p;A=A->next;p=A;m->next=C;C=m;}else{m=p;B=B->next;p=B;m->next=C;C=m;}}3.參考程序main(){/*主程序參數(shù)說明部分*/inta[]={1,2,3,4,5,6,7,8},i;/*將線性表以順序存儲方式存放*/voidConverse(inta[];intn);/*函數(shù)說明*//*程序主體*/printf(“\n原數(shù)組序列為:“);for(i=0;i<8;i++)printf(“%d”,a[i]);Converse(a,8);/*函數(shù)調(diào)用*/printf(“\n逆序數(shù)組序列為:“);for(i=0;i<8;i++)printf(“%d”,a[i]);}/*函數(shù)*/voidConverse(inta[];intn){/*參數(shù)說明部分*/intm,x,i;/*程序主體*/m=n/2;for(i=0;i<m;i++){x=a[i];a[i]=a[n-1-i];a[n-1-i]=x;}}4.參考程序#defineNULL0typedefintdatatype;#definemaxsize1024typedefstruct{datatypedata[maxsize];/*定義線性表是順序存儲結(jié)構(gòu),第一個結(jié)點是data[0]*/intlast;}sequenlist;/*插入函數(shù)*/intinsert(L,x,i)/*將新結(jié)點x插入到順序表L第i個位置*/sequenlist*L;/*L是sequenlist類型的指針變量*/inti;{intj;if((*L).last==maxsize-1){printf(“overflow”);returnNULL;}elseif((i<1)||(i>(*L).last+1)){printf(“error”);returnNULL;}/*非法位置*/else{for(j=(*L).last;j>i-1;j--)(*L