数据结构（C语言版）实验

介绍

数据结构（C语言版）实验，由河南理工大学信息管理与信息系统1803版第四组制作。

制作本次内容是为了完善实验报告册，代码全部C++.

人员架构

实验详细内容

1. 顺序表的基本操作
2. 一元多项式的相加与相乘
3. 链栈与循环队列的练习
4. 字符串块链的实现
5. 二叉树的基本算法实现
6. 图的基本算法实现
7. 二叉排序树的基本算法实现
8. 排序方法的算法实现

实验目的和要求

1. 顺序表的基本操作

Status InitList(SqList &L)
Status Listinsert(SqList &L,  int i,  int e )
Status ListIndele(SqList &L,  int i,  int &e )
Status ListInprint(SqList L)
void MergeList(SqList La, SqList Lb, SqList &Lc)
void Inverse(SqList &Lc)

​ 完成以上几个函数，实现手工创建两个非递减序列存放于La和 Lb中，并调用MergeList实现数据的合并。合并之后用Inverse把Lc中的数据就地逆置（不占用太多额外辅助空间，空间复杂度为常数级别）。

关于程序健壮性的内容：

​ 1、对于插入与删除位置若不合法请给出适当提醒 ​ 2、若输入的数据不是非递减排列可通过自己写的sort()函数排序后再进行后续操作

2. 一元多项式的相加与相乘

实验目的：

​ 根据所给的一元多项式相加的程序，写出一元多项式相乘的程序并调试通过。

实验要求：

​ 1、写出一元多项式的横向输出方式，当系数为零时，要求重新输入数据。

​ 2、把加法改写成Lc=La+Lb,方便进行 Lc=La*Lb

3. 链栈与循环队列的练习

实验要求：

​ 1、用堆栈（链栈）实现括号匹配算法，其中要求对所给出字符串中的｛｝、【】、（）均可检测是否匹配。

​ 2、借助循环队列实现将堆栈中的给定值删除。

4. 字符串块链的实现

实现以下函数：

//将一个不包含’#’字符串str赋值到块链类型变量T中 
void strassign(Lstring &T,char *str)
//将一个块链T中的所有结点释放，最终使得T.head=T.tail=null     T.curlen=0 
void clrstring(Lstring &T)
//打印一个存放在块链T中的字符串
void strprint(Lstring T)
//将块链S插入到块链T中第pos个字符之前
void strinsert(Lstring &T,int pos,Lstring S)
//将块链T中间的’#’去掉，重新放入块链T中   
void zip(Lstring &T)

实例主程序：

int main( )
{
   char s[100]; lstring T1,T2;
   printf(“\n请输入第一个长度不超过100个字符的字  符串(不包含字符\'#\')：");
   gets(s);
   strassign(T1,s); 
   strprint(T1);
   printf("\n请输入第二个长度不超过100个字符的字符串(不包含字符\'#\')：");
   gets(s);
   strassign(T2,s); 
   strprint(T2);
   strinsert(T1,5,T2); zip(T1)；
   strprint(T1);getchar();
   return 0;
}

5. 二叉树的基本算法实现

实验目的：

​ 用二叉链表存储方式存储二叉树，并实现以下相关算法：

​ 1、创建二叉树

​ 2、用非递归算法先中后序遍历二叉树

​ 3、分别求出二叉树中度为0、1、2的结点个数

​ 4、求出树的高度

6. 图的基本算法实现

实验目的：

​ 用邻接表存储方式存储有向图，并实现以下相关算法：

​ 1、创建有向图的邻接表

​ 2、分别用深度优先和广度优先遍历有向图

​ 3、对创建的有向图进行拓扑排序

7. 二叉排序树的基本算法实现

实验目的：

​ 用二叉链表存储方式存储二叉排序树，并实现以下相关算法：

​ 1、创建二叉排序树

​ 2、在二叉排序树上实现查询、插入和删除算法

​ 3、对二叉排序树进行中序遍历以判断目标2是否完成

8. 排序方法的算法实现

实验目的：

​ 用顺序表存储方式存储实验数据，并实现以下相关算法：

​ 1、希尔排序

​ 2、快速排序

​ 3、堆排序

参考资料