單鏈表逆置

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

ADTNumber{

數(shù)據(jù)對象: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)建一個鏈表L。

PrintList(L)

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

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

InverseList(L)

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

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

DestroyList(&L)

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

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

}ADTNumber

2、本程序包含五個模塊:

(1)主程序模塊:

int main(){

定義變量;

接受命令;

處理命令;

退出(return 0);

}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

鏈表:abc123

#include<iostream>

using namespace std;

struct Number //鏈表的類型

{

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

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

}*number;

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

{

Number *s,*r; //定義兩個鏈表類型的臨時指針

char x; //定義一個臨時字符變量

L=(Number *)malloc(sizeof(Number)); //為頭結(jié)點開辟空間

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

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

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

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

{

s=(Number *)malloc(sizeof(Number)); //開辟下一結(jié)點的空間

s->data=x;

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

r=s; //是s指向r

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

}

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

}

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

{

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

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

{

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

p=p->next; //指向下一個結(jié)點

}

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) //銷毀鏈表

{

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

while(q!=NULL)

{

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

p=q;

q=p->next;

}

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

}

int main()

{

cout<<"請輸入一個鏈表:";

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)用銷毀鏈表的函數(shù)

return 0;

}