526互联

线性表之单链表实现

发布时间 2023-03-26 16:28:22作者: 才下眉头3

主函数

main.c

#include "SList.h"

void 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);
}

头文件

SList.h

#ifndef SLIST_SLIST_H
#define SLIST_SLIST_H

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

#define ElemType int
typedef struct Node {
    ElemType data;
    struct Node *next;
} Node, *PNode;
typedef struct List {
    PNode first;
    PNode last;
    size_t size;
} List;

void InitList(List *list);

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 //SLIST_SLIST_H

实现代码

SList.c

#include "SList.h"

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

void push_back(List *list, ElemType x) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    list->last->next = s;
    list->last = s;
    list->size++;
}

void push_front(List *list, ElemType x) {
    Node *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = list->first->next;
    list->first->next = s;
    if (list->size == 0) {
        list->last = s;
    }
    list->size++;
}

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;
    list->last->next = NULL;
    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 *s = (Node *) malloc(sizeof(Node));
    assert(s != NULL);
    s->data = x;
    s->next = NULL;
    Node *p = list->first;
    while (p->next != NULL && p->next->data < x) {
        p = p->next;
    }
    if (p->next == NULL) {
        list->last = s;
    }
    s->next = p->next;
    p->next = s;
    list->size++;
}

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

int length(List *list) {
    return list->size;
}

void delete_val(List *list, ElemType x) {
    if (list->size == 0) {
        return;
    }
    Node *p = find(list, x);
    if (p == NULL) {
        printf("要删除的数据不存在.\n");
        return;
    }
    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 = s;
    list->last->next = NULL;

    while (q != NULL) {
        s = q;
        q = q->next;
        Node *p = list->first;
        while (p->next != NULL && p->next->data < s->data) {
            p = p->next;
        }
        if (p->next == NULL) {
            list->last = s;
        }
        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 = p;
    list->last->next = NULL;
    while (q != NULL) {
        p = q;
        q = p->next;
        p->next = list->first->next;
        list->first->next = p;
    }
}

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

void destory(List* list){
    clear(list);
    free(list->first);
    list->first = list->last = NULL;
    list->size=0;
}

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