Loading [MathJax]/jax/output/HTML-CSS/jax.js

王道数据结构经典代码题-链表

作者： 作者的头像   你微笑说愿望太大 ,  2022-07-31 10:41:37 ,  所有人可见 ,  阅读 283

3


王道数据结构经典代码题−链表

1、设计一个递归算法，删除不带头节点的单链表L中所有值为x的结点

#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *Linklist;

//不带头节点的链表
Linklist aaaa() {
    LNode *L = new LNode;
    int a;
    cin >> a;
    L->data = a;
    LNode *p = L; //声明一个指针指向头结点，
    //生成链表
    cin >> a;
    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }
    p->next = NULL;
    return L;
}

void del_x(LNode *&L, int x) {
    LNode *p;
    /*写递归函数的话首先写递归出口 ，然后再写else的部分，最后再来补充等于x的代码细节*/
    if (L == NULL) 
        return;

    if (L->data == x) {
        p = L;
        L = L->next;
        free(p);
        del_x(L, x);

    }
    else {
        del_x(L->next, x);
    }
}


int main() {

    LNode *L = aaaa();
    del_x(L, 10);

    while (L!=NULL) {
        cout << L->data << " ";
        L = L->next;
    }
}

2. 删除带头节点单链表中所有值为x的结点

#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*Linklist;
//创建带头链表
Linklist aaaa() {
    LNode *L = new LNode;
    LNode *p = L;

    int a;
    cin >> a;

    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }
    p->next = NULL;
    return L;
}
//法一：
void del(LNode *&L , int x) {
    LNode * p = L->next, *pre = L;
    LNode *q;

    while (p!=NULL) {
        if (p->data == x) {
            q = p;
            pre->next = p->next;
            p = p->next;
            free(q);
        }
        else {
            pre = p;
            p = p->next;
        }
    }
}
//法二：对比法一的好处就是用p充当法一pre的角色 写法更简单一些
void Del(LNode *&L, int x) {
    LNode *p = L;

    while (p->next != NULL) {
        if(p->next->data == x){
            LNode *q = p->next;
            p->next = q->next;

            free(q);

        }
        else {
            p = p->next;
        }

    }

}

int main() {
    LNode *L = aaaa();
    Del(L, 10);

    LNode *q = L->next;
    while (q!=NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    return 0;
}

3、删除带头节点单链表中第一个值为x的结点

/* 这题和第二题很像，只不过这题是找到了第一个就退出，所以要比第二题多一个if判断找到了就直接退出*/
#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode, *Linklist;;

//生成链表，a=0时就退出
Linklist aaaa() {
    LNode *L = new LNode;
    LNode *p = L;
    int a;
    cin >> a;

    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }

    p->next = NULL;

    return L;

}

int finddelete(LNode *&C, int x) {
    LNode *p, *q;
    p = C;
    while (p->next!=NULL) {
        if (p->next->data == x) {
            q = p->next;
            p->next = q->next;
            free(q);
            return 1;
        }
        else {
            p = p->next;
        }


    }

    return 0;
}


int main() {
    LNode *L = aaaa();
    finddelete(L, 10);
    LNode * q = L->next;

    while (q != NULL) {
        cout << q->data << " ";
        q = q->next;
    }
    return 0;
}

5.试编写算法将单链表就地逆置

#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*Linklist;

Linklist aaaa() {
    LNode *L = new LNode;
    LNode *p = L;

    //生成链表
    int a;
    cin >> a;
    while (a!=0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }
    p->next = NULL;
    return L;
}

void reverse(LNode  *&L) {
    LNode *p = L->next, *r;
    /*LNode *P = L->next, *r;*/
    L->next = NULL;
    while (p!=NULL) {
        r = p->next;
        p->next = L->next;
        L->next = p;
        p = r; 
    }
}

void Reverse(LNode *&L) {
    LNode *p = L->next, *r = p->next;
    LNode *pre;
    p->next = NULL;
    while (r!=NULL) {
        pre = p;
        p = r;
        r = r->next;
        p->next = pre;
    }
    L->next = p;
}


int main() {
    LNode *L = aaaa();
    reverse(L);
    LNode *q = L->next;
    while (q!=NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    return 0;
}

6.从链表中删除给定值在s到t之间（不包含s和t）的所有元素


#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*Linklist;


Linklist aaaa() {
    LNode *L = new LNode;
    LNode *p = L;

    //生成链表
    int a;
    cin >> a;
    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }
    p->next = NULL;
    return L;
}

void del(LNode *&L, int min, int max) {
    LNode *p = L;
    /*LNode *P = L;*/
    while (p->next!=NULL) {
        if (p->next->data > min && p->next->data < max) {
            LNode *u = p->next;
            p->next = u->next;
            free(u);
        }
        else {
            p = p->next;
        }
    }

}


int main() {
    /*LNode *L = aaaa();
    del(L, 1, 4);
    LNode *q = L->next;
    while (q!=NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    return 0;*/

    LNode *L = aaaa();
    del(L, 1, 4);
    LNode *q = L->next;
    while (q != NULL) {
        cout << q->data << " ";
        q = q->next;
    }
    return 0;
}

7、试编写在带头结点的单链表L中删除最小值点的高效算法（已知最小值唯一）

#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*Linklist;


Linklist aaaa() {

    LNode *L = new LNode;
    LNode *p = L;

    //生成链表
    int a;
    cin >> a;
    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;
        p = p->next;
        cin >> a;
    }
    p->next = NULL;
    return L;
}

void del_min(LNode *&L) {
    LNode *p = L->next;
    LNode *minp = L;

    while (p->next!=NULL) {
        if (p->next->data < minp->next->data) {
            minp = p;
        }
        p = p->next;
    }
    LNode *u = minp->next;
    minp->next = u->next;
    free(u);
}


int main() {
    LNode *L = aaaa();
    del_min(L);
    LNode *q = L->next;
    while (q!=NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    return 0;
}

8 、试编写在不带头结点的单链表L中删除最小值点的高效算法（已知最小值唯一）

#include <iostream>

using namespace std;

typedef struct LNode {
    int data;
    struct LNode *next;
}LNode,*Linklist;


Linklist aaaa() {

    LNode *L = new LNode;

    int a;
    cin >> a;
    L->data = a;
    LNode *p = L;
    while (a != 0) {
        LNode *q = new LNode;
        q->data = a;
        q->next = NULL;
        p->next = q;

        p = p->next;
        cin >> a;

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

void del_min(LNode *&L) {
    LNode *minp = L;
    LNode *p = L->next; 
    while (p!=NULL) {
        if (p->data < minp->data) {
            minp = p;
        }
        p = p->next;
    }
    if (L == minp) {
        L = L->next;
        free(minp);
        return;
    }
    p = L;
    while (p->next!=minp) {
        p = p->next;

    }
    p->next = minp->next;
    free(minp);
}


int main() {
    LNode *L = aaaa();
    del_min(L);
    LNode *q = L->next;
    while (q!=NULL) {
        cout << q->data << " ";
        q = q->next;
    }

    return 0;
}

0 评论

1024
x