链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
相较于数组,链表有以下优点:
逻辑结构
(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 为库
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 '9')c = getchar();
while (c >= '0' && c
(UPD)
看了一眼链表合并,发现如果不在头指针中保存value会好处理一些
重构了一部分代码
初始化
Sqlist* Init(int n)
{
Sqlist* t = Create_node(),*tail=t;
for (int i = 1; i 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 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;
}
1.本站内容仅供参考,不作为任何法律依据。用户在使用本站内容时,应自行判断其真实性、准确性和完整性,并承担相应风险。
2.本站部分内容来源于互联网,仅用于交流学习研究知识,若侵犯了您的合法权益,请及时邮件或站内私信与本站联系,我们将尽快予以处理。
3.本文采用知识共享 署名4.0国际许可协议 [BY-NC-SA] 进行授权
4.根据《计算机软件保护条例》第十七条规定“为了学习和研究软件内含的设计思想和原理,通过安装、显示、传输或者存储软件等方式使用软件的,可以不经软件著作权人许可,不向其支付报酬。”您需知晓本站所有内容资源均来源于网络,仅供用户交流学习与研究使用,版权归属原版权方所有,版权争议与本站无关,用户本人下载后不能用作商业或非法用途,需在24个小时之内从您的电脑中彻底删除上述内容,否则后果均由用户承担责任;如果您访问和下载此文件,表示您同意只将此文件用于参考、学习而非其他用途,否则一切后果请您自行承担,如果您喜欢该程序,请支持正版软件,购买注册,得到更好的正版服务。
5.本站是非经营性个人站点,所有软件信息均来自网络,所有资源仅供学习参考研究目的,并不贩卖软件,不存在任何商业目的及用途
暂无评论内容