數(shù)據(jù)結(jié)構(gòu)實驗(1)線性表及其應(yīng)用

1、v1.0可編輯可修改計算機系數(shù)據(jù)結(jié)構(gòu)實驗報告（1）實驗?zāi)康模簬椭鷮W(xué)生掌握線性表的基本操作在順序和鏈表這兩種存儲結(jié)構(gòu)上的實現(xiàn)，尤以鏈表的操作和應(yīng)用作為重點。問題描述：1、構(gòu)造一個空的線性表 L。2、在線，f表L的第i個元素之前插入新的元素 e；3、在線f表L中刪除第i個元素，并用e返回其值。實驗要求：1、分別利用順序和鏈表存儲結(jié)構(gòu)實現(xiàn)線性表的存儲，并設(shè)計出在不同的存儲結(jié)構(gòu)中線性表的基本操作算法。2、在實驗過程中，對相同的操作在不同的存儲結(jié)構(gòu)下的時間復(fù)雜度和空間復(fù)雜度進行 分析。算法分析：由于兩種存儲結(jié)構(gòu)都用來創(chuàng)建線性結(jié)構(gòu)的數(shù)據(jù)表，可采用相同的輸出模式和整體結(jié)構(gòu)類似的算法，如下：1v1.0可編輯可

2、修改實驗內(nèi)容和過程：順序存儲結(jié)構(gòu)線性表程序清單：/順序存儲結(jié)構(gòu)線性表的插入刪除#include <iostream>#include <>using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType;/typedef struct ElemType *elem;/int len;int listsize;SqList;定義數(shù)據(jù)元素類型為字符型數(shù)據(jù)元素首地址/當(dāng)前元素個數(shù)/ 當(dāng)前存儲最大容量/構(gòu)造一個空的線性表L13 -int InitList(SqList &a

3、mp;L)二(ElemType *)malloc(LISTSIZE*sizeof(ElemType);if (!exit(-2);/分配空間失敗=0;=LISTSIZE;/在順序線性表L中第i個位置之前插入新的元素eint ListInsert(SqList &L,int i,ElemType e)if (i<1|i>+1) return -1; /i值不合法if >=ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType);/存儲空間已滿，增加分配if(!newelem) exit (-

4、2); /分配失敗=newelem;+=CREMENTSIZE;ElemType *q=&i-1);for (ElemType *p=&);p>=q;-p) *(p+1)=*p; /插入位置及其后的元素后移*q=e; +;return 1;/在順序線性表L中刪除第i個元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e)if (i<1|i> return -1; /i值不合法ElemType *p=&i-1);e=*p; ElemType*q=+;for (+p;p<=q+1;+p

5、) *(p-1)=*p; /被刪除元素之后的元素前移return 1;int main ()SqList L; char e,ch;int i,j,state;InitList(L);/構(gòu)造線性表/數(shù)據(jù)初始化獲取表長判斷進行插入還是刪除操作printf("請輸入原始數(shù)據(jù)(字符串個數(shù)099): L=");gets；for ( j=1;j-1!='0'j+)=j;/j='0'；printf(" 操作：才f入(I)還是刪除(D)n");/AGAIN:cin>>ch;if(ch='I')cout<

6、<"插在第幾個元素之前："；/插入操作cin>>i; cout<<"輸入要插入的新元素："；cin>>e;cout<<endl;printf("輸入數(shù)據(jù)：L=(%s) state=ListInsert (L,i,e);else if (ch='D')cout<<"刪除第幾個元素："cin>>i;cout<<endl;printf("輸入數(shù)據(jù)：L=(%s)state=ListDelete(L,i,e);else

7、goto AGAIN;/cout<<endl<<"正確結(jié)果："if(state=-1) cout<<"ERROR,"printf("L=(%s) ",;/ListInsert(L,%d,%c)",i,e);/刪除操作DeleteList(L,%d,e)”,i);操作指示符輸入錯誤處理輸出結(jié)果if(ch='D'&&state!=-1) cout<<",e="<<e;鏈?zhǔn)酱鎯Y(jié)構(gòu)線性表程序清單：/ 單鏈存儲結(jié)構(gòu)線性表的

8、插入刪除 #include <iostream>#include <>using namespace std;#define null 0typedef char ElemType;/typedef struct LNodeElemType data;struct LNode *next;LNode,*LinkList;int GetElem(LinkList L,int i,ElemType &e)LinkList p;int j;p=L->next; j=1;while(p&&j<i)p=p->next; +j;/if(!p

9、|j>i) return -1;/e=p->data;return 1;int ListInsert(LinkList &L,int i,ElemType e)/在帶頭結(jié)點的單鏈線性表L中第LinkList p,s; int j;p=L;j=0;定義數(shù)據(jù)元素類型為字符型/獲取第i個元素的值尋找第i個元素尋找失敗i個元素之前插入元素ewhile(p&&j<i-1) p=p->next;+j;if(!p|j>i-1) return -1;s=(LinkList) malloc( sizeof(LNode);s->data=e;s->

10、next=p->next;p->next=s;return 1; int ListDelete(LinkList&L,int i,ElemType&e)/在帶頭結(jié)點的單鏈線性表L中，刪除第i個元素，并由e返回其值LinkList p,q; int j;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);return 1

11、;int newdata(LinkList&L,char *ch)int k;printf("請輸入原始數(shù)據(jù)(字符串個數(shù)099): L=");/ 數(shù)據(jù)初始化gets(ch);將初始for (k=0;chk!='0'k+)ListInsert(L,k+1, chk);/化數(shù)據(jù)插入鏈表L中cout<<"OK"<<endl;return k;/返回鏈表中的元素個數(shù)int main ()char *ch;ch=(char *)malloc(100*sizeof(char); /LinkList L;/LNode h

12、ead;/L=&head; =null;int i,k,state; char e,CH,f;k=newdata(L,ch);/=k;/printf(" 操作：插入(定義數(shù)組用來輔助數(shù)據(jù)初始化頭指針頭結(jié)點AGAIN:I )還是刪除(D)n");/調(diào)用函數(shù)使鏈表數(shù)據(jù)初始化將元素個數(shù)存入頭結(jié)點的數(shù)據(jù)域判斷進行插入還是刪除操作cin>>CH;if(CH='I')cout<<"插在第幾個元素之前："；/插入操作cin>>i; cout<<"輸入要插入的新元素："；cin&

13、gt;>e;cout<<endl;printf("輸入數(shù)據(jù)：L=(%s)state=ListInsert(L,i,e);+;else if (CH='D')cout<<"刪除第幾個元素："cin>>i;cout<<endl;printf("輸入數(shù)據(jù)：L=(%s)state=ListDelete(L,i,e);-;else goto AGAIN;/cout<<endl<<"正確結(jié)果："ListInsert(L,%d,%c)",ch,i

14、,e);/刪除操作DeleteList(L,%d,e)",ch,i);操作指示符輸入錯誤處理輸出結(jié)果if(state=-1) cout<<"ERROR," /cout<<"L=("for(int m=1;>=m;m+)/一一輸出數(shù)據(jù)GetElem(L,m,f);cout<<f;cout<<")"if(CH='D'&&state!=-1) cout<<",e="<<e;/刪除操作反饋 e實驗結(jié)果：由

15、于兩個程序的輸出模式相同，在此只列一組測試數(shù)據(jù)：L = () Listinsert (L, 1,'k')L = (EHIKMOP) Listinsert (L, 9, 't')C:Us ers'Ad minist rato rDes kto p；未命名 2.exe .口.| 畫L = (ABCEHKNPQTU) ListInsert(L, 4, 'u')CAUs ersAd minist rate rD kt。p:去命名 2.exeL = () ListDelete (L, 1, e)C：lU$g式Administrmt 口 r日

16、7;ktop未命&Zwxs=L = (DEFILMNORU) ListDelete_Sq(L, 5, e)C:Us ersAcl minist rato r D esp；聲靠名 2.exeL = (CD) ListDelete_Sq(L, 1, e)v1.0可編輯可修改-15 -測試過程中所注意到的問題主要還是輸出與輸入界面的問題，通過靈活使用cout 和 cin 函顯得不夠人性化。數(shù)來不斷改進。另外，在用戶端看來在設(shè)計算法時程序的可重復(fù)性未考慮, 時間復(fù)雜度分析:假定線T表有n個節(jié)點，順序存儲結(jié)構(gòu)下，插入程序段以*(p+1)=*p作為基本操作的原操作， 并討論在最壞情況下的時間復(fù)雜度

17、，記T(n)=O(n);刪除程序段以*(p-1)=*(p)作為基本操作的原操作，并討論在最壞情況下的時間復(fù)雜度，記(n)=O(n)。鏈?zhǔn)酱鎯Y(jié)構(gòu)下，插入程序段以 p=p->next作為基本操作的原操作，并討論在最壞情況下的時間復(fù)雜度，記 T(n)=O(n);刪除程序段以p=p->next作為基本操作的原操作，并討論在最壞情況下的時間復(fù) 雜度，記 丁(n)=O(n)?？偨Y(jié)和感想：改進設(shè)想在于減少中間變量， 優(yōu)化數(shù)據(jù)初始化操作， 和增加程序可重復(fù)性。 具體操作完成估 計就該把上述程序全面修改了，還包括算法的修改和增進。從完成該實驗的過程中， 出現(xiàn)的問題很多，一方面由于對 C語言的不夠熟悉，在語法和語句 執(zhí)行效率上總是不盡人意，另一方面由于在設(shè)計算法時考慮不全面， 在后來寫入程序時屢屢 修改，使程序設(shè)計效率大大降低?；?/p>