數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)報(bào)告（附源代碼）

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)演示系統(tǒng)報(bào)告（附源代碼）中南大學(xué)

完成日期2023/07/09

1需求分析

線性表：

（1）順序表的建立；輸入為一個(gè)int型的數(shù)據(jù)，輸入輸出的最大元素都是100為空間建立一個(gè)有序的順序表，然后以負(fù)數(shù)終止輸入

（2）順序表的插入輸入兩個(gè)整型數(shù)據(jù)，用來表示插入的位置和元素，輸出為建立時(shí)候有序的順序表和插入的元素，是有序的整型數(shù)據(jù)

順序表的刪除輸入一個(gè)整型數(shù)據(jù)，但是不能超過其數(shù)據(jù)的長度。輸出為刪除后的整型變量

（3）順序表合并先分派儲(chǔ)存空間，然后分別建立兩個(gè)整型變量，分別以負(fù)數(shù)終止輸入，輸出為一串整型變量

鏈表

（1）鏈表插入首先輸入一個(gè)整型變量，改變量用來限定鏈的長度，在輸入整型變量，輸出為該輸入的整型變量，在插入兩個(gè)整型變量，第一個(gè)變量不能超過你所限定鏈的長度，，其次是你所要插入的數(shù)據(jù)，輸入是改鏈插入之后的整型數(shù)據(jù)

（2）鏈表的刪除同理，首先輸入一個(gè)整型變量，改變量用來限定鏈的長度，在輸入整型變量，輸入數(shù)據(jù)，在輸入一個(gè)整型數(shù)據(jù)，表示你所以刪除位置，輸出的是改刪除后的整型變量

（3）鏈表的查找首先輸入一個(gè)整型變量，改變量用來限定鏈的長度，在輸入整型變量，輸入數(shù)據(jù)，在輸入一個(gè)整型數(shù)據(jù)，表示你要查找的元素位置，輸出是一個(gè)整型數(shù)據(jù)，表示你所要查找的元素

（4）鏈表的合并首先輸入一個(gè)整型變量，改變量用來限定鏈的長度，在輸入整型變量，輸入數(shù)據(jù)，在輸入整型變量，改變量用來限定鏈的長度，在輸入整型變量，輸入數(shù)據(jù)，輸出的表示兩個(gè)鏈表是數(shù)據(jù)元素串的模式匹配

輸入是字符型數(shù)據(jù)，輸出是其模式匹配成功的位置，是整型數(shù)據(jù)

2概要設(shè)計(jì)

主菜單順序表菜單鏈表菜單串的退出模式演示匹配系統(tǒng)順序表的建立順序表的插入順序表的刪除順序返回表的主菜合并單鏈表插入鏈表查找鏈鏈表刪除鏈表返回Next合并主菜匹配單Next返回val主菜匹配單1算2算3算4算法法法法5算6算7算8算法法法法9算法0算法上面是程序框圖

3詳細(xì)設(shè)計(jì)，測試結(jié)果和算法分析

算法分析

注：算法后面是數(shù)字是程序框圖所對(duì)應(yīng)的算法算法1：

數(shù)組指針elem表示線性表的基地址，length表示線性表的當(dāng)前長度，順序表的初始化操作就是為順序表分派一個(gè)預(yù)定義大小的數(shù)組空間，并將線性表的當(dāng)前長度設(shè)為“0〞。Listsize,表示當(dāng)前儲(chǔ)存空間的大小，一但插入元素而空間不足時(shí)，

可在進(jìn)行分派，即為順序表增加一個(gè)大小為儲(chǔ)存LISTINCERMENT個(gè)數(shù)據(jù)元素的空間。

StatusInitList_Sq(SqList*L){

L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));L->length=0;

L->listsize=LIST_INIT_SIZE;return1;

}//InitList_Sq;//初始化線性表

算法2：

假設(shè)有n個(gè)數(shù)據(jù)，線性表的插入操作是指在線性表中的第i-1個(gè)數(shù)據(jù)元素和第i個(gè)數(shù)據(jù)元素之間插入一個(gè)新的數(shù)據(jù)元素。數(shù)據(jù)元素ai-1和ai直接的規(guī)律關(guān)系也發(fā)生了變化，所以此時(shí)需要將第n至第i個(gè)元素向后移動(dòng)一個(gè)位置，表長度增加1。

StatusListInsert_Sq(SqList*L,inti,ElemTypee){

//在順序線性表L中第i個(gè)位置之前插入新的元素e，ElemType*newbase,*p,*q;

if(iL->length+1)returnERROR;if(L->length>=L->listsize){newbase=(ElemType*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);L->elem=newbase;L->listsize+=LISTINCREMENT;}

q=for(p=p>=q;--p){*(p+1)=*p;}*q=e;

++L->length;return1;}//ListInsert_Sq

算法3：

長度為n的線性表變成長度為n-1的線性表，數(shù)據(jù)元素ai-1,ai,ai+1直接的規(guī)律關(guān)系發(fā)生變化，為了在存儲(chǔ)結(jié)構(gòu)上反應(yīng)這個(gè)變化，同樣需要移動(dòng)元素，刪除第i個(gè)元素時(shí)需將從第i+1至n個(gè)元素一次向前移動(dòng)一個(gè)位置。intListDelete_Sq(SqList*L,inti){

intj;//i--;

//要?jiǎng)h除的元素下標(biāo)不在長度范圍內(nèi)if(iL->length+1)

return0;

//刪除第i個(gè)元素，即刪除下標(biāo)為[i-1]的元素i--;

//使得第i-1個(gè)元素后面的所有元素往前移for(j=i;jlength;j++)

L->elem[j]=L->elem[j+1];//i--;

//使得線性表的長度減L->length--;

return1;}

算法4；

分出元素比較有三種狀況，當(dāng)*pa=*pb,只需要將兩者之一插入Lc中，由于La和Lb的元素一次遞增，在對(duì)Lb中的每個(gè)元素，不需要在La中從表頭至表尾進(jìn)行全程探尋，由于用新的線性表Lc,表示并集，則插入實(shí)際上是借助復(fù)制來操作完成的。

StatusMergeList_Sq(SqListLa,SqListLb,SqList*Lc){

ElemType*pa=La.elem,*pb=Lb.elem,*pc;ElemType*pa_last,*pb_last;

//確定Lc線性表的長度為兩個(gè)線性表的長度之和Lc->listsize=Lc->length=La.length+Lb.length;//為Lc線性表分派內(nèi)存空間

pc=Lc->elem=(ElemType*)malloc(Lc->listsize*sizeof(ElemType));//若分派內(nèi)存溢出，則退出if(!Lc->elem)

exit(OVERFLOW);

//使得pa_last指針指向La線性表的最終一個(gè)元素pa_last=La.elem+La.length-1;

//使得pb_last指針指向Lb線性表的最終一個(gè)元素pb_last=Lb.elem+Lb.length-1;

//將兩個(gè)線性表中的值都逐個(gè)賦值到新的線性表Lc中

//當(dāng)兩個(gè)線性表中的值都還未完成賦值時(shí)，先將兩個(gè)值中較小的賦值給Lc線性表的當(dāng)前元素

while(panext=p->next;p->next=s;

所以我們可以根據(jù)這個(gè)算法對(duì)鏈表進(jìn)行插入操作StatusCreat_List(Link_List

L->next=NULL;Link_Listp;//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表for(inti=n;i>0;i--){p=(Link_List)malloc(sizeof(LNode));scanf(\p->next=L->next;L->next=p;}

return1;}

StatusInsert_List(Link_Listintj=0;while(pj++;}

if(!p||j>i-1)returnERROR;

Link_Lists=(Link_List)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return1;}

算法6：

從表中最終一個(gè)記錄開始，逐個(gè)進(jìn)行記錄關(guān)鍵字和給定值的比較，，若某個(gè)記錄的關(guān)鍵字和給定值的比較相等，則查找成功，找的所查的記錄