526互联

线性表之单循环链表实现

发布时间 2023-04-09 22:41:36作者: 才下眉头3

main.cpp

#include "SCList.h"

int main(){
    List mylist;
    InitList(mylist);
    int select=1;
    ElemType Item;
    Node *p=NULL;
    while(select){
        printf("************************************\n");
        printf("* [1] push_back     [2] push_front *\n");
        printf("* [3] show_list     [4] pop_back   *\n");
        printf("* [5] pop_front     [6] insert_val *\n");
        printf("* [7] find          [8] length     *\n");
        printf("* [9] delete_val    [10] sort      *\n");
        printf("* [11] resver       [12] clear     *\n");
        printf("* [13*] destory      [0] quit_sys  *\n");
        printf("************************************\n");
        printf("请选择:>");
        scanf("%d",&select);
        if(select == 0 )
            break;
        switch (select) {
            case 1:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d",&Item),Item != -1){
                    push_back(mylist,Item);
                }
                break;
            case 2:
                printf("请输入要插入的数据(-1结束):>");
                while (scanf("%d",&Item),Item != -1){
                    push_front(mylist,Item);
                }
                break;
            case 3:
               show_list(mylist);
                break;
            case 4:
                pop_back(mylist);
                break;
            case 5:
                pop_front(mylist);
                break;
            case 6:
                printf("请输入要插入的数据:>");
                scanf("%d",&Item);
                insert_val(mylist,Item);
                break;
            case 7:
                printf("请输入要查找的数据:>");
                scanf("%d",&Item);
                p=find(mylist,Item);
                if(p==NULL)
                {
                    printf("要查找的数据在链表中不存在\n");
                }
                break;
            case 8:
                printf("单链表的长度为 %d\n",length(mylist));
                break;
            case 9:
                printf("请输入要删除的值:>");
                scanf("%d",&Item);
                delete_val(mylist,Item);
                break;
            case 10:
                sort(mylist);
                break;
            case 11:
                resver(mylist);
                break;
            case 12:
                clear(mylist);
                break;
                //case 13:
                //    destory(&mylist);
                //    break;
            default:
                printf("输入的命令错误，请重新输入。\n");
                break;
        }
    }
    destory(mylist);
}

SCList.h(头文件)

#ifndef SCLIST_SCLIST_H
#define SCLIST_SCLIST_H

#define ElemType int

#include "malloc.h"
#include "assert.h"
#include <stdio.h>

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *PNode;

typedef struct List {
    PNode first;
    PNode last;
    int size;
} List;

void InitList(List &list);

Node *_buynode(ElemType x);

void push_back(List &list, ElemType x);

void show_list(List &list);

void push_front(List &list, ElemType x);

void pop_back(List &list);

void pop_front(List &list);

void insert_val(List &list, ElemType x);

Node *find(List &list, ElemType key);

int length(List &list);

void delete_val(List &list, ElemType x);

void sort(List &list);

void resver(List &list);

void clear(List &list);

void destory(List &list);
#endif //SCLIST_SCLIST_H

SCList.cpp

#include "SCList.h"

void InitList(List &list) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    list.first = list.last = s;
    list.last->next = list.first;
    list.size = 0;
}

Node *_buynode(ElemType x) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    return s;
}

void push_back(List &list, ElemType x) {
    Node *s = _buynode(x);
    list.last->next = s;
    list.last = s;
    list.last->next = list.first;
    list.size++;

}

void push_front(List &list, ElemType x) {
    Node *s = _buynode(x);
    s->next = list.first->next;
    list.first->next = s;
    if (list.first == list.last) {
        list.last = s;
    }
    list.size++;
}

void show_list(List &list) {
    Node *p = list.first->next;
    while (p != list.first) {
        printf("%d-->", p->data);
        p = p->next;
    }
    printf("Null\n");
}

void pop_back(List &list) {
    if (list.size == 0) {
        return;
    }
    Node *p = list.first;
    while (p->next != list.last) {
        p = p->next;
    }
    free(list.last);
    list.last = p;
    p->next = list.first;
    list.size--;
}

void pop_front(List &list) {
    if (list.size == 0)
        return;
    Node *p = list.first->next;
    list.first->next = p->next;
    free(p);
    if (list.size == 1) {
        list.last = list.first;
    }
    list.size--;
}

void insert_val(List &list, ElemType x) {
    Node *p = list.first;
    while (p->next != list.last && p->next->data < x) {
        p = p->next;
    }
    if (p->next == list.last && p->next->data < x) {
        push_back(list, x);
    } else {
        Node *s = _buynode(x);
        s->next = p->next;
        p->next = s;
        list.size++;
    }
}

Node *find(List &list, ElemType key) {
    if (list.size == 0)
        return NULL;
    Node *p = list.first->next;
    while (p != list.first && p->data != key)
        p = p->next;
    if (p == list.first)
        return NULL;
    return p;
}

void delete_val(List &list, ElemType key) {
    if (list.size == 0)
        return;
    Node *p = find(list, key);
    if (p == NULL) {
        printf("要删除的数据不存在.\n");
    }
    if (p == list.last) {
        pop_back(list);
    } else {
        Node *q = p->next;
        p->data = q->data;
        p->next = q->next;
        free(q);
        list.size--;
    }
}

void sort(List &list) {
    if (list.size == 0 || list.size == 1)
        return;
    Node *s = list.first->next;
    Node *q = s->next;

    list.last->next = NULL;
    list.last = s;
    list.last->next = list.first;

    while (q != NULL) {
        s = q;
        q = q->next;
        Node *p = list.first;
        while (p->next != list.last && p->next->data < s->data) {
            p = p->next;
        }
        if (p->next == list.last && p->next->data < s->data) {
            s->next = list.last->next;
            list.last->next = s;
            list.last = s;
        } else {
            s->next = p->next;
            p->next = s;
        }
    }
}

void resver(List &list) {
    if (list.size == 0 || list.size == 1)
        return;
    Node *p = list.first->next;
    Node *q = p->next;

    list.last->next = NULL;
    list.last = p;
    list.last->next = list.first;
    while(q != NULL){
        p = q;
        q = q->next;
        p->next= list.first->next;
        list.first->next = p;
    }
}

void clear(List &list){
    Node *p = list.first->next;
    while(p != list.first){
        list.first->next = p->next;
        free(p);
        p = list.first->next;
    }
    list.last = list.first;
    list.last->next = list.first;
    list.size =0;
}

void destory(List &list){
    clear(list);
    free(list.first);
    list.first = list.last = NULL;
}
int length(List &list) {
    return list.size;
}