数据结构 - 线性表 - 顺序表

前言

最近刚刚开始复习408数据结构，就想着把每个章节的代码部分汇总记录一下，写成一组文章，便于日后的复习和参考。

本系列整体的框架和课后习题参考了王道的复习指导。在本系列的每篇文章中，我会先把该章节所对应数据结构的基础代码放上来，然后附上参考资料习题对应的题目代码。

线性表介绍

第一章的绪论没有涉及到具体数据结构的程序编写，我们在这里就暂时跳过。从第二章中的线性表开始介绍。首先贴一下本章的整体框架：

线性表
|
|--顺序存储
|  |--顺序表
|
|--链式存储
|  |--单链表（指针实现）
|  |--双链表（指针实现）
|  |--循环链表（指针实现）
|  |--静态链表（数组实现）

线性表（Linear List）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。线性表按照存储结构可分为顺序表和各种链表，本篇文章介绍其中顺序表的实现与其操作算法的编写。

顺序表代码实现

#include <stdio.h>
#include <iostream>
#include <limits.h>
using namespace std;

#define INIT_SIZE 10
#define DEBUG 1

typedef int ElemType;

typedef struct {
    ElemType* data;
    int length;
    int capacity;
} SeqList;

void init(SeqList &l) {
    l.data = (ElemType*) malloc(sizeof (ElemType) * INIT_SIZE);
    l.length = 0;
    l.capacity = INIT_SIZE;
}

void expand(SeqList &l, int target_size) {
    // Re-allocate a larger area for the list
    auto new_cap = l.capacity << 1;
    while (target_size > new_cap) {
        new_cap = new_cap << 1;
    }
    l.capacity = new_cap;

    if (DEBUG) {
        cout << "Expanding list to " << new_cap << " bytes" << endl;
    }

    auto new_data = (ElemType*) malloc(sizeof (ElemType) * new_cap);
    // Copy the array contents
    memcpy(new_data, l.data, sizeof (ElemType) * l.length);
    // Free previously used memory
    free(l.data);
    l.data = new_data;
}

void insert(SeqList &l, ElemType value, int pos) {
    if (pos > l.length || pos < 0) { // It is ok to insert at [l.length]
        cout << "Trying to insert at " << pos << " (Len: " << l.length << ")" << endl;
        
        return;
    }

    int new_len = l.length + 1;

    if (new_len > l.capacity) {
        expand(l, new_len);
    }

    for (int i = l.length - 1; i >= pos; i--) {
        l.data[i + 1] = l.data[i];
    }

    l.data[pos] = value;
    l.length = new_len;
}

void remove(SeqList &l, int pos) {
    if (pos >= l.length || pos < 0) { // It is NOT ok to remove at [l.length]
        cout << "Trying to remove at " << pos << " (Len: " << l.length << ")" << endl;
        
        return;
    }

    int new_len = l.length - 1;

    for (int i = pos; i < new_len; i++) {
        l.data[i] = l.data[i + 1];
    }

    l.length = new_len;
}

void print(SeqList &l) {
    for (int i = 0; i < l.length; i++) {
        cout << l.data[i] << ' ';
    }
    cout << endl;
}

void print_size(SeqList &l) {
    cout << "Len: " << l.length << ", Cap: "<< l.capacity << endl;
}

顺序表综合应用

[01] 从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出。

// Chap 2. 01
ElemType remove_min(SeqList &l) {
    if (l.length == 0) {
        cout << "List is empty" << endl;
    }

    ElemType cur_min = INT_MAX;
    auto min_pos = -1;

    for (int i = 0; i < l.length; i++) {
        if (l.data[i] < cur_min) {
            min_pos = i;
            cur_min = l.data[i];
        }
    }

    l.data[min_pos] = l.data[l.length - 1];
    l.length -= 1;

    return cur_min;
}

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

// Chap 2. 02
void rev(SeqList &l) {
    int i = 0;

    // 右移一个bit就是除以2
    // 奇数的话直接把0.5抹掉，正中间的元素不需要动
    while (i < (l.length >> 1)) {
        auto t = l.data[i];
        l.data[i] = l.data[l.length - 1 - i];
        l.data[l.length - 1 - i] = t;

        i++;
    }
}

[03] 对长度为n的顺序表L，编写一个时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除所有值为x的数据元素。

// Chap 2. 03
void remove_all(SeqList &l, ElemType value) {
    int rm_cnt = 0;

    for (int i = 0; i < l.length; i++) {
        if (l.data[i] == value) {
            rm_cnt++;
        } else {
            l.data[i - rm_cnt] = l.data[i];
        }
    }

    l.length -= rm_cnt;
}