本文格式為Word版，下載可任意編輯——C語言實現(xiàn)單鏈表逆置什么單鏈表的逆置

問題描述

設(shè)計一個程序，實現(xiàn)單鏈表的逆置。

一、需求分析

⑴按程序提醒輸入并創(chuàng)立一個單鏈表，帶有頭結(jié)點⑵可自定義鏈表的長度，可自定義鏈表儲存的數(shù)據(jù)類型，注意更改相應(yīng)的輸入輸出方式⑶實現(xiàn)單鏈表的逆置，直觀地輸出結(jié)果

二、概要設(shè)計

為實現(xiàn)上述程序功能，需創(chuàng)立以下抽象數(shù)據(jù)類型：

ADTLinkList{

數(shù)據(jù)對象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0}數(shù)據(jù)關(guān)系：R={|ai-1,ai∈D,i=1,2，…，n}基本操作：InitList（//函數(shù)狀態(tài)類型

typedefintElemType;//元素類型

typedefstructnode{

ElemTypedata;structnode*next;

}Node,*LinkList;//節(jié)點類型、

2.基本操作和所需調(diào)用的函數(shù)

//初始化一個鏈表

StatusInitList(LinkList*L){

*L=(LinkList)malloc(sizeof(node));if(!(*L))exit(-2);//內(nèi)存分派失敗(*L)->next=NULL;return1;}

//在初始化的基礎(chǔ)上按順序創(chuàng)立一個鏈表StatusCreatList(LinkListL,intn){

LinkListp=L;inti;

for(i=0;inext)=(LinkList)malloc(sizeof(node));if(!(p->next))exit(-2);//內(nèi)存分派失敗scanf(\p=p->next;}

p->next=NULL;return1;}

//依次輸出單鏈表中的各個元素StatusDisplayList(LinkListL){

LinkListp;p=L->next;while(p){

printf(\p=p->next;

}

printf(\return1;}

//逆置1(遞歸方法)

LinkListIeverse(LinkListpre,LinkListcur){

LinkListhead;if(!cur)

returnpre;

head=Ieverse(cur,cur->next);cur->next=pre;returnhead;}

//逆置2（就地逆置）

StatusIeverse(LinkListL){

LinkListlast=L->next;LinkListfirst;while(last->next){

first=L->next;L->next=last->next;

last->next=L->next->next;L->next->next=first;}

return1;}

3.主函數(shù)及功能的實現(xiàn)voidmain(){

LinkListL;intL_Length;

InitList(//初始化鏈表

printf(\請輸入單鏈表的長度：\\n\scanf(\

if(L_Lengthnext=Ieverse(NULL,L->next);此語句可調(diào)用遞歸方法實現(xiàn)鏈表的逆置//Ieverse(L);//實現(xiàn)單鏈表的就地逆置printf(\DisplayList(L);//顯示逆置后的鏈表}

四、調(diào)試分析

本程序的基本框架比較簡單，整個運行過程主要分為五個部分:主程序模塊（接受鏈表的信息）->創(chuàng)立鏈表模塊（初始化鏈表，即創(chuàng)立一個僅含頭結(jié)點的空鏈表；按主程序模塊接受的元素信息創(chuàng)立鏈表）->輸出單鏈表模塊（按一定格式輸出原始鏈表）->單鏈表逆置模塊（可通過兩種方式實現(xiàn)）->輸出鏈表模塊（按一定格式輸出逆置后的鏈表）。

對于單鏈表的逆置，我想到了兩種方法來實現(xiàn)。第一種為遞歸的方式，但在每一次遞歸調(diào)用時均需創(chuàng)立一個額外的節(jié)點，因此空間利用率較低，算法效率低，同時對于參數(shù)的傳入也應(yīng)特別防備；其次種方式為就地逆置，需要額外的兩個輔助節(jié)點，時間繁雜度為O（L_Length），相比遞歸算法更為高效。開始編寫程序時，混淆了一些函數(shù)參數(shù)的確定，對于傳值和傳址地方的概念區(qū)分的不明白，導(dǎo)致調(diào)試程序是花費了好多的時間。今后應(yīng)重視對參數(shù)的屬性的區(qū)分和認(rèn)識。

五、用戶使用說明

依照程序提醒精心操作即可。

六、測試結(jié)果

測試時采用的數(shù)據(jù)類型為整形，若要使用其他數(shù)據(jù)類型，更改相應(yīng)的輸入輸出語句即可。測試結(jié)果如下：

⑴請輸入單鏈表的長度：3

請依次輸入各個元素的值：479

479Afterreversing!974

Pressanykeytocontinu⑵請輸入單鏈表的長度：6

請依次輸入各個元素的值：49361234

493612Afterreversing!

3412639Pressanykeytocontinue⑶請輸入單鏈表的長度：12

請依次輸入各個元素的值：135792468101315

135792468101315Afterreversing!

151310864297531Pressanykeytocontinue

經(jīng)過三組不同的數(shù)據(jù)測試，程序基本能夠?qū)崿F(xiàn)設(shè)計要求。

測試時采用的數(shù)據(jù)類型為整形，若要使用其他數(shù)據(jù)類型，更改相應(yīng)的輸入輸出語句即可。測試結(jié)果如下：

⑴請輸入單鏈表的長度：3

請依次輸入各個元素的值：479

479Afterreversing!974

Pressanykeytocontinu⑵請輸入單鏈表的長度：6

請依次輸入各個元素的值：49361234

493612Afterreversing!

3412639Pressanykeytocontinue⑶請輸入單鏈表的長度：12

請依次輸入各個元素的值：135792468101315

135792468