湖南大学CG题库（数据结构与算法）题解
前言：湖南大学2022数据结构与算法课程答案目录：实验一：预测线性表的实现1、基于链表的线性表实现（题解）题目描述：题解：反思：实验一：预测线性表的实现1、基于链表的线性表实现（题解）题目描述：题解：#include<bits/stdc++.h>usingnamespacestd;//断言工具函数：如果val为假则输出s然后中断程序voidAssert(boolval,strings)
·
前言：湖南大学2022数据结构与算法课程答案
实验一：预测线性表的实现
1、基于链表的线性表实现（题解）
题目描述：
题解：
#include<bits/stdc++.h>
using namespace std;
//断言工具函数：如果val为假则输出s然后中断程序
void Assert(bool val,string s){
if(!val){
cout<<"断言失败："<<s<<endl;
}
}
template <typename E> class List { // List ADT
private:
void operator =(const List&) {} // Protect assignment
List(const List&) {} // Protect copy constructor
public:
List() {} // Default constructor
virtual ~List() {} // Base destructor
// Clear contents from the list, to make it empty.
virtual void clear() = 0;
// Insert an element at the current location.
// item: The element to be inserted
virtual void insert(const E& item) = 0;
// Append an element at the end of the list.
// item: The element to be appended.
virtual void append(const E& item) = 0;
// Remove and return the current element.
// Return: the element that was removed.
virtual E remove() = 0;
// Set the current position to the start of the list
virtual void moveToStart() = 0;
// Set the current position to the end of the list
virtual void moveToEnd() = 0;
// Move the current position one step left. No change
// if already at beginning.
virtual void prev() = 0;
// Move the current position one step right. No change
// if already at end.
virtual void next() = 0;
// Return: The number of elements in the list.
virtual int length() const = 0;
// Return: The position of the current element.
virtual int currPos() const = 0;
// Set current position.
// pos: The position to make current.
virtual void moveToPos(int pos) = 0;
// Return: The current element.
virtual const E& getValue() const = 0;
};
// Singly linked list node
template <typename E> class Link {
public:
E element; // Value for this node
Link *next; // Pointer to next node in list
// Constructors
Link(const E& elemval, Link* nextval =NULL) {
element=elemval;
next=nextval;
}
Link(Link* nextval =NULL) {
next=nextval;
}
};
template <typename E> class LList: public List<E> {
private:
Link<E>* head; // Pointer to list header
Link<E>* tail; // Pointer to last element
Link<E>* curr; // Access to current element
int cnt; // Size of list
void init() { // Intialization helper method
curr=tail=head=new Link<E>;
cnt=0;
}
void removeall() { // Return link nodes to free store
while(head!=NULL){
curr=head;
head=head->next;
delete curr;
}
}
public:
LList(int size=100) {
init(); // Constructor
}
~LList() {
removeall(); // Destructor
}
// 使用空格分隔输出线性表中的所有数据，并最终换行
//无数据时直接输出空行
void print(){
Link<E>* tmp=head->next;
while(tmp!=NULL){
cout<<tmp->element<<' ';
tmp=tmp->next;
}
cout<<endl;
}
void clear() {
removeall(); // Clear list
init();
}
// Insert "it" at current position
void insert(const E& it) {
curr->next=new Link<E>(it,curr->next);
if(tail==curr)tail=curr->next;
cnt++;
}
void append(const E& it) { // Append "it" to list
tail=tail->next=new Link<E>(it,NULL);
cnt++;
}
// Remove and return current element
E remove() {
Assert(curr->next != NULL, "No element"); //如当前元素不存在，将直接报错，并终止程序
E it=curr->next->element;
Link<E>* ltemp=curr->next;
if(tail==curr->next)tail=curr;
curr->next=curr->next->next;
delete ltemp;
cnt--;
return it;
}
// Place curr at list start
void moveToStart() {
curr=head;
}
// Place curr at list end
void moveToEnd() {
curr=tail;
}
// Move curr one step left; no change if already at front
void prev() {
if(curr==head)return;
Link<E>* temp=head;
while(temp->next!=curr)temp=temp->next;
curr=temp;
}
// Move curr one step right; no change if already at end
void next() {
if(curr!=tail)curr=curr->next;
}
// Return length
int length() const {
return cnt;
}
// Return the position of the current element
int currPos() const {
Link<E>* temp=head;
int i=0;
for(;curr!=temp;i++)
temp=temp->next;
return i;
}
// Move down list to "pos" position
void moveToPos(int pos) {
Assert ((pos>=0)&&(pos<=cnt), "Position out of range");
curr=head;
for(int i=0;i<pos;i++)
curr=curr->next;
}
// Return current element
const E& getValue() const {
Assert(curr->next != NULL, "No value");
return curr->next->element;
}
};
//读取测试指令，进行测试
void test(LList<int> &llist) {
int act;
int pos,value;
do {
//读取指令 指令说明：1 插入 2 删除 3 获取值 4 查找
cin>>act;
switch(act) {
case 1://在pos位置插入值value
cin>>pos>>value;
llist.moveToPos(pos);
llist.insert(value);
llist.print();
break;
case 2://删除pos位置的元素
cin>>pos;
llist.moveToPos(pos);
llist.remove();
llist.print();
break;
case 3://获取指定位置的值
cin>>pos;
llist.moveToPos(pos);
cout<<llist.getValue()<<endl;
break;
case 4://查询特定值所在位置，如果存在输出位置，否则不输出
cin>>value;
for(llist.moveToStart(); llist.currPos()<llist.length(); llist.next()) {
if(llist.getValue()==value) {
cout<<llist.currPos()<<endl;
break;
}
}
break;
case 0:
return;
}
} while(true);
}
int main() {
LList <int>llist;
test(llist);//测试
return 0;
}
反思：
关于学校的CG作业，我一直是比较轻视的。加上我从大一上就开始了数据结构与算法课程的自学，对待这些作业一直有些心高气傲。
而本学期的第一次课程考试就考了这一道题目,但那时，我还拖着没有做（课代表催我们做，但我要拖到DDL）。
最后考试结果自然是零分。一直程序报错。
考试时，我一直以为是insert函数实现有问题
一直找，一直报错。
回来后我试着对每个函数进行一下重构——
发现居然是print实现出错，很简单的事嘛
考试时，我一直写的print是：
void print(){
Link<E>* tmp=head;
while(tmp!=NULL){
tmp=tmp->next;
cout<<tmp->element<<' ';//head是哑巴头结点直接跳过）
}
cout<<endl;
}
回宿舍后，我把print改成：
void print(){
Link<E>* tmp=head;
while(tmp!=NULL&&tmp->next!=NULL){
tmp=tmp->next;
cout<<tmp->element<<' ';//不要错误地访问到空指针
}
cout<<endl;
}
这样就没问题了。
经历这件事，我深深地反省了自己——
仅仅是知道原理就够了吗？
只是学了一点皮毛就可以不听课了吗？
明明可以早早做完的事为什么要拖到明天做呢？
为什么要骗课代表，自己已经写完了呢？
知道 不等于 精通，会想 不代表 能做。
3、实验三：预测（二叉树的实现）
题目描述：
题解：
#include<iostream>
#include"string"
#include<queue>
using namespace std;
template<typename E>
class BinNode//结点类
{
private:
BinNode*lc;//左孩子
BinNode*rc;//右孩子
E elem;
public:
BinNode()//默认构造函数，设置左右孩子为空
{
lc=rc=NULL;
}
BinNode(E tmp, BinNode*l=NULL, BinNode*r=NULL)//带参构造函数
{
elem=tmp;lc=l;rc=r;
}
BinNode*left()//返回左孩子
{
return lc;
}
BinNode*right()//返回右孩子
{
return rc;
}
void setLeft(BinNode*l)//设置左孩子
{
lc=(BinNode*)l;
}
void setRight(BinNode*r)//设置右孩子
{
rc=(BinNode*)r;
}
void setValue(E tmp)//设置当前结点的值
{
elem=tmp;
}
E getValue()//获得当前结点的值
{
return elem;
}
bool isLeaf()//判断当前结点是否为叶子结点
{
return (lc==NULL)&&(rc==NULL);
}
};
template<typename E>
class BinTree//二叉树类
{
private:
BinNode<E>*root;//根结点
void clear(BinNode<E>*r)//清空二叉树
{
if(r!=NULL){
clear(r->left());
clear(r->right());
delete r;
}
}
void preOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//先序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp==nullptr)return;
visit(tmp);
preOrder(tmp->left(),visit);
preOrder(tmp->right(),visit);
}
void inOrder( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//中序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp==nullptr)return;
inOrder(tmp->left(),visit);
visit(tmp);
inOrder(tmp->right(),visit);
}
void postOrder(BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//后序遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp==nullptr)return;
postOrder(tmp->left(),visit);
postOrder(tmp->right(),visit);
visit(tmp);
}
void LevelOrderTranverse( BinNode<E>*tmp,void(*visit)(BinNode<E>*node))//层次遍历，void(*visit)(BinNode<E>*node)为一个函数指针参数，用visit代替传进来的函数，在遍历函数中使用传进来的函数功能
{
if(tmp==nullptr)return;
queue<BinNode<E>*>q;
q.push(tmp);
while(!q.empty()){
int n=q.size();
for(int i=0;i<n;i++){
BinNode<E>* atmp=q.front();
q.pop();
visit(atmp);
if(atmp->left())q.push(atmp->left());
if(atmp->right())q.push(atmp->right());
}
}
}
int BinTreeDepth(BinNode<E>*tmp)//获得二叉树的深度
{
return BinTreeHeight(tmp)==0?0:(BinTreeHeight(tmp)-1);
}
int BinTreeNodes(BinNode<E>*tmp)//获得二叉树的结点数
{
if(tmp==nullptr)return 0;
else return BinTreeNodes(tmp->left())+BinTreeNodes(tmp->right())+1;
}
int BinTreeHeight(BinNode<E>*tmp)//获得二叉树的高度
{
if (tmp == nullptr) return 0;
return max(BinTreeHeight(tmp->left()), BinTreeHeight(tmp->right()) )+1;
}
int BinTreeLeafs(BinNode<E>*tmp)//获得二叉树的叶子结点数
{
if(!tmp)return 0;
if(!tmp->left()&&!tmp->right())return 1;
else{
int m=BinTreeLeafs(tmp->left());
int n=BinTreeLeafs(tmp->right());
return m+n;
}
}
bool find(BinNode<E>*tmp, E e)//查找二叉树中是否含有某个名为e的结点
{
if(tmp==nullptr)return false;
if(tmp->getValue()==e)return true;
else return find(tmp->left(), e)||find(tmp->right(),e);
}
public:
BinTree()//默认构造函数
{
root=new BinNode<E>;
}
~BinTree()//析构函数
{
clear(root);
}
bool BinTreeEmpty()//判断二叉树是否为空
{
if (root == NULL)
return true;
else
return false;
}
BinNode<E>*getRoot()//获得根节点
{
return root;
}
void setRoot(BinNode<E>*r)//设置根节点
{
root = r;
}
//下面的函数是对外的函数，所以内部还会有一些同名的函数，但是参数列表不一样，实现数据的封装，外部的调用不会涉及到内部的数据对象
void clear()//清空二叉树
{
clear(root);
root = NULL;
}
void preOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
preOrder(root,visit);
}
void inOrder(void(*visit)(BinNode<E>*node)) //先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
inOrder(root,visit);
}
void postOrder(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
postOrder(root,visit);
}
void LevelOrderTranverse(void(*visit)(BinNode<E>*node))//先序遍历，传入相对应的访问函数即可对该当前结点实现不同功能的访问（本程序为输出）
{
LevelOrderTranverse(root,visit);
}
int BinTreeDepth()//获得二叉树深度
{
return BinTreeDepth(root);
}
int BinTreeNodes()//获得二叉树结点数
{
return BinTreeNodes(root);
}
int BinTreeHeight()//获得二叉树高度
{
return BinTreeHeight(root);
}
int BinTreeLeafs()//获得二叉树叶子结点数
{
return BinTreeLeafs(root);
}
bool find(E e)//查找二叉树中是否存在名为e的结点
{
return find(root, e);
}
};
template<typename E>
void printNode(BinNode<E>*tmp)//打印结点的值的函数
{
cout << tmp->getValue() << " ";
}
template<typename E>
BinNode<E>* creatBinaryTree(string s[], int &x,int n)//构建二叉树的主函数，根据先序遍历，采用递归思想构建
{
if (s[x] =="/")
return NULL;
else
{
BinNode<E>*node = new BinNode<E>(s[x]);
x = x + 1;
if (x < n);
node->setLeft(creatBinaryTree<E>(s, x,n));
x = x + 1;
if (x < n);
node->setRight(creatBinaryTree<E>(s, x,n));
return node;
}
}
void creatBinaryTree(BinTree<string>*BT)//构建二叉树的函数，包含了上面的构建二叉树的主函数，仅仅起到了在主函数中简洁一些的作用
{
//cout << "现在进入构建二叉树程序......" << endl;
//cout << "请输入二叉树有多少个结点(空结点也计算其中)" << endl;
int n = 0;
cin >> n;
//cout << "请按preorder顺序输入，遇到NULL请输入'/',用空格隔开或者回车隔开均可以" << endl;
string*s = new string[n];
for (int i = 0; i < n; i++)
{
cin >> s[i];
}
int now = 0;
BT->setRoot(creatBinaryTree<string>(s, now, n));
}
int main()
{
//本程序的二叉树是一个模板类，若想改变为别的类型，可以在相关的地方在“<>”中修改相关参数,本程序默认为最具有普遍性的string
BinTree<string>*BT = new BinTree<string>;
creatBinaryTree(BT);
string strfind;
cin>>strfind;
//在这里，已经构建好了一棵二叉树
//下面是二叉树的基本函数操作的展示
cout << "0:判断是否为空树：";
if (BT->BinTreeEmpty() == true)
cout << "是" << endl;
else
cout << "否" << endl;
cout << "1:前序遍历:";
BT->preOrder(printNode);
cout << endl;
cout << "2:中序遍历:";
BT->inOrder(printNode);
cout << endl;
cout << "3:后序遍历:";
BT->postOrder(printNode);
cout << endl;
cout << "4:层次遍历:";
BT->LevelOrderTranverse(printNode);
cout << endl;
cout << "5:记录树的深度:";
cout << BT->BinTreeDepth() << endl;
cout << "6:记录树的高度:";
cout << BT->BinTreeHeight() << endl;
cout << "7:统计结点:";
cout << BT->BinTreeNodes() << endl;
cout << "8:统计叶子结点:";
cout << BT->BinTreeLeafs() << endl;
cout << "9:查找"<<strfind<<":";
if (BT->find(strfind) == true)
cout << "存在" << endl;
else
cout << "不存在" << endl;
cout << "10:是否清空:";
BT->clear();
cout << "已清空" << endl;
cout << "5:记录树的深度:";
cout << BT->BinTreeDepth() << endl;
cout << "6:记录树的高度:";
cout << BT->BinTreeHeight() << endl;
cout << "7:统计结点:";
cout << BT->BinTreeNodes() << endl;
cout << "8:统计叶子结点:";
cout << BT->BinTreeLeafs() << endl;
return 0;
}
反思
果然，运行成功花费一小时,解答成功五分钟
这次的题目遇到的问题：
- 其一是：二叉树高度和深度的区别
- 其二是：计算叶子节点的个数，开始用的方法又指针出错了，找了好久才找到
没有可恶的test函数找bug容易多了
惟楚有才，于斯为盛。欢迎来到长沙！！！ 茶颜悦色、臭豆腐、CSDN和你一个都不能少~
更多推荐
12
0- 0
已为社区贡献2条内容
所有评论(0)