首页 > 其他分享 >顺序表和链表知识点

顺序表和链表知识点

时间：2024-08-30 16:22:05浏览次数：10  
标签：知识点 顺序 ListNode void pos next 链表 phead SListNode

1 顺序表

顺序表是指用一段物理地址连续的空间去存储数据的线性结构。

顺序表有两种：静态顺序表，动态顺序表。

1.1 静态顺序表结构体定义

typedef int ElemDataSL;

typedef struct SequeList {
	ElemDataSL arr[100];
	int size;
}SL;

静态顺序表在创建结构体的时候就已经把容量固定，后期空间不够，不允许增加新空间，所以并不方便实际使用。

例子：通讯录（C语言实现）-CSDN博客

1.2 动态顺序表结构体定义

typedef int ElemDataSL;

typedef struct SequeList {
	ElemDataSL* arr;
	int size;
	int capatity;
}SL;

 动态顺序表在创建结构体的时候定义了arr的指针作为一段连续内存空间的首地址，如果有需要可以用realloc开辟新空间进行扩容处理。

1.2.1 接口声明

//初始化
void InitSequeList(SL* s);
//尾插
void SequeListPushBack(SL* s,ElemDataSL num);
//尾删
void SequeListPopBack(SL* s);
//头插
void SequeListPushFront(SL* s, ElemDataSL num);
//头删
void SequeListPopFront(SL* s);
//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos);
//pos处删
void SequeListPopInsert(SL* s,int pos);
//显示
void SequeListShowData(SL* s);
// 顺序表删除pos位置的值
void SequeListErase(SL*s, size_t pos);
// 顺序表销毁
void SequeListDestory(SL* s);

1.2.2 初始化

//初始化
void InitSequeList(SL* s) {
	assert(s);
	s->arr = (ElemDataSL*)malloc(DefaultData * sizeof(ElemDataSL));
	s->capatity = DefaultData;
	s->size = 0;
}

1.2.3 尾插

//尾插
void SequeListPushBack(SL* s,ElemDataSL num) {
	assert(s);
	AddCapatity(s);
	s->arr[s->size] = num;
	s->size++;
}

 1.2.4 尾删

//尾删
void SequeListPopBack(SL* s)
{
    assert(s);
	s->size--;
}

1.2.5 头插

//头插
void SequeListPushFront(SL* s,ElemDataSL num) {
	AddCapatity(s);
	for (int i = s->size-1; i >=0; i--)
	{
		s->arr[i + 1] = s->arr[i];
	}
	s->arr[0] = num;
	s->size++;
}

1.2.6 头删

//头删
void SequeListPopFront(SL* s)
{
	for (int i = 0; i <= s->size - 1; i++)
	{
		s->arr[i] = s->arr[i + 1];
	}
	s->size--;
}

1.2.7 中间插入

//pos处插
void SequeListPushInsert(SL* s,ElemDataSL num,int pos)
{
	AddCapatity(s);
	for (int i = s->size - 1; i >= pos-1; i--)
	{
		s->arr[i + 1] = s->arr[i];
	}
	s->arr[pos-1] = num;
	s->size++;
}

1.2.8 中间删除

//pos处删
void SequeListPopInsert(SL* s, int pos) {
	for (int i = pos-1; i <= s->size - 1; i++)
	{
		s->arr[i] = s->arr[i + 1];
	}
	s->size--;
}

1.2.9 打印顺序表

//显示
void SequeListShowData(SL* s)
{
	assert(s);
	for (int i = 0; i < s->size; i++)
	{
		printf("%d ", s->arr[i]);
	}
	printf("\n");
}

1.3 顺序表销毁

// 顺序表销毁
void SequeListDestory(SL* s) {
	free(s->arr);
	s->arr = NULL;
}

顺序表优点：可以利用随机访问。

缺点：开辟空间可能会导致空间浪费，增删改查的时间复杂度为O（N）。

2 链表

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

注意：

1、链式结构在逻辑上是连续的，但在物理上非连续。

2、在堆上开辟空间。

3、在堆上申请空间，按照一定策略进行的，两次开辟的空间可能连续也可能不连续。

2.1 单链表

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。

2.2 接口声明

typedef int SLDATATYPE;
typedef struct SListNode {
	int data;
	struct SListNode* next;
}SListNode;
//尾插
void SListPushBack(SListNode** pphead, SLDATATYPE num);
//尾删
void SListPopBack(SListNode* phead);
//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num);
//头删
void SListPopFront(SListNode* phead);
//查找
SListNode* SListFind(SListNode* phead, SLDATATYPE num);
//中间后插
void SListInsertAfter(SListNode* pos, SLDATATYPE num);
//中间删
void SListEraseAfter(SListNode* pos);
//打印
void SListPrint(SListNode* phead);
//销毁链表
void SListDistory(SListNode** phead);

2.3 尾插

//尾插
void SListPushBack(SListNode* *pphead, SLDATATYPE num) {

	
	SListNode* NewNode = BuySListNode(num);
	if (*pphead == NULL)
	{
		*pphead= NewNode;
	}
	else
	{	SListNode* tail = *pphead;
		while (tail->next!=NULL)
		{
			tail = tail->next;
		}
		tail->next= NewNode;
	}
}

2.4 尾删

//尾删
void SListPopBack(SListNode** phead)
{
	SListNode* tail = *phead;
	SListNode* prev = tail;
	if (*phead == NULL)
	{
		return;
	}
	else if ((*phead)->next == NULL)
	{
		free(*phead);
		*phead = NULL;
	}
	else
	{
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	}
	

}

2.5 头插

//头插
void SListPushFront(SListNode** pphead, SLDATATYPE num)
{
	SListNode* newNode = BuySListNode(num);

	if ((*pphead) == NULL)
	{
		*pphead = newNode;
	}
	else
	{
		newNode->next = *pphead;
	}
	*pphead = newNode;
}

2.6 头删

//头删
void SListPopFront(SListNode* *pphead)
{	
	SListNode* head = *pphead;
	if (head == NULL)
	{
		return;
	}
	else if (head->next == NULL)
	{
		*pphead = NULL;
	}
	else
	{

		(*pphead) = (*pphead)->next;
		free(head);
	}
	
	
}

2.7 查找

SListNode* SListFind(SListNode* phead, SLDATATYPE num) {
	SListNode* ptr = phead;
	while (ptr)
	{
		if (ptr->data == num)
		{
			printf("%d找到了!\n",ptr->data);
			return  ptr;
		}
		ptr = ptr->next;
	}
	printf("%d没找到!\n",num);
	return NULL;
}

2.8 中间后插

void SListInsertAfter(SListNode* *pos, SLDATATYPE num)
{
	SListNode* newNode = BuySListNode(num);
	newNode->next = (*pos)->next;
	(*pos)->next = newNode;
}

2.9 中间后删

void SListEraseAfter(SListNode* pos)
{
	assert(pos);
	assert(pos->next);
	SListNode* next = pos->next;
	pos->next = next->next;
	free(next);
}

3 打印

//打印
void SListPrint(SListNode* phead)
{
	SListNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

3.1 销毁链表

void SListDistory(SListNode** phead)
{
	assert(*phead);
	SListNode* next = (*phead)->next;
	while (next)
	{
		free(*phead);
		*phead = next;
		next = next->next;
	}
	free(*phead);
	*phead = NULL;
}

单链表优点：需要增加多少个元素就开辟多少空间不会导致空间浪费，插入时间复杂度低。

缺点：不能随机访问，只能依次往后访问，无法实现从后往前。

2.2 双链表

头节点不存储有效数据。

2.2.1 接口声明

typedef int ListData;
typedef struct ListNode
{
	ListData data;
	struct ListNode* next;
	struct ListNode* prev;
}ListNode;
//链表创建
ListNode* ListCreate();
//尾插
void ListPushBack(ListNode* phead, ListData x);
//尾删
void ListPopBack(ListNode* phead);
//头插
void ListPushFront(ListNode* phead, ListData x);
//头删
void ListPopFront(ListNode* phead);
//查找
ListNode* ListFind(ListNode* phead, ListData x);
//中间插
void ListInsert(ListNode* pos,ListData x);
//中间删
void ListErase(ListNode* pos);
//显示
void ListPrint(ListNode* phead);
//清空链表
void ListClear(ListNode** phead);
//销毁链表
void ListDestory(ListNode* phead);

2.2.2 创建新节点 


ListNode* BuyListNode(ListData x)
{
	ListNode* node = (ListNode*)malloc(sizeof(ListNode));
	node->data = x;
	node->next = NULL;
	node->prev = NULL;
	return node;
}

2.2.3 双链表创建

ListNode* ListCreate() {
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

2.2.4 尾插 

//尾插
void ListPushBack(ListNode* phead, ListData x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newNode = BuyListNode(x);
	tail->next = newNode;
	newNode->prev = tail;
	newNode->next = phead;
	phead->prev = newNode;
}

 2.2.5 尾删

//尾删
void ListPopBack(ListNode* phead)
{
	assert(phead->next != phead);
	/*ListNode* tail = phead->prev;
	ListNode* tailPrev = tail->prev;
	tailPrev->next = phead;
	phead->prev = tailPrev;*/
	ListErase(phead->prev);
}

2.2.6 头插

//头插
void ListPushFront(ListNode* phead, ListData x)
{
	ListNode* newNode = BuyListNode(x);
	ListNode* pheadNext = phead->next;
	phead->next = newNode;
	newNode->prev = phead;
	newNode->next = pheadNext;
	pheadNext->prev = newNode;
}

2.2.7 头删 

//头删
void ListPopFront(ListNode* phead)
{
	ListNode* pheadNext = phead->next;
	phead->next = pheadNext->next;
	pheadNext->next->prev = phead;
	free(pheadNext);
}

2.2.8 查找

//查找
ListNode* ListFind(ListNode* phead, ListData x)
{
	ListNode* pos = NULL;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			pos = cur;
			break;
			
		}
		cur = cur->next;
	}
	return pos;
}

2.2.9 中间插

//中间插
void ListInsert(ListNode* pos, ListData x)
{
	assert(pos);
	/*ListNode* newNode = BuyListNode(x);
	ListNode* posPrev = pos->prev;
	newNode->next = pos;
	pos->prev = newNode;
	posPrev->next = newNode;
	newNode->prev = posPrev;*/
	ListPushFront(pos->prev, x);
}

2.3 中间删

//中间删
void ListErase(ListNode* pos)
{
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;
	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

2.3.1 显示

//显示
void ListPrint(ListNode* phead)
{
	assert(phead);
	ListNode* tail = phead->next;
	
	while (tail != phead)
	{
		printf("%d ", tail->data);
		tail = tail->next;
	}
	
	printf("\n");
}

2.3.2 清空链表

void ListClear(ListNode** phead)
{
	ListNode* cur = (*phead)->next;
	while (cur != *phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	(*phead)->next = *phead;
	(*phead)->prev = *phead;
}

2.3.3 销毁链表

//销毁链表
void ListDestory(ListNode** phead)
{
	ListClear(phead);
	free(*phead);
}

双链表优点：插入时间复杂度比单链表更低，可以前驱访问。

缺点：不能随机访问。

 3 顺序表和链表的区别

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续，物理上不一定连续
随机访问支持O（1）不支持O（N）
任意位置插入或者删除元素可能需要搬移元素，效率低O（N）只需修改指针指向
插入动态顺序表，空间不够时需要扩容没有容量概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存利用率高低

标签：知识点,顺序,ListNode,void,pos,next,链表,phead,SListNode
From： https://blog.csdn.net/m0_63703622/article/details/141676097

相关文章

  • Oracle物化视图的干货知识点
    物化视图1.简介  Oracle的物化视图是包括一个查询结果的数据库对像，它是远程数据的的本地副本，或者用来生成基于数据表求和的汇总表。物化视图存储基于远程表的数据，即快照。视图中数据不存在；物化视图数据实际存在2.创建物化视图选型2.1刷新的2种模式：  ONDEMAND仅在该物......
  • 数据结构线性表（1）顺序表
    ......
  • 分享丨【题单】链表、二叉树与一般树（前后指针/快慢指针/DFS/BFS/直径/LCA）
    作者：灵茶山艾府链接：https://leetcode.cn/circle/discuss/K0n2gO/一、链表注：由于周赛中的链表题可以转成数组处理，难度比直接处理链表低，故不标明难度分。带着问题去做下面的题目：在什么情况下，要用到哨兵节点（dummynode）？在什么情况下，循环条件要写while(node!=null)？什么情况......
  • 代码随想录算法day3 - 链表1
    题目1203.移除链表元素给你一个链表的头节点head和一个整数val，请你删除链表中所有满足Node.val==val的节点，并返回新的头节点。示例1：输入：head=[1,2,6,3,4,5,6],val=6输出：[1,2,3,4,5]示例2：输入：head=[],val=1输出：[]示例3：输入：head=[7,7,7,7],v......
  • 数据结构-单链表-详解-1
    数据结构-单链表-详解-11.前言2.结点3.打印3.1关于断言3.2下一结点的找法物理结构逻辑结构1.前言在数据结构-顺序表-详解中，我详细介绍了顺序表的实现，而顺序表也有一些缺点：中间，头部插入时，需整体挪动数据，效率低下。空间不够时扩容，有一定的消耗，也可能有一定空间浪费......
  • 数据结构：双向链表
    目录结构体创建链表插入链表头插法尾插法 遍历打印删除更新查找销毁结构体typedefintDataType;typedefstructnode{structnode*pPre;DataTypedata;structnode*pNext;}LinkNode;创建链表LinkNode*CreateDouList(){LinkNode......
  • 顺序表
    线性表线性表的初始化StatusInitList(SqList&L){L.elem=(ElemType*)malloc(sizeof(ElemType)*MAXSIZE);if(!L.elem)exit(OVERFLOW);L.length=0;returnOK;}线性表的销毁voidDestoryList(SqList&L){if(L.elem)fr......
  • 顺序控制和状态机之间的差别
    1.背景在PLC一直以来的工程经验里面。如果想要做一个顺序控制（业务逻辑）：用Graph实现用Csae..Of分支跳转语句用int数的变化切换不同的执行语句下面一种一种的来看，先看看使用int数切换实现一个顺序控制的案例：在这个案例里面，程序扫描currrent_step的值的不同，从而选择执......
  • CSP-S初赛知识点汇总
    CSP-S初赛知识点汇总进制转换二进制整数部分略。小数部分将小数点后部分整体*2，取其整数部分的结果即为对应二进制数字。之后，取计算后的数字小数部分继续计算直到其全为0为止。举一个例子：将33.25转化为二进制数整数部分：33/2=16......116/2=8......08/2=4......0......
  • 力扣: 环形链表
    文章目录需求MapSet快慢指针结尾需求给你一个链表的头节点head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从0开始）。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99