线性表之单链表实现

2019-09-29 本文已影响0人温柔倾怀

线性表之单链表实现

实现单链表的初始化、插入、删除等基本运算
实现单链表的输入、输出运算
实现单链表的逆置、归并、排序等复杂运算

main.c

主程序逻辑实现

#include <stdio.h>
#include "Slist.h"
int main() {
    printf("Hello, World!\n");
    List mylist;
    List yourlist,itlist;
    InitList(&mylist);
    ElemType Item;
    int select =1;
    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] merge_list [0] exit system  *\n");
        printf("************************************\n");
        printf("your selection:");
        scanf("%d",&select);
        if(select==0){
            break;
        }

        switch (select){
            case 1:
                //push_back
                printf("please input your linklist content (-1 to end) :");
                while (scanf("%d",&Item),Item!=-1){
                    push_back(&mylist,Item);
                }
                break;
            case 2:
//                push_front
                printf("please input your linklist content (-1 to end) :");
                while (scanf("%d",&Item),Item!=-1){
                    push_front(&mylist,Item);
                }
                break;
            case 3:
                show_list(&mylist);
                break;
            case 4:
//                pop_back
                pop_back(&mylist);
                break;
            case 5:
//                pop_front
                pop_front(&mylist);
                break;
            case 6:
//                insert_val
                printf("please input the node value:");
                scanf("%d",&Item);
                insert_val(&mylist,Item);
                break;
            case 7:
//                find
                printf("please input the data to find:");
                Node *p=NULL;//接收返回的node
                scanf("%d",&Item);
                p = find(&mylist,Item);
                if (p==NULL){
                    printf("not find");
                } else{
                    printf("date exist\n");
                }
                break;
            case 8:
//                length
                printf("the LinkList length is : ");
                int len=0;
                len= length(&mylist);
                printf("%d\n",len);
                break;
            case 9:
//                delete_val
                printf("please delete value:");
                scanf("%d",&Item);
                delete_val(&mylist,Item);
                break;
            case 10:
//                sort
                sort(&mylist);
                break;
            case 11:
//                resver
                resver(&mylist);
                break;
            case 12:
//                clear
                clear(&mylist);
                break;
            case 13:
                InitList(&yourlist);
                InitList(&itlist);
                printf("now input your second list! ");
                printf("please input your linklist content (-1 to end) :");
                while (scanf("%d",&Item),Item!=-1){
                    push_back(&yourlist,Item);
                }
                printf("show your second list:\n");
                show_list(&yourlist);
                merge_list(&mylist,&yourlist,&itlist);
                break;
            default:
                printf("selection not exist!\n");
                break;
        }
    }
    return 0;
}

SList.h

标示符常量的定义，单链表的存储类型描述和基本运算的声明

//
// Created by wenrou on 2019-09-16.
//

#ifndef SLIST_SLIST_H
#define SLIST_SLIST_H

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

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

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

void InitList(List *list);
void push_back(List *list,ElemType item);
void push_front(List *list,ElemType item);
void show_list(List *list);
void pop_back(List *list);
void pop_front(List *list);
void insert_val(List *list,ElemType item);
Node* find(List *list,ElemType item);
int length(List *list);
void delete_val(List *list,ElemType item);
void sort(List *list);
void resver(List *list);
void clear(List *list);
void merge_list(List *list1,List *list2,List *list3);
#endif //SLIST_SLIST_H

SList.c

基本操作及各功能实现函数体

//
// Created by wenrou on 2019-09-16.
//
#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 item){
    Node *s = (Node *)malloc(sizeof(Node));
    assert(s!=NULL);
    s->data=item;
    s->next=NULL;
    list->last->next=s;
    list->last=s;
    list->size++;
}

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

void push_front(List *list,ElemType item){
    Node *s = (Node *)malloc(sizeof(Node));
    assert(s!=NULL);
    s->data=item;
    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){
        printf("LinkList is NULL");
    }
    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){
        printf("LinkList is NULL");
    }
    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 item){//假设 有序 递增

    Node *s = (Node *)malloc(sizeof(Node));
    assert(s!=NULL);
    s->data=item;
    s->next=NULL;
    Node *p = list->first;
    while (p !=NULL&&p->next->data<item){
        p=p->next;
    }
    if(p->next==NULL){ //在最后插入 尾结点变动
        list->last=s;
    }
    s->next=p->next;
    p->next=s;
    list->size++;

}

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

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

void delete_val(List *list,ElemType item){

    if(list->size==0){
        printf("LinkList empty");
        return;
    }
    Node *p = find(list,item);
    if (p==NULL){
        printf("data not exist");
        return;
    }
    //删除p的后继

    //若删除最后一个节点
    if(p==list->last){
        pop_back(list);
    }else{
        /*
         * 1 2 3
         * 2 的前继 循环 繁琐
         * 思路：将 3 拷贝到 2 ，将3 删除
         * */
        Node *q = p->next;//3
        p->data=q->data;//3 copy  to 2
        p->next=q->next;//2->4
        free(q);//rm 3
        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;
    /*
     * (first)1(last) -- 2 3 4 5
     *
     * */
    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 merge_list(List *list1,List *list2,List *list3){
    //归并
    if(list1->size==0||list2->size==0){
        return;
    }
    sort(list1);
    sort(list2);
    Node *p = list1->first;
    Node *q = list2->first;

    while (p->next!=NULL&&q->next!=NULL){
        if(p->next->data<q->next->data){
            push_back(list3,p->next->data);
            p=p->next;
        } else{
            push_back(list3,q->next->data);
            q=q->next;
        }
    }

    while (p->next!=NULL){
        push_back(list3,p->next->data);
        p=p->next;
    }
    while (q->next!=NULL){
        push_back(list3,q->next->data);
        q=q->next;
    }
    printf("the gerge list is :");
    show_list(list3);
}

执行结果

主程序运行，显示功能菜单

尾插法

排序

逆置

归并
当前已有链表1，再输入链表2，归并返回并显示为链表3

线性表之单链表实现

线性表之单链表实现

main.c

SList.h

SList.c

执行结果

OVER

猜你喜欢

热点阅读