實驗二 棧和隊列的操作與應用 - 下載本文

實驗二 棧和隊列的操作與應用

【實驗目的】

1.熟練掌握棧和隊列的特點

2.掌握棧的定義和基本操作,熟練掌握順序棧的操作及應用

3.掌握對列的定義和基本操作,熟練掌握鏈式隊列的操作及應用, 掌握環形隊列的入隊和出隊等基本操作

4. 加深對棧結構和隊列結構的理解,逐步培養解決實際問題的編程能力1.掌握線性表的兩類存儲結構(順序存儲結構和鏈式存儲結構)的描述方法。

【實驗內容】

1.定義順序棧,完成棧的基本操作:空棧、入棧、出棧、取棧頂元素;

2.實現十進制數與八進制數的轉換,十進制數與十六進制數的轉換和任意進制之間的轉換;

3.定義鏈式隊列,完成隊列的基本操作:入隊和出隊;·

··1 親親1··················11112

【實驗指導】

1.利用棧的順序存儲結構,設計一組輸入數據(假定為一組整數),能夠對順序棧進行如下操作:

(1) 初始化一個空棧,分配一段連續的存儲空間,且設定好棧頂和棧底; (2)完成一個元素的入棧操作,修改棧頂指針; (3)完成一個元素的出棧操作,修改棧頂指針; (4)讀取棧頂指針所指向的元素的值;

(5) 將十進制數N 和其它d 進制數的轉換是計算機實現計算的基本問題,其解決方案很多,其中最簡單方法基于下列原理:即除d 取余法。例如:(1348)10=(2504)8

N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2

從中我們可以看出,最先產生的余數4 是轉換結果的最低位,這正好符合棧的特性即后進先出的特性。所以可以用順序棧來模擬這個過程。以此來實現十進制數與八進制數的轉換,十進制數與十六進制數的轉換;

(6)編寫主程序,實現對各不同的算法調用。 2.程序組織

(1)首先將順序棧存儲結構定義放在一個頭文件:如取名為SqStackDef.h。

(2)將順序棧的基本操作算法也集中放在一個文件之中,如取名為SqStackAlgo.h 。如:InitStack、DestroyStack、ClearStack、StackEmpty、StackLength、GetTop、Push、Pop等。

(3)將函數的測試和主函數組合成一個文件,如取名為SqStackUse.cpp。

3.利用隊列的鏈式存儲結構,設計一組輸入數據(假定為一組整數),能夠對鏈式隊列進行如下操作:

(1)初始化一個空隊列,形成一個帶表頭結點的空隊; (2)完成一個元素的入隊操作,修改隊尾指針; (3) 完成一個元素的出隊操作,修改隊頭指針; (4)修改主程序,實現對各不同的算法調用。 4.程序組織

(1)首先將鏈式隊列的存儲結構定義放在一個頭文件:如取名為LinkQueueDef.h。 (2)將鏈式隊列的基本操作算法也集中放在一個文件之中,如取名為LinkQueueAlgo.h。如:InitQueue、DestroyQueue、ClearQueue、QueueEmpty、QueueLength、GetHead_Q、EnQueue、DeQueue、QueueTraverse等。

(3)將函數的測試和主函數組合成一個文件,如取名為LinkQueueUse.cpp。

長春大學計算機科學技術學院實驗報告

日期_______________ 地點______________ 指導教師_____________ 成績

實驗二 棧和隊列的操作與應用

要求:

1.完成算法填空,并上機運行調試。 2.將運行結果粘貼在指定處。

3.將完成的實驗報告單獨建立一個新文件,命名為:班級+學號+姓名+(實驗二),(如:1340538張三(實驗二)),發郵件到:[email protected]。

一、順序棧,對于輸入的任意一個非負十進制整數,打印輸出與其等值的八進制數 1.文件SqStackDef. h 中實現了棧的順序存儲表示 #define STACK_INIT_SIZE 10 /* 存儲空間初始分配量*/ #define STACKINCREMENT 2 /* 存儲空間分配增量*/ typedef struct SqStack {

SElemType *base; /* 在棧構造之前和銷毀之后,base 的值為NULL */ SElemType *top; /* 棧頂指針*/

int stacksize; /* 當前已分配的存儲空間,以元素為單位*/

}SqStack; /* 順序棧*/

2. 文件SqStackAlgo.h 中實現順序棧的基本操作(存儲結構由SqStackDef.h 定義) Status InitStack(SqStack &S) { /* 構造一個空棧S */

S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)

exit(OVERFLOW); /* 存儲分配失敗*/ S.top=S.base;

S.stacksize=STACK_INIT_SIZE; return OK; }

int StackLength(SqStack S)

{ /* 返回S 的元素個數,即棧的長度*/

int a;

a=(S.top-S.base)+1;

編寫此函數 return a ; }

Status Push(SqStack &S,SElemType e) { /* 插入元素e 為新的棧頂元素*/

if(S.top-S.base>=S.stacksize) /* 棧滿,追加存儲空間*/ {

S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREMENT)

*sizeof(SElemType));

if(!S.base)

exit(OVERFLOW); /* 存儲分配失敗*/ S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT; }

*(S.top)++=e; return OK; }

Status Pop(SqStack &S,SElemType &e)

{ /* 若棧不空,則刪除S 的棧頂元素,用e 返回其值,并返回OK;否則返回ERROR */ if(S.top==S.base) return ERROR; e=*--S.top; return OK; }

Status StackEmpty(SqStack S)

{ /* 若棧S 為空棧,則返回TRUE,否則返回FALSE */ if(S.top==S.base) return TRUE; else

return FALSE; }

void conversion10_8( )

{ /* 對于輸入的任意一個非負十進制整數,打印輸出與其等值的八進制數*/ SqStack s;

unsigned n; /* 非負整數*/ SElemType e;

InitStack(s); /* 初始化棧*/ printf(\;

scanf(\; /* 輸入非負十進制整數n */ while(n) /* 當n 不等于0 */ {

n= n%8 ; /* 入棧n 除以8 的余數(8 進制的低位) */ S.base =n ; }

while(!StackEmpty(s)) /* 當棧不空*/ {

e*=S.top ; /* 彈出棧頂元素且賦值給e */ printf(\; /* 輸出e */ }

printf(\; }

3.在SqStackUse.cpp 文件中,測試算法的調用,其中間接調用了順序棧的其他基本算法。

typedef int SElemType; /* 定義棧元素類型為整型*/

#include \常量定義與系統函數原型聲明,與實驗一中的相同*/ #include \采用順序棧的類型定義*/ #include \利用順序棧的基本操作*/ void main()

{ conversion10_8(); /* 十進制數到八進制轉換的驗證*/ }

運行結果:

請將運行結果粘貼在此處





陕西福彩快乐十分玩法