[数据结构与算法]c进阶——链表介绍及综合操作

动态链表所需的一些函数

malloc函数

（类型说明符*）mallco（size）

函数功能是在内存的动态存储区分配出一块长度为size的连续空间；

函数返回值为指向该空间起始地址的指针；

函数原型的指针类型为void，若未能成功执行则返回空指针，NULL；

（类型说明符*）用于将指针强制转换类型；

p=(struct *)mallco(sizeof(struct student));
//申请“struct student"类型长度的空间，并把该空间的起始地址赋值给p；

free函数

free (p);//释放p所指向的一块内存区；

链表综合应用?

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

struct student {
    int num;
    float score;
    struct student *next;
};

int n = 0; //结点总数

//----------建立动态链表-------------

struct student *create(void) {
    struct student *head, *p1, *p2; //建立三个指针变量（head）；
    head = NULL; n = 0;
    p1 = p2 = (struct student*)malloc(sizeof(struct student));
    //建立初始节点，并将p1、p2指向节点地址
    scanf("%d,%f", &p1->num, &p1->score); //输入节点数值；
    while(p1->num != 0) {
        n = n+1;
        if(n == 1) {
            head = p1; //第一个节点时，将其链接到表头（head）；
        }else {
            p2->next = p1; //否则链接到前一个节点的尾部（next）;
            p2 = p1;
        }
        p1 = (struct student *)malloc(sizeof(struct student));
        //申请一个新的节点空间
        scanf("%d,%f", &p1->num, &p1->score); //输入新的节点数据；
    }
    p2->next = NULL; //将最终结点的指针域置空；
    free(p1); //释放p1的内存空间；
    return (head); //返回头指针；
}
//----------输出链表--------------
void print(struct student *head) {
    printf("总共有%d条学生记录\n", n);
    struct student *p; //建立新指针；
    p = head; //将指针指向head；
    while(p != NULL) {
        printf("\t%d\t%.2f\n", (*p).num, p->score);
        p = p->next;
    }//依次访问链表的值
}
//----------删除链表结点--------------------
struct student *del(struct student *head, int num) {
    struct student *p1, *p2; //建立新指针；
    p1 = head;
    while(p1->num != num && p1->next != NULL) {
        //当p1不是要删除的结点；
        p2 = p1;
        p1 = p1->next;
    }
    if(p1->num == num) {
        //找到要删除的结点；
        if(p1 == head)//在头部删除;
        head = p1->next;
        else
        p2->next = p1->next; //其余删除;
        free(p1);
        printf("delete:%d\n", num);
        n = n-1;
    }
    else
    printf("找不到该结点\n");
    return (head); //
}
//----------插入链表结点--------------------
struct student *insert(struct student *head, struct student *in) {
    struct student *p1, *p2, *p0; //建立新指针；
    p1 = head;
    p0 = in;
    while((p0->num > p1->num) && (p1->next != NULL)) {
        //当p0不是起始点和结尾点；
        p2 = p1;
        p1 = p1->next;
    }
    if(p0->num <= p1->num) {
        //找到要插入的位置；
        if(p1 == head) {
            head = p0; p0->next = p1;
        }//在头部插入;
        else
        {
            p2->next = p0; p0->next = p1;
        }//在中部插入;
    }
    else
    {
        p1->next = p0; p0->next = NULL;
    }//在尾部插入;
    n++;
    return (head); //
}

//----------主函数-------------
int main() {
    struct student *head, *stu;
    printf("请输入记录：\n");
    head = create(); //调用函数建立链表
    print(head); //调用函数输出链表

    int del_num;
    printf("请输入删除的编号：");
    scanf("%d",&del_num);
    while(del_num != 0) {
        head = del(head, del_num); //调用函数删除结点
        print(head);
        printf("请输入删除的编号：");
        scanf("%d", &del_num);
    }

    printf("请输入要插入的记录：");
    stu = (struct student*)malloc(sizeof(struct student));
    scanf("%d,%f", &stu->num, &stu->score);
    while(stu->num != 0) {
        head = insert(head, stu);
        print(head);
        printf("请输入要插入的记录：");
        stu = (struct student*)malloc(sizeof(struct student));
        scanf("%d,%f", &stu->num, &stu->score);
    }
    return 0;

---------------------------------------------
$ cpp main.c -o main.ii
$ cc main.ii -o main
$ ./main
请输入记录：
1,50
2,60
3,70
0,0
总共有3条学生记录
        1       50.00
        2       60.00
        3       70.00
请输入删除的编号：4
找不到该结点
总共有3条学生记录
        1       50.00
        2       60.00
        3       70.00
请输入删除的编号：2
delete:2
总共有2条学生记录
        1       50.00
        3       70.00
请输入删除的编号：0
请输入要插入的记录：4,60
总共有3条学生记录
        1       50.00
        3       70.00
        4       60.00
请输入要插入的记录：2,100
总共有4条学生记录
        1       50.00
        2       100.00
        3       70.00
        4       60.00
请输入要插入的记录：0
Program exited with status 0