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

2、性表的插入刪除 #include #include using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType; /定義數(shù)據(jù)元素類型為字符型 typedef struct ElemType *elem; /數(shù)據(jù)元素首地址 int len; /當前元素個數(shù)int listsize; /當前存儲最大容量 SqList;/構(gòu)造一個空的線性表L intInitList(SqList &L) L.elem=(ElemType *)malloc(LISTSIZE*sizeof(ElemType)

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

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

5、mType*q=L.elem+L.len-1; for (+p;pch;if(ch=I) couti; coute; coutendl; printf(輸入數(shù)據(jù)：L=(%s)ListInsert(L,%d,%c),L.elem,i,e); state=ListInsert (L,i,e); else if (ch=D) couti; coutendl; printf(輸入數(shù)據(jù)：L=(%s)DeleteList(L,%d,e),L.elem,i); state=ListDelete(L,i,e); else goto AGAIN; /操作指示符輸入錯誤處理 coutendl正確結(jié)果：; if(s

6、tate=-1) coutERROR,; printf(L=(%s),L.elem); /輸出結(jié)果 if(ch=D&state!=-1) cout,e=e;鏈式存儲構(gòu)造線性表程序清單：/ - - - - -單鏈存儲構(gòu)造線性表的插入刪除 - - - - -#include #include using namespace std;#define null 0 typedef char ElemType; /定義數(shù)據(jù)元素類型為字符型 typedef struct LNode ElemType data; struct LNode *ne*t; LNode,*LinkList;int GetElem

7、(LinkList L,int i,ElemType &e) /獲取第i個元素的值 LinkList p;int j; p=L-ne*t; j=1; while(p&jne*t; +j; /尋找第i個元素 if(!p|ji) return -1; /尋找失敗 e=p-data; return 1; int ListInsert(LinkList &L,int i,ElemType e) /在帶頭結(jié)點的單鏈線性表L中第i個元素之前插入元素e LinkList p,s; int j; p=L;j=0; while(p&jne*t;+j; if(!p|ji-1) return -1; s=(Link

8、List) malloc( sizeof(LNode); s-data=e;s-ne*t=p-ne*t; p-ne*t=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-ne*t&jne*t;+j; if(!(p-ne*t)|ji-1) return -1; q=p-ne*t;p-ne*t=q-ne*t; e=q-data;free(q); return 1; int newdata(LinkL

9、ist&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中 coutOKCH;if(CH=I) couti; coute; coutendl; printf(輸入數(shù)據(jù)：L=(%s)ListInsert(L,%d,%c),ch,i,e); state=ListInsert(L,i,e); (head.data)+; else if (CH=D) couti; coutendl; printf(輸入數(shù)據(jù)：L=

10、(%s)DeleteList(L,%d,e),ch,i); state=ListDelete(L,i,e); (head.data)-; else goto AGAIN; /操作指示符輸入錯誤處理 coutendl正確結(jié)果：; if(state=-1) coutERROR,; /輸出結(jié)果 cout=m;m+) /一一輸出數(shù)據(jù) GetElem(L,m,f);coutf; cout); if(CH=D&state!=-1) cout,e=ne*t作為根本操作的原操作，并討論在最壞情況下的時間復(fù)雜度，記T(n)=O(n);刪除程序段以p=p-ne*t作為根本操作的原操作，并討論在最壞情況下的時間復(fù)雜度，記T(n)=O(n)?？偨Y(jié)和感想：改良設(shè)想在于減少中間變量，優(yōu)化數(shù)據(jù)初始化操作，和增加程序可重復(fù)性。具體操作完成估計就該把上述程序全面修改了，還包括算法的修改和增進。從完成該實驗的過程中，出現(xiàn)的問題很多，一方面由于對C語言的不夠熟悉，在語法和語句執(zhí)行效率上總是不盡人意，另一方面由于在設(shè)計算法時考慮不全面，在后來寫入程序時屢屢修改，使程序設(shè)計效率大大降低?；谏鲜鰞牲c，今后需全面復(fù)習(xí)C語言以效后計，并做好在設(shè)計算法方面的工作。思考題：實現(xiàn)鏈表的逆置算法：以上述鏈式存儲構(gòu)造線性表程序做根底，可省略數(shù)據(jù)初始化和輸入輸出等操作，此處只列出實現(xiàn)逆置的用戶函數(shù)Inversion()