中国地质大学(武汉)数据结构课程设计
发布时间:2024-02-09
摘要: 题目一 带环、相交链表问题 本次实习采用了链式存储结构进行线性表的构建,其中结点结构体如下所示: struct linknode { int data;//数据域 linknode* next;//指针域 linknode(int a = 0, li...

题目一

带环、相交链表问题


本次实习采用了链式存储结构进行线性表的构建,其中结点结构体如下所示:

struct linknode
{
	int data;//数据域
	linknode* next;//指针域
	linknode(int a = 0, linknode* p = NULL)//构造函数
	{
		data = a;
		next = p;
	}
};

链表的类结构如下所示:

class list
{
成员变量:
	linknode* first1;//头结点指针
	linknode* first2;//成环后的另一个头结点指针
	linknode* last;//单链表的尾指针
	int length;//单链表长度(元素个数)
	


成员函数:
构造函数:list() ;
析构函数:~list() { }
判断链表是否为空:bool isempty();
清空链表:void makeempty();
寻找元素值为x的结点的指针函数:bool find(int x,linknode*&p);
数值为m,n的两个结点成环:bool ring(int m, int n);
判断链表是否成环:bool isring(linknode *x,linknode *&p,linknode *&q,int &l);
恢复成单链表:bool relist();
求单链表长度:int listlength(linknode* x);
判断链表相交情况:bool iscross(linknode* a, linknode* b,linknode *&c);
};

(2)模块设计
A.主程序模块:

Int main(){
初始界面;
选择实现的功能;
1.	构建链表
2.	链表成环
3.	恢复单链表
4.	判断链表是否相交
}

B. 构建链表模块
C. 链表成环模块
D. 恢复单链表模块
E. 判断链表是否相交模块

各模块之间关系图:


那时候还不会用PPT画图,所以画出来的图片贼丑,强烈建议使用PPT画图片,科研论文里的插图也可以用PPT画出来,还很精美。

详细设计

关键函数及其算法思想

  1. 链表构造函数
list() 
	{ 
		first1 = new linknode();
		first2 = new linknode();
		last = first1;
		length = 0;
	}

2.	判断链表是否为空函数
如果头指针指向的元素为空,则整个链表是空的
bool isempty()
	{
		if (first1->next == NULL) return true;
		else return false;
}
  1. 清空链表函数
    对于2个指针,依次从头结点开始向后遍历,每遇到一个非空结点,就将其删除,同时指针向后移动,最后所有的结点都被清空
void makeempty()
	{
		while (first1->next!= NULL)//从第一个头结点出发清空
		{
			linknode* p  = first1->next;
			first1 = p->next;
			delete p;
		}

		while (first2->next != NULL)//从第二个头结点出发
		{
			linknode* p = first2->next;
			first2 = p->next;
			delete p;
		}
	}
  1. 寻找值为x的结点函数(仅对于普通单链表)
    从第一个头结点first1开始依次向后遍历,每一次访问的结点元素和x比较,如果相等则返回将结点的指针赋值给p,否则向后移动继续遍历,如果到结尾仍然没有相等,p最终返回空指针。
bool find(int x,linknode*&p)
	{
		linknode* q = first1->next;
		while (q != NULL)//遍历
		{
			if (q->data == x) {//找到了该结点
				p = q;//赋值
				return true;
			}
			q = q->next;//向下继续寻找
		}
		if(q==NULL) return false;//没有找到,返回空指针
	}
  1. 插入值为x的结点函数
    首先进行对于当前数值的结点是否在链表中存在的判断,如果有则结束函数。
    如果没有,则将链表插入,由于之前提前设定了一个尾部指针,所以在插入的时候可以直接将结点加入到尾部,同时尾部指针后移,链表长度加一。
bool insert(int x)
	{
		linknode* l;
		if (find(x,l)) { cout << "当前结点已存在,请重新输入" << endl; return false; }//判断当前元素是否存在
		else
		{
			if (first1->next == NULL)
			{
				first1->next = new linknode(x);
				last = first1->next;
				length++;
				return true;
			}
			Else//从尾部插入
			{
				linknode* q = new linknode(x);
				last->next = q;//尾插
				last = q;//尾指针后移
				length++;//链表长度增加
				return true;
			}
		}
	}
  1. 单链表成环函数
    成环的思路如下:首先找到输入的m,n的结点的位置(如果两个结点不存在直接结束函数),然后将n所在结点q的指针next指向m所在的结点p,同时给n结点后面的单链表增加一个头结点first2,最后将last指向的结点的next指向m所在的结点p。具体操作如下:
bool ring(int m, int n)
{
linknode* p,* q;
if (!find(m,p) || !find(n,q)) { cout << "当前结点不存在!请重新输入" << endl; return false; }//判断结点是否存在
linknode* k = q;
while (k != NULL)
{
	if (k->next == p) { cout << "结点顺序错误,请重新输入" << endl; return false; }
	k = k->next;
}
first2 = new linknode();
first2->next = q->next;
last->next = p;
q->next = p;
成环后需要将链表输出,首先需要统计两个头结点非环部分的元素个数,以便输出时可以对齐。然后首先输出first1头结点非环部分的元素,并且统计输出字符的个数;之后输出环部分,先空出之前统计的字符的位置,然后从环起点开始依次输出元素;最终输出first2头结点非环部分的元素。
}
  1. 成环相交链表寻找环起点、终点、长度函数
    该函数采用快慢指针的方式进行寻找。
    首先设置快慢指针fast、slow。其中快指针每次走2步,慢指针走1步,开始时两个指针同时从头结点出发,当慢指针走到和快指针再次相遇时,将慢指针回到头结点,2个指针以相同的速度往前行走,当二者再次相遇时,所在位置就是环的起点。(具体数学原理在下面说明)。之后慢指针继续移动,快指针不动,每次移动统计走过结点数量,当slow->next== fast 时,到达环终点,统计的数量就是环的长度。
    设链表非环部分长度为k,环长度为R。一开始快指针走两步,慢指针走一步,当慢指针到达环的入口时存在等式2k=k+nR+delta(delta为快指针在环内领先慢指针的距离)。得到k=nR+delta,即链表非环部分的长度。
    当它们再次相遇时满足如下式子 2t+delta-t=NR;
    可以解得t=NR-delta.此时慢指针再次从头结点出发走k步到达环入口,而快指针每次也只走一步,共走了k步,k+t=(N+n)R,也回到了环的起点。
bool isring(linknode *x,linknode *&p,linknode *&q,int &l)
	{
		linknode* fast,*slow;
		fast = slow = x->next;
		while (fast != NULL && slow != NULL)
		{
			slow = slow->next;
			fast = fast->next->next;
			if (fast == slow)
			{
				slow = x->next;
				while (slow != fast&&slow!=NULL&&fast!=NULL)
				{
					slow = slow->next;
					fast = fast->next;
					if(slow==fast)
					{
						p = fast;
						int count = 1; slow = slow->next;
						while (slow->next != fast)
						{
							slow = slow->next;
							count++;
						}
						q = slow;
						l = count;
						break;
					}
				}
				return true;
			}
		}
		return false;
	}
  1. 恢复单链表函数
    首先判断链表是否被成环,如果已经是单链表则结束函数。如果是有环的,恢复的方法是将环终点的指针指向first2->next,然后删掉first2,然后将last->next=null即完成恢复。
    由于之前构建单链表的时候统计了链表长度,所以恢复单链表以后只需要从first1->next开始遍历,同时统计已经经过的结点数量,当达到length/2时结束,返回结点的值。
bool relist()
	{
		linknode*x=first1,* p, * q;
		int l;
		if (!isring(x, p, q, l)) { return false; }
		else
		{
			q->next = first2->next;
			delete first2;
			last->next = NULL;
			p = first1->next;
			int count = 0;
			while (p != NULL)
			{
				count++;
				if (count == length / 2)
				{
					cout <<"中间元素为"<< p->data<next;
			}
		}
	}

9.判断链表的相交函数
首先,两条链表相交存在三种情况:1.均没有环2.有环且入口相同3.有环且入口不同。
对于后两者,首先判断两个链表有无环并得到环的入口结点指针,如果相同则直接得到相交结点。
如果不一样则从其中一个入口出发,依次遍历环的元素,当达到另一个入口时返回当前结点指针。
对于第一种全都无环的情况,首先需要统计两条链表的长度l1、l2,然后让长的链表先走|l1-l2|步使得两个链表“长度一样”,然后两个链表的指针一起移动,当指针相遇时就可以得到相交的位置。

bool iscross(linknode* a, linknode* b,linknode *&c)
	{
		if (a == NULL || b == NULL || a->next == NULL || b->next == NULL) return false;
		linknode* pa, * pb, * qa, * qb; int la,lb;
		//均没有环
		if (!isring(a, pa, qa, la) && !isring(b, pb, qb, lb))
		{
			int l1 = listlength(a);
			int l2 = listlength(b);
			if (l1 > l2)
			{
				for (int i = 0; i < (l1 - l2); i++) a = a->next;
			}
			else
			{
				for (int i = 0; i < (l1 - l2); i++) b = b->next;
			}
			while (a != NULL && b != NULL&&a!=b)
			{
				if (a == b) { c = a; return true; }
				a = a->next; b = a->next;
			}
			if (a == NULL || b == NULL) return false;
		}
		//都有环
		else if (isring(a, pa, qa, la) && isring(b, pb, qb, lb))
		{
			if (pa == pb) {//环入口位置相同,直接找到相交结点
				c = pa; return true;
			}
			else if (pa != pb)//环入口位置不一样,需要从其中一个入口依次遍历环上结点,最终与另一个入口相遇
			{
				pa = pa->next;
				while (pa != pa)
				{
					if (pa == pb) {
						c = pa; return true;
					}
					pa = pa->next;
				}
				if (pa == pa) return false;
			}
		}
	}

时间复杂度分析:

时间复杂度分析:由于在一开始采用了一个 last 指针标记尾部,所以在进行插入元素、构建成环链表、恢复单链表时时间复杂度均为 O(1),在寻找链表的
环出入口时,可能主要是快指针的遍历,设环长度为 R,非环部分长度为 k,时间复杂化度为 O(k+(n+N+1)R)。在寻找相交结点的时候,最差情况下是遍历了整个链表,所以时间复杂度为 O(n)。
改进措施:可以完善以下可视化,将链表的构造、成环以及寻找相交结点的
过程展示出来,使得看起来更加清楚

题目二

BST问题


当时在写这题的时候,我理解错了题意,当时还问了老师很久,属实当时有点没转过弯哈哈哈。
在每个TreeNode里面,我不仅存了每个结点的左右子节点,还存了转换为双向链表之后的前驱和后继结点的位置,这样在得到双向链表时,我只需要中序遍历一遍得到结点的顺序,再相互连接,就可以得到双向链表
1、数据结构定义:
程序将涉及到如下线性表结构以及结点类的数据类型,用类C语言描述如下:
(1)定义单链表类型:

ADT CreateTree {
	数据对象:D={Si | Si ∈树节点类集合};
	数据关系:R1={<Si-1,Si>} |结点左右子树,前后结点的关系}
	基本操作:
preinorder(vector<int> pre, vector<int> in);
初始条件:前序和中序序列;
操作结果:通过前序和中序序列得到树;
postinorder(vector<int> post, vector<int> in);
初始条件:后序和中序序列;
操作结果:通过后序和中序序列得到树
isBst(TreeNode* rt, int low, int high);
初始条件:树的根结点,以及左右边界;
操作结果:判断是否是BST
inorder(TreeNode* rt, vector<TreeNode*>& vec);
初始条件:根节点以及存储结果的数组;
操作结果:输出前序遍历的结果;
change2link(TreeNode* rt);
初始条件:根节点;
操作结果:把树转换成双向链表;
}ADT CreateTree

(2)定义树的结点类型:
ADT  TreeNode{
	数据对象:D={Si | Si ∈标准c++整数集合,i = 1,2,3,…….,n,n ≥ 0};
	数据关系:R1={<Si-1,Si>} |左右结点,前后结点 }
	基本操作:构造与析构
}ADT TreeNode

2、模块设计:

  1. 主程序模块:主界面设计如下
    i. 数据输入框;
    ii. 建立二叉树模块;
    iii. 重新建立二叉树;
    iv. 判断是否为BST;
    v. 改变为双向链表;
  2. 建立二叉树模块-------建立二叉树;
  3. 判断是否为BST --------判断二叉树是否是BST;
  4. 改变为双向链表------将BST改变为二叉树;
  5. 结果展示-------画出单链表或者是环

    1、存储结构设计
/**
*	结点类,存储的是值、位置、前驱后继和左右子树
*/
class TreeNode {
public:
	TreeNode* left;
	TreeNode* right;
	TreeNode* parent;
	TreeNode* next;
	TreeNode* front;
	int x = 0, y = 0;
	int val;
};
 /**
*	二叉树
*/
class CreateTree :public TreeNode {
public:
	TreeNode* head;
	TreeNode* root;
	int size = 0;
	int tag = 0;//标志是否建树成功};
3、主要算法设计:
/**
*	根据前序和中序建树
*/	
		TreeNode* root = new TreeNode(pre[pl]);//根据前序确立根节点
		int left_tree_size = mp[pre[pl]] - il;
		// 递归地构造左子树,并连接到根节点
		// 先序遍历中「从 左边界+1 开始的 size_left_subtree」个元素就对应了中序遍历中「从 左边界 开始到 根节点定位-1」的元素
		root->left = ctpreinorder(pre, in, pl + 1, pl + left_tree_size, il, mp[pre[pl]] - 1);
		// 递归地构造右子树,并连接到根节点
		// 先序遍历中「从 左边界+1+左子树节点数目 开始到 右边界」的元素就对应了中序遍历中「从 根节点定位+1 到 右边界」的元素
		root->right = ctpreinorder(pre, in, pl + left_tree_size + 1, pr, mp[pre[pl]] + 1, ir);
/**
*	根据后序和中序建树
*/
	//原理与前序+中序基本相同
	TreeNode* root = new TreeNode(post[pr]);//根据后序确立根节点
	int right_tree_size = ir - mp[post[pr]];
	root->right = ctpostinorder(post, in, pr - right_tree_size, pr - 1, mp[post[pr]] + 1, ir);
	root->left = ctpostinorder(post, in, pl, pr - right_tree_size - 1, il, mp[post[pr]] - 1);
/**
*	判断是否是BST,根据BST的性质,运用递归的思想,设置一个左右区间,如果不在这个范围,说明该节点有问题所以不是BST
*/
	bool isBst(TreeNode* rt, int low, int high) {
		if (rt == nullptr)return true;//如果到了叶节点的左右结点则返回
		if (rt->val <= low || rt->val >= high)return false;//如果该结点的值不在左右区间

		return isBst(rt->left, low, rt->val) && isBst(rt->right, rt->val, high);//递归遍历左右子树
	} 
/**
*	改变为双向链表,BST中序遍历得到的结果是有序的,可以直接建立双向链表
*/
	bool change2link(TreeNode* rt) {
		vector< TreeNode*>vec;//存储中序遍历结果
		if (inorder(rt, vec)) {//中序遍历
			int n = vec.size();
			for (int i = 0, j = 1; j < n; i++, j++) {
				vec[i]->next = vec[j];
				vec[j]->front = vec[i];
			}
			head = vec[0];
		}
	} 

题目三

交通咨询系统设计



两个题里选一个,我做的第一个,第二当时感觉很难~~我太菜了
~~

交通设计

MFC做的,代码太多了,直接截图放个报告参考叭。
那时候也没有学会如何在报告里粘一个好看的代码QWQ,大二下才知道Carbon这个代码高亮的网站,以后报告都用这个粘代码了,可以选择不同样式,个人觉得很美观,如下:





答案对不对我就没有去考证了

题目四

简单搜索引擎系统

这个和队友写的,两个人合作,当时学了一点git,算是第一次合作开发的项目,比较有点意义吧,当时按照评分规则,这题写了就90+。验收的时候看到有大神用了前端东西,做了一个web的前端搜索页面出来,是能说是太牛了%%%%%%%。我们的就太丑陋了。

题目五 重量级的一题!!!!

高校带权无向图简单图与交通路线规划系统



这个题改编自普林斯顿大学的题目原题链接,但是说实话改编好像不是很好,当时做这个题的同学在说哪个地方不对来着,(好像还结合哪一个题来着,就是那个带权无向图很熟悉 )。这道题当时我想自己做来着,可是那会濒临寒假,时间也来不及,加上自己比较菜,就放弃了,打算后来寒假里写的,可是寒假做了个手术,床上躺了两个星期就把这个事情给忘记了,哈哈哈哈,今年数据结构课设又来了,抽空在这个寒假把这个写了,也算是锻炼自己吧,正好可以抽空学一下前端,做一个前端页面出来。

看了一下今年2022的数据结构课设,加了几个题

2022的题目:

疫情控制


这个题是NOIP2012 提高组原题,
下面放一个洛谷原题链接,很多人可能见过,但我们那年没这个题。
疫情控制
洛谷yyds

海关检查站模拟


这道题我绝对在哪里见过,好像是前几年的数据结构课设题目。

社交网络红楼梦任务关系


哈哈哈哈,前几个月的数据可视化课程上做过类似的工作,不过是调库完成。类似这个PPT图例



主要是中文分词jieba库、词云绘制wordcloud库、社交关系网络networkx库这三个库的使用。

头皮发麻
2022年12月5日:
后续更新代码,先弄完计科的课设和报告润回家。。。。。。。
2022年12月13日:
已更新部分代码和报告