數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)單鏈表操作

本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)單鏈表操作《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》報(bào)告

題目：?jiǎn)捂湵聿僮?/p>

專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班級(jí)：

單鏈表操作

針對(duì)帶頭結(jié)點(diǎn)的單循環(huán)鏈表，編寫實(shí)現(xiàn)以下操作的算法函數(shù)。

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

實(shí)現(xiàn)要求：

⑴單鏈表建立函數(shù)create：先輸入數(shù)據(jù)到一維數(shù)組A[M]中，然后根據(jù)一維數(shù)組A[M]建立一個(gè)單循環(huán)鏈表，使鏈表中個(gè)元素的次序與A[M]中各元素的次序一致，要求該函數(shù)的時(shí)間繁雜度為O(m)；

⑵定位查找函數(shù)Locate：在所建立的單循環(huán)鏈表中查找并返回值為key的第1個(gè)元素的結(jié)點(diǎn)指針；若找不到，則返回NULL；

⑶求出該鏈表中值最大和次大的元素值，要求該算法的時(shí)間繁雜度為O(m)，最大和次大的元素值通過(guò)指針變量帶回，函數(shù)不需要返回值；

⑷將鏈表中所有值比key(值key通過(guò)形參傳入)小的結(jié)點(diǎn)作為值為key的結(jié)點(diǎn)前驅(qū)，所有值比key大的結(jié)點(diǎn)作為值為key的結(jié)點(diǎn)后繼，并盡量保持原有結(jié)點(diǎn)之間的順序，要求該算法的時(shí)間繁雜度為O(m);⑸設(shè)計(jì)一個(gè)菜單，具有上述處理要求和退出系統(tǒng)功能。

⒈本人完成的工作：

一、定義結(jié)構(gòu)體：LNode二、編寫以下函數(shù)：（1）建立單循環(huán)鏈表（2）建立定位查找函數(shù)（3）求出鏈表中最大和次大值

（4）將鏈表中的值和輸入的Key比較，小的作為key前驅(qū)結(jié)點(diǎn)，大的作為key

的后繼結(jié)點(diǎn)

三、設(shè)計(jì)具有上述處理要求和退出系統(tǒng)菜單

⒉所采用的數(shù)據(jù)結(jié)構(gòu)：?jiǎn)捂湵頂?shù)據(jù)結(jié)構(gòu)的定義：

typedefstructNode{

DataTypedata;

//數(shù)據(jù)域//指針域

//定義結(jié)點(diǎn)的結(jié)構(gòu)體

structNode*next;

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

}LNode;

//結(jié)點(diǎn)的類型

⒊所設(shè)計(jì)的函數(shù)

（1）Create(void)

LNode*Create(void){

//勾鏈建表，使鏈表中元素的次序與數(shù)組A各元素次序一致for(j=0;jdata=A[j];

//根據(jù)一維數(shù)組A[M]建立一個(gè)單循環(huán)鏈表

inti,j,n,A[M];

//建立數(shù)組A

//建立單循環(huán)鏈表，鏈表頭結(jié)點(diǎn)head作為返回值

LNode*head,*p,*move;

head=(LNode*)malloc(sizeof(LNode));head->next=head;move=head;

printf(\請(qǐng)輸入數(shù)組元素的個(gè)數(shù)：\scanf(\printf(\請(qǐng)輸入數(shù)組：\for(i=0;inext=move->next;move->next=p;move=move->next;

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

}

開(kāi)始定義變量：inti,j,n,A[M];LNode*head,*p,*move;建立空單循環(huán)鏈表head建立一維數(shù)組Aj=0NJdata=A[j];p->next=move->next;J++終止

（2）Locate(LNode*head,DataTypekey)

LNode*Locate(LNode*head,DataTypekey){

LNode*q=head->next;

//查找并返回值為key的第1個(gè)元素的結(jié)點(diǎn)指針；若找不到，則返回NULL

//建立定位查找函數(shù)Locate

while(q!=head

if(q->data==key)

returnq;

else

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

}

{

printf(\查找的結(jié)點(diǎn)不存在！！\\n\}

returnNULL;

開(kāi)始定義變量：*q=head->next；;Yq!=head&&q->data!=keyq=q->nextNq->data==keyNYreturnqReturnNULlL終止

（3）Search(LNode*head,DataType*a,DataType*b)

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

//求鏈表的最大值和次大值，分別由*a和*b帶回

voidSearch(LNode*head,DataType*a,DataType*b){

LNode*p,*Max,*Secmax;

p=head->next->next;//*Max和*Secmax指第一個(gè)結(jié)點(diǎn)，*p指向其次個(gè)結(jié)點(diǎn)，Max=head->next;

Secmax=head->next->next;;while(p!=head)

{

if(Max->data>p->data){}else{}

p=p->next;

}

}

*a=Max->data;*b=Secmax->data;

//把最大和次大值分別賦值給*a和*b

Secmax=Max;Max=p;

//*Sexmax指向次大值

if(p->data>Secmax->data)

Secmax=p;

//*Max指向最大值

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

開(kāi)始LNode*p,*Max,*Secmax;p=head->next->next;Max=head->next;Secmax=p;NP!=headYMax->data>p->dataYp->data>Secmax->dataYp=p->next;Secmax=p;NSecmax=Max;Max=p;N*a=Max->data;*b=Secmax->data;終止

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

（4）Sort(LNode*head)

//查找key,把鏈表中比key小的作為前驅(qū)結(jié)點(diǎn)，比key大的作為后繼結(jié)點(diǎn)

LNode*Sort(LNode*head){

//*front指向key前部分鏈表，*rear指向key后部分鏈表

DataTypekey;

LNode*k,*p,*front,*rear,*L;

front=head;p=head->next;

printf(\請(qǐng)輸入key：\scanf(\L=Locate(head,key);k=L;rear=k;while(p!=head){

if(front->next!=k){}

//調(diào)用Locate()查找key

//判斷key前面鏈表是否已經(jīng)比較完畢

if(p->data>k->data)//將key結(jié)點(diǎn)前驅(qū)比key大的插到key后面{}else{}

p=p->next;

//移動(dòng)指針

front->next=front->next->next;p->next=rear->next;rear->next=p;rear=rear->next;p=front->next;

//*p指回key的前驅(qū)結(jié)點(diǎn)

//斷開(kāi)結(jié)點(diǎn)//插入結(jié)點(diǎn)

front=front->next;

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

else{p=rear->next;

if(p->datadata)//將key結(jié)點(diǎn)后繼比key小的插到key前面{rear->next=rear->next->next;p->next=front->next;

front->next=p;front=front->next;p=rear->next;

}else{p=p->next;

rear=rear->next;

}

}

}

returnhead;}

//斷開(kāi)結(jié)點(diǎn)

//插入結(jié)點(diǎn)

//*p指回key的后繼結(jié)點(diǎn)

//移動(dòng)指針

//返回頭指針

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

開(kāi)始LNode*k,*p,*front,*rear,*L;DataTypekey;front=head;p=head->next;printf(\請(qǐng)輸入key：\scanf(\L=Locate(head,key);k=L;rear=k;Np!=headYfront->next!=kYNp->data>k->dataYfront->next=front->next->next;p->next=rear->next;rear->next=p;rear=rear->next;p=front->next;p->datadataYrear->next=rear->next->next;p->next=front->next;front->next=p;front=front->next;p=rear->next;p=rear->next;NNp=p->next;front=front->nextp=p->next;rear=rear->next;returnhead;終止

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

（5）主函數(shù)：

voidmain(){

LNode*L,*W,*H;DataTypea,b;

//主函數(shù)

intkey,choice;printf(\H=Create();//界面美化printf(\

//choice記載操作,key為輸入值

//調(diào)用Create()建立單循環(huán)鏈表

printf(\

******\\n\

printf(\

*\\n\

printf(\

定

位

查

找

1*\\n\

printf(\

輸

出

最

大

和

次

大

值

2*\\n\

printf(\

輸

出

比

較

值

key

后

的

結(jié)

果

3*\\n\

printf(\

重

新

輸

入

一

個(gè)

數(shù)

組

4*\\n\

printf(\

退

出

系

統(tǒng)

0*\\n\

printf(\

*\\n\

printf(\

******\\n\

printf(\

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

//功能選擇

printf(\請(qǐng)選擇系統(tǒng)功能:\scanf(\printf(\

while(choice!=0){switch(choice){case1:

{printf(\請(qǐng)輸入要查找的值：\scanf(\L=Locate(H,key);if(L!=NULL)

printf(\查找成功!!\\n\

}

break;

case2:

{Search(H,

printf(\最大值：%d\\n\

printf(\次大值：%d\\n\

}

break;

case3:{

H=Sort(H);

//查找數(shù)值key并返回指針//求鏈表的最大和次大值

//將key插入鏈表中

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告內(nèi)容及其格式

}

W=H->next;

printf(\結(jié)果是：\while(W!=H){}

printf(\

printf(\W=W->next;

//依次輸出

//輸出結(jié)果

break;

case4:

main();

default:}

printf(\請(qǐng)輸入正確的選項(xiàng)??！\\n\

//錯(cuò)誤處理

//功能重復(fù)

printf(\

******\\n\

printf(\*\\n\

printf(\

定

位

查

找

1*\\n\

printf(\

輸

出

最

大

和

次

大

值

2*\\n\

printf(\

輸

出

比

較

值

key

后

的

結(jié)

果

3*\\n\

printf(\

重

新

輸

入