浦江移动网络学院实验报告书课程名：《数据结构》题目：线性数据结构实验班级：学号：姓名：线性表算法实现与应用报告要求1目的与要求:1）掌握栈与队列的数据类型描述及特点；2）掌握栈的顺序和链式存储存表示与基本算法的实现；3）掌握队列的链式和循环存储表示与基本操作算法实现;4) 掌握栈与队列在实际问题中的应用和基本编程技巧;5）按照实验题目要求，独立完成实际程序的编写编写、调试和运行，并通过用例数的运行过程抓获相关屏面验证程序设计的正确性；7）认真书写实验报告，并在下周一以前按时提交。

2 实验内容或题目（一）必做题：1、实现顺序栈的创建（初始化）、压入（插入）、弹出（删除）操作，要求给出栈的操作变化过程；2、实现链栈的创建（初始化）、压入（插入）、弹出（删除）操作，要求给出栈的操作变化过程；3、实现循环队列的创建、进队、出队等基本操作，并实时给出队列的操作变化状态；4、实现链式队列的创建、进队、出队等基本操作，并实时给出队列的操作变化状态；（二）选做题（有能力同学建议多做此类应用题目）：1、实现表达式求值算法；2、用递归算法实现汉诺塔问题；3、使用循环队列实现打印杨辉三角形算法。

3 实验步骤与源程序第一题#define TRUE 1#define FALSE 0#define Stack_Size 50#include <iostream>using namespace std;typedef struct{int elem[Stack_Size];int top;}SeqStack;void InitStack(SeqStack *S){S->top =-1;}int IsEmpty(SeqStack *S){return(S->top==-1?TRUE:FALSE);}int IsFull(SeqStack *S){return(S->top==Stack_Size-1?TRUE:FALSE); }int Push(SeqStack *S,int x){if(S->top==Stack_Size-1)return(FALSE);S->top++;S->elem[S->top] = x;return(TRUE);}int Pop(SeqStack *S,int *x){if(S->top == -1)return(FALSE);else{*x = S->elem[S->top];S->top--;return(TRUE);}}int GetTop(SeqStack *S,int *x){if(S->top == -1)return(FALSE);else{*x = S->elem[S->top];return(TRUE);}int main(){SeqStack S;int x;int y;int i;InitStack(&S);if(!IsFull(&S))cout<<"栈为空"<<endl;cout<<"输入要压入的元素:"<<endl; for(i=0;i<10;i++){cin>>y;Push(&S,y);}GetTop(&S,&x);cout<<"栈首元素:"<<endl;cout<<x<<endl;cout<<"弹出的元素为:"<<endl; while(!IsEmpty(&S)){Pop(&S,&x);cout<<x<<" ";}cout<<endl;return 0;}第二题#define TRUE 1#define FALSE 0#include<iostream>using namespace std;typedef struct node{int data;struct node *next;}LinkStackNode;typedef LinkStackNode *LinkStack; int GetTop(LinkStack top,int *x)if(NULL==top->next )return FALSE;*x=top->next ->data ;return TRUE;}int IsEmpty(LinkStack top){return NULL==top->next?TRUE:FALSE;}int InitStack(LinkStack *top){*top=(node*)malloc(sizeof(node));if(NULL==*top)return FALSE;(*top)->next =NULL;return TRUE;}int Push(LinkStack top, int x){LinkStackNode *temp;temp=(LinkStackNode *)malloc(sizeof(LinkStackNode));if(temp==NULL)return(FALSE);temp->data=x;temp->next=top->next;top->next=temp;return(TRUE);}int Pop(LinkStack top, int *x){LinkStackNode * temp;temp=top->next;if(temp==NULL)return(FALSE);top->next=temp->next;*x=temp->data;free(temp);return(TRUE);}void main(){InitStack(&s);int x,i;if(IsEmpty(s))cout<<"栈为空"<<endl;cout<<"请输入要压入的元素："<<endl; for(i=0;i<10;i++){cin>>x;Push(s,x);}GetTop(s,&x);cout<<"栈的首元素为:"<<endl;cout<<x<<endl;cout<<"弹出的元素依次为:"<<endl; while(!IsEmpty(s)){Pop(s, &x);cout<<x<<" ";}cout<<endl;}第三题#define TRUE 1#define FALSE 0#define MAXSIZE 50#include<iostream>using namespace std;typedef struct{int element[MAXSIZE];int front;int rear;}SeqQueue;void InitQueue(SeqQueue *Q){Q->front=Q->rear=0;}int EnterQueue(SeqQueue *Q, int x) {if((Q->rear+1)%MAXSIZE==Q->front) return(FALSE);Q->element[Q->rear]=x;Q->rear=(Q->rear+1)%MAXSIZE;return(TRUE);}int DeleteQueue(SeqQueue *Q, int *x) {if(Q->front==Q->rear)return(FALSE);*x=Q->element[Q->front];Q->front=(Q->front+1)%MAXSIZE; return(TRUE);}int GetHead(SeqQueue *Q, int *x) {if(Q->front==Q->rear)return(FALSE);*x=Q->element[Q->front];return(TRUE);}int IsEmpty(SeqQueue *Q){if(Q->front==Q->rear)return(TRUE);elsereturn(FALSE);}void main(){SeqQueue s;InitQueue(&s);int x,i;if(IsEmpty (&s))cout<<"队列为空"<<endl;cout<<"请输入元素:"<<endl;for(i=0;i<10;i++){cin>>x;EnterQueue(&s,x);GetHead(&s,&x);cout<<"队列首元素为:"<<endl;cout<<x<<endl;cout<<"弹出的元素依次为:"<<endl; while(!IsEmpty(&s)){DeleteQueue(&s,&x);cout<<x<<" ";}cout<<endl;if(IsEmpty (&s))cout<<"空队列"<<endl;}第四题#define TRUE 1#define FALSE 0#include <iostream>using namespace std;typedef struct Node{int data;struct Node *next;}LinkQueueNode;typedef struct{LinkQueueNode *front ; LinkQueueNode *rear;}LinkQueue;int IsEmpty(LinkQueue *Q){return Q->front ==Q->rear?TRUE:FALSE; }int GetTop(LinkQueue *Q,int *x){if(NULL==Q->rear )return FALSE;*x=Q->rear->data ;return TRUE;}int InitQueue(LinkQueue *Q){if(Q->front!=NULL){Q->rear=Q->front;Q->front->next=NULL;return (TRUE);}else return(FALSE);}int EnterQueue(LinkQueue *Q,int x){LinkQueueNode *NewNode;NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL){NewNode->data=x;NewNode->next=NULL;Q->rear->next=NewNode;Q->rear=NewNode;return (TRUE);}else return(FALSE);}int DeleteQueue(LinkQueue *Q,int *x){LinkQueueNode *p;if(Q->front==Q->rear)return(FALSE);p=Q->front->next ;Q->front->next =p->next ;if(Q->rear==p)Q->rear=Q->front;*x=p->data;free(p);return (TRUE);}int main(){LinkQueue q;int x,i;InitQueue(&q);if(IsEmpty(&q))cout<<"队列为空"<<endl;cout<<"请输入要压入的元素:"<<endl;for(i=0;i<10;i++)cin>>x;EnterQueue(&q,x);}GetTop(&q,&x);cout<<"队列首元素为:"<<endl;cout<<x<<endl;cout<<"队列弹出的元素依次为:"<<endl;for(i=0;i<10;i++){DeleteQueue(&q,&x);cout<<x<<" ";}cout<<endl;return 0;}4 测试数据与实验结果（可以抓图粘贴）第一题第二题《数据结构》实验报告- 10 -第三题第四题5 结果分析与实验体会这是第二次数据结构实验，这次老师只给了一些函数，而没给出主函数，相对于上次难度是增大了，可是考察的内容都是书本上最基本的，全都是书本上的思想和算法，因此只要掌握了书本上的内容，很多问题就可以迎刃而解了。