数据结构：一般线性表

简介

数据结构

数据的逻辑结构：是指数据元素之间的逻辑关系，分为线性结构和非线性结构。

数据的存储结构：是指数据结构在计算机中的表示，也称物理结构。主要有顺序存储、链式存储、索引存储、散列存储。

复杂度

时间复杂度：取f(n)中随n增长最快的项将其系数设置为1作为时间复杂度的度量。

空间复杂度：

线性表

线性表：是具有相同数据类型的n个数据元素的有限序列（n大于等于0）

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

顺序表

顺序表的特点是表中元素的逻辑顺序与其物理顺序相同

特点：

• 最主要特点是可以进行随机访问，即通过首地址和元素序号可以在O(1)时间内找到指定元素
• 存储密度高，每个结点只存储数据元素
• 逻辑上相邻的元素物理上也相邻，所以，插入和删除需要移动大量的元素

时间复杂度：

• 线性表插入的时间复杂度是O(n)
• 线性表删除的时间复杂度是O(n)
• 线性表按值查找的时间复杂度是O(n)

链表

1. 单链表

线性表的链式存储又称为单链表，它是通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据与元素之间的线性关系，对每个链表节点，除了存放元素自身的信息之外，还需要一个存储指向其后继的指针。data为数据域，存放数据元素；next为指针域，存放其后继节点的地址。

单链表节点结构

为了操作上方便，在单链表的第一个节点之前附加一个节点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等相关信息。头结点的指针域指向线性表的第一个元素节点。

时间复杂度：

• 头插法建立单链表每个节点插入的时间为O(1)，设单链表元素为n，则总的时间复杂度为O(n)
• 尾插发建立单链表每个节点插入的时间为O(1)，设单链表元素为n，则总的时间复杂度为O(n)
• 按序号查找节点值的时间复杂度为O(n)
• 按值查找表节点的时间复杂度为O(n)
• 插入节点的时间复杂度为O(n)，若是在给定的节点后面插入新节点，则时间复杂度仅为O(1)
• 删除节点的时间复杂度为O(n)
• 求表长的时间复杂度为O(n)

2. 双链表

3. 循环链表

循环单链表：循环单链表和单链表的区别在于，表中最后一个节点的指针不是NULL，而是指向头结点

循环双链表：

4. 静态链表

静态链表是借助数组来描述线性表的链式存储结构，节点也有数据域data和指针域next，这里的指针是节点的相对地址（数组下标），又称游标。和顺序表一样，静态链表也需要预先分配一块连续的内存空间。

静态链表存储示意图

静态链表以next=-1作为其结束的标致。静态链表的插入、删除操作与动态链表相同，只需修改指针，而不需要移动元素。总体来说静态链表没有单链表使用起来方便，但是在一些不支持指针的高级语言中，这是一种非常巧妙的方法。