回 帖 发 新 帖 刷新版面

主题:高手进!关于链表和算法复杂度的概念问题

刚开始自己学习数据结构,有很多地方不是很明白。想请高手指点一下。
第一关于链表的问题,我看书上说某某有表头结点的算法,按照这样的语句意思难道还有没有表头结点的链表吗?如果没有,那为什么需要存在表头结点,直接引用第一个元素不就好了吗,为什么还需要HEAD的存在,然后用表头指针指向第一元素,尤其是在环链中表尾元素完全可以直接指向第一元素,而此时的表头元素就是一个没有值的空壳无任何意义。
第二是关于建立链表的一些语句或者函数。
比如这个结构体
struct student
{ int num;
  float score;
  struct student *next;      /*这里的这个指针是按照student 结构体类型定义了这个指针 我不是很理解 这样嵌套 感觉象是形成了一个无限循环似的  */
};
第三个是关于算法复杂度 我不是很理解 那个概念很抽象 而且那个表达式我不是看的很明白 还有怎么去测试这个复杂度啊 是按照数学理解来算还是靠软件测试 影响这些的因素有哪些

希望高手给予帮助

回复列表 (共8个回复)

沙发

next 的类型是一个指针,在 win32 系统占 4 个字节.

板凳

第一个问题:
  有表头结点的好处,比如你要往链表头部插入一个结点,如果没有表头结点的话,插入后,要重新给表头赋值,因为表头因你的插入操作而改变了。而有头结点的话,就没有这个问题了,因为表头始终没变,这就统一了插入操作,而无需区分中间和头部的插入操作。

第二个问题:C里面的指针占用四个字节,next仅储存了下一个结点的地址,而不是下一个结点的内容,所以没有嵌套。

3 楼

楼上的解释很好 第一个问题我明白了 第二个问题我再看看书 理解一下 谁能回答一下第三个问题  这个也是关于以后工作时候的真正的实际意义啊

4 楼

一个比较简单的看复杂度的问题是就是看它的循环次数,现在刚学数据结构不需要太追求那个,关键是理解各个算法的具体作用,有些经典算法应该背下来,(当然是理解了再背),比如二叉树的三个遍历,LDR,DLR,LRD,
有些时间复杂度是用计算机算出来的,还用到高等数学的积分和微分的方法,不用太在意这个,反正就是简单的住要看循环次数的乘积就可以了,

5 楼

3。关于复杂度,可以这么理解(当然不是很准确):
假设算法的循环次数为f(n),那么复杂度O(n)的意思就是要求一个最简单形式的g(n),使得
lim f(n)
n->∞-- = a  (a为常数)
     g(n)

这个g(n)就是要求的O(n),即复杂度。
比如如果f(n)=3n^2 + 4n+3那么O(n)=g(n)=n^2

这个O(n)只是一个理论上的推导,要实际测试一个算法的效率就得统计该算法的运行所花时间,但这个时间必须与其他的算法对比才有实际意义。影响所花时间的因素很多,非算法因素有cpu,内存,操作系统,编译器,编程语言等等;算法相关因素有数据规模,数据的输入次序等等。

6 楼

偶也明白了,谢谢大家

7 楼

亲娘哩,你过了一年才看到回复?!

8 楼

[quote]亲娘哩,你过了一年才看到回复?![/quote]

...你一说我才刚发现

我来回复

您尚未登录,请登录后再回复。点此登录或注册