棧和鏈表的綜合應(yīng)用

摘 要:本文從設(shè)計(jì)任務(wù)，對問題分析理解，及算法中涉及知識(shí)點(diǎn)來簡述棧和鏈表的綜合應(yīng)用。

關(guān)鍵詞:棧鏈表入棧出棧

中圖分類號(hào):TH-39文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1674-098X(2011)01(a)-0205-01

1 設(shè)計(jì)的任務(wù)

借助一個(gè)棧，將帶頭結(jié)點(diǎn)的單鏈表逆置，用C語言實(shí)現(xiàn)。

2 對問題的分析和理解

首先理解棧和鏈表的基本知識(shí)，然后建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表，建立一個(gè)空棧，將建立的鏈表中數(shù)據(jù)入棧，再出棧賦給鏈表。最后輸出逆置單鏈表。

3 算法中涉及到的知識(shí)點(diǎn)

棧:僅限定在一端進(jìn)行插入和刪除操作的線性表，允許插入和刪除的一端稱為棧頂，另一端稱為棧底;沒有任何元素的棧稱為空棧;棧中元素之間的關(guān)系為一對一的關(guān)系;棧的運(yùn)算規(guī)則:只能在棧頂運(yùn)算，先進(jìn)后出(FILO)或者是后進(jìn)先出(LIFO);入棧是從棧頂(表尾)插入元素;出棧是從棧頂(表尾)刪除元素;棧的基本運(yùn)算有:構(gòu)造空棧，進(jìn)棧—可形象地理解為壓入，這時(shí)棧中會(huì)多一個(gè)元素，出棧—可形象地理解為彈出，彈出后棧中就無此元素了。

4 設(shè)計(jì)用計(jì)算機(jī)環(huán)境:turbo C2.0/ VC++環(huán)境

5 任務(wù)的源代碼

#include

#include

#define maxsize 1024

typedef struct//自定義棧類型

{int data[maxsize];

int top;}seqstack;

typedef struct note //單鏈表

{int data;

struct note *next;}linklist;

linklist *head，*p;

linklist *createlist()//創(chuàng)建單鏈表

{char ch;int x;

printf(\"請輸入一個(gè)字符和數(shù)字\");

linklist *head，*r，*p;

p=(linklist *)malloc(sizeof(linklist));

head=p;p->next=NULL;r=p;ch=getchar();

while(ch!='?')

{scanf(\"%d\"，x);

p=(linklist *)malloc(sizeof(linklist));

p->data=x;p->next=NULL;r->next=p;r=r->next;ch=getchar();}

return (head);}

seqstack *init_seqstack() //置空棧

{ seqstack *s;

s=(seqstack *)malloc(sizeof(seqstack));

s->top=-1; return s;}

int empty_seqstack(seqstack *s) //判空棧

{if(s->top==-1)return 1;

elsereturn 0;}

int push_seqstack(seqstack *s，int x)//入棧

{if(s->top==maxsize-1)return 0;

else {s->top++;s->data[s->top]=x;return 1;}

int pop_seqstack(seqstack *s) //出棧

{ int x;

if(empty_seqstack(s)) return 0;

else{x=s->data[s->top]; s->top--;return x;} }

void main()主程序

{linklist *head，*p;

seqstack *s;

int select，loop=1;

while(loop)

{ printf(\"[1]建立單鏈表[2]將鏈表數(shù)據(jù)入棧[3]輸出逆置鏈表==》\");

scanf(\"%d\"，select);

switch(select)

{case 1: head=createlist();break;

case 2: s=init_seqstack();p=head->next;

while(p->next!=NULL)

{push_seqstack(s，p->data); p=p->next;} break;

case 3:p=head->next;

while(p->next!=NULL)

{p->data=pop_seqstack(s); p=p->next;}

p=head->next;

while(p->next!=NULL) //打印輸出

{printf(\"%4d\"，p->data); p=p->next->next;}

printf(\"\\");break;}}}

6 采用的算法(圖1流程圖)

7 測試結(jié)果 (圖2)

8 結(jié)語

棧是操作受限的線性表，具有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。順序表示的棧，必須預(yù)先分配空間，并且空間大小受限，使用起來限制比較多。而且，由于限定存取位置，順序表示的隨機(jī)存取的優(yōu)點(diǎn)就沒有了，但是，在現(xiàn)實(shí)生活中解決倒序問題是還是用順序棧比較方便。

參考文獻(xiàn)

[1] 王學(xué)軍.數(shù)據(jù)結(jié)構(gòu)[M].中國計(jì)劃出版社.

[2] 嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)[M].清華大學(xué)出版社.