中天建设集团山西分公司网站,郑州做公司网站,在税局网站上如何做进项税转出,门户网站的推广目录 顺序表的问题及思考链表链表的概念及结构链表的分类单链表的实现链表功能实现遍历链表void SLTprint(SLNode* phead)代码 创造新节点SLNode* CreateNode(SLNDataType x)代码 顺序表的问题及思考
中间/头部的插入删除#xff0c;时间复杂度为O(N),效率低,但是尾部插入效率… 目录 顺序表的问题及思考链表链表的概念及结构链表的分类单链表的实现链表功能实现遍历链表void SLTprint(SLNode* phead)代码 创造新节点SLNode* CreateNode(SLNDataType x)代码 顺序表的问题及思考
中间/头部的插入删除时间复杂度为O(N),效率低,但是尾部插入效率可以
增容需要申请新空间拷贝数据释放旧空间,且增容一般是呈2倍的增长会有一定的空间浪费。例如当前容量为100满了以后增容到200我们再继续插入了5个数据后面没有数据插入了那么就浪费了95个数据空间。
链表
链表的概念及结构
概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 由于链表不像顺序表一样要求连续所以我们需要一种方式来管理这些数据(因为空间不一定是连续,如果不管理的话可能就找不到数据)
这种方式就是我们需要找到最开始的一块空间,然后那块空间会告诉你下一块空间的地址在哪,只有这样你才能够找到链表中的所有数据
而满足这种方式只有是通过结构体实现结构中包含了我们想要的数据以及下一块空间的地址
当我们所有的数据都查找完后我们需要有人提醒我们已经找到尽头了所以在查找完最后一块空间时那块空间记录的下一块空间地址为空指针也就是告诉你不需要再往后查找
链表的分类
实际中链表的结构非常多样以下情况组合起来就有8种链表结构 单向或者双向 带头或者不带头 循环或者非循环
虽然有这么多的链表的结构但是我们实际中最常用还是两种结构
无头单向非循环链表结构简单一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
带头双向循环链表结构最复杂一般用在单独存储数据。实际中使用的链表数据结构都是带头双向循环链表。另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了
单链表的实现
typedef int SLNDataType;
typedef struct SListNode
{SLNDataType val;struct SListNode *next;
}SLNode;这段代码是一个结构体里装这一个数据val和一个结构体指针next(next就是为了告诉你下一块空间的地址而存在的)
很多人可能有疑惑认为结构体还没有实现完为什么里面就可以包含一个结构体的指针
其实结构体的指针也是指针结构体只要定义了知道结构体的名称就可以实现内部包含一个结构体指针
如果我们把struct SListNode* next的*去掉就会报错 此外这里有一个问题,如何计算上面链表中一个节点所占用内存的空间,这就涉及到结构占用内存的计算,在我之前的文章中有讲过
链表功能实现
遍历链表void SLTprint(SLNode* phead) phead为第一块空间的地址cur是为了避免在使用链表时phead会被使用者改变,导致我们找不到第一块空间地址的指针
代码
void SLTprint(SLNode* phead)
{SLNode* cur phead;while (cur ! NULL){printf(%d- , cur-val);cur cur-next;}printf(NULL\n);
}curcur-next是让cur去遍历链表,也就是cur指向cur的下一块节点的地址
当cur指向空时就意味着cur已经遍历完整个链表,所以直接跳出循环 创造新节点SLNode* CreateNode(SLNDataType x)
因为对于链表创建节点是非常常见的一种操作,所以我们单独拿出来写成一个函数
代码
SLNode* CreateNode(SLNDataType x)
{SLNode* newnode (SLNode*)malloc(sizeof(SLNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-next NULL;return newnode;
}
