844 字
4 分钟
链表
我们存储很多数的时候，通常使用数组，但是数组不够灵活。
哦？为什么说不灵活？
我们如果要在一个数组前面或者中间插入一个数，就会很麻烦。
假设我们有一个数组a,里面是排序好的数字,我们要将7按大小顺序插入数组
我们就得把后面的数全都依次往后移一位，再将7放入。
这样如果后面的数非常多的话就会很耽误时间。
所以我们需要用到链表。
链表就是利用结构体和指针，在存储数据的同时，存储一个指向下一个结点的指针。
这样我们要插入数字的时候，只要修改下指针的指向，就可以快速的进行插入或取出之类的操作。
链表有很多种：
**单链表:**每个结点记录后继(图片演示的就是)
**双链表:**每个结点记录前驱和后继，它比单链多了个往前走的功能
**循环单链表:**将单链表的最后一个结点的后继指向第一个结点，形成一个环形结构
**循环双链表:**将双链表连成环形
…（还有几种就不一一列述了）
这里我们设计一个程序实现一下链表，首先输入四个按大小顺序排列的数字，然后再输入要插入的数字，
程序会输出插入后的排列
先上代码
#include <iostream>using namespace std;
struct node { int data;//存数据 node* next;//后继指针};
int main(){ int a; node* head, * p, * q = NULL; head = NULL; for (int i = 1; i < 5; i++) { //用指针p指向一个动态申请的node大小的空间 p = (node*)malloc(sizeof(node)); cin >> a; //将数据存入当前结点(p指向的结点) p->data = a; p->next = NULL;
if (head == NULL)head = p;//如果是第一个结点，就将头指针指向当前结点 else q->next = p;//否则将上一个结点的后继指针指向当前结点 q = p;//将q指向当前结点 }
//插入数据 int b; cin >> b; node* t = head;//从链表头开始遍历 while (t != NULL) { if (t->next->data > b) { p = (node*)malloc(sizeof(node)); //将数据存入当前结点(p指向的结点) p->data = b; p->next = t->next;//将当前结点的后继指针指向下一结点 t->next = p;//将上一结点的后继指针指向当前结点 break; } t = t->next;//下一结点 }
//输出 t = head;//从链表头开始遍历 while (t != NULL) { cout << t->data << endl; t = t->next;//下一结点 }
//释放动态申请的空间(确保安全) t = head; while (t != NULL) { node* current = t;//记录当前结点 t = t->next;//下一结点 free(current); } return 0;}代码不长，但是可能需要时间理解。
讲讲malloc函数，malloc函数的作用是动态分配内存。
每次输入数据前，我们就用p指向一个动态申请的新空间，然后存入数据。
程序的最后，我们用free()函数来释放动态申请的空间，这样可以让我们的程序更安全。
我们学习c语言和c++应该追求最大程度地优化，排除可能出现的问题。
分享文章
生成精美分享图或复制链接，与更多人分享本文。
继续阅读
换条路线
从其他文章中稳定抽取
最后更新于 ，距今已过 1356 天
部分内容可能已过时
评论