c/c++开发分享C语言深入讲解链表的使用

现实生活中的火车就像一个完整的链表,现在我们来深入理解一下链表这个数据结构。一、链表的概念概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的

现实生活中的火车就像一个完整的链表,现在我们来深入理解一下链表这个数据结构。

一、链表的概念

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

C语言深入讲解链表的使用

注:

1、从上图中可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续。

2、从现实中的结点一般是通过malloc函数申请的,所以其内存分配是在堆区。

3、从堆上申请的空间,是按照一定的策略来分配的,则一个节点的大小为8个字节。

二、链表的分类

实际中链表的结构非常多样,以下情况组合起来就有8种链表结构:

1. 单向或者双向链表

C语言深入讲解链表的使用

2. 带头或者不带头(是否有自带哨兵位头结点)

C语言深入讲解链表的使用

第二个链表的d1指向了我们的哨兵位头结点。

3. 循环或者非循环链表

C语言深入讲解链表的使用

4. 无头单向非循环链表和带头双向循环链表

C语言深入讲解链表的使用

1. 无头单向非循环链表:结构简单,一般不会单独用来存数据。实际中更多是作为其他数据结构的子结 构,如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

2. 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向 循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而 简单了。

3、链表的实现(代码和注释)

无头+单向+非循环链表增删查改实现

头文件:

#pragma once   #include<stdio.h>  #include<stdlib.h>  #include<assert.h>  //要求存储的数据从0开始,依次存储  //静态的顺序表  //问题:开小了,不够用,开大了,存在浪费。  //struct seqlist  //{  //	int a[n];  //	int size;//记录存储了多少个数据。  //};  typedef int sldatetype;//宏定义我们的 sldatetype是int类型的  //动态的顺序表  typedef struct seqlist  {  	sldatetype* a;  	int size;	//存储数据个数  	int capacity;//存储空间大小  }sl, seqlist;  void seqlistprint(seqlist* psl);//链表的打印  void seqlistinit(seqlist* psl);//链表的初始化  void seqlistdestroy(seqlist* psl);//链表的销毁  void seqlistcheckcapacity(seqlist* psl);//检查内存空间是否足够  //时间复杂度是o(1)  void seqlistpushback(seqlist* psl, sldatetype x);//链表的尾插  void seqlistpopback(seqlist* psl);//链表的尾删  //时间复杂度是o(n)  void seqlistpushfront(seqlist* psl, sldatetype x);//链表的头插  void seqlistpopfront(seqlist* psl);//链表的头删  void seqlistinsert(seqlist* psl, size_t pos, sldatetype x);  // 删除pos位置的数据  void seqlisterase(seqlist* psl, size_t pos);  // 顺序表查找  int seqlistfind(seqlist* psl, sldatetype x);

链表的函数实现部分的代码:

#include"seqlist.h"  #include<assert.h>  void seqlistprint(seqlist* psl)//结构体指针传参  {  	for (int i = 0; i < psl->size; ++i)  	{  		printf("%d ", psl->a[i]);  	}  	printf("n");  }  void seqlistinit(seqlist* psl)  {  	assert(psl);//断言psl不为空  	psl->a = null;//a就相当于是链表的头  	psl->size = 0;  	psl->capacity = 0;  }  void seqlistdestroy(seqlist* psl)//链表的删除  {  	assert(psl);  	free(psl->a);//free掉链表中a这个节点的位置  	psl->a = null;//将a指向空  	psl->capacity = psl->size = 0;//将链表的内存大小置为0  }  void seqlistcheckcapacity(seqlist* psl)//检查链表的内存,如果不够就增容。  {  	assert(psl);  	if (psl->size == psl->capacity)  	{  		//capacity == 0,所以要先特判一下capacity 的值  		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;//初始节点数为4,如果内存现在为0就扩大一倍  		sldatetype* tmp = realloc(psl->a, sizeof(sldatetype) * newcapacity);//申请空间  		if (tmp == null)  		{  			printf("realloc failn");  			exit(-1);  		}  		else  		{  			psl->a = tmp;  			psl->capacity = newcapacity;//原来的空间变为新空间  		}  	}  }  void seqlistpushback(seqlist* psl, sldatetype x)  {  	//如果满了,要扩容  	if (psl->size == psl->capacity)  	{  		//capacity == 0,所以要先特判一下capacity 的值  		size_t newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;  		sldatetype* tmp = realloc(psl->a, sizeof(sldatetype) * newcapacity);  		if (tmp == null)  		{  			printf("realloc failn");  			exit(-1);  		}  		else  		{  			psl->a = tmp;  			psl->capacity = newcapacity;  		}  	}  	psl->a[psl->size] = x;  	psl->size++;  }  void seqlistpopback(seqlist* psl)  {  	assert(psl);  	if (psl->size > 0)  	{   		psl->size--;//尾删就size--就好了  	}  }  void seqlistpushfront(seqlist* psl, sldatetype x)  {  	assert(psl);  	seqlistcheckcapacity(psl);  	int end = psl->size - 1;  	while (end >= 0)//所有的数据往后挪1位  	{  		psl->a[end + 1] = psl->a[end];  		--end;  	}  	psl->a[0] = x;//两种操作是等价的  	psl->size++;  	//seqlistinsert(psl, 0, x);在头部插入。  }  void seqlistpopfront(seqlist* psl)  {  	assert(psl);  	if (psl->size > 0)  	{  		int begin = 1;  		while (psl->size > begin)  		{  			psl->a[begin - 1] = psl->a[begin];  			++begin;  		}  		--psl->size;  	}  }  void seqlistinsert(seqlist* psl, size_t pos, sldatetype x)  {  	// 暴力检查  	assert(psl);  	// 温和检查  	if (pos > psl->size)  	{  		printf("pos 越界:%dn", pos);  		return;  		//exit(-1);  	}  	// 暴力检查  	//assert(pos <= psl->size);  	seqlistcheckcapacity(psl);  	//int end = psl->size - 1;  	//while (end >= (int)pos)  	//{  	//	psl->a[end + 1] = psl->a[end];  	//	--end;  	//}  	size_t end = psl->size;  	while (end > pos)  	{  		psl->a[end] = psl->a[end - 1];  		--end;  	}  	psl->a[pos] = x;  	psl->size++;  }

4、链表oj题(小试牛刀)

1、leetcode203移除链表元素力扣

C语言深入讲解链表的使用

C语言深入讲解链表的使用

包含三种情况

画个图分析:

思路:情况一和情况二都可以用prev和cur指针遍历数组的两个元素, if cur指针不等于6,prev指针和cur指针都往前走,如果cur = 6,prev跳到cur的下一个位置

如果是第三种情况,则需先找到head != val的位置,再重复进行如上操作。

代码示例:

struct listnode* removeelements(struct listnode* head, int val)  {      struct listnode* prev = null;      struct listnode* cur = head;      while(cur)      {          if(cur->val != val)//当cur这个位置的值不等于val时往下走          {              prev = cur;//prev跳到cur位置               cur = cur->next;//cur指针继续往下走          }          else          {              struct listnode* next = cur->next;//定义一个新的指针              if(prev == null)//头删,head为空的状态              {                  free(cur);                  head = next;//继续往后面走                  cur = next;              }              else              {                  free(cur);//free掉cur这个节点                  prev->next = next;//跳过了cur这个点                  cur = next;//cur继续往后走              }          }      }      return head;  }

2、leetcode206反转链表力扣

C语言深入讲解链表的使用

思路1:反转指针方向

思路二:用三个指针, n1, n2, n3 分别存放null, head, head->next;

C语言深入讲解链表的使用

代码示例:

struct listnode* reverselist(struct listnode* head)  {      if(head == null) return null;      struct listnode* n1, *n2, *n3;      n1 = null;      n2 = head;      n3 = n2->next;//n3的地址是n2的下一位      while(n2)      {          n2->next = n1;//n2 的下一位指向 n1;起到掉头的作用          n1 = n2;          n2 = n3;          if(n3)          n3 = n3->next;      }      return n1;  }

方法2:头插法

殊途同归。newhead 相当于之前的n1, cur = n2, next = n3;  struct listnode* reverselist(struct listnode* head)  {      struct listnode* newhead = null;      struct listnode* cur = head;      while(cur)      {          struct listnode* next = cur->next;          //头插          cur->next = newhead;//代表链表的指向方向。          newhead = cur;//接着把地址传过来(更新)          cur = next;//(更新)      }      return newhead;  }

3、leetcode 876链表的中间结点力扣

思路:快慢指针法

C语言深入讲解链表的使用

struct listnode* middlenode(struct listnode* head)  {      struct listnode* slow, * fast;      slow = fast = head;//刚开始slow和fast指针都指向头      while(fast && fast->next) //想的是结束的条件,写的是继续的条件      {          slow = slow->next;          fast = fast->next->next;//fast 每次走两步      }      return slow;  }

总结

这里我带大家从链表的概念,链表的分类,链表的简单实现以及3题oj题四个方面带大家认识链表

到此这篇关于c语言深入讲解链表的使用的文章就介绍到这了,更多相关c语言链表内容请搜索<猴子技术宅>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<猴子技术宅>!

需要了解更多c/c++开发分享C语言深入讲解链表的使用,都可以关注C/C++技术分享栏目—猴子技术宅(www.ssfiction.com)

本文来自网络收集,不代表猴子技术宅立场,如涉及侵权请点击右边联系管理员删除。

如若转载,请注明出处:https://www.ssfiction.com/c-cyuyankaifa/1240215.html

(0)
上一篇 4天前
下一篇 4天前

精彩推荐

发表回复

您的电子邮箱地址不会被公开。