C++学习（三十四）（C语言部分）之 链表

1、栈和队列 操作 增查改删
重点 插入删除
先进先出 -->队列
先进后出 -->栈
2、链表 写之前先画图
存储数据的方式 通过指针将所有的数据链在一起
数据结构的目的 管理存储数据 方便快速查找使用

链表定义 链式存储的线性表 一对一的关系
结构体 指针 函数 循环

结构体复习：
struct 点运算符（结构体变量） 箭头运算符（结构体指针）
结构体变量.成员 的方式访问成员
字符数组 gets strcpy

链表操作
刚开始只有一个结构体
增 插入一个节点 需要申请内存
删 删除一个节点 需要释放内存

链表 需要插入的时候申请节点 需要删除的时候直接释放节点 会节约内存

静态数组 1.栈区大小 放不了态度数据
2.数组大小不能改变
动态数组 1.如果有一个数据 插入 重新申请内存 所有数据都要移动一次
2.插入删除不便
3.申请大的空间可能会申请失败

链表 有一个数据 申请一个 删除时只需要删除节点 不会影响其他节点
每次一个结构体大小 所以空间比较小 会比较节省内存 申请失败的可能性小
插入和删除比较简单不需要大规模的移动

 

测试的代码笔记如下：

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

typedef struct node  //定义结构体
{
    //数据  数据域
    int data;
    //指针  指针域  存放下一个节点的地址
    struct node*next;
}NODE, *PNODE;  //别名
//结构体的类型里面不能放数据  变量里面放数据
//PNODE就是struct node*  结构体指针类型  就好比int和int*

void insert(PNODE head,int data)  //增
{
    //准备要插入的节点
    PNODE p = (PNODE)malloc(sizeof(NODE));
    p->data = data;
    p->next = NULL;
    //开始插入
#if 0    
    //头插法  head->A（没有数据）->C->D->NULL 指向要插入的节点B
    p->next = head->next;  //B 去保留C的地址
    head->next = p;  //A保留的是B的首地址
    //head->A（没有数据）->B->C->D->NULL
#else
    //尾插法
    PNODE temp;
    temp = head;  //找到第一个节点的位置
    while (temp->next!=NULL)  //判断是不是最后的节点 next是NULL
    { 
        temp = temp->next;
    }
    //循环退出之后 temp指向它的最后一个节点
    temp->next = p;

#endif
}

void findData(PNODE head, int data)  //查
{
    //查找
    PNODE temp = head->next;  //从第二个元素开始
    while (temp!=NULL)  //从头到尾一个一个找
    {
        if (temp->data == data)
        {
            //数据匹配
        }
        temp = temp->next;
    }
    
    //PNODE temp = head;
    //while (temp->next!=NULL)
    //{
    //    if (temp->next->data == data)  //temp指向第一个节点
    //    {

    //    }
    //    temp = temp->next;
    //}
}

void changeNode(PNODE head, int data, int newData)  //改
{
    //修改
    PNODE temp = head->next;  //从第二个元素开始
    while (temp != NULL)  //从头到尾一个一个找
    {
        if (temp->data == data)
        {
            //数据匹配
            temp->data = newData;  //修改数据
        }
        temp = temp->next;
    }
}

void deleNode(PNODE head, int data)  //删
{
    //删除
    PNODE p = head;
    while (p->next!=NULL)
    {
        if (p->next->data == data)  //下一个节点的data
        {
            //要删除的节点 p->next
            PNODE temp = p->next;
            p->next = p->next->next;  //连接成功
            free(temp);  //释放掉temp  内存
        }
    }
}

void deleAllNode(PNODE head)  //释放所有节点
{
    PNODE temp;  //临时的指针作为辅助
    while (head != NULL)
    {
        temp = head;
        head = head->next;
        free(temp);
    }
}

void print(PNODE head)//打印全部节点
{
    PNODE temp = head->next;//从第二个元素开始   打印内容
    while (temp != NULL)
    {
        printf("%d->", temp->data);
        temp = temp->next;
    }
    printf("NULL)");
}
//链表 所有的节点都在堆区 用一个指针去管理这个链表 每次插入一个数据 重新申请节点
//事先申请好空间 数组/动态数组 临时申请

int main()
{
    PNODE head;  //指针 结构体类型的指针
    head = (PNODE)malloc(sizeof(PNODE)); //申请一个空的节点 为了后面的增查改删
    //第一个节点可以窜数据但是不存 以浪费空间的代价 换取后面操作的简单
    head->next = NULL;  //表示后面没有其他节点
    for (int i = 0; i < 10; ++i)
    {
        insert(head, i);
    }
    print(head);
    deleAllNode(head);

    getchar();
    return 0;
}

 

2019-04-01  08:31:37