【数据结构】宜宾大学-计院-实验四

实验目的：

1．掌握栈的顺序存储结构和链式存储结构
2．实现栈的基本操作，包括栈的建立、求长度、取栈顶元素、入栈、出栈、判栈空 等函数

实验内容：

1．完成顺序栈的建立
2．实现顺序栈的入栈
3．实现顺序栈的出栈
4．判断顺序栈是否为空
5．实现取栈顶元素
6. 实现十进制数与其它进制数的转换

实验结果：

每个同学都要记录实验结果（无论对与错），如果程序调试中有什么错误，记录并分析原因，必须另寻时间调试成功。

实验报告:（及时撰写实验报告）：

实验测试结果：

代码实现1.0：（C/C++）【含注释】

#define SIZE_MAX 2  //初始栈容量
#define STACK_INCREMENT 5  //扩容增量
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;typedef int datatype;//top减base为有效元素个数
typedef struct Stack
{datatype* top;//top指向栈顶元素的下一个地址datatype* base;//栈底int capacity;//容量
}ST;void InitStack(ST& head)
{datatype* tmp = (datatype*)malloc(sizeof(datatype) * SIZE_MAX);if (tmp == NULL) return;//都指向首地址head.top = head.base = tmp;head.capacity = SIZE_MAX;
}void DestroyStack(ST& head)
{free(head.base);head.base = head.top = NULL;head.capacity = 0;
}bool EmptyStack(ST& head)
{return head.base == head.top;
}
bool OverflowStack(ST& head)
{if (head.top - head.base == head.capacity)return true;return false;
}
void Push(ST& head, datatype x)
{if (OverflowStack(head)){datatype* tmp = (datatype*)realloc(head.base, sizeof(datatype) * (head.capacity + STACK_INCREMENT));if (tmp == NULL) return;head.base = tmp;//扩容后恢复原来指针指向，更新容量head.top = head.base + head.capacity;head.capacity += STACK_INCREMENT;}*head.top++ = x;
}
void PopTop(ST& head)
{if (EmptyStack(head)) return;head.top--;
}
datatype GetTop(ST& head)
{if (!EmptyStack(head))return *(head.top - 1);
}
int SizeStack(ST& head)
{if(!OverflowStack(head))return head.top - head.base;
}int main()
{ST head;InitStack(head);Push(head, 1);Push(head, 2);Push(head, 3);Push(head, 4);while (!EmptyStack(head)){cout << "输出当前栈顶元素：" << GetTop(head) << endl;PopTop(head);cout << "栈里剩余元素个数：" << SizeStack(head) << endl << endl;}DestroyStack(head);return 0;
}

代码实现2.0：（优化 且 纯C版本）

1. 优化：动态2倍扩容
2. 与1.0版本对栈的实现区别：这里的top也是指向栈顶元素下一个位置，其类型为整形（即下标）

stack.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}ST;
void STInite(ST *ps);
void STDestroy(ST* ps);void STPush(ST* ps, STDataType x);
void STPop(ST* ps);
int STSize(ST* ps);
bool STEmpty(ST* ps);
STDataType STTop(ST* ps);

stack.c

#include"stack.h"
void STInite(ST* ps)
{assert(ps);ps->a = (STDataType*)malloc(sizeof(STDataType) * 3);if (ps->a==NULL){perror("malloc fail");return;}ps->capacity = 3;ps->top = 0;//栈顶为top前一个元素//ps->top = -1;//栈顶为top元素
}
void STDestroy(ST* ps)
{assert(ps);free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->capacity == ps->top){STDataType *tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * ps->capacity*2);if (tmp == NULL){perror("realloc fail");return;}ps->a = tmp;ps->capacity =ps->capacity * 2;}ps->a[ps->top++] = x;//ps->top++;
}
void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps->top--;
}
int STSize(ST* ps)
{assert(ps);return ps->top;
}
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}
STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps->a[ps->top - 1];
}

text.c

#include"stack.h"
int main()
{ST st;STInite(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);while (!STEmpty(&st)){printf("输出当前栈顶元素：%d\n", STTop(&st));STPop(&st);printf("栈里剩余元素个数：%d\n\n", STSize(&st));}STDestroy(&st);return 0;
}

实现十进制数与其它进制数的转换

代码实现：

void conversion()
{int num, x;cout << "请输入要转化的十进制数字：" << endl;cin >> num;cout << "期望将它转化为几进制数" << endl;cin >> x;cout << "将十进制数 " << num  << " " << "转化为 " << x << " " << "进制数得到的结果为：" << endl;ST st;InitStack(st);while (num > 0){Push(st, num % x);num /= x;}while (!EmptyStack(st)){cout << GetTop(st);PopTop(st);}DestroyStack(st);
}

测试结果：

传送们：实验三