当前位置：首页 > article >正文

《重生到现代之从零开始的数据结构生活》——单链表

article 2025/1/15 20:38:17

单链表

和顺序表不同，单链表是物理结构上非连续，非顺序的储存结构，但是在逻辑上是连续的。通过指针来实现

他的结构是怎么样的呢？为什么说它是物理结构上非连续呢

struct slist{
   int val;//储存的数值
   struct slist *next;//下一个结点的指针
};

那么结点是什么呢

和顺序表不一样，单链表里面的空间都是独立申请下来的，我们称这一个个独立的空间叫结点

所以就是说，单链表中有两个组成部分：单链表中储存的值，还有指向下一个结点的指针

所以大家应该知道为什么单链表是逻辑上是连续的，但是物理结构上不连续

头插

一个单链表会有怎么头插

头插就是在链表的头上插一个数据

但是单链表的数据在物理结构上不连续，那么我们怎么实现呢

我们写一个粗糙的模拟代码（没有考虑NULL）

#include<stdio.h>
#include<stdlib.h>
typedef struct list list;
struct list {
	int val;
	struct list* next;
}; //定义一个结构体

list* buymem(int x)
{
	list* a = (list*)malloc(sizeof(list));
	a->val = x;
	a->next = NULL;
	return a;

}//创建内存


void listprint(list* a)
{
	while (a->next)
	{
		printf("%d->", a->val);
		a = a->next;
	}

	printf("NULL\n");
}//打印单链表

list* headinsert(list** pphead,int x)//因为要更改实参，所以用双重指针
{ 
	list*b=buymem(x);
	b->next = *pphead;
	list* newhead = b;
	return newhead;


}//！！！！！！头插
int main() {

	list * list1 = (list*)malloc(sizeof(list));
	list * list2 = (list*)malloc(sizeof(list));
	list * list3 = (list*)malloc(sizeof(list));
	list * list4 = (list*)malloc(sizeof(list));

	list1->val = 1;
	list2->val = 2;
	list3->val = 3;
	list4->val = 4;

	list1->next = list2;
	list2->next = list3;
	list3->next = list4;
	list4->next = NULL;

	listprint(list1);
	list * head=headinsert(&list1,3);
	listprint(head);
	

	return 0;

思路就是创造一个新节点，让他的next指针指向原来的头节点，这样就能联系到一起啦

尾删

就是删除末尾的一个结点

我们要做的有：将倒数第二个结点的next指针指向NULL,然后将最后一个动态空间返还

所以我们来

void * lastdel(list ** pphead) {
	assert(pphead && *pphead);
	if ((*pphead)->next==NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	list* pcur = NULL;
	list* ptail = *pphead;
	while (ptail->next)
	{
		pcur = ptail;
		ptail = ptail->next;
	}
	free(ptail);
	
	ptail = pcur;
	ptail->next = NULL;
	
}//尾删