广东省建设行业统一身份认证平台,谷歌seo网站推广,济南莱芜又出新情况了,石家庄制作网站推广链表的使用
虽然有这么多的链表的结构#xff0c;但是我们实际中最常⽤还是两种结构#xff1a; 单链表 和 双向带头循环链表 1. ⽆头单向⾮循环链表#xff1a;结构简单#xff0c;⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构#xff0c;如哈希桶、…链表的使用
虽然有这么多的链表的结构但是我们实际中最常⽤还是两种结构 单链表 和 双向带头循环链表 1. ⽆头单向⾮循环链表结构简单⼀般不会单独⽤来存数据。实际中更多是作为其他数据结 构的⼦结构如哈希桶、图的邻接表等等。另外这种结构在笔试⾯试中出现很多。 2. 带头双向循环链表结构最复杂⼀般⽤在单独存储数据。实际中使⽤的链表数据结构都 是带头双向循环链表。另外这个结构虽然结构复杂但是使⽤代码实现以后会发现结构会带 来很多优势实现反⽽简单了后⾯我们代码实现了就知道了。
补充说明
1、链式机构在逻辑上是连续的在物理结构上不⼀定连续
2、节点⼀般是从堆上申请的 3、从堆上申请来的空间是按照⼀定策略分配出来的每次申请的空间可能连续可能不连续 SList.h
#pragma once
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includestdlib.h
#includeassert.h
#includestdbool.h
//定义链表节点的结构
typedef int SLDataType;
typedef struct SListNode{int data;//要保存的数据struct SListNode* next;
}SLNode;
//创建节点组成链表并打印链表
void SLPrint(SLNode* phead);
//尾插
void SLPushBack(SLNode** pphead, SLDataType x);
void SLPushFront(SLNode** pphead, SLDataType x);
//尾删
void SLPopBack(SLNode** pphead);
void SLPopFront(SLNode** pphead);
//在指定位置之前插入数据
void SLInit(SLNode** pphead, SLNode* pos, SLDataType x);
//在指定位置之后插入数据
void SLInit(SLNode* pos, SLDataType x);
//找节点(考虑第一个参数为一级指针还是二级指针)
//因为不改变头节点所以可以传一级指针
//但由于代码一致性原则(保持接口一致性)应该传二级指针
void SLFind(SLNode** pphead, SLDataType x);
//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos);
//删除pos之后的结点
void SLEraseAfter(SLNode** pphead, SLNode* pos);
//销毁链表
void SLDesTory(SLNode** pphead);
SList.c
#define _CRT_SECURE_NO_WARNINGS
#include SList.h
void SLPrint(SLNode* phead) {//循环打印、SLNode* pcur phead;while (pcur) {printf(%d -, pcur-data);pcur pcur-next;}printf(NULL\n);
}SLNode* SLBuyNode(SLDataType x) {SLNode* node (SLNode*)malloc(sizeof(SLNode));node-data x;node-next NULL;return node;
}
//尾插
void SLPushBack(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node SLBuyNode(x);if (*pphead NULL) {*pphead node;return;}//链表不为空找尾(定义一个临时变量pcur)SLNode* pcur *pphead;while (pcur-next) {pcur pcur-next;}pcur-next node;
}
void SLPushFront(SLNode** pphead, SLDataType x) {assert(pphead);SLNode* node SLBuyNode(x);//新节点跟头结点连接起来node-next *pphead;//plist//让新的节点成为头结点*pphead node;
}
void SLPopBack(SLNode** pphead) {assert(pphead);//第一个节点不能为空assert(*pphead);//只有一个节点的情况if ((*pphead)-nextNULL) {//直接删除头结点free(*pphead);pphead NULL;return;}//有多个结点的情况//找到尾结点的前一个节点SLNode* prev NULL;SLNode* ptail *pphead;while (ptail-next ! NULL) {prev ptail;ptail ptail-next;}//prev的next指针不在指向ptail而是指向ptail的下一个节点prev-next ptail-next;free(ptail);ptail NULL;
}
void SLPopFront(SLNode** pphead) {assert(pphead);assert(*pphead);SLNode* del *pphead;*pphead (*pphead)-next;free(del);del NULL;
}
void SLInit(SLNode** pphead, SLNode* pos, SLDataType x) {assert(pphead);SLNode* node SLBuyNode(x);//处理没有结点的情况(约定链表不能为空pos也不能为空)assert(pos);assert(*pphead);//处理只有一个结点pos指向第一个结点(pos即为第一个结点)if ((*pphead)-next NULL||pos*pphead) {node-next *pphead;*pphead node;return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next ! NULL) {prev prev-next;}prev-next pos;pos-next node;
}
//查找第一个为x的节点
void SLFind(SLNode** pphead, SLDataType x) {SLNode* pcur *pphead;while (pcur) {if (pcur-data x) {return pcur;}pcur pcur-next;}return NULL;
}
//删除pos结点
void SLErase(SLNode** pphead, SLNode* pos) {assert(pphead);assert(*pphead);assert(pos);if (pos *pphead) {*pphead (*pphead)-next;free(pos);return;}//找pos的前一个节点SLNode* prev *pphead;while (prev-next!pos) {prev prev-next;}prev-next pos-next;free(pos);posNULL;
}
//删除pos之后的结点
void SLEraseAfter(SLNode** pphead, SLNode* pos) {assert(pos pos-next);SLNode* del pos-next;free(del);del NULL;
}
//销毁链表
void SLDesTory(SLNode** pphead) {assert(pphead);SLNode* pcur *pphead;//循环删除while (pcur) {SLNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS
//int removeElement(int* nums, int numsSize, int val) {
// int src, dst;
// while (src numsSize) {
// if (nums[src] val) {
// src;
// }
// else {
// nums[dst] nums[src];
// src;
// dst;
// }
// }
// return dst;
//}
//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
// int l1 m - 1, l2 n - 1;
// int l3 m n - 1;
// while (l1 0 l2 0) {
// if (nums1[l1] nums2[l2]) {
// nums1[l3--] nums1[l1--];
// }
// else {
// nums1[l3--] nums2[l2--];
// }
// }
// while (l2 0) {
// nums1[l3--] nums2[l2--];
// }
//}
#includeSList.h
void slttest() {SLNode* node1 (SLNode*)malloc(sizeof(SLNode));node1-data 1;SLNode* node2 (SLNode*)malloc(sizeof(SLNode));node2-data 2;SLNode* node3 (SLNode*)malloc(sizeof(SLNode));node3-data 3;SLNode* node4 (SLNode*)malloc(sizeof(SLNode));node4-data 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLNode* plist node1;SLPrint(plist);
}
int main() {slttest();return 0;
}
