CSK.Blog--个人原创Weblog

这个学期的数据结构课终于告一段落了，虽然数构我高中就看过一些，但现在学好了还是觉得这是门比较复杂的学科。今天附上的就是这门课的每章的大作业。 虽然我不想对学校这门课作太多评价，感觉上的很不好，而且其实没有多少人是自己完成作业的（其实那应该是学校造成的）。但如果每次每道题目都能去做，尤其是那些打星号的题目也作的话，那的确能学到不少知识的。 我附上的文件是我的作业代码，当然我放上来的目的不是为了让大家抄袭，而且也不可能，因为关键代码我都留有个人信息。主要目的有这几个： 1.每次大作业对我都是个相当不好受的经历，每次都要花2-4天的时间去完成（当然我可以保证作业质量）。特别是最近刚完成的图那一章的作业更是令我痛苦。每次大作业其实已经不亚于编写Stereoic一半的工程量了。同时里面大部分题目我都尽力做了，除了AVL树和AOV网络求所有可能的拓扑序列这2道外。所以即使作业中仍有不足，我相信能给各位起到一些微弱的参考意义可已经足够了 2.我编写作业过程中尽力以符合工程强度的要求来书写代码，而不是简单的应付作业，所以其中每个组建，每个数据类型都可以立刻用于其他的实际应用中，同时可以保证运行的效率和健壮性。 这一套作业集是自成体系的，比如前面实现的双向链表，堆栈，将会在后面的使用中用到。 作业中已经提供的现成数据结构有： 双向链表，单链表，和他们的相关常用操作函数 多项式类，支持多项式乘法和加法 基于链表的队列和堆栈 基于数组的共享堆栈 带有父节点指针的二叉树 BST树 基于多重邻接表的无向图、基于十字链表的有向图 基于数组的并查集 二叉树的前序、中序、后序、广度优先遍历算法 图的广度、深度优先算法 图的KRUSKAL \ Dijkstra算法 有向图求解强连同分量的算法 以上的类型和相关算法在作业中是以单独的类形式封装的，同时以独立的头文件保存。所有代码采用C++模版。程序没有采用任何STL元素，同时支持异常处理。 正如我前面说的，实现数据结构并非是什么轻松的事，所以如果需要也可以采用我现成的代码来实现更高级的功能，而不需要花大力气去实现原始结构了。至于具体如何大家还是开代码吧。 同时程序中还附上一个自己写的将二叉树打印成文本形式的函数，这个在编写二叉树相关的程序是使相当直观的。比如下面就是函数直接显示的一颗BST的画面：

==================Asc Tree View===================
       H
      / \
   D       J
  / \       \
 A   F       K
  \
  B
================== End Of View ===================

好了不说废话了，附上一次作业程序的运行画面和下载地址: Data Structure Act 5 Demos Designed By CSK(www.csksoft.net) ---------------------------------------- Please Select Demos: [1].Get Strongly Spanning Graphs(Problem 1,2) [2].KRUSKAL algorithm Demo(Problem 1,3) [3].Dijkstra algorithm Demo(Problem 1,4) [4].DFS & BFS Demo(Problem 1,4) [0].Exit Load Demo Num: ============================= Act 1 Problem 2:Multiply two polynomials ============================= Would you like to use the default two polynomials?[Y/N]y the first default polynomial is +7x^2+3.5x^3+2x^4+2x^9 the second default polynomial is +2.3x^2+4.4x^3+1x^4+6x^10 请按任意键继续. . . polynomial1 * polynomial2 = +16.1x^4+38.85x^5+27x^6+12.3x^7+2x^8+4.6x^11+50.8x^1 2+23x^13+12x^14+12x^19 ---------------------------- Demo Finished 请按任意键继续. . . 我的实践作业下载： [url]ftp://FTP_visitor:visitor@ftp.csksoft.net/Public/Products/APP/DataStructProduct_BY_CSK.rar[/url] 原题下载（可能SJTU有版权..）： [url]ftp://FTP_visitor:visitor@ftp.csksoft.net/Public/Article/DataStruct_Instruction.rar[/url] 最后真心祝愿每一位将要考数构的朋友都能通过