算法&数据结构 - 线性表之静态链表、循环链表、双向链表

        除了上文所介绍的最常见的单链表，本文简单介绍一下线性的其他链式存储结构表，本篇较多代码。

目录

静态链表

插入、删除操作

优缺点

循环链表

双向链表

线性表总结

---

静态链表

        如果没有指针，无法使用指针指向下一个元素地址，链表也就无法按我们之前所说的那样实现了。那怎么办能既存储数据域（data）的信息又存储指针域（cur）的信息？

        我们用数组来描述链表，这样的链表就叫做静态链表。

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

插入、删除操作

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

优缺点

优点

• 插入、删除时修改游标不需要移动元素，改进了顺序结构中原本复杂的插入、删除操作

缺点 

• 连续存储空间表长难以确定；
• 失去了随机存取的特性。

循环链表

最后一个结点的指针域指到头结点，链表闭合。

将两个循环链表连接起来：

p=rearA->next;   			    /* 保存A表的头结点 */
rearA->next=rearB->next->next;	/* 将本是指向B表的第一个结点（不是头结点）*/
                 				/* 赋值给reaA->next*/
q=rearB->next;
rearB->next=p;				   	/* 将原A表的头结点赋值给rearB->next */
free（q）;					   	/* 释放q */

双向链表

        我们的指针按顺序指下来，在单链表中是不可逆的，也就是通过上一个结点可以找到下一个，但下一个节点找不到上一个。在每个节点中，再设置一个指向前一节点的指针，就成了双向链表。

 如果是循环的双项链表呢？

/*线性表的双向链表存储结构*/
typedef struct DulNode
{
		ElemType data;
		struct DuLNode *prior;    	/*直接前驱指针*/
		struct DuLNode *next;		/*直接后继指针*/
} DulNode, *DuLinkList;
 
 
 
p->next->prior = p = p->prior->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->prior->next=p->next;   	/*把p->next赋值给p->prior的后继*/
p->next->prior=p->prior;	/*把p->prior赋值给p->next的前驱*/
free（p）;					/*释放结点*/

线性表总结

        线性表是最基本、最简单、也是最常用的一种数据结构。线性表是数据结构中的一种，一个线性表是n个具有相同特性的数据元素的有限序列。

 

 

欢迎点赞、收藏、评论区交流，转载标明出处。

-----------------------------

上文连接：

算法&数据结构 - 线性表及其链式存储结构_昊昊该干饭了的博客-CSDN博客本篇主要介绍线性表另一种存储形式，链式存储结构及其操作方法，本篇中量代码。https://blog.csdn.net/qq_52213943/article/details/125824927

下文连接：

敬请期待：栈与队列详解