专业建设润滑油网站,教程网站建设,网站建设属于什么工作,装修公司做推广网站怎么弄目录
1.链表的概念及结构
2.单链表功能的实现
2.1打印单链表
2.2创建节点
2.3单链表尾插
2.3单链表头插
2.5单链表尾删
2.6单链表头删
2.7单链表的查找
2.8在指定位置之前插入数据
2.9在指定位置之后插入数据
2.10删除pos节点
2.11删除pos之后的节点
2.12销毁链表…目录
1.链表的概念及结构
2.单链表功能的实现
2.1打印单链表
2.2创建节点
2.3单链表尾插
2.3单链表头插
2.5单链表尾删
2.6单链表头删
2.7单链表的查找
2.8在指定位置之前插入数据
2.9在指定位置之后插入数据
2.10删除pos节点
2.11删除pos之后的节点
2.12销毁链表
3.完整代码
SList.h
SList.c 1.链表的概念及结构 线性表的逻辑结构属于线性结构采用顺序存储结构为顺序表采用链式存储结构为线性链表。 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的。 链表的结构跟火车车厢相似淡季时火车的车厢会相应减少旺季时火车的车厢会额外增加几节。只需要将某节车厢去掉或者加上不影响其他车厢每节车厢都是独立存在的。 且每节车厢都有车门假设每节车厢的车门都是锁上的状态需要不同的钥匙才能解锁每次只能携带一把钥匙的情况下如何从车头走到车尾 最简单的做法每节车厢里都放一把下一节车厢的钥匙。 在链表里每节“车厢”是什么样的呢 与顺序表不同的是链表里的每节车厢都是独立申请下来的空间我们称之为“结点/节点” 节点的组成主要有两个部分要保存的数据和下一个节点的地址指针变量。 图中指针变量 plist保存的是第一个节点的地址我们称plist此时“指向”第一个节点如果我们希望plist“指向”第二个节点时只需要修改plist保存的内容为0x0012FFA0。 为什么还需要指针变量来保存下一个节点的位置 链表中每个节点都是独立申请的即需要插入数据时才去申请一块节点的空间通过指针变量保存下一个节点位置才能从当前节点找到下一个节点。 注意 链式结构在逻辑上是连续的在物理结构上不一定连续。节点一般是从堆上申请的。从堆上申请来的空间是按照一定策略分配出来的每次申请的空间可能连续可能不连续。 2.单链表功能的实现
2.1打印单链表
void SLPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur)//pcur!NULL{printf(%d-, pcur-data);pcur pcur-next; //将指针指向下一个节点}printf(NULL\n);
}
2.2创建节点 单链表每次插入都需要插入一个节点所以我们最好写一个创建节点的函数方便后续调用。 SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL) //申请失败{perror(malloc fail!);exit(1);}newnode-data x;newnode-next NULL;return newnode;
}
2.3单链表尾插 尾插时需要找到最后一个节点的位置再插入数值但是要注意假如传进来一个空链表ptailNULL那么对它进行找尾操作势必会造成ptail-next这句代码对空指针进行解引用所以分成两种情况 1.如果链表为空直接插入即可。 2.如果链表不为空需要找到尾节点再插入。 输出结果 我们发现输出结果不是1而是NULL这是为什么呢 SLTPushBack(plist, 1); 一级指针不能实现的原因传参的时候另外创建一个一级指针phead接收plist传过来的值它和plist指针一样指向NULL 这里属于传值调用虽然plist变量存储的值是地址尾插数据后再让phaed指针指向newnode,在此期间plist仍然指向NULL没有发生任何改变因为形参的改变无法影响实参调用链表打印函数打印字符NULL。 当链表为空时一开始plist指向空指针然后需要plist指向newnode需要改变plist的指向这里用一级指针是实现不了的需要用二级指针二级指针才能改变一级指针plist的指向。若链表不为空不需要改变plist的指向程序依然可以正常运行。 小贴士 一级指针的作用 : 将普通变量的一级指针传入函数作为参数 ,可以在函数中访问该一级指针指向的普通变量, 并且可以修改该普通变量的值,但是该普通变量所在内存地址不能被修改。 传参的时候传一级指针变量的地址plist使用pphead二级指针来接收 尾插代码
void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); //不能传空指针不能对空指针进行解引用//空链表和非空链表SLTNode* newnode SLTBuyNode(x);if (*pphead NULL) //*pphead是指向第一个节点的指针{*pphead newnode;}else{//找尾SLTNode* ptail *pphead;while (ptail-next)//ptail-next!NULL{ptail ptail-next;}//ptail指向的就是尾节点ptail-next newnode;}
}
2.3单链表头插 头插数据需要改变一级指针plist的指向这里也需要二级指针改变一级指针plist的指向。 void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead; //将newnode和头结点连接在一起*pphead newnode; //将链表头结点指向新的头
}
2.5单链表尾删 与单链表尾插类似当链表只有一个头结点时需要将plist置为空所以也需要二级指针。 void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空//链表只有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//链表有多个节点SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next) //找尾节点{prev ptail;ptail ptail-next;}free(ptail); //释放掉ptail指向的空间ptail NULL;prev-next NULL;//将ptail前一个节点next指针置为空防止野指针}
}
2.6单链表头删 先创建一个指针next,保存第二个节点的位置防止释放头结点导致找不到第二个节点。 void SLPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空SLTNode* next (*pphead)-next;//保存第二个节点free(*pphead);*pphead next; //第二个节点作为链表新头头指针走到新头的位置
}
2.7单链表的查找 查找数据不需要改变指针plist的指向这里使用一级指针传参即可。如果找到就返回这个节点的地址否则就返回空指针NULL。 SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{SLTNode* pcur phead;//再定义一个指针phead指针可能后续还要用不希望改变phead指针while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//pcurNULL 没有找到return NULL;
}
2.8在指定位置之前插入数据 当链表在头节点插入时使用头插。 void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);assert(pos);//若pos*pphead;说明是头插if (pos *pphead){SLTPushFront(pphead, x);//调用头插}else{SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos)//找pos的前一个节点prev{prev prev-next;}//将prev newnode pos 三个节点连起来newnode-next pos;prev-next newnode;}
}
2.9在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;//这里一定要注意顺序问题!pos-next newnode;
}
2.10删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos是头节点/pos不是头节点if (pos *pphead){//头删SLPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos)//找pos的前一个节点prev{prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;}
}2.11删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;//pos del del-nextpos-next del-next;free(del);del NULL;
}
2.12销毁链表
void SListDesTroy(SLTNode** pphead)
{assert(pphead);assert(*pphead);SLTNode* pcur *pphead;while (pcur){SLTNode* next pcur-next;free(pcur);pcur next;}*pphead NULL;
}
3.完整代码
SList.h
#pragma once
#includestdio.h
#includestdlib.h
#includeassert.h
//定义节点的结构
typedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;//链表打印
void SLPrint(SLTNode* phead);//链表尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//尾删
void SLTPopBack(SLTNode** pphead);//头删
void SLPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, 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
#includeSList.h
//打印链表
void SLPrint(SLTNode* phead)
{SLTNode* pcur phead;while (pcur)//pcur!NULL{printf(%d-, pcur-data);pcur pcur-next;}printf(NULL\n);
}//申请一个新节点
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL){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);if (*pphead NULL) //*pphead是指向第一个节点的指针{*pphead newnode;}else{//找尾SLTNode* ptail *pphead;while (ptail-next)//ptail-next!NULL{ptail ptail-next;}//ptail指向的就是尾节点ptail-next newnode;}
}//链表头插
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode SLTBuyNode(x);newnode-next *pphead; //将newnode和头结点连接在一起*pphead newnode; //将链表头结点指向新的头
}//尾删
void SLTPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空//链表只有一个节点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//链表有多个节点SLTNode* prev *pphead;SLTNode* ptail *pphead;while (ptail-next){prev ptail;ptail ptail-next;}free(ptail); //释放掉ptail指向的空间ptail NULL;prev-next NULL;//将ptail前一个节点next指针置为空防止野指针}
}//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead);assert(*pphead);//链表不能为空SLTNode* next (*pphead)-next;//先保存第二个节点的位置防止释放头结点导致找不到第二个节点free(*pphead);*pphead next; //第二个节点作为链表新头头指针走到新头的位置
}//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x)//不需要改变plist指向传一级指针即可
{SLTNode* pcur phead;//再定义一个指针phead指针可能后续还要用不希望改变phead指针while (pcur){if (pcur-data x){return pcur;}pcur pcur-next;}//pcurNULL 没有找到return NULL;
}//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(*pphead);assert(pos);//若pos*pphead;说明是头插if (pos *pphead){SLTPushFront(pphead, x);//调用头插}else{SLTNode* newnode SLTBuyNode(x);SLTNode* prev *pphead;while (prev-next ! pos)//找pos的前一个节点prev{prev prev-next;}//将prev newnode pos 三个节点连起来newnode-next pos;prev-next newnode;}
}//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode SLTBuyNode(x);//pos newnode pos-nextnewnode-next pos-next;//这里一定要注意顺序问题!pos-next newnode;
}//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);assert(pos);//pos是头节点/pos不是头节点if (pos *pphead){//头删SLPopFront(pphead);}else{SLTNode* prev *pphead;while (prev-next ! pos)//找pos的前一个节点prev{prev prev-next;}//prev pos pos-nextprev-next pos-next;free(pos);pos NULL;}
}//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* del pos-next;//pos del del-nextpos-next del-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;
}
