第二章 线性表

2.1 线性表的定义与操作

2.1.1 线性表的定义

线性表是具有相同数据类型的n (n\geqslant0)个数据元素的有限序列，其中n为表长，当n=0
时线性表是一个空表。若用L 命名线性表，则其一般表示为

式中A，a_1是唯一的“第一个”数据元素，又称表头元素；a_n是唯一的“最后一个”数据元素，又称表尾元素。除第一个元素外，每个元素有且仅有一个直接前驱。除最后一个元素外，每个元素有且仅有一个直接后继(“直接前驱”和“前驱”、“直接后继”和“后继”通常被视为同义词)。
以上就是线性表的逻辑特性，这种线性有序的逻辑结构正是线性表名字的由来。
由此，我们得出线性表的特点如下：

• 表中元素的个数有限。
• 表中元素具有逻辑上的顺序性，表中元素有其先后次序。
• 表中元素都是数据元素，每个元素都是单个元素。
• 表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
• 表中元素具有抽象性，即仅讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

线性表是一种逻辑结构，表示元素之间的一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层次的概念，因此不要将其混淆。

2.1.2 线性表的基本操作

一个数据结构的基本操作是指最核心、最基本的操作。其他较复杂的操作可以通过调用其基本操作来实现。线性表的主要操作如下。

• InitList(&L)：初始化表。构造一个空的线性表。
• Length(L)：求表长，返回线性表L的长度，即L中数据元素的个数。
• LocateElem(L,e)：按值查找。在L查找具有给定关键字值的元素。
• GetElem(L,i)：按位查找。获取L中第i个位置的元素的值。
• ListInsert(&L,i,e)：插入。在L中第i个位置上插入给定元素。
• ListDelete(&L,i,&e)：删除。删除表L中第i个位置的元素，并用e返回删除元素的值。
• PrintList(L)：输出。按前后位置顺序输出L的所有元素值。
• Empty(L)：判空。若L为空，返回true，否则返回false。
• DestroyLsit(&L)：销毁。销毁线性表，并释放L所占的内存空间。

基本操作的实现取决于采取哪种存储结构。

2.2线性表的顺序表示

2.2.1顺序表的定义

线性表的顺序存储又称顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。第 1 个元素存储在顺序表的起始位置， 第i个元素的存储位置后面紧接着存储的是第i+1个元素，称i为元素a_i在顺序表中的位序。因此，顺序表的特点是表中元素的逻辑顺序与其存储的物理顺序相同。

假设顺序表 I 存储的起始位置为 LOC(A), sizeof(ElemType)是每个数据元素所占用存
储空间的大小，则表 I所对应的顺序存储如图所示。

每个数据元素的存储位置都和顺序表的起始位置相差一个和该数据元素的位序成正比的常数，因此，顺序表中的任意一个数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。通常用高级程序设计语言中的数组来描述线性表的顺序存储结构。

线性表中元素位序从1开始，数组的元素下标从0开始。

假设线性表的元素类型为ElemType(数据元素的类型)，则静态分配的顺序表结构存储机构描述为

#define MAXSIZE 50
typedef struct{
	ElemType data[MAXSIZE];
	int length;
}SqList;

public class SqLsit {
    public static int DEFAULT_SIZE = 50;
    public ElemType[] data=new ElemType[DEFAULT_SIZE];
    public int length;
}

一维数组可以是静态分配的，也可以是动态分配的。对数组进行静态分配时，因为数组的和空间事先已经固定，所以一旦空间占满再加入新数据就会产生溢出，进而导致程序崩溃。

而在动态分配时，存储数组的空间是在程序执行过程中通过动态存储分配语句分配的，一旦数据空间占满，就另外开辟一块更大的存储空间，将原表中的元素全部拷贝到新空间，从而达到扩充数组存储空间的目的，而不需要为线性表一次性地划分所有空间。
动态分配的顺序表存储结构描状为

#define INITSIZE 100
typedef struct{
	ElemType *data;//数组指针
	int MaxSize,length;
}SqList;

public class SqLsit {
    public static int DEFAULT_SIZE = 50;
    public ElemType[] data;
    public int length;
}

初始动态分配语句为

SqList.data=(ElemType*)malloc(sizeof(ElemType)*INITSIZE);

SqList.data=new EleType[INITSIZE];

public class SqLsit {
    public static int DEFAULT_SIZE = 50;
    public ElemType[] data;
    public int length;
    public SqList(){
        data = new ElemType[DEFAULT_SIZE];
        length = 0;
    }
    public SqList(int size){//size应大于0，否则设为默认值
        if(size<0){
            data = new ElemType[DEFAULT_SIZE];
        }else{
            DEFAULT_SIZE+=size;
            data = new ElemType[DEFAULT_SIZE];
        }
        length = 0;
    }
}

注意，动态分配内存也属于顺序存储结构，物理结构没有变化，依旧是随机存储方式，只是分配的空间大小可以在运行时动态决定。

顺序表的主要优点：

1. 可进行随机访问，即可通过首地址和元素序号可以在O(1)时间内找到指定的元素；
2. 存储密度高，每个结点只存储数据元素。

顺序表的缺点也很明显：

1. 元素的插入和删除需要移动大量的元素，插入操作平均需要移动 n/2 个元素，删除操作平均需要移动(n-1)/2 个元素；

2. 顺序存储分配需要一段连续的存储空间，不够灵活。

2.2.2 顺序表上基本操作的实现

具体实现只考虑算法的实现，不考虑边界、变量定义、内存分配不足等问题。

1. 顺序表的初始化

静态初始化时，数组长度已经被确定，故直接将length设为0即可。

void InitList(SqList &L){
    L.length=0;
}

动态分配的初始化为顺序表分配一个预定义大小的数组空间，并将顺序表的当前长度设为0。MaxSize指示当前顺序表分配的存储空间大小，一旦因插入数据而空间不足，就进行再分配。

void InitList(SqList &L){
    L.data=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);
    L.length=0;
    L.MAXSIZE=INITSIZE;//初始存储容量
}

  //构造函数
	public SqList(){
        data = new ElemType[DEFAULT_SIZE];
        length = 0;
    }
    public SqList(int size){//size应大于0，否则设为默认值
        if(size<0){
            data = new ElemType[DEFAULT_SIZE];
        }else{
            DEFAULT_SIZE+=size;
            data = new ElemType[DEFAULT_SIZE];
        }
        length = 0;
    }

2.插入操作

在顺序表 L的第 i(1<=i<=L.length+1)个位置插入新元素 e。若 i 的输入不合法，则返回 false,表示插入失败；否则，将第 i 个元素及其后的所有元素依次往后移动一个位置，腾出一个空位置插入新元素 e,顺序表长度增加 1,插入成功，返回 true。

index表示索引，即数组的下标从0开始，java实现索引插入，c/c++实现位置插入，后面的代码实现也是如此

bool ListInsert(SqList &L,int i,ElemType e){
    if(i<1||i>L.length+1){//判断越界
        return false;
    }
    if(L.Length>= MAXSIZE){//判断溢出
        return false;
    }
    for(int j=L.length,j>=i;j--){//j是索引，i是位置
        L.data[j]=L.data[j-1];
    }
    L.data[i-1]=e;
    length++;
    return true;
}

    public boolean  insertData(ElemType data,int index) {
        //若length的值为5，则数组最大索引为4，可以在索引为5的位置插入数据。
        if(index < 0 || index >  length){
            System.out.println("索引越界");
            return false;
        }
        if(length >= MAX_SIZE){
            System.out.println("数组已满");
            return false;
        }
        for(int end=length;end>index;end--){
            this.data[end]=this.data[end-1];
        }
        this.data[index] = data;
        length++;
        return true;
    }

最好情况：在表尾插入(即 i=n+1),元素后移语句将不执行，时间复杂度为O(1)。

最坏情况：在表头插入(即i=1),元素后移语句将执行n次，时间复杂度为O(n)。

平均情况：假设p_i(p_i=1/(n+1))是在第i个位置上插入一个结点的概率，则在长度为n的线性表中插入一个结点时，所需移动结点的平均次数为

因此，顺序表插入算法的平均时间复杂度为O(n)。

3.删除操作

删除顺序表 L 中第 i(1<=i<=L.length)个位置的元素，用引用变量 e返回。若 i 的输入不合法，则返回 false;否则，将被删元素赋给引用变量 e,并将第 i+1 个元素及其后的所有元素依次往前移动一个位置，返回 true。

bool ListDelete(SqList &L,int i,ElemType ＆e){
    if(i<1||i>L.length){//判断越界
        return false;
    }
    e=L.data[i-1];
    for(int j=i,j<L.length;j++){//j是索引，i是位置
        L.data[j-1]=L.data[j];
    }
    length--;
    return true;
}

    //为图方便令data的ElemType为int,后续一致
	public boolean deleteData(int index){
        if(index < 0 || index >length){
            System.out.println("索引越界");
            return false;
        }
        int temp=this.data[index];
        //索引范围0~length-1
        for(int i=index;i<length-1;i++){
            this.data[i] = this.data[i+1];
        }
        length--;
        System.out.println("删除索引为"+index+"的数据为："+temp);
        return true;
    }

最好情况：删除表尾元素(即 i=n),无须移动元素，时间复杂度为O(1)。

最坏情况：删除表头元素(即 i=1),需移动除表头元素外的所有元素，时间复杂度为O(n)。

平均情况：假设p_i(p_i=1/n)是删除第i个位置上结点的概率，则在长度为n 的线性表中删
除一个结点时，所需移动结点的平均次数为

因此，顺序表删除算法的平均时间复杂度为O(n)。

可见，顺序表中插入和删除操作的时间主要耗费在移动元素上，而移动元素的个数取决于插入和删除元素的位置。

4.按值查找（顺序查找）

在顺序表L中查找第一个元素值等于e的的元素，并返回其位序。

int LocateList(SqList L,ElemType e){
    for(int i=0,i<L.length;i++){//i是索引
        if(L.data[i]==e){
            return i+1;//返回位置
        }
    }
    return -1;
}

    public int locateData(int data) {
        int index=0;
        for(int temp:this.data){
            if(temp==data){
                return index;
            }
            index++;
        }
        System.out.println("未找到数据");
        return -1;
    }

最好情况：查找的元素就在表头，仅需比较一次，时间复杂度为O(1)。

最坏情况：查找的元素在表尾(或不存在)时，需要比较n次，时间复杂度为O(n)。

平均情况：假设 p_i(p_i=1/n) 是查找的元素在第 i(1<=i<=L.length)个位置上的概率则在长度为n 的线性表中香找值为 e 的元素所需比较的平均次数为

因此，顺序表按值查找算法的平均时间复杂度为O(n)。

顺序表的按序号查找非常简单，即直接根据数组下标访问数组元素，其时间复杂度为O(1)。

2.3线性表的链式表示

顺序表的存储位置可以用一个简单直观的公式表示，它可以随机存取表中任一元素，但插入和删除操作需要移动大量元素。链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。

2.3.1单链表的定义

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

单链表中结点类型的描述如下：

//针对需要时声明，C与C++有所不同，C必须加上struct而C++不需要。C中为了简化声明struct变量，因此常在类型定义时与typedef结合使用。换言之，对于C++，其实可以不与typedef结合使用。
typedef struct LNode{
    ElemType data;
    Struct LNode *Next;
}LNode,*LinkList;//LinkList 头指针,将struct LNode *重命名为linklist

public class LinkListiml<T> implements LinkList<T> {
    //头指针或头结点，取决于构造函数如何初始化
    private Node<T> head;
    public static class Node<T>{
        private T data;
        private Node<T> next;
        Node(){
            this.data=0;
            this.next=null;
        }
        Node(T data,Node<T> next){
            this.data = data;
            this.next = next;
        }
        Node(T data){
            this.data = data;
            this.next = null;
        }
    }
}

利用单链表可以解决顺序表需要大量连续存储单元的缺点，但附加的指针域，也存在浪费存储空间的缺点。由于单链表的元素离散地分布在存储空间中，因此是非随机存取的存储结构，即不能直接找到表中某个特定结点。查找特定结点时，需要从表头开始遍历，依次查找。

通常用头指针 L(或 head 等)来标识一个单链表，指出链表的起始地址，头指针为 NULL 时表示一个空表。此外，为了操作上的方便，在单链表第一个数据结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，但也可以记录表长等信息。单链表带头结点时， 头指针 L指向头结点，表尾结点的指针域为 NULL(用“Λ”表示)。

头结点和头指针的关系：不管带不带头结点，头指针都始终指向链表的第一个结点，而头结点是带头结点的链表中的第一个结点，结A点内通常不存储信息。

引入头结点后，可以带来两个优点：

1. 由于第一个数据结点的位置被存放在头结点的指针域中，因此在链表的第一个位置上的操作和在表的其他位置上的操作一致，无须进行特殊处理。
2. 无论链表是否为空，其头指针都是指向头结点的非空指针(空表中头结点的指针域为空),因此空表和非空表的处理也就得到了统一。

2.3.2单链表上基本操作的实现

本节默认c++实现的链表带头结点，java不带。一定要实现头结点，不然会麻烦点。java只有值传递，对象传递的实际上是该对象的引用值，所以涉及到参数传递时，若要修改该对象的指向修改时要返回给该对象相应的引用值，若对象与该方法位于同一个类中则直接赋值就会修改。而且null传递为值传递，没有开辟新的空间。所以写链表时最好用内部类。

1. 单链表的初始化

带头结点的单链表：

//LNode* &L，直接传入LNode就行，此时为C++的引用
//若定义为LNode* L，传入＆LNode，此时为取地址
bool InitList(LinkList &L){
    L=(LNdoe*)malloc(sizeof(LNode));
    L->next=NULL;
    return true;
}

//构造函数初始化头结点
    public LinkListiml(){
        //不带头结点
        head =new Node<T>();
    }

不带头结点的单链表：

bool InitList(LinkList &L){
	L=NULL;
    return true;
}

//构造函数初始化
    public LinkListiml(){
        //不带头结点
        head =null;
    }

设p为指向链表结点发结构体指针，则*p表示结点本身，(*p).data==p->data。(*(*p).next).data==p->next->data。

2.求表长操作

计算链表中数据结点的个数，需要从一个结点开始依次访问表中每个结点。

//有头结点的求法
int Length(LinkList L){
    int len=0;
    LNode* p=L;
    while(p->next!=NULL){
		p=p->next;
        len++;
    }
    return len;
}

//无头结点的求法
    @Override
    public int getLength() {
        Node<T>  temp = head;

        int length=0;
        while(temp!=null){
            length++;
            temp = temp.next;
        }
        return length;
    }

时间复杂度为O(n)，单链表长度不包含头结点，要注意区分有无头结点的情况。

3.按序号查找节点

//c++实现返回指定位置结点，且有头节点的链表
LNode* GetElem(LinkList L,int i){
    LNode *p=L;
    int j=0;
    while(p!=NULL&&j<i){
        p=p->next;
        j++;
    }
    return p;
}

    @Override
    public Node<T> getNode(int index){
        if(index < 0 || index >getLength()){
            System.out.println("索引越界");
            return null;
        }
        Node<T>  temp = head;
        for(int i=0;i<index;i++){
            temp = temp.next;
        }
        System.out.println("当前索引为"+index+"的数据为："+temp.data);
        return temp;
    }

时间复杂度为O(n)。

4.按值查找表结点

LNode* LocateElem(LinkList L,ElemType e){
    LNode *p=L->next;
    while(p!=NULL&&data!=e){
        p=p->next;
    }
	return p;
}

    public Node<T> locateData(T data) {
        int index=0;
        Node<T> temp = head;
        while(temp!=null){
            if(temp.data == data){
                System.out.println("当前数据为"+data+"的索引为："+index);
                return temp;
            }
            temp = temp.next;
            index++;
        }

        System.out.println("未找到数据");
        return null;
    }

时间复杂度为O(n)。

5.插入结点操作

bool ListInsert(LinkList &L,int i,ElemType e){
    LNode* p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==null)
        return false;
    LNode* s=new [LNode*];
    s->data=e;
    //注意先后顺序
    s->next=p->next;
    p->next=s;
    return true;
}

    public boolean insertNode(T data, int index){
        if(index < 0 || index >getLength()){
            System.out.println("索引越界");
            return false;
        }
        //没有头结点，所以如果要插入第一个节点，则直接将head指向新的节点即可
        if(index==0){
            Node<T> newNode = new Node<>(data);
            newNode.next = head;
            head = newNode;
            return true;
        }
        Node<T> temp = head;
        for(int i=0;i<index-1;i++){
            temp = temp.next;
        }
        Node<T> newNode = new Node<>(data);
        newNode.next = temp.next;
        temp.next = newNode;
        return true;
    }

时间复杂度为O(n)。

扩展：对某一结点进行前插操作。

前插操作是指在某结点的前面插入一个新结点，后插操作的定义刚好与之相反。在单链表插入算法中，通常都采用后插操作。以上面的算法为例，先找到第 i-1 个结点，即插入结点的前驱， 再对其执行后插操作。由此可知，对结点的前插操作均可转化为后插操作，前提是从单链表的头结点开始顺序查找到其前驱结点，时间复杂度为O(n)。

此外，可采用另一种方式将其转化为后插操作来实现，设待插入结点为* s,将* s插入到* p 的前面。我们仍然将* s 插入到* p 的后面，然后将 p->data 与 s->data 交换，这样做既满足逻辑关系，又能使得时间复杂度为O(1)。该方法的主要代码片段如下：

//大体思路为，将待插入结点放在目标结点后面，然后直接交换数据即可实现后插变前插
//s插入p后面
s->next=p->next;
p->next=s;
//交换数据
temp=p->data;
p-data=s->data;
s->data=temp;

6.删除结点操作

bool ListDelete(LinkList &L,int i,ElemType &e){
    LNdoe* p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL||p->next==NULL)
        return false;
    //删除p的后继结点
    LNode* q=p->next;
    e=q->data;
    p->next=q->next;
    free(q);
    return true;
}

    @Override
    public boolean deleteNode(int index){
        if(index < 0 || index >getLength()){
            System.out.println("索引越界");
            return false;
        }
        if(index==0){
            head = head.next;
            return true;
        }
        Node<T> temp = head;
        for(int i=0;i<index-1;i++){
            temp = temp.next;
        }
        temp.next = temp.next.next;
        return true;
    }

同插入算法一样，该算法的主要时间也耗费在查找操作上，时间复杂度为O(n)。当链表不带头结点时，需要判断被删结点是否为首结点，若是，则要做特殊处理，将头指针L指向新的首结点。当链表带头结点时，删除首结点和删除其他结点的操作是相同的。

扩展：删除结点^\starp。

要删除某个给定结点* p,通常的做法是先从链表的头结点开始顺序找到其前驱，然后执行删除操作。其实，删除结点* p 的操作可用删除* p 的后继来实现，实质就是将其后继的值赋予其自身，然后再删除后继，也能使得时间复杂度为O(1)。该方法的主要代码片段如下：

q=p->next;
//用后继结点的数据覆盖当前节点，完成删除p结点
p->data=p->next->data;
p->next=q->next;
free(q);

7.采用头插法建立单链表

LinkList List_HeadInsert(LinkList &L){
	LNode *s;int x;
    L=new [LNode*];
    L->Next=NULL;
    scanf("%d",&x);
    while(x!=9999){
        s=new [LNode*];
        s->data=x;
        s->next=L->next;
        L->next=s;
        scanf("%d",&x);
    }
    return L;
}

    @Override
    public  void insertHeadNode(T data){
        if(head == null){
            head = new Node<T>(data);
            return;
        }
        Node<T> temp = head;
        head=new Node<T>(data,temp);
    }

读入数据的顺序与生成的链表中的元素的顺序是相反的，可用来实现链表的逆置，时间复杂度为O(n)。

8.采用尾插法建立单链表

LinkList List_TailInsert(LinkList &L){
	LNode *s,*r=L;
    int x;
    L=new [LNode*];
    scanf("%d",&x);
    while(x!=9999){
        s=new [LNode*];
        s->data=x;
        r->next=s;
        r=s;
        scanf("%d",&x);
    }
    r->next=null;
    return L;
}

    @Override
    public  void insertTailNode(T data){
        if(head == null){
            head = new Node<T>(data);
            return;
        }
        Node<T> temp = head;
        while (temp.next != null){
            temp= temp.next;
        }
        temp.next = new Node<T>(data);
    }

2.3.3双链表

单链表结点中只有一个指向其后继的指针，使得单链表只能从前往后依次遍历。要访问某个结点的前驱(插入、删除操作时),只能从头开始遍历，访问前驱的时间复杂度为O(n)。为了克服单链表的这个缺点，引入了双链表，双链表结点中有两个指针 prior 和 next,分别指向其直接前驱和直接后继。

typedef stuct DNode{
	ElemType data;
    struct DNode *prior,*next;
}DNode,*DLinkList;

public class DoubleLinkListiml<T> implements DoubleLinkList<T> {

    private Node<T> head;
    public static class Node<T>{
        private T data;
        private Node<T> prior;
        private Node<T> next;
        Node(T data,Node<T> next){
            this.data = data;
            this.next = next;
        }
        Node(T data){
            this.data = data;
            this.next = null;
        }
    }
}

添加了指向前驱的指针prior，所以双链表的按值查找和按位查找的操作与单链表相同。但双链表的插入与删除的相关操作的实现上有些不同。而且可以很方便地找到当前结点的前驱结点，插入删除操作的时间复杂度为O(1)。

1.双链表的插入操作

bool DListInsert(DLinkList &L,int i,ElemType e){
    DNode* p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==null)
        return false;
    DNode* s=new [DNode*];
    s->data=e;
    //多了添加前置节点指针的操作
    p->next->prior=s;
    s->prior=p;
    
    //注意先后顺序
    s->next=p->next;
    p->next=s;
    return true;
}

    @Override
    public boolean insertNode(T data, int index){
        if(index < 0 || index >getLength()){
            System.out.println("索引越界");
            return false;
        }
        //没有头结点，所以如果要插入第一个节点，则直接将head指向新的节点即可
        if(index==0){
            //这里改变一下
            head.prior=new Node<T>(data,null,head);
            head=head.prior;
            return true;
        }
        Node<T> temp = head;
        for(int i=0;i<index-1;i++){
            temp = temp.next;
        }
        //这里
        Node<T> newNode = new Node<>(data,temp,temp.next);
        if(temp.next!=null){
            temp.next.prior = newNode;
        }
        
        temp.next = newNode;
        return true;
    }

2.双链表的删除操作

bool DListDelete(DLinkList &L,int i,ElemType &e){
    DNdoe* p=L;
    int j=0;
    while(p!=NULL&&j<i-1){
        p=p->next;
        j++;
    }
    if(p==NULL||p->next==NULL)
        return false;
    //删除p的后继结点
    DNode* q=p->next;
    e=q->data;
    //区别
    p->next=q->next;
    q->next->prior=p;

    free(q);
    return true;
}

    public boolean deleteNode(int index){
        if(index < 0 || index >getLength()){
            System.out.println("索引越界");
            return false;
        }
        if(index==0){
            head = head.next;
            return true;
        }
        Node<T> temp = head;
        for(int i=0;i<index-1;i++){
            temp = temp.next;
        }
        temp.next = temp.next.next;
		//多了这一句
        if(temp.next!=null){
            temp.next.prior = temp;
        }
        return true;
    }

java实现的头插尾插见github

2.3.4 循环链表

1.循环单链表

循环链表和单链表的区别在于，最后一个结点的指针不是指向NULL，而是指向头结点，从而形成一个环。

循环链表的判空条件为头结点的指针是否等于头指针。

循环单链表的插入、删除算法与单链表的几乎一样，所不同的是若操作是在表尾进行，则执行的操作不同，以让单链表继续保持循环的性质。当然，正是因为循环单链表是一个“环”,所以在任何位置上的插入和删除操作都是等价的，而无须判断是否是表尾。

在单链表中只能从表头结点开始往后顺序漏历整个链表，而循环单链表可以从表中的任意一个结点开始遍历整个链表。有时对循环单链表不设头指针而仅设尾指针，以使得操作效率更高。其原因是，若设的是头指针，对在表尾插入元素需要 O(n)的时间复杂度，而若设的是尾指针 r， r->next 即为头指针，对在表头或表尾插入元素都只需要O(1)的时间复杂度。

2.循环双链表

对于循环双链表，头结点的prior需要指向尾节点，尾节点的next需要指向头结点。

2.3.5静态链表

静态链表是用数组来描述线性表的链式存储结构，结点也有数据域data和指针域next，与前面所讲的链表的指针不同的是，这里的指针是指结点在数组中的相对位置（数组下标），又称游标。跟顺序表一样要分配一块连续的内存空间。

#define MaxSize 50
typedef struct{
    ElemType data;
    int next;
}SLinkList[MaxSize];

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

2.3.6顺序表和链表的比较

1.存取（读/写）方式

顺序表可以顺序存取，也可以随机存取，链表只能从表头开始依次顺序存取。例如在第i个位置上执行存取的操作，顺序表仅需一次访问，而链表则需从表头开始依次访问i次。

2.逻辑结构与物理结构

采用顺序存储时，逻辑上相邻的元素，对应的物理存储位置也相邻。而采用链式存储时，逻辑上相邻的元素，物理存储位置不一定相邻，对应的逻辑关系是通过指针链接来表示的。

3.查找、插入和删除操作

对于按值查找，顺序表无序时，两者的时间复杂度均为O(n);顺序表有序时，可采用折半查找，此时的时间复杂度为O(\log_2n)。对于按序号查找，顺序表支持随机访问，时间复杂度仅为O(1), 而链表的平均时间复杂度为O(n)。顺序表的插入、删除操作，平均需要移动半个表长的元素。链表的插入、删除操作，只需修改相关结点的指针域即可。

4.空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素，则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率降低，而且若内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的结点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活、高效。此外，由于链表的每个结点都带有指针域，因此存储密度不够大。

在实际中如何选取存储结构？

1. 基于存储的考虑

难以估计线性表的长度或存储规模时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储结构的存储密度是小于 1 的。

2. 基于运算的考虑

在顺序表中按序号访问a_i的时间复杂度为O(1),而链表中按序号访问的时间复杂度为O(n),因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。

在顺序表中进行插入、删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长时，这一点是不应忽视的：在链表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑显然后者优于前者。

3. 基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型；链表的操作是基于指针的，相对来讲，前者实现较为简单，这也是用户考虑的一个因素。

总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定。通常较稳定的线性表选择顺序存储，而频繁进行插入、删除操作的线性表(即动态性较强)宜选择链式存储。

链表常用的算法，头插法、尾插法、逆置法、归并法、双指针法。顺序表，归并排序、二分查找等。