C 语言 初探链表

hack_hu

思维导图
思维导图在学习链表之前我们要先了解 结构 、 空指针 C 语言除了数组还有 ： 结构 、 联合和枚举三种类型结构 ( struct ) ： 可以是多种不同类型数据的成员集合 ， 成员之间存储在不同的内存地址。
简单示例struct Person //声明一个结构类型
    {
        char name[8];
        int age;
    };
    Person programmer = {"hack-hu",99};
    printf(" 码农的名字 ： %s , 码农的年龄 ： %d",programmer.name,programmer.age);
联合 ( union ) ：联合类似于结构 ， 但是只为其中最大的成员分配内存空间 ， 每次为联合成员赋值 ， 之前的值全部会被覆盖。union select
    {
        int i;
        float n;
    };
    select num ;
    num.i = 1;
    printf("%d\n",num.i);
    num.n = 1.62;
枚举是一个整数型成员 ， 值由成员命名， 默认从 0 开始。enum  // 声明一个枚举类型
    {
        red,
        black,
        blue,
        yellow
    }color;
    int one = red;
    printf("%d\n",one);
    int select[] = {1,2,3};
    select[red] = 11;
    printf("%d", select[red]);//枚举成员可作为数组下标使用这样显示的效果更为直观
动态内存分配

• C 语言支持动态存储分配， 即在程序执行期间分配内存单元的能力。动态分配内存可以根据需要扩大（ 缩小 ）数据结构。
• -> 运算符在指针访问成员中非常常用 例 ( *p ).next 我们可以简写为 p->next 代码更为简洁 。
• 动态存储分配适用于所有类型数据， 但主要用于字符串、 数组和结构。
• 为了动态的分配存储空间，需要调用三种内存分配函数的一种，这些函数都是声明在 库  中，所以在使用前要先引入。
  • malloc 函数 —— 分配内存块， 但是并不对内存块进行初始化。
    
  
  

struct Person
    {
        char name[8];
        int age;
    };
    Person *programmer = (Person *)malloc(sizeof(Person));// 给programmer 分配动态内存 ， 需要将分配内存的类型转换成 Person*
    programmer->age=99;

• calloc 函数 —— 分配内存块， 并且对内存块进行清零。
  

struct Person
    {
        char name[8];
        int age;
    };
    Person *programmer = (Person *)calloc(1,sizeof(Person));// 给programmer 分配 数量为 1 ，每个单位为 Person 结构体需要的内存大小
    printf("%d\n",programmer->age);// calloc自动初始化数据为 0
    programmer->age=99;

• realloc 函数 —— 调整前先分配内存块大小。
  

int a = (int)malloc(sizeof(int));
    a = (int)realloc(&a,sizeof(long));//将 a 分配的内存块调整为 long 大小 ， 可以调大内存也可以调小内存

  因为 malloc 函数不需要对分配的内存块进行清零， 所以比 calloc 函数更高效。

• free 函数， 释放所分配的内存
  

    int a = (int)malloc(sizeof(int));
    a = (int)realloc(&a,sizeof(long));//将 a 分配的内存块调整为 long 大小 ， 可以调大内存也可以调小内存
    free(a); //释放 a 所分配的内存

---

  所有动态内存分配所获得的内存块都来自于 “ 堆 ”（ heap ） 的存储池。 过于频繁，       且不回收的调用堆中的内存块会耗尽堆的内存，当堆中的内存耗尽时， 指针会返回空指针。  对程序而言， 不再访问到的内存被称为垃圾。 留有垃圾的程序存在 “ 垃圾泄露 ” 。在 C# 中提供了 垃圾回收， 而 C 语言中并不提供， 这个工作由 free 函数接管。  程序中很容易在给一个变量动态内存分配后又丢失对这些内存块的记录。 例 ： int p=malloc( nsizeof( int ) ) ; int q = malloc( msizeof( int ) ) ; q=p; 此时对 p 之前分配的内存块记录丢失。  悬空指针， 指针 动态分配的内存被 free 函数释放， 但是 指针本身还是存在的， 当指针再次进行内存写入操作时， 程序就会报错， 因为此时指针并没有内存可以用来存储数据。  一旦指针指向动态分配的内存块， 指针就可以当作数组来使用 （ 字符串实际上和数组的在内存的存储上是一致的，都是以 ASCLL码形式存储 ）

空指针

• 不指向任何地方的指针。
• 当调用内存分配函数， 找不到足够的内存块时，函数就会返回 “ 空指针 ”。 空指针是判断函数内存分配是否成功的重要标准 ，所以对于返回的指针变量我们要判断该指针变量是否为空指针。
• 判断指针是否为空的方法和数的测试一般， 所有非空指针为真， 空指针为假（ 0 ）。
  

链表

• 链表是由一串的结构 （ 称为 结点 ）组成的， 每个结点都包含指向链表中下一个结点的指针， 而链表中的最后一个结点包含一个 空指针。
  

    struct node  //定义一个包含指针的结构体
{
    int value;
    struct node *next;
};
    /* 每个结点中的指针都指向了下一个结点的地址 */
    node p1 = { 1,NULL },
         p2 = { 2,NULL },
         p3 = { 3,NULL };
    p1.next = &p2;
    p2.next = &p3;
    p3.next=NULL;
    node *head=&p1;//定义指针 head 从头节点开始遍历链表
    while (head!=NULL)
    {
        printf("%d ",head->value);// 输出当前 结点 （ 结构体 ）中的数据 即 value
        head = head->next;//让指针指向下一个结点
    }
    printf("\n");
在代码中每一个结点 （ 定义的三个结构体变量 ） 都有一个指向下一结点的指针 ， 其中最后一个结点中的指针指向空 ， 这就是 “ 单链表 ” 的基本形式 ，下面根据这个代码的基础进行 链表的基本操作。    struct node  //定义一个包含指针的结构体
{
    int value;
    struct node *next;
};
    node *p1 = (node *)malloc(sizeof(node)),
     *p2 = (node *)malloc(sizeof(node)),
     *p3 = (node *)malloc(sizeof(node));
/* 初始化链表数据 */
p1->value = 1;// (*p1).value 可以简写为 p1->value
p2->value = 2;
p3->value = 3;
/* 将结点之间串联 */
p1->next = p2;
p2->next = p3;
p3->next = NULL;
node *p = p1;//定义头结点

/* 尝试头结点插入结点 */
node first = {11,NULL};
first.next = p;//first 指向的结点为 p当前所在的结点 即 p1
p = &first;//指针 p 指向结点 first
printf("头结点插入\n");
while (p!=NULL)//输出结点数据
{
    printf("%d ",p->value);
    p=p->next;
}
printf("\n");
链表插入的主要点在于 先判断插入点 的 上一结点 和 下一结点 指向谁 ， 插入点的上一结点应当指向当前结点 ， 而插入结点 应当 指向下一结点。
可以把结点中的指针当作一场接力 ， 弄清楚该从谁手中接过 又该送到谁手上 。p = &first;//指回头结点

/* 尝试在链表中点中插入结点 */
node two = {22,NULL};
//printf("链表中插入\n");
while (p->next!=NULL)
{

    if (p->value == 2)
    {
        two.next = p->next;
        p->next = &two;
    }
    p=  p->next;
}
//p = &first;//指针 p 指向结点 first
/* 尝试在尾部插入结点 */
printf("当前结点的值 %d \n",p->value);
node last = {99,NULL};
p->next = &last;//将尾指针指向要增加的结点
last.next = NULL;//尾指针指向 NULL
p = &first;//指回头结点
while (p != NULL)
{
    printf("%d ", p->value);
    p = p->next;
}
printf("\n");
链表中的删除 要联想到 指针的增加 几个人的接力赛跑中 有名选手退出了 ，那他的上一个队友只要记住 下场的那民选手传给的是谁 ， 把本该给 下场选手的接力棒传给 他的下一名选手就好了/* 删除指定结点 */

printf(" 请输入要删除的结点数据值 ");
int n;
node *q1;
scanf("%d",&n);
p = &first;
q1 = p->next;
while (q1->value!=n)
{
    p = p->next;
    q1 = p->next;
}
p->next = q1->next;

while (p != NULL)
{
    printf("%d ", p->value);
    p = p->next;
}
printf("\n");
总结 ：
要弄清楚链表 ， 需要先弄清楚指针 ， 结点中的指针上一个指向下一个 ，直到达到终点 （ 读到空指针 ）时退出 ， 这样看起来 ， C 语言中字符串的存储和链表有一定的相似之处。

hack_hu

璞玉晨星 发表于 2018-11-28 22:43
迷迷糊糊 看不太懂

需要一定的指针基础

hack_hu

xushiweiq 发表于 2018-12-10 15:47
了解C 之后  学什么都没那么难了，，顶起

从基础开始更容易理解本质 ， 目前流行的语言大多是在 C 语言的基础上开发的 ， 所以语法也基本类似学习的成本小。

ling441

人生得意一杯酒，饮过方知此中愁

陌小全

可我只懂Hello world

xieyunsky

学习学习

hxy

去年学了C++，感觉好难啊

hxy

H5网页制作挺有意思

hack_hu

ling441 发表于 2018-11-26 14:10
人生得意一杯酒，饮过方知此中愁

故事都在心里

hack_hu

陌小全 发表于 2018-11-26 14:15
可我只懂Hello world

编程的开始

hack_hu

hxy 发表于 2018-11-26 15:29
H5网页制作挺有意思

以前做过没有深入 ， 现在全部重头开始学

runfog

C 语言除了数组还有 ： 结构 、 联合和枚举三种类型结构