php商城网站的要求与数据,全国工商企业查询平台,制作公司网页软件,网站卡密怎么做已经两天没有更新了#xff0c;今天就写一篇数据结构的链表吧#xff0c;巩固自己也传授知识#xff0c;不知道各位是否感兴趣看看这一篇有关联表的文章。
目录
链表的概念与结构 单向链表的实现
链表各个功能函数 首先我在一周前发布了一篇有关顺序表的文章#xff0c;…已经两天没有更新了今天就写一篇数据结构的链表吧巩固自己也传授知识不知道各位是否感兴趣看看这一篇有关联表的文章。
目录
链表的概念与结构 单向链表的实现
链表各个功能函数 首先我在一周前发布了一篇有关顺序表的文章其中我们通过简单的介绍和代码实践已经基本了解顺序表了那么即使我们把顺序表弄成动态的顺序表但其实我们运用顺序表还是有以下问题
1. 如果空间不够我们进行增容。但增容回付出一定的性能消耗其次可能存在一定的空间浪费因为我们每次增容都是2倍的增容我们可能并用不完这两倍的空间。
2.头部和中部左右两部分的插入效率太低因为我饿们需要将数据一个一个的往后移所以效率不高。 那么我们要怎么解决这个问题呢
1.空间上 按照需求给空间比如我要101个空间就给我101个空间而不是两倍。
2.不要求物理空间上的连续这样在头部和中部时我们就不需要挪动数据那么这种解决方法就是用链表实现。 OK我们下面就展开展开链表的知识了。 链表的概念与结构
链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表 中的指针链接次序实现的 。
其逻辑结构这里说的逻辑结构是我们想象出来便于理解的结构 上方逻辑结构可以是n个数据和指针这样我们就完成了非物理空间上的连续的表。
链表有许多结构我们今天就讲一种简单的结构——————单向链表。 单向链表的实现
我们继续创建一个结构体里面是数据和指针。
typedef int SLTDataType;
struct SListNode
{SLTDataType data;struct SListNode* next;
};
typedef struct SListNode SLTNode;代码中将结构体命名为SLTNode是为了方便写代码。
typedef int SLTDataType 为了易于改变数据类型时只需将int 改成其他类型即可改变 整个链表的数据类型。
struct SListNode* next 这里面储存一个结构体指针用来链接下一个结构体。 既然结构体已经完成了那么我们现在就简单用函数链接一个链表了。 链表各个功能函数 链表必须要找一个头即链表的首个结构体那么我们就将这个头命名为 plist传给其他函数完成其功能。
现在我们就实现第一个函数开辟空间的函数。
SLTNode* BuySListNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;return newnode;
}
这个函数主要用于链表的增加在各个部位进行插入数据都需要这个函数开辟空间。 头插函数
如何头插呢这是我们需要思考的。
void SListPushFront(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);newnode-next *pphead;*pphead newnode;
}
链表头插即开辟一块新的空间将这块空间作为头*pphead newnode;而这块空间的next则储存着原来的头结构体newnode-next *pphead; 。
注意这里要改变pist本身则我们就要使用指针进行传址改变其地址。 头删函数
这个函数也相较简单我们也是将第一个节点删除然后将第二个节点设为头节点而第二个节点就是原来头节点里储存的 next了我们必须先储存第二节点的地址然后再进行销毁。
void SListPopFront(SLTNode** pphead)
{SLTNode* next (*pphead)-next;free(*pphead);*pphead next;
} 尾插函数
尾插函数我们只需先创建一个新空间newnode然后将原来的尾的结构体中的 next 改为现在newnode 即可。但需要注意当链表还一个节点都没有的时候原来是没有尾的这又是一种情况我们只需将*pphead变为newnode即可。由此得出下面代码。
void SListPushBack(SLTNode** pphead, SLTDataType x)
{SLTNode* newnode BuySListNode(x);if (*pphead NULL){*pphead newnode;}else{// 找尾节点的指针SLTNode* tail *pphead;while (tail-next ! NULL){tail tail-next;}// 尾节点链接新节点tail-next newnode;}
} 尾删函数
尾删时我们需要考虑三种情况 1、空 2、一个节点 3、一个以上的节点
空的时候我们不需要任何操作直接return即可。
一个节点时我们需要用free函数进行销毁空间然后将该*phead 赋一个NULL。
一个节点i以上我们要考虑的又有些不同因为当我们将尾节点删除时我们还需将倒数第二个节点赋为NULL不然程序可能会崩掉。我们知道找最后一个尾节点很容易但是我们要找倒数第二个节点很难 这里我们就需要借助第三指针变量一前一慢进行往后遍历最后即可得到这两个节点了。
void SListPopBack(SLTNode** pphead)
{// 1、空// 2、一个节点// 3、一个以上的节点if (*pphead NULL){return;}else if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{SLTNode* prev NULL;SLTNode* tail *pphead;while (tail-next ! NULL){prev tail;tail tail-next;}free(tail);prev-next NULL;}
}打印函数
以NULL为链表结束标志即打印结束。
void SListPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL){printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}下面给大家展示一下这些函数 void Test()
{SLTNode* plist NULL;SListPushFront(plist, 8);SListPushFront(plist, 88);SListPushBack(plist, 29);// 88 8 29SListPrint(plist);SListPopBack(plist);SListPushFront(plist, 5);SListPushBack(plist, 89);// 5 88 8 89SListPrint(plist);SListPopFront(plist);SListPrint(plist);//88 8 89}int main()
{Test();return 0;
} 文章到这就结束了。
