哈尔滨做网站的,wordpress反应,广东省自然资源厅邮箱,怎样自学设计室内装修效果图文章目录 目录1. 链表的概念及结构2. 实现单链表2.1 链表的打印2.2 链表的尾插2.3 链表的头插2.4 链表的尾删2.5 链表的头删2.6 查找2.7 在指定位置之前插入数据2.8 在指定位置之后插入数据2.9 删除pos节点2.10 删除pos之后的节点2.11 销毁链表 3. 链表的分类 目录
链表的概念… 文章目录 目录1. 链表的概念及结构2. 实现单链表2.1 链表的打印2.2 链表的尾插2.3 链表的头插2.4 链表的尾删2.5 链表的头删2.6 查找2.7 在指定位置之前插入数据2.8 在指定位置之后插入数据2.9 删除pos节点2.10 删除pos之后的节点2.11 销毁链表 3. 链表的分类 目录
链表的概念及结构实现单链表链表的分类
1. 链表的概念及结构
概念 链表是⼀种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的链表在逻辑上是连续的在物理结构上不一定连续 。 链表是由一个一个节点结点组成的一个节点由两个部分组成要存储的数据 指针结构体指针
因此只要定义节点的结构就等于定义了链表
typedef int SLTDataType;//链表是由节点组成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;2. 实现单链表
2.1 链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}2.2 链表的尾插
void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));newnode-data x;newnode-next NULL;//链表为空新节点作为pheadif (NULL phead){phead newnode;return;}//链表不为空找尾节点SLTNode* ptail phead;while (ptail-next){ptail ptail-next;}//ptail就是尾节点ptail-next newnode;
}这样写是错误的当一开始链表为空时尾插的节点就变成了第一个节点因此要把phead中的NULL改为第一个节点的地址所以要传phead的地址而不是传值。
应该这样写
//因为头插、尾插、指定位置插入都需要申请新节点所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (NULL newnode){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//链表为空新节点作为pheadif (NULL *pphead){*pphead newnode;return;}//链表不为空找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail就是尾节点ptail-next newnode;
}2.3 链表的头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}2.4 链表的尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点有多个节点if (NULL (*pphead)-next){free(*pphead);*pphead NULL;return;}SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;//销毁尾节点free(ptail);ptail NULL;
}2.5 链表的头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头节点释放掉SLTNode* next (*pphead)-next;//-的优先级高于*free(*pphead);*pphead next;
}2.6 查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}2.7 在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode SLTBuyNode(x);//pos刚好是头节点if (pos *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev - newnode - posprev-next newnode;newnode-next pos;
}2.8 在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}2.9 删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是第一个节点没有前驱节点执行头删if (*pphead pos){//头删SLTPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}2.10 删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos-next不能为空assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}2.11 销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}完整代码
//SList.h#include stdio.h
#include stdlib.h
#include assert.htypedef int SLTDataType;//链表是由节点组成
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//链表的头插、尾插
//void SLTPushBack(SLTNode* phead, SLTDataType x);//err
void SLTPushBack(SLTNode** pphead, SLTDataType x);
void SLTPushFront(SLTNode** pphead, SLTDataType x);//链表的头删、尾删
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);//SList.c#include SList.hvoid SLTPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur){printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//因为头插、尾插、指定位置插入都需要申请新节点所以单独封装成一个函数
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (NULL newnode){perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);//链表为空新节点作为pheadif (NULL *pphead){*pphead newnode;return;}//链表不为空找尾节点SLTNode* ptail *pphead;while (ptail-next){ptail ptail-next;}//ptail就是尾节点ptail-next newnode;
}void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead;*pphead newnode;
}void SLTPopBack(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//链表不为空//链表只有一个节点有多个节点if (NULL (*pphead)-next){free(*pphead);*pphead NULL;return;}SLTNode* ptail *pphead;SLTNode* prev NULL;while (ptail-next){prev ptail;ptail ptail-next;}prev-next NULL;//销毁尾节点free(ptail);ptail NULL;
}void SLTPopFront(SLTNode** pphead)
{assert(pphead);//链表不能为空assert(*pphead);//让第二个节点成为新的头//把旧的头节点释放掉SLTNode* next (*pphead)-next;//-的优先级高于*free(*pphead);*pphead next;
}//查找
SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{assert(pphead);//遍历链表SLTNode* pcur *pphead;while (pcur) //等价于pcur ! NULL{if (pcur-data x){return pcur;}pcur pcur-next;}//没有找到return NULL;
}//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//要加上链表不能为空assert(*pphead);SLTNode* newnode SLTBuyNode(x);//pos刚好是头节点if (pos *pphead){//头插SLTPushFront(pphead, x);return;}//pos不是头节点的情况SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}//prev - newnode - posprev-next newnode;newnode-next pos;
}//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);newnode-next pos-next;pos-next newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos刚好是第一个节点没有前驱节点执行头删if (*pphead pos){//头删SLTPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);//pos-next不能为空assert(pos-next);SLTNode* del pos-next;pos-next pos-next-next;free(del);del NULL;
}//销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}//Test.c//int removeElement(int* nums, int numsSize, int val)
//{
// //定义两个变量
// int src 0, dst 0;
//
// while (src numsSize)
// {
// //nums[src] val,src
// //否则赋值,src和dst都
// if (nums[src] val)
// {
// src;
// }
// else
// {
// //说明src指向位置的值不等于val
// nums[dst] nums[src];
// dst;
// src;
// }
// }
//
// //此时dst的值刚好是数组的新长度
// return dst;
//}//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
// int l1 m - 1;
// int 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--];
// }
// }
//
// //要么是l1 0要么是l2 0
// while (l2 0)
// {
// nums1[l3--] nums2[l2--];
// }
//}#include SList.hvoid SListTest01()
{//一般不会这样去创建链表这里只是为了给大家展示链表的打印SLTNode* node1 (SLTNode*)malloc(sizeof(SLTNode));node1-data 1;SLTNode* node2 (SLTNode*)malloc(sizeof(SLTNode));node2-data 2;SLTNode* node3 (SLTNode*)malloc(sizeof(SLTNode));node3-data 3;SLTNode* node4 (SLTNode*)malloc(sizeof(SLTNode));node4-data 4;node1-next node2;node2-next node3;node3-next node4;node4-next NULL;SLTNode* plist node1;SLTPrint(plist);
}void SListTest02()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);//SLTPushBack(NULL, 5);//SLTPushFront(plist, 5);//SLTPrint(plist);//SLTPushFront(plist, 6);//SLTPrint(plist);//SLTPushFront(plist, 7);//SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);SLTPopBack(plist);SLTPrint(plist);//SLTPopBack(plist);//SLTPrint(plist);
}void SListTest03()
{SLTNode* plist NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);//头删//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);//SLTPopFront(plist);//SLTPrint(plist);SLTPopFront(plist);SLTPrint(plist);//SLTNode* FindRet SLTFind(plist, 3);if (FindRet){ printf(找到了\n);}else{ printf(未找到\n);}SLTInsert(plist, FindRet, 100);SLTPrint(plist);SLTInsertAfter(FindRet, 100);SLTPrint(plist);删除指定位置的节点//SLTErase(plist, FindRet);//SLTPrint(plist);SListDesTroy(plist);
}int main()
{//SListTest01();//SListTest02();SListTest03();return 0;
}3. 链表的分类
链表的结构非常多样以下情况组合起来就有8种2 x 2 x 2链表结构 链表说明 注
之前代码里写的 SList 意思是 single linked list -- 单链表不带头单向不循环链表刚才在单链表中提到的“头节点”指的是第一个有效的节点“带头”链表里的“头”指的是无效的节点“带头”中的“头”放哨的头节点哨兵位不保存任何有效的数据
虽然有这么多的链表的结构但是我们实际中最常用还是两种结构单链表和双向带头循环链表。
无头单向非循环链表结构简单⼀般不会单独用来存数据实际中更多是作为其他数据结构的子结构如哈希桶、图的邻接表等等另外这种结构在笔试面试中出现很多。带头双向循环链表结构最复杂⼀般用在单独存储数据实际中使用的链表数据结构都是带头双向循环链表另外这个结构虽然结构复杂但是使用代码实现以后会发现结构会带来很多优势实现反而简单了后面我们代码实现了就知道了。
