数据结构（五）静态链表、循环链表和双向链表

　　一、静态链表

　　　1.静态链表：用数组描述的链表叫做静态链表。C语言中，让数组的元素都是由两个数据域组成，data和cur。数组的每个下标都对应着一个data和一个cur。数据域data，用来存放数据元素，也就是要处理的数据；而cur相当于单链表中的next指针，存放该元素的后继在数据中的下标，把cur叫游标。另外，数组的第一个和最后一个元素作为特殊元素处理，不存数据。数组的第一个元素，即下标为0的元素的cur存放备用链表（未被使用的数组元素）第一个结点的下标，而数组的最后一个元素的cur则存放第一个有数值的元素的下标，相当于单链表中的头结点的作用。

　　2.静态链表的优缺点：

• 在插入和删除操作时，只需要修改游标，不需要移动元素，从而改进了在顺序存储结构中的插入和删除操作需要移动大量元素的缺点。
• 没有解决连续存储分配带来的表长难以确定的问题；失去了顺序存储结构随机存取的特性。

　　3.静态链表的C语言代码实现：

#include "string.h"
#include "ctype.h"      

#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

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

typedef int Status;           /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef char ElemType;        /* ElemType类型根据实际情况而定，这里假设为char */


Status visit(ElemType c)
{
    printf("%c ",c);
    return OK;
}

/* 线性表的静态链表存储结构 */
typedef struct 
{
    ElemType data;
    int cur;  /* 游标(Cursor) ，为0时表示无指向 */
} Component,StaticLinkList[MAXSIZE];


/* 将一维数组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 */
int Malloc_SSL(StaticLinkList space) 
{ 
    int i = space[0].cur;                   /* 当前数组第一个元素的cur存的值 */
                                            /* 就是要返回的第一个备用空闲的下标 */
    if (space[0]. cur)         
        space[0]. cur = space[i].cur;       /* 由于要拿出一个分量来使用了， */
                                            /* 所以我们就得把它的下一个 */
                                            /* 分量用来做备用 */
    return i;
}


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

/*  在L中第i个元素之前插入新的数据元素e   */
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个元素之前元素的ur */
        return OK;   
    }   
    return ERROR;   
}

/*  删除在L中第i个数据元素   */
Status ListDelete(StaticLinkList L, int i)   
{ 
    int j, k;   
    if (i < 1 || i > ListLength(L))   
        return ERROR;   
    k = MAXSIZE - 1;   
    for (j = 1; j <= i - 1; j++)   
        k = L[k].cur;   
    j = L[k].cur;   
    L[k].cur = L[j].cur;   
    Free_SSL(L, j);   
    return OK;   
} 

Status ListTraverse(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
            visit(L[i].data);
            i=L[i].cur;
            j++;
    }
    return j;
    printf("
");
    return OK;
}


int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf("初始化L后：L.length=%d
",ListLength(L));

    i=ListInsert(L,1,'F');
    i=ListInsert(L,1,'E');
    i=ListInsert(L,1,'D');
    i=ListInsert(L,1,'B');
    i=ListInsert(L,1,'A');

    printf("
在L的表头依次插入FEDBA后：
L.data=");
    ListTraverse(L); 

    i=ListInsert(L,3,'C');
    printf("
在L的“B”与“D”之间插入“C”后：
L.data=");
    ListTraverse(L); 

    i=ListDelete(L,1);
    printf("
在L的删除“A”后：
L.data=");
    ListTraverse(L); 

    printf("
");

    return 0;
}


输出为：
初始化L后：L.length=0
在L的表头依次插入FEDBA后：
L.data=A B D E F 
在L的“B”与“D”之间插入“C”后：
L.data=A B C D E F 
在L的删除“A”后：
L.data=B C D E F 

　　4.静态链表的Java语言代码实现：

　　

package bigjun.iplab.staticLinkList;

public class StaticLinkList {

    private Element[] L = null; 
    private int MAXSIZE = 1000;//默认存储大小
    
    class Element{
        int data;
        int cur;
    }

    // 静态链表的初始化
    public StaticLinkList(){
        L = new Element[MAXSIZE];
        for (int i = 0; i < MAXSIZE-1; i++) {
            L[i] = new Element();
            L[i].cur = i+1;
        }
        L[MAXSIZE-1] = new Element();
        L[MAXSIZE-1].cur = 0;
    }
    
    public int listLength() {
        int j = 0;
        int i = L[MAXSIZE-1].cur;
        while (i!=0) {
            i = L[i].cur;
            j++;
        }
        return j;
    }
    
    // 获得静态链表中存放备用链表的第一个结点的下标，即第一个空闲空间的数组下标
    public int mallocSLL() {
        int i = L[0].cur;
        if (L[0].cur!=0) {  // 链表为空时，空闲元素的下标即为1
            L[0].cur = L[i].cur;
        }
        return i;
    }
    
    public void listInsert(int i, int e) throws Exception{
        int k = MAXSIZE-1;
        if (i < 1 || i > listLength() + 1) 
            throw new Exception("超出范围，无法插入");
        int j = mallocSLL();
        if (j!=0) { 
            L[j].data = e;
            for (int l = 1; l <= i -1 ; l++) 
                k = L[k].cur;
            L[j].cur = L[k].cur;
            L[k].cur = j;
        }
    }
    
    public void freeSSL(int k) {
        L[k].cur = L[0].cur;
        L[0].cur = k;
    }
    
    public void listDelete(int i) throws Exception {
        if (i < 1 || i > listLength()) 
            throw new Exception("超出范围，无法删除");
        int k = MAXSIZE - 1 ;
        for (int l = 1; l <= i - 1; l++) 
            k = L[k].cur;
        int j = L[k].cur;
        L[k].cur = L[j].cur;
        freeSSL(j);
    }
    
    public void ListTraverse() {
        int i = L[MAXSIZE-1].cur;
        while (i!=0) {
            System.out.print(L[i].data + " ");
            i = L[i].cur;
        }
    }
    

    
    public static void main(String[] args) throws Exception {
        StaticLinkList sList = new StaticLinkList();
        sList.listInsert(1, 1);
        System.out.print("此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listInsert(1, 2);
        System.out.print("此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listInsert(1, 3);
        System.out.print("此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listInsert(1, 4);
        System.out.print("此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listInsert(1, 5);
        System.out.print("此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listInsert(3, 6);
        System.out.print("在第三个元素之前插入一个值6，此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listDelete(1);
        System.out.print("删除第一个元素后，此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
        
        sList.listDelete(3);
        System.out.print("删除第三个元素后，此时链表的输出为:");
        sList.ListTraverse();
        System.out.println("此时链表的长度为" + sList.listLength());
    }
    
    
}

输出为：
此时链表的输出为:1 此时链表的长度为1
此时链表的输出为:2 1 此时链表的长度为2
此时链表的输出为:3 2 1 此时链表的长度为3
此时链表的输出为:4 3 2 1 此时链表的长度为4
此时链表的输出为:5 4 3 2 1 此时链表的长度为5
在第三个元素之前插入一个值6，此时链表的输出为:5 4 6 3 2 1 此时链表的长度为6
删除第一个元素后，此时链表的输出为:4 6 3 2 1 此时链表的长度为5
删除第三个元素后，此时链表的输出为:4 6 2 1 此时链表的长度为4

　　二、循环链表

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

　　2.循环链表和单链表的主要差异就在于循环的判断条件上，原来是判断p->next是否为空，现在则是判断p->nex不等于头结点，则循环未结束。

　　3.为了用O(1)的时间由链表指针访问到最后一个结点，可以采用这样的方法：不使用头指针，而是用指向终端结点的尾指针来表示循环链表，此时查找开始结点和终端结点都很方便了。即终端结点用尾指针rear指示，而头结点就是rear->next，开始结点就是rear->next->next。

　　三、双向链表

　　1.双向链表：在单链表的每个结点中，再设置一个指向其前驱结点的指针域。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。

　　2.双向链表也可以有循环链表，即对于某一结点p，它的后继的前驱是它自己，它的前驱的后继还是它自己：p->next->prior = p = p->prior->next。

　　3.双向链表在插入和删除时，需要改变两个指针变量：

　　（1）插入时：假设要将存储元素e的结点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的后继

　　（2）删除时：假设要将结点p删除

p->prior->next = p->next;     // 把p->next 赋值给p->prior的后继
p->next->prior = p->prior;    // 把p->prior赋值给p->next 的前驱
free(p);