单循环链表的C++实现

仅供参考

#include <iostream>
using namespace std;

// 函数结果状态代码
#define TRUE    1
#define FALSE   0
#define OK      1
#define ERROR   0
#define INFEASIBLE -1
#define OVERFLOW   -2
#define MAXSIZE    100

// Status 是函数的类型 其值是函数结果状态代码
typedef int Status;

typedef int ElemType;

typedef struct _tag_CirListNode{
    ElemType data;          // 数据域
    struct _tag_CirListNode *next;  // 指针域
}CirListNode, *CirLinkList;

// 单链表的初始化
Status InitCirList(CirLinkList &L);

// 判断链表是否为空
int CirListEmpty(CirLinkList L);

// 单链表的销毁，销毁后不存在
Status DestroyCirList_L(CirLinkList &L);

// 清空链表：链表仍存在，但链表中无元素，成为空链表(头指针和头节点仍然存在)
// 算法思路：依次释放所有节点，并将头结点的指针域设置为空
Status ClearCirList(CirLinkList &L);

// 单链表的表长
int CirListLength(CirLinkList L);     // 返回Ｌ中数据元素个数

// 获取线性表Ｌ中的某个数据元素的内容，通过变量e返回
Status GetElem_L(CirLinkList L, int i, ElemType &e);

// 在线性表Ｌ中查找值为e的数据元素
// 找到，则返回Ｌ中值为e的数据元素的地址，查找失败返回ＮＵＬＬ；
CirListNode* LocateElem_address(CirLinkList L, ElemType e);

// 在线性表Ｌ中按照值为e的数据元素的位置序号
// 返回Ｌ中值为e的数据元素的序号，查找失败返回０；
int LocateElem_value(CirLinkList L, ElemType e);

// 在Ｌ中第i个元素之前插入数据元素e
Status CirLinkInsert_L(CirLinkList &L, int i, ElemType e);

// 将线性表Ｌ中第i个数据元素删除
Status CirListDelete_L(CirLinkList &L, int i, ElemType &e);

// 头插法  算法复杂度Ｏ(n)
void CreateCirList_H(CirLinkList &L, int n);

// 尾插法:正序输入Ｎ个元素值，建立带头结点的单链表  算法复杂度Ｏ(n)
void CreatList_R(CirLinkList &L, int n);

// 遍历链表
Status PrintCirList(CirLinkList L);

// 头插法测试代码
int main() {

    // 创建一个空链表
    CirLinkList L;
    // 初始化链表
    InitCirList(L);
    // 头插法
    CreateCirList_H(L, 5);
    // 遍历链表
    PrintCirList(L);

    // 求线性表的长度
    int length = CirListLength(L);
    cout << "链表长度：" << length << endl;

    // 获取线性表第i个元素的值
    ElemType e;
    int i;
    cout << "查找第i个元素：";
    cin >> i;
    GetElem_L(L, i, e);
    cout << "第 " << i << " 个位置的值： " << e << endl;

    // 获取某个值的地址
    CirListNode *temp;
    cout << "想要获取值为e的地址:";
    cin >> e;
    temp = LocateElem_address(L, e);
    cout << "temp->data: "  << temp->data << endl;

    // 查找某个值的序号
    int index = 0;
    cout << "想要获取值为e的序号:";
    cin >> e;
    index =  LocateElem_value(L, e);
    cout << "值为 " << e << " 的序号: " << index << endl;

    // 插入元素
    cout << "在第几个位置插入元素：";
    cin >> i;
    cout << "插入的值为：";
    cin >> e;
    CirLinkInsert_L(L, i, e);
    length = CirListLength(L);
    cout << "链表长度：" << length << endl;
    // 遍历链表
    PrintCirList(L);

    // 删除元素
    cout << "在第几个位置删除元素：";
    cin >> i;
    int ret = CirListDelete_L(L, i, e);
    if (ret != OK){
        cout << "CirListDelete_L error!" << endl;
        return 0;
    }
    cout << "被删除的值为: " << e << endl;
    // 遍历链表
    PrintCirList(L);

    // 清空链表
    ClearCirList(L);
    // 是否为空
    CirListEmpty(L);
    // 销毁链表
    DestroyCirList_L(L);

    return 0;
}

// 单链表的初始化
Status InitCirList(CirLinkList &L){
    L = new CirListNode;   // 生成新节点作头结点，用头指针Ｌ指向头结点
    L->next = L;  // 将头结点的指针域置空
    return OK;
}

// 判断链表是否为空
int CirListEmpty(CirLinkList L){
    if (L->next != L) {
        cout<<"链表非空";
        return FALSE;
    }
    else {
        cout << "链表为空";
        return TRUE;
    }

}

// 单链表的销毁，销毁后不存在
Status DestroyCirList_L(CirLinkList &L){
    CirListNode *p;
    while (L != L->next){          // Ｌ头结点非空
        p = L;          // 存储头结点的地址
        L = L->next;    // 头结点下移
        delete p;
    }
    return OK;
}

// 清空链表：链表仍存在，但链表中无元素，成为空链表(头指针和头节点仍然存在)
// 算法思路：依次释放所有节点，并将头结点的指针域设置为空
Status ClearCirList(CirLinkList &L){
    CirListNode *p, *q;    // 2个辅助指针
    p = L->next;        // ｐ指向第一个结点
    while (p != L){
        q = p->next;
        delete p;
        p = q;
    }
    L->next = L;
    return OK;
}

// 单链表的表长
int CirListLength(CirLinkList L){     // 返回Ｌ中数据元素个数
    CirListNode *p;
    int i = 0;
    p = L->next;           // p指向第一个结点
    while (p != L){              // 遍历单链表，统计结点数
        p = p->next;
        i++;
    }
    return i;
}

// 获取线性表Ｌ中的某个数据元素的内容，通过变量e返回
Status GetElem_L(CirLinkList L, int i, ElemType &e){
    CirListNode *p;
    p = L->next;
    int j = 1;
    while (p != L && j < i){

        p = p->next;
        j++;
    }
    if ( p == L || j > i) return ERROR;
    e = p->data;
    return OK;
}

// 在线性表Ｌ中查找值为e的数据元素
// 找到，则返回Ｌ中值为e的数据元素的地址，查找失败返回ＮＵＬＬ；
CirListNode* LocateElem_address(CirLinkList L, ElemType e){
    CirListNode *p;
    p = L->next;
    while ( p != L && p->data != e){
        p = p->next;
    }
    return p;
}

// 在线性表Ｌ中超照值为e的数据元素的位置序号
// 返回Ｌ中值为e的数据元素的序号，查找失败返回０；
int LocateElem_value(CirLinkList L, ElemType e){

    CirListNode *p;
    p = L->next;
    int j = 1;
    while (p != L && p->data != e){
        p = p->next;
        j++;
    }
    if (p != L) return j;
    else return 0;
}

// 在Ｌ中第i个元素之前插入数据元素e
Status CirLinkInsert_L(CirLinkList &L, int i, ElemType e){
    CirListNode *p, *s;
    p = L;
    int j = 0;
    while (j < i-1){      // 寻找
        p = p->next;
        j++;
    }
    if ( j>i-1 )
        return ERROR;
    s = new CirListNode;
    s->data = e;

    s->next = p->next;
    p->next = s;
    return OK;
}

// 将线性表Ｌ中第i个数据元素删除
Status CirListDelete_L(CirLinkList &L, int i, ElemType &e){

    if  (i < 1 || i > CirListLength(L)){
        cout << "删除位置不合法！" << endl;
        return ERROR;
    }
    CirListNode *p = L;
    int j = 0;
    while (p->next != L && j < i-1){         // 寻找第i个节点，并令p指向其前驱
        p = p->next;
        j++;
    }
    CirListNode *q = p->next;     //　临时保存被删节点的地址以备释放
    p->next = q->next;         //  改变删除结点前驱节点的指针域
    e = q->data;                // 保存删除节点的数据域
    delete q;                   // 释放删除节点的空间
    return OK;
}

// 头插法  算法复杂度Ｏ(n)
void CreateCirList_H(CirLinkList &L, int n){

    L = new CirListNode;
    L->next = L;  // 先建立一个带头节点的单链表
    L->data = 0;

    for (int i = n; i > 0; --i) {
        auto *p = new CirListNode;     // 生成新结点
        cout << "头插法：";
        cin >> p->data;             // 输入元素值
        p->next = L->next;          // 插入到表头
        L->next = p;
    }
}

// 尾插法:正序输入Ｎ个元素值，建立带头结点的单链表  算法复杂度Ｏ(n)
void CreatList_R(CirLinkList &L, int n){

    L = new CirListNode;
    L->next = nullptr;
    CirListNode *r = L;   // 尾指针ｒ指向头节点
    for (int i = 0; i < n; ++i) {
        auto p = new CirListNode;      // 生成新节点，输入元素值
        cout << "尾插法:";
        cin >> p->data;
        p->next = nullptr;
        r->next = p;            // 插入到表尾
        r = p;          // r 指向新的为结点
    }
}

// 遍历链表
Status PrintCirList(CirLinkList L){

    CirListNode *p = L->next;
    while (p != L){
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
    return OK;
}