实验⼀线性表1 实验⽬的
通过选择下⾯四个题⽬之⼀进⾏实现，掌握如下内容：熟悉C++语⾔的基本编程⽅法，掌握集成编译环境的调试⽅法学习指针、模板类、异常处理的使⽤掌握线性表的操作的实现⽅法学习使⽤线性表解决实际问题的能⼒2 实验内容2.1题⽬1
根据线性表的抽象数据类型的定义，选择下⾯任⼀种链式结构实现线性表，并完成线性表的基本功能。线性表存储结构（五选⼀）：1、带头结点的单链表2、不带头结点的单链表3、循环链表4、双链表5、静态链表线性表的基本功能：
1、构造：使⽤头插法、尾插法两种⽅法
2、插⼊：要求建⽴的链表按照关键字从⼩到⼤有序3、删除4、查找
5、获取链表长度6、销毁
7、其他：可⾃⾏定义
编写测试main()函数测试线性表的正确性。2.2题⽬2
利⽤线性表实现⼀个通讯录管理，通信录的数据格式如下：struct DataType{
int ID; //编号char name[10]; //姓名char ch; //性别char phone[13]; //电话char addr[31]; //地址
};要求：
实现通讯录的建⽴、增加、删除、修改、查询等功能
能够实现简单的菜单交互，即可以根据⽤户输⼊的命令，选择不同的操作。能够保存每次更新的数据（选作）
能够进⾏通讯录分类，⽐如班级类、好友类、⿊名单等等（选作）编写测试main()函数测试线性表的正确性2.3题⽬3
利⽤线性表实现⼀个⼀元多项式Polynomialf(x) = a
+ a1x + a2x2 + a3x3+ … + a n x n提⽰：
Polynomial的结点结构如下：struct term{
float coef; //系数int expn; //指数};
可以使⽤链表实现，也可以使⽤顺序表实现。要求：
能够实现⼀元多项式的输⼊和输出能够进⾏⼀元多项式相加能够进⾏⼀元多项式相减能够计算⼀元多项式在x处的值能够计算⼀元多项式的导数（选作）能够进⾏⼀元多项式相乘（选作）编写测试main()函数测试线性表的正确性2.4题⽬4
利⽤循环链表实现约瑟夫问题的求解。
约瑟夫问题如下：已知n个⼈（n>=1）围坐⼀圆桌周围，从1开始顺序编号。从序号为1的⼈开始报数，顺时针数到m的那个⼈出列；他的下⼀个⼈⼜从1开始报数，数到m的那个⼈⼜出列；依此规则重复下去，直到所有⼈全部出列。请问最后⼀个出列的⼈的编号。3代码要求
1、必须要有异常处理，⽐如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空⾏和缩近
标识符名称应该与其代表的意义⼀致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能实验⼆栈和队列1 实验⽬的
通过选择下⾯五个题⽬之⼀进⾏实现，掌握如下内容：进⼀步掌握指针、模板类、异常处理的使⽤掌握栈的操作的实现⽅法掌握队列的操作的实现⽅法学习使⽤栈解决实际问题的能⼒学习使⽤队列解决实际问题的能⼒2 实验内容2.1题⽬1
根据栈和队列的抽象数据类型的定义，按要求实现⼀个栈或⼀个队列。要求：
1、实现⼀个共享栈2、实现⼀个链栈3、实现⼀个循环队列4、实现⼀个链队列
编写测试main()函数测试线性表的正确性。2.2题⽬2
利⽤栈结构实现⼋皇后问题。
⼋皇后问题19世纪著名的数学家⾼斯于1850年提出的。他的问题是：在8*8的棋盘上放置8个皇后，使其不能互相攻击，即任意两个皇后都不能处于同⼀⾏、同⼀列、同⼀斜线上。请设计算法打印所有可能的摆放⽅法。提⽰：
1、可以使⽤递归或⾮递归两种⽅法实现
2、实现⼀个关键算法：判断任意两个皇后是否在同⼀⾏、同⼀列和同⼀斜线上2.3题⽬3
利⽤栈结构实现迷宫求解问题。迷宫求解问题如下：
⼼理学家把⼀只⽼⿏从⼀个⽆顶盖的⼤盒⼦的⼊⼝赶进迷宫，迷宫中设置很多隔壁，对前进⽅向形成了多处障碍，⼼理学家在迷宫的唯⼀出⼝放置了⼀块奶酪，吸引⽼⿏在迷宫中寻找通路以到达出⼝，测试算法的迷宫如下图所⽰。提⽰：
1、可以使⽤递归或⾮递归两种⽅法实现
2、⽼⿏能够记住已经⾛过的路，不会反复⾛重复的路径3、可以⾃⼰任意设置迷宫的⼤⼩和障碍
4、使⽤“穷举求解”的⽅法
2.4题⽬4
设计⼀个算术四则运算表达式求值的简单计算器。表达式求值是程序设计语⾔编译中最近本的问题，它要求把⼀个表达式翻译成能够直接求值的序列。基本要求：
1、输⼊中缀表达式能够转化成后缀表达式，⽐如输⼊中缀表达式“(A+B)*C”，输出“AB+C*”
2、操作数使⽤单字母变量A、B、C等表⽰，操作符仅为+、-、*、/、（和）；3、能够对变量A、B、C等赋值，得出正确的计算结果2.5题⽬5
利⽤队列结构实现车厢重排问题。车厢重排问题如下：
⼀列货车共有n节车厢，每个车厢都有⾃⼰的编号，编号范围从1~n。给定任意次序的车厢，通过转轨站将车厢编号按顺序重新排成1~n。转轨站共有k个缓冲轨，缓冲轨位于⼊轨和出轨之间。开始时，车厢从⼊轨进⼊缓冲轨，经过缓冲轨的重排后，按1~n的顺序进⼊出轨。缓冲轨按照先进先出⽅式，编写⼀个算法，将任意次序的车厢进⾏重排，输出每个缓冲轨中的车厢编号。提⽰：
1、⼀列⽕车的每个车厢按顺序从⼊轨进⼊不同缓冲轨，缓冲轨重排后的进⼊出轨，重新编排成⼀列货车。⽐如：编号为3的车厢进⼊缓冲轨1，则下⼀个编号⼩于3的车厢则必须进⼊下⼀个缓冲轨2，⽽编号⼤于3的车厢则进⼊缓冲轨1，排在3号车厢的后⾯，这样，出轨的时候才可以按照从⼩到⼤的顺序重新编排。3代码要求
1、必须要有异常处理，⽐如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空⾏和缩近标识符名称应该与其代表的意义⼀致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能
3、递归程序注意调⽤的过程，防⽌栈溢出实验三树1 实验⽬的
通过选择下⾯两个题⽬之⼀进⾏实现，掌握如下内容：掌握⼆叉树基本操作的实现⽅法了解赫夫曼树的思想和相关概念学习使⽤⼆叉树解决实际问题的能⼒2 实验内容2.1 题⽬1
根据⼆叉树的抽象数据类型的定义，使⽤⼆叉链表实现⼀个⼆叉树。⼆叉树的基本功能：1、⼆叉树的建⽴2、前序遍历⼆叉树3、中序遍历⼆叉树4、后序遍历⼆叉树5、按层序遍历⼆叉树6、求⼆叉树的深度7、求指定结点到根的路径8、⼆叉树的销毁9、其他：⾃定义操作
编写测试main()函数测试线性表的正确性2.2题⽬2
利⽤⼆叉树结构实现赫夫曼编/解码器。基本要求：
1、初始化(Init)：能够对输⼊的任意长度的字符串s进⾏统计，统计每个字符的频度，并建⽴赫夫曼树
2、建⽴编码表(CreateTable)：利⽤已经建好的赫夫曼树进⾏编码，并将每个字符的编码输出。
3、编码(Encoding)：根据编码表对输⼊的字符串进⾏编码，并将编码后的字符串输出。
4、译码(Decoding)：利⽤已经建好的赫夫曼树对编码后的字符串进⾏译码，并输出译码结果。
5、打印(Print)：以直观的⽅式打印赫夫曼树（选作）
6、计算输⼊的字符串编码前和编码后的长度，并进⾏分析，讨论赫夫曼编码的压缩效果。
测试数据：
I love data Structure, I love Computer。I will try my best to study data Structure.提⽰：
1、⽤户界⾯可以设计为“菜单”⽅式：能够进⾏交互。
2、根据输⼊的字符串中每个字符出现的次数统计频度，对没有出现的字符⼀律不⽤编码。3代码要求
1、必须要有异常处理，⽐如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空⾏和缩近标识符名称应该与其代表的意义⼀致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能
3、递归程序注意调⽤的过程，防⽌栈溢出实验四排序1 实验⽬的
通过选择下⾯两个题⽬之⼀，学习、实现、对⽐各种排序算法，掌握各种排序算法的优劣，以及各种算法使⽤的情况。2 实验内容2.1 题⽬1
使⽤简单数组实现下⾯各种排序算法，并进⾏⽐较。排序算法：1、插⼊排序2、希尔排序3、冒泡排序4、快速排序5、简单选择排序6、堆排序（选作）7、归并排序（选作）8、基数排序（选作）9、其他要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，⽐较上述排序算法中关键字的⽐较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，⽐较上述排序算法中不同算法的执⾏时间，精
确到微秒（选作）
4、对2和3的结果进⾏分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性。2.2 题⽬2
使⽤链表实现下⾯各种排序算法，并进⾏⽐较。排序算法：1、插⼊排序2、冒泡排序3、快速排序4、简单选择排序5、其他要求：
1、测试数据分成三类：正序、逆序、随机数据
2、对于这三类数据，⽐较上述排序算法中关键字的⽐较次数和移动次数（其中关键字交换计为3次移动）。
3、对于这三类数据，⽐较上述排序算法中不同算法的执⾏时间，精确到微秒（选作）
4、对2和3的结果进⾏分析，验证上述各种算法的时间复杂度编写测试main()函数测试线性表的正确性3代码要求
1、必须要有异常处理，⽐如删除空链表时需要抛出异常；2、保持良好的编程的风格：代码段与段之间要有空⾏和缩近标识符名称应该与其代表的意义⼀致函数名之前应该添加注释说明该函数的功能关键代码应说明其功能
3、递归程序注意调⽤的过程，防⽌栈溢出
因篇幅问题不能全部显示，请点此查看更多更全内容