408 第一章链表代码

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

408 第一章链表代码

作者：

s12345333 , 2021-10-05 21:04:15 , 所有人可见 , 阅读 285

0

1

#include<iostream>
#include<algorithm>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList

//初始化单链表
bool InitList(LinkList& L) {
    L = NULL;
    return true;
}

//按位查找，返回第i个元素（不带带头节点）
LNode* GetElem(LinkList L, int i) {
    if (i <= 0) return NULL;
    int j = 1;
    LNode* p = L;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L;
    while (p && p->data != e) {
        p = p->next;
    }
    return p;
}

//统计单链表的长度
int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}


//不带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1) return false;
    if (i == 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode* p;
    p = L;
    int j = 1;  //当前p指向的是第几个节点，没有头节点，所以从1开始
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p) return false;
    return InsertNextNode(p, e);
}

//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
    if (!p || !s) return false;
    s->next = p->next;
    p->next = s;
    swap(s->data, p->data);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
    if (L == NULL) {
        e = -1;
        return false;
    }
    if (i < 1) return false;
    if (i > 1) {
        LNode* p = GetElem(L, i - 1);
        if (!p || !(p->next)) return false;
        LNode* q = p->next;
        e = q->data;
        p->next = q->next;
        free(q);
    }
    else {
        if (L->next == NULL) {
            e = L->data;
            L = NULL;
        }
        else {
            e = L->data;
            L = L->next;
        }
    }

    return true;
}

//删除指定节点P
bool DeleteNode(LNode* p) {
    if (p->next == NULL) return false;
    //下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
    LNode* q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}


//尾插法，不带头结点
LinkList List_TailInsert(LinkList& L) {
    InitList(L);
    LNode* s, * r = L ; //r表示表尾指针
    int x;
    bool is_head = true;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));

        if (is_head) {
            is_head = false;
            s->data = x;
            L = s;
            r = s;
        }
        s->data = x;
        r->next = s;
        r = s;

    }
    r->next = NULL;
    return L;
}

//头插法，不带头结点
LinkList List_HeadInsert(LinkList& L) {
    InitList(L);
    LNode* s;
    int x;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L;
        L = s;
    }
    return L;
}

void print(LinkList L) {
    LNode* s = L;
    while (s!= NULL) {

        cout << s->data << " ";
        s = s->next;
    }
    cout << endl;
}

int main() {

    LinkList L;
    List_HeadInsert(L);
    cout << "头插法的结果" << endl;
    print(L);
    //List_TailInsert(L);
    //cout << "尾插法的结果" << endl;
    //print(L);
    cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
    cout << "链表的长度：" << Length(L) << endl;
    int e;
    ListDelete(L, 5, e);
    cout << "删除的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 5, e);
    cout << "插入的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    LNode* s = LocateElem(L, 5);

    return 0;
}

单链表带头节点

#include<iostream>
#include<algorithm>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, *LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList

//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    int j = 0;
    LNode* p = L;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L->next;
    while (p && p->data!=e) {
        p = p->next;
    }
    return p;
}

//统计单链表的长度
int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next) {
        len++;
        p = p->next;
    }
    return len;
}

//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode *p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (!p) return false;
    return InsertNextNode(p, e);
}

//不带头节点的插入操作，在第i个位置插入元素e
bool NoHead_ListInsert(LinkList& L, int i, int e) {
    if (i < 1) return false;
    if (i == 1) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = L;
        L = s;
        return true;
    }
    LNode* p;
    p = L;
    int j = 1;  //当前p指向的是第几个节点，没有头节点，所以从1开始
    while (p && j < i - 1) {
        p = p->next;
        j++;
    }
    if (!p) return false;
    return InsertNextNode(p, e);
}

//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
    if ( !p || !s ) return false;
    s->next = p->next;
    p->next = s;
    swap(s->data , p->data);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (!p || !(p->next)) return false;
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

//删除指定节点P
bool DeleteNode(LNode* p) {
    if (p->next == NULL) return false;
    //下面这段代码有bug，不能删除最后一个节点，因此要是删除最后一个节点的话要重新进行操作
    LNode* q = p->next;
    p->data = q->data;
    p->next = q->next;
    free(q);
    return true;
}

bool InitList(LinkList& L) {
    L = (LNode* )malloc(sizeof(LNode));//分配一个头节点
    if (!L) return false;
    L->next = NULL;
    return true;
}

//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode* s, * r = L;  //r表示表尾指针
    int x;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = NULL;
    return L;
}

//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
    L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    LNode* s;
    int x;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
    }
    return L;
}

void print(LinkList L) {
    LNode* s = L;
    while (s->next!=NULL) {
        s = s->next;
        cout << s->data << " ";
    }
    cout << endl;   
}

int main() {

    LinkList L;
    //List_HeadInsert(L);
    //cout << "头插法的结果" << endl;
    //print(L);
    List_TailInsert(L);
    cout << "尾插法的结果" << endl;
    print(L);
    cout << "链表的第2个元素："<< GetElem(L, 2)->data << endl;
    cout << "链表的长度："<< Length(L) << endl;
    int e;
    ListDelete(L, 3, e);
    cout << "删除的第3个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 3, e);
    cout << "插入的第3个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    LNode* s = LocateElem(L, 5);

    return 0;
}

双链表

#include<iostream>

using namespace std;

typedef int ElemType;

typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
}DNode, * DLinkList;

//初始化双链表
bool InitDLinkList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }
    L->prior = NULL;
    L->next = NULL;
    return true;
}

//判断双链表是否为空
bool empty(DLinkList L) {
    if (L->next = NULL) {
        return true;
    }
    return false;
}

//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
    if (i < 0) return NULL;
    int j = 0;
    DNode* p = L;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
    DNode* p = L;
    if (p == NULL) return NULL;
    p = p->next;
    while (p != NULL && p->data != e) {
        p = p->next;
    }
    return p;
}

//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
    if (p == NULL || s == NULL) {
        return false;
    }
    s->next = p->next;
    if(p->next != NULL)
        p->next->prior = s;
    s->prior = p;
    p->next = s;
}

//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
    if (p == NULL) return false;
    DNode* q = (DNode*)malloc(sizeof(DNode));
    if (q == NULL) return false;
    q->data = e;
    q->next = NULL;
    q->prior = p;
    if (p->next != NULL) {
        p->next->prior = q;
        q->next = p->next;
    }
    p->next = q;
    return true;
}

//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
    return InsertNextDNode(p->prior, s);
}

//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
    if (i <= 0) return false;
    DNode* p = GetElem(L, i - 1);
    return InsertNextDNode(p, e);
}

//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
    if (p == NULL) return false;
    DNode* q = p->next;
    if (q == NULL) return false;
    p->next = q->next;
    if (q->next != NULL) q->next->prior = p;
    free(q);
    return true;
}

//销毁双链表
bool DestoryList(DLinkList& L) {
    while (L->next != NULL) {
        DeleteNextNode(L);
    }
    free(L);
    L = NULL;
    return true;
}

//尾插法
DLinkList List_TailInsert(DLinkList& L) {
    InitDLinkList(L);
    DNode* p = L;
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(p, x);
        p = p->next;
    }
    return L;
}

//头插法
DLinkList List_HeadInsert(DLinkList& L) {
    InitDLinkList(L);
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(L, x);
    }
    return L;
}

int Length(DLinkList L) {
    DNode* p = L;
    int len = 0;
    while (p->next != NULL) {
        len++;
        p = p->next;
    }
    return len;
}


//删除指定节点s
bool DeleteNode(DNode* s) {
    DNode* p;
    p = s->prior;
    p->next = s->next;
    if (s->next != NULL) {
        s->next->prior = p;
    }
    free(s);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
    if (i <= 0 || i > Length(L)) return false;
    DNode* s;
    s = GetElem(L, i);
    if (s == NULL) return false;
    e = s->data;
    return DeleteNode(s);
}


void print(DLinkList L) {
    DNode* p = L->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void testDLinkList() {
    DLinkList L;
    //cout << "头插法" << endl;
    //List_HeadInsert(L);
    //print(L);
    cout << "尾插法" << endl;
    List_TailInsert(L);
    print(L);
    cout << "长度：" << Length(L) << endl;
    cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
    cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
    cout << "在第一个位置插入元素0" << endl;
    InsertDLinkList(L, 1, 0);
    print(L);
    cout << "在最后一个位置插入元素6" << endl;
    InsertDLinkList(L, 7, 6);
    print(L);

    int e;
    ListDelete(L, 1, e);
    cout << "删除第一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    ListDelete(L, 6, e);
    cout << "删除最后一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    DestoryList(L);
}

int main() {

    testDLinkList();
    return 0;
}

循环单链表 L(表头)

#include<iostream>
#include<algorithm>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
    if (L == NULL) return false;
    L->next = L;
    return true;
}

//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    if (i == 0) return L;
    int j = 1;
    LNode* p = L->next;
    while (p != L && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L->next;
    while (p != L && p->data != e) {
        p = p->next;
    }
    if (p->data == e) return p;
    return NULL;
}

//统计单链表的长度
int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next != L) {
        len++;
        p = p->next;
    }
    return len;
}

//后插操作，在节点p之后插入元素e
bool InsertNextNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (!p) return false;
    return InsertNextNode(p, e);
}


//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
    if (!p || !s) return false;
    s->next = p->next;
    p->next = s;
    swap(s->data, p->data);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (p == NULL || p->next == L) return false;
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
    LNode* q = p->next;
    p->data = q->data;
    p->next = q->next;

    if (L == q) {
        L = p;
    }
    free(q);
    return true;
}

//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
    InitList(L);
    LNode* s, * r = L;  //r表示表尾指针
    int x;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = L;
    return L;
}

//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
    InitList(L);
    LNode* s, * r = L;
    int x;
    bool isFirst = true;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        if (isFirst) {
            r = s;
            isFirst = false;
        }
    }
    r->next = L;
    return L;
}

bool Empty(LinkList L) {
    if (L->next == L) {
        return true;
    }
    return false;
}

//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
    if (p->next == L) return true;
    return false;
}

void print(LinkList L) {
    LNode* s = L->next;
    while (s != L) {

        cout << s->data << " ";
        s = s->next;
    }
    cout << endl;
}

int main() {

    LinkList L;
    //List_HeadInsert(L);
    //cout << "头插法的结果" << endl;
    //print(L);
    List_TailInsert(L);
    cout << "尾插法的结果" << endl;
    print(L);
    cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
    cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
    cout << "链表的长度：" << Length(L) << endl;
    int e;

    ListDelete(L, 5, e);
    cout << "删除的第5个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 5, e);
    cout << "插入的第5个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);

    ListDelete(L, 1, e);
    cout << "删除的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 1, e);
    cout << "插入的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);

    LNode* s = LocateElem(L, 5);
    DeleteNode(L, s);
    print(L);

    return 0;
}
/*
输入样例：
1 2 3 4 5
*/

循环双链表 L指向表尾

#include<iostream>
#include<algorithm>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode* next;
}LNode, * LinkList;
//struct LNode*  == LinkList
//强调节点  用LNode
//强调链表  用LinkList

bool InitList(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));//分配一个头节点
    if (L == NULL) return false;
    L->next = L;
    return true;
}

//按位查找，返回第i个元素（带头节点）
LNode* GetElem(LinkList L, int i) {
    if (i < 0) return NULL;
    if (i == 0) return L->next;
    int j = 1;
    LNode* p = L->next->next;
    while (p != L->next && j < i) {
        p = p->next;
        j++;
    }
    if (p == L->next) return NULL;
    return p;
}

//按值查找，找到数据域等于e的节点
LNode* LocateElem(LinkList L, int e) {
    LNode* p = L->next->next;
    while (p != L->next && p->data != e) {
        p = p->next;
    }
    if (p->data == e) return p;
    return NULL;
}

//统计单链表的长度
int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next != L) {
        len++;
        p = p->next;
    }
    return len;
}

//后插操作，在节点p之后插入元素e
bool InsertNextNode(LinkList& L, LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    if (p == L) L = s;
    return true;
}

//带头节点的插入操作，在第i个位置插入元素e
bool ListInsert(LinkList& L, int i, int e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (!p) return false;
    return InsertNextNode(L, p, e);
}


//前插操作，在p节点前插入元素e
bool InsertPriorNode(LNode* p, int e) {
    if (!p) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    if (!s) return false;
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

//前插操作，在节点p之前插入节点s
bool InsertPriorNode(LNode* p, LNode* s) {
    if (!p || !s) return false;
    s->next = p->next;
    p->next = s;
    swap(s->data, p->data);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(LinkList& L, int i, int& e) {
    if (i < 1) return false;
    LNode* p = GetElem(L, i - 1);
    if (p == NULL || p == L) return false;
    if (p->next == L) {
        L = p;
    }
    LNode* q = p->next;
    e = q->data;
    p->next = q->next;
    free(q);
    return true;
}


//删除指定节点P
bool DeleteNode(LinkList& L, LNode* p) {
    LNode* q = p->next;
    p->data = q->data;
    p->next = q->next;

    if (L == p) {       //尾节点
        q = p;
        while (q->next != p) {
            q = q->next;
        }
        L = q;
    }
    //free(q)；   不能这样写，因为指针之间的赋值是指向同一块区域，就比如L和q就是指向相同的区域
    return true;
}

//尾插法，带头结点
LinkList List_TailInsert(LinkList& L) {
    InitList(L);
    LNode* s, * r = L;  //r表示表尾指针
    int x;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
    }
    r->next = L;
    L = r;
    return L;
}

//头插法，带头结点
LinkList List_HeadInsert(LinkList& L) {
    InitList(L);
    LNode* s, * r = L;
    int x;
    bool isFirst = true;
    while (cin >> x) {
        s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        if (isFirst) {
            r = s;
            isFirst = false;
        }
    }
    r->next = L;
    L = r;
    return r;
}

bool Empty(LinkList L) {
    if (L->next == L) {
        return true;
    }
    return false;
}

//判断是否为表尾节点
bool isTail(LinkList L, LNode* p) {
    if (p == L) return true;
    return false;
}

void print(LinkList L) {
    LNode* s = L->next->next;
    while (s != L->next) {

        cout << s->data << " ";
        s = s->next;
    }
    cout << endl;
}

int main() {

    LinkList L;
    //List_HeadInsert(L);
    //cout << "头插法的结果" << endl;
    //print(L);
    List_TailInsert(L);
    cout << L->data << endl;
    cout << "尾插法的结果" << endl;
    print(L);
    cout << "链表的第1个元素：" << GetElem(L, 1)->data << endl;
    cout << "链表的第5个元素：" << GetElem(L, 5)->data << endl;
    cout << "链表的长度：" << Length(L) << endl;
    int e;

    ListDelete(L, 5, e);
    cout << "删除的第5个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 5, e);
    cout << "插入的第5个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);

    ListDelete(L, 1, e);
    cout << "删除的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);
    ListInsert(L, 1, e);
    cout << "插入的第1个元素是：" << e << endl;
    cout << "当前的链表" << endl;
    print(L);

    LNode* s = LocateElem(L, 5);
    DeleteNode(L, s);
    print(L);

    return 0;
}
/*
输入样例：
1 2 3 4 5
*/

循环双链表

#include<iostream>

using namespace std;

typedef int ElemType;

typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
}DNode, * DLinkList;

//初始化双链表
bool InitDLinkList(DLinkList& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (L == NULL) {
        return false;
    }
    L->prior = L;
    L->next = L;
    return true;
}

//判断双链表是否为空
bool empty(DLinkList L) {
    if (L->next = L) {
        return true;
    }
    return false;
}

bool isTail(DLinkList L, DNode* p) {
    if (p->next == L) return true;
    return false;
}

//按位查找：返回第i个结点
DNode* GetElem(DLinkList L, int i) {
    if (i < 0) return NULL;
    if (i == 0) return L;
    int j = 1;
    DNode* p = L->next;
    while (p != L && j < i) {
        p = p->next;
        j++;
    }
    if (p == L) return NULL;
    return p;
}

//按值查找：找到第一个数据域为e的结点
DNode* LocateElem(DLinkList L, ElemType e) {
    DNode* p = L;
    if (p == NULL) return NULL;
    p = p->next;
    while (p != L && p->data != e) {
        p = p->next;
    }
    if (p == L) return NULL;
    return p;
}

//在p节点之后插入s节点
bool InsertNextDNode(DNode* p, DNode* s) {
    if (p == NULL || s == NULL) {
        return false;
    }
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
}

//在p节点后面插入值是e的节点
bool InsertNextDNode(DNode* p, ElemType e) {
    if (p == NULL) return false;
    DNode* q = (DNode*)malloc(sizeof(DNode));
    if (q == NULL) return false;
    q->data = e;
    q->prior = p;
    p->next->prior = q;
    q->next = p->next;
    p->next = q;
    return true;
}

//前插，在p节点前面插入节点s
bool InsertPriorDnode(DNode* p, DNode* s) {
    return InsertNextDNode(p->prior, s);
}

//按位插入，在第i个位置插入值为e的节点（位序i）
bool InsertDLinkList(DLinkList& L, int i, ElemType e) {
    if (i <= 0) return false;
    DNode* p = GetElem(L, i - 1);
    return InsertNextDNode(p, e);
}

//删除p节点的后继节点
bool DeleteNextNode(DNode* p) {
    if (p == NULL) return false;
    DNode* q = p->next;
    p->next = q->next;
    q->next->prior = p; 
    free(q);
    return true;
}

//销毁双链表
bool DestoryList(DLinkList& L) {
    while (L->next != L) {
        DeleteNextNode(L);
    }
    free(L);
    L = NULL;
    return true;
}

//尾插法
DLinkList List_TailInsert(DLinkList& L) {
    InitDLinkList(L);
    DNode* p = L;
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(p, x);
        p = p->next;
    }
    return L;
}

//头插法
DLinkList List_HeadInsert(DLinkList& L) {
    InitDLinkList(L);
    ElemType x;
    while (cin >> x) {
        InsertNextDNode(L, x);
    }
    return L;
}

int Length(DLinkList L) {
    DNode* p = L;
    int len = 0;
    while (p->next != L) {
        len++;
        p = p->next;
    }
    return len;
}


//删除指定节点s
bool DeleteNode(DNode* s) {
    DNode* p;
    p = s->prior;
    p->next = s->next;
    s->next->prior = p;
    free(s);
    return true;
}

//删除位序i的节点，e是i节点的值
bool ListDelete(DLinkList& L, int i, ElemType& e) {
    if (i <= 0 || i > Length(L)) return false;
    DNode* s;
    s = GetElem(L, i);
    if (s == NULL) return false;
    e = s->data;
    return DeleteNode(s);
}


void print(DLinkList L) {
    DNode* p = L->next;
    while (p != L) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

void testDLinkList() {
    DLinkList L;
    //cout << "头插法" << endl;
    //List_HeadInsert(L);
    //print(L);
    cout << "尾插法" << endl;
    List_TailInsert(L);
    print(L);
    cout << "长度：" << Length(L) << endl;
    cout << "第1个元素为：" << GetElem(L, 1)->data << endl;
    cout << "第5个元素为：" << GetElem(L, 5)->data << endl;
    cout << "在第一个位置插入元素0" << endl;
    InsertDLinkList(L, 1, 0);
    print(L);
    cout << "在最后一个位置插入元素6" << endl;
    InsertDLinkList(L, 7, 6);
    print(L);

    int e;
    ListDelete(L, 1, e);
    cout << "删除第一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    ListDelete(L, 6, e);
    cout << "删除最后一个节点：" << e << endl;
    cout << "当前链表为" << endl;
    print(L);

    DestoryList(L);
}

int main() {

    testDLinkList();
    return 0;
}

0 评论

App 内打开