第二章 线性表

　　线性表是一种最简单、最常见的数据结构。

　　一、本章总述

　　本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现。

　　线性表是一种最简单、最常见的数据结构。线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

　　二、本章重点

　　熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。

　　三、本章难点

　　使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。

　　四、本章知识点

　　1、线性表的逻辑结构的基本特征

　　图2-1 线性表

　　线性结构是一个数据元素的有序(次序)集

　　1).集合中必存在唯一的一个“第一元素”；

　　2).集合中必存在唯一的一个“最后元素”

　　3).除最后元素之外，均有唯一的后继；

　　4).除第一元素之外，均有唯一的前驱。

　　2、线性表的顺序存储实现

　　顺序表是线性表的顺序存储结构。用一组地址连续的存储单元依次存储线性表的元素。

　　顺序表特点：

　　逻辑顺序与物理顺序一致

　　属随机存取的存储结构，即存取每个元素所花时间相等

　　假设线性表中每个元素需占用c个存储单元，计算结点存储地址公式：

　　LOC(ai+1)=LOC(ai)+c (1)

　　LOC(ai)=LOC(a1)+(i-1)*c (2)

　　顺序表上实现基本运算及时间复杂度分析。

　　1)插入算法：

　　假设在第 i 个元素之前插入的概率为 pi，则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

　　若假定在线性表中任何一个位置上进行插入的概率都相等，则移动元素的期望值为：

　　插入算法的平均时间复杂性为 ，平均时间复杂性量级为O(n)。

　　2)删除算法：

　　假设删除第 i 个元素的概率为qi , 则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：

　　若假定在线性表中任何一个位置上进行删除的概率都是相等的，则移动元素的期望值为：

　　删除算法的平均时间复杂性为

　　3、线性表的链式存储实现

　　链接实现线性表，可以克服顺序表的缺点。线性表的常见链式存储结构有：单链表、循环链表、双链表。

　　1)单链表

　　用一组地址任意的存储单元存放线性表中的数据元素。

　　元素(数据元素的映象)+ 指针(指示后继元素存储位置的) = 结点

　　链式存储特点：

　　 逻辑顺序与物理顺序有可能不一致

　　 属顺序存取的存储结构，即存取每个数据元素所花费的时间不相等

　　几种运算在单链表上的实现，包括：建立单链表、查找、插入、删除等。

　　2)循环链表

　　表中最后一个结点的指针域指向头结点，链表形成一个环。

　　特点：从表中任何一个结点出发可扫描整个链表中的所有结点。

　　3)双链表

　　特点: 每个结点有两个指针域,克服单链表的单向性

　　注意：“插入”、“删除”操作，与单链表有很大不同。需要同时修改两个方向上的指针。

　　4、顺序表和链表的比较

　　空间性能比较、时间性能比较。

　　顺序存储结构：

　　优点：存储密度大、简单。数据元素的地址可以通过公式计算。

　　缺点：插入、删除操作效率低，存储空间需要按最大需求事先分配，且要求一片连续的存储空间，容易造成浪费。

　　链式存储结构：

　　优点：存储空间按需分配；插入、删除操作效率高。

　　缺点：链表中的结点需要存储指针，构造本身比顺序存储结构大。

　　时间复杂性量级

　　定位运算，顺序表和单链表,均为 O(n)

　　读表元：顺序表-O(1) (随机存取);单链表-O(n)

　　链入、删除：顺序表-0(n); 单链表-O(1) (插入、删除方便)

　　五、相关考题

　　本章将可能有算法题出现。

　　2006.01

　　三、解答题

　　28.当将两个长度均为n的有序表A=(a1，a2，…，an)与B=(b1，b2，…，bn)(ai≠bj,1≤i,j≤n)归并为一个有序表C=(c1, c2,…,c2n)时，所需进行的元素比较次数最少可达n,最多可达2n-1。

　　(1)假设有序表C=(2，4，5，6，7，9)，试举出两组A与B的例子，使它们在归并过程中进行的元素比较次数分别达到最少和最多；

　　(2)写出一般情况下，使归并所需进行的元素比较次数分别达到最少和最多时，A与B中的元素应满足的条件。

　　算法阅读：

　　30.已知head为带头结点的单循环链表的头指针，链表中的数据元素依次为(a1，a2,a3,a4,…,an),A为指向空的顺序表的指针。阅读以下程序段，并回答问题：

　　(1)写出执行下列程序段后的顺序表A中的数据元素；

　　(2)简要叙述该程序段的功能。

　　算法设计题：

　　34.在带头结点的循环链表L中，结点的数据元素为整型，且按值递增有序存放。给定两个整数a和b，且a

　　2005.01算法设计题(本题共10分)

　　34.假设一元多项式以循环链表表示，链表的结点结构为：

　　2005.10算法阅读题

　　30. 阅读下列算法，并回答问题：

　　(1)设顺序表L=(3,7,11,14,20,51)，写出执行f30(&L,15)之后的L；

　　(2)设顺序表L=(4,7,10,14,20,51)，写出执行f30(&L,10)之后的L；

　　(3)简述算法的功能。

    更多信息请访问：新浪自考频道