2.3 静态链表 循环链表 双向链表

（注意：所有代码均已成功测试。编译环境：devC++）

1. 静态链表

用数组描述的链表叫做静态链表，又称游标实现法。

首先，让数组的元素都是由两个数据域组成,data和cur。即为,数组的每一个下标都对应一个data和一个cur。数据域data，用来存放数据元素，而cur相当于单链表中的next指针，存放该元素的后继在数组中的下标，我们通常把cur叫做下标。

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

//线性表的静态链表存储结构
#define MAXSIZE 1000  //存储空间初始分配量 
typedef struct 
{
    ElemType data;
    int cur;  //游标(Cursor),为0时表示无指向
} StaticLinkList[MAXSIZE];

另外，对数组第一个和最后一个元素作为特殊元素处理，不存数据。通常把未被使用的数组元素称为备用链表。而数组第一个元素，即下标为0的元素的 cur就存放备用链表的第一个结点的下标，而数组的最后一个元素的 cur 则存放第一个有数值的元素的下标。

静态链表的初始化：

/* 将一维数组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;
}

静态链表的元素个数：

/* 初始条件：静态链表L已存在。操作结果：返回L中数据元素个数 */
int ListLength(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
        i=L[i].cur;
        j++;
    }
    return j;
}

静态链表的插入：

/* 若备用空间链表非空，则返回分配的结点下标，否则返回0 */
int Malloc_SSL(StaticLinkList space) 
{ 
	int i = space[0].cur;           		//当前数组第一个元素的cur存的值
	                                		//就是要返回的第一个备用空闲的下标
	if (space[0]. cur)         
	    space[0]. cur = space[i].cur;       //由于要拿出一个分量来使用了,所以我们就得把它的下一个分量用来做备用 
	return i;
}

/*  在L中第i个元素之前插入新的数据元素e   */
Status ListInsert(StaticLinkList L, int i, ElemType e)   
{  
    int j, k, l;   
    k = MAXSIZE - 1;   
    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;   
}

静态链表的删除：

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

//画个图就理解了！！！

/*  删除在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;   
} 

静态链表的打印：

void ListTraverse(StaticLinkList L)
{
    int j=0;
    int i=L[MAXSIZE-1].cur;
    while(i)
    {
		printf(\"%c \",L[i].data);
        i=L[i].cur;
        j++;
    }
    printf(\"\\n\");
}

代码测试：

int main()
{
    StaticLinkList L;
    Status i;
    i=InitList(L);
    printf(\"初始化L后：L.length=%d\\n\",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(\"\\n在L的表头依次插入FEDBA后：\\nL.data=\");
    ListTraverse(L); 

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

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

    printf(\"\\n\");

    return 0;
}

小结：静态链表的优缺点

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

缺点：没有解决连续存储分配带来的表长难以确定的问题。

失去了顺序存储结构随机存取的特性。

2. 循环链表

将单链表中的终端结点的指针端由空指针改为指向头节点，就可以使整个链表形成一个环，这种头尾相连的链表称为单循环链表，简称循环链表。
它可以解决一个很麻烦的问题：如何从当中一个结点出发，访问到链表的全部结点。

循环链表带有空节点的循环链表：

非空循环链表：

注意：循环链表和单链表的主要差异就在于判断条件上，原来是判断p->next是否为空，现在则是p->next是否为头节点。

将两个循环链表合并成一个表(使用尾指针)：

p=rearA->next;   			    
rearA->next=rearB->next->next;	
                 				
q=rearB->next;
rearB->next=p;				   	
free（q）;					    

3. 双向链表

双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域。

所以在双向链表中的结点都有两个指针域，一个指向直接后继，一个指向直接前驱。

/*线性表的双向链表存储结构*/
typedef struct DulNode
{
		ElemType data;
		struct DuLNode *prior;    	/*直接前驱指针*/
		struct DuLNode *next;		/*直接后继指针*/
} DulNode, *DuLinkList;

双向循环链表：

双向链表的循环带头结点的空链表：

非空的循环带头结点的双向链表：

p->next->prior = p = p->prior->next

双向循环链表的插入：

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

双向循环链表的删除：

p->prior->next=p->next; 
p->next->prior=p->prior;	
free（p）;				

第二章学习结构图：

第二章完！

希望可以对大家有帮助，若发现错误请及时反馈。