• 欢迎访问hellobiancheng.com 本站包含大量编程教程、编程工具软件以及学习资源!

数组模拟单链表实现最优化

编程经验 小小丁更努力 17次浏览 0个评论

数组模拟单链表实现最优化

什么是链表?

1、链表是物理存储单元上非连续的、非顺序的存储结构,数据元素的逻辑顺序是通过链表的指针地址实现,有一系列结点(地址)组成,结点可动态的生成。
2、结点包括两个部分:
(1)存储数据元素的数据域(内存空间)。
(2)存储指向下一个结点地址的指针域。
3、相对于线性表顺序结构,操作复杂。
4.链表分为:
(1)单链表 (2)双链表 (3)单向循环链表 (4)双向循环链表。

写在前面

要发挥链表动态分配内存空间的优势,需要使用指针建立链表。但是,在信息学竞赛中,我们基本上不需要过多考虑动态空间分配,所以,使用数组模拟链表就可以很好的实现链表数据结构。

数组模拟链表,是一种半静态链表,是链表的线性存储,比链式存储要简单的多了,最大的优点是快很多。每个链表可以用一对数组或一个记录数组表示,每个元素是有两个数据域:分别是数据 data 域和下一个结点在数组中的位置 next 域(整型的)。这样插入,删除,遍历等,都可以归结到数组操作了,这就比链式存储容易多了,却不丧失链表快速插入删除的优势。

数组模拟单链表和普通链式单链表时间比较

链式单链表实现

数据输入:
5
1 2 3 4 5
数据输出:
1 2 3 4 5
#include 
using namespace std;
int n;
typedef struct LNode
{
	int data;
	struct LNode* next;
}SqList, * LinkList;
void InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
}
void ListInsert(LinkList &L)
{
	cin >> n;
	LNode* p, * r;
	r = L;
	for (int i = 0; i < n; i++) { p = new LNode; cin >> p->data;
		p->next = NULL;
		r->next = p;
		r = p;
	}
}
void print(LinkList L)
{
	LNode* p;
	p = L->next;
	while (p)
	{
		cout << p->data << " "; p = p->next;
	}
	cout << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	LinkList L;
	InitList(L);
	ListInsert(L);
	print(L);
	free(L);
	return 0;
}

数组模拟单链表实现最优化
数组模拟单链表实现

数据输入:
5
1 2 3 4 5
数据输出:
1 2 3 4 5
#include 
using namespace std;
const int N = 1000010;
int e[N], ne[N];
int head, idx, n;
void Init()
{
	head = -1;
	idx = 0;
}
void add_to_head(int x)
{
	e[idx] = x;
	ne[idx] = head;
	head = idx++;
}
void add(int k, int x)
{
	e[idx] = x;
	ne[idx] = ne[k];
	ne[k] = idx++;
}
int main()
{
	Init();
	cin >> n;
	int x, k = 0;
	cin >> x;
	add_to_head(x);
	n--;
	while (n --)
	{
		int x;
		cin >> x;
		add(k ++, x);
	}
	for (int i = head; i != -1; i = ne[i]) cout << e[i] << " ";
	cout << endl;
	return 0;
}

数组模拟单链表实现最优化
根据上面的代码对比可以清楚的看到,利用数组模拟单链表程序运行时间远远的小于链式结构下的代码,这也是数组模拟单链表最大的优点之一,下面就来介绍数组模拟单链表具体的代码书写方式。

数组模拟单链表

实现一个数组 e[ ] 代表数据域,ne[ ] 代表下一个结点的下标,idx 表示的是当前结点的下标;

  • 链表的初始化;
  • 链表头插入一个结点;
  • 在链表的第 k 个输入的数后面插入一个数 x;
  • 删除第 k 个输入的数后面的数;

模板

// head存储链表头,e[]存储节点的值,ne[]存储节点的next指针,idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;

// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数a
void insert(int a)
{
    e[idx] = a, ne[idx] = head, head = idx ++ ;
}

// 将头结点删除,需要保证头结点存在
void remove()
{
    head = ne[head];
}
C语言网提供「C语言、C++、算法竞赛」在线课程,全部由资深研发工程师或ACM金牌大佬亲授课,更科学、全面的课程体系,以在线视频+在线评测的学习模式学习,学练同步,拒绝理论派,真正学会编程!还有奖学金等增值福利等你!

你好编程, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明数组模拟单链表实现最优化
喜欢 (0)
[jinyangH@aliyun.com]
分享 (0)
发表我的评论
取消评论
表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)