定义

线性表（linear list）是数据结构的一种，一个线性表是n个具有相同特性的数据元素的有限序列。数据元素是一个抽象的符号，其具体含义在不同的情况下一般不同。
在稍复杂的线性表中，一个数据元素可由多个数据项（item）组成，此种情况下常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。
线性表中的个数n定义为线性表的长度，n=0时称为空表。在非空表中每个数据元素都有一个确定的位置，如用ai表示数据元素，则i称为数据元素ai在线性表中的位序。
线性表的相邻元素之间存在着序偶关系。如用（a1，…，ai-1，ai，ai+1，…，an）表示一个顺序表，则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i=1,2，…，n-1时，ai有且仅有一个直接后继，当i=2，3，…，n时，ai有且仅有一个直接前驱

抽象数据类型

所谓的抽象数据类型就是把数据类型和相关炒作绑在一起.

线性表的物理存储结构

线性表有两种物理存储结构:顺序存储结构和链式存储结构

线性表的顺序存储结构

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

#define MAXSIZE 20
typedef int ElemType;
typedef struct{
   ElemType data[MAXSIZE];
   int length;//线性表当前长度
}Sqlist;

• 顺序存储结构封装需要三个属性
  ①存储空间的起始位置,数组data,它的存储位置就是线性表存储空间的存储位置
  ②线性表的最大存储容量:数组长度MaxSize
  ③线性表的当前长度:length

获取元素操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
//Status 是函数的类型,其值是函数结果状态代码,如OK等.
//初始条件:顺序线性表L已存在
//操作结果:用e返回L中第i个数据元素的值
Status GetElem(sqlist L, int i ,ElemType *e){
 if(L.length == 0 || i< 1 || i>L.length ){
returen ERROR;
}
*e = L.data[i-1];
return OK;
}

插入新元素

插入算法的基本思路
① 如果插入位置不合理,抛出异常
② 如果线性长度大于等于数组长度,抛出异常或动态增加数组容量
③从最后一个元素开始向前遍历到第i个位置,分别将他们都向后移动一个位置
④ 将要插入元素填入位置i处
⑤ 线性表长+1

Status ListInsert(Sqlist *L ,int i, ElemType e ){

int k;
if(L->length == MAXSIZE)//顺序线性表已满{
 return ERROR;
}
if(i<1 | | i>L->length+1)//当I不在范围内时{
 return ERROR;
}
if(i<=L->length)//若插入数据位置不在表尾{
//将要插入位置后数据元素向后移动一位
for(k = L->length-1;k>=I -1;k--){
  L->data[k+1] = L->data[K];
}
}
L->data[I-1] = e;//将新元素插入
L->length++;
return OK;

删除操作

删除算法的思路
①如果删除位置不合理抛出异常
②取出删除元素
③从删除元素位置开始遍历到最后一个元素位置,分别将他们都向前移动一个位置
④表长-1

Status ListDelete(Sqlist *L ,int i, ElemType e ){
int k;
if(L->length == 0){
 return ERROR;
}
if(i<1 | | i>L->length){
 return ERROR;
}
*e = L->data[I-1]
if(i<=L->length){
 for(k =I; k<L->length;k++){
  L->data[k-1] = L->data[k];
}
}
L->length--;
return OK;

插入和删除时间复杂度分析

• 最好情况:插入和删除操作刚好要求放在最后一个位置,因为不要移动人和元素所以时间复杂度为O(1)
• 最坏情况:如果插入和删除位置都是第一个,那就意味着要移动所有元素向后或向前,所以这个时间复杂度为O(n)
• 平均情况:就取中间值O((n-1)/2),其复杂度简后还是O(n)
• 线性表的顺序存储结构,在存读数据时,不管是哪个位置,时间复杂度都是O(1)。而在插入或删除时,时间复杂度都是O(n)
• 说明它比较适合元素个数比较稳定,不经常插入和删除元素,而更多的操作是存取数据的应用

线性表顺序存储结构的优缺点

优点:
①无须为表示表中元素之间的逻辑关系而增加额外的存储空间
②可以快速的存取表中任意位置的元素
缺点:
①插入和删除操作需要移动大量元素
②当线性表长度变化较大时,难以确定存储空间的容量
③容易造成存储空间的碎片

线性表的链性存储结构

线性表的顺序存储结构最大缺点就是插入和删除时需要移动大量元素,需要耗费时间,其原因就在于相邻两元素的存储位置也具有邻居关系,它们在内存中的位置是紧挨着,中间没有间隙,无法快速的插入和删除,所以要移动大量元素,于是就有了链式存储结构

定义

• 线性表的链式存储结构的特点就是用一组任意的存储单元存储线性表的数据元素,这组存储单元可以在内存中未被占用的仍以位置
• 比起顺序存储结构每个数据元素秩序要存储一个位置就可以了。现在链式存储结构中,除了要存储数据元素信息外,还要存储它饿后续元素的存储地址(指针)
• 我们把存储数据元素信息的域称为数据域,把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链.这两部分数据元素称为存储映像,称为节点(Node)
• n 个节点链接成一个链表,即为线性表的链式存储结构

• 因此此链表的每个节点中只包含一个指针域,多以叫做单链表

  
  

单链表

对于线性表来说,总得有个头有个尾,链表也不例外。我们把链表中的第一个节点的存储位置叫做头指针,最后一个节点指针为空(NULL)

头指针与头结点的异同

头指针:

• 头指针是指链表指向第一个结点的指针,若链表有头结点,则是指向头结点的指针
• 头指针具有标识作用,所以常用头指针冠以链表的名字(指针变量的名字)
• 无论链表是否为空,头指针均不为空
• 头指针是链表的必要元素

头结点:

• 头结点是为了操作的统一和方便we设立的,放在第一个元素的节点之前,其数据一般无意义(但也可以用来存放链表的长度)
• 有了头结点,对在第一元素结点前插入结点和删除第一结点起操作与其它结点的操作就统一了

• 头结点不一定是链表的必须要素

  
  单链表图例

空链表图例

单链表的存储结构

在C语言中可以用结构指针来描述单链表

typedef struct Node{
   ElemType data; //数据域
   struct Node* Next;//指针域
}Node;
typedef struct Node* LinkList;
//可以看出结点由存放数据元素的数据域和存放后继结点地址的指针域组成

单链表的读取

• 在线性表的顺序存储结构中,我们要计算任意一个元素的存储位置是很容易的,但在单链表中由于第I个元素到底在哪?我们压根没办法一开始就知道,必须得从第一个节点开始挨个找.
• 获得链表第i个数据的算法思路
  ①声明一个节点p指向链表第一个节点,初始化j从1开始
  ②当j<i时,就遍历链表,让p的指针向后移动,不断指向下一个节点,j+1
  ③若到链表末尾p为空,则说明第i个元素不存在
  ④否则查找成功,返回节点P的数据

上代码:

Status GetElem(LinkList L, int I, ElemType *e){
   int j;
   LinkList p;
  
   p = L->next;
   j = 1;

  while(p && j <i){
   p = p->next;
   ++j;
}  

if( !p || j>i){
 return ERROR;
}

*e = p->data;
return OK;

}

• 说白了就是从头开始找,直到第i个元素为止
• 由于这个算法的时间复杂度取决于i的位置每当i=1时,则不需要遍历,而i=n时则需要遍历n-1次才可以.因此最坏情况的时间复杂度为O(n)
• 由于单链表的结构中没有有定义表长,所以不能实现直到要循环多少次,因此不方便用for来控制循环
• 其核心思想叫做"工作指针后移" ,这其实也是很多算法的常用技术

单链表的插入

如图我们发现不用改变其他结点,只需要让s->next和p->next的指针做一点改变即可

s->next = p->next;
p->next = s;

单链表第i个数据插入结点算法思路:

• 声明一结点p指向链表头结点,初始化j从1开始
• 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累计+1
• 若到链表末尾p为空,则说明第i个元素不存在
• 否则查找成功,在系统中生成一个空节点s;
• 将数据元素e复制给s->data
• 单链表的插入刚才两个标准语句
• 返回成功

Status ListInsert(LinkList *L ,int I, ELemType e){
  
 int j;
LinkList p,s;
p = *L;
j = 1;
while(p && j<1){
 p = p->next;
 j++;
}
if( !p || j>1){
 return ERROR;
}
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}

单链表的删除

假设a2的结点为q,要实现结点q删除单链表的操作,其实就是将它的前结点的指针绕过指向后继结点即可

即: p->next = p->next->next;
单链表第i个数据删除结点算法思路:

• 声明一结点p指向链表第一个结点,初始化j=1
• 当j<1时,就遍历链表,让p的指针向后移动,不断指向下一结点,j累计+1
• 若到链表末尾p为空,则说明第i个元素不存在
• 否则查找成功,将欲删除结点p->next赋值给q
• 单链表的删除标准语句p->next = q->next;
• 将q结点中的数据赋值给e,作为返回
• 释放q结点

Status ListDelete(LinkList *L ,int I, ELemType *e){
  
 int j;
LinkList p,q;
p = *L;
j = 1;
while(p->next && j<1){
 p = p->next;
 ++j;
}
if( !(p->next) || j>1){
 return ERROR;
}

q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}

效率PK

• 我们发现无论是单链表插入还是删除算法,它们其实都是由两部分组成:第一部分就是遍历查找第i个元素,第二部分就是实现插入和删除元素;
• 从整个算法来说,我们很容易可以推测出它们的时间复杂度都是O(n);
• 再详细点分析:如果我们不知道第i元素的指针位置;单链表数据结构在插入和删除操作上与线性表的顺序存储结构是没有太大优势的
• 但如果,我们希望从第i和位置开始,插入连续10个元素,对于顺序存储结构意味着,每一次插入都需要移动n-i个位置,多以每次都是0(n);二而单链表,我们只需要在第一次时,找到第i个位置的指针,此时为O(n),接下来只是简单的通过赋值移动指针而已,时间复杂度都是O(1)
• 显然,对于插入或删除数据越频繁的操作,单链表的优势就是越是明显的

单链表的整表创建

• 对于顺序存储结构的线性表的整表创建,我们可以用数组的初始化来直观理解
• 而单链表和顺序存储结构就不一样了,他不像顺序存储结构数据那么集中,他的数据可以是分散在内存各个角落的,他的增长也是动态的
• 对于每个链表来说,它所占用空间的大小和位置是不需要事先分配划定的,可以根据系统的情况和实际的需求即时生成

创建单链表的过程是一个动态生成链表的过程,从空表的初始状态起,依次建立各元素结点并逐个插入链表

单链表的整表创建的算法思路如下:

• 声明一结点p和计数器变量i
• 初始化一空链表L
• 让L的头结点的指针指向Null,即建立一个带头结点的单链表
• 循环实现后继结点的赋值和插入

头插法建立单链表

头插法从一个空表开始,生成新结点,读取数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到结束为止
简单来说,就是把新加进的元素放在表头后的第一个位置

• 先让新结点的next指向头结点之后
• 然后让表头的next指向新结点

上代码

void CreatListHead(LinkList *L, int n){
 LinkList p;
 int I;
 srand(time(0));初始化随机数
 *L = (LinkList)malloc(sizeof(Node));
(*L)->next = NULL;
for (I = 0 ;I <n; I++){
 
 p =(LinkList)malloc(sizeof(Node));
 p->data = rand()%100+1;
 p->next = (*L)->next;
 (*L )->next = p;
}
}

头部法生成的链表中结点的次序和输入的顺序是相反的

尾部发建立单链表

上代码

void CreatListTail(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 = (Node *)malloc(sizeof(Node));
p->data = rand()%100+1;
r->next = p;
r = p;
}
r->next = NULL;
}

单链表的整表删除

单链表整表删除的算法思路

• 声明结点p和q
• 将第一个结点赋值给p,下一个结点赋值给q
• 循环执行释放p和将q赋值给p的操作

上代码

Status ClearList(LinkList *L){
LinkList p,q;
p = (*L)->next;
while(p){
q = p->next;
free(p);
p=q;
}
(*L)->next = NULL;
return OK;
}

单链表结构与顺序存储结构优缺点

从存储分配方式,时间性能,空间性能三方面来对比

存储分配方式

• 顺序存储结构用一段连续的存储单元依次存储线性表的数据元素
• 单链表采用链式存储结构,用一组任意的存储单元存放线性表的元素

时间性能

查找

• 顺序存储结构O(1)
• 单链表O(n)

插入和删除

• 顺序存储结构需要平均移动表长一半的元素,时间为O(n)
• 单链表在计算出某位置的指针后,插入和删除时间仅为O(1)

空间性能

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

综上:若线性表需要频繁的查找,很少进行插入和删除操作宜采用顺序存储结构;若需频繁插入和删除时,宜采用单链表结构