第十七章 链表

NS流程图

NS分别是两位科学家的名字首字母 NS流程图是从流程图简化过来的去掉了其中的一些箭头而已

常见结构如下:

链表

1. 链表是一种常见的重要数据结构
2. 他是动态进行分配存储的一种结构
3. 特点:
   我们知道用数组批量存储数据,我们要先定义好数组,然而有时候我们并不知道要存储多少数据,因此通常就会先定义一个足够大的数组,那么这样就会造成内存的浪费.链表就没有这种弊端,他根据需要开辟内存单元.

单向链表结构:

根据上图可以看到如下特点:

1. 链表有一个”头指针”变量,图中以head表示,它存放一个地址,该地址指向一个元素.
2. 链表中每一个元素称为”结点”,每个结点包含两部分:
   • 用户需要用的实际数据
   • 下一个结点的地址
3. head指向第一个元素,第一个元素指向第二个元素…最后一个元素的地址存放一个空指针(NULL),不指向任何地址,表示链表结束
4. 链表中各元素在内存中的地址可以是不连续的.
5. 要找到某一个元素必须先找到上一个元素,根据他提供的地址找到
6. 如果不提供头指针(head),则整个链表无法访问
7. 通过链表结点我们看到,一种数据类型不仅能存储数据,而且还要存储指针,很显然基本数据类型不行,结构体是最好的选择,比如:

struct Student {
    int age;
    int score;
    char dengji;
    char *name;
    //结构体不可以递归定义
//    struct Student next;
    //但是可以递归指向
    //一个指针类型的成员变量,不仅可以指向其他类型的结构体数据,也可以指向自己所在结构体类型的数据
    struct Student *next;
};
上图9.8中的A,B,C,D就可以用这种结构体表示

建立简单的静态链表

代码如下:

#include<stdio.h>
struct Student {
    int num;
    float score;
    struct Student *next;

};
int main(){
    struct Student a,b,c, *head ,*p;
    a.num = 10101;a.score = 89.0;
    b.num = 10103;b.score = 89.0;
    c.num = 10107;b.score = 87;
    head = &a;
    a.next = &b;
    b.next = &c;
    c.next = NULL;
    p = head;
    do {
        printf("%d %5.1f\n",p->num,p->score);
        p = p->next;
    } while (p != NULL);
    return 0;
}

打印如下:

10101  89.0
10103  87.0
10107   0.0

用p的作用是可以分别拿到各个结点的地址,分别输出
本例中所有结点都是在程序中定义的,不是临时开辟的,也不能用完后释放,这种链表称为静态链表;

建立动态链表

所谓的建立动态链表是指在程序执行过程中从无都有的建立起一个链表,即一个一个的开辟结点和输入各个结点的数据,并建立起前后相连接的关系.
举例: 一个函数建议一个有3名学生数据的单向动态链表 一个函数将链表各节点数据依次输出,然后释放该结点
条件:当输入学号num = 0时结束
NS流程图如下:

代码如下:

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof(struct Student)
struct Student {
    int num;
    float score;
    struct Student *next;
};
int n;
//创建链表函数
struct Student * creat(){
    struct Student *head,*p1,*p2;
    n = 0;
    //开辟一个结点,p1,p2都指向这个结点
    p1 = p2 = (struct Student *)malloc(LEN);
    //给这个结点输入学号跟分数数据
    scanf("%d,%f",&p1->num,&p1->score);
    //使头结点为空指针
    head = NULL;;
    while (p1->num != 0) {
        n = n+1;
        //头结点,赋值head,此时head,p1,p2都指向第一个结点
        if (n == 1) head = p1;
         //把p1所指向的结点连接到表尾(注意,当n = 1时可不执行这一句哦!!!!)
        else p2->next = p1;
        //将p2移动到表尾
        p2 = p1;
        //开启一个新的结点使p1指向这个结点
        p1 =(struct Student *)malloc(LEN);
        //给这个结点填充数据
        //给这个结点输入学号跟分数数据
        scanf("%d,%f",&p1->num,&p1->score);
    }
    //设置表尾
    p2->next = NULL;
    return head;
}
//输出链表的函数
void print(struct Student * head){
    struct Student *p;
    struct Student *pp;
    p = head;
    if (head != NULL) {
        do{
            printf("\nnum:%d\nscore:%5.1f\n",p->num,p->score);
            pp = p;
            //释放结点
            free(pp);
            p = p->next;
        }while(p != NULL);
    }
}
int main(){
    struct Student *pt;
    pt = creat();
    print(pt);
    return 0;
}

终端如下:

10,99
11,98
12,87
0

num:10
score: 99.0

num:11
score: 98.0

num:12
score: 87.0

对链表中结点的删除和插入就不在介绍了;结构体和指针的应用领域很广泛,除了单向链表外还有环形链表,双向链表.此外还有队列/树/栈/图等数据结构也不再深入了