0204：数据结构-比较

发表信息: October 06, 2018 by

文章分类:
算法 17

本文依照学习难度，分成入门、进阶两个部分。

入门部分以直观、易于理解为主；进阶部分重点在于概念、推导等。

入门

优缺点

使用数组存储数据时，当插入新数据，通常需要将数据移动到足够的连续空间里，或者在最初预留足够的空间

这样的存储方式麻烦且浪费

但是链表可以分开来存储

使用链表查询数据时，当需要读取最后一个元素时，不能直接读取，需要先访问第一个元素，由第一个元素获取第二个元素的位置，直至最后一个元素。

而数组的元素是连在一起的，可以想象成位置也是连着的，很容易计算得到第n个元素位置是多少。因此在随机读取元素时，数组的效率很高。

两者各有各的优点，各有各的缺点。最理想的当然是能组合两者，最大的发挥其中的优点。

链表数组是其中的一种组合方式。

链表数组

此时，存储新数据，如Adit时，首先访问数组的第一个元素，再访问该元素指向的链表，并将Adit添加到这个链表末尾。

现实中，会根据不同的应用场景选择不同的存储方式，再进行组合。比如Facebook实际使用的很可能是十多个数据库，它们基于众多不同的数据结构：散列表，B树等。数组和链表是这些更复杂的数据结构的基石。

模拟链表

前面的链表部分使用指针去链接下一个数（指出右边的数是谁）

链表还有另外一种使用数组来实现的方式，叫做模拟链表

这里面只需用一个数组来存放序列中每个数右边的数是谁就可以。

举个例子：

如上图所示，第一个整数数组data是用来存放序列中具体数字的；另一个整型数组right是用来存放当前序列中每一个元素右边的元素在数组data中未知的e

比如，right[1]的值为2，就表示当前序列中1号元素右边的元素存放在data[2]中。right[9]=0，表示当前序列9号元素的右边每一元素。

那插入操作如何做呢？

现在需要在8前面插入一个6.只需要将6存放在数组data的末尾。接下来将right[3]=10,right[10]=4.

如下图所示：

实现的代码是：

# 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]);
	..

进阶

[1] 算法图解 Aditya Bhargava (作者) 袁国忠 (译者)

目录

入门

优缺点

链表数组

模拟链表

进阶