用php源码如何建设网站,wordpress 分类 模板,利用模板做网站,威海市建设工程协会网站目录
一#xff1a;什么是链表#xff1f;
二#xff1a;创建源文件和头文件
(1)头文件
(2)源文件
三#xff1a;实参和形参
四#xff1a;一步步实现单向链表
#xff08;1#xff09;建立一个头指针并置空
#xff08;2#xff09;打印链表#xff0c;便于…目录
一什么是链表
二创建源文件和头文件
(1)头文件
(2)源文件
三实参和形参
四一步步实现单向链表
1建立一个头指针并置空
2打印链表便于观察测试
3创建一个新的结点
4尾部插入数据
5头部插入
6尾部删除
7头部删除
8查找
9指定位置插入
10指定删除
11清空链表
12最终代码
SingleLinkedList.h
SingleLinkedList.c
text.c 五小结 一什么是链表 我们先看下面这个结构体。 这个结构体存储数据的同时保存了一个结构体指针。 链表其实就是一个个结构体后文把这样的一个结构体称为结点通过保存地址的方式找到下一个结构体最后一个结构体保存的地址为空。 链表的两种实现方式 1带头结点 2不带头结点 区别:带头结点有一个哨兵结点这个节点作为第一个节点,它的数据域不存储数据。 两者各有利弊我们进行结点删除时需要用到待删除结点的前一个结点。对于没有哨兵的单链表,当链表中只存在一个节点,需要进行单独处理。从而代码的复杂性增加。但如果设计了哨兵结点则第一个结点的处理与其他结点一致。但处理链表数据时这个哨兵结点属于无效数据我们需要规避这个数据也需要进行处理。 本文选择的是无哨兵链表。 二创建源文件和头文件
(1)头文件 头文件SingleLinkedList.h用来包含一些必要的头文件声明函数以及定义结构体。 (2)源文件 源文件SingleLinkedList.c用来实现链表的具体功能。 源文件text.c用来对各个功能进行测试。 三实参和形参 在实现链表之前我们需要先深入的认识一下实参和形参的关系。 我们看下面这个代码: 我们可以看到a的值并没有发生变化那我们如果传入a的地址进行解引用呢我们看下面这个代码。 我们可以看到a成功被修改为了5但这是为什么呢 答:其实在传入参数的时候系统临时开辟了一块空间用来接收数据函数调用结束时这一块空间就会被释放这意味着如果我们直接传入a的值我们只是在对这一块临时开辟的空间内的数据进行修改无论如何都不会影响到a,但如果我们传入的是a的地址对a进行解引用就能直接找到并修改a。 图解: 这是否意味着只要我们传入的是地址就一定能改变实参的值呢我们看下面这个代码。 我们发现虽然传入的是地址但p依旧指向a[0],并没有改变。这是为什么呢 答:与前面的原理一致我们传入p的时候也临时开辟了一片空间来保存p的值无论我们怎么改变p值在函数调用结束后这片空间会被释放所以p实际上还是指向a[0]的。 图解: 那如果我们传入p的地址是不是就能改变p了呢我们看代码。 图解: 四一步步实现单向链表
1建立一个头指针并置空 struct SListNode* head NULL; 2打印链表便于观察测试 我们用头指针的地址是否为空为循环条件。 我们可以分成两种情况讨论如果链表为空我们不进行遍历直接打印NULL。 如果链表中有元素从头指针第一个结点开始我们打印结点数据并让头指针指向下一个结点一直到NULL。 代码: 图解以有三个结点为例子 3创建一个新的结点 只要插入新结点我们就一定要生成新的结点我们可以把生成新结点的功能单独封装成函数BuyListNode()。 代码 4尾部插入数据 进行数据插入我们要改变实参的值即改变指针的指向必须传入头指针的地址二级指针。 基础思路【1】在进行数据插入之前我们要先生成一个新的结点。 【2】要进行尾部插入我们需要找到链表的最后一个结点并将它存储的指针指向新生成的结构体。 【3】我们设计一个指针tail来找尾部结点如果tail-next为NULL我们就找到了尾部结点结束循环。 图解 现阶段代码 我们对代码进行测试: 可以发现程序崩溃了这是为什么呢 答这是因为我们没有考虑链表为空的情况如果链表为空我们会直接对空指针进行解引用导致程序崩溃。 为了解决这个问题我们可以对这种情况进行单独处理。 代码 再次测试观察结果。 我们发现数据成功插入了。 5头部插入 进行数据插入我们要改变实参的值即改变指针的指向必须传入头指针的地址二级指针。 思路头部插入我们只需要让头指针指向新结点让新结点的指针域指向原来的头结点。 代码 前面进行尾部插入的时候需要考虑链表为空的情况那头部插入需不需要单独进行这个临界条件的处理呢 图解 我们可以发现最后结点的指针域会指向空所以不需要考虑这个临界情况。 6尾部删除 进行数据插入我们要改变实参的值即改变指针的指向必须传入头指针的地址二级指针。 思路和尾部插入一样我们需要使用一个tail指针找到尾部结点方法与前面一致然后释放这个结点。 我们看代码和运行结果 我们发现程序打印的是随机数这是为什么呢 答因为我们释放最后一个结点的时候上一个结点的指针域没有指空但空间已经被系统回收了此时我们进行指针的引用是非法的也就是我们常说的野指针。 解决方案我们可以设计一个指针prev来记录倒数第二个结点在释放尾结点后让倒数第二个结点的指针域指向空。 但此时程序依然存在不足。 如果链表为空我们就会对空指针进行解引用所以我们需要单独处理这种情况这里提供两种解决方案 第一我们可以直接返回空。 第二我们可以使用断言让程序直接报错。 这里使用第一种方法。 代码和测试结果 7头部删除 进行数据插入我们要改变实参的值即改变指针的指向必须传入头指针的地址二级指针。 思路进行头部删除可以将第一个结点释放然后让头指针指向第二个结点。 代码和运行结果 8查找 查找有两种实现方式一种返回结点地址一种返回数据在第几个结点。 思路遍历整个链表一直到找到要查找的数据或最后一个结点为止。 如果没有查找到数据返回NULL或者0。 第一种(我用的) 第二种 上述函数我们只能找到第一个数后面相同的找不到如果我们需要查找链表中所有该数的位置 我们可以设计一个pos指针并进行循环循环结束条件为pos为空这样就可以实现多次查找我们看代码。这个方法只适用于第一种 9指定位置插入 这里给出两种插入方式一种是指定在那个结点前插入一种是指定在那个结点后插入 第一种前插入 第一种后插入 在进行插入前我们需要找到要插入的那个结点的前面后面可以先使用查找函数找到位置在进行插入。 测试结果 10指定删除 思路删除的思路同尾删类似我们需要找到待删除的结点并保存待删除的结点的指针域。 代码 在进行删除前我们需要找到要删除的那个结点的前一个结点目的是让前面的结点指针域指向下下个结点可以先使用查找函数找到位置再进行删除。 测试 11清空链表 思路从第一个结点开始设计一个pos指针每次循环把头指针指向的结点地址赋给pos让头指针指向下一个结点地址调用free释放pos指向的结点。 图解(以三个结点为例子): 代码和测试结果 12最终代码 SingleLinkedList.h #pragma once
#include stdio.h
#include stdlib.h
//#include assert.h 要使用断言的话注意包含头文件//结构体数据类型重定义方便我们更改要存储的元素类型
typedef int SLTDataType;struct SListNode
{SLTDataType data; //要存储的数据(数据域)struct SListNode* next; //用来存储下一个结构体的地址指针域
};//打印
void SListPrint(struct SListNode* phead);
//创建一个新节点
struct SListNode* BuyListNode(SLTDataType x);
//尾部插入
void SListPushBack(struct SListNode** pphead, SLTDataType x);
//头部插入
void SListPushFront(struct SListNode** pphead, SLTDataType x);
//尾部删除
void SListPopBack(struct SListNode** pphead);
//头部删除
void SListPopFront(struct SListNode** pphead);
//查找,返回对应结点地址
//int SListFind(struct SListNode* phead, SLTDataType x);
struct SListNode* SListFind(struct SListNode* phead, SLTDataType x);
//指定插入还有一种按输入位置来插入在前面插入
void SListInsertF(struct SListNode** pphead, struct SListNode* pos, SLTDataType x);
void SListInsertB(struct SListNode** pphead, struct SListNode* pos, SLTDataType x);//指定删除
void SListEarse(struct SListNode** pphead, struct SListNode* pos);
//销毁链表
void SListDestory(struct SListNode** pphead);SingleLinkedList.c #define _CRT_SECURE_NO_WARNINGS 1
#include SingleLinkedList.h//打印链表
void SListPrint(struct SListNode* phead)
{//一直循环直到找到最后一个结点while (phead){printf(%d- , phead-data); //依次打印结点存储的数据phead phead-next; //让phead指向下一个结点}printf(NULL\n);
}//生成新节点
struct SListNode* BuyListNode(SLTDataType x)
{//调用maoolc()函数生成一个结点struct SListNode* newNode (struct SListNode*)malloc(sizeof(struct SListNode));//如果申请失败打印错误并结束程序if (newNode NULL){printf(malloc error\n);exit(-1);}//将要插入的数据赋给新结点newNode-data x;//新节点的next置空newNode-next NULL;//返回生成的结点的地址return newNode;
}//尾部插入
void SListPushBack(struct SListNode** pphead, SLTDataType x)
{//生成一个新的结点struct SListNode* newnode BuyListNode(x);//如果链表为空直接把新结点地址赋给*ppheadif (*pphead NULL){*pphead newnode;}else{ //设置一个指针tail用来找到尾部结点struct SListNode* tail *pphead;//不断循环直到找到尾部结点while (tail-next){tail tail-next;//指向下一个结点}//让原本置空的指针指向新生成的结点tail-next newnode;}
}//头部插入
void SListPushFront(struct SListNode** pphead, SLTDataType x)
{//生成新结点struct SListNode* newnode BuyListNode(x);//保存原来第一个结点的地址struct SListNode* prev *pphead;//让头指向新结点*pphead newnode;newnode-next prev;
}//尾部删除
void SListPopBack(struct SListNode** pphead)
{//如果链表为空就直接返回空也可以使用assert(*pphead!NULL)if (*pphead NULL){ return;}//如果只有一个结点if ((*pphead)-next NULL){free(*pphead);*pphead NULL;}else{//找尾部struct SListNode* tail *pphead;//记录尾部的前一个结点的地址struct SListNode* prev NULL;//找尾部结点并保存尾部结点的前一个结点的地址while (tail-next){prev tail;tail tail-next;}//找到尾部结点释放free(tail);//置空tail NULL;//把尾部的前一个结点保存的地址置空prev-next NULL;}
}//头部删除
void SListPopFront(struct SListNode** pphead)
{//如果链表为空返回空也可以使用assert(*pphead!NULL)if (*pphead NULL){return;}else{//找到下一个结点的地址struct SListNode* prev (*pphead)-next;//释放第一个结点free(*pphead);//头指针指向第二个结点*pphead prev;}
}//查找
struct SListNode* SListFind(struct SListNode* phead, SLTDataType x)
{struct SListNode* cur phead;//循环查找while (cur){//找到返回该结点地址if (cur-data x){return cur;}//没找到指向下一个结点else{cur cur-next;}}//如果没找到返回NULLreturn NULL;
}
//第二种
//int SListFind(struct SListNode* phead, SLTDataType x)
//{
// //记录第几个结点
// int i 1;
// struct SListNode* cur phead;
// //循环查找
// while (cur)
// {
// //找到返回该结点地址
// if (cur-data x)
// {
// return i;
// }
// //没找到指向下一个结点,i加1
// else
// {
// i i 1;
// cur cur-next;
// }
// }
// //如果没找到返回0
// return 0;
//}//指定结点前插入
void SListInsertF(struct SListNode**pphead,struct SListNode* pos,SLTDataType x)
{//生成一个新的结点struct SListNode* newnode BuyListNode(x);//只有一个结点或者链表为空进行头插if (*pphead pos){newnode-next *pphead;*pphead newnode;}else{//设计一个结构体指针来找pos的前一个结点struct SListNode* posprev *pphead;while (posprev-next ! pos){posprev posprev-next;}posprev-next newnode;newnode-next pos; }
}
//指定结点后插入
void SListInsertB(struct SListNode**pphead,struct SListNode* pos,SLTDataType x)
{//生成一个新的结点struct SListNode* newnode BuyListNode(x);//新结点指针域指向该结点的后一个newnode-next pos-next;//结点的指针域指向新结点pos-next newnode;
}//指定位置删除
void SListEarse(struct SListNode** pphead, struct SListNode* pos)
{//如果链表为空返回空也可以使用assert(*pphead!NULL)if (*pphead NULL){return;}//要删除的结点是第一个结点if (pos *pphead){//找到下一个结点的地址struct SListNode* prev (*pphead)-next;//释放第一个结点free(*pphead);//头指针指向第二个结点*pphead prev;}else{//要找到pos结点的前一个结点位置struct SListNode* posprev *pphead;while (posprev-next ! pos){posprev posprev-next;}//让posprev的指针域指向下下个结点posprev-next pos-next;//释放结点pos的空间free(pos);pos NULL;}
}//清空链表
void SListDestory(struct SListNode** pphead)
{struct SListNode* prev *pphead;while ((*pphead)! NULL){//找到头指针指向的结点prev *pphead;//让头指针指向下一个结点*pphead (*pphead)-next;//释放前面的结点free(prev);}
} text.c #define _CRT_SECURE_NO_WARNINGS 1
#include SingleLinkedList.hvoid text1()
{struct SListNode* head NULL;SListPushFront(head, 5);SListPushFront(head, 50);SListPushFront(head, 50);SListPushFront(head, 5);struct SListNode* pos SListFind(head, 50);int i 1;//查找多个相同的值while (pos){printf(第%d个pos节点:%p-%d\n, i, pos, pos-data);//pos指向目标结点的下一个结点pos SListFind(pos-next, 50);}SListPrint(head);//修改pos SListFind(head, 50);if (pos){pos-data 30;}SListPrint(head);}void text2()
{struct SListNode* head NULL;//插入SListPushBack(head, 2);SListPushBack(head, 5);SListPushBack(head, 15);//查找14位置struct SListNode* pos SListFind(head, 14);//判断是否有14if (pos NULL){printf(没有该数据\n);}else{//删除14SListEarse(head, pos);}SListPrint(head);//清空SListDestory(head);//插入SListPushBack(head, 2);SListPushBack(head, 5);SListPrint(head);
}int main()
{/*text1();*/text2();return 0;
} 五小结 相较于顺序表链表能够更好的利用零散的空间并且插入数据不需要大量移动数据但是单链表在物理层上不是连续存储的我们只能前找后却无法后找前而且一旦指针域的数据丢失我们就没法找到后续结点后续的双向链表可以很好的解决这个问题。 顺序表讲解链接http://t.csdn.cn/V96aI
