顺序表与链表

这篇具有很好参考价值的文章主要介绍了顺序表与链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

思维导图:

顺序表与链表,数据结构初阶,链表,数据结构,c语言,学习

 

顺序表与链表都是两种线性表,但是两者之间又有着许多的不同。顺序表是一种连续的空间,实际上就是数组。链表是不连续的空间,链表的空间是一块一块的开辟出来的。

两者的优点与缺点

顺序表:

优点:1.顺序表的空间是连续的,所以能够支持下标的随机访问。

缺点:2.顺序表的空间是连续的容易造成空间的浪费。

链表:

优点:1.空间不连续,要用时才申请所以不会造成空间的浪费。

缺点:2.空间不连续不能支持下标的随机访问。

一,顺序表的操作

1.顺序表的结构

顺序表的本质是数组,所以要定义一个有数组的结构体。并且,这个顺序表是动态的。所以我们又需要一个表示顺序表内元素个数的变量size和一个表示顺序表容量的变量capacity。结构体定义如下:

 代码:

typedef  int dataType;
typedef struct List
{
	dataType* a;//数组
	int size;//个数
	int capacity;//容量
}List;

2.顺序表的初始化

 顺序表的初始化是一个必要的操作,数组指针先初始化为NULL,size初始化为0,capacity初始化为0.代码如下:

void ListInit(List* list)
{
	assert(list);//防止传入NULL
	list->a = NULL;
	list->size = 0;
	list->capacity = 0;
}

 3.顺序表的前插操作

顺序表的插入操作都要先判断顺序表内的空间是否够用,所以在插入数据到顺序表之前得先对顺序表的容量是否已满进行判断。先写一个判断容量的函数,代码如下:

代码:文章来源地址https://www.toymoban.com/news/detail-526295.html

void checkCapacity(List* list)
{
	assert(list);
	if (list->size == list->capacity)
	{
		int newcapacity = list->capacity==0 ? 4: 2 * list->capacity;
		dataType* tmp = (dataType*)realloc(list->a, sizeof(dataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail!");
			return;
		}
		list->a = tmp;
		list->capacity = newcapacity;
	}
	
}

 然后便是对顺序表的头插操作,头插操作插入的位置都是数组下标为0的位置。为了实现这一操作,我们就必须在数组不为空的条件下对数据进行后移然后将下标为0的位置腾出来。代码如下:

代码:

void LishPushFront(List* list, dataType x)
{
	assert(list);
	checkCapacity(list);//判断容量是否已满
	if (list->size == 0)//当数组为空时直接插入
	{
		list->a[0] = x;
	}
	else//数组不为空时要将原有数据后移将下标为0的位置腾出
	{
		int end = list->size - 1;
		for (int i = end;i >= 0;i--)
		{
			list->a[i + 1] = list->a[i];
		}
		list->a[0] = x;
	}
	list->size++;//插入后数组元素个数增加
	
}

4,顺序表的尾插操作

顺序表的尾插操作也是一个插入操作,所以尾插操作的第一步便是对数组的容量进行检查。然后才是数据的尾插操作。尾插不需要数据的移动,只需要在size的位置上插入数据即可。

代码如下:

代码:

void ListPushBack(List* list, dataType x)
{
	assert(list);
	checkCapacity(list);
	list->a[list->size] = x;
	list->size++;
}

5.顺序表的头删

顺序表的头删操作是一个移动数据覆盖然后将size减1的过程。说是删除数据其实就是覆盖掉数组下标为0的位置的数据。注意要对数组是否为空进行判断,当数组为空时不能够对这个顺序表进行删除!!代码如下:

代码:

void ListPopFront(List* list)
{
	assert(list);
	assert(list->size > 0);//对顺序表是否为空进行判断
	for (int i = 1;i < list->size;i++)
	{
		list->a[i - 1] = list->a[i];
	}
	list->size--;
}

 6.顺序表的尾删

顺序表的尾删操作比起顺序表的头删操作就显得更加简单。顺序表的尾删操作不需要覆盖只需要让数组的最后一个数据访问不到便可,也就是将size减1。注意要对数组是否为空进行判断,当数组为空时不能够对这个顺序表进行删除操作!!代码如下:

代码:

void ListPopBack(List* list)
 {
	 assert(list);
	 assert(list->size > 0);
	 list->size--;
 }

 7.顺序表的中间插入

顺序表的中间插入操作实现的功能就是将要插入的数据插入到要插入的下标pos位置处。中间插入的操作能够被头插1和尾插复用进而实现头插与尾插。中间插入操作代码如下:

代码:

void ListInsert(List* list, int pos, dataType x)
 {
	 assert(list);
	 assert(0 <= pos && pos <= list->size);//对pos的值进行判断以免造成越界
	 checkCapacity(list);
	 for (int i = list->size;i >= pos;i--)
	 {
		 list->a[i] = list->a[i - 1];
	 }
	 list->a[pos] = x;
	 list->size++;
 }

 8.顺序表的中间删除操作

顺序表的中间删除操作就是将下标为pos的位置上的数据删除的操作。也能被其他两个删除操作进行复用从而实现头删和尾删。和前两个操作一样中间删除的操作的删除就是覆盖下标pos位置上的1数据或者让pos数据上的数据不可访问。中间删除操作代码如下:

代码:

void ListErase(List* list, int pos)
 {
	 assert(list);
	 assert(list->size>0);
	 assert(0 <= pos && pos < list->size);
	 for (int i = pos;i < list->size-1;i++)
	 {
		 list->a[i] = list->a[i + 1];
	 }
	 list->size--;
 }

9.顺序表内数据的寻找

在顺序表内寻找某个数据其实并不难,不过就是遍历顺序表内的数组然后看看有没有匹配的数据。如果有便返回数据的下标,没有便返回不存在的下标-1。代码如下:

 代码:

int ListFind(List* list, dataType x)
 {
	 assert(list);
	 for (int i = 0;i < list->size;i++)
	 {
		 if (list->a[i] == x)
			 return i;
	 }
	 return -1;
 }

10,顺序表数据的修改

 顺序表内数据的修改这一操作是和上一个查找操作配合着使用的。只有要查找的元素存在才能替换。否则便不能。代码如下:

代码:

void ListModify(List* list,int i,dataType x)
 {
	 assert(list);
	 if (i == -1)//i这个值是通过ListFind函数找到的下标
	 {
		 printf("要修改的值不存在!\n");
		 return;
	 }
	 else
	 {
		 list->a[i] = x;
	 }

 }

11.顺序表的销毁

太简单了,直接上代码:

代码:

 void ListDestory(List* list)
 {
	 assert(list);
	 free(list->a);
	 list->a = NULL;
	 list->size = list->capacity = 0;
 }

二,链表的创建与操作

1.链表的创建

链表是一种不连续的空间,但是又要将一个一个的节点联系起来并且链表里还要放置一些数据。所以链表的结构里就要有两个变量,一个是存下一个链表节点的指针,一个是存当前节点内数据的变量。链表节点的结构代码如下:

代码:

typedef int  dataType;
typedef struct listNode
{
	dataType val;//存放当前节点内的数据
	struct listNode* next;//存放下一个节点的地址
}listNode;

 2.链表的头插操作

链表的头插操作在执行时要分两种情况。第一种情况是链表为NULL时,你需要让链表的头节点头节点指向newnode。当链表不为NULL时,newnode指向的next就是原来的头节点,然后让头节点指向新的头节点。代码如下:

代码:

void SlistPushFront(SListNode** pphead, dataType x)
{
	assert(pphead);
	assert(pphead);//防止传入空指针
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//当链表不为NULL时
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

 3.链表的尾插操作

链表的尾插操作其实与头插操作差不多。最主要的是当链表不是NULL时需要去找到尾节点,然后让尾节点的next指向newnode。代码如下:

代码:

void SlistPushBack(SListNode** pphead, dataType x)
{
	assert(pphead);//防止传入空指针
	SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
    //找尾插入值
	else
	{
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

以上两个代码能复用的地方:生成节点的地方

代码:

SListNode* BuyNode(dataType x)
{
	SListNode* node = (SListNode*)malloc(sizeof(SListNode));
	if (node == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	node->val = x;
	node->next = NULL;
	return node;
}

改进后的代码:

头插:

void SlistPushFront(SListNode** pphead, dataType x)
{
	assert(pphead);
	assert(pphead);//防止传入空指针
	SListNode* newnode = BuyNode(x);
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	//当链表不为NULL时
	else
	{
		newnode->next = *pphead;
		*pphead = newnode;
	}
}

尾插:

void SlistPushBack(SListNode** pphead, dataType x)
{
	assert(pphead);//防止传入空指针
	SListNode* newnode = BuyNode(x);
	if (newnode == NULL)
	{
		perror("malloc fail\n");
		return;
	}
	newnode->val = x;
	newnode->next = NULL;
	//当链表为NULL
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SListNode* tail = *pphead;
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}

四,链表的头删操作

链表的头删操作也是一个简单的操作,这个操作就是将头节点给销毁掉然后再让头指针指向第二个节点。这也要分两种情况来删除,第一种情况是链表为NULL不能删,第二种情况便是当链表内只有一个头节点时直接删除这个节点然后置空便可以了。第三种情况是当链表内有多个节点时需要将第二个节点的地址保存下来然后再将头节点删掉并置空。代码如下:

代码:

void SListPopFront(SListNode** pphead)
{
	assert(pphead);
	//当链表为空时不能够继续删除
	assert(*pphead);
	//只有一个节点时
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	//有两个节点时
	else
	{
		SListNode* next = (*pphead)->next;
		free(*pphead);
		*pphead = next;
	}

}

五,链表的尾删

链表的尾删操作就是一个将链表的尾节点删除的操作。这个操作也得分三种情况:

1.链表为NULL不删   2.链表内只有一个节点,直接删除第一个节点  3.链表内有多个节点,找到最后一个节点删除置空。代码如下:

 代码:

void SListPopBack(SListNode** pphead)
{
	assert(pphead);
	assert(*pphead);
	//只有一个节点
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SListNode* tail = *pphead;
		SListNode* prev = NULL;//记录尾节点的前一个节点
		while (tail->next)//找尾节点
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);//去尾
		tail = NULL;//将尾节点置空
		prev->next = NULL;//尾节点的前一个节点的next指向NULL,消除野指针问题
	}
}

六,链表的中间插入

链表的中间插入操作讲的是在链表的某个数据的位置处插入一个操作者想要插入的值。这个操作的关键点就在于找到要插入位置的前一个位置然后将这个位置的nex指向给改掉,改成指向我们想要插入的值。代码如下:

代码:

void SListInsert(SListNode** pphead,dataType target ,dataType x)
{
	assert(pphead);
	SListNode* cur = *pphead;//表示当前节点
	SListNode* prev = NULL;//表示当前节点的前一个节点
	while (cur)
	{
		SListNode* newnode = BuyNode(x);
		if (cur->val == target)
		{
			if (prev == NULL)//当第一个节点就是目标值所在节点时
			{
				newnode->next = *pphead;
				*pphead = newnode;
			}
			else//当其他节点才是目标值所在节点时
			{
				prev->next = newnode;
				newnode->next = cur;

			}
			return ;
	   }
		prev = cur;
		cur = cur->next;
	}
//当链表循环完以后链表内便没有数据为目标值的节点
	printf("链表内没有要找的目标值\n");
	return ;
}

七,链表的中间删除

链表的中间删除操作的作用是将目标值所在节点删除,释放掉。这个操作的代码和中间插入的代码有异曲同工之妙,都要找到要删除的节点的前一个节点然后再执行下列的操作。也有两种情况要讨论——1,当第一个节点为目标节点   2,当其它节点为目标节点。

void SListErase(SListNode** pphead, dataType target)
{
	assert(pphead);
	assert(*pphead);
	SListNode* cur = *pphead;
	SListNode* prev = NULL;
	while (cur)
	{
		SListNode* next = cur->next;
		if (cur->val == target)
		{
			if (prev == NULL)
			{
				free(cur);
				cur = next;
			}
			else
			{
				free(cur);
				prev->next = next;

			}
			return ;
		}
		prev = cur;
		cur = cur->next;

	}
	printf("链表内没有要删除的目标节点\n");
	return;
}

当然,中间删除与插入的代码的写法不止这一种,我们还可以通过寻找某个值所在的节点来对链表进行中间插入与删除。这里读者可以自己思考一下该如何写代码。 如果要写这样一个代码的话还需要写一个find函数来找到这个节点然后利用这个函数来与中间插入,中间删除函数配合着使用。

八,链表的销毁

 这个代码比较简单,但是一定要记得在删除掉当前节点的时候要记录一下之后的节点。代码如下:

代码:

void SListDestory(SListNode** pphead)
{
	SListNode* cur = *pphead;
	while (cur)//一个一个节点销毁
	{
		SListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;//最后将外面的list置空
}

到了这里,关于顺序表与链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构与算法分析】反转链表与顺序表(内含源码,思路清晰)

      顺序表和链表都是数据结构中常见的线性表。它们的主要区别在于 内存管理方式不同 。   顺序表(Array)是由一系列元素按照一定顺序依次排列而成,它使用连续的内存空间存储数据。顺序表使用一个数组来存储数据,数组中的每个元素都可以通过下标来访问。顺序

    2024年02月07日
    浏览(101)
  • 顺序表与链表

    思维导图:   顺序表与链表都是两种线性表,但是两者之间又有着许多的不同。顺序表是一种连续的空间,实际上就是数组。链表是不连续的空间,链表的空间是一块一块的开辟出来的。 两者的优点与缺点 : 顺序表: 优点: 1.顺序表的空间是连续的,所以能够支持下标的

    2024年02月12日
    浏览(55)
  • 顺序表与链表的区别

    目录 一、顺序表和链表的比较 顺序表 优点: 缺点: 链表 优点 缺点 二、顺序表和链表的区别 1.顺序表和链表都具有增、删、查、改功能,但算法复杂度却不相同。 2、从数据元素存储的内存角度来看 三、顺序表与链表选取方案 顺序表的特点是逻辑上相邻数据元素,物理存

    2024年02月08日
    浏览(105)
  • 【数据结构初阶】顺序表和链表(1)

    线性表(linear list) 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的,线性表在物理上

    2024年02月08日
    浏览(194)
  • 初阶数据结构之---顺序表和链表(C语言)

    线性表: 线性表(linear list)是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构。线性表在逻辑上是线性结构,也就是说是连续的一条直线。但在物理上并不一定是连续的。线性表在物理上存储时,通常以 数组 和 链式结构 的形式存储。

    2024年02月22日
    浏览(61)
  • 【数据结构和算法初阶(C语言)】复杂链表(随机指针,随机链表的复制)题目详解+链表顺序表结尾

    目录  1.随机链表的复制 1.2题目描述  1.3题目分析 1.4解题: 2.顺序表和链表对比 2.1cpu高速缓存利用率 3.结语 一个长度为  n  的链表,每个节点包含一个额外增加的随机指针  random   该指针可以指向链表中的任何节点或空节点。        构造这个链表的  深拷贝 。 深拷贝

    2024年03月10日
    浏览(81)
  • 数据结构—LinkedList与链表

    目录 一、链表 1. 链表的概念及结构 1. 单向或者双向 2. 带头或者不带头 3. 循环或者非循环 二.LinkedList的使用  1.LinkedList概念及结构 2. LinkedList的构造 3. LinkedList的方法 三. ArrayList和LinkedList的区别           链表是一种 物理存储结构上非连续 存储结构,数据元素的 逻辑

    2024年02月04日
    浏览(49)
  • 【数据结构】LinkedList与链表

    上节课已经熟悉了ArrayList的使用,并且进行了简单模拟实现。通过源码知道,ArrayList底层使用数组来存储元素: 由于其底层是一段连续空间,当 在ArrayList任意位置插入或者删除元素时,就需要将后序元素整体往前或者往后搬移,时间复杂度为O(n),效率比较低 ,因此A rrayLi

    2024年02月07日
    浏览(44)
  • 【数据结构】顺序表与ArrayList

    作者主页: paper jie 的博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏

    2024年02月08日
    浏览(41)
  • 【数据结构(二)】顺序表与ArrayList

    ❣博主主页: 33的博客❣ ▶文章专栏分类:数据结构◀ 🚚我的代码仓库: 33的代码仓库🚚 🫵🫵🫵 关注我带你学更多数据结构知识 在计算机科学中,数据结构是处理和组织数据的方法和技术。顺序表是一种常见的线性表数据结构,它基于数组实现,提供了快速的随机访问能力

    2024年04月12日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包