C语言线性表--单链表

• 1 代码解析
• 2.代码

main.c

//
//  main.c
//  SingLinkList

#include "SingleLinkList.h"

int main() {
    List mylist;
    InitList(&mylist);
    List newlist;
    InitList(&newlist);
    
    int select=1;
    Elemtype value=0;
    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] reverse           [12] clear       *n");
        printf("* [13] destroy           [14] quit_system *n");
        printf("*******************************************n");
        printf("请选择：> ");
        scanf("%d",&select);
        if(0 == select)
            break;
        
        switch (select)
        {
            case 1:
                printf("Please input a number(-1 end): ");
                while(scanf("%d",&value),value!= -1)
                {
                    push_back(&mylist,value);
                }
                show_list(mylist);
                break;
            case 2:
                printf("Please input a number(-1 end) : ");
                while(scanf("%d",&value),value!= -1)
                {
                    push_front(&mylist,value);
                }
                show_list(mylist);
                break;
            case 3:
                show_list(mylist);
                break;
            case 4:
                pop_back(&mylist,&value);
                show_list(mylist);
                break;
            case 5:
                pop_front(&mylist);
                show_list(mylist);
                break;
            case 6:
                printf("Please input pos,value : ");
                int pos;
                scanf("%d,%d,",&pos,&value);
                insert_val(&mylist,pos,value);
                show_list(mylist);
                break;
            case 7:
                printf("Please input value : ");
                scanf("%d",&value);
                PLnode p = find(mylist,value);
                if(!p)printf("No value in List.n");
                break;
            case 8:
                printf("length: %dn",length(mylist));
                break;
            case 9:
                printf("Please input value : ");
                scanf("%d",&value);
                delete_val(&mylist,value);
                show_list(mylist);
                break;
            case 10:
                sort(&mylist);
                show_list(mylist);
                break;
            case 11:
                reverse(&mylist,&value,&newlist);
                printf("n");
                show_list(newlist);
                break;
            case 12:
                clear0(&mylist);
                break;
            case 13:
                destroy(&mylist);
                break;
            default:
                break;
        }
    }
    destroy(&mylist);
    destroy(&newlist);
    printf("Hello, World!n");
    return 0;
}

2. SingleLinkList.h

//
//  SingleLinkList.h


#ifndef SingleLinkList_h
#define SingleLinkList_h

#include 
#include 
#include 

// 1 定义宏
#define Elemtype int

// 2 定义节点、单链表
typedef struct Lnode
{
    Elemtype data;
    struct Lnode *next;
}Lnode,*PLnode;

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

// 3 函数声明
void InitList(List *List);
void push_back(List *List,Elemtype num);
void push_front(List *List,Elemtype num);
void show_list(List list);
void pop_back(List *List,Elemtype *num); 
void pop_front(List *List);
void insert_val(List *List,int pos,Elemtype num);
PLnode find(List list,Elemtype num);
int length(List list);
void delete_val(List *List,Elemtype value);
void sort(List *List);
void reverse(List *List,Elemtype *num,struct List *newlist);
void clear0(List *List);
void destroy(List *List);
#endif 

3 SingleLinkList.c

//
//  SingleLinkList.c
//  SingLinkList


#include "SingleLinkList.h"

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

void push_back(List *List,Elemtype num)         // 1
{
    PLnode new = (PLnode)malloc(sizeof(Lnode));
    new->data = num;
    new->next = NULL;
    
    List->last->next = new;
    List->last = new;
    printf("%p",List->last->next);
    List->size++;
}
void push_front(List *List,Elemtype num)       // 2
{
    PLnode new = (PLnode)malloc(sizeof(Lnode));
    new->data = num;
    if(0==List->size)
    {
        List->last=new;
    }
    new->next = List->first->next;
    List->first->next = new;
    List->size++;
}
void show_list(List list)                     // 3
{
    if(list.first == NULL)
    {
        printf("List is NULL!n");
        return;
    }else
    {
        PLnode p = list.first->next;
        while (p)
        {
            printf("%d,",p->data);
            p = p->next;
        }
    }
    printf("n");
}
void pop_back(List *List,Elemtype *num)                    // 4
{
    PLnode p = List->first;
    if(0==List->size) return;
    while (p->next != List->last) {
        p = p->next;
    }
    *num = List->last->data;
    free(List->last);
    List->last=p;
    List->last->next=NULL;    // 尾指针指向p，地址存放n-1的地址，因此要把尾指针重新设为NULL；
    List->size--;
    p=NULL;
}
void pop_front(List *List)                   // 5
{
    PLnode p = List->first->next;
    if(!p) return;
    List->first->next = p->next;
    free(p);
    p=NULL;
    if(1==List->size) List->last=List->first;

    List->size--;
}
void insert_val(List *List,int pos,Elemtype num)     // 6 只能在某元素前插入
{
    PLnode new = (PLnode)malloc(sizeof(Lnode));
    new->data = num;
    
    PLnode p=List->first;
    int i=pos;
    while(p && i>1)
    {
        p=p->next;
        i--;
    }
    if(!p || pos<=0) return;
    
    new->next = p->next;
    p->next=new;
    if(pos==List->size+1) List->last=new;
    List->size++;
    
}
PLnode find(List List,Elemtype num)                  // 7
{
    PLnode p=List.first->next;
    while (p && p->data!=num) {
        p = p->next;
    }
    return p;
}
int length(List list)                                // 8
{
    return list.size;
}
void delete_val(List *List,Elemtype value)           // 9
{
    PLnode p = List->first;
    while (p->next && p->next->data != value)
    {    p=p->next;
        
    }
    if(!p->next) return;
    p->next = p->next->next;
    if(p->next == List->last )    
    {
        List->last=p;
        List->last->next=NULL;
    }
    free(p->next);
    List->size--;
}
void sort(List *List)                             // 10
{
    Elemtype tmp;
    PLnode p;
    int n = List->size;
    for(int i=0;ifirst->next;
        for(int j=0;jdata > p->next->data)
            {
                tmp = p->next->data;
                p->next->data = p->data;
                p->data=tmp;
            }
            p = p->next;
        }
    }
    
}
void reverse(List *List,Elemtype *num,struct List *newlist)                            // 11
{
    // 2 从链表中尾部删除数据，并放在新的链表中
    int n= List->size;
    while (n>0) {
        pop_back(List,num);
        push_back(newlist,*num);
        --n;
    }
    
}
void clear0(List *List)                             // 12
{
    PLnode p = List->first->next;
    if(!p) return;
    while (p) {
        List->first->next= p->next;
        free(p);
        p=List->first->next;
        List->size--;
    }
    List->last = List->first;
    List->size=0;
}
void destroy(List *List)                            // 13
{
    clear0(List);
    free(List->first);
    List->first = NULL;
    List->last = NULL;
}