欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

C++ 循环单链表(带头结点)

程序员文章站 2024-03-21 19:12:04
...

文章目录

总结归纳

  1. 在 DeleteNode 函数中(删除指定结点),如果删除的是最后一个结点,则要特殊处理,需要通过遍历找到该结点的前驱结点,再进行删除操作。
  2. 循环链表比起单链表,它的优势在于:知道一个结点,就可以知道该结点的前驱结点,以致于所有结点;而单链表必须通过头结点才能得到所有结点,否则无法通过已知结点得到前驱结点。
  3. 如果你需要频繁的对表头或者表尾操作,那么循环链表很适合,你只需要在表尾置一个尾指针,或者使用循环双链表。

代码实现

/*
循环单链表(带头结点)
*/

#include <iostream>
#include <string>

using namespace std;

struct LNode {
    int data;    // 数据域
    LNode *next; // 指针域
};

typedef LNode LNode;     // LNode是一个循环单链表的结点
typedef LNode *LinkList; // LinkList是一个循环单链表

// 初始化循环单链表
void InitList(LinkList &L) {
    L = new LNode;
    L->next = L;
}

// 判断循环单链表是否为空
bool Empty(LinkList &L) {
    if (L->next == L) {
        return true;
    } else {
        return false;
    }
}

// 获取循环单链表长度
int GetLength(LinkList &L) {
    LNode *p = L->next;
    int length = 0;
    while (p != L) {
        p = p->next;
        length++;
    }
    return length;
}

// 头插法建立循环单链表
LinkList List_HeadInsert(LinkList &L) {
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->data = e;
        s->next = L->next;
        L->next = s;
        cin >> e;
    }
    return L;
}

// 尾插法建立循环单链表
LinkList List_TailInsert(LinkList &L) {
    LNode *r = L; // r为尾指针
    int e;
    cin >> e;
    while (e != 9999) {
        LNode *s = new LNode;
        s->next = r->next;
        s->data = e;
        r->next = s;
        r = s; // 将r置为新的尾指针
        cin >> e;
    }
    r->next = L; // 尾指针的next置为L
    return L;
}

// 按位查找:查找第i个结点
LNode *GetElem(LinkList &L, int i) {
    if (i < 0) {
        return NULL; // i值不合法
    }
    LNode *p = L;
    int j = 0;
    while (p->next != L && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

// 按值查找:查找数据域为e的结点
LNode *GetLNode(LinkList &L, int e) {
    LNode *p = L->next;
    while (p != L && p->data != e) {
        p = p->next;
    }
    return p;
}

// 查找指定结点的前一个结点
LNode *GetPriorNode(LinkList &L, LNode *p) {
    LNode *s = L;
    while (s->next != p) {
        s = s->next;
    }
    return s;
}

// 查找最后一个结点
LNode *GetLastNode(LinkList &L) {
    LNode *p = L->next;
    while (p->next != L) {
        p = p->next;
    }
    return p;
}

// 前插操作:在p结点之前插入数据e
bool InsertPriorNode(LNode *p, int e) {
    LNode *s = new LNode;
    s->next = p->next;
    s->data = p->data; // 数据后移,模拟结点后移
    p->next = s;
    p->data = e; // 将前结点置为新插入的结点
    return true;
}

// 后插操作:在p结点之后插入数据e
bool InsertNextNode(LNode *p, int e) {
    LNode *q = new LNode;
    q->data = e;
    q->next = p->next;
    p->next = q;
    return true;
}

// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
    if (i < 1) { // i值不合法
        return false;
    }
    // LNode *p = GetElem(L, i - 1); // 遍历查找i-1个结点
    // InsertNextNode(p, 5244);      // 使用后插法
    // 使用前插法,达到同样效果
    LNode *p = GetElem(L, i);
    InsertPriorNode(p, 5244);

    return true;
}

// 删除指定结点
bool DeleteNode(LinkList &L, LNode *p) {
    if (p == L) {
        return false;
    }
    if (p->next == L) {                // 要删除最后一个结点
        LNode *s = GetPriorNode(L, p); // s为p的前驱结点
        s->next = p->next;
        delete p;
    } else {
        LNode *s = new LNode;
        s = p->next;       // 指向被删除结点的后继节点
        p->data = s->data; // 数据前移,模拟结点前移
        p->next = s->next; // 断开与被删除结点的联系
        delete s;
    }

    return true;
}

// 删除p结点的后继结点
bool DeleteNextLNode(LinkList &L, LNode *p) {
    if (p == NULL || p->next == L) {
        return false;
    }
    LNode *s = new LNode;
    s = p->next;
    p->next = s->next;
    delete s;
    return true;
}

// 按位序删除
bool ListDelte(LinkList &L, int i, int &e) {
    if (i < 1) {
        return false;
    }
    /*  // 按结点删除,实现同样效果
    LNode *p = GetElem(L, i); // 被删除结点
    e = p->data;
    DeleteNode(L, p);
    */
    LNode *p = GetElem(L, i - 1);
    e = p->next->data;
    DeleteNextLNode(L, p);
    return true;
}

// 遍历循环单链表
void TraverseList(LinkList &L) {
    if (L->next == L) {
        return;
    }
    LNode *p = L->next; // 指向头指针
    while (p != L) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    LinkList L;
    InitList(L);
    cout << Empty(L) << endl;

    // List_HeadInsert(L); // 头插法
    List_TailInsert(L); // 尾插法
    TraverseList(L);

    InserstList(L, 3, 5244);
    TraverseList(L);
    cout << "长度:" << GetLength << endl;

    int e = -1;
    ListDelte(L, 6, e);
    cout << "被删除的值:" << e << endl;
    TraverseList(L);
    cout << GetElem(L, 5)->next->next->data << endl; // 验证循环链表的效果
}