首页 > 代码库 > 链表和模拟链表[插入数字]
链表和模拟链表[插入数字]
有一串已经从小到大排好序的数2 3 5 8 9 10 18 26 32。现需要往这串数中插入6使其得到的新序列仍符合从小到大排列。如我们使用数组来实现这一操作，则需要将8和8后面的数都依次往后挪一位，如下
这样操作显然很耽误时间，如果使用链表则会快很多。
此时如果需要在8前面插入一个6，就只需像下图这样更改一下就可以了，而无需再将8及后面的数都依次往后挪一位。是不是很节省时间呢？
那么如何实现链表呢？在C语言中可以使用指针和动态分配内存函数malloc来实现。
指针大家都很熟悉了，下面说下动态存储方法
malloc(4);malloc函数的作用就是从内存中申请分配指定字节大小的内存空间。上面这行代码就申请了4个字节。如果你不知道int类型是4个字节的，还可以使用sizeof(int)获取int类型所占用的字节数，如下：
malloc(sizeof(int));现在你已经成功地从内存中申请了4个字节的空间来准备存放一个整数，可是如何来对这个空间进行操作呢？这里我们就需要用一个指针来指向这个空间，即存储这个空间的首地址。
int *p; p=(int *)malloc(sizeof(int));需要注意，malloc函数的返回类型是void * 类型。void * 表示未确定类型的指针。在C和C++中，void * 类型可以强制转换为任何其他类型的指针。上面代码中我们将其强制转化为整型指针，以便告诉计算机这里的4个字节作为一个整体用来存放整数。为什么要分不同类型的指针呢？因为指针变量存储的是一个内存空间的首地址（第一个字节的地址），但是这个空间一共占用了多少个字节，用来存储什么类型的数，则是由指针的类型来标明的。这样系统才知道应该取多少个连续内存作为一个数据。
#include <stdio.h>
#include <stdlib.h>
//这里创建一个结构体用来表示链表的结点类型
struct node
{
int data;
struct node *next;
};
int main()
{
struct node *head,*p,*q,*t;
int i,n,a;
scanf("%d",&n);
head = NULL;//头指针初始为空
for(i=1;i<=n;i++)//循环读入n个数
{
scanf("%d",&a);
//动态申请一个空间，用来存放一个结点，并用临时指针p指向这个结点
p=(struct node *)malloc(sizeof(struct node));
p->data=http://www.mamicode.com/a;//将数据存储到当前结点的data域中>
如果你压根就很讨厌指针这些东西，没关系！链表还有另外一种使用数组来实现的方式，叫做模拟链表。链表中的每一个结点只有两个部分。我们可以用一个数组data来存储每序列中的每一个数。那每一个数右边的数是谁，这一点该怎么解决呢？这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了。
上图的两个数组中，第一个整型数组data是用来存放序列中具体数字的，另外一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中位置的。例如right[1]的值为2，就表示当前序列中1号元素右边的元素存放在data[2]中；如果是0，例如right[9]的值为0，就表示当前序列中9号元素的右边没有元素。现在需要在8前面插入一个6，只需将6直接存放在数组data的末尾即data[10]=6。接下来只需要将right[3]改为10，表示新序列中3号元素右边的元素存放在data[10]中。再将right[10]改为4，表示新序列中10号元素右边的元素存放在data[4]中。这样我们通过right数组就可以从头到尾遍历整个序列了（序列的每个元素的值存放在对应的数组data中），如下。
#include <stdio.h>
int main()
{
int data[101],right[101];
int i,n,t,len;
//读入已有的数
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&data[i]);
len=n;
//初始化数组right
for(i=1;i<=n;i++)
{
if(i!=n)
right[i]=i+1;
else
right[i]=0;
}
//直接在数组data的末尾增加一个数
len++;
scanf("%d",&data[len]);
//从链表的头部开始遍历
t=1;
while(t!=0)
{
if(data[right[t]]>data[len])//如果当前结点下一个结点的值大于待插入数，将数插入到中间
{
right[len]=right[t];//新插入数的下一个结点标号等于当前结点的下一个结点编号
right[t]=len;//当前结点的下一个结点编号就是新插入数的编号
break;//插入完成跳出循环
}
t=right[t];
}
//输出链表中所有的数
t=1;
while(t!=0)
{
printf("%d ",data[t]);
t=right[t];
}
return 0;
}
链表和模拟链表[插入数字]