凡科建站网站怎样做软件下载,赣榆区住房和城乡建设局网站,北海市建设局官方网站,贵州易广建设集团网站一.链表的概念以及结构
链表是一种物理结构上不连续#xff0c;逻辑结构上连续的存储结构#xff0c;数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的结构与火车是类似的#xff0c;一节一节的#xff0c;数据就像乘客一样在车厢中一样。
与顺序表不同的…一.链表的概念以及结构
链表是一种物理结构上不连续逻辑结构上连续的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表的结构与火车是类似的一节一节的数据就像乘客一样在车厢中一样。
与顺序表不同的是链表里的每节车厢都是独立申请的空间我们将这样的空间称为节点或者结点 既然链表是一节一节的结点构成的那么这样的结点是怎么连接的呢
链表中的节点一般是通过结构体来实现的结构体中的存储着数据和下一个节点的地址这样我们就可以访问下一个节点中的数据了。
节点
typedef struct SListNode
{SLTDataType val;struct SListNode* next;
}SLTNode;为了使用方便我们可以对其重命名。
二.单链表的实现
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data; //节点数据struct SListNode* next; //指针保存下⼀个节点的地址
}SLTNode;
void SLTPrint(SLTNode* phead);
//头部插⼊删除/尾部插⼊删除
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDesTroy(SLTNode** pphead);
首先我们来思考如何打印数据呢
void SLTPrint(SLTNode* phead);
这个参数是指向第一个头节点的指针为什么要使用指针呢
通过指针我们可以访问这个结构体中的元素如果我们不使用指针形参是实参的一份临时拷贝如果数据过大这样会很浪费空间我们这里存储的数据是整形为了泛用性我们还是要使用一级指针直接使用会降低程序性能。
phead-data就可以访问到数据了那么下一个节点的数据呢
这时候就会用到我们在结构体中存储的指针了这个指针指向下一个结构体所以再通过下一个结构体我们就可以访问下一个结构体的数据同理下下个结构体的指针同理。
void SLTPrint(SLTNode* phead) {SLTNode* pcur phead;while (pcur) {printf(%d-,pcur-data);pcur pcur-next;}printf(NULL\n);
};
通常习惯上我们是不会改变直接传过来的参数的所以我们要使用的话就再使用一个变量来进行接收。
这里pcur不为NULL时代表我们的指针并没有走到结构体的末尾我们就可以以它作为限制条件每经过一个节点就打印一次数据直到遇到空指针停止。
然后就是要完成指定位置之前插入数据了。
假设有一个链表1-2-3-5-NULL.
我们要在数据5的前面插入4.可是在插入之前我们要找到数据五的位置才能插入。
如何查找元素呢
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);
第一个参数是指向第一个节点的指针第二个是要寻找的数据虽然这里可能会存在相同的数字但是这只是我们练习的场景假设我们要存储人的身份信息这是不可能存在相同的人的所以我们这里假设数据不相同。
最后返回这个节点的地址。
SLTNode* SLTFind(SLTNode* phead, SLTDataType x) {assert(phead);SLTNode* pcur phead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
};
和打印数据相同。我们只需要遍历整个数组即可如果找到就返回这个节点的地址否则就返回空。
接着我们再来完成指定位置插入数据。
即使我们找打这个节点的地址我们要在它之前插入数据也就是再创建一个节点然后把这个节点的next指针指向找的节点这样我们就在指定节点前面插入了数据。
但是我们新建的这个节点是没有被节点指向的所以我们还要让前一个节点指向新的节点。
这个SLTBuyNode是创建新节点函数我们在插入数据时会频繁用到这个代码如果重复的写就太浪费时间了所以我们单独封装一个函数来完成这个功能。
SLTNode* SLTBuyNode(SLTDataType x) {SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL) {perror(malloc);exit(1);}newnode-data x;newnode-next NULL;return newnode;
} SLTNode* pcur *pphead;while (pcur-next ! pos) {pcur pcur-next;}pcur-next SLTBuyNode(x);pcur-next-next pos;
可是这样写就完了吗
如果我们要在链表的第一个节点之前插入数据我们会发现这个代码循环是根本没有进入的并且会访问NULL地址这是非法的。
所以为了防止这样的问题我们还需要额外区分头插的情况。
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x) {assert(pphead);assert(*pphead);if (*pphead pos) {*pphead SLTBuyNode(x);(*pphead)-next pos;}else {SLTNode* pcur *pphead;while (pcur-next ! pos) {pcur pcur-next;}pcur-next SLTBuyNode(x);pcur-next-next pos;}
}; 然后我们来思考为什么这里要使用二级指针我们使用指针的目的是为了在函数中改变指针所指向的变量的值这里就是传值和传址的区别了我们在头插的过程中指向头节点的指针是会改变的如果我们传一级指针是改变不了这个指针的所以我们要使用二级指针。
然后就是删除数据函数
void SLTErase(SLTNode** pphead, SLTNode* pos);
这里与插入函数一样是需要考虑头删的。
void SLTErase(SLTNode** pphead, SLTNode* pos) {assert(pphead);assert(*pphead);SLTNode* pcur *pphead;if (pos *pphead) {*pphead pos-next;free(pos);}else {while (pcur-next ! pos) {pcur pcur-next;}pcur-next pos-next;free(pos);pos NULL;}
};
删除指定节点只需要我们将前一个节点指向下一个节点就行了然后再释放指定节点即可 。
而头删就是释放头节点然后将头指针指向头节点的下一个节点既可以。
为了方便头插头删位插尾删我们都使用前面两个函数来进行完成这样更加方便。
void SLTPushBack(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead NULL) {*pphead SLTBuyNode(x);}else {SLTInsert(pphead,NULL,x);}
}
在尾插时如果链表为空我们就直接创建一个新的节点即可否则我们就只需要在NULL前面插入一个节点即可因为最后一个节点的next指针指向的是空。
void SLTPushFront(SLTNode** pphead, SLTDataType x) {assert(pphead);if (*pphead NULL) {*pphead SLTBuyNode(x);}else {SLTInsert(pphead, *pphead, x);}
};
头插同理如果链表为空直接创建新的链表即可否则就是在头节点之前插入即可而且头节点直接作为参数给我们使用了所以我们就不需要再查找了.
void SLTPopBack(SLTNode** pphead) {assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur-next ! NULL) {pcur pcur-next;}SLTErase(pphead,pcur);
};
尾删就需要我们遍历链表找到最后一个链表的指针 这样再删除即可。链表为空就不能删了所以我们要断言一下。
void SLTPopFront(SLTNode** pphead) {assert(pphead *pphead);SLTErase(pphead,*pphead);
};
头删更简单不需要遍历直接调用删除函数即可。
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x) {assert(pos);SLTNode* next SLTBuyNode(x);next-next pos-next;pos-next next;
};
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos) {assert(pos);SLTNode* next pos-next;pos-next next-next;free(next);next NULL;
}; 这里是同理要插入就直接创建新链表然后插入即可,删除也是同理这里是需要判断pos是否为空的因为如果没有找到find函数就会返回空。
删除链表
void SListDesTroy(SLTNode** pphead) {assert(pphead *pphead);SLTNode* pcur *pphead;while (pcur) {SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
};
就需要遍历整个链表然后依次释放最后为了防止野指针我们还需要将*pphead置为NULL。
三.链表
链表的种类有很多种。 任意两两组合就有2 * 2 * 2 8种组合
这个带头和不带头后面双链表再讲解。
我们通常所说的单链表是不带头单向不循环链表。
单向就是通过一个只能访问下一个节点不能访问上一个节点否则就是双向。
循环就是链表围成一个圈链表的最后一个节点next指向头节点了而不是NULL. 虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构 单链表 和 双向带头循环链表 ⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带 来很多优势实现反⽽简单了后⾯我们代码实现了就知道了。
