线性表——最基础的数据结构

1、什么是线性表？

​ 在学习线性表之前，我们首先需要了解线性表是什么

​ 线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构中的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

​ 线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表（存储层次上属于链式存储，但是把最后一个数据元素的尾指针指向了首位结点）

​ 我们说“线性”和“非线性”，只在逻辑层次上讨论，而不考虑存储层次，所以双向链表和循环链表依旧是线性表。

2、线性表的分类

（图片来自网络，侵删）

3、顺式结构

定义：

​ 线性表的顺序存储是指在内存中用地址连续的一块存储空间依次存放线性表的数据元素，用这种存储形式存储的线性表称为顺序表。

其储存方式如下图所示：

顺序存储的实现方式：

#include<iostream>
#define MAXSIZE 100        //定义最大储存空间
#define ElemType int        //定义数据类型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1

using namespace std;

//定义顺序表
typedef struct LNode *List;
struct LNode{
    ElemType Data[MAXSIZE];
    int Last;
};           

创建一个空的顺序表：

List MakeEmpty(){
    //构造一个空的线性表Ptrl
    List L
    L= new LNode;    //分配存放顺序表的空间
    L->Last = 0;
    return L;
}           

输入顺序表/初始化顺序表

void MakeList(List Ptrl)
{
    int i;
    cin >> n;        //输入需要的表长
    for(i = 0; i < n; i++){
        cin >> Ptrl->Data[i];    
    }
    L->Last = n;        //设置表长
}           

销毁/删除顺序表：

void DestroyList(List Ptrl)
{
    delete Ptrl；
}           

按数据元素查找：

int Find(List Ptrl, ElemType X)
{
    int i = 0;
    while(i <= Ptrl->Last && Ptrl->Data[i] != X)
        i++;
    if (i > Ptrl->Last)
         return ERROR;
    else
        return i;           

顺序表的插入：

bool Insert(List Ptrl, ElementType X, int i)
{
    int j;

    if (Ptrl->Last >= MAXSIZE-1)        //判断空间是否已满
    {
        cout << "NO SPACE";
        return OVERFLOW;
    }
    if (i < 1 ||i > Ptrl->Last+2)        //判断是否非法输入
    {
        cout << "ILLEGAL INPUT";
        return ERROR;
    }
    for (j = Ptrl->Last; j >= i-1; j--)        //将位置i后面的元素后移一个位置
    {
        Ptrl->Data[j+1] = Ptrl->Data[j];
    }
    Ptrl->Data[i-1] = X;    //插入数据
    Ptrl->Last++;    //顺序表长度加1
    return TRUE;
}           

顺序表的删除：

bool Delete(List Ptrl, int i)
{
    int j;

    if (i < 1 ||i > Ptrl->Last+1)        //判断是否非法输入
    {
        cout << "ILLEGAL INPUT";
        return ERROR;
    }
    for (j = i; j <= Ptrl->Last; j++)        //将位置i后面的元素前移一个位置
    {
        Ptrl->Data[j-1] = Ptrl->Data[j];
    }
    Ptrl->Last--;    //顺序表长度减1
    return TRUE;
}           

4、链式结构

​ 线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些元素可以存在内存未被占用的任意位置。

链式结构的实现方式：

#include<iostream>
#define MAXSIZE 100        //定义最大储存空间
#define ElemType int        //定义数据类型
#define ERROR 0
#define TRUE 1
#define OVERFLOW -1

using namespace std;

//定义链表
typedef struct LNode *List;
struct LNode{
    ElemType Data;
    List *Next;
};           

求一个链表的表长：

int length(List Ptrl){
    List P = Ptrl;    int j = 0;
    while(P){
        P = P->Next;    //指向下一个结点
        j++;        //当前P指向的是第j个节点    
        }
    return j;}           

查找第K项：

List FindKth(int K, List Ptrl){
    List P = Ptrl;    int i = 1;    
       while(P != nullptr && i < K){
        P = P->Next;
        i++;
       }
    if(i == K)
        return P;
    else
        return NULL;
}           

按值查找：

List Find(ElemType X, List Ptrl){
    List P = Ptrl;    int i = 1;
    while(P != nullptr && P->Data[i] != K){
        P = P->Next;
        i++;
    }
    if(P)
        return ERROR;
    else
        return P;
}           

链表的插入：

List Insert(ElemType X,  int i, List Ptrl){    List P, s;
    if(i == 1){        //新结点在第1位
        s = (List)malloc(sizeof(struct LNode));    //也可以这样去申请空间
         s = new(LNode);
        s->Data = X;
        s->Next = Ptrl;
        return s;
    }
    P = FindKth(i-1, Ptrl);    //查找第i-1个结点
    if(P == nullptr){    //第i-1个结点不存在，不能插入
        cout << "error";
        return nullptr;
    }
    else{
        s = (List)malloc(sizeof(struct LNode));
        s->Data = X;
        s->Next = P->Next;        //新结点插在第i-1个结点的后面
        P->Next = s;
        return Ptrl;    
        }
}           

链表的删除：

List Delete(int i, List Ptrl){
    List P, s;
    if(i == 1){    //如果删除的是第1个结点
        s = Ptrl;    //s指向第1个结点
        if(Ptrl != nullptr)
            Ptrl = Ptrl->Next;        //从链表中删除
        else
            return nullptr;
        delete s;        //释放被删除结点所申请的空间，防止内存泄漏
        return Ptrl;
    }
    P = FindKth(i-1, Ptrl);    //查找第i-1个结点
    if(P == nullptr){
        cout << "error";
        return NULL;
    }
    else if(P->Next == nullptr){
        cout << "not instance";
         return nullptr;
        }
    else{
        s = P->Next;
        P->Next = s->Next;        //删除结点
        delete s;
        return Ptrl;
    }
}           

5、顺式结构和链式结构的优缺点总结

1、顺序存储结构

优点：可以随机访问，在O(1)内查询、修改元素，存储容量高

缺点：在O(n)内插入和删除数据，修改困难，存储空间需要一次性获得，表示关系能力弱

2、链式存储结构

优点：空间任意，便于删改，表示关系的能力强，在O(1)内插入、删除元素

缺点：占用空间较多，必须通过指针来访问元素，在O(n)内查找、修改元素