双向循环链表

ListBook_Double_Link.h

#pragma once

#ifndef _ListBook_Double_Link_
#define _ListBook_Double_Link_
#include<iostream>
#include <string>
#include <stdlib.h>
#include <malloc.h>
using namespace std;

#define LIST_SIZE sizeof(L_Node)        // 结构体的字节数     

typedef struct Student
{
    int id;
    struct Student * prior;
    struct Student * next;
}L_Node, *List_Node;

class Double_link
{
public:
    /**
        注意使用合理的结构声明，
        Node *       强调结构体
        List_Node    强调指针链表
    */
    bool IsNULL(List_Node L);                               // 判断是否为空表
    L_Node* InitList();                                     // 构建空的线性表
    int  ListLength(List_Node L);                           // 线性表的长度

    bool  GetElem(List_Node L, int cur_e, List_Node &pre_e);// 查找数据

    bool ListInsert(List_Node& L, int i, int e);            // 添加数据e
    bool ListDelete(List_Node& L, int i, int &e);           // 删除 i 位置上的数据

    void FindList(List_Node L);                             // 查看 表的数据
};
// 判断是否为空表
bool Double_link::IsNULL(List_Node L)
{
    return L->prior == L;
}
// 构建空的线性表
L_Node* Double_link::InitList()
{
    L_Node * L = (List_Node)malloc(LIST_SIZE);
    if (!L) exit(1);
    L->prior = L;
    L->next = L;
    return L;
}
// 线性表的长度
int  Double_link::ListLength(List_Node L)
{
    if (this->IsNULL(L))  return 0;
    List_Node p = L;
    int num = 0;
    while (p->next != L)
    {
        p = p->next;
        num++;
    }
    return num;
}

// 查找数据
bool  Double_link::GetElem(List_Node L, int cur_e, List_Node &pre_e)
{
    if (this->IsNULL(L)) return false;
    if (cur_e<0 || cur_e >this->ListLength(L)) return false;

    List_Node p = L;
    int num = 0; // 判断位置
    // 循环链表，到结尾位置，或者 第 i 个位置
    while (p->next != L && num < cur_e)
    {
        p = p->next;
        num++;
    }
    // 返回指针
    pre_e = p;
    return true;
}

// 添加数据e
bool Double_link::ListInsert(List_Node& L, int i, int e)
{
    // i > this->ListLength(L) + 1
    // i 最高可以取到 this->ListLength(L) + 1
    // 当链表长度为 0，是可以直接在 1 的位置添加数据
    // 当链表长度为 2，是可以直接在 3 的位置添加数据
    if (i < 1 || i > this->ListLength(L) + 1 ) return false;

    L_Node * p = (List_Node)malloc(LIST_SIZE);  // 开辟内存空间
    if (!p) exit(1);
    p->id = e;                                  // 为开辟的空间赋值

    L_Node * link = L;                      // 获取L 的地址
    // 注意：link初始化需要设置为L， 因为存在表位空的情况


    this->GetElem(L, i - 1, link);              // 查找前一位的指针位置

    if (link->next == L)
    {
        // 当添加位置到结尾
        p->next = L;            // 新建节点(p)的next指针   指向  开头(L)
        L->prior = p;           // 开头(L)的prior指针        指向  结尾
    }
    else
    {
        p->next = link->next;       // 新建节点(p)的next指针   指向  链表的i+1位置的prior结点
        link->next->prior = p;      // 链表的i+1位置的prior结点 指向 新建节点(p)
    }

    p->prior = link;                // 新建节点(p)的 prior指针  指向 链表的i位置的结点
    link->next = p;                 // 链表的i位置的结点        指向 新建节点(p)
    return true;
}

// 删除 i 位置上的数据
bool Double_link::ListDelete(List_Node& L, int i, int &e)
{

    if (IsNULL(L)) return false;
    if (i < 1 || i > this->ListLength(L)) return false;

    L_Node * p = NULL;
    L_Node * link = NULL ;                          // 获取L 的地址

    this->GetElem(L, i - 1, link);              // 查找前一位的指针位置

    p = link->next;
    e = p->id;
    if (link->next->next == L)
    {
        link->next = L;
    }
    else
    {
        link->next = p->next;
    }
    free(p);
    return true;
}

// 查看 表的数据
void Double_link::FindList(List_Node L)
{
    if (this->IsNULL(L))
    {
        cout << "Not Found message" << endl;
        return;
    }

    List_Node p = L;
    int num = 1;
    while (p->next != L)
    {
        p = p->next;
        cout
            << "第"  << num  << ":"
            << "id ="
            << p->id
            << endl;
        num++;
    }
}
#endif 

测试使用：

#include <iostream>
#include <stdlib.h>
#include "ListBook_Double_Link.h"  // 上边创建的头文件
using namespace std;

void ListBook_Double_Link();
int main()
{
    ListBook_Double_Link();
    system("pause");
    return 0;
}
void ListBook_Double_Link()
{
    Double_link man;
    List_Node L = man.InitList();
    if (man.IsNULL(L))
    {
        cout << "空表" << endl;
    }
    cout << man.ListLength(L) << endl;
    cout << "____________________________" << endl;

    /* 添加数据
        根据链表的长度增加数据
        可以直接在结尾添加数据
        例如表长为5，则可以在6的位置添加数据，7就不能添加
    */
    man.ListInsert(L, 0, 0);    // 不能添加，默认是从第一位开始
    man.ListInsert(L, 1, 1);
    man.ListInsert(L, 2, 2);
    man.ListInsert(L, 3, 3);
    man.ListInsert(L, 4, 4);
    man.ListInsert(L, 2, 6777);
    man.ListInsert(L, 6, 6);
    man.ListInsert(L, 7, 65651651);

    man.FindList(L);            // 遍历查看数据

    cout << "____________________________" << endl;
    // 查找数据
    List_Node pp = NULL;
    man.GetElem(L, 6 ,pp);
    cout
        << "第6个数据为："
        << pp->id
        << endl;

    cout << "____________________________" << endl;
    // 删除数据
    int e = 0;
    man.ListDelete(L, 7, e);
    cout 
        << "删除的数据："
        << e 
        << endl;
    man.FindList(L);
    cout << "____________________________" << endl;
    cout
        << "链表长度："
        << man.ListLength(L) << endl;

}