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