...wd......wd......wd...計算機系數(shù)據(jù)構造實驗報告〔1〕實驗目的：幫助學生掌握線性表的基本操作在順序和鏈表這兩種存儲構造上的實現(xiàn)，尤以鏈表的操作和應用作為重點。問題描述：構造一個空的線性表L。在線性表L的第i個元素之前插入新的元素e；在線性表L中刪除第i個元素，并用e返回其值。實驗要求：文法是一個四元分別利用順序和鏈表存儲構造實現(xiàn)線性表的存儲，并設計出在不同的存儲構造中線性表的基本操作算法。在實驗過程中，對一樣的操作在不同的存儲構造下的時間復雜度和空間復雜度進展分析。算法分析：由于兩種存儲構造都用來創(chuàng)立線性構造的數(shù)據(jù)表，可采用一樣的輸出模式和整體構造類似的算法，如下：實驗內(nèi)容和過程：順序存儲構造線性表程序清單：//順序存儲構造線性表的插入刪除#include<iostream>#include<stdlib.h>usingnamespacestd;#defineLISTSIZE100#defineCREMENTSIZE10typedefcharElemType;//定義數(shù)據(jù)元素類型為字符型typedefstruct{ ElemType*elem;//數(shù)據(jù)元素首地址 intlen; //當前元素個數(shù) intlistsize; //當前存儲最大容量}SqList;//構造一個空的線性表Lint InitList(SqList&L){L.elem=(ElemType*)malloc(LISTSIZE*sizeof(ElemType)); if(!L.elem)exit(-2);//分配空間失敗 L.len=0; L.listsize=LISTSIZE;}//在順序線性表L中第i個位置之前插入新的元素eintListInsert(SqList&L,inti,ElemTypee){ if(i<1||i>L.len+1)return-1;//i值不合法 if(L.len>=L.listsize) { ElemType*newelem=(ElemType*)realloc(L.elem,(L.listsize+CREMENTSIZE)*sizeof(ElemType)); //存儲空間已滿，增加分配 if(!newelem)exit(-2);//分配失敗 L.elem=newelem; L.listsize+=CREMENTSIZE; }ElemType*q=&(L.elem[i-1]);for(ElemType*p=&(L.elem[L.len-1]);p>=q;--p)*(p+1)=*p;//插入位置及其后的元素后移*q=e;++L.len; return1;}//在順序線性表L中刪除第i個元素，并用e返回其值intListDelete(SqList&L,inti,ElemType&e){ if(i<1||i>L.len)return-1;//i值不合法 ElemType*p=&(L.elem[i-1]); e=*p;ElemType*q=L.elem+L.len-1; for(++p;p<=q+1;++p)*(p-1)=*p;//被刪除元素之后的元素前移 --L.len; return1;}int main(){ SqListL;chare,ch; inti,j,state; InitList(L);//構造線性表 printf("請輸入原始數(shù)據(jù)(字符串個數(shù)0~99)：L="); //數(shù)據(jù)初始化 gets(L.elem); for(j=1;L.elem[j-1]!='\0';j++)L.len=j;//獲取表長L.len L.elem[j]='\0'; printf("操作：插入〔I〕還是刪除(D)?\n");//判斷進展插入還是刪除操作AGAIN: cin>>ch; if(ch=='I') { cout<<"插在第幾個元素之前:";//插入操作 cin>>i;cout<<"輸入要插入的新元素:"; cin>>e; cout<<endl; printf("輸入數(shù)據(jù)：L=(%s) ListInsert(L,%d,%c)",L.elem,i,e); state=ListInsert(L,i,e); } elseif(ch=='D') { cout<<"刪除第幾個元素：";//刪除操作 cin>>i; cout<<endl; printf("輸入數(shù)據(jù)：L=(%s) DeleteList(L,%d,e)",L.elem,i); state=ListDelete(L,i,e); } elsegotoAGAIN;//操作指示符輸入錯誤處理 cout<<endl<<"正確結果："; if(state==-1)cout<<"ERROR,"; printf("L=(%s) ",L.elem);//輸出結果if(ch=='D'&&state!=-1)cout<<",e="<<e;}鏈式存儲構造線性表程序清單：//-----單鏈存儲構造線性表的插入刪除-----#include<iostream>#include<stdlib.h>usingnamespacestd;#definenull0typedefcharElemType;//定義數(shù)據(jù)元素類型為字符型typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;intGetElem(LinkListL,inti,ElemType&e)//獲取第i個元素的值{ LinkListp;intj;p=L->next;j=1; while(p&&j<i){ p=p->next;++j;//尋找第i個元素} if(!p||j>i)return-1;//尋找失敗 e=p->data; return1;}intListInsert(LinkList&L,inti,ElemTypee){ //在帶頭結點的單鏈線性表L中第i個元素之前插入元素eLinkListp,s;intj; p=L;j=0;while(p&&j<i-1){p=p->next;++j;}if(!p||j>i-1)return-1;s=(LinkList)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}intListDelete(LinkList&L,inti,ElemType&e){ //在帶頭結點的單鏈線性表L中,刪除第i個元素，并由e返回其值 LinkListp,q;intj; p=L;j=0;while(p->next&&j<i-1){ p=p->next;++j;}if(!(p->next)||j>i-1)return-1;q=p->next;p->next=q->next;e=q->data;free(q);return1;}intnewdata(LinkList&L,char*ch){ intk; printf("請輸入原始數(shù)據(jù)(字符串個數(shù)0~99)：L=");//數(shù)據(jù)初始化 gets(ch); for(k=0;ch[k]!='\0';k++) ListInsert(L,k+1,ch[k]);//將初始化數(shù)據(jù)插入鏈表L中cout<<"OK"<<endl; returnk;//返回鏈表中的元素個數(shù)}intmain(){char*ch;ch=(char*)malloc(100*sizeof(char));//定義數(shù)組用來輔助數(shù)據(jù)初始化 LinkListL;//頭指針 LNodehead;//頭結點 L=&head;head.next=null; inti,k,state;chare,CH,f; k=newdata(L,ch);//調(diào)用函數(shù)使鏈表數(shù)據(jù)初始化 head.data=k;//將元素個數(shù)存入頭結點的數(shù)據(jù)域 printf("操作：插入〔I〕還是刪除(D)\n");//判斷進展插入還是刪除操作AGAIN: cin>>CH;if(CH=='I') { cout<<"插在第幾個元素之前:";//插入操作 cin>>i;cout<<"輸入要插入的新元素:"; cin>>e;cout<<endl; printf("輸入數(shù)據(jù)：L=(%s) ListInsert(L,%d,%c)",ch,i,e); state=ListInsert(L,i,e); (head.data)++; } elseif(CH=='D') { cout<<"刪除第幾個元素：";//刪除操作 cin>>i; cout<<endl; printf("輸入數(shù)據(jù)：L=(%s) DeleteList(L,%d,e)",ch,i); state=ListDelete(L,i,e); (head.data)--; } elsegotoAGAIN;//操作指示符輸入錯誤處理 cout<<endl<<"正確結果："; if(state==-1)cout<<"ERROR,";//輸出結果 cout<<"L=("; for(intm=1;(head.data)>=m;m++)//一一輸出數(shù)據(jù) { GetElem(L,m,f);cout<<f; } cout<<")"; if(CH=='D'&&state!=-1)cout<<",e="<<e;//刪除操作反響e}實驗結果：由于兩個程序的輸出模式一樣，在此只列一組測試數(shù)據(jù)： L=()ListInsert(L,1,'k')L=(EHIKMOP)ListInsert(L,9,'t')L=(ABCEHKNPQTU)ListInsert(L,4,'u')L=()ListDelete(L,1,e)L=(DEFILMNORU)ListDelete_Sq(L,5,e)L=(CD)ListDelete_Sq(L,1,e)測試過程中所注意到的問題主要還是輸出與輸入界面的問題，通過靈活使用cout和cin函數(shù)來不斷改進。另外，在用戶端看來在設計算法時程序的可重復性未考慮，顯得不夠人性化。時間復雜度分析：假定線性表有n個節(jié)點，順序存儲構造下，插入程序段以*(p+1)=*p作為基本操作的原操作，并討論在最壞情況下的時間復雜度，記T(n)=O(n)；刪除程序段以*(p-1)=*(p)作為基本操作的原操作，并討論在最壞情況下的時間復雜度，記T’(n)=O(n)。鏈式存儲構造下，插入程序段以p=p->next作為基本操作的原操作，并討論在最壞情況下的時間復雜度，記T(n)=O(n);刪除程序段以p=p->next作為基本操作的原操作，并討論在最壞