考试网 >> IT认证 >> 水平 >> 软件指导 >> 线性表串讲+复习要点

发布时间：2006-06-28 04:47     点击：

要求达到< 识记 >层次的内容有:线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。

要求达到< 综合应用 >层次的内容有：顺序表的含义及特点，顺序表上的插入、删除操作及其平均时间性能分析，解决简单应用问题。

链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别； 单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度 。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。

要求达到< 领会 >层次的内容就是顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。

线性表 的 逻辑结构特征 是很容易理解的，如其名，它的逻辑结构特征就好象是一条线，上面打了一个个结，很形象的，如果这条线上面有结，那么它就是非空表，只能有一个 开始结点 ，有且只能有一个 终端结点 ，其它的结前后所相邻的也只能是一个结点( 直接前趋 和 直接后继 )。

关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。

线性表 的 逻辑结构 和 存储结构 之间的关系。在计算机中，如何把线性表的结点存放到存储单元中，就有许多方法，最简单的方法就是 按顺序存储 。就是按线性表的逻辑结构次序依次存放在一组地址连续的存储单元中。 在存储单元中的各元素的物理位置和逻辑结构中各结点相邻关系是一致的 。

在顺序表中实现的基本运算主要讨论了 插入 和 删除 两种运算。相关的算法我们通过练习掌握。对于顺序表的插入和删除运算，其平均时间复杂度均为 O(n) 。

线性表的 链式存储结构 。它与顺序表不同， 链表 是用一组 任意的存储单元 来存放线性表的结点，这组存储单元可以分布在内存中任何位置上。因此， 链表中结点的逻辑次序和物理次序不一定相同 。所以为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还存储了其后继结点的地址信息(即指针或链)。这 两部分信息组成链表中的结点结构 。

一个单链表由头指针的名字来命名。

对于单链表，其操作运算主要有 建立单链表 (头插法、尾插法和 在链表开始结点前附加一个 头结点 的算法)、 查找 (按序号和按值)、 插入 运算、 删除 运算等。以上各运算的平均时间复杂度均为 O(n) .其主要时间是耗费在查找操作上。

发表评论： 匿名发表 用户名: 查看评论

您将承担一切因您的行为、言论而直接或间接导致的民事或刑事法律责任 留言板管理人员有权保留或删除其管辖留言中的任意内容 本站提醒：不要进行人身攻击。谢谢配合。