标签：结点 单链 线性表 元素 链表 指针

线性表

线性表的定义

线性表（List）：零个或多个数据元素的有限序列

元素之间是有自己的顺序的。若元素存在多个，则第一个元素五前趋，最后一个元素无后继，其他元素有且只有一个前趋和后继

线性表的抽象数据类型

InitList(*L):          初始化操作，建立一个空的线性表L。
ListEmpty(L):          若线性表为空，返回true，否则返回false。
ClearList(*L):         将线性表清空。
GetElem(L, i, *e):     将线性表L中的第i个位置元素值返回给e。
LocateElem(L, e):      在线性表L中查找与给定值e相等的元素，查找成功则返回该元素在表中的序号
ListInsert(*L,i,e)     在线性表中的第i个位置插入新元素e

线性表的顺序存储结构

顺序存储的定义

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

顺序存储方式

/* 存储空间初始分配量 */
#define MAXSIZE 20             
/* ElemType类型根据实际情况而定，这里假设为int */
typedef int ElemType;          
typedef struct
{
/* 数组存储数据元素，最大值为MAXSIZE */
ElemType data[MAXSIZE];    
/* 线性表当前长度 */
int length;                
} SqList;

描述顺序存储结构需要三个属性
-存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置
-线性表的最大存储容量：数组Maxsize
-线性表的当前长度：length

线性表长度与数组长度的区别

数组长度是存放线性表的存储空间的长度，存储分配后这个量一般是不变的

线性表的长度是线性表中数据元素的个数，随着线性表的插入与删除操作的进行，这个量是变化的

在任意时刻线性表的长度应该小于等于数组的长度

地址计算方法

用数组存储顺序表意味着要分配固定长度的数组空间，由于线性表中可以进行插入与删除操作，因此分配的数组空间要大于等于当前线性表的长度。

假设表中的每个数据元素占用c个存储单元，则顺序表中第i+1个数据元素的存储位置和第i个数据元素的存储位置满足以下关系

LOC(ai+1)=LOC(ai)+c

所以对于第i个数据元素ai的存储位置可以由a1推算得出

loc(ai)=loc(a1)+(i-1)c

通过这个公式我们可以随时算出线性表中任意位置的地址，不管它是哪一个都是相同的时间，那么对线性表中任意位置的数据的存储与删除对于计算机都是相同的时间，则它的时间复杂度为O（1）。我们通常把具有这一特点的存储结构称为随机存储结构

顺序存储结构的插入与删除

获取元素操作

即将线性表中的第i个元素值返回。
就程序而言，只要i的数值在数组下标的范围内，就把第i-1下标值返回即可。

插入操作

算法思路

• 如果插入操作不合理，抛出异常
• 如果线性表的长度大于数组长度，则抛出异常或动态增加容量
• 从最后一个元素开始向前遍历到第i个位置，并将它们向后移动一个位置
• 将要插入元素填入位置i处，表长加1

删除操作

算法思路

• 如果删除不合理，抛出异常
• 取出删除元素
• 从删除元素开始便利到最后一个元素位置，分别将它们都向前移动一个位置
• 表长减一

时间复杂度

线性表的顺序存储结构，在存，读数据时，时间复杂度为O(1)，而插入或删除时，时间复杂度都是O(n)。

顺序存储结构的优缺点

优点

• 无须为表示表中元素之间的逻辑关系而增加额外的存储空间
• 可以快速的存取表中任意位置的元素

缺点

• 插入和删除操作需要移动大量的元素
• 当线性表长度变化较大时，难以确定存储空间的容量
• 造成存储空间碎片

线性表的链式存储结构

线性表链式存储结构的定义

用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是可连续的，也可以是不连续的。这意味着，这些数据元素课一存储在内存中未被占用的任意位置。

在链式结构中，每个数据元素除要存的数据星系外，还要存储它的后继元素的存储地址。

对于每个数据元素ai，处理存储本身的信息外，还需要存储一个指示其直接后继的信息（直接后继位置的存储位置）。

我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称为指针或链。

这两部分信息组成ai的存储映像，称为结点。

n个结点（ai的存储映像）链接成一个链表，即为线性表的链式存储结构，此链表中的每个结点值包含一个指针域，称为单链表。

单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

我们把链表中第一个结点的存储位置称为头指针，整个链表的存取必须从头指针开始进行。

之后的每一个结点都是上一个的后继指针指向的位置。最后一个结点指针为空（通常用NULL表示）。

有时未来方便操作，会在单链表的第一个结点前附设一个结点，称为头结点。头结点的数据与可以不存储任何信息。

头指针可以存储线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针。

头指针与头结点的异同

头指针

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

头结点

• 头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表长度）。
• 有了头结点，对在第一元素结点前插入结点与删除第一结点的操作就统一了。
• 头结点不一定是链表的必须要素。

线性表链式存储结构代码描述

结点由存放数据元素的数据域和存放后继结点的指针域组成。假设p是指向线性表第i个元素的指针，则该结点ai的数据域我们可以用p->data表示，p->data的值是一个数据元素。

结点ai的指针域可以用p->next表示，p->next的值是一个指针。

p->next指向第i+1个元素，即指向ai+1的指针，也就是说p->data=ai,p->next->data=ai+1.

单链表的读取

获取链表第i个数据的算法思路

• 声明一个指针p指向链表的第一个结点，初始化j从1开始
• 当j＜i时，就遍历链表，让怕的指针向后移动，不断指向下一个结点，j累加1
• 若到链表末尾p为空时，则说明第i个结点不存在
• 否则查找成功，返回结点p的数据

此算法的时间复杂度取决于i，最坏情况下为O（n）

单链表的插入与删除

单链表的插入

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

• 声明一指针p指向链表头结点，初始化j从1开始
• 当j＜i时，就遍历链表，让p的指针想后移动，不断指向下一结点，j累加1
• 若到链表末尾p为空，则说明第i个结点不存在
• 否则查找成功，在系统中生成一个空结点s
• 将数据元素e赋值给s->data
• 插入标准语句s->next=p->next（让p的后继结点变为s的后继结点）p->next=s（让b的后继结点变为s）

单链表的删除

单链表第i个数据删除结点的算法思路

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

单链表插入与删除算法时间复杂度也都是O(n),但如果插入与删除数据越繁琐的操作，单链表的效率就越明显

单链表的整表创建

单链表创建的算法思路

• 声明一指针p和计数器变量
• 初始化一空链表L
• 让L的头结点的指针指向NULL，即建立一个带头结点的单链表
• 循环：
  1.生成一新结点赋值给p
  2.随机生成随机数赋值给p的数据域p->data
  3.将p插入到头结点与前一新结点之间

单链表的整表删除

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

• 声明一指针p和q
• 将第一个结点赋值给p
• 循环：
  1.将下一结点赋值给q
  2.释放p
  3.将q赋值给p

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

存储分配方式

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

时间性能

查找

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

插入与删除

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

空间性能

• 顺序存储结构需要预分配存储空间，易发生分配不合理
• 单链表不需要分配存储空间，只要有就可与i分配，元素个数也不受限制

静态链表

让数组的元素由两个数据域组成，data和cur。

也就是说，数组的每个下表都对应着一个data和一个cur。

数据域data，用来存放数据元素，也就是通常我们要处理的数据.而cur相当于单链表中的next指针，存放该元素后继在数组的下标，我们把cur叫做游标

我们把这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法

为了方便插入数据，通常会把数组建立的大一些。以便有一些空闲空间可以便于插入时不至于溢出。

通常对数组的第一个和最后一个元素做特殊处理，不存数据，我们通常把未被使用的数组元素称为备用链表。

数组的第一个元素，即下标为0的元素cur就存放备用链表结点的第一个下标；而数组的最后一个元素cur则存放第一个有数值的元素的下标，相当于但链表中头结点作用，当整个链表为空时，则为0。

静态链表的插入操作

静态链表中要解决的是：如何用静态模拟动态链表结构的存储空间的分配，需要时申请，无用时解放

解决方法时将所有未被使用过的及已经被删除的分量用游标链接成一个备用的链表，每当进行插入时，便可从备用链表上去的第一个结点作为待插入的点。

静态链表的删除操作

与单链表基本相同

静态链表的优缺点

优点

• 再插入与删除操作时，只需要修改游标，不需要移动元素，从而改进了再顺序存储结构中的插入与删除操作需要移动大量元素的缺点

缺点

• 没有解决连续分配存储单元带来的表长难以确认的问题
• 失去了顺序存储结构随机存取的特性

循环列表

对于单链表，由于每个结点只存储了向后的指针，到了为标志就停止了向后链的操作，这样就会使当中某一结点无法找到它的前趋结点

将单链表中的终端结点的指针端由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为单循环列表，简称循环列表。

双向列表

在单链表的每个结点中，再设置一个指向其前趋结点的指针域将其改为双向链表

在进行插入操作时，顺序是先搞定s的前趋和后继，然后解决后结点的前趋，最后解决前结点的后继。

标签：结点,单链,线性表,元素,链表,指针
From： https://www.cnblogs.com/wcho825/p/16837117.html