C语言链表-学习二十九

链表的概念

• 结构体数组:静态分配存储单元，容易造成内存浪费。
• 链表:是重要的数据结构，它根据需要，动态分配内存单元。
• 特征:头指针变量，存放链表首地址，链表中每个元素称结点。

• 其内容:

  • 数据域:可有若干项(整、实、字符、结构体类型等)
  • 指针域:下一结点的地址，最后一个结点（表尾）的地址部分为NULL。

• 链表存储数据的空间可以是不连续的，因此对空间的要求和应比较低。
• 链表中结点的空间是在程序执行过程中根据需要随时向系统申请开辟的内存单元，不用时可以随时释放结点所占用的空间。动态分配与数组不同，它不存在空间浪费的问题。

• 例如：

  • void *malloc(unsigned int size)
  • 作用：在内存的动态存储区分配一个长度为size的连续空间。
  • void *calloc(unsigned n,unsigned size);
  • 作用：在内存动态区分配n个长度为size的连续空间，函数返回指向分配起始地址的指针；
    若分配不成功，返回NULL值。
  • void free(void *p)
  • 作用：释放由p指向的动态存储区
• 结点之间是通过指针建立先后顺序。
  链表的插入、删除等操作只要改变个别结点地址部分的指向即可,无需移动大量的数据。
• 对链表的操作必须从头指针开始，然后逐个结点进行访问。

链表的声明

struct Student {
    // 结点的数据域
    int no;
    char name[20];
    float score;

    // 结点的指针域 类型是自身结构体类型
    struct Student *next;
};

• next是成员名，是指针类型,它指向struct Student数据类型。

静态链表

在C语言中，静态链表的表现形式为结构体数组，是在程序中定义，不是临时开辟的，也不能用完后释放，
每个数组元素包含数据域(data)和指针域(next)。

• 例如

#include <stdio.h>

struct Student {
    // 结点的数据域
    int no;
    char name[20];
    float score;
    // 结点的指针域 类型是自身结构体类型
    struct Student *next;
};

void main() {
    struct Student head, *p;
    struct Student stu1 = {10001,"Zhang Yin", 100}; 
    struct Student stu2 = {10002,"Qian Feng", 90}; 
    struct Student stu3 = {10003,"Liu Liang", 91};

    head.next = &stu1;
        // 将stu2的起始地址赋给stu1的next成员
    stu1.next = &stu2;
    stu2.next = &stu3;
    stu3.next = NULL;
    for (p = head.next; p!= NULL; p = p->next) {
        printf("%d\t%s\t%.2f\n",p->no,p->name,p->score);
    }
}

动态链表

建立链表

• 建立链表是指从无到有的形成一个链表。建立链表的思想就是逐个输入各结点的数据，同时建立结点之间的关系。

• 建立链表的算法概念

  • 先开辟一个结点的空间作为头结点，并让头指针指向头结点；
  • 然后开辟第一个数据结点，并输入结点数据，将第一结点“挂”在头结点之后；
  • 接着开辟第二个数据结点，并输入结点数据，将第二个结点“挂”在第一个结点之后...
  • 即按照输入顺序特结点“挂”在一起，形成链表。

例子

建立一个带有头结点的学生链表，直到输入的学生学号小于等于0时结束。

#include <stdio.h>
#include <string.h>

struct Student {
    int no;
    char name[20];
    unsigned sex;
    struct Student *next;
};

void main() {
    void setdata(struct Student *temp);
    struct Student *creatlink();
    void printlink(struct Student *head);
    struct Student *head;
    head = creatlink();
    printlink(head);
}

void setdata(struct Student *temp) {
    printf("No:");
    scanf_s("%d", &temp->no);
    getchar();
    printf("Name:");
    gets(temp->name);
    printf("Sex(1:boy;0:girl):");
    scanf_s("%d", &temp->sex);
}

struct Student *creatlink() {
    int i = 0;
    struct Student *head, *p, *q;
    head = (struct Student *)malloc(sizeof(struct Student));
    head -> next = NULL;
    p = head;
    q = (struct Student *)malloc(sizeof(struct Student));
    printf("请输入学生信息：\n");
    setdata(q);
    while ((q->no) > 0) {
        p->next = q;
        p = q;
        q = (struct Student *)malloc(sizeof(struct Student));
        printf("请输入学生信息：\n");
        setdata(q);
    }
    p->next = NULL;
    return head;
}

void printlink(struct Student *head) {
    struct Student *p;
    printf("-学生信息-\n");
    for (p = head->next; p != NULL; p = p->next) {
        printf("%d\t%s\t%d\n", p->no, p->name, p->sex);
    }
}

对链表的删除操作

• 并不真从内存中抹掉，只是把它分离，再前后结点相链接。
• 思路:本例以学号作为删除结点的标志（查找对象)
  设两个指针变量p1和p2。从head开始，p1依次指向各结点查找num值是否等于要删除结点的学号。每次下移前使p2=p1。学号相等删除该结点，直至查到表尾。

struct Student *del(struct Student *head, int no) {
    struct Student *p1, *p2;
    if (head == NULL) {
        printf("\n 链表为空！ \n");
        return head;
    }
    p1 = head;
    p2 = NULL;
    while (no != p1->no && p1->next != NULL) {
        p2 = p1; 
        p1 = p1->next;
    }
    if (no == p1->no) {
        if (p1 == head) {
            head = p1->next;
        }
        else {
            p2->next = p1->next;
        }
        printf("已删除：%d\n", no);
    }
    else{
        printf("\n没有找到要删除的对象：%d\n", no);
    }
        return(head);
}    

对链表的插入操作

• 思路:找到插入点后，将该点的next值指向新结点，并使新结点的next值等于断点后面结点的首地址。

struct Student *insert(struct Student *head, struct Student *stud) {
    struct Student *p0, *p1, *p2;
    p1 = head;     // 使p1指向第一个结点
    p0 = stud;  // p0指向要插入的结点
    p2 = NULL;
    if (head == NULL) { // 原来的链表是空表
        head = p0; 
        p0 -> next = NULL; // 使p0指向的结点
    }
    else {
        while ((p0->no > p1->no) && (p1->next != NULL)) {
            p2 = p1; // 使p2指向刚才p1指向的结点
            p1 = p1->next; // p1后移一个结点
        }
        if (p0->no <= p1->no) {
            if (head == p1) {
                head = p0; //插到原来第一个结点之前
            }
            else {
                p2->next = p0;  // 插到p2指向的结点之后
            }
            p0->next = p1;
        }
        else {
            p1->next = p0;   // 插到最后一个结点之后
            p0->next = NULL;
        }
        return(head);
    }
}

综合例子

#include <stdio.h>
#include <string.h>

struct Student {
    int no;
    char name[20];
    unsigned sex;
    struct Student *next;
};

void main() {
    void setdata(struct Student *temp);
    struct Student *creatlink();
    void printlink(struct Student *head);
    struct Student *del(struct Student *head, int no);
    struct Student *insert(struct Student *head, struct Student *stud);
    struct Student *head, *stu;
    int num;
    head = creatlink();
    printlink(head);
    printf("请输入要删除的学号:");
    scanf_s("%d", &num);
    while (num != 0) {  // 为0退出删除
        head = del(head, num);
        printlink(head);
        printf("请输入要删除的学号:");
        scanf_s("%d", &num);
    }
    printf("请输入要插入的信息:\n");
    stu = (struct Student *)malloc(sizeof(struct Student));
    setdata(stu);
    while (stu->no != 0) {
        head = insert(head, stu);
        printlink(head);
        printf("请输入要插入的信息:\n");
        stu = (struct Student *)malloc(sizeof(struct Student));
        setdata(stu);
    }
}

void setdata(struct Student *temp) {
    printf("No:");
    scanf_s("%d", &temp->no);
    getchar();
    printf("Name:");
    gets(temp->name);
    printf("Sex(1:boy;0:girl):");
    scanf_s("%d", &temp->sex);
}

struct Student *creatlink() {
    int i = 0;
    struct Student *head, *p, *q;
    head = (struct Student *)malloc(sizeof(struct Student));
    head -> next = NULL;
    p = head;
    q = (struct Student *)malloc(sizeof(struct Student));
    printf("请输入学生信息：\n");
    setdata(q);
    while ((q->no) > 0) {
        p->next = q;
        p = q;
        q = (struct Student *)malloc(sizeof(struct Student));
        printf("请输入学生信息：\n");
        setdata(q);
    }
    p->next = NULL;
    return head;
}

void printlink(struct Student *head) {
    struct Student *p;
    printf("-学生信息-\n");
    for (p = head->next; p != NULL; p = p->next) {
        printf("%d\t%s\t%d\n", p->no, p->name, p->sex);
    }
}

struct Student *del(struct Student *head, int no) {
    struct Student *p1, *p2;
    if (head == NULL) {
        printf("\n 链表为空！ \n");
        return head;
    }
    p1 = head;
    p2 = NULL;
    while (no != p1->no && p1->next != NULL) {
        p2 = p1; 
        p1 = p1->next;
    }
    if (no == p1->no) {
        if (p1 == head) {
            head = p1->next;
        }
        else {
            p2->next = p1->next;
        }
        printf("已删除：%d\n", no);
    }
    else{
        printf("\n没有找到要删除的对象：%d\n", no);
    }
    return(head);
}    

struct Student *insert(struct Student *head, struct Student *stud) {
    struct Student *p0, *p1, *p2;
    p1 = head;     // 使p1指向第一个结点
    p0 = stud;  // p0指向要插入的结点
    p2 = NULL;
    if (head == NULL) { // 原来的链表是空表
        head = p0; 
        p0 -> next = NULL; // 使p0指向的结点
    }
    else {
        while ((p0->no > p1->no) && (p1->next != NULL)) {
            p2 = p1; // 使p2指向刚才p1指向的结点
            p1 = p1->next; // p1后移一个结点
        }
        if (p0->no <= p1->no) {
            if (head == p1) {
                head = p0; //插到原来第一个结点之前
            }
            else {
                p2->next = p0;  // 插到p2指向的结点之后
            }
            p0->next = p1;
        }
        else {
            p1->next = p0;   // 插到最后一个结点之后
            p0->next = NULL;
        }
        return(head);
    }
}