数据结构上机实验二(更新).doc

数据结构上机实验二实验内容:栈和链队列的基本操作实验目的: 1)熟悉C/C+基本编程,培养动手能力. 2)通过实验,加深对堆栈和队列的理解.实验要求: 1) 栈和队列的显示要作为函数被调用. 2) 把自己使用的栈和队列结构明确的表达出来.分组要求：可单独完成，也可两人一组。评分标准： 1) 只完成第一或第二题，3分； 2）完成一和二题，得5分； 3）在2）基础上，可选做三）中的题目。题目:一)堆栈题（顺序栈）:创建一个栈+入栈+出栈 (1)由键盘一个一个的输入正整数，建立相应的堆栈，输入-1时，堆栈结束； (2)在（1）中创建的堆栈中添加一个元素； (3)在（1）中创建的堆栈中删除一个元素；(要求在显示器可见)；#include#include#include #define OK 1#define ERROR 0#define Status int#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct Stackint *base;int *top;Status stacksize;SqStack;Status CreatStack(SqStack &S)/创建空栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(struct Stack);if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status InStack(SqStack &S)/创建栈元素 int e;printf(请输入初始栈元素:n);scanf(%d,&e);while(e!=-1)if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(struct Stack);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=e;scanf(%d,&e);return OK;Status Push(SqStack &S,int e)/栈加元素if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(struct Stack); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S,int e)/栈中删除元素if(S.top=S.base) return ERROR;e=*-S.top; printf(n请输出出栈元素:%d,e); return OK;void print()printf(n菜单：);printf(n1.创建栈：);printf(n2.入栈：);printf(n3.出栈：);printf(n4.退出：);void printS(SqStack &S)/打印堆栈int *p;printf(请输出堆栈中的元素:n);for(p=S.base;pS.top;p+)printf(%d ,*p);void main()/主程序SqStack S;int e,choice;doprint();printf(n请输入你的选项：); scanf(%d,&choice);switch(choice)case 1:if(CreatStack(S)=1)if(InStack(S)=1)printS(S);break;case 2:printf(n请输入入栈元素：);scanf(%d,&e);Push(S,e);printS(S);break;case 3:Pop(S,e);printS(S);break;case 4:break;while(1);二)链队列题目：初始化队列+入队列+出队列+销毁队列 (1)初始化一个链队列；(2)在初始化好的链队列中放入数，入队列，完成后要求显示；(3)从队列中出队列，要求显示出来的元素和之后的队列；(4)销毁创建的队列，释放内存；#include#include#define OK 1#define ERROR 0#define Status inttypedef struct Qnode int data; struct Qnode *next;QNode, *QueuePtr;typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue; Status CreatQueue(LinkQueue &Q)/初始化队列 Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front-next=NULL; return OK;Status InQueue(LinkQueue &Q) /输入队列元素QueuePtr p;int e;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR;printf(请输入初始队列元素：n);scanf(%d,&e);while(e!=-1)p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;p=(QueuePtr)malloc(sizeof(QNode);if(!p) return ERROR;scanf(%d,&e);return OK;Status EnQueue(LinkQueue &Q,int e)/入队列 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,int &e)/出队列 QueuePtr p;if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;Status DestroyQueue (LinkQueue &Q)/ 销毁队列 while(Q.front) Q.rear=Q.front-next; free(Q.front); Q.front=Q.rear; return OK;void print()/打印菜单printf(n菜单：);printf(n1.创建队列：);printf(n2.入队列：);printf(n3.出队列：);printf(n4.销毁队列：);void printS(LinkQueue &Q)/打印队列QueuePtr p;p=Q.front-next;printf(请输出队列中的元素:n);while(p)printf(%d ,p-data);p=p-next;void main()LinkQueue Q;int e,choice;doprint();printf(n请输入你的选项：); scanf(%d,&choice);switch(choice)case 1:if(CreatQueue(Q)=1)if(InQueue(Q)=1)printS(Q);break;case 2:printf(请输入入队列元素：);scanf(%d,&e);EnQueue(Q,e);printS(Q);break;case 3:DeQueue(Q,e);printS(Q);break;case 4:DestroyQueue(Q);if(Q.front=NULL)printS(Q);else printf(队列不存在);break;while(1);三）应用题（1）编制程序，将输入的十进制数据M 转换为八进制数据M8，将其调试通过。在此基础上修改程序，实现十进制数据M向任意进制（2-9进制）的转换。（1分）#include#include#include #define OK 1#define ERROR 0#define Status int#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct Stackint *base;int *top;Status stacksize;SqStack;Status CreatStack(SqStack &S)/创建空栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(struct Stack);if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status InStack(SqStack &S,int d,int N)/创建栈元素while(d!=0)if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(struct Stack);if(!S.base) return ERROR;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+=d%N;d=d/N;return OK;void print()printf(n菜单：);printf(n2.转化为2进制：);printf(n3.转化为3进制：);printf(n4.转化为4进制：);printf(n5.转化为5进制：);printf(n6.转化为6进制：);printf(n7.转化为7进制：);printf(n8.转化为8进制：);printf(n9.转化为9进制：);void printS(SqStack &S)/打印堆栈int *p;printf(转换后的数为:n);for(p=S.top-1;p=S.base;p-)printf(%d ,*p);void main()/主程序SqStack S;int e,choice;doprint();printf(n请输入需要转化的进制:); scanf(%d,&choice);printf(请输入十进制数元素:);scanf(%d,&e);if(CreatStack(S)=1)if(InStack(S,e,choice)=1)printS(S);while(1);（2）编制程序，从键盘接收一个字符串(长度最长设为100)，检测其中的括号()，匹配情况，若有成对括号则在屏幕输出括号对及其所包含的字符内容。（2分）#include#include#include #define OK 1#define ERROR 0#define Status int#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct Stackchar *base;char *top;Status stacksize;SqStack;typedef struct Qnode char data; struct Qnode *next;QNode, *QueuePtr;typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue; Status CreatStack(SqStack &S)/创建空栈S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(struct Stack);if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack &S,char e)/栈加元素if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(struct Stack); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S,char &i)/栈中删除元素if(S.top=S.base) return ERROR;i=*-S.top;return OK;Status CreatQueue(LinkQueue &Q)/初始化队列 Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front-next=NULL; return OK;Status EnQueue(LinkQueue &Q,char e)/入队列 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,char &j)/出队列QueuePtr p;if(Q.front=Q.rear) return ERROR;p=Q.front-next; j=p-data;Q.front-next=p-next;if(Q.rear=p) Q.rear=Q.front;free(p);return OK;void print()printf(n菜单：);printf(n1.创建栈和队列：);printf(n2.输入字符串：);printf(n3.查找字符：);void printS(SqStack &S)/打印堆栈char *p;printf(请输出堆栈中的元素:);for(p=S.base;pnext;printf(n请输出队列中的元素:);while(p)printf(%c,p-data);p=p-next;void printW(LinkQueue &Q,char c,char d)printf(n括号中的元素:);printf(%c,c);QueuePtr p;p=Q.front-next;while(p-data!=d)printf(%c,p-data);p=p-next;printf(%c,d);void Search(LinkQueue &Q,SqStack &S,char c,char d)char i,j;intflag,flag1;flag=0;flag1=0;QueuePtr p;p=Q.front-next;while(p)p=p-next;while(Q.front!=Q.rear)DeQueue(Q,j);if(j=c)flag+;while(S.top!=S.base)Pop(S,i);if(i=d)flag1+;printW(Q,c,d);if(flag=0) printf(ERROR:不存在字符);if(flag1=0) printf(ERROR:字符不匹配);void main()/主程序SqStack S;LinkQueue Q;int choice;char e,c,d;doprint();printf(n请输入你的选项：); scanf(%d,&choice);switch(choice)case 1:CreatStack(S);CreatQueue(Q);break;case 2:printf(请输入字符串:n);e=getchar();while(e!=)Push(S,e);EnQueue(Q,e);e=getchar();printS(S);printQ(Q);break;case 3:fflush(stdin);printf(请输入查找的字符:);scanf(%c%c,&c,&d);Search(Q,S,c,d);break;while(1);（3）假设以和分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由和组成的序列，称可以操作的序列为合法序列，否则为非法序列。编写一个算法，判断所给的序列S1：，S：及S：，S：是否合法。（1分）#include#include#include #define OK 1#define ERROR 0#define Status int#define STACK_INIT_SIZE 100#define STACKINCREMENT 10typedef struct Stackint *base;int *top;Status stacksize;SqStack;Status CreatStack(SqStack &S)/创建空栈S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(struct Stack);if(!S.base) return ERROR; S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK;Status Push(SqStack &S,int e)/栈加元素if(S.top-S.base=S.stacksize) /栈满,追加存储空间 S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(struct Stack); if(!S.base) return ERROR; S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK;Status Pop(SqStack &S,int &j)/栈中删除元素if(S.top=S.base) return ERROR;j=*-S.top;return OK;void print()/菜单printf(n菜单：);printf(n1.创建空栈：);printf(n2.输入需要判断的序列：n);void Judge(SqStack &S,char *p,int i)int e,j;while(i=0)if(S.top=S.base)if(*p=I)Push(S,1);p+;else if(*p=O)if(Pop(S,j)=0)printf(序列不合法n);S.top-;break;p+;i-;if(S.top=S.base)printf(序列合法n);else if(S.topS.base) printf(序列不合法n);void main()/主程序SqStack S;int choice,i=0;char aSTACK_INIT_SIZE,e,*p;doprint();printf(请输入你的选项：); scanf(%d,&choice);switch(choice)case 1:CreatStack(S);break;case 2:fflush(stdin);e=getchar();while(e!=)ai=e;i+;e=getchar();p=a;Judge(S,p,i-1);break;while(1); 1 1 1 1 2 1 1 3 3 1（4）二项式(a+b)n展开后，其系数构成杨辉三角形，利用队列写出打印杨辉三角形的前n行的程序。（1分）#include#include#define OK 1#define ERROR 0#define Status inttypedef struct Qnode int data; struct Qnode *next;QNode, *QueuePtr;typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针LinkQueue; Status CreatQueue(LinkQueue &Q)/初始化队列 Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode); if(!Q.front) return ERROR; Q.front-next=NULL; return OK;Status EnQueue(LinkQueue &Q,int e)/入队列 QueuePtr p;p=(QueuePtr)malloc(sizeof(QNode); if(!p) return ERROR; p-data=e; p-next=NULL; Q.rear-next=p; Q.rear=p; return OK;Status DeQueue(LinkQueue &Q,int &e)/出队列 QueuePtr p;if(Q.front=Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return OK;Status GetHead(LinkQueue &Q,int &x)/ QueuePtr p;if(Q.front=Q.rear) return ERROR; p=Q.front-next; x=p-data; return OK;void YangHuiTriangle(LinkQueue &Q,int N)int temp,x,n,i;CreatQueue(Q); EnQueue(Q,1); /第1行元素入队for(n=2;n=N;n+)/产生第i行元素并入队，同时打印第i-1行元素 EnQueue(Q,1);for(i=1;i=n-2; i+)/利用第n-1行元素产生第n行的中间n-2个元素 DeQueue(Q,temp); printf(%d ,temp); GetHead(Q,x); temp=temp+x; EnQueue(Q,temp); DeQueue(Q,x); printf(%d n,x); /打印第N-1行的最后一个元素 EnQueue(Q,1); /第N行的最后一个元素入队 while(Q.front!=Q.rear) /打印最后一行元素 DeQueue(Q,x); printf(%d ,x); printf(n);void main()LinkQueue Q;int e;while(1)printf(请输入打印的行数n);scanf(%d,&e);printf(%d行杨辉三角为:n,e);YangHuiTriangle(Q,e);（5）基于堆栈，编写迷宫求解程序。（3分）#include#include#include #define OK 1#define ERROR 0#define Status int#define STACK_INIT_SIZE 300#define STACKINCREMENT 10typedef struct Stackint *bas