精华内容
下载资源
问答
  • 华中科技大学数据结构的基于AVL的课程设计,要求实现Set集合和人物之间的关系操作。
  • 从键盘读入一组数据,建立二叉排序并对其进行查找、遍历、格式化打印等有关操作。 【基本要求】 建立二叉排序并对其进行查找,包括成功和不成功两种情况,并给出查找长度 【选作内容】 实现二叉排序的插入、...
  • 数据结构课设

    2012-01-25 18:18:16
    数据结构很好的学习材料,希望可以帮助到更多的朋友。
  • 数据结构课程设计 数据结构课设 数据结构 课程设计 课设
  • 这是大二时的数据结构课设,今天与大家分享。可以读写文件,编码译码,以及对输入的异常处理。
  • 数据结构课设 哈夫曼 C++源码 需要的拿去
  • 数据结构课设B

    2015-07-22 19:36:01
    数据结构课程设计 B,使用QT写的,运行在linux上,IDE是Qt Creator 4.8
  • c语言数据结构课设

    2011-06-23 21:42:44
    包含有表达式求职,订票系统,二叉排序,二叉树的便利,哈夫曼殊,内部排序的比较等
  • 一共有4个,汽车到停车场停车的问题;利用哈夫曼利用哈夫曼求得用于通信的二进制编码;针对学生的手机号码,设计一个哈希表,使得平均查找长度不超过给定值R;训练双向链表的建立,以及链表中数据查找插入删除。
  • 一.问题描述 很多涉及图上操作的算法都是以图的遍历操作为基础的。试写一个程序,演示无向图的遍历操作。 二....以用户指定的结点为起点,分别输出每种遍历下的结点访问序列和相应生成的边集。
  • 浙江理工大学数据结构课程设计,构建一个哈夫曼编码,前端页面展示
  • 数据结构课设_B+.zip

    2020-05-16 01:11:10
    数据结构课设_B+.zip
  • 但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个...
  • 数据结构课设_B+

    2018-06-12 22:52:45
    用c编写的B+,BUG较少,综合了网上的优秀代码,并进一步形成自己的代码。代码基本有注释,风格良好,能够很快看懂。内含有比较规范的报告文档,包含所有流程图,说明图,以及文档风格绝对不错,无需更改,建议下载...
  • 一个完整的系统应具有以下功能: (l)I:初始化 (Initialization)。...将已在内存中的哈夫曼以直观的方式 (或凹入表形式)显示在终端上,同时将此字符形式的哈夫曼写入文件 treeprint 中。 txt文件自建
  • 数据结构课设<最小生成问题>cpp含实验报告 数据结构课设<最小生成问题>cpp含实验报告 数据结构课设<最小生成问题>cpp含实验报告 打包下载 打包下载
  • 这要求在发送端通过一个编码系统对待传输数据预先编码,在接收端将传来的数据进行译码(复原)。写一个哈夫曼编码译码系统。 2.基本要求 一个完整的系统应具有以下功能: I:初始化(Initialization)。从终端读入...
  • 数据结构课设:二叉排序的判别 有源代码
  • 数据结构课设

    2012-12-27 19:08:58
    数据结构课程设设计,c语言编程,有关图的操作,包括深度遍历,最小生成,迪杰斯特拉算法
  • 可以通过人机界面,手工绘制包含顺序型、选择型的NS图,为每个类型的NS图可以输入C语言源代码文本,各类型的图可以相互嵌套组合,并能够将绘制好的NS图转换为C语言代码描述的程序。 1)程序运行时先拖入一个“顺序型...
  •   本次《数据结构课设我选择了有关拓扑排序的题目,题目大意如下:   给定课程编号、课程名称、学分、先修条件以及约束条件:学期数和每学期学分上限,给出一个排课方案。 1.设计的逻辑结构:   邻接...

    拓扑排序

    相关概念

    先给出百度百科的有关概念:

      对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边(u,v)∈E(G),则u在线性序列中出现在v之前。通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。

      举个通俗的例子——排课方案。只有学习了相应的基础课(如高数、线代)后,才能学习进阶课(比如人工智能),而拓扑序列正是因此产生——拓扑序列满足一个事件发生的条件一定排列在这个事件之前。比如有课程及其先修课程如下:

    课程先修课程
    数据结构离散数学
    离散数学高等数学
    高等数学

    显然,想要学习数据结构,就要先学习离散数学,想要学习离散数学,就先要知道基础的高数知识,而高数作为大学基础课,则不需要先修。
      那么,依据此课程表排出的一个拓扑序列则是:

    高等数学→离散数学→数据结构

      拓扑排序得到的拓扑序列不一定唯一,例如,在上边中加入不需要先修知识的《程序设计基础》课程,此课程与高数的层级是并列关系,那么,先修这两个的哪个都是一样的。因此拓扑序列存在不唯一性。

    算法设计

      按照先修课程的思想,我们应当从依赖课程较少的课开始,逐渐学习。就像玩DNF给角色升级技能一样,不同角色觉醒后拥有不同技能,而想要获得高级技能,就要先学习其依赖的低级技能。
      因此,不妨从无依赖的课程开始学起,逐渐解锁“技能树”。那么,生成拓扑序列的一种方案是这样的(使用栈或队列存储信息均可):

    1. 遍历所有课程,将无先修依赖(入度为 000)的点全部压入栈中;
    2. 判断栈是否为空,如果不为空,弹出一个课程并将其加入拓扑序列;
    3. 由于此课程被解锁,以它为依赖的课程便均没有了这个依赖。因此,以它为依赖的课程入度均−1-1−1;
    4. 判断以它为依赖的课程在经过入度−1-1−1后,入度是否变为 000,如果是,将课程压栈;
    5. 重复 2 → 4 2→4 24,直至栈为空为止。

      另外,拓扑排序图中不能存在回路——其实很好理解,想象一下,回路的存在意味着一个课程以它自己为先修条件——这显然很荒谬。


    代码实现

      本次《数据结构》课设我选择了有关拓扑排序的题目,题目大意如下:
      给定课程编号、课程名称、学分、先修条件以及约束条件:学期数和每学期学分上限,给出一个排课方案。

    1.设计的逻辑结构:
    在这里插入图片描述
      邻接表部分表示了我做的题目的课程依赖关系。这里我使用了哈希表的方式,来减少通过搜索课程编号进而索引其邻接表表头下标带来的 O ( n ) O(n) O(n)时间复杂度。

    2. A O V AOV AOV网络图

    在这里插入图片描述
    3.代码

    #include<iostream>
    #include<map>
    #include<fstream>
    #include<stack>
    #include<vector>
    #include<string>
    #include<sstream>
    #include<windows.h>
    using namespace std;
    typedef int ScoreType;
    typedef string Number;
    struct CourseInfo {								   // 单个课程的信息 
    	string courseName;							   // 课程名称 
    	ScoreType credit;						       // 课程学分 
    	int inDgree;							       // 每个点的入度 
    	CourseInfo(string courseName = "NULL", ScoreType credit = 0, int inDgree = 0) {
    		this->courseName = courseName;
    		this->credit = credit;
    		this->inDgree = inDgree;
    	}
    };
    struct CourseNode {								   // 单个课程节点 
    	Number courseNumber;						   // 课程编号 
    	struct CourseNode *next;
    	CourseNode(Number courseNumber = "NULL") {
    		this->courseNumber = courseNumber;
    		next = NULL;
    	}
    };
    struct CourseList {
    	vector<CourseNode*> courseNet;  			   // 课程邻接表 
    	vector<CourseNode*> tailPoint;    			   // 记录每行的尾指针
    	vector<CourseInfo> courseInfo;   			   // 课程信息
    	map<Number, int> hm;	     	 			   // 哈希表,用来记录编号与下标的关系,如201706020115对应下标 1号 
    	int vertexNum;					 			   // 当前课程数量
    	CourseList() {
    		vertexNum = 0;
    	}
    	void CreateHashMap(stringstream &ss);		   // 建立索引哈希表
    	void CreateAdjList(string buf, int index);     // 建立邻接表
    };
    struct UserInterface {
    	CourseList course;
    	vector<string> topoOrder;         			   // 拓扑序列:C1->C2->C3...
    
    	bool JudgeLogicError(int count);  			   // 判断课程逻辑是否有误,拓扑图不能有环 
    	void LoadingCourseInfo();
    	void ReadFromFile();
    	void GetTopologicalOrder();
    	void ShowTopoOrder();             			   // 显示拓扑序列方案
    	void ShowCourseInfo();
    	void UserOption();
    	char ShowOption();
    };
    int main()
    {
    	UserInterface user;
    	user.UserOption();
    	system("pause");
    	return 0;
    }
    void CourseList::CreateHashMap(stringstream &ss) { // 记录编号与下标的映射、课程名称、课程学分
    	string cName;
    	Number cNumber;
    	CourseInfo cInfo;
    	ss >> cNumber >> cInfo.courseName >> cInfo.credit;
    	courseInfo.push_back(cInfo);
    	hm[cNumber] = vertexNum++;					   // 将课程号与下标建立哈希映射,减少顺序检索带来的时间复杂度
    	CourseNode *cn = new CourseNode(cNumber);
    	courseNet.push_back(cn);
    	tailPoint.push_back(cn);
    }
    void CourseList::CreateAdjList(string buf, int index) {
    	vector<string> mark;
    	string str;
    	// 解析字符串
    	int len = buf.size(), c = 0, flag = 1;
    	if (buf[0] != 'C') {
    		flag = 0;
    	}
    	for (int i = 0;flag && i < len;i++) {
    		if (buf[i] != ',') {
    			str += buf[i];
    		}
    		else {
    			mark.push_back(str);
    			str.clear();
    		}
    	}
    	if (flag) {
    		mark.push_back(str);
    	}
    	// 根据 hm[courseNumber] 进行下标索引
    	int size = mark.size(), cnt = 0;
    	for (int i = 0;flag && i < size;i++) {
    		cnt++;
    		CourseNode * newNode = new CourseNode(courseNet[index]->courseNumber);
    		int n = hm[mark[i]];
    		tailPoint[n]->next = newNode;
    		tailPoint[n] = tailPoint[n]->next;
    	}
    	courseInfo[index].inDgree += cnt;
    }
    bool UserInterface::JudgeLogicError(int count) {   // 判断课程是否存在回路 
    	return bool(count != course.vertexNum);
    }
    void UserInterface::GetTopologicalOrder() {
    	stack<CourseNode *> st;
    	for (int i = 0;i < course.vertexNum;i++) {     // 将入度为 0 的点压入栈中
    		if (!course.courseInfo[i].inDgree)
    			st.push(course.courseNet[i]);
    	}
    	int cnt = 0;
    	while (!st.empty()) {                          // 拓扑的核心,也可用队列存储
    		CourseNode *p, *temp = st.top();		   // 若优化方案,考虑到先修课程并行学习,可以做多个辅助栈以达到模拟并行的目的 
    		st.pop();
    		topoOrder.push_back(temp->courseNumber);
    		p = temp->next;
    		while (p) {
    			int index = course.hm[p->courseNumber];
    			if (!(--course.courseInfo[index].inDgree)) {
    				st.push(course.courseNet[index]);
    			}
    			p = p->next;
    		}
    		cnt++;
    	}
    	if (JudgeLogicError(cnt)) {
    		cout << "There are logical errors in course information!";
    		system("pause");
    		exit(0);
    	}
    }
    char UserInterface::ShowOption() {
    	system("cls");
    	char ch;
    	cout << "    请选择操作:  " << endl;
    	cout << "1.显示全部课程信息" << endl;
    	cout << "2.显示学期课程安排" << endl;
    	cout << "3.退出自动排课系统" << endl;
    	cin >> ch;
    	return ch;
    }
    void UserInterface::UserOption() {
    	char op;
    	int flag = 1;
    	LoadingCourseInfo();
    	while (op = ShowOption()) {
    		switch (op)
    		{
    		case '1':
    			ShowCourseInfo();Sleep(5000);break;
    		case '2':
    			if (flag) {
    				GetTopologicalOrder();
    				flag = 0;
    			}
    			ShowTopoOrder();Sleep(10000);break;
    		case '3':
    			cout << "谢谢使用,再见!" << endl;
    			system("pause");exit(0);break;
    		default:
    			break;
    		}
    	}
    }
    void UserInterface::LoadingCourseInfo() {
    	ReadFromFile();
    }
    void UserInterface::ReadFromFile() {
    	const string fileName = "courseInfo.txt";
    	fstream fin;
    	try {
    		fin.open(fileName, ios::in | ios::out);
    		if (!fin)
    			throw "File Open Error!";
    	}
    	catch (const char *Warning)
    	{
    		cout << Warning << endl;
    		system("pause");
    		exit(0);
    	}
    	//成功打开文件
    	string line;
    	int flag = 0;
    	while (getline(fin, line))
    	{
    		if (!flag) {		                   	   // 跳过第一行(标题属性) 
    			flag = 1;
    			continue;
    		}
    		stringstream ss(line);
    		course.CreateHashMap(ss);
    	}
    	fin.clear();
    	fin.seekg(0);
    	// 再读一遍,此时根据课程依据的先序,创建邻接表
    	flag = 0;
    	int st = 0;
    	while (getline(fin, line))
    	{
    		if (!flag) {						       // 跳过第一行(标题属性) 
    			flag = 1;
    			continue;
    		}
    		string buf;
    		stringstream ss(line);
    		for (int j = 1;j <= 4;j++) ss >> buf;      // 吞掉前面3个字符串,只留下先修课程做解析
    		course.CreateAdjList(buf, st);
    		st++;
    	}
    	fin.close();
    }
    void UserInterface::ShowCourseInfo() {
    	//显示全部信息
    	for (int i = 0;i < course.vertexNum;i++) {
    		string name = course.courseNet[i]->courseNumber;
    		cout << course.hm[name] << ": " << name << " " << course.courseInfo[i].courseName << " ";
    		cout << course.courseInfo[i].credit << endl;;
    	}
    }
    void UserInterface::ShowTopoOrder() {
    	int verNum = course.vertexNum, size; 		   // verNum 和 Size 均为总共课程数量
    	int flag = 0;
    	size = verNum;
    	cout << "课程学习序列为:" << endl;
    	for (int i = 0;i < size;i++) {
    		int index = course.hm[topoOrder[i]];
    		cout << course.courseInfo[index].courseName << "(" << topoOrder[i] << ") ";
    		if (!((i + 1) % 5))
    			cout << endl;
    		if (--verNum)
    			cout << "→ ";
    	}
    	cout << endl;
    
    	// 增加学期数和每学期学分上限的约束 
    	int semester = 7, hasLearned = 0, ceiling = 9;
    	int curScore = 0, index = 0, t = 1;
    	for (int i = 0;i < size;i++) {
    		if (t) {
    			cout << "第 " << ++index << " 学期:" << endl;
    			t = 0;
    		}
    		int temp = course.courseInfo[course.hm[topoOrder[i]]].credit;
    		if ((hasLearned <= size - semester)) {
    			if (curScore <= ceiling - temp) {      // 预判 
    				cout << course.courseInfo[course.hm[topoOrder[i]]].courseName << " ";
    				hasLearned++;
    				curScore += temp;
    			}
    			else {							       // 如果不满足上面的约束条件,回退到上一次并清空状态,开始下一学期的排课 
    				cout << endl;
    				hasLearned--;
    				i--;
    				curScore = 0;
    				t = 1;
    			}
    		}
    		else {
    			cout << endl;
    			hasLearned--;
    			i--;
    			curScore = 0;
    			t = 1;
    
    		}
    	}
    	cout << endl;
    }
    
    展开全文
  • c语言数据结构课设

    2018-11-07 18:28:48
    该资源是基于数据结构的校园导航系统,使用,和链表相关知识
  • C语言 数据结构课设

    2010-08-16 22:47:39
    两个星期折腾出来的数据结构课设,包含有五种排序方法,二叉树,二叉排序书,哈夫曼,表达式求值。下载了的朋友如果有什么好的意见,请不吝赐教!
  • 的资源 用实现一些东西 很是有用 对于的各种调用都能判断
  • 这是数据结构课设 哈夫曼的c语言实现 大家可以借鉴一下
  • 形结构作为数据结构这门课中的一个重点知识,在实际生活的应用也是十分广阔的。就比如经常接触的Windows系统中文件就是用的形结构,因此用形结构来模拟Windows中的文件管理是十分必要的。该代码也是vs2017中...
  • 数据结构的课程设计,有课程设计说明书,还有源代码。如果觉得有用可以试试,但愿能帮到你。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 842
精华内容 336
关键字:

数据结构树课设

数据结构 订阅