数据结构_链式表

一、数据结构链式表的实现

//
// Created by XuYiMing on 2020/2/3.
//

#include <cstdio>
#include <cstdlib>
#include <iostream>

#define MaxSize 100

typedef int ElemType;

using namespace std;

//////////////////单链表//////////////
typedef struct LNode {
    ElemType data;
    struct LNode *next;
} LNode, *LinkList; // *LinkList表示人为增加的头结点，也可以用LNode *表示，LinkList是全局变量 指向头结点，可以这样定义：LNode *LinkList

//头插法建立单链表（输出时会得到反序的链表）
LinkList List_HeadInsert(LinkList &L) {     //时间复杂度为O(n)
    int x;
    LinkList s;     //LNode *s;
    L = (LinkList) malloc(sizeof(LNode));   //L = (LNode *) malloc(sizeof(LNode));  为头结点申请内存分配
    L->next = nullptr;     //初始化为空链表
    cout << "输入结点的值，输入9999表示结束：";
    cin >> x;
    while (x != 9999) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        cout << "输入结点的值，输入9999表示结束：";
        cin >> x;
    }
    return L;
}

//尾插法建立单链表（输出时会得到正序的链表）
LinkList List_TailInsert(LinkList &L) {     //时间复杂度为O(n)
    int x;
    L = (LinkList) malloc(sizeof(LNode));
    LinkList s, r = L;
    cout << "输入结点的值，输入9999表示结束：";
    cin >> x;
    while (x != 9999) {
        s = (LinkList) malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        cout << "输入结点的值，输入9999表示结束：";
        cin >> x;
    }
    r->next = nullptr;
    return L;
}

//按序号查找结点值（时间复杂度为O(n)）
LinkList GetElem(LinkList L, int i) {       //因为不会对链表进行改动，所以可以不用 &L，直接用 L
    int j = 1;
    LinkList p = L->next;
    if (i == 0)     //返回头结点
        return L;
    if (i < 1)
        return nullptr;
    while (p && j < i) {    //从第一个结点出发，逐个往下查找第i个结点
        p = p->next;
        j++;
    }
    return p;   //返回第i个结点的指针，若i大于表长则返回 NULL
}

//按值查找表结点（时间复杂度为O(n)）
LinkList LocateElem(LinkList L, ElemType e) {
    LinkList p = L->next;
    while (p->data != e && p != nullptr) {
        p = p->next;
    }
    return p;       //找到则返回该结点指针，否则返回 NULL
}

//在位置i上插入新值e
LinkList ListInsert(LinkList &L, int i, ElemType e) {
//法一：
// （对位置i前插操作，时间复杂度为O（n），对位置i的前驱结点后插操作，时间复杂度O（1））
//主要消耗时间在查找上
    if (i < 1)
        return nullptr;
    LinkList p = GetElem(L, i - 1);    //找到要插入的位置的前驱结点
    LinkList s;
    s = (LinkList) malloc(sizeof(LNode));   //新建一个结点放要插入的值
    s->data = e;
    s->next = p->next;  //对位置i的前驱结点后插操作
    p->next = s;
    return L;
//法二：
//可以直接把值插在位置i结点的后面，然后交换值(时间复杂度为O（1）)，假设已经知道i位置的结点Q,插入其前面的结点为s
//    s->next = Q->next;
//    Q->next = s;
//    ElemType temp = Q->data;
//    Q->data = s->data;
//    s->data = temp;
}

//删除位置i结点操作
LinkList ListDelete(LinkList &L, int i) {
//法一：
//
    LinkList p = GetElem(L, i - 1); //寻找前驱结点
    LinkList q = p->next;   //把q指向要删除结点
    p->next = q->next;
    ElemType e = q->data;
    free(q);    //释放存储空间
    return L;
//法二：
//假设要删除Q点，可以把后继结点的值赋给自身（时间复杂度为O（1））
//    q = Q->next;
//    Q->data = Q->next->data;
//    Q->next = q->next;
//    free(q);
}

//求表长长度
ElemType ListLength(LinkList L) {
    int count = 0;
    LinkList p = L;
    if (p->next == nullptr)
        return 0;
    while (p->next != nullptr) {    //（p->next != nullptr指下一个结点， p != nullptr指当前结点）
        p = p->next;
        count++;
    }
    cout << "个数为：" << count << endl;
    return count;
}

//输出链表（针对有头结点的）
void List_show(LinkList &L) {
    if (L->next == nullptr)
        return;
    LinkList p = L;
    p = p->next;
//    do {
//        cout << p->data << " ";
//        p = p->next;
//    } while (L->next != nullptr);
    int m = ListLength(L);
    for (int i = 0; i < m; i++) {
        cout << p->data << " ";
        p = p->next;
    }
}

///////////////////////双链表/////////////////////////
typedef struct DNode {
    ElemType data;
    struct DNode *prior, *next;
} DNode, *DLinkList;

//双链表的按序号查找操作
DLinkList DGetElem(DLinkList L, int i) {
//..........................
    return L;
}

//双链表的插入操作(头插法)
DLinkList DListInsert(DLinkList &L, int i, ElemType e) {
    DLinkList p = DGetElem(L, i - 1);   //在p后面插入s
    DLinkList s;
    s = (DLinkList) malloc(sizeof(DNode));
    s->next = p->next;
    p->next->prior = s;
    s->prior = p;
    p->next = s;
    return L;
}

//双链表的删除操作(头插法)
DLinkList DListDelete(DLinkList &L, int i) {
    DLinkList p = DGetElem(L, i - 1);   //在p后面删除q
    DLinkList q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return L;
}

//循环单/双链表******************
/*
void 判空() {
	LinkList M;
	DLinkList L;

M->next == M;		//循环单链表判空

L->next == L;
L->prior == L;		//循环双链表判空

}*/

//静态链表，用数组实现链式的存储方式(适用于不借助指针)
typedef struct SDNode {
    ElemType data;
    int next;
} SLinkList[MaxSize];

///////////////////第40页综合应用题//////////////////////////
//设计一个递归算法，删除不带头结点的单链表L中所有值为x的结点
void test1_Delete_x(LinkList &L, ElemType x) {
//法一：交换前后值删除结点
    if (L->next == nullptr)
        return;
    if (L->data == x) {
        LinkList p = L->next;
        L->data = L->next->data;
        L->next = p->next;
        free(p);
        test1_Delete_x(L, x);
    } else {
        test1_Delete_x(L->next, x);     //这里不能先让 L=L->next，再把L代入test1_Delete_x，会导致所有结果都会消失，
    }
//法二：直接删除结点
//    LinkList p;
//    if (L->next == nullptr)
//        return;
//    if (L->data == x) {
//        p = L;
//        L = L->next;
//        free(p);
//        test1_Delete_x(L, x);
//    } else
//        test1_Delete_x(L->next, x);   //这里不能先让 L=L->next，再把L代入test1_Delete_x，会导致所有结果都会消失，
}

//在带头结点的单链表L中，删除所有值为x的结点，释放其空间
void test2_Delete_x(LinkList &L, ElemType x) {
//法一：由p从头扫描到尾，每一次都要连接前驱和后继
    if (L->next == nullptr)
        return;
    LinkList p = L->next;
    LinkList pre = L;   //pre作为p的前驱，起连接作用
//    int Len = ListLength(L);
//    for (int i = 0; i < Len; i++) {
    while (p != nullptr) {
        if (p->data == x) {
            LinkList q = p;
            p = p->next;
            pre->next = p;
            free(q);
        } else {
            pre = p;
            p = p->next;
        }
    }
//法二：采用尾插法建立单链表
//    LinkList p = L->next, r = L, q;
//    while (p != nullptr) {
//        if (p->data != x) {
//            r->next = p;
//            r = p;
//            p = p->next;
//        } else {
//            q = p;
//            p = p->next;
//            free(q);
//        }
//    }
//    r->next = nullptr;
}

//L为带头结点的单链表，实现反向输出每个结点的值
//本题为递归思想，也可以用逆置法，相当于尾插法
void test3_Reverse_output(LinkList L) {
    if (L->next != nullptr)
        test3_Reverse_output(L->next);
    cout << L->data << " ";
}

//带头结点的单链表L，删除其最小值的结点
LinkList test4_Delete_min(LinkList &L) {
    LinkList pre = L, p = pre->next, minpre = pre, minp = p;
    while (p != nullptr) {
        if (p->data < minp->data) {
            minp = p;
            minpre = pre;
        }
        pre = p;
        p = p->next;
    }
    minpre->next = minp->next;
    free(minp);
    return L;
}

//将一个带头结点的单链表就地逆置，即空间复杂度为O（1），即不能新建一个链表
LinkList test5_Reverse_Local(LinkList &L) {
//法一：先把头结点摘下来，然后用头插法的方法从第一个结点开始吧结点插在头结点的后面
//    LNode *p, *r;
//    p = L->next;
//    L->next = nullptr;        //把头结点摘下
//    while (p != nullptr) {
//        r = p->next;
//        p->next = L->next;
//        L->next = p;
//        p = r;
//    }
//    return L;
//法二：把各结点的指针反向指
    LNode *pre, *p = L->next, *r = p->next;
    p->next = nullptr;      //这个要作为尾结点
    while (r != nullptr) {
        pre = p;
        p = r;
        r = r->next;
        p->next = pre;
    }
    L->next = p;
    return L;
}

//使一个带头结点的单链表有序递增
void test6_increasing_order(LinkList &L) {
    LinkList p = L->next, pre;
    LinkList r = p->next;   //r始终要为p的后继结点
    p->next = nullptr;      //从原链表断开，和头结点构造一个有序的链表
    p = r;      //令p指针指回还未排序的原链表
    while (p != nullptr) {
        r = p->next;
        pre = L;    //pre始终要从头结点开始
        while (pre->next != nullptr && p->next->data < p->data)
            pre = pre->next;
        p->next = pre->next;
        pre->next = p;
        p = r;    //令p指针指回还未排序的原链表
    }
}

//带头结点的无序单链表L，删除所有值在（s， e）之间的元素，不包括s和e
void test7_Delete_s_e(LinkList &L, ElemType s, ElemType e) {
    LinkList p = L->next, pre = L;
    if (L->next == nullptr)
        return;
    while (p != nullptr) {
        if (p->data > s && p->data < e) {
            LinkList q = p;
            p = p->next;
            pre->next = p;
            free(q);
            //或者
//            pre->next = p->next;
//            free(p);
//            p = pre->next;
        } else {
            pre = p;
            p = p->next;
        }
    }
}

//给定两个单链表，找出两个链表的公共结点(公共结点指某一时刻两个链表的某个节点->next会指向同一个结点，
// 并且之后的结点都是公共的，直到尾结点,会形成一个 Y 型)
//暴力法：逐个检查,时间复杂度为O（n?）
//线性时间复杂度法O（len1+len2）：先求出长度差，减去差后同步寻找
LinkList test8_find_common_LNode(LinkList L1, LinkList L2) {
    int len1 = ListLength(L1), len2 = ListLength(L2);
    LinkList longList, shortList;
    int dist;
    if (len1 > len2) {
        longList = L1->next;
        shortList = L2->next;
        dist = len1 - len2;
    } else {
        longList = L2->next;
        shortList = L1->next;
        dist = len2 - len1;
    }
    while (dist--)
        longList = longList->next;
    while (longList != nullptr) {
        if (longList == shortList)
            return longList;
        else {
            longList = longList->next;
            shortList = shortList->next;
        }
    }
    return nullptr;
}



int main() {
    LinkList L;
    List_TailInsert(L);
//    cout << "输入要删除的值：";
//    ElemType x;
//    cin >> x;
//    test2_Delete_x(L, x);
    test3_Reverse_output(L);
//    List_show(L);
    return 0;
}