第二章 线性表

一 线性表的定义和基本运算

填空题

1. 线性表是最简单和最常用的数据结构，它是由n个数据元素（结点）a1,a2,a3,…an组成的有限序列。其中，数据元素的个数n为表的长度。当n为零时称为空表，非空的线性表通常记为：（a1, a2, …, ai-1, ai, ai+1, …,an）

2. 对于一个非空的线性表，其逻辑特征是：

3. 有且仅有一个称为开始元素的a1，它没有前趋，仅有一个直接后继a2。

4. 有且仅有一个称为终端元素的an，它没有后继，仅有一个直接前趋an-1。

5. 其余元素ai(2<=i<=n-1)称为内部元素，它们都有且仅有一个直接前趋ai-1和一个直接后继ai+1。

二 线性表的顺序存储和基本运算的实现

填空题

线性表的顺序存储指的是将线性表的数据元素按其逻辑次序依次存入一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。

单选题

顺序存储结构的特点是，元素在表中的相邻关系，在计算机内也存在这相邻的关系。

填空题

1. 线性表的插入运算是指在线性表的第i-1个元素和第i个元素之间插入一个新元素x，使长度为n的线性表：（a1, a2, …, ai-1, ai, …, an）变为长度为n+1的线性表：（a1, a2, …, ai-1, x, ai, …, an）。
2. 一般情况下，在顺序表的第i(1<=i<=n)个元素之前插入一个新元素时，需要进行n-i+1次移动。
3. 在等概率情况下，顺序表上插入一个元素需要移动元素的平局次数为n/2。
4. 线性表的删除运算指的是将表中第i(1<=i<=n)个元素删除，使长度为n的线性表（a1, a2, …, ai-1, ai, ai+1, … an）变为长度为n-1的线性表：（a1, a2, …, ai-1, ai+1, … an）
5. 在等概率情况下，顺序表上删除一个元素的平局移动次数为**(n-1)/2**。

算法设计题

已知一长度为n顺序存储的线性表，试写一算法将该线性表逆置。

// 这是一段没有提前创建线性表的伪代码

SeqList Converts( SeqList L)  // 定义一个逆置函数
{
    DataType x;  // 定义一个中间转换变量
    int i, k;  // 定义i为任意元素索引值，k为线性表长度的一半位置的索引值
    k = L.length / 2;
    for (i = 0; i < k; i++) {
        x = L.data[i];  // 把表中第i个元素赋值给x保存起来
        L.data[i] = L.data[L.length - i - 1];  // 把表表遍的数据赋值给左边相应位置上
        L.data[L.length - i - 1] = x;  // 反过来赋值
    }
    return L;
}

三 线性表的链式存储结构

填空题

在使用链式存储结构表示每个数据元素ai时，除了存储ai本身的信息之外，还需要一个存储指示其后继元素ai+1存储位置的指针，由这两部分组成元素ai的存储映像通常称为结点。它包括两个域：存储数据元素的域称为数据域，存储直接后继存储地址的域称为指针域。利用这种存储方式表示的线性表称为链表，链表中一个结点的存储结构为

data

next

n个结点链成一个链表，即为线性表（a1, a2,…, an）的链式存储结构。由于这种链表的每个结点中只包含一个指针域，因此又称为单链表。

解答题

1. 在单循环链表中，为了使空表和非空表的处理一致，需要设置头结点。
2. 双向链表既有向前链接的链，也有向后链接的链，所以在做链表上结点的插入和删除时就显得十分方便。
3. 在用头指针表示的单循环链表中，查找任何结点都必须从开始结点查起，而在实际应用中，表的操作常常会在表尾进行，此时若用尾指针表示单循环链表，可使某些操作简化。

算法阅读题（这里有问题）

1. 双向链表上的插入操作：在双向链表的给定结点前插入一结点，设P为给定结点的指针，x为待插入结点的值，其实现算法如下：

void DLInsert(DLNode * p, DataType x)
{
    DLNode * s = (DLNode *)malloc(sizeof(DLNode));
    	s->data = x;
    	s->prior = p->prior; s->next=p;
    	p->prior->next = s; p->prior=s;
}

2. 双向链表上的删除操作：双向链表上删除指定结点*p，其删除算法如下：

DataType DLDelete(DLNode * p)
{
    p->prior->next=p->next;
    p->next->prior=p->prior;
    x=p->data;
    free(p);
    return x;
}

四 顺序表和链表的比较

解答题

线性表有两种存储结构：顺序存储结构（顺序表）和链式存储结构（链表）。在实际应用中，通常从两个方面的性能来比较。

1. 时间性能：如果在实际问题中，对线性表的操作是经常性的查找运算，以顺序表形式存储为宜，如果经常进行的运算是插入和删除运算，以链式存储结构为宜。
2. 空间性能：对数据量大小能事先知道的应用问题，适合使用顺序存储结构，对数据量变化较大的动态问题，适合使用链式存储结构。