链表

在存储一大波数的时候，我们通常使用数组，但有时候数组显得不够灵活。比如需要向一组已经排好序的数中插入一个数，插入后仍然是按从小到大的顺序。如果用数组来实现这一操作，需要把这个数以后的所有数往后移，这样的操作显然很耽误时间。这里，用链表会很省时间的解决这一问题。

在c语言中，可以使用指针和动态分配内存函数malloc来实现。

指针用来存储一个内存空间的地址；

malloc函数的作用是从内存中申请分配指定字节大小的内存空间。

如，malloc(4);此代码申请了4个字节的内存空间，等同于malloc(sizeof(int));。需要记住，在程序中使用malloc函数时需要用到stdlib.h头文件。

相应代码：

#include<iostream>#include<stdio.h>#include<stdlib.h>#include<cstdio>#include<cstdlib>using namespace std;//创建一个结构体用来表示链表的结点的类型struct node {	int data;	struct node *next;//指针用来存储下一个结点的地址，因为下一个结点的类型是struct node，所以这个指针的类型也必须是struct node *类型的指针};int main() {	struct node *head, *p, *q=0, *t;	int n, a;	scanf("%d", &n);	head = NULL;//头指针初始为空	for (int i = 1; i <= n; i++) {		scanf("%d", &a);		//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点		p = (struct node *)malloc(sizeof(struct node));		p->data = a;//将数据存储到当前结点的data域中		p->next = NULL;//设置当前结点的后继指针指向空		if (head == NULL)			head = p;//如果这是第一个创建的结点，则将头指针指向这个结点		else			q->next = p;//如果不是第一个创建的结点，则将上一个结点的后继指针指向当前结点		q = p;//指针q也指向当前结点	}	scanf("%d", &a);//读入待插入的数	t = head;//从链表头部开始遍历	while (t != NULL) {//当没有到达链表尾部时循环		if (t->next == NULL || t->next->data > a) {//如果当前结点是最后一个或者下一个结点的值大于待插入数时			p = (struct node *)malloc(sizeof(struct node));//动态申请一个空间，用来存放新增节点			p->data = a;			p->next = t->next;//新增节点的后继指针指向当前结点的后继指针所指向的结点			t->next = p;//当前结点的后继针针指向新增结点			break;//插入完毕退出循环		}		t = t->next;//继续下一个结点	}	//输出链表中的所有数	t = head;	while (t != NULL) {		PRintf("%d ", t->data);		t = t->next;	}	system("pause");	return 0;}
代码实现：