華南農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)上機(jī)答案實(shí)驗(yàn)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上華南農(nóng)業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)上機(jī)答案實(shí)驗(yàn) 8583 順序棧的基本操作時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):530 通過次數(shù):212 題型: 編程題 語言: 無限制Description創(chuàng)建一個(gè)空的順序棧，并實(shí)現(xiàn)棧的入棧、出棧、返回棧的長(zhǎng)度、返回棧頂元素、棧的遍歷等基本算法。請(qǐng)將下#include<malloc.h> #include<stdio.h> #define OK 1#define ERROR 0#define STACK_INIT_SIZE 100 / 存儲(chǔ)空間初始分配量#define STAC

2、KINCREMENT 10 / 存儲(chǔ)空間分配增量typedef int SElemType; / 定義棧元素類型typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等struct SqStackSElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; / 棧頂指針int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位; / 順序棧Status InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧S，該棧預(yù)定義大小為STACK_INIT_SIZE/ 請(qǐng)補(bǔ)

3、全代碼S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status Push(SqStack &S,SElemType e) / 在棧S中插入元素e為新的棧頂元素/ 請(qǐng)補(bǔ)全代碼if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCR

4、EMENT)*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e) / 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR/ 請(qǐng)補(bǔ)全代碼if(S.top=S.base) return ERROR;e=*-S.top;return OK;Status GetTop(SqStack S,SElem

5、Type &e) / 若棧不空，則用e返回S的棧頂元素，并返回OK；否則返回ERROR/ 請(qǐng)補(bǔ)全代碼if(S.top=S.base) return ERROR;e=*(S.top-1);return OK;int StackLength(SqStack S) / 返回棧S的元素個(gè)數(shù)/ 請(qǐng)補(bǔ)全代碼return S.top-S.base;Status StackTraverse(SqStack S)/ 從棧頂?shù)綏５滓来屋敵鰲Ｖ械拿總€(gè)元素SElemType *p = (SElemType *)malloc(sizeof(SElemType); p = S.top ; /請(qǐng)?zhí)羁読f(S

6、.top=S.base)printf("The Stack is Empty!"); /請(qǐng)?zhí)羁誩lseprintf("The Stack is: ");p-;while(p>=S.base) /請(qǐng)?zhí)羁誴rintf("%d ", *p);p- ; /請(qǐng)?zhí)羁誴rintf("n");return OK;int main()int a;SqStack S;SElemType x, e;if(InitStack(S) / 判斷順序表是否創(chuàng)建成功，請(qǐng)

7、填空printf("A Stack Has Created.n");while(1)printf("1:Push n2:Pop n3:Get the Top n4:Return the Length of the Stackn5:Load the Stackn0:ExitnPlease choose:n");scanf("%d",&a);switch(a)case 1: scanf("%d", &x);if(!Push(

8、S,x) printf("Push Error!n"); / 判斷Push是否合法，請(qǐng)?zhí)羁誩lse printf("The El ement %d is Successfully Pushed!n", x); break;case 2: if(!Pop(S,e) printf("Pop Error!n"); / 判斷Pop是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successfully Poped!n", e);b

9、reak;case 3: if(!GetTop(S,e)printf("Get Top Error!n"); / 判斷Get Top是否合法，請(qǐng)?zhí)羁誩lse printf("The Top Element is %d!n", e);break;case 4: printf("The Length of the Stack is %d!n",StackLength(S); /請(qǐng)?zhí)羁誦reak;case 5: StackTraverse(S); /請(qǐng)?zhí)羁誦reak;case 0: retur

10、n 1;8584 循環(huán)隊(duì)列的基本操作時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):366 通過次數(shù):157 題型: 編程題 語言: 無限制Description創(chuàng)建一個(gè)空的循環(huán)隊(duì)列，并實(shí)現(xiàn)入隊(duì)、出隊(duì)、返回隊(duì)列的長(zhǎng)度、返回隊(duì)頭元素、隊(duì)列的遍歷等基本算法。請(qǐng)將下面的程序補(bǔ)充完整。#include<malloc.h> #include<stdio.h> #define OK 1#define ERROR 0typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等typedef int QEl

11、emType;#define MAXQSIZE 100 / 最大隊(duì)列長(zhǎng)度(對(duì)于循環(huán)隊(duì)列，最大隊(duì)列長(zhǎng)度要減1)typedef structQElemType *base; / 初始化的動(dòng)態(tài)分配存儲(chǔ)空間int front; / 頭指針,若隊(duì)列不空,指向隊(duì)列頭元素int rear; / 尾指針,若隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置SqQueue;Status InitQueue(SqQueue &Q) / 構(gòu)造一個(gè)空隊(duì)列Q，該隊(duì)列預(yù)定義大小為MAXQSIZE/ 請(qǐng)補(bǔ)全代碼Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType);if(

12、!Q.base) return ERROR;Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q,QElemType e) / 插入元素e為Q的新的隊(duì)尾元素/ 請(qǐng)補(bǔ)全代碼if(Q.rear+1)%MAXQSIZE=Q.front)return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;Status DeQueue(SqQueue &Q, QElemType &e) / 若隊(duì)列不空, 則刪除Q的隊(duì)頭元素, 用e返回其值, 并

13、返回OK; 否則返回ERROR/ 請(qǐng)補(bǔ)全代碼if(Q.front=Q.rear)return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXQSIZE;return OK;Status GetHead(SqQueue Q, QElemType &e)/ 若隊(duì)列不空，則用e返回隊(duì)頭元素，并返回OK，否則返回ERROR/ 請(qǐng)補(bǔ)全代碼if(Q.front=Q.rear) return ERROR;e=Q.baseQ.front;return OK;int QueueLength(SqQueue Q) / 返回Q的元素個(gè)數(shù)/ 請(qǐng)補(bǔ)全代碼ret

14、urn (Q.rear+MAXQSIZE-Q.front)%MAXQSIZE;Status QueueTraverse(SqQueue Q) / 若隊(duì)列不空，則從隊(duì)頭到隊(duì)尾依次輸出各個(gè)隊(duì)列元素，并返回OK；否則返回ERROR.int i;i=Q.front;if(Q.front=Q.rear)printf("The Queue is Empty!"); /請(qǐng)?zhí)羁誩lseprintf("The Queue is: ");while(i<Q.rear) /請(qǐng)?zhí)羁誴rintf("%d &q

15、uot;,Q.basei); /請(qǐng)?zhí)羁読 = i+1; /請(qǐng)?zhí)羁誴rintf("n");return OK;int main()int a;SqQueu e S;QElemType x, e;if(InitQueue(S) / 判斷順序表是否創(chuàng)建成功，請(qǐng)?zhí)羁誴rintf("A Queue Has Created.n");while(1)printf("1:Enter n2:Delete n3:Get the Front n4:Return the Length of the Queuen5:Load th

16、e Queuen0:ExitnPlease choose:n");scanf("%d",&a);switch(a)case 1: scanf("%d", &x);if(!EnQueue(S,x) printf("Enter Error!n"); / 判斷入隊(duì)是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successfully Entered!n", x); break;

17、case 2: if(!DeQueue(S,e) printf("Delete Error!n"); / 判斷出隊(duì)是否合法，請(qǐng)?zhí)羁誩lse printf("The Element %d is Successfully Deleted!n", e);break;case 3: if(!GetHead(S,e)printf("Get Head Error!n"); / 判斷Get Head是否合法，請(qǐng)?zhí)羁誩lse printf("The Head of the Queue

18、is %d!n", e);break;case 4: printf("The Length of the Queue is %d!n",QueueLength(S); /請(qǐng)?zhí)羁誦reak;case 5: QueueTraverse(S); /請(qǐng)?zhí)羁誦reak;case 0: return 1;8585 棧的應(yīng)用進(jìn)制轉(zhuǎn)換時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):320 通過次數(shù):203 題型: 編程題 語言: 無限制Description利用順序棧的基本操作算法，編寫滿足下列要求的數(shù)制轉(zhuǎn)換程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打

19、印輸出與其等值的八進(jìn)制數(shù)。 #include<malloc.h> #include<stdio.h>#include<stdlib.h>#define OVERFLOW -1 #define OK 1#define ERROR 0#define STACK_INIT_SIZE 20 / 存儲(chǔ)空間初始分配量#define STACKINCREMENT 10 / 存儲(chǔ)空間分配增量typedef int SElemType; / 定義棧元素類型typedef int Status; / Status是函數(shù)的類型,其值

20、是函數(shù)結(jié)果狀態(tài)代碼，如OK等typedef struct SqStackSElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; / 棧頂指針int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位SqStack; / 順序棧Status InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧S，該棧預(yù)定義大小為STACK_INIT_SIZES.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERF

21、LOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; Status Push(SqStack &S,SElemType e) / 在棧S中插入元素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+

22、=STACKINCREMENT;*S.top+=e;return OK;Status StackTraverse(SqStack S)/ 從棧頂?shù)綏５滓来屋敵鰲Ｖ械拿總€(gè)元素SElemType *p; p = S.top; /請(qǐng)?zhí)羁読f(!p)printf("The Stack is Empty!"); /請(qǐng)?zhí)羁誩lsep-; while(p!=S.base) /請(qǐng)?zhí)羁?printf("%d", *p);p-; /請(qǐng)?zhí)羁誴rintf("%d", *p);printf("n

23、");return OK;Status Modulo (SqStack &S,int x)int y=x;if(y!=0)Push(S,y%8);Modulo(S,y/8); return OK;int main()int a;SqStack S;SElemType x, e;InitStack(S); scanf("%d", &x);Modulo(S,x); StackTraverse(S);8586 括號(hào)匹配檢驗(yàn)時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):679 通過次數(shù):182 題型: 編程題

24、 語言: 無限制Description利用棧編寫滿足下列要求的括號(hào)匹配檢驗(yàn)程序：假設(shè)表達(dá)式中允許包含兩種括號(hào)：圓括號(hào)和方括號(hào)，其嵌套的順序隨意，即()或()等為正確的格式，(或()或()均為不正確的格式。輸入一個(gè)包含上述括號(hào)的表達(dá)式，檢驗(yàn)括號(hào)是否配對(duì)。本題給出部分check()函數(shù)，要求將check()函數(shù)補(bǔ)充完整，并完成整個(gè)程序。typedef char SElemType;#include"malloc.h" #include"stdio.h"#include"math.h"#inc

25、lude"stdlib.h" / exit()#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Status; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等#define STACK_INIT_SIZE 10 / 存儲(chǔ)空間初始分配量#define STACKINCREMENT 2 / 存儲(chǔ)空間分配增量struct SqStackSElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; / 棧頂指針i

26、nt stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位; / 順序棧Status InitStack(SqStack &S)S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK; Status StackEmpty(SqStack S)if(S.top=S.base) return TRUE;else return FALSE;Status Push(

27、SqStack &S,SElemType e)if(S.top-S.base>=S.stacksize)S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)if(

28、S.top=S.base) return ERROR;e=*-S.top;return OK;void check() / 對(duì)于輸入的任意一個(gè)字符串，檢驗(yàn)括號(hào)是否配對(duì)SqStack s;SElemType ch80,*p,e;if(InitStack(s) / 初始化棧成功/printf("請(qǐng)輸入表達(dá)式n");scanf("%s",ch);p=ch;while(*p) / 沒到串尾switch(*p)case '(':case '':Push(s,*p);p+

29、;break; / 左括號(hào)入棧，且p+case ')':case '':if(!StackEmpty(s) / 棧不空Pop(s,e); / 彈出棧頂元素if(*p=')'&&e!='('|*p=''&&e!='') / 彈出的棧 頂元素與*p不配對(duì)printf("isn't matched pairsn&a

30、mp;quot;);exit(ERROR);elsep+;break; / 跳出switch語句else / ?？誴rintf("lack of left parenthesisn");exit(ERROR);default: p+; / 其它字符不處理，指針向后移if(StackEmpty(s) / 字符串結(jié)束時(shí)?？誴rintf("matchingn");elseprintf("lack of right parenthesisn");int main()check();8587 行編

31、輯程序時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):578 通過次數(shù):173 題型: 編程題 語言: 無限制Description利用棧編寫簡(jiǎn)單的行編輯程序：接受用戶從終端輸入的程序或數(shù)據(jù)，在輸入過程中，允許用戶輸入出差錯(cuò)，并在發(fā)現(xiàn)有誤時(shí)可以及時(shí)更正。例如：當(dāng)用戶發(fā)現(xiàn)剛剛鍵入的一個(gè)字符是錯(cuò)的時(shí)，可以補(bǔ)進(jìn)一個(gè)退格符“#”，以表示前一個(gè)字符無效；如果發(fā)現(xiàn)當(dāng)前鍵入的行內(nèi)差錯(cuò)較多或難以補(bǔ)救，則可以鍵入一個(gè)退行符“”，以表示當(dāng)前行中的字符均無效。例如：假設(shè)從終端接受了這樣兩行字符： whli#ilr#e (s#*s) outchaputchar(*s=#+); 則實(shí)際有效的是下列兩行： whil

32、e (*s) putchar(*s+); 本題目給出部分函數(shù)，要求將行編輯函數(shù)補(bǔ)充完整，并完成整個(gè)程序。 typedef char SElemType;#include"malloc.h" #include"stdio.h"#include"math.h"#include"stdlib.h" / exit()#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int Statu

33、s; / Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等#define STACK_INIT_SIZE 10 / 存儲(chǔ)空間初始分配量#define STACKINCREMENT 2 / 存儲(chǔ)空間分配增量struct SqStackSElemType *base; / 在棧構(gòu)造之前和銷毀之后，base的值為NULLSElemType *top; / 棧頂指針int stacksize; / 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位; / 順序棧Status InitStack(SqStack &S) / 構(gòu)造一個(gè)空棧SS.base=(SElemType*)malloc(ST

34、ACK_INIT_SIZE*sizeof(SElemType);if(!S.base) return ERROR;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return OK;Status StackEmpty(SqStack S) / 若棧S為空棧，則返回TRUE，否則返回FALSEif(S.top=S.base) return TRUE;else return FALSE;Status ClearStack(SqStack &S) / 把S置為空棧S.top=S.base;return OK;Status DestroyStack(S

35、qStack &S) / 銷毀棧S，S不再存在free(S.base);S.base=NULL;S.top=NULL;S.stacksize=0;return OK;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) return ERROR;S.top=S.

36、base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status Pop(SqStack &S,SElemType &e)/ 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERRORif(S.top=S.base) return ERROR;e=*-S.top;return OK;Status StackTraverse(SqStack S,Status(*visit)(SElemType)/ 從棧底到棧頂依次對(duì)棧中每個(gè)元素調(diào)用函數(shù)visit()。/ 一旦visit(

37、)失敗，則操作失敗while(S.top>S.base)visit(*S.base+);printf("n");return OK;Status visit(SElemType c)printf("%c",c);return OK;void LineEdit() / 利用字符棧s，從終端接收一行并送至調(diào)用過程的數(shù)據(jù)區(qū)。算法3.2SqStack s;char ch,c;int n,i;InitStack(s);scanf("%d",&n);ch=getchar

38、();for(i=1;i<=n;i+) ch=getchar();while(ch!='n')switch(ch)case '#':Pop(s,c);break; / 僅當(dāng)棧非空時(shí)退棧case '':ClearStack(s);break; / 重置s為空棧default :Push(s,ch); / 有效字符進(jìn)棧ch=getchar(); / 從終端接收下一個(gè)字符StackTraverse(s,visit); / 將從棧底到棧頂?shù)臈?nèi)字符輸出ClearStack(s); / 重置s為

39、空棧DestroyStack(s);void main()LineEdit(); 8588 表達(dá)式求值時(shí)間限制:1000MS 內(nèi)存限制:1000K提交次數(shù):182 通過次數(shù):84 題型: 編程題 語言: 無限制Description利用棧編寫表達(dá)式求值程序：輸入含有“+”、“-”、“*”、“/”四則運(yùn)算的表達(dá)式，其中負(fù)數(shù)要用（0-正數(shù)）表示，并以=結(jié)束。要求輸出表達(dá)式的值（兩運(yùn)算符號(hào)的優(yōu)先關(guān)系見教材表3.1）。此題目可選做。#include<stdio.h>#include <math.h>#define True 1#define Fa

40、lse 0#define size 1005/字符棧typedef char stack;struct nodestack asize;int top;int Isempty(struct node *s)return (s->top=-1?True:False);int Isfull(struct node *s)return (s->top+1=size?True:False);int Push(struct node *s,stack x)if(!Isfull(s) s->top+;s->as->top=x;retur

41、n True;elsereturn False;int Pop(struct node *s, stack *x) if(!Isempty(s)*x=s->as->top;s->top-;return True;elsereturn False;int Gettop(struct node *s) stack x;if(!Isempty(s)x=s->as->top;return x;else return False;/整形 棧typedef int sta;struct node1sta asize;int top;in

42、t Isempty1(struct node1 *s)return (s->top=-1?True:False);int Isfull1(struct node1 *s)return (s->top+1=size?True:False);int Push1(struct node1 *s,sta x)if(!Isfull1(s) s->top+; s->as->top=x;return True;elsereturn False;int Pop1(struct node1 *s, sta *x) if(!Isempty1(s

43、)*x=s->as->top;s->top-;return True;elsereturn False;sta Gettop1(struct node1 *s) sta x;if(!Isempty1(s)x=s->as->top;return x;else return False;int In(char ch)if(ch>=48&&ch<=57)return True;elsereturn False;char compare(char a,char b) int

44、 i,j;char c7='+','-','*','/','(',')','#'char d77='>','>','<','<','<',&

45、;#39;>','>','>','>','<','<','<','>','>','>','>',&#3

46、9;>','>','<','>','>','>','>','>','>','<','>','&

47、amp;gt;','<','<','<','<','<','=','','>','>','>','>',&

48、amp;#39;','>','>','<','<','<','<','<','','=',;if(b='=') return '>'for(i=0;ci!=a;i+)for(j=0;cj!=b;j+)return dij;sta claculat(sta a,char op,sta b) sta m;if(op=&#39