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

单循环链表的C++实现

程序员文章站 2024-03-21 19:42:10
...

仅供参考

#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);     // 返回L中数据元素个数

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

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

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

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

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

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

// 尾插法:正序输入N个元素值,建立带头结点的单链表  算法复杂度O(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指向头结点
    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){          // L头结点非空
        p = L;          // 存储头结点的地址
        L = L->next;    // 头结点下移
        delete p;
    }
    return OK;
}

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

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

// 获取线性表L中的某个数据元素的内容,通过变量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;
}

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

// 在线性表L中超照值为e的数据元素的位置序号
// 返回L中值为e的数据元素的序号,查找失败返回0;
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;
}

// 在L中第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;
}

// 将线性表L中第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;
}

// 头插法  算法复杂度O(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个元素值,建立带头结点的单链表  算法复杂度O(n)
void CreatList_R(CirLinkList &L, int n){

    L = new CirListNode;
    L->next = nullptr;
    CirListNode *r = L;   // 尾指针r指向头节点
    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;
}

 

相关标签: 循环链表