数据结构--链表
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。相较于数组，链表有以下长处：
逻辑结构
（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 为库中的函数，用于动态分配内存，传入所需内存大小，返回值为范例为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<stdio.h>
#include<stdlib.h>
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;
}
</stdlib.h></stdio.h>
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]