王道数据结构 第二章 线性表

线性表的定义和基本操作

线性表的定义

线性表是具有相同数据类型的n(n>=0)个数据元素的有限序列。其中n为表长，当n = 0时该线性表是一个空表。
除了第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继。线性有序！！
线性表的特点如下：

1. 表中元素的个数有限
2. 表中元素具有逻辑上的顺序性，在序列中各元素排序有其先后次序。
3. 表中元素都是数据元素，每个元素都是单个元素
4. 表中元素的数据类型都相同，每一个元素占有相同大小的存储空间
5. 表中元素具有抽象性。仅讨论元素间的逻辑关系，不考虑元素究竟表示什么内容

线性表示是一种逻辑结构，表示元素之间一对一相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念。

线性表的基本操作

一个数据结构的基本操作是指其最核心最基本的操作。其他较复杂的操作可以通过调用其基本操作来实现。
线性表基本操作如下：

InitList(&L);//初始化表。构造一个空的线性表

Length(L);//求表长。返回线性表的长度。

LocateElem(L,e);//按值查找操作。在表中查找具有给定关键字值的元素。

GetElem(L,i);//按位查找操作。在表中第i个位置元素的值。

ListInsert(&L,i,e);//插入操作。在表中第i个位置插入指定元素e。

ListDelete(&L,i，&e);//删除操作。删除表中第i个位置的元素，并用e返回删除元素的值。

PrintList(L);//输出操作，按照前后顺序输出线性表L的所有元素值。

Empty(L); //判空操作，若为空返回 True。

DestroyList(L);//销毁操作，销毁线性表，并释放线性表L所占用的内存空间。

需要注意到线性表是逻辑结构而不是存储结构，线性表的长度一定是有限的，是由有限个数据元素组成的，数据元素是数据项组成的。

线性表的顺序表示

顺序表的定义

线性表的顺序存储又称为顺序表。用一组连续的存储单元，依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。特点是：表中元素的逻辑顺序和其物理顺序相同。

线性表的存储类型描述如下

#define MAXSIZE 100                  //定义顺序表的最大长度
typedef  struct {
    ElemType data[MAXSIZE];          //顺序表的元素
    int length;                      //顺序表当前长度
}SqList；

其中一维数组可以是静态分配，也可以是动态分配的。静态分配时，若空间占满，再加入新的数据将会产生溢出，导致程序崩溃。
动态分配是指在程序执行过程中通过动态存储分配语句分配内存。一旦数据空间占满，就开辟一块更大的存储空间，替换掉原有的。

动态分配不是链式存储，还是属于顺序存储结构，物理结构并无变化。分配的空间可以在运行时决定。

顺序表最主要的特点是随机访问。可以在O(1)的时间内找到指定元素。
存储密度高，每个节点只存储数据元素。
逻辑上相邻的元素物理上也相邻，插入和删除需要移动大量元素。

顺序表上基本操作的实现

1. 插入操作,在顺序表L的第i个位置插入元素e，成功返回true，失败返回false

bool listInsert(sqList & L,int i,ElemType e) {
    if(i<1 || i > L.length + 1) return false;
    if(L.length >= maxSize) return false;
    for(int j = L.length; j >= i; j--) L.data[j] = L.data[j-1];
    L.data[i-1] = e;
    L.length ++;
    return true;
}

2. 删除操作，删除第i个位置上的元素，成功返回TRUE，并将删除的元素用e返回，失败返回false

bool listDelete(sqList & L,int i, ElemType &e) {
    if(i < 1|| i> L.length) return false;
    e = L.data[i-1];
    for(int j = i; j < L.length; j++) L.data[j-1] = L.data[j];
    L.length --;
    return true;
}

3. 按值查找，在L中查找元素值为e的元素，并返回其位序

int LocateElem(sqList L, ElemType e) {
    int i;
    for(i = 0; i < L.length ; i++) {
        if(L.data[i] == e) return i+1;
    }
    return 0;//查找失败
}

---

Ok，基础知识搞定了，接下来上编程题。（线性表为了方便debug，我在这里全部采用STL中的vector）

1. 从顺序表中删除具有最小值的元素，并由函数返回被删除元素的值，空出的位置由最后一个元素填补，若表为空则显示出错信息并退出运行。

#include <iostream>
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;
//T1
bool deleteMin(vector<int> &v, int &e) {
    if (v.size() < 1) return false;
    int len = v.size(), pos = 0; e = v[0];
    for (int i = 1; i < len; i++) {
        if (v[i] < e) {
            e = v[i];pos = i;
        }
    }
    v[pos] = v[len - 1];
    v.resize(len - 1);
    return true;
}

void testT1() {
    vector<int> t;
    int e = 0;
    for (int i = 1; i < 10; i++)  t.push_back(i);
    deleteMin(t, e);
    for (int i = 0; i < t.size(); ++i)
        cout << t[i];
    cout << endl;
    cout << e << endl;
}

int main() {
    testT1();
    system("pause");
    return 0;
}

代码模板如下，之后将只给出功能函数和test函数。

2. 设计一个高效的算法，将顺序表的所有元素逆置，要求空间复杂度为O(1)

void reverseSqList(vector<int> &v) {
    int temp;
    int length = v.size() / 2;
    for (int i = 0; i < length; i++) {
        temp = v[i];
        v[i] = v[v.size() - i - 1];
        v[v.size() - i - 1] = temp;
    }
}

void testT2() {
    vector<int> t;
    for (int i = 1; i < 10; i++)  t.push_back(i);
    reverseSqList(t);
    for (int i = 0; i < t.size(); ++i)
        cout << t[i];
    cout << endl;
}

3. 长度为n的顺序表L，编写一个时间复杂度O(n) 空间复杂度O(1)的算法，实现删除线性表中所有值为x的元素。

void deleteAllx(vector<int> &v, int x) {
    int index = 0, length = v.size();
    for (int i = 0; i < length; i++) {
        if (v[i] != x)  v[index++] = v[i];
    }
    v.resize(index);
}

void testT3() {
    vector<int > t;
    t.push_back(1);
    for (int i = 1; i < 10; i++)  t.push_back(2);
    deleteAllx(t, 1);
    for (int i = 0; i < t.size(); i++)  cout << t[i];
}

4. 从有序表中删除其值在s和t（s<t）之间的所有元素，若s或t不合理或者顺序表为空则显示出错信息并退出运行。

bool deleteS2T1(vector<int> &v, int s, int t) {
    if (s > t) return false;
    if (v.size() == 0) return false;
    int length = v.size();
    int index = 0;
    for (int i = 0; i < length; i++) 
        if (v[i] < s || v[i] > t)  v[index++] = v[i];
    v.resize(index);
    return true;
}

bool deleteS2T2(vector<int> &v, int s, int t) {
    if (s > t) return false;
    if (v.size() == 0) return false;
    int length = v.size();
    int i, j;
    for (i = 0; i < length && v[i] < s; i++);
    if (i >= length) return false;
    //cout << i << endl;
    for (j = i; j < length && v[j] <= t; j++);
    //cout << j << endl;
    for (; j < length; i++, j++) v[i] = v[j];
    v.resize(i);
    return true;
}

void testT4() {
    vector<int> t;
    for (int i = 1; i < 10; i++)  t.push_back(i);
    if(deleteS2T2(t,2,7)) for (int i = 0; i < t.size(); i++)  cout << t[i];
    else cout << "wrong parm" << endl;
}

5. 从有序顺序表中删除所有其值重复的元素，使表中所有元素的值均不同。

bool deDuplicate(vector<int> &v) {
    if (v.size() == 0 ) return false;
    int length = v.size();
    int i = 0;
    for (int j = 1; j < length; j++) {
        if (v[i] != v[j]) {
            v[++i] = v[j];
        }
    }
    v.resize(i + 1);
}
void testT5() {
    vector<int> t;
    for (int i = 0; i < 20; i++)
        t.push_back(i / 2);
    for (int i = 0; i < 20; i++) cout << t[i];
    cout << endl;
    deDuplicate(t);
    int length = t.size();
    for (int i = 0; i < length; i++) cout << t[i];
    cout << endl;
}

6. 将两个有序顺序表合并成一个新的有序顺序表，并由函数返回结果顺序表。

vector<int> merge2List(vector<int> v1, vector<int> v2) {
    
    int len1 = v1.size(), len2 = v2.size();
    vector<int> temp(len1 + len2);
    int i = 0, j = 0, index = 0 ;
    while (i < len1 && j < len2){
        if (v1[i] < v2[j]) {
            temp[index++] = v1[i++];
        }
        else {
            temp[index++] = v2[j++];
        }
    }
    while (i < len1) temp[index++] = v1[i++];
    while (j < len2) temp[index++] = v2[j++];
    return temp;
}

void testT6() {
    vector<int> t1,t2,t3;
    for (int i = 0; i < 10; i++) t1.push_back(i * 2);
    for (int i = 0; i < 10; i++) t2.push_back(i * 3);
    t3 = merge2List(t1, t2);
    for (int i = 0; i < t3.size(); i++) cout << t3[i];
}

7. 已知在一维数组A[m+n]中依次存放着两个线性表a（长度为m），b（长度为n），写一个函数，将数组中的两个顺序表的位置互换。

void reverse(int a[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    for (int i = 0; i <= mid - left; i++) {
        int temp = a[left + i];
        a[left + i] = a[right - i];
        a[right - i] = temp;
    }
}

void Exchange(int a[], int m, int n) {
    reverse(a, 0, m + n - 1);
    reverse(a, 0, n - 1);
    reverse(a, n, m + n - 1);
}

void testT7() {
    int a[100];
    for (int i = 0; i < 10; i++)
        a[i] = i;
    Exchange(a, 2, 8);
    for (int i = 0; i < 10; i++)
        cout << a[i];
}

8. 线性表中元素递增有序且按照顺序存储于计算机内，要求设计一算法完成用最少时间在表中查找数值为x的元。若找到将其与后继元素相交换，若找不到将其插入表中，使表中元素仍递增有序。

void binarySearch(vector<int> &v, int e) {
    int low = 0, high = v.size() - 1, mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (v[mid] == e) break;
        else if (v[mid] < e) low = mid + 1;
        else high = mid - 1;
    }
    if (v[mid] == e && mid != v.size() - 1) {
        int temp = v[mid];
        v[mid] = v[mid + 1];
        v[mid + 1] = temp;
    }
    if (low > high) {
        int i;
        v.resize(v.size()+ 1); 
        for ( i = v.size() - 2; i > high; i--) v[i + 1] = v[i];
        v[i + 1] = e;
    }
}

void testT8() {
    vector<int> t;
    for (int i = 0; i < 10; i++) t.push_back(2*i);
    binarySearch(t,11);
    int length = t.size();
    for (int i = 0; i < length; i++)
    {
        cout << t[i];
    }
}

9.数组循环移p位

void reverse(int a[], int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    for (int i = 0; i <= mid - left; i++) {
        int temp = a[left + i];
        a[left + i] = a[right - i];
        a[right - i] = temp;
    }
}
void Exchange(int a[], int p, int n) {
    reverse(a, 0, p- 1);
    reverse(a, p, n - 1);
    reverse(a, 0, n - 1);
}

还有两题待补！