《数据结构》—— 循环链表与静态链表

小鱼儿 2022-09-11 03:28 228阅读 0赞

### 循环链表 ###

*   *  一、循环单链表
     *   *  1.1 初始化循环单链表
     *  二、循环双链表
     *   *  2.1 循环双链表初始化思想
         *  2.2 循环双链表的插入、删除操作
     *  三、静态链表
     *   *  3.1 静态链表定义
         *  3.2 静态链表的特点：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]

## 一、循环单链表 ##

循环单链表和单链表的区别在于，表中最后一个结点的指针不是NULL，而改为指向头结点，形成了一个环。  
![在这里插入图片描述][542817594bb34a7191e52c26b671507d.png]  
在循环单链表中，表尾结点 \***r** 的next域指向L，故表中没有指针城为NULL的结点，因此，

*  循环单链表的判空条件不是头结点的指针是否为空，而是它是否等于头指针；
 *  判断结点p为表尾结点，满足p的后继是L。

// 判断循环单链表是否为空
    bool Empty(LinkList L){
        
        if(L->next==L)
            return true;
        else
            return false;
    }
    
    // 判断结点p是否为表尾结点
    bool isTail(LinkList L, LNode *p){
        
        if(p->next==L)
            return true;
        else
            return false;
    }

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

### 1.1 初始化循环单链表 ###

// 循环单链表存储定义
    typedef struct LNode{
        
    	ElemType data;
    	struct LNode *next;
    }LNode, *LinkList;
    
    // 循环单链表初始化
    bool InitList(LinkList &L){
        
        L = (LNode *)malloc(sizeof(LNode)); // 分配头结点
        if(L==NULL)     // 内存不足，分配失败
            return false;
        L->next = L;   // 头结点next指向头结点
        return true;
    }

循环单链表的插入、删除算法与单链表的几乎一样，循环单链表不设头指针而仅设尾指针，从而使得操作效率更高。其原因是，若设的是头指针，对表尾进行操作需要O(n)的时间复杂度，而若设的是尾指针r，r->next 即为头指针，对表头与表尾进行操作都只需要0(1)的时间复杂度。

**【注意】：在表尾进行(插入、删除时）可能需要修改L。**

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

## 二、循环双链表 ##

![在这里插入图片描述][ff423f0b684842b997fb5ec75946112e.png]  
在循环双链表L中，某结点 \*p为尾结点时，p->next==L; 当循环双链表为空表时， 其头结点的prior域和next域都等于L。

### 2.1 循环双链表初始化思想 ###

*  存储定义与双链表一样；
 *  判断结点p是否为表尾结点的思路与循环单链表一样；
 *  判断空表要满足 头结点的前驱、后继==L；
 *  初始化与双链表也一样。

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

### 2.2 循环双链表的插入、删除操作 ###

*  在p结点之后插入s结点；
 *  删除p的后继结点q。

1、后插核心代码
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    ----
    2、后删操作
    p->next=q->next;
    q->next->prior=p;
    free(q);

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

## 三、静态链表 ##

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

**【注意】**：在这里我们默认(游标) next==-1是表尾结束，next==-2 为空闲结点，可以存储。  
![在这里插入图片描述][8031679a9b1441bc9c15da643fb8065a.png]

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

### 3.1 静态链表定义 ###

1、SlinkList a; // a是一个静态链表
    #define Maxsize 10
    typedef struct{
        		//静态链表的最大长度
    	ElemType data;	//静态链表结构类型的定义
    	int next;	    //存储数据元素
    }SlinkList[Maxsize]; //下一个元素的数组下标
    ----
    2、struct Node a[Maxsize]; // a 是一个Node型数组
    #define Maxsize 10
    struct Node{
        		//静态链表的最大长度
    	ElemType data;	//静态链表结构类型的定义
    	int next;	    //存储数据元素
    };
    typedef struct SlinkList[Maxsize]; //SLinkList定义“一个长度为MaxSize的Node型数组”

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

### 3.2 静态链表的特点： ###

**特点：**

*  静态链表以next==-1作为其结束的标志；
 *  静态链表的插入、删除操作与动态链表的相同，只需要修改指针,而不需要移动元素。

**优点:** 增、删操作不需要大量移动元素；  
**缺点:** 不能随机存取，只能从头结点开始依次往后查找；容量固定不可变。

**适用场景：**

*  不支持指针的低级语言;
 *  数据元素数量固定不变的场景(如操作系统的文件分配表FAT )

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZSQ5qi9_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/f152798e58804e9a8627ee614c7854eb.png
[542817594bb34a7191e52c26b671507d.png]: /images/20220828/a142791598a24a698d01600fbe939acc.png
[ff423f0b684842b997fb5ec75946112e.png]: /images/20220828/52ed81d35001403ebd37e60b0c32c291.png
[8031679a9b1441bc9c15da643fb8065a.png]: /images/20220828/3bf373a23f5c4a3289b3a2bd8f6cc6b3.png