多项式的类定义

Struct Term{

int coef;

int exp;

Term(int c,int e) {coef=c; exp=e;}

};

class Polynomial{

friend Polynomial operator +( Polynomial &,Polynomial &);

private:

List<Term> poly;

};

AD:乙醇气体检测仪、探测器、报警器

• 单链表( Singly Linked List)
• 循环链表
• 多项式及其相加
• 双向链表
• 稀疏矩阵
• C++中的虚函数和动态联编

利用数组或顺序方式来组织数据结构,其优点是存储利用率高,存取速度快.但是,对于数据元素个数动态增长的情形,由于数组的元素个数不能自由扩充(除动态数组外),一旦空间用完就不能再向里加入新的元素,否则就会导致系统停工.

单链表(Singly Linked List)

• 单链表的结构
• 单链表的类定义
• 单链表的插入与删除
• 带表头结点的单链表
• 用模板定义的单链表类
• 单链表的游标类
• 静态链表

循环链表的类定义

是另一种形式的表示线性聚集的链表,它的结点结构与单链表相同,与单链表不同的是链表中表尾结点的LINK域不是0(NULL),而是存放了一个指向链表开始结点的指针,这样,只要知道表中任何一个结点的地址,就能遍历表中其它任一结点.

在循环链表中检查指针Current 是否达到链表的链尾时,不是判断是否Current->link=NULL,而是判断是否Current->link==first.

用循环链表求解约瑟夫问题

• 作为抽象数据类型的数组
• 在C++中数组的定义和初始化
• 作为抽象数据类型的数组
• 数组的顺序存储方式
• 顺序表
• 顺序表的查找,插入和删除
• 作为抽象数据类型,使用顺序表的事例
• 多项式抽象数据类型
• 多项式的表示
• 多项式的相加
• 稀疏矩阵
• 稀疏矩阵的抽象数据类型
• 稀疏矩阵的压缩表示
• 稀疏矩阵的转置
• 稀疏矩阵的相乘
• 字符串
• 字符串抽象数据类型和类定义
• 字符串操作的实现
• 字符串的模式匹配
• 模式匹配的改进算法(KMP算法)

关于K的确定方法,Knuth等人发现,对于不同的j,k的取值不同,它仅依赖于模式P本身前j个字符的构成,与目标无关.

因此,可以用一个失效函数(failure function)来确定,当模式P中第j个字符与目标S中相应字符失配时,模式P中应当由哪个字符(设为第K个)与目标中刚失配的字符对齐继续进行比较.

设模式P=P0P1P2...P(m-2)P(m-1),则它的失效函数f(j)定义如下:

f(j)=K, 当0<=K<J,且使得P0P1..Pk=P(j-K)P(j-K+1)...Pj的最大整数

-1, 其它情况

我们称P0P1..PK为串P0P1P2...P(j-1)的前缀子串,P(j-k)P(j-k+1)...Pj为串P0P1P2...P(j-1)Pj的后缀子串.

第一章习题:课本共9道题,习题集上共21道.

课本第1道:

什么是数据?它与信息是什么关系?

答:数据是描述客观事物的数,字符,以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合.是信息的载体.

在计算机中,有时候信息不能直接被处理,所以常被转换成数据的形式进行处理.

2.什么是数据结构?有关数据结构的讨论涉及哪三个方面?

答:数据结构是指数据元素以及数据元素之间的相互关系所组成的集合.

讨论涉及:逻辑结构,存储结构,以及在数据结构上的运算,也即施加于该数据结构上的操作,算法.

3.数据的逻辑结构分为线性结构和非线性结构两大类.线性结构包括数组、链表、栈，队列、优先栈队列等；非线性结构包括树、图等、这两类结构各自的特点是什么？

答：线性结构的特点是：在结构中所有的数据成员都处于一个序列中，有且仅有一个开始成员和一个终端成员，并且所有数据成员都最多有一个直接前驱和一个直接后继。例如：线性表就是典型的线性结构。

非线性结构的特点是：一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如：树、图或网络等都是典型的非线性结构。

４。什么是抽象数据类型？试用Ｃ＋＋的类声明定义“复数”的抽象数据类型。要求：

（１）在复数内部用浮点数定义它的实部和虚部。

(２）实现３个构造函数；缺省的构造函数没有参数；第２个构造函数将双精度浮点数赋给复数的实部，虚部置为０；第３个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。

（３）定义获取和修改复数的实部和虚部，以及＋，－，＊，／等运算的成员函数。

（４）定义重载的流函数来输出一个复数。

template <class Type>

class complex{

private:

double Re,Im;

public:

complex(){RE=IM=0;}

complex(double r) {Re=r;Im=0;}

complex(double r,double i) {Re=r;Im=i;}

double getReal(){return Re;}

double getImag(){return Im;}

void setReal(double r) { Re=r;}

void setImag(double i){Im=i;}

complex operator=(complex ob) {Re=ob.re;Im=ob.Im;}

complex operator+(complex ob);

complex operator-(complex ob);

complex operator *(complex ob);

complex operator /(complex ob);

friend ostream &operator<<(ostream &os.complex&c);

};

[此贴子已经被作者于2004-8-18 17:05:22编辑过]

6671605(Mars) 16:29:55
喂，赌徒，那个是书上原题，你可以查课后练习题有的。
6671605(Mars) 16:30:02
就是书上的题目了。
11584467(冷面铁手) 16:33:21
有考自动化的吗？
329821486(赌徒) 16:33:59
呵,谢了.这道我做出来了.
后面的还不会.第二道题(图)你会么?
329821486(赌徒) 16:34:15
我现在一天学习八小时,你呢?
6671605(Mars) 16:34:22
这张卷子我研究过了。基本都会吧！
329821486(赌徒) 16:34:33
啊,真是太好了.!!

6671605(Mars) 16:35:19
人家研究生有建议的，一天学习６小时，否则效率难以保证。
6671605(Mars) 16:35:37
那个清华考上的。家伙说的。
他考了４００分吧！
6671605(Mars) 16:35:51
事实一天坚持１０小时确实很难。
6671605(Mars) 16:36:04
但是答案我都没什么把握了。
329821486(赌徒) 16:36:27
六小时我可不行.
329821486(赌徒) 16:36:45
觉得太少了!
6671605(Mars) 16:37:20
已经足够了。其余的时间锻炼。或者别的了。
329821486(赌徒) 16:37:44
complex operator=(complex ob) {Re=ob.re;Im=ob.Im;}
329821486(赌徒) 16:37:55
请帮我分析一下这个语句的意思.
6671605(Mars) 16:38:07
恩。第二题，首先现在只考Ｃ＋＋，第二ＰＡＣＡＬ　我也只能看懂程序而已。只是一个欧拉定理了。
329821486(赌徒) 16:38:11
那这六小时如何安排? 晚上?下午?
329821486(赌徒) 16:38:37
几点到几点?各门课如何安排?
6671605(Mars) 16:38:44
离散数学书上有写。。这个我们现在也不考了。
卷子只有０３，０４有价值的。以前的都是计算机改革之前的。
6671605(Mars) 16:38:51
这个看个人了
19341774(220伏-2004) 16:39:13
我现在才开始复习，各位有没有什么建议，谢谢
6671605(Mars) 16:39:16
条件有个每个点的度数为偶数了。
329821486(赌徒) 16:39:25
也是.可是04年的题好象找不到.
6671605(Mars) 16:39:28
这个每个人都不一样了。
6671605(Mars) 16:39:44
当然啊！！》我也郁闷呢！搞的现在只能研究０３的。
329821486(赌徒) 16:39:45
329821486(赌徒) 16:37:44
complex operator=(complex ob) {Re=ob.re;Im=ob.Im;}
329821486(赌徒) 16:37:55
请帮我分析一下这个语句的意思.  
329821486(赌徒) 16:40:57
能够研究03年的也不错了。
6671605(Mars) 16:42:04
就是运算符重载啊！
6671605(Mars) 16:43:01
就是以后你可以直接用等号表示复数相等啊！
6671605(Mars) 16:43:42
Ｃ＋＋，运算符重载。随便哪本书都有的。。。
329821486(赌徒) 16:44:21
这里它倒是说复数赋值。
但是这个ＯＢ，指的是一个形式复数对象，对不？
329821486(赌徒) 16:44:45
复数对象的形式参数，对不？
6671605(Mars) 16:44:50
对。
329821486(赌徒) 16:45:09
那为什么前面不用“引用”符呢？
6671605(Mars) 16:46:15
好象用了也可以的。不过我原来写程序的　时候很少用引用的。
329821486(赌徒) 16:46:28
引用与不引用看什么情况而定？

6671605(Mars) 16:47:01
引用的话，好象都不能算形参了。。
6671605(Mars) 16:47:08
会直接改变的。
6671605(Mars) 16:47:19
所以这儿不用比较好了。
329821486(赌徒) 16:47:56
我知道它产生的不同结果
但是为什么在有些地方有，而有些地方没有，我就不明白。
你做了殷人昆的第一章的习题１－４了吗？
6671605(Mars) 16:48:10
全部做了。
329821486(赌徒) 16:49:02
那在重载＋，－的时候，都用了引用类型的方式，将形参声明为引用类型，而在重载＊与／的时候，就没有使用？
6671605(Mars) 16:49:06
enbo的地址是多少？那儿数学问题的解答如何？
329821486(赌徒) 16:49:35
不知道了。我的数学也是急。

76583169(我就是我) 14:24:36 ｔｍｄ五门　害怕了 你在北航？ 329821486(赌徒) 14:24:54 不在. 76583169(我就是我) 14:25:00 在哪？ 329821486(赌徒) 14:25:43 不在北京 76583169(我就是我) 14:25:51 我也是 329821486(赌徒) 14:26:07 郁闷,你操作系统复习得如何了? 76583169(我就是我) 14:26:21 我还没有怎么复习 329821486(赌徒) 14:26:44 什么是数据?它与信息是什么关系? (你能不能帮我用很简单的话来说.我怎么理不清楚.) 329821486(赌徒) 14:27:00 那你数学复习得如何?我都快急死了,听你口气倒是很平静. 76583169(我就是我) 14:29:41 我还在上班 数学没有问题 英语偏差 政治无恙 专业课危机 80860738( 川中清竹) 14:30:10 你们哈哈 329821486(赌徒) 14:30:14 那真太好了.数学课本你做完一遍了吗?没想还遇到数学高手了 329821486(赌徒) 14:30:55 我的英语没有问题,数学偏差,专业无恙,政治危机. 我们正好可以互相讨论. 76583169(我就是我) 14:32:17 数据是客观事物的符号表示 21435302(查无此人) 14:32:33 太好了 我是数学有问题,英语偏差,专业匮乏,政治危机 正好可以向你们请教 76583169(我就是我) 14:32:35 信息怎比较大　 329821486(赌徒) 14:33:01 哈哈,互相学习 329821486(赌徒) 14:33:11 大家谁有数学课本这里? 329821486(赌徒) 14:33:55 谁能说说圆心在(a,0)半径为a的圆的参数方程或极坐标方程? 329821486(赌徒) 14:34:22 这个查无此人听起来太谦虚了 21435302(查无此人) 14:34:40 是事实..... 21435302(查无此人) 14:35:26 甚至奥运开始过后就没复习 天天都在看奥运....... 329821486(赌徒) 14:36:21 了不起. 21435302(查无此人) 14:37:05 唉.... 没办法 看来至少要等男篮打完才可能静得下来 329821486(赌徒) 14:37:20 能考上就行. 76583169(我就是我) 14:47:55 赌徒还在？ 329821486(赌徒) 14:48:08 在. 329821486(赌徒) 14:48:17 做出来了? 76583169(我就是我) 14:49:45 我现在只能这样告诉你 但树稿相等时　莫认为１小题所言 所以这样做出来 第一小题于第二小提答案一样！ 329821486(赌徒) 14:50:17 不一样的. 329821486(赌徒) 14:50:33 答案很不同的. 76583169(我就是我) 14:50:47 ｉｓ　ｔｈｅｒｅ　ａ　ｋｅｙ　？ 329821486(赌徒) 14:50:59 什么是KEY? 329821486(赌徒) 14:51:15 你给我说说你理解如何第二题的题意吧? 76583169(我就是我) 14:51:16 有答案，吗？ 329821486(赌徒) 14:51:23 答案一样.呵,我看错了. 329821486(赌徒) 14:51:38 是第三题与第一题完全不一样.第一题与第二题答案确实完全一样. 76583169(我就是我) 14:51:51 集合是用　树来做的 329821486(赌徒) 14:51:54 你这里如何说它的树高是一样的呢? 76583169(我就是我) 14:52:39 肯定的拉　第三销题与第一体肯定不一样 76583169(我就是我) 14:52:59 题目已经很明白　以他为根 329821486(赌徒) 14:53:03 第二题:按I和J为根,是指什么意思? 329821486(赌徒) 14:53:11 以谁为根? 76583169(我就是我) 14:53:19 ｉ，ｊ 76583169(我就是我) 14:53:31 分开来理解 329821486(赌徒) 14:53:37 哪个是I,哪个是J?到底以谁为根? 76583169(我就是我) 14:53:47 各自为根　然后比较 329821486(赌徒) 14:53:49 就是以I为根,和以J为根吗? 329821486(赌徒) 14:55:37 就是说比如UNION(1,2) 先以1为根画一棵树 然后以2为根画一棵树 用了题中所给出的所有UNION画完树以后,比较其两树?树高者为树小者的双亲?? 76583169(我就是我) 14:55:45 比如ｕｎｉｏｎ　（１，２） 此时　１，２　都是单节点 所以其树高肯定相等 那就是１　是２　的双亲节点 329821486(赌徒) 14:55:48 题目我是这样理解的.但是我又不知道是否合理. 329821486(赌徒) 14:56:15 是这样,那你给我举个高度不等的情况? 76583169(我就是我) 14:57:45 如果不这样理解 你倒回来　２　是１　的父亲节点　那就做不出来了

在此题中　都是　相等的情况　所以会与第一小题答案一样 329821486(赌徒) 14:58:24 OK,我有点听明白了,你能否给我举个高度不同的情况? 76583169(我就是我) 14:59:04 你说是吗？ 你画两棵树不就明白 76583169(我就是我) 14:59:17 你有答案给我一份好吗？ 329821486(赌徒) 14:59:49 这个是因为在课本上也有一道题.在相应的习题集上有答案.所以我在习题集上看到它所画出来的图了,是一样的图,但是没有过程. 329821486(赌徒) 15:00:25 我挺看不明白题意的. 329821486(赌徒) 15:00:59 那请你再给我看看第三步的题目的意思 76583169(我就是我) 15:01:17 噢 但两棵树树高不一样时 就很明显 真要举例子　你打开严的书 随便找两棵树给我我告诉你 329821486(赌徒) 15:01:54 我是说在UNION的情况下不同的高度的树 76583169(我就是我) 15:02:26 [贴图] 第二大题 有回路的　前提是什么 我忘了 76583169(我就是我) 15:03:26 UNION　之前 肯定存在两棵树（单节点也算） 329821486(赌徒) 15:04:13 是么?我看看 76583169(我就是我) 15:04:21 我没有离散书 虽然北航不考图论 但这问题是很简单的 329821486(赌徒) 15:05:17 第二题连个图也没有啊 329821486(赌徒) 15:05:33 好,严的书我打开了,你说吧 329821486(赌徒) 15:06:48 北航的数据结构中不考图? 76583169(我就是我) 15:06:59 ｐａｇｅ　１３８　６．１７ 329821486(赌徒) 15:07:16 晕,你是说习题集? 76583169(我就是我) 15:07:22 不是是北航的离散不考图 76583169(我就是我) 15:07:31 不是 76583169(我就是我) 15:07:33 书 76583169(我就是我) 15:07:44 是书 76583169(我就是我) 15:07:58 找到没有 329821486(赌徒) 15:08:00 C语言版? 76583169(我就是我) 15:08:06 市的 329821486(赌徒) 15:08:14 找到了 76583169(我就是我) 15:08:40 坐上角的　三棵树 329821486(赌徒) 15:08:48 是. 329821486(赌徒) 15:09:24 这个与UNION有关系吗? 76583169(我就是我) 15:09:51 此时按第二种方法 ｕｎｉｏｎ（Ａ，Ｇ）；那么 Ｇ就是Ａ的父亲 329821486(赌徒) 15:10:26 对.可是在书上,所有的UNION里面的那些树,不都是只有一层吗? 76583169(我就是我) 15:11:20 怎么回呢？每一次ｕｎｉｏｎ都加了一个节点 76583169(我就是我) 15:11:47 有可能生成一层 329821486(赌徒) 15:11:50 意思是说:在这里,以I或者J为根吗?至于每次操作中,到底以谁为根,看情况而定?还是什么意思? 76583169(我就是我) 15:12:01 对呀！

329821486(赌徒) 15:12:20 那为什么不用(或)字,而用(和)字,这个如何理解呀?? 76583169(我就是我) 15:12:43 同时 当然用和 76583169(我就是我) 15:13:02 好了 解决了？ 329821486(赌徒) 15:13:11 就是每一次UNION(I,J),到底以谁为根,

没有,为什么又是同时了?? 329821486(赌徒) 15:13:23 为什么又是"同时"了? 329821486(赌徒) 15:13:39 我得先谢你一次 76583169(我就是我) 15:13:46 你是不是在钻牛角尖 329821486(赌徒) 15:14:15 我确实是在钻牛角尖吧,可是这题目的字面意思我无法确切理解呀. 76583169(我就是我) 15:15:30 UNION(I,J)　中的ｉ，ｊ是，指代 但一个UNION(I,J)　出现时　ｉ，ｊ同时存在 同时找以自己为根的树高 329821486(赌徒) 15:16:13 去哪里找? 329821486(赌徒) 15:16:32 76583169(我就是我) 15:16:39 此前， 集合是一步一步建立起来的 329821486(赌徒) 15:16:53 好,我具体地做一遍,谢了. 76583169(我就是我) 15:17:13 UNION(I,J)　的同时　也就是建立 76583169(我就是我) 15:17:23 你身边有离散书吗？ 329821486(赌徒) 15:17:34 你要问什么问题,离散书没有, 76583169(我就是我) 15:18:47 就是第二大题 有一个定理 有回路的要求好像是 定点数与边数的要求 329821486(赌徒) 15:19:28 你还真有心情做这一份题嘛,那太好了,一道道看一下 329821486(赌徒) 15:24:05 唉,你说这个问题有解的条件是什么? 连图也没有一个啊,你如何做? 76583169(我就是我) 15:24:27 我只问定理 329821486(赌徒) 15:26:37 N个顶点的边通网络没有回路的条件是有N个顶点,N-1条边吧? 329821486(赌徒) 15:26:50 最多N-1条边 329821486(赌徒) 15:28:26 对不对?? 76583169(我就是我) 15:34:20 是的 但不是这样的 在离散树立有很好地解释 好像没那么简单 那要是我这ｎ各点形成了树 不就不对了吗？ 329821486(赌徒) 15:35:37 N个点形成了树有什么不对的呢,不是一样不能超过N-1条吗? 76583169(我就是我) 15:36:32 那还是不能符合要求 只是符合了连通． 没有成环（回路） 329821486(赌徒) 15:37:13 你是说要让它成环?? 329821486(赌徒) 15:37:23 形成回路的条件? 329821486(赌徒) 15:37:33 我说成了不形成回路的条件了. 76583169(我就是我) 15:37:52 要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地 这个要求亚 329821486(赌徒) 15:40:11 每一对结点度数之和大于等于N,则有回路. 76583169(我就是我) 15:40:44 每一对结点？ 329821486(赌徒) 15:41:04 是呀,这个题还有些难.那这里图也没有画出来,如何操作 76583169(我就是我) 15:41:04 怎么说？ 76583169(我就是我) 15:41:13 那就算了 329821486(赌徒) 15:41:34 每一对:就是任何两个 329821486(赌徒) 15:42:12 第一题我也做出来了. 就是第二题还不知道如何解 329821486(赌徒) 15:43:05 二、设在4地（A,B,C,D）之间架设有6座桥,如图所示:

要求从某一地出发,经过每座桥恰巧一次,最后仍回到原地 (1) 试就以上图形说明:此问题有解的条件是什么? (5分) (2) 设图中的顶点数为n,试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法,找出满足要求的一条回路. (10分) 329821486(赌徒) 15:43:14 好好看一下哈 329821486(赌徒) 15:44:59 你还有没有在看这道题啊? 76583169(我就是我) 15:46:28 在 329821486(赌徒) 15:47:00 第一小步有解的条件也就是有回路存在的条件了,对否? 76583169(我就是我) 15:47:26 我是这样理解的 329821486(赌徒) 15:49:01 这样理解是对的.殷人昆的书你看过一遍吗?我看你对这些题很熟悉的,你的数据结构基础很不错啊. 76583169(我就是我) 15:49:43 看了一半 后来不考清华了 就不看了 329821486(赌徒) 15:52:57 为什么不考了 329821486(赌徒) 15:53:21 考北航不是还要换书? 76583169(我就是我) 15:53:39 我没买 329821486(赌徒) 15:53:54 那你用什么书? 76583169(我就是我) 15:54:00 严 329821486(赌徒) 15:54:08 数据结构都不同,还有要考组合什么的啊 76583169(我就是我) 15:54:51 都是比较 是的 没有 你有北航考钢吗？ 那里没说 329821486(赌徒) 15:55:36 北航考纲好象在2002年还是什么时候曾经有过一个,我忘了在哪儿看到它了 329821486(赌徒) 15:55:50 现在考试科目不同了,大纲也应该变了啊 329821486(赌徒) 15:56:02 我看到他们流传的那个就是前几年的了 76583169(我就是我) 15:56:18 那三科不变 另外的还没出来 329821486(赌徒) 15:56:35 对了.这道题应该看成是一个无向图了吧? 那四个地方有三座桥就可以通了啊 329821486(赌徒) 15:56:44 不变的三科你有大纲了?? 76583169(我就是我) 15:57:02 有吧！ 329821486(赌徒) 15:57:26 有就OK啊.这道题的范畴北航应该是不会考的了? 76583169(我就是我) 15:58:11 因为很简单 靠不考都无所谓 只是 但做课外 329821486(赌徒) 15:58:46 很简单?? 329821486(赌徒) 15:59:00 什么东西很简单?你很吓人

#ff0066

6.什么是算法?算法的5个特性是什么?试根据这些解释算法与程序的区别.

答:算法:为解决某一特定任务而规定的一个指令序列.

五个特性:有输入,有输出,确定性,有穷性,有效性

算法和程序不同,程序可以不满足"有穷性"

[此贴子已经被作者于2004-8-18 18:26:24编辑过]