数据结构的几种基础实现

数据结构是计算机专业的一门重要的基础课，它的教学要求大致有三个重要方面：第一就是让学生学会分析研究计算机加工的数据对象的特性，确定数据的逻辑结构和适当的物理结构；第二，根据结构，设计适当的算法，并初步掌握算法的时间分析和空间分析；第三，学习复杂的程序设计。

以下内容包括三部分：
1、有序表的建立、插入与删除
2、中序线索二叉树
3、快速排序

一、有序表的建立、插入与删除

一、实验目的

1 了解有序表的顺序存储结构。
2 掌握有序表元素在内存中是怎样存储的。
3 在有序表中实现如下操作：
（1)插入一个新元素到第i个位置，使原来标号为增1；
（2)删除第i个位置的元素；
（3)存一个新元素到第i个位置；
（4)读表；
（5)检索表中第i个元素；
（6)寻表的长度。

二、实验原理

线性表是最常用的而且也是最简单的一种数据结构，线性表是N个数据元素的有限序列。例如26个英文元素的字母表：（A，B，C，D…）。其数据结构的描述为：Linear_list=(D,R)其中：D={ai|ai属于D0,i=1,2,3,···}R={N},N={<ai-1,ai>|i=2,3,4,···}。本实验是以数组的形式把有序表存放在计算机内存的一个连续的区域内，这样便有：LOC(ai+1)=LOC(ai)+m。其中m是存放每个元素所占的内存字数。LOC(ai)=LO+m·(i-1)。其中LO是ai的地址，即首地址。
实验程序说明：
插入一个新元素到第i个位置，既把元素ai向后移一个位置，成为元素ai+1，把新元素放入到第i个位置，其他元素依次后移。
存一新元素到第i个位置是把元素ai冲掉后存上新值。
删除第i个元素就是把余后的元素依次向前移一个位置。即：以元素ai+1，ai+2，……，依次取代ai，ai+1……。删除后的表长是n-1（n是原表长）。

三、程序流程图

四、程序示例

#include<stdio.h>
#include<stdlib.h>
#define maxn 100int a[maxn];
int array_Length; //用户所定义的线性表长度
int op; //定义操作数
int p; //操作位置
bool is_OK=false;
bool is_Flag=true; //主循环结束标志void show_Welcome(); //欢迎语句
void init_Array(); //初始化线性表
void show_Menu(); //功能菜单
void insert(); //线性表插入操作
void _delete(); //线性表删除操作
void get_NewNumber(); //线性表读新值操作
void show(); //打印表中元素
void search(); //检索表中元素
void get_ListLength(); //获取表长
void pause(); //用于程序暂停，便于查看输出结果
bool is_Check(int length); //检查是否超出表长int main()
{show_Welcome();init_Array();while(is_Flag){show_Menu();scanf("%d",&op);switch (op) {case 1: insert(); break;case 2: _delete(); break;case 3: get_NewNumber(); break;case 4: show(); break;case 5: search(); break;case 6: get_ListLength(); break;case 0: is_Flag=false; break;}}return 0;
}void show_Welcome()
{printf("-------欢迎使用本程序-------\n");
}void init_Array()
{printf("请输入您所要线性表的长度:\n");scanf("%d",&array_Length);printf("请依次输入线性表的元素:\n");for(int i=1;i<=array_Length;i++){scanf("%d",&a[i]);}printf("-------顺序表初始化完成-------\n");
}void show_Menu()
{printf("以下是菜单内容:\n");printf("插入操作----------按键1\n");printf("删除操作----------按键2\n");printf("读新值操作--------按键3\n");printf("打印表中所有元素---按键4\n");printf("按序列号查找表中元素-按键5\n");printf("显示表长----------按键6\n");printf("退出-------------按键0\n");printf("请输入您要进行的操作按键:\n");
}void insert()
{int number;while(1){printf("请输入您要插入的位置\n");scanf("%d",&p);is_OK=is_Check(p);if(is_OK)break;}printf("请输入要插入的元素:\n");scanf("%d",&number);for(int i=array_Length;i>=p;i--){a[i+1]=a[i];}a[p]=number;array_Length++;printf("-------插入成功!-------\n");pause();
}bool is_Check(int length)
{if(length>array_Length || length<0){printf("-------您所输入的位置不合法，请重新输入-------\n");return false;}else{return true;}
}void _delete()
{while(1){printf("请输入您要删除的位置\n");scanf("%d",&p);is_OK=is_Check(p);if(is_OK)break;}for(int i=p;i<p;i++){a[i]=a[i+1];}array_Length--;printf("-------删除成功!-------\n");pause();
}void get_NewNumber()
{int number;while(1){printf("请输入新元素的位置\n");scanf("%d",&p);is_OK=is_Check(p);if(is_OK)break;}printf("请输入新的元素:\n");scanf("%d",&number);a[p]=number;printf("-------覆盖成功!-------\n");pause();
}void show()
{printf("表中元素为:");for(int i=1;i<=array_Length;i++){printf("%4d",a[i]);}printf("\n");pause();
}void search()
{while(1){printf("请输入您要检索的位置\n");scanf("%d",&p);is_OK=is_Check(p);if(is_OK)break;}printf("第%d个元素为: %d\n",p,a[p]);pause();
}void get_ListLength()
{printf("线性表的表长为：%d\n",array_Length);pause();
}void pause()
{printf("-------请按回车键继续-------\n");getchar();getchar();
}

二、中序线索二叉树

一、 实验目的：

1. 理解线索的含义，掌握线索二叉树的算法。
2. 了解中序线索及其遍历的实现过程。

二、实验内容：

通过学习同学知道，遍历二叉树是以一定的规则，将二叉树中的结点排列成一个线性序列，得到二叉树的先序序列、中序序列、或者后序序列。这实质是将一个非线性结构进行线性化操作。但是，当以二叉链表作为存储结构时，只能找到左右孩子的信息，而不能找到任意的结点的前驱信息和后继信息。这种信息只能在遍历的动态过程之中才能得到。

试做如下的结点结构：

LCHILD	LTAG	DATA	RTAG	RCHILD

其中：

         Link  lchild  域指向结点的左孩子LTAG=Thread lchild  域指向结点的线性前驱结点Link  rchild  域指向结点的右孩子RTAG=Thread rchild  域指向结点的线性后继结点

以这种结点结构构成的二叉链表作为二叉树的存储结构，叫做线性链表。其中指向结点前驱和后继的指针，叫做线索。加上线索的二叉树叫做线索二叉树。对二叉树进行某种操作使其变为线索二叉树的过程叫做线索化。
在线索二叉树上进行遍历，只要先找到序列的第一个结点，然后依次找结点的后继直到结点的后继为空时为止。

三、程序流程图

四、程序示例

#include<iostream>
using namespace std;
enum TBT{child=0,thread};  //线索二叉树结点的指针是指向孩子还是前驱后继
typedef struct tbt
{struct tbt* lchild;enum TBT ltag;char data;enum TBT rtag;struct tbt* rchild;
}TBTreeNode,*pTBTree;int createThreadedBinaryTree(pTBTree& root);void inorderThreadingBinaryTree(const pTBTree& root);  //中序线索化二叉树
//在中序遍历的同时就线索化二叉树void inorderThreadedBinaryTreeTraversal(pTBTree root); //中序线索化二叉树遍历int main()
{TBTreeNode* root = nullptr;int ret = createThreadedBinaryTree(root);{if(0==ret){inorderThreadingBinaryTree(root);cout<<endl;inorderThreadedBinaryTreeTraversal(root);cout<<endl;}}system("pause");
}int createThreadedBinaryTree(pTBTree& root)
{char data;if(cin>>data){if('#'==data){root = nullptr;return -1;}else{ //用data数据来初始化root结点，然后递归建立左子树和右子树root = new TBTreeNode();  //创建结点的时候就把结点全部赋值为空root->data = data;createThreadedBinaryTree(root->lchild);createThreadedBinaryTree(root->rchild);}}return 0;
}static TBTreeNode* pre = nullptr;  //定义一个指针指向中序遍历当前访问结点的前一个访问结点
//线索化结点的后继要用到,因为中序遍历顺序：左子树,根结点，右子树
//前驱可以用刚刚访问过的结点直接赋值，后继还没有访问，这时候当前结点就是上一个访问结点pre的后继
//当然，前提条件是pre的右子树为空
//pre初始值为nullptr,因为从根结点开始访问，前一个访问结点就只能是空了
void inorderThreadingBinaryTree(const pTBTree& root)
{if(nullptr==root)return ;/*  参考中序遍历inorderTraversal(root->lchild);cout<<root->data<<" ";inorderTraversal(root->rchild);*/inorderThreadingBinaryTree(root->lchild);  //中序遍历左子树//判断结点指针域可不可以线索化if(nullptr==root->lchild)  //如果左子树为空，就可以把指针域拿来线索化，指向前驱{root->lchild = pre;root->ltag = thread;}if(nullptr!=pre&&nullptr==pre->rchild)  //如果当前访问的根结点不为空，并且前面访问的结点pre右子树为空，线索化前一个结点的后继{pre->rchild = root;pre->rtag = thread;}//访问根结点就变成修改前一个访问结点指针prepre = root;  //之后要访问右子树，当前结点自然就是preinorderThreadingBinaryTree(root->rchild);  //中序遍历右子树
}void inorderThreadedBinaryTreeTraversal(pTBTree root)
{if(nullptr==root)return;while(nullptr!=root){while(nullptr!=root->lchild&&child==root->ltag)  //两个条件，区别中序遍历第一个结点的前驱是nullptr{//搜寻从根结点开始的左子树的最后一个节点root = root->lchild;}cout<<root->data<<" ";  //输出根结点while(thread==root->rtag)  //该结点有后继,意味着没有右子树{cout<<root->rchild->data<<" ";  //直接输出后继，也就是中序遍历当前结点下一个要访问的结点的值root = root->rchild;  //根结点回溯到后继}//该结点有右子树，root->rtag==child,左子树已经遍历完了，这里进入右子树root = root->rchild;  //重复上面的操作}
}

三、快速排序

一、实验目的

掌握快速排序的算法。

二、实验内容

排序是计算机领域的一项重要技术，是程序设计中的一种重要运算。它的功能是将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。学习和研究各种排序方法，是计算机工作者的一项重要工作课题。

冒泡排序想来大家都很熟悉，它是一种想法很自然的排序方法。快速排序是对冒泡排序的一种改进。它的基本思想是，通过一趟排序将待排记录分割成独立的两个部分。其中，一部分记录的关键字均比另一部分小，则可分别对两个部分的记录进行排序，以达到整个序列的有序。

基本实现：
假设待排的序列为{R[S], R[S+1], R[S+2],……， R[T]},
首先任意选取一个记录，R[S]作为枢轴，然后重新排列其它记录。将所有关键字比它小的记录都放在它的前面，其它所有关键字比它大的记录放在它的后面。由此可以将记录以“枢轴”为界，将记录分为两个子序列，这个过程称为一趟快速排序。以后再分别对两个子序列进行快速排序，重复进行这个过程，直到整个序列全部有序为止。
快速排序的平均时间为 Tavg(n)=kn ln n，其中n为待排记录的个数。K为某个常数，经验证明在所有的同数量级的先进排序方法之中，快排的k最小。因此，就平均时间而言，快排是被认为最好的内部排序方法。

三、实验步骤

1 读懂理解〈数据结构〉教材中的冒泡排序的算法。
2 基于冒泡排序，读懂理解快速排序的算法。
3 编写快速排序的程序，上机调试。
4 进行排序分析。

四、流程图

五、程序示例

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;void quicksort(vector<int> &nums, int low, int high){if(low<high){int i = low, j = high, temp = nums[low];while(i<j){while(i<j&&nums[j]>=temp) j--;//先 从右向左找第一个小于temp的数，因为在j--的过程中会出现j<i的情况所以while语句中必须包含i<jif(i<j) nums[i++] = nums[j];while(i<j && nums[i]<= temp) i++;// 后从左向右找第一个大于等于temp的数if(i<j) nums[j--] = nums[i];}nums[i] = temp;quicksort(nums, low, i-1);quicksort(nums, i+1, high);}
}int main()
{int n;while(cin>>n){vector<int>nums(n);for(int i =0;i<n;++i){cin>>nums[i];}quicksort(nums, 0, n-1);for(int i =0;i<n;++i){cout<<nums[i]<<" ";}}return 0;
}