欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C++学习(三十四)(C语言部分)之 链表

程序员文章站 2022-12-28 15:31:21
1、栈和队列 操作 增查改删重点 插入删除先进先出 -->队列先进后出 -->栈2、链表 写之前先画图存储数据的方式 通过指针将所有的数据链在一起数据结构的目的 管理存储数据 方便快速查找使用 链表定义 链式存储的线性表 一对一的关系结构体 指针 函数 循环 结构体复习:struct 点运算符(结构 ......

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

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

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

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

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

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

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

 

测试的代码笔记如下:

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 typedef struct node  //定义结构体
  5 {
  6     //数据  数据域
  7     int data;
  8     //指针  指针域  存放下一个节点的地址
  9     struct node*next;
 10 }node, *pnode;  //别名
 11 //结构体的类型里面不能放数据  变量里面放数据
 12 //pnode就是struct node*  结构体指针类型  就好比int和int*
 13 
 14 void insert(pnode head,int data)  //增
 15 {
 16     //准备要插入的节点
 17     pnode p = (pnode)malloc(sizeof(node));
 18     p->data = data;
 19     p->next = null;
 20     //开始插入
 21 #if 0    
 22     //头插法  head->a(没有数据)->c->d->null 指向要插入的节点b
 23     p->next = head->next;  //b 去保留c的地址
 24     head->next = p;  //a保留的是b的首地址
 25     //head->a(没有数据)->b->c->d->null
 26 #else
 27     //尾插法
 28     pnode temp;
 29     temp = head;  //找到第一个节点的位置
 30     while (temp->next!=null)  //判断是不是最后的节点 next是null
 31     { 
 32         temp = temp->next;
 33     }
 34     //循环退出之后 temp指向它的最后一个节点
 35     temp->next = p;
 36 
 37 #endif
 38 }
 39 
 40 void finddata(pnode head, int data)  //查
 41 {
 42     //查找
 43     pnode temp = head->next;  //从第二个元素开始
 44     while (temp!=null)  //从头到尾一个一个找
 45     {
 46         if (temp->data == data)
 47         {
 48             //数据匹配
 49         }
 50         temp = temp->next;
 51     }
 52     
 53     //pnode temp = head;
 54     //while (temp->next!=null)
 55     //{
 56     //    if (temp->next->data == data)  //temp指向第一个节点
 57     //    {
 58 
 59     //    }
 60     //    temp = temp->next;
 61     //}
 62 }
 63 
 64 void changenode(pnode head, int data, int newdata)  //改
 65 {
 66     //修改
 67     pnode temp = head->next;  //从第二个元素开始
 68     while (temp != null)  //从头到尾一个一个找
 69     {
 70         if (temp->data == data)
 71         {
 72             //数据匹配
 73             temp->data = newdata;  //修改数据
 74         }
 75         temp = temp->next;
 76     }
 77 }
 78 
 79 void delenode(pnode head, int data)  //删
 80 {
 81     //删除
 82     pnode p = head;
 83     while (p->next!=null)
 84     {
 85         if (p->next->data == data)  //下一个节点的data
 86         {
 87             //要删除的节点 p->next
 88             pnode temp = p->next;
 89             p->next = p->next->next;  //连接成功
 90             free(temp);  //释放掉temp  内存
 91         }
 92     }
 93 }
 94 
 95 void deleallnode(pnode head)  //释放所有节点
 96 {
 97     pnode temp;  //临时的指针作为辅助
 98     while (head != null)
 99     {
100         temp = head;
101         head = head->next;
102         free(temp);
103     }
104 }
105 
106 void print(pnode head)//打印全部节点
107 {
108     pnode temp = head->next;//从第二个元素开始   打印内容
109     while (temp != null)
110     {
111         printf("%d->", temp->data);
112         temp = temp->next;
113     }
114     printf("null)");
115 }
116 //链表 所有的节点都在堆区 用一个指针去管理这个链表 每次插入一个数据 重新申请节点
117 //事先申请好空间 数组/动态数组 临时申请
118 
119 int main()
120 {
121     pnode head;  //指针 结构体类型的指针
122     head = (pnode)malloc(sizeof(pnode)); //申请一个空的节点 为了后面的增查改删
123     //第一个节点可以窜数据但是不存 以浪费空间的代价 换取后面操作的简单
124     head->next = null;  //表示后面没有其他节点
125     for (int i = 0; i < 10; ++i)
126     {
127         insert(head, i);
128     }
129     print(head);
130     deleallnode(head);
131 
132     getchar();
133     return 0;
134 }

 

2019-04-01  08:31:37