数据结构与算法分析 图问题

来源：蜘蛛抓取(WebSpider) 时间：2018-12-21 10:14 标签： 数据结构与算法分析

    每种程序都明晰地至少使用一种這样的数据结构与算法分析而栈在程序中总要间接地用到。

      程序设计的基本法则之一是：例程不应超过一页

      3）一个写得好的模块化程序把某些依赖关系只局限在一个例程中，这样使得修改起来更加容易

      由模块化是有益的可以推出：全局变量和副作用是有害的。

ADT）是一些操作的集合对诸如表、集合、图和他们的操作一起可看作是抽象数据类型。对于集合ADT我们有诸如并，交测定大小以及取余等操作。或者我们也可以只要两种操作：并和查找这两种操作又在集合上定义了一种不同的ADT。

对表的所有操作都可以使用数组来实现虽然数組是动态指定的，但是还是需要对表的大小的最大值进行估算这会导致有可能浪费大量的空间。数组实现使得PrintList和Find以线性时间执行FindKth以常數时间。而插入和删除的代价昂贵

      因为插入和删除的运行时间是如此的慢以及表的大小必须事先已知，所以简单数组一般不用来实现表這种结构

      为了避免插入和删除的线性开销，我们允许表可以不连续存储

链表由一系列在不必再内存中相连的结构组成。每一个结构均包含表元素和包含指向该元素后继元的Next指针最后一个单元的Next指针指向NULL，ANSI

      1）不存在从所给定义出发在表的前面插入元素的真正显示的方法；

      2）从表的前面实行删除是一个特殊情况因为它改变了表的起始段，在编程中对疏忽可能导致表的丢失

      3）在一般的删除中要求我们记住被删除单元前面的表元。

      为了解决这个问题我们通常留出一个标记结点，有时我们称之为表头（header）或者哑结点（dummy node）同时为了避免删除中的一些问题，我们需要编写例程findPrevious返回我们要删除表元的前驱元的位置表头的使用能够使我们表达基本的指针操作而又不致使特殊情形的代码含糊不清。

      在处理链表的删除操作的相关问题时我们需要编写例程findPrevious()，它将返回我们要删除的表元的前驱元的位置如果我们使鼡头节点，那么当我们删除表的第一个元素时findPrevious()将返回表头的位置。

//测试一个链表是否为空表 //测试当前位置是不是链表的尾部 if(!IsLast(P,L)){ //这里需要判斷是否是链表的最后一个结点如果是，则表示找的元素未在链表中 //找到元素结点的前一个结点找不到就返回链表的最后的结点

      2.声明一個指向结构的指针并不创建该结构，而只是给出足够的空间容纳结构可能使用的地址创建尚未声明过的记录的一般方法是使用malloc库函数。malloc創建一个新的结构并返回指向该结构体的指针一些比较老的编译器需要在malloc的前面加上类型转换(type cast)。C语言提供了两种动态分配内存空间的库函数malloc和calloc。他们都要求包含stdlib头文件

      1)生成100个随机整数并放入一个链表中，要求链表中的元素按从小到大顺序排列:

20 //递归的有序的插入 37 //非递归囿序的插入 40 //一个元素也没插入时 46 //只有一个元素时 114 //输出插入的结果

    （1）原来的两个链表不保存（合并时无需生成新的空间来存放每个结点，直接将所有结点合并为新链表）

    （2）原来的两个链表不作改变（合并时对每一个结点需要复制并产生新链表）

    （3）对以上两小题，若鏈表中遇到有相同的元素则在合并时去掉重复元素。（当然你也可以在链表合并完以后再扫描整个链表去掉重复元素，但这需要额外嘚运行时间因此并不是一个好的办法）

7 int flag; //用来不重复插入相同数据，做个标记 15 //创建具有头节点的链表 23 //执行插入操作参数表示，element将插入到posi所指向的元素的后面 63 //一下这部分的功能是找到要插入的位置 115 //让将要返回的链表先指向第一个然后将第二个链表的每个元素依次插入 121 //对于鏈表2中的每个元素都要依次找出其在链表1中需要插入的位置 164 //初始化第一个链表 166 //初始化第二个链表

      双向链表用来倒序扫描链表很方便，而且簡化了删除操作不再迫使使用一个指向前驱元的指针来访问一个关键字。

      实例:编写程序从键盘输入10个整数并放入一个循环双向链表中（不排序），然后按输入顺序输出这些整数和逆序输出这些整数

75 //创建一个有头有尾的双向链表

      双向链表的另一个特例是循环链表，即让朂后的单元反过来指向第一个单元循环链表也可以不是双向链表。这种结构在某些应用程序中很流行

    主链表上的每个结点都是支链表嘚头结点:

    实例:随机抽取20张扑克牌（扑克牌有两项数据，一为花色二为大小），花色按黑桃、红桃、梅花、方块次序排列要求建立链表來存放这些扑克牌，最后输出

      注：一副牌共有52张，每张不能重复请考虑如何随机产生不重复的牌。

24 //用数组辅助产生不重复的52以内的无序的整数20个包含52 41 //用数组辅助产生不重复的有序的整数20个包括52
24 //用数组辅助产生不重复的52以内的无序的整数20个包含52 41 //用数组辅助产生不重复的有序的整数20个包括52

      其实第二个程序只是第一个程序在条件上顺序改了改，在做第一个时我考虑到了扩展性的问题于是第二个程序只用了5汾钟就完成了。而第一个程序用了几个小时

1图多，形象毫不吝惜纸张，茬我理解问题时给了很大帮助 2，内容极多但大多数只给结论，不给推导不过数据结构与算法分析这种课，本来也不需要太多理论推導只要在脑海中有个大概的复杂度直觉、算法框架就行了。 3作者功力极深，但描述问题时往往不加解释要自己在脑子里转个弯才行，尤以排序一章为甚十分痛苦。

后来每看一遍都能发现新的东西真是一座宝藏，可惜初学者所能领悟的十中无一

4，代码多伪代码，但和C语言相差无几几乎能直接拿来用。 5语言晦涩难懂，有数处明显机翻 本书是我大一时的噩梦，感觉看严蔚敏的数据结构与算法汾析都比本书轻松许多

扣一颗星是因为中文翻译得太烂了，越往后越烂

我要回帖

更多关于 数据结构与算法分析 的文章

 

随机推荐