数据结构实验三

姓名：

学号：

实验项目 栈和队列及其应用（I） 实验内容 2．采用顺序存储结构，实现队列的存储和基本操作。 算法设计与程序实现： 算法分析一： 算法分析 1、定义栈元素类型与空间大小，对栈进行基本操作。 2、定义init函数初始化栈，push函数入栈，pop则是出栈元素等。相应基本算法描述见书上p47页。 3、判断栈是否为空以及是否为满则定义isempty和isfull函数将指针分别指向栈首与栈为即可判断。 4、搜索栈中元素，则将输入元素与栈内元素一一进行比较，操作数依次递增。对比完成后输出其操作数即为元素位置。 算法分析二： 1、头文件与题目一相似，根据书中P61页内容进行一定的更改后可得相应代码。 2、创建新队列—清空—判断是否为空是否为满，其原理同上。队列长度以及查出删除元素均以书上为标准。 1．采用顺序存储结构，实现栈的存储和基本操作。 核心程序 #include #include typedef int TYPE; //定义栈元素类型 #define SIZE 5 //栈空间大小 //声明顺序栈结构体 typedef struct { TYPE data[SIZE];//记录栈中元素值 int length; //记录栈的长度 }seqStack; void init(seqStack*);//初始化 void push(seqStack*,TYPE);//入栈 TYPE pop(seqStack*);//出栈 void clear(seqStack*);//清空 1．采用顺序存储结构，实现栈的存储和基本操作。 电子信息工程学院2015级《数据结构》实验报告

bool isEmpty(seqStack*);//判断栈是否为空 bool isFull(seqStack*);//判断栈是否已满 int length(seqStack);//返回栈的大小 void ergodic(seqStack*);//遍历栈中元素 int search(seqStack*,TYPE);//搜索，返回是第几个元素，失败则返回-1 int main() { seqStack nodes; //栈初始化 init(&nodes); //元素入栈 printf(\"输入要入栈的元素个数:\"); int count = 0; scanf(\"%d\ TYPE elem; printf(\"输入%d个入栈元素：\ if(count<=SIZE-length(nodes)) { while(count) { scanf(\"%d\ push(&nodes,elem); count--; } } else { printf(\"\\n输入数据过多或者栈已满，入栈失败\\n\"); } //元素出栈 if(!isEmpty(&nodes)) printf(\"出栈元素是：%d\\n\ else printf(\"栈已空，出栈失败!\\n\"); 电子信息工程学院2015级《数据结构》实验报告

//搜索元素 printf(\"输入要搜索的元素：\"); scanf(\"%d\ int number = search(&nodes,elem); if(number>0) printf(\"找到元素%d是第%d个元素\\n\ else printf(\"元素%d不存在\\n\ //遍历栈 printf(\"遍历栈：\"); ergodic(&nodes); //清空栈 clear(&nodes); printf(\"清空后遍历:\"); ergodic(&nodes); return 0; } //栈初始化 void init(seqStack* stack) { stack->length = 0; } //入栈操作 void push(seqStack* stack,TYPE e) { if(!isFull(stack)) { stack->data[stack->length] = e; stack->length++; } //判断上面最后一个元素插入后，栈满则清空缓冲区 //不能用else分支，必须用isFull再判断一次 if(isFull(stack)) { scanf(\"%*[^\\n]\"); scanf(\"%*c\"); } } 电子信息工程学院2015级《数据结构》实验报告 //出栈操作 TYPE pop(seqStack* stack) { stack->length--; return stack->data[stack->length]; } //判断是否为空 bool isEmpty(seqStack* stack) { return stack->length==0; } //判断是否为满 bool isFull(seqStack* stack) { return stack->length>=SIZE; } //返回栈的长度 int length(seqStack stack) { return stack.length; } //遍历栈 void ergodic(seqStack* stack) { for(int i=0;ilength;i++) printf(\"%d \ printf(\"\\n\"); } //搜索栈中元素,返回元素首次在栈中出现的位置 int search(seqStack* stack,TYPE e) { int pos=0; for(int i=0;ilength;i++) { if(stack->data[i]==e) { pos=i+1; break; 电子信息工程学院2015级《数据结构》实验报告

} } return pos; } //清空栈 void clear(seqStack* stack) { stack->length = 0; } 2．采用顺序存储结构，实现队列的存储和基本操作。 #include using namespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define QUEUE_INIT_SIZE 100 //队列存储空间的初始分配量 #define QUEUEINCREMENT 10 //队列存储空间的分配增量 #define MAXQSIZE 100 //队列最大长度 typedef int QElemType; //顺序表中元素的数据类型 typedef int Status; //函数结果状态类型 typedef struct{ QElemType base[MAXQSIZE]; int front; //头指针，若队列不空，指向队列头元素 int rear; //尾指针，若队列不空，指向队列尾元素的下一个位置 int count; }SqQueue; Status InitQueue(SqQueue &Q){ //构造一个空队列Q Q.front=Q.rear=0; Q.count=0; return OK; } Status EnQueue(SqQueue &Q,QElemType e){ //插入元素e为Q的新的队尾元素 if((Q.rear+1)%MAXQSIZE==Q.front) return ERROR; //队列满 Q.base[Q.rear]=e; //将元素赋值给队尾 Q.rear=(Q.rear+1)%MAXQSIZE; //rear指针向后移一位置，若到最后则转到数组头部 Q.count++; return OK; 电子信息工程学院2015级《数据结构》实验报告

} Status GetHead_Sq(SqQueue &Q,QElemType *e){ //若队列不空，则返回队头元素e，并返回函数结果状态OK;否则返回ERROR if(Q.front==Q.rear) return ERROR; *e=Q.base[Q.front]; cout<<\"队列首元素：\"<<*e<>n; cout<<\"请输入元素：\"; for(int i=0;i>data; EnQueue(Q,data); } cout<<\"队列为：\"; 电子信息工程学院2015级《数据结构》实验报告 QueueTraverse(Q); GetHead_Sq(Q,&data); DeQueue(Q,&data); cout<<\"删除头元素后的队列为：\"; QueueTraverse(Q); system(\"pause\"); } 栈的运行结果： 运行结果 队列的运行结果： 运行结果分析：栈和队列的基本操作主要是输入、输出、插入和删除，通过运行结果，可以看出程序实现了这些功能。 实验总结： 实验总结 本次实验中要求我们掌握顺序栈的基本操作以及循环队列的基本操作实现方法。与之前的实验方法一致我们需要 首先要定义类型、分配栈空间。其中初始化、清空、判断为空为满操作不尽相同。 在虽然最终结果调试无误，但程序中也有很多不足之处。如在最开始的bool工具包并不存在，因此我们 需要重新进行宏定义，但基本上在第二章中的头文件定义内容中包含了所需内容。 在调试过程中，程序运行完出现了闪退的问题，在经过一系列尝试后发现程序运行调试则会出现闪退 问题，因此我们采用的是运行不调试解决了问题。

电子信息工程学院2015级《数据结构》实验报告