C语言链表之回顾

知识总结

结构

建立结构声明

struct book{
    char title[MAXTITL];
    char author[MAXAUTL];
    float value;
};    // 结构布局定义结束

定义结构变量

struct book library;    // 把library声明为一个使用book结构布局的结构变量

编译器使用book模板为该变量分配空间：一个内含MAXTITL格元素的char数组、一个内涵MAXAUTL个元素的char数组和一个float类型的变量；

在结构变量的声明中，struct book就相当于一般声明中的int或者float，可以定义变量或者指针

声明+定义

struct book{
    char title[MAXTITL];
    char author[MAXAUTL];
    float value;
}library;    // 声明的右花括号后跟变量名

也可以使用无结构标记，即去掉book

初始化结构

struct book library = {
    "Hello C",
    "xherlock",
    100.0
};

访问结构成员

library.title    // char型变量
library.author    // char型变量
library.value    // float型变量

和数组不同的是，结构名并不是结构的地址，因此要在结构名前加上运算符

typedef

为某一类型自定义名称

eg：

typedef unsigned char BYTE;    // 自定义BYTE类型变量
BYTE x,y[10],*z;

typedef没有创建任何新类型，只是为某个已存在的类型增加了一个个方便使用的标签

理解链表中的p=p->next

借了网上的图，这样好理解多了

代码

#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{
    int data;
    struct node *next;
};

int main()
{
    struct node *head,*p,*q,*t;
    int i,n,a;
    scanf("%d",&n);
    head = NULL;//头指针初始为空
    for(i=1;i<=n;i++)//循环读入n个数
    {
        scanf("%d",&a);
        //动态申请一个内存空间，用来存放一个结点，并用临时指针p指向这个结点
        p=(struct node *)malloc(sizeof(struct node));
        p->data=a;//将数据存储到当前结点的data域中
        p->next=NULL;//设置当前结点的后继指针指向空，也就是当前结点的下一个结点为空
        if(head==NULL)
            head=p;//如果这是第一个创建的结点，则将头指针指向这个结点
        else
            q->next=p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点
        q=p;//指针q也指向当前结点
    }
    //输出链表中的所有数
    t=head;
    while(t!=NULL)
    {
        printf("%d ",t->data);
        t=t->next;//继续下一个结点
    }
    getchar();getchar();
    return 0;
}

静态链表

#include <stdio.h>  // 标准输入输出头文件
#include <stdlib.h> // 包含了C、C++语言最常用的系统函数

#define LEN sizeof(struct Student)  // 宏定义节点长度
#define TYPE struct Student // 宏定义结构体变量名称

struct Student  // 定义一个学生类型结构体，包括学号、分数
{
    long num;
    float score;
    struct Student *next;   // next是指针变量，指向结构体变量
};
// 指向结构体对象的指针变量既可以指向结构体变量，也可以指向结构体数组中的元素

int main()
{
    TYPE *head, *p; // 定义头指针
    struct Student a, b, c;
    a.num = 101;
    a.score = 20;
    b.num = 102;
    b.score = 20;
    c.num = 103;
    c.score = 20;
    /*1、A.B则A为对象或者结构体
      2、A->B则A为指针，->是成员提取，A->B是提取A中的成员B，A只能是指向类、结构、联合的指针；
     */
    head = &a;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    p = head;   // 把首地址给变量
    do
    {
        printf("%ld %5.1f\n", p->num, p->score);
        p = p->next;    // 不断循环将a,b,c地址传递给p，直到p为NULL
    } while (p != NULL);
    return 0;
}

动态链表

#include <stdio.h>  // 标准输入输出头文件
#include <stdlib.h> // 包含了C、C++语言最常用的系统函数
#include <malloc.h> // 动态存储分配函数头文件

#define LEN sizeof(struct Student)  // 宏定义节点长度得命名
#define TYPE struct Student // 宏定义结构体变量命名

struct Student  // 定义一个学生类型结构体，包括学号、分数
{
    long num;
    float score;
    struct Student *next;   // next是指针变量，指向结构体变量
};
// 指向结构体对象的指针变量既可以指向结构体变量，也可以指向结构体数组中的元素

TYPE* Creat(void)   // 定义函数，此函数返回一个指向链表头的指针
{
    TYPE *head; // 定义头指针
    TYPE *p1, *p2;  // 定义两个指针来相互保存
    int number = 0;
    p1 = p2 = (TYPE *)malloc(LEN);  // 创建存储空间
    printf("请按格式输入学生学号，分数(eg:101,2/102,3)\n");
    scanf("%ld,%f", &p1->num, &p1->score);
    head = NULL;    // 第一个结点头指针赋空值
    while(p1->num != 0) // 循环直到学生学号为0
    {
        number++;   // 结点自增，用来判断是否为头指针
        if(number == 1)
            head = p1;
        else
            p2->next = p1;  // 如果大于一个，用p2的next指针保存前一个结点p1的信息
        p2 = p1;    // 保存前一个结点的信息
        p1 = (TYPE *)malloc(LEN);   // 开辟新结点
        scanf("%ld,%f", &p1->num, &p1->score);  // 输入下一个结点的信息
    }
    p2->next = NULL;    // 循环结束后将指向信息赋空值
    return (head);  // 返回首地址
}

int Length(TYPE *head)
{
    TYPE *p;
    int num = 0;
    p = head;
    if (head != NULL)
    {
        do
        {
            num++;
            p = p->next;
        } while (p != NULL);
    }
    return num;
}

void Print(TYPE *head, int len)
{
    TYPE *p;    // 定义指针
    printf("\nNOW These %d records are:\n", len);
    p = head;   // 指向第一个结点
    if (head != NULL)
        do
        {
            printf("%ld %5.1f\n", p->num, p->score);    // 给指针赋值
            p = p->next;    // 指向下一结点
        } while (p != NULL);
}

void Change(TYPE *head, int n)
{
    TYPE *p = head; // 传入首地址
    int i = 0;
    while (i < n && p != NULL)
    {
        p = p->next;
        i++;
    }
    if (p != NULL)
    {
        printf("输入要修改的值\n");
        scanf("%ld,%f", &p->num, &p->score);
    }
    else
        printf("结点不存在\n");
}

void Delete(TYPE *head, int n)
{
    TYPE *p = head, *in = NULL;    // 定义两边指针
    int i = 0;
    while (i < n && p != NULL)
    {
        in = p;         // 找到左边的
        p = p->next;    // 找到右边的
        i++;
    }
    if (p != NULL)
    {
        in->next = p->next; // 将左右连接
        free(p);    // 释放中间结点的存储空间
    }
    else
        printf("结点不存在\n");
}

void Insert(TYPE *head, int n)
{
    TYPE *p = head, *in = NULL;    // 定义两边指针
    int i = 0;
    while (i < n && p != NULL)
    {
        in = p;         // 找到左边的
        p = p->next;    // 找到右边的
        i++;
    }
    if (p != NULL)
    {
        in = (TYPE *)malloc(sizeof(TYPE));
        printf("请输入要插入的值：");
        scanf("%ld,%f", &in->num, &in->score);
        in->next = p->next; // 填充in结点的指针域，也就是把in的指针域指向p的下一个结点
        p->next = in;   // 填充p结点的指针域，把p的指针与重新指向in
    }
    else
        printf("结点不存在\n");
}

int main()
{
    TYPE *pt;
    pt = Creat();
    // printf("\nnum:%ld\nscore:%3.lf\n", pt->num, pt->score);
    printf("请输入你要对链表进行的操作：\n");
    printf("***********************\n");
    printf("1) 求长度\n");
    printf("2) 输出\n");
    printf("3) 修改\n");
    printf("4) 删除\n");
    printf("5) 插入\n");
    printf("6) 退出\n");
    printf("***********************\n");
    int num = 0;
    int len = Length(pt);
    while (1)
    {
        printf("请输入数字选项：");
        scanf("%d", &num);
        int n;
        switch (num)
        {
            case 1:
                printf("链表长度为 %d \n", len);
                break;
            case 2:
                Print(pt, len);
                break;
            case 3:
                printf("请输入你要修改的位置：");
                scanf("%d", &n);
                Change(pt, n);
                break;
            case 4:
                printf("请输入你要删除的位置：");
                scanf("%d", &n);
                Delete(pt, n);
                break;
            case 5:
                printf("请输入你要插入的位置：");
                scanf("%d", &n);
                Insert(pt, n);
                break;
            case 6:
                printf("成功退出！");
                exit(0);
            default:
                break;
        }
    }
    return 0;
}

后面还得再学习下大一上C语言课程的对链表和文件操作的测试