山东大学软件学院2017-18学年大二数据结构实验一、二、三、四
注：实验代码均为自己编写，均能满足实验要求，但实现方法不唯一仅供参考。
实验一 递归练习
1.实验内容（题目内容，输入要求，输出要求）
①、输入2-10个大于0的正整数，如果输入0作为结束。
②、输出这几个整数的全排列，每个数之间用半角“，”隔开，中间不要有空格，每个排列单独一行。
③、程序一定要有Input、Output、End提示信息，但是不要有格式没有出现的其他提示
④、程序最后增加system(pause)，显示Press any key to continue并暂停。
2.实现源代码
#include <iostream>
using namespace std;
void swap(int &m, int &n) { //交换两个元素
int temp = m;
m = n;
n = temp;
}
void fullPerm(int Array[], int i, int j) { //全排列递归方法
if (i == j) {
for (int k = 0; k <= j; k++) { //当排到最后输出一种排列方式
cout << Array[k];
if (k<j) {
cout << ",";
}
else
{
cout << endl;
}
}
}
else
{
for (int k = i; k <= j; k++) //以第一个输入的数据为开头
{
swap(Array[i], Array[k]); //交换后面两位相邻元素
fullPerm(Array, i + 1, j); //用递归产生多种排列方法
swap(Array[i], Array[k]); //交换为首的元素
}
}
}
int main()
{
cout << "Input" << endl;
int array[11];
int n, m;
for (int i = 0; i < 11; i++)
{
cin >> n;
array[i] = n;
if (n == 0) {
m = i - 1; //记录共输入了多少个数字
break;
}
}
cout << "Output" << endl;
fullPerm(array, 0, m);
cout << "End" << endl;
system("pause");
return 0;
}
实验二 排序练习
-
实验内容（题目内容，输入要求，输出要求）
- 输入2-10个不为零的正整数，遇到0代表输入结束，0不参与排序。
- 数字选择排序方法，1-冒泡排序、2-插入排序、3-基数排序
- 基数排序能够实现小于10的正整数的排序。
- 使用所选排序方法的排序，结果输出所用方法以及结果，每个数之间用“，”隔开，中间不要有空格。
- 输入输出请严格按下面要求的格式实现
2.数据结构与算法描述 （整体思路描述，所需要的数据结构与算法）
①、冒泡排序思路就是交换排序，通过相邻数据的交换来达到排序的目的。对数组中各数据依次比较相邻两个元素的大小，如果前面数据大于后面，就交换。在用同样的方法把剩下的数据逐个进行比较，最后便可按从小到大的顺序排好。
②、插入排序首先对数组的前两个数据进行从小到大排序，再将第三个数据与排好序的两个数据比较，将第三个数据插入合适位置，然后将第四个数据插入已排好的三个数中，以此类推。
③、基数排序先算最大位数，然后按位依次排序，先排个位再排十位以此类推。
3.实现源代码
#include <iostream>
using namespace std;
template<class T>
void bubblesort(T a[], int n)
{
//冒泡排序
for (int i = 1; i < n; i++) { //共进行n-1步排序
for (int j = 0; j < n - i; j++) { //把每次排列的大数排到第n-i的位置上
if (a[j] > a[j + 1]) //比较相邻两个数，大数排后面
swap(a[j], a[j + 1]);
}
}
output(a,n);
}
template<class T>
void insertsort(T a[], int n)
{
//插入排序
for (int i = 1; i < n;i++) {
T temp = a[i]; //从第二个数开始先赋值给temp
int j;
for (j = i - 1; j >= 0 && temp < a[j];j--) { //j为选的这个数的前一个数 如果这个数小于前一个数
a[j + 1] = a[j]; //那么这个数赋值为前一个数 不断向前比较插入
}
a[j + 1] = temp;
}
output(a,n);
}
template <class T>
int maxDigit(T a[], int n) //为基数排序求出最大位数
{
int maxdigit = 1; //求出并保存一个数中最大的位数是十位还是百位等等
int divisor = 10; //除数为10
for (int i = 0; i < n; i++) //对每个数据求最大位数
{
while (a[i] >= divisor)
{
divisor *= 10;
maxdigit++;
}
}
return maxdigit;
}
template<class T>
void radixsort(T a[], int n) {
//基数排序
int maxdigit = maxDigit(a, n);
int *temp = new T[n];
int *count = new int[10]; //用来计数
int i, j, k;
int radix = 1; //基数从个位开始
for (i = 0; i < maxdigit; i++) //进行辅助函数算出来的最大位数次排序
{
for (j = 0; j < 10; j++)
count[j] = 0; //每次排序前初始化count数组
for (j = 0; j < n; j++)
{
k = (a[j] / radix) % 10; //统计每个桶中的数字个数 比如位数是9的有count[9]个
count[k]++;
}
for (j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将每个桶中的数字分配好在temp中的位置 位置为 count[j] 从1开始
for (j = n - 1; j >= 0; j--) //将每个桶中数字依次赋值到temp中
{
k = (a[j] / radix) % 10;
temp[count[k] - 1] = a[j];
count[k]--;
}
for (j = 0; j < n; j++) //将临时数组复制到传入的数组a[]中
a[j] = temp[j];
radix = radix * 10;
}
output(a, n);
}
template<class T>
void output(T a[],int n) {
//统一格式化输出结果
for (int i = 0; i <= n - 1; i++) {
cout << a[i];
if (i<n - 1)
{
cout << ",";
}
else
{
cout << endl;
}
}
}
void threePermutation(int array[],int n) { //对含有n个数据的数组array进行排序
int i;
cout << "1-冒泡排序,2-插入排序,3-基数排序" << endl;
cin >> i; //输入选项
cout << "Output" << endl;
switch (i)
{
case 1:
cout << "冒泡排序" << endl;
bubblesort(array, n);
cout << "End" << endl;
break;
case 2:
cout << "插入排序" << endl;
insertsort(array, n);
cout << "End" << endl;
break;
case 3:
cout << "基数排序" << endl;
radixsort(array, n);
cout << "End" << endl;
break;
default:
break;
}
}
int main() {
cout << "Input" << endl;
int array[11]; //创建一个可输入10个数的数组
int n, m; //n为当前输入的数据
for (int i = 0; i < 11; i++)
{
cin >> n;
array[i] = n;
if (n == 0) {
m = i; //m为了记住0前一共输入了几个数
break;
}
}
threePermutation(array, m);
system("pause");
return 0;
}
实验三 线性表操作
1.实验内容（题目内容，输入要求，输出要求）
- 创建线性表类。线性表的存储结构使用链表。
- 完成表首插入元素、删除指定元素、搜索表中是否有指定元素、输出链表。
- 输入n个不为零的整数作为节点元素值，遇到0代表输入结束（不创建元素值为0的节点），创建链表。输出整个链表。
- 输入一个整数，将该数作为一个元素值插入表首位置。输出整个链表。
- 输入一个整数，在链表中进行搜索，输出其在链表中的位置。如果不存在输出0。
- 再一次输入一个整数，在链表中进行搜索，输出其在链表中的位置。如果不存在输出0。
- 再一次输入n个不为零的整数作为节点元素值，遇到0代表输入结束（不创建元素值为0的节点），创建并输出整个链表。
- 实现上面两个链表的合并，第一个链表在前第二个在后，输出合并后的链表。
- 使用链表遍历器输出合并后的链表的反序输出。
2.实现源代码
#include<iostream>
using namespace std;
class chainNode //节点类
{
friend class chain; //友元类便于访问private的data与link
friend class chainIterator;
public:
chainNode() {};
chainNode(const int& data);
chainNode(const int& data, chainNode* link);
private:
int data;
chainNode *link;
};
chainNode::chainNode(const int& data) {
this->data = data;
}
chainNode::chainNode(const int& data, chainNode* link) {
this->data = data;
this->link = link;
}
class chain
{
friend class chainIterator; //友元类便于访问private的firstNode
public:
chain() { firstNode = 0; };
~chain();
chain &insertAtFirst(const int&x); //在链表表首插入元素x
chain &deleteNode(const int index); //删除指定位置的节点
int search(const int&x)const; //查找链表中指定元素x存在返回x不存在返回0
void push_back(const int&x); //在链表末尾添加元素x
bool ifexist(const int&x)const; //查找链表中指定元素x是否存在
private:
chainNode *firstNode;
};
chain::~chain()
{
while (firstNode != NULL)
{
chainNode* nextNode = firstNode->link;
delete firstNode;
firstNode = nextNode;
}
}
void chain::push_back(const int&x) {
chainNode * newNode = new chainNode(x, NULL);
if (firstNode == NULL) {
firstNode = newNode;
}
else
{
chainNode * lastNode = new chainNode(0, firstNode);
while (lastNode->link)
{
lastNode = lastNode->link;
}
lastNode->link = newNode;
}
}
chain&chain::insertAtFirst(const int&x) {
chainNode *element = new chainNode(x, firstNode);
firstNode = element;
return*this;
}
int chain::search(const int&x)const {
chainNode *current = firstNode;
int index = 0;
while (current)
{
index++;
if (current->data == x)
{
return index;
}
current = current->link;
}
return 0;
}
chain&chain::deleteNode(const int index) {
chainNode*checksize = firstNode;
int size = 0;
while (checksize)
{
size++;
}
delete checksize;
if (index<1 || index>size || size == 0) {
return*this;
}
else
{
chainNode*current = firstNode;
chainNode*before = firstNode;
for (int i = 0; i < index; i++)
{
current = current->link;
}
for (int j = 0; j < index - 1; j++)
{
before = before->link;
}
before->link = current->link;
}
return*this;
}
bool chain::ifexist(const int&x)const {
chainNode *ifexist = new chainNode();
ifexist = firstNode;
while (ifexist)
{
if (ifexist->data == x) {
return true;
}
ifexist = ifexist->link;
}
return false;
}
class chainIterator //遍历器 输出链表
{
private:
chainNode *current;
public:
void output(const chain &a) {
current = a.firstNode;
while (current)
{
cout << current->data;
if (current->link != NULL)
{
cout << ",";
}
current = current->link;
}
cout << endl;
}
void addtogether(const chain &a, const chain &b) {
current = a.firstNode;
while (current->link)
{
current = current->link;
}
current->link = b.firstNode;
current = a.firstNode;
while (current)
{
cout << current->data;
if (current->link != NULL)
{
cout << ",";
}
current = current->link;
}
cout << endl;
}
void reverse(const chain &a,chain &b) {
current = a.firstNode;
while (current)
{
b.insertAtFirst(current->data);
current = current->link;
}
current = b.firstNode;
while (current)
{
cout << current->data;
if (current->link != NULL)
{
cout << ",";
}
current = current->link;
}
cout << endl;
}
};
int main() {
chain * chain1 = new chain();
chain * chain2 = new chain();
int number = 0;
cout << "Input1" << endl;
cin >> number;
chain1->insertAtFirst(number);
while (1){
cin >> number;
if (number == 0) {
break;
}
chain1->push_back(number);
}
cout << "Output1" << endl;
chainIterator c;
c.output(*chain1);
cout << "Input2" << endl;
cin >> number;
chain1->insertAtFirst(number);
cout << "Output2" << endl;
c.output(*chain1);
cout << "Input3" << endl;
cin >> number;
int a = chain1->search(number);
cout << "Output3" << endl;
cout << a << endl;
cout << "Input4" << endl;
cin >> number;
a = chain1->search(number);
cout << "Output4" << endl;
cout << a << endl;
cout << "Input5" << endl;
cin >> number;
chain2->insertAtFirst(number);
while (1) {
cin >> number;
if (number == 0) {
break;
}
chain2->push_back(number);
}
cout << "Output5" << endl;
c.output(*chain2);
chainIterator c2;
c2.addtogether(*chain1, *chain2);
chain * chain3 = new chain();
c2.reverse(*chain1, *chain3);
cout << "End" << endl;
system("pause");
}
实验四 堆栈的应用
1.实验内容（题目内容，输入要求，输出要求）
- 1输入一个数学表达式（假定表达式输入格式合法），计算表达式结果并输出。
- 数学表达式由单个数字和运算符“+”、“-”、“*”、“/”、“(、) ”构成，例如 2 + 3 * ( 4 + 5 ) - 6 / 4。
- 变量、输出采用整数，只舍不入。
2.实验源代码
#include <iostream>
#include <string>
using namespace std;
template<class T>
class stack
{
public:
stack(int initialCapacity);
bool isEmpty()const; //判断堆栈是否空
bool isFull()const; //判断堆栈是否满
T top()const; //返回栈顶元素
void add(const T& x); //元素入栈
T deleteAtTop(); //栈顶元素出栈并且返回此元素
private:
int MaxTop; //堆栈最大栈顶值
int Top; //栈顶
T *stackArray; //数组实现堆栈
};
template <class T>
stack<T>::stack(int initialCapacity)
{
MaxTop = initialCapacity-1;
Top = -1;
stackArray = new T[initialCapacity];
}
template<class T>
bool stack<T>::isEmpty() const
{
return Top == -1;
}
template<class T>
bool stack<T>::isFull() const
{
return Top == MaxTop - 1;
}
template<class T>
T stack<T>::top() const
{
if (isEmpty()) throw OutOfBounds();
else return stackArray[Top];
}
template<class T>
void stack<T>::add(const T & x)
{
if (isFull()) throw Nomem();
stackArray[++Top] = x;
}
template<class T>
T stack<T>::deleteAtTop()
{
if (isEmpty()) throw OutOfBounds();
else return stackArray[Top--];
}
int lengthOfExpression(const char *expression) { //计算并返回表达式的长度
int count = 0;
for (int i = 0; expression[count]!=NULL ; i++)
{
count++;
}
return count;
}
char* changeIntoSuffixExpression(const char *infixExpression) { //将输入的中缀表达式转换成后缀表达式
char *suffixExpression = new char[lengthOfExpression(infixExpression)]; //后缀表达式数组 缺点只能按题意计算单个数字 对于>=10的数字无法计算
stack<char> * symbolStack = new stack<char>(lengthOfExpression(infixExpression)); //声明一个符号栈
int current = 0; //在后缀表达式中的位置
for (int i = 0; i < lengthOfExpression(infixExpression); i++) //对中缀表达式的每个元素遍历
{
switch (infixExpression[i])
{
case '+':
case '-': {
if (symbolStack->isEmpty() || symbolStack->top() == '(') //如果符号栈里空或者是左括号那么直接把加减号放入
{
symbolStack->add(infixExpression[i]);
}
else if (symbolStack->top() == '*' || symbolStack->top() == '/' || symbolStack->top() == '+' || symbolStack->top() == '-') //如果符号栈里还有其他符号
{
while (!symbolStack->isEmpty()) //只要符号栈不空就把左括号之上的符号全部拿出来 因为这些符号都<= 加减号的优先级
{
if (symbolStack->top() == '(') //遇到左括号就跳出循环
break;
suffixExpression[current++] = symbolStack->deleteAtTop(); //拿出符号放入表达式
}
symbolStack->add(infixExpression[i]); //最后把减号放入符号栈
}
break;
};
case '*':
case '/': {
if (symbolStack->isEmpty() || symbolStack->top() == '('||symbolStack->top() == '+' || symbolStack->top() == '-') //如果符号栈里空或者是左括号 或者是比乘除优先级小的加减号那么直接把加减号放入
{
symbolStack->add(infixExpression[i]);
}
else if (symbolStack->top() == '*' || symbolStack->top() == '/') //如果符号栈里还有与乘除本身相同运算优先级的符号 即乘除本身
{
while (!symbolStack->isEmpty()) //只要符号栈不空就把左括号之上的符号全部拿出来
{
if (symbolStack->top() == '(' || symbolStack->top() == '+' || symbolStack->top() == '-') //如果遇到左括号或者比乘除优先级小的+-就跳出循环直接放入除号
break;
suffixExpression[current++] = symbolStack->deleteAtTop(); //拿出符号放入表达式
}
symbolStack->add(infixExpression[i]); //最后把除号放入符号栈
}
break;
};
case '(': {
symbolStack->add(infixExpression[i]); //如果是左括号直接加入符号栈
break;
};
case ')': {
while (!symbolStack->isEmpty()) //如果此时遍历前缀表达式时遇到右括号，并且符号栈不为空就把遇到左括号之前所有符号依次出栈并加入后缀表达式
{
if (symbolStack->top() == '(') //遇到左括号就跳出循环
break;
suffixExpression[current++] = symbolStack->deleteAtTop();
}
symbolStack->deleteAtTop(); //左括号只出栈不加入后缀表达式
break;
};
default: {
suffixExpression[current++] = infixExpression[i]; //如果是数字直接进入后缀表达式
break;
};
}
}
while (!symbolStack->isEmpty()) //遍历结束后如果符号栈里还有剩余符号全部出栈加入后缀表达式
{
suffixExpression[current++] = symbolStack->deleteAtTop();
}
suffixExpression[current] = NULL; //由于为current++当处理完所有位置后最后current必须赋上空值不然会出现指针乱指 每次式子相同但是求出结果不一样的情况
return suffixExpression;
}
int result(char *suffixExpression) { //把后缀表达式从左到右依次取出如果是数据就入栈，是符号就取出栈顶两个数据计算
stack<char> * result = new stack<char>(lengthOfExpression(suffixExpression));
for (int i = 0; i < lengthOfExpression(suffixExpression); i++)
{
switch (suffixExpression[i])
{
case'+': {
int a, b; char c;
a = result->deleteAtTop() - '0';
b = result->deleteAtTop() - '0';
c = a + b + '0';
result->add(c);
break;
}
case'-': {
int a, b; char c;
a = result->deleteAtTop() - '0';
b = result->deleteAtTop() - '0';
c = b-a+'0';
result->add(c);
break;
}
case'*': {
int a, b; char c;
a = result->deleteAtTop() - '0';
b = result->deleteAtTop() - '0';
c = a * b + '0';
result->add(c);
break;
}
case'/': {
int a, b; char c;
a = result->deleteAtTop() - '0';
b = result->deleteAtTop() - '0';
c = b/a + '0';
result->add(c);
break;
}
default:
result->add(suffixExpression[i]);
break;
}
}
return(result->top() - '0');
}
class OutOfBounds :public exception {
public: OutOfBounds() :exception("ERROR! OutOfBounds\n") {}
};
class Nomem :public exception {
public: Nomem() :exception("ERROR! Nomem\n") {}
};
int main() {
cout << "Input" << endl;
string s;
cin >> s;
const char*a = s.c_str();
cout << "Output" << endl;
char * b = changeIntoSuffixExpression(a);
int Result = result(b);
cout << Result << endl;
cout << "End" << endl;
system("pause");
}