《算法与数据结构考研试题精析》笔记(2) - 线性表

Published: by Creative Commons Licence

Tips

  • 注意细节！看清题目！
  • 在处理链表时，清楚是否有头结点！

Points

单链表中，增加一个头结点是为什么？简单来说(选择题)，是为了方便运算的实现；详细来说(简答题或者填空题)，如下回答：有头结点后，插入元素和删除元素的算法统一了，不再需要判断是否在第一个元素之前插入和删除第一个元素。另外，不论链表为空，链表指针不变。

静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

静态链表与动态链表(链表)相比，其缺点：有可能浪费较多空间。

【长度为n的顺序表】的相关题目要注意的问题：是移动次数还是平均移动次数？至于平均移动次数求均值就可以了。

对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为O(1)和O(n)。【青岛大学2000 五、1】【烟台大学2007 一、2】

线性表中的所有数据元素的数据类型必须相同。

顺序存储结构属于静态结构，链式结构属于动态结构。

静态结构和动态结构相关摘自此网页： （1）数据结构也叫信息结构,讨论的是数据的组织的问题.而我们常用的整型.浮点型等类型的数据,都属于静态数据,他们的存储空间在程序执行过程中不能加以改变,因此被称为静态数据结构。所以静态数据结构的特点是由系统分配固定大小的存储空间，以后在程序运行的过程中，存储空间的位置和容量都不会再改变。 （2）动态数据结构不确定总的数据存储量，而是为现有的每一个数据元素定义一个确定的初始大小的空间，若干个数据元素分配若干个同样大小的空间；当问题的数据量发生变化时，数据的存储空间的大小也发生变化。如果数据量增加，就重新向系统申请新的空间；如果数据量减少，就将现有的多余的空间归还给系统。

【换思想解决问题】如果仅仅为下面这种情况“指针p指向单链表的某个结点，在指针p所指结点之前插入s所指结点。其中结点结构为(data,next)”，正常思想是只有知道当前结点p的前继才可以往p结点之前插入结点；但是另外一种处理方式是“交换数据元素的data”，就是插在p的后头，然后将p和s所指结点的数据向交换，如此也可以达到预期目标。

根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成单链表和双链表；而又根据指针的连接方式，链表又可分为(动态)链表和静态链表。

顺序存储结构是通过结点物理上相邻表示元素之间的关系的；链式存储结构是通过结点指针表示元素之间的关系的。

循环单链表的最大优点：从任一结点出发都可访问到链表中每一个元素。

【如何描述算法的功能】先描述算法过程中的关键步骤，最后讲述算法的最终运行结果。