C語言實作單向循環連結清單

循環連結清單簡介

循環連結清單的結構和單連結清單結構一樣，不過對于單連結清單，每個結點隻存儲了向後的指針，到了尾标志就停止了向後鍊的操作，這樣知道某個結點卻無法找到它的前驅結點。将單連結清單中的終端點的指針由空指針改為指向頭結點，就使整個單連結清單形成一個環，這種頭尾相接的單連結清單稱為循環單連結清單，簡稱循環連結清單。

代碼實踐

data.h

/*
 * @Author: xgh
 * @Date: 2020-06-08 22:52:43
 * @LastEditTime: 2020-06-13 21:44:44
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \VS-CODE-C\.vscode\cycleLinkedLists\data.h
 */ 

#ifndef __DATA_H__
#define __DATA_H__

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SUCCESS 1  // 成功
#define FAILURE 0  // 失敗
#define ERROER 0 // 錯誤
#define NOT_EMPTY 1 // 連結清單不為空
#define EMPTY 0 // 連結清單為空

typedef int Statue;  // 為int取别名，用于區分表示執行狀态的int
typedef int ElemType;  // 資料域類型


/*
循環連結清單的結構和單連結清單結構一樣，不過對于單連結清單，每個結點隻存儲了向後的指針，
到了尾标志就停止了向後鍊的操作，這樣知道某個結點卻無法找到它的前驅結點。
将單連結清單中的終端點的指針由空指針改為指向頭結點，就使整個單連結清單形成一個環，
這種頭尾相接的單連結清單稱為循環單連結清單，簡稱循環連結清單。
*/
typedef struct ClinkNode
{
    ElemType data; //資料域

    // 這裡不能寫成Node *next
    // 因為類型名的作用域是從大括号結尾開始，而在結構體内部不能使用，因為還沒有定義
    // 需要聲明
    struct ClinkNode *next;  // 指針域
}clinkNode; 

// 使用*CLinkLine而不直接使用ClinkNode的原因為：
// 節省空間, 無論ClinkNode中的data有多大, ClinkNode隻占一個指針變量大小
typedef struct ClinkNode *CLinkLine;

#endif

實作代碼

/*
 * @Author: xgh
 * @Date: 2020-06-08 22:43:59
 * @LastEditTime: 2020-06-13 23:43:55
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: \VS-CODE-C\.vscode\cycleLinkedLists\cycleLinkedLists.c
 */ 

#include "data.h"

Statue InitList(CLinkLine *L);
int GetLenght(CLinkLine L);
Statue ListInsert(CLinkLine L, int index, ElemType data);
void showList(CLinkLine L);
Statue ListDelete(CLinkLine L, int index, ElemType *data);
void ClearList(CLinkLine L);
Statue ListEmpty(CLinkLine L);
void DestoryList(CLinkLine *L);
Statue GetElem(CLinkLine L, int index, ElemType *data);
int GetLocation(CLinkLine L, int Elem);
Statue BeforeElem(CLinkLine L, ElemType choose, ElemType *before);

int main(void)
{
    CLinkLine cLine = NULL;
    int i, index = 2;
    ElemType data;

    InitList(&cLine);
    printf("循環連結清單長度為：%d\n\n", GetLenght(cLine));

    for (i = 1; i <= 5; i++)
    {
        ListInsert(cLine, i, i);
    }
    
    ListInsert(cLine, 1, 6);
    printf("插入完成, 循環連結清單長度為：%d\n\n", GetLenght(cLine));
    showList(cLine);

    GetElem(cLine, index, &data);
    printf("第%d個位置的資料為:%d\n", index, data);
    printf("元素6的位置為:%d\n", GetLocation(cLine, 6));

    ListDelete(cLine, 1, &data);
    printf("删除的資料為：%d\n", data);
    showList(cLine);

    BeforeElem(cLine, 5, &data);
    printf("資料5的前驅結點元素為%d\n", data);

    ClearList(cLine);
    printf("表是否為空（1: 不為空, 0: 空）: %d, 表長度為: %d\n", ListEmpty(cLine), GetLenght(cLine));

    DestoryList(&cLine);
    

    return 0;
}

/**
* @description: 建立空循環連結清單
* @param {CLinkLine *L: 二級指針} 
* @return: SUCCESS:建立成功
*/
Statue InitList(CLinkLine *L)
{

    (*L) = (CLinkLine)malloc(sizeof(clinkNode)); // 配置設定記憶體
    if ((*L) == NULL)
    {
        printf("循環連結清單記憶體配置設定失敗\n\n");
        exit(ERROER);
    }

    (*L)->next = (*L); // 指針域指向自己
    printf("循環連結清單記憶體配置設定成功\n\n");
    return SUCCESS;
}

/**
 * @description: 銷毀連結清單
 * @param {CLinkLine *L: 二級指針} 
 * @return: NULL
 */
void DestoryList(CLinkLine *L){
    ClearList((*L)); // 清除表資料
    free((*L)); // 釋放頭結點
    (*L) = NULL; // 頭指針置空

    printf("連結清單銷毀成功\n\n");
}

/**
 * @description: 清空連結清單
 * @param {CLinkLine L: 一級指針} 
 * @return: NULL
 */
void ClearList(CLinkLine L){

    CLinkLine p, q;
    p = L->next; // 指向第一個結點

    // 循環清除結點
    while(p != L){
        q = p->next;  // 擷取要清除的結點的下一結點
        free(p); // 釋放結點
        p = q; // 将要清除的結點的下一結點給到p,以此類推
    }

    L->next = L; // 指向自己
    printf("清除資料結束,連結清單長度為%d\n\n", GetLenght(L));

}

/**
 * @description: 判斷連結清單是否為空
 * @param {CLinkLine L: 一級指針} 
 * @return: EMPTY: 連結清單為空
 * @return: NOT_EMPTY: 連結清單不為空
 */
Statue ListEmpty(CLinkLine L){
    return L != L->next ? NOT_EMPTY : EMPTY;
}

/**
 * @description: 擷取循環連結清單長度
 * @param {CLinkLine L: 一級指針} 
 * @return: len: 表長度
 */
int GetLenght(CLinkLine L)
{
    int len = 0;

    CLinkLine p = L->next; // 指向頭結點

    // 判斷是否到表尾
    while (p != L)
    {
        len++;
        p = p->next;
    }

    return len;
}

/**
 * @description: 周遊連結清單
 * @param {CLinkLine L: 一級指針} 
 * @return: NULL
 */
void showList(CLinkLine L)
{
    CLinkLine p = L->next;
    printf("循環連結清單資料為：");
    while (p != L)
    {
        printf("%4d", p->data);
        p = p->next;
    }

    printf("\n\n");
}

/**
 * @description:  插入資料
 * @param {CLinkLine L: 一級指針} 
 * @param {int index: 插入的位置}
 * @param {ElemType data: 插入的資料}
 * @return: SUCCESS: 删除成功
 */
Statue ListInsert(CLinkLine L, int index, ElemType data)
{

    CLinkLine s, p = L;
    int j = 1;

    // 判斷插入位置是否合法
    if (index <= 0 || index > (GetLenght(L) + 1))
    {
        printf("循環連結清單插入位置不合法\n\n");
        return ERROER;
    }

    // 查找插入結點的前一個結點
    while (j <= (index - 1))
    {
        ++j;
        p = p->next;
    }

    // 生成新結點
    s = (CLinkLine)malloc(sizeof(clinkNode));

    if (s == NULL)
    {
        printf("循環連結清單插入記憶體配置設定失敗\n\n");
        exit(ERROER);
    }

    // 将資料寫入新結點的資料域
    s->data = data;
    // 将新結點的指針域指向插入位置的上一個結點的下一個結點
    s->next = p->next;
    // 将插入位置的上一個結點的指針域指向新結點
    p->next = s;

    //假如插入的位置是表尾，把新的表尾位址給尾指針
    /* if(p == L)
	{
		L = s;
	} */

    return SUCCESS;
}

/**
 * @description: 删除元素
 * @param {CLinkLine L: 一級指針}
 * @param {int index: 插入的位置}
 * @param {ElemType *data: 删除的結點資料存放位址}
 * @return: FAILURE: 删除失敗
 * @return: SUCCESS: 删除成功
 */
Statue ListDelete(CLinkLine L, int index, ElemType *data)
{

    CLinkLine s, p = L;
    int j = 1;

    // 判斷删除的位置是否合法
    if (index < 1 || index > GetLenght(L))
        return FAILURE;

    // 找到删除結點的前一個結點
    while (j <= (index - 1))
    {
        j++;
        p = p->next;
    }

    s = p->next;       // 擷取到要删除的結點
    p->next = s->next; // 将删除結點的後一個結點位址給到上一個結點的指針域

    *data = s->data; // 擷取到删除的資料

    if(s == L)
	    L = p;

    free(s);

    return SUCCESS;
}

/**
 * @description: 擷取表中指定位置的資料 
 * @param {CLinkLine L: 一級指針}
 * @param {int index: 插入的位置}
 * @param {ElemType *data: 删除的結點資料存放位址}
 * @return: FAILURE: 查找位置錯誤
 * @return：SUCCESS: 查找成功
 */
Statue GetElem(CLinkLine L, int index, ElemType *data){

    int j = 1;

    if(index < 0 || index > GetLenght(L)){
        return FAILURE;
    }

    CLinkLine p = L->next; // 指向第一個結點

    while(j < index){  // 找到要查找的結點
        j++;
        p = p->next;
    }

    *data = p->data; // 擷取到資料域資料
    return SUCCESS;
}

/**
 * @description: 擷取元素的位置
 * @param {CLinkLine L: 一級指針}
 * @param {int Elem: 查找的元素}
 * @return: 0: 表中不存在該資料
 * @return: location: 結點位置
 */
int GetLocation(CLinkLine L, int Elem){

    CLinkLine p = L->next;  // 擷取首結點
    int location = 1;

    while (p->data != Elem && p != L)  
    {
        location++;
        p = p->next;
    }

    // 判斷是否是表尾, 到達表尾則元素不存在
    if( p == L){
        return 0;
    }

    return location;
}

/**
 * @description: 查找某元素的前驅結點元素
 * @param {CLinkLine L: 一級指針}
 * @param {ElemType choose: 查找的元素}
 * @param {ElemType *before: 前驅結點元素} 
 * @return: FAILURE: 查找失敗
 * @return: SUCCESS: 查找成功
 */
Statue BeforeElem(CLinkLine L, ElemType choose, ElemType *before){
    // 擷取兩個相鄰結點,判斷第二個結點資料域資料是不是要查找的元素;
    // 是則擷取第一個結點的資料域資料;
    // 否則兩個結點向前移,将第二個結點給到第一個結點,第二個結點next;
    // 當到達表尾還未找到要查找的元素,則傳回查找失敗

    CLinkLine p = L->next; //p,q為相鄰結點,
    CLinkLine q = p->next;

    // 判斷是否達到表尾
    while(q != L){
        // 判斷是否是要尋找的元素
        if(q->data == choose){
            *before = p->data;  // 擷取前驅結點元素
            return SUCCESS;
        }

        p = q; //繼續後移
        q = q->next;
    }

    return FAILURE;
}

C語言實作單向循環連結清單C語言實作單向循環連結清單

C語言實作單向循環連結清單

循環連結清單簡介

代碼實踐

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器