c语言链表操作

---

链表的创建

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
//结构体
struct Student{
    long num;
    float score;
    struct Student *next;
};
//全局变量，记录student的个数
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    //输入0，退出，尾插法
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        //p2永远指向链表最后一个元素
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}
//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);
    system("pause");
    return 0;
}

链表的建立.png

链表原地翻转

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;
    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}
//逆序
struct Student* reverseOrder(struct Student* head){
    struct Student *p,*temp,*r,*q;
    p = head;
    q = p;
    r = p->next;
    while (r != NULL){
        //temp指针指向r
        temp = r;
        //r指针指向下一个
        r = r->next;
        temp->next = p;
        head = temp;
        p = head;
    }
    q->next = NULL;
    return head;
}
//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);
    pt = reverseOrder(pt);
    print(pt);

    system("pause");
    return 0;
}

Snipaste_2021-03-12_22-45-42.png

链表结点删除

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;
    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

//删除链表结点
struct Student* del(struct Student *head,long num){
    struct Student *p1,*p2;
    int count = 0;
    if(head == NULL){
        printf("empty");
        return head;
    }
    p1 = head;
    while(p1 != NULL){
        struct Student *temp;
        if(num == p1->num){
            if(p1 == head){
                temp = p1;
                head = p1->next;
                p1 = p1->next;

            }else{
                temp = p1;
                p2->next = p1->next;

            }
            free(temp);
            printf("delete:%d\n",num);
            n--;
            count++;
        }else{
            p2 = p1;
            p1 = p1->next;
        }

    }
    if(count == 0){
        printf("not found!\n");
    }
    return head;
}

//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);
    pt = del(pt,1001);
    print(pt);
    
    system("pause");
    return 0;
}

结点删除.png

头插法添加结点

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;
    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

//头插法
struct Student* ins(struct Student *head,struct Student *stud){
    struct Student *p0,*p1,*p2;
    p0 = head;
    p1 = stud;
    if(head == NULL){
        head = p1;
        p1->next = NULL;
    }else{
        head = p1;
        p1->next = p0;
    }
    n++;
    return head;

}

//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);

    struct Student s1;
    s1.score = 90;
    s1.num = 1004;
    pt = ins(pt,&s1);
    print(pt);
    
    system("pause");
    return 0;
}

头插法.png

修改链表某个结点的值

• 相当于查找元素，修改其关联元素的值

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;
    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

struct Student *change(struct Student *head,long num,float score){
    struct Student *p;
    p = head;
    while (p != NULL){
        if(num == p->num){
            p->score = score;
        }
        p = p->next;
    }
    return head;
}

//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);

    pt = change(pt,1002,99);
    print(pt);

    system("pause");
    return 0;
}

结点删除.png

链表元素排序

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;
    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

//排序（按成绩），选择排序
struct Student* sortStudent(struct Student *head){
    struct Student *p,*min,*ptr;
    long tempNum;
    float tempScore;
    p = head;
    while (p->next != NULL){
        min = p;
        ptr = p->next;
        while (ptr != NULL){
            if(min->score > ptr->score){
                min = ptr;
            }
            //交换ptr指针和p的值
            tempNum = min->num;
            min->num = p->num;
            p->num = tempNum;
            
            tempScore = min->score;
            min->score = p->score;
            p->score = tempScore;
            
            ptr = ptr->next;
        }
        p = p->next;
    }
    return head;

}
//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);

    pt = sortStudent(pt);
    print(pt);
    
    system("pause");
    return 0;
}

链表排序.png

两个有序链表的合并

• 先将两个链表分别排序再合并

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;

    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

//合并两个链表
struct Student* merge(struct Student *head1,struct Student *head2){
    struct Student *p1,*p2,*pre,*temp;
    p1 = head1;
    p2 = head2;
    while (p1 != NULL && p2 != NULL){
        if(p1->score <= p2->score){
            pre = p1;
            p1 = p1->next;
        }else{
            if(p1 == head1){
                p2 = p2->next;
                head1 = head2;
                head2->next = p1;
            }else{
                temp = p2;
                p2 = p2->next;
                pre->next = temp;
                temp->next = p1;
                pre = temp;

            }
        }
    }
    if(p1 == NULL){
        pre->next = p2;
    }

    return head1;
}

//排序（按成绩），选择排序
struct Student* sortStudent(struct Student *head){
    struct Student *p,*min,*ptr;
    long tempNum;
    float tempScore;
    p = head;
    while (p->next != NULL){
        min = p;
        ptr = p->next;
        while (ptr != NULL){
            if(min->score > ptr->score){
                min = ptr;
            }
            tempNum = min->num;
            min->num = p->num;
            p->num = tempNum;
            tempScore = min->score;
            min->score = p->score;
            p->score = tempScore;
            ptr = ptr->next;
        }
        p = p->next;
    }
    return head;

}
//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    pt = sortStudent(pt);
    print(pt);

    struct Student *pt1;
    pt1 = create();
    pt1 = sortStudent(pt1);
    print(pt1);

    pt = merge(pt,pt1);
    print(pt);
    
    system("pause");
    return 0;
}

链表合并.png

按序插入

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;

    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}



//按序插入,按成绩
struct Student* insSort(struct Student *head,struct Student *stud){
    struct Student *p,*pre,*temp;
    p = head;
    temp = stud;
    if(head->score >= temp->score){
        head = temp;
        temp->next = p;
        return head;
    }
    while (p != NULL){
        if(p->score > temp->score){
            pre->next = temp;
            temp->next = p;
            break;
        }
        pre = p;
        p = p->next;
    }
    return head;
}


//排序（按成绩），选择排序
struct Student* sortStudent(struct Student *head){
    struct Student *p,*min,*ptr;
    long tempNum;
    float tempScore;
    p = head;
    while (p->next != NULL){
        min = p;
        ptr = p->next;
        while (ptr != NULL){
            if(min->score > ptr->score){
                min = ptr;
            }
            tempNum = min->num;
            min->num = p->num;
            p->num = tempNum;
            tempScore = min->score;
            min->score = p->score;
            p->score = tempScore;
            ptr = ptr->next;
        }
        p = p->next;
    }
    return head;

}
//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    pt = sortStudent(pt);
    print(pt);

    struct Student *s2;
    //必须申请空间
    s2=(struct Student *)malloc(LEN);
    s2->score = 78;
    s2->num = 1005;
    pt = insSort(pt,s2);
    print(pt);
    system("pause");
    return 0;
}

有序添加.png

释放内存

#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#define LEN sizeof(struct Student)

//链表
struct Student{
    long num;
    float score;

    struct Student *next;
};
int n;

//创建链表
struct Student* create(){
    struct Student *head;
    struct Student *p1,*p2;
    n = 0;
    p1=p2=(struct Student *)malloc(LEN);
    scanf("%d %f",&p1->num,&p1->score);
    head = NULL;
    while(p1->num != 0){
        ++n;
        if(n==1) head = p1;
        else p2->next = p1;
        p2 = p1;
        //p1不断生成新的结点
        p1 = (struct Student*)malloc(LEN);
        scanf("%ld %f",&p1->num,&p1->score);
    }
    p2->next = NULL;
    return head;
}

//打印链表元素
void print(struct Student* head){
    struct Student *p;
    printf("The numbers is %d\n",n);
    p = head;
    if(head != NULL){
        do{
            printf("num:%d,score:%5.1f\n",p->num,p->score);
            p = p->next;
        }while(p != NULL);
    }
}
void deleteAll(struct Student *head){
    struct Student *p,*temp;
    p = head;
    while (p != NULL){
        n--;
        temp = p;
        p = p->next;
        free(temp);
    }
    printf("%d numbers\n",n);
}
int main(int argc, char* argv[])
{

    struct Student *pt;
    pt = create();
    print(pt);

    deleteAll(pt);
    system("pause");
    return 0;
}

delete.png