线性表

一、线性表简介

  线性表是一种线性结构，它是由零个或多个数据元素构成的有限序列。线性表的特征是在一个序列中，除了头尾元素，每个元素都有且只有一个直接前驱，有且只有一个直接后继，而序列头元素没有直接前驱，序列尾元素没有直接后继。
  数据结构中常见的线性结构有数组、单链表、双链表、循环链表等。线性表中的元素为某种相同的抽象数据类型。可以是C语言的内置类型或结构体，也可以是C++自定义类型。

二、数组（vector和array）

  数组在实际的物理内存上也是连续存储的，数组有上界和下界。C语言中定义一个数组：

数组下标是从0开始的，a[0]对应第一个元素。其中，a[0]称为数组a的下界，a[6]称为数组a的上届。超过这个范围的下标使用数组，将造成数组越界错误。在C语言中，容易发生数组越界操作，尽量使用vector和string代替常规的数组和字符串。
【Note】：
（1）数组的特点是：数据连续，支持快速随机访问。

  数组分为固定数组与动态数组。其中固定数组的大小必须在编译时就能够确认，动态数组允许在运行时申请数组内存。复杂点的数组是多维数组，多维数组实际上也是通过一维数组来实现的。在C语言中，可以通过malloc来分配动态数组，C++使用new。另外，C++的标准模板库提供了动态数组类型vector以及内置有固定数组类型array。

  线性表的顺序存储结构，在存、读数据时，不管是哪个位置，时间复杂度都是O（1）;而插入或删除时，时间复杂度都是O（n）。

优点：

• 无需为表示线性表中的逻辑关系而增加额外的存储空间

• 可以快速的存取线性表中任一位置的元素

缺点：

• 插入和删除操作需要移动大量的元素

• 难以确定线性表存储空间的容量

• 造成存储空间的“碎片”，浪费存储空间

三、单向链表（forward_list）

  为了每个数据元素ai与其后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储本身的信息之外，还需要存储一个指示其后继元素的信息（即直接后继元素的存储位置）。

1、单向链表的一些操作

  单向链表是链表的一种。链表由节点所构成，节点内含一个指向下一个节点的指针，节点依次链接成为链表。因此，链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点，头节点不存放实际的值，它含有一个指针，指向存放元素的第一个节点。

（1）链表的结构代码：

typedef struct node
{
    int data;
    node *next;
}LNode,*LinkList;//Lnode是node的别名，LinkList是node*的别名

（2）查找某个节点：

bool FindNode(const LinkList head, int data)
{
    LinkList ptr = head;
    while(ptr != nullptr)
    {
       if(ptr->data == data)
          return true;
       ptr = ptr->next;//移动临时指针
    }
    return false;
}

（3）求节点的个数：

int NodeNum(const LinkList head)
{
    int length = 0;
    LinkList ptr = head;
    while(ptr != nullptr)
    {
        ++length;
        cout << ptr->data << " ";
        ptr = ptr->next;
    }
    return length;
}

（4）插入某个节点：

//在ptr之前插入某个节点
LinkList InsertNode(LinkList ptr, LinkList newnode)
{
    if (ptr == nullptr)
    {
        ptr->next = newnode;
        newnode->next = nullptr;
    }
    else
    {
        newnode->next = ptr->next;
        ptr->next = newnode;
    }
    return newnode;
}

（5）删除某个节点：

void EraseNode(LinkList ptr)
{
    LinkList Y = new LNode;
    if (ptr != nullptr)
    {
        Y = ptr->next;
        ptr->next = Y->next;
        delete Y;
    }
}

（6）尾插法创建链表：

void CreateListTail(LinkList *L, int n)
{
    LinkList p,r;
    int i;

    srand(time(0));
    *L = (LinkList)malloc(sizeof(Node));

    r = *L;

    for (i = 0; i < n; i++)
    {
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand() % 100 + 1;
        r->next = p;        /*将表尾终端节点的指针指向新节点*/
        r = p;  /*将当前的新节点定义为表尾终端节点*/
    }

    r->next = NULL;
}

（7）删除链表：

Status ClearList(LinkList *L)
{
    LinkList p, q;
    p = (*L)->next;      /*p指向第一个节点*/

    while (p)   /*没到结尾*/
    {
        q = p->next;
        free(p);
        p = q;
    }
    (*L)->next = NULL; /*头节点指针域为空*/
    return OK;
}

2、单向链表结构与顺序存储结构的优缺点

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素。

• 查找：顺序存储结构O(1)，单链表O(n)。

• 插入和删除：顺序存储结构O(n)，单链表O(1)。

• 顺序存储结构需要预先分配存储空间，分大了浪费空间，分小了容易造成内存溢出；单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

3、链表反转

LinkList ReverseNode(LinkList head)
{
    LinkList p, q, r;
    p = head;
    q = nullptr;
    while (p != nullptr)
    {
        r = q;
        q = p;
        p = p->next;
        q->next = r;
    }
    return q;
}

四、循环链表

  将单链表中终端节点的指针由空指针改为指向头节点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环列表，简称循环列表（circular linked list）。循环列表解决了一个很麻烦的问题：如何从任意一个节点出发，访问到链表的全部节点。

  非空的循环列表：

  其实循环列表和单链表的主要差异就在于循环的判断条件上，单链表是判断p->next是否为空，现在则是p->next不等于头结点，则循环未结束。

（1）插入节点：

//在链表首节点前插入节点
void InsertNode(LinkList ptr, LinkList X)
{
    LinkList head = X;
    ptr->next = head;
    LinkList curnode = head;
    while (curnode->next != head)
    {
        curnode = curnode->next;
    }
    curnode->next = ptr;
    ptr = head;
}

（2）删除节点：

//删除某个节点
void EraseNode(LinkList ptr, LinkList Y)
{
    while ((ptr != nullptr) && (ptr->next != Y))
    {
        ptr = ptr->next;
    }
    Y = ptr->next;
    ptr->next = Y->next;
    delete Y;
}

五、双向循环链表（list）

  单链表的节点链接是单方向的，要得到指定节点的前一个节点，必须从头遍历链表。
  双向链表是链表的一种。与单链表一样，双向节点由节点链接而成，每个节点含有两个指针，分别指向直接前驱与直接后继。从双向链表的任何一个节点开始都能够遍历整个链表。
  我们将双向链表实现为双向循环链表，也即是最后一个元素的后继将指向头节点，整个链表形成一个循环

（1）插入节点

s->prior = p;           /*把p赋值给s的前驱,如图①*/
s->next = p->next;      /*将p的后继节点赋值给s的后继,如图②*/
p->next->prior = s;     /*将s赋值给p->next的前驱,如图③*/
p->next = s;            /*将s赋值给p的后继,如图④*/

（2）删除节点

p->prior->next = p->next;   /*将p->next赋值给p->prior的后继,如图①*/
p->next->prior = p->prior;  /*将p->prior赋值给p->next的前驱,如图②*/