线性表

标签：结点 cur 元素 next 链表 线性表

线性表：零个或多个元素的有限序列。

1. 若存在多个元素，则第一个元素无前驱，最后一个元素无后继，其他的每个元素有且只有一个前驱或后继；
2. 若将线性表记为a₁、a₂……a_i-1、a_i、a_i+1、a_n，a_i-1称为a_i的直接前驱元素，a_i+1是a_i的直接后继元素。
3. 线性表强调元素个数是有限的，线性表元素的个数n（n>=0）称为线性表的长度，当n=0时，称为空表；
4. 在较复杂的线性表中，一个数据元素可以由若干个数据项组成

• 线性表的抽象数据类型（Abstract Data Type）

　　抽象数据类型是计算机科学中 （  具有类似行为的特定类别的数据结构  ） 的数学模型；或者 （  具有类似语义的一种或多种程序设计语言  ） 的数据类型。抽象数据类型是描述数据结构的一种伦理工具，其目的是使人们能够独立于程序的实现细节来理解数据结构的特性。抽象数据类型的定义取决于它的一组逻辑特性，而与计算机内部如何表示无关。

　　抽象数据类型有可能是数据结构的数学模型，和程序设计语言的数据类型，能反映数据结构的特性。

　　抽象数据类型是指一个数学模型以及定义在此数学模型上的一组操作，它通常是对数据的某种抽象，定义了数据的取值范围及其结构形式，以及对数据操作的集合。抽象数据类型的特征是将使用与实现分离，从而实行封装状与隐藏信息。（例如，整数类型也是一种抽象数据类型）

ADT　　线性表（List）

Data

　　线性表的数据对象集合为（a₁、a₂，……，a_n），每个元素的类型均为DataType。其中，除第一个元素a₁外，每一个元素有且只有一个直接前驱元素，除了最后一个元素a_n外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。

Operation

　　InitList（*L）：初始化操作，建立一个空的线性表L。

　　ListEmpty（L）：若线性表为空，返回true，否则返回false。

　　ClearList（*L）：将线性表清空。

　　GetElem（L，i，*e）：将线性表L中的第i个位置元素值返回给e。

　　LocateElem（L，e）：在线性表L中查找与给定值e相等的的元素，如果查找成功，返回该元素在表中序号表示成功，否则，返回0表示失败。

　　ListInsert（*L，i，e）：在线性表L中的第i个位置插入新元素e。

　　ListDelete（*L，i，*e）：删除线性表L中第i个位置元素，并用e返回其值。

　　ListLength（L）：返回线性表L的元素个数。

　　void unionL(SqList *La,SqList Lb)
　　{
　　　　int La_len,Lb_len,i;
　　　　ElemType e;　　 /*声明与La、Lb相同的数据元素e*/
　　　　La_len=ListLength(*La); 　　 /*求线性表的长度*/
　　　　Lb_len=ListLength(Lb);
　　　　for(i=1;i<=Lb_len;i++)
　　　　{
　　　　　　GetElem(Lb,i,&e);　　 /*取Lb第i个数据元素赋给e*/
　　　　　　if(!LocateElem(*La,e)) 　　 /*La中不存在和e相同的数据元素*/
　　　　　　　　ListInsert(La,++La_len,e);　　 /*插入*/
　　　　}
　　}

　　可见，对复杂的个性化的操作，其实就是把基本操作组合起来实现的。当你传递一个参数给函数的时候，这个参数会不会在函数内被改动决定了使用什么参数形式。如果需要被改，则需要传递指向这个参数的指针。如果不用被改动，可以直接传递这个参数。

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

通过占位的形式把一块内存空间给占了，然后把相同类型的数据元素都依次存放在这块空地中，可以用c语言的一维数组来实现顺序存储结构

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

　　这里，我们就发现描述数据存储结构需要三个特性：

　　（1）存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置；

　　（2）线性表的最大存储容量：数组长度MAXSIZE；

　　（3）线性表的当前长度：length。

　数组长度>=线性表长度。

 地址计算方法：存储器中的每个存储单元都有自己的编号，这个编号成为地址。LOC表示获得存储位置的函数：

　　1.LOC(a_i+1)=LOC(a_i)+c　　2.LOC(a_i)=LOC(a₁)+(i-1)*c

存储时间性能为O(1)，具有这一特点的存储结构记为随机存储结构。

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

线性表顺序存储的优缺点

优点：无需为表示表中元素之间的逻辑关系而增加额外的存储空间，可以快速地存取表中任意位置的元素。

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

• 【线性表】的链式存储结构：用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称作指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。n个结点（a的存储映像）链结成一个链表，即为线性表（a₁、a₂，……，a_n）的链式存储结构。

单链表：因为此链表的每个结点包含一个指针域，所以叫做单链表。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起。

　　我们把链表中第一个结点的存储位置叫做头指针。（我们规定，线性链表的最后一个结点指针为“空”，通常用NULL或“^”符号表示），为了方便操作，一般会在单链表的第一个结点前附设一个结点，称为头结点。头指针：链表指向第一个结点的指针，若链表有头结点，则是指向头结点的指针，头指针具有标志作用，所以常用头指针冠以链表的名字，无论链表是否为空，头指针均不为空，头指针是链表的必要元素。头结点：头结点是为了操作的统一和方便而设立的，放在第一元素的结点之前，其数据域一般无意义（也可存放链表的长度），有了头结点，对在第一元素结点前插入结点和删除第一结点，其操作与其它结点的操作就统一了，头结点不一定是链表必需要求。结点由存放数据元素的数据域和存放后继结点地址的指针域组成。

• 我们在C语言中可用结构指针来描述

　　/*线性表的单链表存储结构*/
　　typedef struct Node
　　{
　　　　ElemType data;
　　　　struct Node *next;
　　}Node;

• 单链表的读取

　　/*初始条件：链式线性表L已存在，1<=i<=ListLength(L)*/
　　/*操作结果：用e返回L中第i个元素的值*/
　　Status GetElem(LinkList *L,int i,ElemType e)
　　{
　　　　int j;
　　　　LinkList p; 　　 /*声明一结点p*/
　　　　p=L->next; 　　 /*让p指向链表L的第一个结点*/
　　　　j=1; 　　 /*j为计数器*/
　　　　while(p&&j<i) 　　 /*p不为空或者计数器还没有等于i时，循环继续*/
　　　　{
　　　　　　p=p->next; 　　 /*让p指向下一个结点*/
　　　　　　++j;
　　　　}
　　　　if(!p||j>i)
　　　　　　return ERROR; 　　 /*第i个元素不存在*/
　　　　*e=p->data; 　　 /*取第i个元素的数据*/
　　　　return OK;
　　}

• 单链表的插入

　　/*初始条件：链式线性表L已存在，1<=i<=ListLength(L)*/
　　/*操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1*/
　　Status ListInsert(LinkList *L,int i,ElemType e)
　　{
　　　　int j;
　　　　LinkList p,s;
　　　　p=*L;
　　　　j=1;
　　　　while(p&&j<i)
　　　　{
　　　　　　p=p->next;
　　　　　　++j;
　　　　}
　　　　if(!p||j>i)
　　　　return ERROR;　　 /*第i个元素不存在*/
　　　　s=(LinkList)malloc(sizeof(Node));　　/*生成新结点（C语言标准函数）*/
　　　　s->data=e;
　　　　s->next=p->next; 　　 /*将p的后继结点赋值给s的后继*/
　　　　p->next=s; 　　 /*将s赋值给p的后继*/
　　　　return OK;
　　}

• 单链表的删除

　　/*初始条件：链式线性表L已存在，1<=i<=ListLength(L)*/
　　/*操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1*/
　　Status ListDelete(LinkList *L,int i,ElemType e)
　　{
　　　　int j;
　　　　LinkList p,q;
　　　　p=*L;
　　　　j=1;
　　　　while(p->next&&j<i) 　　 /*遍历寻找第i个元素*/
　　　　{
　　　　　　p=p->next;
　　　　　　++j;
　　　　}
　　　　if(!(p->next)||j>i)
　　　　return ERROR;　　 /*第i个元素不存在*/
　　　　q=p->next;
　　　　p->next=q->next; 　　 /*将q的后继赋值给p的后继*/
　　　　*e=q->data; 　　 /*将q结点中的数据给e*/
　　　　free(q); 　　 /*让系统回收此结点，释放内存*/
　　　　return OK;
　　}

• 单链表的整表创建

　　typedef struct Node *LinkList;/*定义LinkList*/

　　/*头插法
　　　　　随机产生n个元素的值，建立带表头结点的单链线性表L（头插法）*/
　　void CreateListHead(LinkList *L,int n)
　　{
　　　　LinkList p;
　　　　int i;
　　　　srand(time(0)); 　　 /*初始化随机数种子*/
　　　　*L=(LinkList)malloc(sizaof(Node));
　　　　(*L)->next=NULL; 　　 /*先建立一个带头结点的单链表*/
　　　　for(i=0;i<n;i++)
　　　　{
　　　　　　p=(LinkList)malloc(sizaof(Node)); 　　 /*生成新结点*/
　　　　　　p->data=rand()%100+1; 　　 /*随机产生100以内的随机数*/
　　　　　　p->next=(*L)->next;
　　　　　　(*L)->next=p; 　　 /*插入到表头*/
　　　　}
　　}
　　/*尾插法
　　　　　随机产生n个元素的值，建立带表头结点的单链线性表L（尾插法）*/
　　void CreateListHead(LinkList *L,int n)
　　{
　　　　LinkList p,r;
　　　　int i;
　　　　srand(time(0)); 　　 /*初始化随机数种子*/
　　　　*L=(LinkList)malloc(sizaof(Node)); 　　 /*L为整个线性表*/
　　　　r=*L; 　　/*r为指向尾部的结点*/
　　　　for(i=0;i<n;i++)
　　　　{
　　　　　　p=(LinkList)malloc(sizaof(Node));　　 /*生成新结点*/
　　　　　　p->data=rand()%100+1;　　 /*随机产生100以内的随机数*/
　　　　　　r->next=p;　　 /*将表尾终端结点的指针指向新结点*/
　　　　　　r=p; 　　 /*将当前的新结点定义为表尾的终端结点*/
　　　　}
　　　　r->next=NULL; 　　 /*表示当前链表结束*/
　　}

• 单链表的整表删除

　　/*初始条件，链式线性表L已存在、操作结果：将L重置为空表*/
　　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;
　　}

单链表结构与顺序存储结构的差异

• 顺序存储结构用一段连续存储单元依次存储线性表的数据元素。查找：O(1)，插入和删除：O(n)。需要预分配存储空间，分大了，浪费，分小了易发生上溢
• 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素。查找：O(n)，单链表在找出位置的指针后，插入和删除时间复杂度仅为O(1)。不需要分配存储空间，只要有就可以分配，元素个数也不受限制。

若线性表需要频繁查找，很少进行插入和删除操作时，宜采用顺序存储结构。当线性表中的元素变化较大或者根本不知道有多大时，最好用单链表结构。

 静态链表：我们让数组的元素都是由两个数据域组成，data和cur。数组的每个下表都对应一个data和一个cur。数据域data，用来存放数据元素，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标。我们把这种用数组描述的链表叫静态链表。（又称游标实现法）。

　　#define MAXSIZE 1000　　/*存储空间初始分配量*/

　　/*线性表的静态链表存储结构*/

　　typedef struct

　　{

　　　　ElemType data;

　　　　int cur;　　/*游标（Cursor），为0时表示无指向*/

　　}Component,StaticLinkList[MAXSIZE]；

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

以下代码是初始化的数组状态：

　　/*将一维数组space中各分量链成一个备用链表，space[0].cur为头指针，“0”表示空指针*/

　　Status InitList(StaticLinkList space)

　　{

　　　　int i;

　　　　for(i=0;i<MAXSIZE-1;i++)

　　　　　　space[i].cur=i+1;

　　　　space[MAXSIZE-1].cur=0;　　/*目前静态链表为空，最后一个元素的cur为0*/

　　　　return OK；

　　}

　　/*若备用空间链表为非空，则返回分配结点的下标，否则返回0*/

　　为了辨明数组中哪些分量未被使用，解决的办法是将所有未被使用过的及已被删除的分量用游标链成一个备用的链表，每当进行插入时，便可以从备用链表上取得第一个结点作为待插入的新结点。

---手动实现Malloc函数---

　　int Malloc_SSL(StaticLinkList space)

　　{

　　　　int i=space[0].cur;　　/*当前数组第一个元素的存的值*/

　　　　　　　　　　　　　　/*就是要返回的第一个备用空闲的下标*/

　　　　if(space[0].cur)

　　　　　　space[0].cur=space[i].cur;　　/*由于要拿出第一个分量来使用了*/

　　　　　　　　　　　　　　　　　　　/*所以我们就得把它的下一个*/

　　　　　　　　　　　　　　　　　　　/*分量用来做备用*/

　　　　return i;

　　} 

　　Status ListInsert(StaticLinkList L,int i,ElemType e)

　　{

　　　　int j,k,l;

　　　　k=MAXSIZE-1;　　/*注意k首先是最后一个元素的下标*/

　　　　if(i<1||i>ListLength(L)+1)

　　　　　　return ERROR;

　　　　j=Malloc_SSL(L);　　/*获得空闲分量的下标*/

　　　　if(j)

　　　　{

　　　　　　L[j].data=e;　　/*将数值赋值给此分量的data*/

　　　　　　for(l=1;l<=i-1;l++)　　/*找到第i个元素之前的位置*/

　　　　　　　　k=L[k].cur;

　　　　　　L[j].cur=L[k].cur;　　/*把第i个元素之前的cur赋值给新元素的cur*/

　　　　　　L[k].cur=j;　　/*把新元素的下标赋值给第i个元素之前元素的cur*/

　　　　　　return OK;

　　　　}

　　　　return ERROR;

　　}

•  线性表的插入

　　Status ListDelete(staticLinkList L,int i) 　　{ 　　　　int j,k; 　　　　if(j<1||j>ListLength(L)+1) 　　　　　　return ERROR; 　　　　k=MAXSIZE-1; 　　　　for(j=1;j<i-1;j++) 　　　　　　k=L[k].cur; 　　　　L[j].cur=L[k].cur; 　　　　L[k].cur=j; 　　　　Free_SSL(L,j); 　　　　return OK; 　　} ---手动实现Free函数---

　　/*将下标为k的空闲结点回收到备用链表*/
　　void Free_SSL(staticLinkList space,int k)
　　{
　　　　space[k].cur=space[0].cur; 　　 /*把第一个元素的cur值赋给要删除的分量cue*/
　　　　space[0].cur=k; 　　 /*把要删除的分量下标赋值给第一元素的cur*/
　　}

/*初始条件：静态链表L已存在。操作结果：返回L中数据元素的个数*/

　　int ListLength(StaticLinkList L)
　　{
　　　　int j=0;
　　　　int i=L[MAXSIZE-1].cur;
　　　　while(i)
　　　　{
　　　　　　i=L[i].cur;
　　　　　　j++;
　　　　}
　　　　return j;
　　}

静态链表的优点：在插入和删除操作时,只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中插入和删除操作需要移动大量元素的缺点。

缺点：没有解决连续存储分配带来的表长难以确定的问题，失去了顺序存储结构随机存储的特性。

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

　　p=rearA->next;　　/*保存A表的头结点*/

　　rearA->next=rearB->next->next;　　/*将本是指向B表的第一个结点（不是头结点）*/

　　　　　　　　　　　　　　　　　　/*赋值给rearA->next*/

　　q=rearB->next;

　　rearB->next=p;　　/*将原A表的头结点赋值给rearB->next*/

　　free(q);　　/*释放q*/

 双向链表（double linked list）：双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，一个指向直接前驱。

　　/*线性表的双向链表存储结构*/

　　typedef stuct DulNode

　　{

　　　　ElemType data;

　　　　struct DulNode *prior;　　/*直接前驱指针*/

　　　　struct DulNode *next;　　/*直接后继指针*/

　　}DulNode,*DulNode *next;

　　/*操作结果：把s插入到p和p->next之间*/

　　s->prior=p;　　/*把p赋值给s的前驱*/

　　s->next=p->next;　　/*把p->next赋值给s的后继*/

　　p->next->prior=s;　　/*把s赋值给p->next的前驱*/

　　p->next=s;　　/*把s赋值给p的后继*/

　　/*操作结果：删除结点p*/

　　p->prior->next=p->next;　　/*把p->next赋值给p->prior的后继*/

　　p->next->prior=p->prior;　　/*把p->prior赋值给p->next的前驱*/

　　free(p);　　/*释放结点*/

 线性表

顺序存储结构　　　　　　　　链式存储结构

数组　　　　　　　　　　　　单链表　　静态链表　　循环链表　　双向链表

标签：结点,cur,元素,next,链表,线性表
From： https://www.cnblogs.com/cge2ox/p/17534690.html