数据结构--链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

相较于数组,链表有以下优点:

逻辑结构

(1)链表采用动态内存分配的方式,在内存中不连续 (2)支持动态增加或者删除元素 (3)需要时可以使用malloc或者new来申请内存,不用时使用free或者delete来释放内存

内存结构

链表从堆上分配内存,自由度大,但是要注意内存泄漏

访问效率

链表访问效率低,如果想要访问某个元素,需要从头遍历

越界问题

指针一般使用$ malloc $关键字申请动态内存,只要可以申请得到链表空间,链表就无越界风险

链表的基本操作

创建链表

这里用结构体(struct)存储链表。不同于C++,C语言中新定义结构体变量需要以下格式

struct Data a;

使用typedef关键字后可直接用Sqlist来定义变量
next指针指向表中下一个数据

typedef struct Data {
	int value;
	struct Data* next;
}Sqlist;

malloc 为库<stdlib.h>中的函数,用于动态分配内存,传入所需内存大小,返回值为类型为void的指针,这里使用(Sqlist *)强制转换

Sqlist* Init()
{
	Sqlist* t = (Sqlist*)malloc(sizeof(Sqlist));
	t->value = 1;
	t->next = NULL;
	return t;
}
在pos后插入数值

传入参数为插入数值的位置pos和数值,从头开始遍历链表直到第pos个位置,新建一个节点,将pos指向新节点,新节点指向pos的下一个节点(pos->next)

Sqlist* Create_node()
{
	Sqlist* node = (Sqlist*)malloc(sizeof(Sqlist));;
	return node;
}
Sqlist* getPos(Sqlist*head,int pos)
{
	Sqlist* t = head;
	int i = 1;
	while (i != pos && t != NULL)
	{
	t = t->next; i++;
	}
	return t;
}
void Insert(Sqlist* head, int pos, int value)
{
	Sqlist* t = getPos(head,pos), * newNode = Create_node;
	newNode->value = value;
	t->next = newNode;
	if (t == NULL)//t 为最后一个节点,没有next
	{
	return;
	}
	newNode->next = t->next;
}
删除节点pos

记录下当前节点的前一个节点pre,将pre->next指向pos->next,释放pos的内存

void Delete(Sqlist* head, int pos)
{
	Sqlist* t = head,*pre=head; int i = 1;
	while (i != pos && t != NULL)
	{
	pre = t;
	t = t->next;
	i++;
	}
	if (t != NULL)
	{
	pre->next = t->next;
	free(t);
	}
}

基本操作大概就这些,根据实际问题灵活运用。
提供luogu上的一道练习题luogu
由于用指针维护链表每次操作都需要从头遍历,导致效率不尽人意,想要AC这道题可以考虑使用数组模拟链表
如果出现了RE,可能是调用了NULL->next

附70ptsCODE

展开查看
 
#include
#include
using namespace std;
typedef struct data
{
	int value;
	struct data* next;
}Sqlist;
int Length = 0;
Sqlist* Create()
{
	Sqlist* node = (Sqlist*)malloc(sizeof(Sqlist));
	Length++;
	return node;
}
Sqlist* Init()
{
	Sqlist* head;
	head = Create();
	head->value = 1;
	head->next = NULL;
	return head;
}
void Delete(Sqlist* head, int ith)
{
	Sqlist* t = head, * pre=head;
	int i = 1;
	while (i != ith && t != NULL)
	{
	pre = t;t = t->next; i++;
	}
	pre->next = t->next;
	free(t); Length--;
}
void Insert(Sqlist* head, int ith, int data)
{
	Sqlist* t = head,*newnode = Create();
	int i = 1;
	while (i != ith && t != NULL)
	{
	t = t->next; i++;
	}
	newnode->value = data;
	newnode->next = t->next;
	t->next = newnode;
}
int Locate(Sqlist* head, int Target)
{
	Sqlist* t = head; int pos=1;
	while (t != NULL)
	{
	if (t->value == Target)return pos;
	t = t->next; pos++;
	}
	return 0;
}
int Query(Sqlist* head, int pos)
{
	Sqlist* t = head;
	int i = 1;
	while (t != NULL && i != pos)
	{
	t = t->next; i++;
	}
	return t->value;
}
void print(Sqlist* head)
{
	Sqlist* t = head;
	while (t != NULL)
	{
	printf("%d ", t->value);
	t = t->next;
	}
	puts("");
}
inline int read()
{
	char c = getchar(); int res = 0;
	while (c < '0' || c>'9')c = getchar();
	while (c >= '0' && c <= '9') {
	res = (res << 1) + (res << 3) + (c - '0'); c = getchar();
	}
	return res;
}
void work()
{
	int q = read();
	Sqlist* L = Init();
	for (int i = 1; i <= q; ++i)
	{
	int var = read(),x,y;
	if (var == 1)
	{
	x = read(), y = read();
	int pos= Locate(L, x);
	Insert(L, pos, y);
	}
	if (var == 2)
	{
	x = read();
	int pos=Locate(L, x);
	if (pos == Length)printf("0\n");
	else {
	printf("%d\n",Query(L,pos+1));
	}
	}
	if (var == 3)
	{
	x = read();
	int pos = Locate(L, x);
	Delete(L, pos+1);
	}
	}
}
int main()
{
	work();
	return 0;
}
 

\(UPD\)

看了一眼链表合并,发现如果不在头指针中保存value会好处理一些
重构了一部分代码

初始化

Sqlist* Init(int n)
{
	Sqlist* t = Create_node(),*tail=t;
	for (int i = 1; i <= n; ++i)
	{
	Sqlist* newNode = Create_node();
	scanf_s("%d", &newNode->value);
	tail->next = newNode;
	tail = newNode;
	}
	tail->next = NULL;
	return t;
}

链表合并,并且使得新表按照升序排列

Sqlist* Merge(Sqlist* L1,Sqlist* L2)
{
	Sqlist* t1 = L1->next, * t2 = L2->next, * t3 = Create_node();
	Sqlist* new_Head = t3;
	while (t1 != NULL && t2 != NULL)
	{
	if (t1->value <= t2->value)
	{
	t3->next = t1;
	t3 = t1;
	t1 = t1->next;
	}
	else
	{
	t3->next = t2;
	t3 = t2;
	t2 = t2->next;
	}
	}
	if (t1) {
	t3->next = t1; t3 = t1;
	}
	else {
	t3->next = t2; t3 = t2;
	}
	free(L1); free(L2);
	return new_Head;
}
作者:Chano_sb原文地址:https://www.cnblogs.com/Chano/p/18396618

%s 个评论

要回复文章请先登录注册