單鏈表

#include<iostream>

using namespace std;

struct Number //鏈表的類型

{

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è)鏈表類型的臨時(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è)從鍵盤輸入的字符

while(x!='\n') //控制當(dāng)輸入回車鍵時(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è)從鍵盤輸入的字符

}

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

{

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

return 0;

}

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

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é)果:銷毀鏈表L。

}ADTNumber

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

(1)主程序模塊:

int main(){

定義變量;

接受命令;

處理命令;

退出(return 0);

}

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

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

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

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

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

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

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

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

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

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

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

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

鏈表:abc123