單鏈表逆置需求分析

1、本程序由用戶輸入運(yùn)行命令和數(shù)據(jù)，運(yùn)行結(jié)果顯示在其后。

2、程序執(zhí)行的命令包括:

1)創(chuàng)建一個(gè)鏈表;2)執(zhí)行鏈表的逆置;3)結(jié)束。

2、測(cè)試數(shù)據(jù)

鏈表:abc123

1、鏈表的抽象數(shù)據(jù)類(lèi)型定義為:

ADTNumber{

數(shù)據(jù)對(duì)象:D={ai|ai∈(0，1，…，9)，i=0,1，2，…，n，n≥0}

數(shù)據(jù)關(guān)系:R={<ai-1,ai>|ai-1,ai∈D,i=1,2，…，n}

基本操作:

CreateList(&L)

操作結(jié)果:創(chuàng)建一個(gè)鏈表L。

PrintList(L)

初始條件:鏈表L已存在。

操作結(jié)果:在屏幕上輸出鏈表的值。

InverseList(L)

初始條件:鏈表L已存在。

操作結(jié)果:將鏈表逆置。

DestroyList(&L)

初始條件:鏈表L已存在。

操作結(jié)果:銷(xiāo)毀鏈表L。

}ADTNumber

2、本程序包含五個(gè)模塊:

(1)主程序模塊:

int main(){

定義變量;

接受命令;

處理命令;

退出(return 0);

}

(2)創(chuàng)建鏈表模塊--產(chǎn)生一個(gè)鏈表;

(3)輸出鏈表模塊--把鏈表輸出;

(4)鏈表逆置模塊--將鏈表逆置;

(5)銷(xiāo)毀鏈表模塊--程序結(jié)束后釋放鏈表開(kāi)辟的空間。

各模塊之間的調(diào)用關(guān)系如下:

主程序模塊 創(chuàng)建鏈表模塊

創(chuàng)建鏈表模塊 輸出鏈表模塊 鏈表逆置模塊

輸出鏈表模塊 創(chuàng)建鏈表模塊 銷(xiāo)毀鏈表模塊

#include<iostream>

using namespace std;

struct Number //鏈表的類(lèi)型

{

char data; //鏈表當(dāng)前結(jié)點(diǎn)的值

struct Number *next; //鏈表當(dāng)前結(jié)點(diǎn)指向下一結(jié)點(diǎn)的指針

}*number;

void CreateList(Number *&L) //創(chuàng)建鏈表

{

Number *s,*r; //定義兩個(gè)鏈表類(lèi)型的臨時(shí)指針

char x; //定義一個(gè)臨時(shí)字符變量

L=(Number *)malloc(sizeof(Number)); //為頭結(jié)點(diǎn)開(kāi)辟空間

L->next=NULL; //此時(shí)頭結(jié)點(diǎn)的后繼指針和前驅(qū)指針賦值為空

r=L; //是r指針指向頭結(jié)點(diǎn)

x=getchar(); //用x接受一個(gè)從鍵盤(pán)輸入的字符

while(x!='\n') //控制當(dāng)輸入回車(chē)鍵時(shí)結(jié)束

{

s=(Number *)malloc(sizeof(Number)); //開(kāi)辟下一結(jié)點(diǎn)的空間

s->data=x;

r->next=s; //r的后繼指針指向s

r=s; //是s指向r

x=getchar(); //用x接受一個(gè)從鍵盤(pán)輸入的字符

}

r->next=NULL; //當(dāng)創(chuàng)建結(jié)束時(shí)，r的后繼指針為空

}

void PrintList(Number *L) //輸出鏈表

{

Number *p=L->next; //定義一個(gè)臨時(shí)指針并指向鏈表的第一個(gè)結(jié)點(diǎn)

while(p!=NULL) //判斷結(jié)點(diǎn)是否為空，空就結(jié)束

{

cout<<p->data; //輸出結(jié)點(diǎn)的值

p=p->next; //指向下一個(gè)結(jié)點(diǎn)

}

cout<<endl; //換行

}

void InverseList(Number *L) //鏈表的逆置

{

Number *p=L->next,*q=L->next;

q=q->next;

p->next=NULL;

p=q;

while(p!=NULL)

{

q=q->next;

p->next=L->next;

L->next=p;

p=q;

}

}

void DestroyList(Number *&L) //銷(xiāo)毀鏈表

{

Number *p=L,*q=p->next;

while(q!=NULL)

{

free(p); //釋放p的空間

p=q;

q=p->next;

}

cout<<"釋放鏈表"<<endl;

}

int main()

{

cout<<"請(qǐng)輸入一個(gè)鏈表:";

CreateList(number); //調(diào)用創(chuàng)建鏈表

cout<<"********************************************************************************";

cout<<"輸入的鏈表為:"<<endl;

PrintList(number); //調(diào)用輸出鏈表

InverseList(number); //調(diào)用逆置鏈表

cout<<"此鏈表的逆置為:"<<endl;

PrintList(number); //調(diào)用輸出鏈表

cout<<"********************************************************************************";

DestroyList(number); //調(diào)用銷(xiāo)毀鏈表的函數(shù)

return 0;

}

1、在創(chuàng)建長(zhǎng)整數(shù)時(shí)，沒(méi)有使用getchar()來(lái)接受字符，而用C++中的cin>>來(lái)輸入，這樣使得每一次輸入之后都要按回車(chē)鍵，而且在輸入結(jié)束時(shí)控制也不方便，使用getchar()函數(shù)解決了這一問(wèn)題。

2、首先，遇到的問(wèn)題就是if條件中的"= ="中少了一個(gè)"="導(dǎo)致編譯正確，但是一運(yùn)行就錯(cuò)誤，這個(gè)問(wèn)題不該錯(cuò)的，以后一定重視每一個(gè)細(xì)節(jié)。還有就是鏈表的使用過(guò)程中，指針太多，一會(huì)兒指向這個(gè)，一會(huì)兒又指向那個(gè)，如果思路不清楚的話，很容易弄暈的;有時(shí)候一個(gè)指針指向空的時(shí)候根本就不知道，編譯沒(méi)錯(cuò)誤，檢查不出來(lái)，一運(yùn)行就不正確，有時(shí)候運(yùn)行正確了，但是結(jié)果卻不正確，這還好點(diǎn)，有時(shí)候指針指向空了，運(yùn)行就彈出錯(cuò)誤要終止程序。經(jīng)過(guò)一步一步的測(cè)試，一步一步的運(yùn)行，花了不少時(shí)間終于弄出來(lái)了。

3、在銷(xiāo)毀鏈表的時(shí)候，也遇到過(guò)一個(gè)問(wèn)題，現(xiàn)在還沒(méi)弄明白是為什么。在銷(xiāo)毀鏈表的函數(shù)中，如果參數(shù)接受兩個(gè)鏈表來(lái)銷(xiāo)毀的話，如:void DestroyList(Number *&L1，Number *&L2)，運(yùn)行會(huì)出錯(cuò)，或許是我寫(xiě)的代碼不正確;但是，當(dāng)用void DestroyList(Number *&L)來(lái)一個(gè)鏈表一個(gè)鏈表的銷(xiāo)毀就沒(méi)問(wèn)題。