太原网站建设方案维护,建设网站案例分析,三合一网站制作价格,网站广告代理如何做线性表
线性表#xff08;linear list#xff09;是n个具有相同特性的数据元素的有限序列
线性表是一种在实际中广泛使 用的数据结构#xff0c;常见的线性表#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构#xff0c;也就说是连续的一条直线 …线性表
线性表linear list是n个具有相同特性的数据元素的有限序列
线性表是一种在实际中广泛使 用的数据结构常见的线性表顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构也就说是连续的一条直线 但是在物理结构上并不一定是连续的 线性表在物理上存储时通常以数组和链式结构的形式存储 也就是说我们可以将线性表当作顺序表与链表的集合体 顺序表
顺序表的本质是数组
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构一般情况下采用数组存 储
数组有一个绝对的优势下标的随机访问
举个例子:
对于二分查找来说只能用于数组还有其他排序一样就是通过数组的下标访问来实现的由于数组的数据是连续存储的可以通过下标按照规定的顺序来访问相对于的元素
在数组上完成数据的增删查改 顺序表一般可以分为
1. 静态顺序表使用定长数组存储元素
使用定长数组存储元素
//静态的顺序表#define N 10
typedef int SLDatatype;
//对SLDatatype重新赋予类型目的是可以随意改变SLDatatype的类型struct SeqList
{SLDatatype a[N];//定义一个数组int size;//评估顺序表有多少数据
};
但是对于静态顺序表而言它存在两个问题
1.由于事先给定长度当想扩容会变得非常麻烦给小了不够用
2.若给定过大长度则容易造成内存空间浪费给多了浪费
所以我们一般使用动态顺序表 2. 动态顺序表使用动态开辟的数组存储
//动态的顺序表typedef int SLdatatype;struct SeqList
{SLdatatype* a;//定义一个动态开辟的空间int size;//评估顺序表存储的有效数据个数int capacity;//评估顺序表的容量空间
};
对SeqList结构体进行初始化操作
void SLInit(SL* psl)//顺序初始化
{psl-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟4个SLDatatype类型的空间//将返回的无符号类型指针地址强制转换为SLDatatype*类型if (psl-a NULL){perror(malloc fail);return;}psl-size 0;psl-capacity 4;
}
通过上面可以看到对SeqList的数组a进行了动态开辟内存的操作
这样就可以弥补静态开辟内存的不足
接下来我们研究增删查改的实现
增
在上面我们进行了开辟空间的操作接下来我们进行增加元素的操作
分为以下几种头部增加头插尾部增加尾插任意位置增加
先来看头插
void SLPushFront(SL* psl, SLDatatype x)//头插
{int end psl-size - 1;int str 0;while (end str){psl-a[end 1] psl-a[end];//令后一项等于前一项后移前避免覆盖数据end--;}psl-a[str] x;psl-size;
}
由于我们在最前方进行数据插入的操作为了让移动数据时不会覆盖掉数据导致bug的出现
我们应该从后往前移动数据如上代码所示
但是对于这个代码会有什么样的问题出现呢
若当该空间psl-a已全部存放数据此时再进行插入数据操作时会出现越界问题
所以在进行插入操作前我们应该增加一次检查空间容量的操作
如下代码所示即为检查空间容量实现代码
void SLCheckCapacity(SL* psl)检查容量
{if (psl-size psl-capacity){SLDatatype* tmp (SLDatatype*)realloc(psl-a, sizeof(SLDatatype) * psl-capacity * 2);//扩容到原来空间的2倍if (tmp NULL){perror(realloc fail);return;}psl-a tmp;psl-capacity * 2;}
}
并需要在插入操作时加入该操作
下面看尾插
void SLPushBack(SL* psl, SLDatatype x)//尾插
{SLCheckCapacity(psl);//检查容量psl-a[psl-size] x;//psl-a[psl-size] x;//先赋值再自增psl-size;
}
由于也是插入数据操作我们依旧需要判断空间是否足够
在这里我们有两种表达方式
一种是psl-a[psl-size] x; psl-size;
另一种是psl-[psl-size] x;
这两种等效由于size为后置自增先使用再自增详细查看操作符详解
由于下标索引为psl-size指向的位置正为当前空间的最后一个元素空间
所以直接进行赋值操作再另size即可
最后看任意位置插入
void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{SLCheckCapacity(psl);//检查容量int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;
}
同上先进行空间检查操作
由于是在任意位置插入需要进行数据移位操作为了不覆盖数据需要从后往前移动
设定指针end令其指向当前最后有效一个元素的位置再进行移动赋值操作
直到end的位置等于pos的位置
但是对于这个代码而言存在一个很严重的问题
当我选择插入的空间大于或者小于这个空间的范围时会出现越界的情况
所以我们还需要在此之前增加一个判断检测pos的值是否合法
在这里我们有两种表达方式
void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{//assert(pos 0 pos psl-size);SLCheckCapacity(psl);//检查容量if (pos psl-size || pos 0){printf(输入错误!\n);return;}int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;
}
我么可以使用assert断言或者使用if判断语句前者是暴力检查后者是柔性检查
assert断言的使用方法 其实对于头插和尾插我们都可以通过引用任意位置插入的函数来实现 头插SLInsert(psl, 0, x);在起始位置插入 尾插SLInsert(psl , psl-size, x);在结束位置插入 删
对于删除操作我们也有以下三种情况
头部删除头删尾部删除尾删任意位置删除
首先看头删
void SLPopFront(SL* psl)//头删
{int str 0;while (str psl-size - 1){psl-a[str] psl-a[str 1];//将后值赋给前值从前往后避免覆盖str;}psl-size--;
}
由于是头部删除删除之后要进行元素移动操作
为了不使数据被覆盖这里需要从前往后移动数据避免覆盖
当删除完毕后size需要自减
对于这里而言我们仍然需要增加一个判断来检查空间内是否有元素需要删除避免越界
完整代码如下
void SLPopFront(SL* psl)//头删
{//assert(psl-size 0);if (psl-size 0){printf(表内无数据!\n);return;}int str 0;while (str psl-size - 1){psl-a[str] psl-a[str 1];//将后值赋给前值从前往后避免覆盖str;}psl-size--;
}
再来看尾部删除
void SLPopBack(SL* psl)//尾删
{//assert(psl-size 0);if (psl-size 0){printf(表内无数据!\n);return;}psl-size--;
}
同理我们仍然需要先判断空间内是否有元素
对于尾删而言也许我们一开始会选择将最后一个有效元素赋值为0
可是当最后一个有效元素本身就为0的情况下这种操作未免显得没有意义
所以我们可以直接选择直接令psl-size减少1直接去除最后一个元素
最后看任意位置删除
void SLErase(SL* psl, int pos)//任意位置删除
{//assert(pos 0 pos psl-size);if (pos psl-size || pos 0){printf(输入错误!\n);return;}while (pos psl-size - 1){psl-a[pos] psl-a[pos 1];pos;}psl-size--;
}
老规矩先检查空间
再进行移动赋值操作需要从后往前移动避免覆盖 对于头删和尾删可以引用任意位置删除函数来进行删除操作 头删SLErase(psl, 0);删除第一位元素 尾删SLErase(psl, psl-size - 1);删除最后一位元素 查
代码如下
SLDatatype SLFind(SL* psl, SLDatatype x)//查
{for (int i 0; i psl-size; i){if (psl-a[i] x){return i;}elsereturn -1;}
}
非常简单只需要一个循环遍历即可 改
代码如下
void SLModify(SL* psl, int pos, SLDatatype x)//改
{//assert(pos 0 pos psl-size);if (pos psl-size || pos 0){printf(输入错误!\n);return;}psl-a[pos] x;
}
同样非常简单
只需要通过下标索引值找到想要修改的值对其重新赋值即可 执行完上面的操作之后下面还有几个需要注意的点
打印函数
为了可以直观地看到数据我们需要使用一个打印函数来检查是否满足我们的需求
void SLPrint(SL* psl)//打印
{if (psl-size 0){printf(表内无数据!\n);}for (int i 0; i psl-size; i){printf(%d , psl-a[i]);}printf(\n);
}
释放内存
由于使用malloc和relloc函数在堆中开辟空间结束使用后需要手动释放内存
避免造成内存泄漏
void SLDestroy(SL* psl)//释放内存
{free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}值得一提的是我们在进行函数调用时有时候可能会出现错误传递空指针
为了避免这样的情况我们应该在每一个函数定义部分都加上assert断言
来判断是否有传递空指针的情况
完整代码如下
SeqList.h#include stdio.h
#include stdlib.h
#include assert.h//静态的顺序表//#define N 10
//typedef int SLDatatype;
对SLDatatype重新赋予类型目的是可以随意改变SLDatatype的类型
//
//struct SeqList
//{
// SLDatatype a[N];
// //定义一个数组
// int size;
// //评估顺序表有多少数据
//};//动态的顺序表typedef int SLDatatype;typedef struct SeqList
{SLDatatype* a;//定义一个动态开辟的空间int size;//评估顺序表存储的有效数据个数int capacity;//评估顺序表的容量空间
}SL;
//对结构体SeqList类型重命名void SLInit(SL* psl);//初始化
void SLDestroy(SL* psl);//释放内存void SLCheckCapacity(SL* psl);//检查容量空间是否足够
void SLPrint(SL* psl);//打印void SLPushBack(SL* psl, SLDatatype x);//尾插
void SLPushFront(SL* psl, SLDatatype x);//头插void SLPopBack(SL* psl);//尾删
void SLPopFront(SL* psl);//头删void SLInsert(SL* psl, int pos, SLDatatype x);//任意位置插入
void SLErase(SL* psl, int pos);//任意位置删除SLDatatype SLFind(SL* psl, SLDatatype x);//查
void SLModify(SL* psl, int pos, SLDatatype x);//改
此处是对结构体的定义函数的声明以及#define操作
SeqList.c#include SeqList.hvoid SLInit(SL* psl)//顺序初始化
{psl-a (SLDatatype*)malloc(sizeof(SLDatatype) * 4);//开辟4个SLDatatype类型的空间//将返回的无符号类型指针地址强制转换为SLDatatype*类型if (psl-a NULL){perror(malloc fail);return;}psl-size 0;psl-capacity 4;
}void SLCheckCapacity(SL* psl)检查容量
{assert(psl ! NULL);if (psl-size psl-capacity){SLDatatype* tmp (SLDatatype*)realloc(psl-a, sizeof(SLDatatype) * psl-capacity * 2);//扩容到原来空间的2倍if (tmp NULL){perror(realloc fail);return;}psl-a tmp;psl-capacity * 2;}
}void SLPrint(SL* psl)//打印
{assert(psl ! NULL);if (psl-size 0){printf(表内无数据!\n);}for (int i 0; i psl-size; i){printf(%d , psl-a[i]);}printf(\n);
}void SLDestroy(SL* psl)//释放内存
{assert(psl ! NULL);free(psl-a);psl-a NULL;psl-size 0;psl-capacity 0;
}void SLPushBack(SL* psl, SLDatatype x)//尾插
{assert(psl ! NULL);SLCheckCapacity(psl);//检查容量psl-a[psl-size] x;//psl-a[psl-size] x;//先赋值再自增psl-size;//SLInsert(psl , psl-size, 3);
}void SLPushFront(SL* psl, SLDatatype x)//头插
{assert(psl ! NULL);SLCheckCapacity(psl);//检查容量int end psl-size - 1;int str 0;while (end str){psl-a[end 1] psl-a[end];//令后一项等于前一项后移前避免覆盖数据end--;}psl-a[str] x;psl-size;//SLInsert(psl, 0, 3);
}void SLPopBack(SL* psl)//尾删
{assert(psl ! NULL);//assert(psl-size 0);if (psl-size 0){printf(表内无数据!\n);return;}psl-size--;//SLErase(psl, psl-size - 1);
}void SLPopFront(SL* psl)//头删
{assert(psl ! NULL);//assert(psl-size 0);if (psl-size 0){printf(表内无数据!\n);return;}int str 0;while (str psl-size - 1){psl-a[str] psl-a[str 1];//将后值赋给前值从前往后避免覆盖str;}psl-size--;//SLErase(psl, 0);
}void SLInsert(SL* psl, int pos, SLDatatype x)//任意位置插入
{assert(psl ! NULL);//assert(pos 0 pos psl-size);SLCheckCapacity(psl);//检查容量if (pos psl-size || pos 0){printf(输入错误!\n);return;}int end psl-size - 1;while (end pos){psl-a[end 1] psl-a[end];end--;}psl-a[pos] x;psl-size;
}void SLErase(SL* psl, int pos)//任意位置删除
{assert(psl ! NULL);//assert(pos 0 pos psl-size);if (pos psl-size || pos 0){printf(输入错误!\n);return;}while (pos psl-size - 1){psl-a[pos] psl-a[pos 1];pos;}psl-size--;
}SLDatatype SLFind(SL* psl, SLDatatype x)//查
{assert(psl ! NULL);for (int i 0; i psl-size; i){if (psl-a[i] x){return i;}elsereturn -1;}
}void SLModify(SL* psl, int pos, SLDatatype x)//改
{assert(psl ! NULL);//assert(pos 0 pos psl-size);if (pos psl-size || pos 0){printf(输入错误!\n);return;}psl-a[pos] x;
}
此处是对各个函数的定义
main.c#include SeqList.hvoid test1(SL* s)//头尾插及打印测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPushFront(s, 4);SLPrint(s);SLDestroy(s);
}void test2(SL* s)//尾删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPopBack(s);SLPopBack(s);SLPopBack(s);SLPopBack(s);//SLPopBack(s);//SLPopBack(s);//测试是否有越界的问题SLPrint(s);SLDestroy(s);
}void test3(SL* s)//头删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushFront(s, 1);SLPushFront(s, 2);SLPushFront(s, 3);SLPopFront(s);SLPopFront(s);SLPopFront(s);SLPopFront(s);//SLPopFront(s);//SLPopFront(s);SLPrint(s);SLDestroy(s);
}void test4(SL* s)//任意位置插与任意位置删测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLInsert(s, 2, 3);SLInsert(s, 3, 4);SLInsert(s, 4, 5);SLInsert(s, 5, 6);SLErase(s, 2);SLErase(s, 2);SLErase(s, 2);SLPrint(s);SLDestroy(s);
}void test5(SL* s)//查找与修改测试
{SLInit(s);SLPushBack(s, 1);SLPushBack(s, 2);SLPushBack(s, 3);SLPushBack(s, 4);SLModify(s, 1, 20);SLPrint(s);printf(%d\n, SLFind(s, 1));SLDestroy(s);
}int main()
{SL s;//test1(s);//test2(s);//test3(s);//test4(s);test5(s);return 0;
}
此处是主函数对各个函数的测试 链表
链表是一种物理存储结构上非连续、非顺序的存储结构
数据元素的逻辑顺序是通过链表中的指针链接次序实现的 相比较于顺序表链表可以做到以下几个点 1.不需要扩容 2.可以按需求申请释放 3.解决头部/中间插入删除需要解决的移动数据的问题 单链表
画图来理解
如图所示
黄色区域存放的是链表中每个结点的数据
粉色区域存放的是链表中每个结点指向下一个结点的地址
那么如何管理他们
首先起始位置需要有一个指针指向第一个结点
通过第一个结点的指针部分找到下一个结点的地址从而进行访问
以此类推
最后一个结点的指针指向空指针
如何定义
typedef int SLTDataType; //将int类型重命名为SLTDataTypetypedef struct SListNode
{SLTDataType data; //存放数据struct SListNode* next; //指向下一段的结构体指针
}SLTNode; //将struct SListNode重命名为SLTNode
对于单链表我们也需要实现不同的功能增删查
但在实现这些功能之前我们需要为链表写一个开辟空间的函数方便调用
//开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//开辟一个新的SLTNode结构体的空间将其强制转换为SLTNode*类型并将地址传给newnodeif (newnode NULL){perror(malloc fail);return NULL;}//判断是否开辟空间成功newnode-data x;newnode-next NULL;//对newnode进行初始化return newnode;
}
接收一个data数据x用于存放在链表结点内
将开辟的空间存放在newnode结构体指针中进行判断是否开辟成功
随后将newnode中的data赋值为x将newnode中的next置空防止出现悬空指针
返回这个新开辟的结点newnode 增
对于增有三种方法分别是头插尾插与任意位置前插
头插
//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//判断是否接收到plist的地址pphead是头指针plist的地址SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//判断是否开辟成功newnode-next *pphead;//令结点指针指向原先的结点通过pphead的地址修改*pphead newnode;//令phead指针指向新结点通过pphead的地址修改,其实是改变plist
}
首先使用断言判断是否接收到pphead传送过来的地址
调用开辟空间函数使用newnode接收新结点的地址
判断是否开辟成功
再另新结点指针指向原先的结点最后令phead指针指向新结点将头指向newnode 尾插第一种
//尾插
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail phead;while (tail ! NULL){tail tail-next;}SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//判断是否开辟成功tail newnode;
} 上面这种属于错误写法
首先定义以一个结构体指针tail接收phead的地址(将tail作为头)
判断tail是否为空
之后再使用一个结构体指针newnode接收新结点的地址
判断是否开辟成功
再令tail等于新结点newnode
但是
对于这个函数而言其实尾插是不成功的
有两个原因 1、本质上tail并没有与链表连接起来局部变量出了函数销毁 2、链表连接应该使用tail-next newnode来连接 接下来来改进一下 尾插第二种
//尾插
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail phead;while (tail-next ! NULL){tail tail-next;}SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);tail-next newnode;
}
上面这种属于错误写法
此处与上面第一种不同的点为最后连接方式是使用tail-next newnode来建立连接的
但是我们仍然忽略了一个最重要的点
局部变量出了函数自动销毁
此处我们定义了一个tail结构体指针来接收phead也就是想通过tail来改变链表
但是tail属于局部变量当尾插函数一结束tail自动销毁而他会对phead指向的链表更改吗
答案是不会的 由于phead本身属于指针SLTNode* phead他指向链表的头结点 想要通过传参改变链表就需要通过二级指针来传参SLTNode** pphead 第一层*访问找到pphead的地址第二层*通过地址在访问到pphead指向的链表头结点 只有这样才能通过传参改变链表 尾插第三种
//尾插正确写法
void SLPushBack(SLTNode** pphead, SLTDataType x)//使用二级指针来接收plist的地址
{SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//链表为空if (*pphead NULL)//对pphead进行解引用来访问pphead{*pphead newnode;//将newnode的地址赋值给pphead}//链表非空else{SLTNode* tail *pphead;//用结构体指针tail来接收pphead的地址(拷贝)while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}
对于这一种写法我们还加入了一个判断条件判度链表是否为空
假如链表没有任何元素时phead为NULL使用上面原来的方法将无法进行插入
需要分为两种情况链表有元素链表无元素进行讨论
之后再用结构体指针tail来接收指向头结点pphead的地址
通过二级指针来顺利改变链表 任意位置前插
//任意位置前插入
void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//判断目标位置是否为空SLTNode* prev *pphead;if (*pphead pos)//若目标位置为起始位置{SLPushFront(pphead, x);//头插return;}while (prev-next ! pos)//找到pos节点的上一个节点地址{prev prev-next;}SLTNode* newnode BuyLTNode(x);prev-next newnode;newnode-next pos;
}
参数为头结点指针pphead插入位置指针pos和插入元素x
老样子先进行链表判断是否为空的操作
由于任意位置前插会出现两种情况目标位置为起始位置、目标位置不为起始位置
对于这两种情况有不同的操作方法 起始位置 直接进行头插即可 非起始位置 首先要找到目标位置的上一个结点的地址定义一个结构体指针prev来接收头结点的地址 通过while循环来自增当prev的next指向的地址为pos的地址时 停止循环此时prev指向的结点即为pos的上一个位置的结点 用结构体指针newnode接收开辟空间返回的新结点的地址
随后令prev-next newnode; newnode-next pos;
即完成任意位置前插的操作 注意此种方法需要结合查的函数使用 删
删也分为三种方式头删、尾删与任意位置删
头删第一种
//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead NULL){printf(链表内无结点);}SLTNode* head *pphead;if (head ! NULL){if (head-next NULL)//只有一个结点{free(head);*pphead NULL;return;}*pphead head-next;//有多个结点free(head);}
}
由于是删除操作需要进行链表是否为空的判断以免出现越界访问的问题
使用结构体指针head访问*pphead达到二级指针更改结点的目的
若只有一个结点直接释放并令*pphead指向空NULL并返回
若有多个结点则令*pphead指向head-next的地址
释放head
对于头删还存在另一种方法 头删第二种
//头删
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead NULL){printf(链表内无结点);}SLTNode* head *pphead;//令结构体指针head指向起始位置if ((*pphead) ! NULL){*pphead (*pphead)-next;free(head);//释放head}
}
令起始位置指针指向next指向的位置 若只有一个元素则(*pphead)-next为NULL,令*pphead为NULL相同效果妙哉 尾删第一种
//尾删双指针法
void SLPopBack(SLTNode** pphead)
{if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;SLTNode* flag NULL;//找倒数第二个结点//while (tail-next ! NULL)//{// flag tail;// tail tail-next;//}while (tail-next)//指针整型可以直接做条件逻辑判断{flag tail;tail tail-next;}free(tail);if (flag ! NULL){flag-next NULL;}//此处加上判断是为了防止报警告
}
令结构体指针tail指向*pphead的地址
结构体指针flag指向空
当tail-next指向非空时
令falg指向tailtail指向tail-next此循环步骤是为了找到倒数第二个结点
找到以后释放tail
令flag-next指向NULL此处加一个判断是为了避免在VS运行的时候出现警告
但是这种方法可以更加简洁 尾删第二种
//尾删(直接找倒数第二个节点)
void SLPopBack(SLTNode** pphead)
{if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;while ((tail-next)-next)//两次解引用找到tail指向的结点的next指向的结点的next{tail tail-next;}free((tail-next));//更加巧妙tail-next NULL;
}
相比于第一种用两个指针来操作这种方法显得更加简洁
使用两次解引用找到tail指向的结点的next指向的结点的next
显得更加巧妙
但是以上两种尾删的方法都是不完美的当出现只有一个元素的情况是该如何处理呢 尾删第三种
//尾删(分两种情况)
void SLPopBack(SLTNode** pphead)
{assert(pphead);if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;if (tail ! NULL){if (tail-next NULL)//当前结点为唯一结点{free(tail);*pphead NULL;return;}while ((tail-next)-next)//当前节点非唯一结点{tail tail-next;}free((tail-next));tail-next NULL;}//此处的判断是为了防止报警告
}
首先进行判断链表是否为空的操作
令结构体指针tail接收*pphead
进行判断操作 若当前tail-next指向的为空则代表链表只有tail这一个结点直接释放tail并将*pphead置空返回 若tail并非当前唯一结点则令tail指向tail-next释放tail-next并将tail-next置空避免出现悬空指针 任意位置删除
//任意位置删除
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//判断目标位置是否为空if (pos *pphead)//判断是否为头{SLPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
参数为头结点pphead、目标位置pos
首先判断pos位置是否为头结点
是则使用头删
否则定义一个结构体指针prev接收*pphead
循环令prev指向pos的上一个结点的位置
令prev-next指向pos-next的位置
释放pos并将pos置空 查
//查
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur)//遍历链表查找{if (cur-data x){return cur;}cur cur-next;}return NULL;
}
使用遍历链表的方法查找
定义结构体指针cur接收phead
循环遍历链表当cur不为NULL时
cur指向cur-next的位置
若其中cur-data为目标元素返回cur否则返回空 完整代码如下
//SList.htypedef int SLTDataType;typedef struct SListNode
{SLTDataType data;//存放数据struct SListNode* next;//指向下一段的结构体指针
}SLTNode;void SLTPrint(SLTNode* phead);//打印
SLTNode* BuyLTNode();//开辟空间void SLPushFront(SLTNode** pphead, SLTDataType x);//头插
void SLPushBack(SLTNode** pphead, SLTDataType x);//尾插void SLPopFront(SLTNode** pphead);//头删
void SLPopBack(SLTNode** pphead);//尾删SLTNode* STFind(SLTNode* phead, SLTDataType x);//查找void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x);//任意位置前插入
void SLInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x);//任意位置后插入void SLErase(SLTNode** pphead, SLTNode* pos);//任意位置删除SList.c
#define _CRT_SECURE_NO_WARNINGS 1#include SList.hvoid SLTPrint(SLTNode* phead)//打印链表遍历
{SLTNode* cur phead;//令cur等于当前指针拷贝while (cur ! NULL){printf(%d - , cur-data);cur cur-next;//令cur指向下一段的地址}printf(NULL\n);
}//开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));//开辟一个新的SLTNode结构体的空间将其强制转换为SLTNode*类型并将地址传给newnodeif (newnode NULL){perror(malloc fail);return NULL;}//判断是否开辟空间成功newnode-data x;newnode-next NULL;//对newnode进行初始化return newnode;
}//头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);//判断是否接收到plist的地址pphead是头指针plist的地址SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//判断是否开辟成功newnode-next *pphead;//令结点指针指向原先的结点通过pphead的地址修改*pphead newnode;//令phead指针指向新结点通过pphead的地址修改,其实是改变plist
}/*
//尾插(错误写法1)
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail phead;while (tail ! NULL){tail tail-next;}SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//判断是否开辟成功tail newnode;
}//本质上tail并没有与链表连接起来局部变量出了函数销毁
*//*
//尾插错误写法2
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* tail phead;while (tail-next ! NULL){tail tail-next;}SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);tail-next newnode;//假如链表没有任何元素时phead为NULL使用上面的方法将无法进行插入//需要分为两种情况链表有元素链表无元素进行讨论
}
*//*
//尾插错误写法3
void SLPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//链表为空if (phead NULL){phead newnode;}//链表非空else{SLTNode* tail phead;while (tail-next ! NULL){tail tail-next;}tail-next newnode;}//由于plist传参phead无法改变plist局部变量所以需要使用地址传参来改变plist
}
*///尾插正确写法
void SLPushBack(SLTNode** pphead, SLTDataType x)//使用二级指针来接收plist的地址
{SLTNode* newnode BuyLTNode(x);assert(newnode ! NULL);//链表为空if (*pphead NULL)//对pphead进行解引用来访问plist{*pphead newnode;//将newnode的地址赋值给plist}//链表非空else{SLTNode* tail *pphead;//用结构体指针tail来接收plist的地址(拷贝)while (tail-next ! NULL){tail tail-next;}tail-next newnode;}
}/*
//头删方法1
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead NULL){printf(链表内无结点);}SLTNode* head *pphead;if (head ! NULL){if (head-next NULL)//只有一个结点{free(head);*pphead NULL;return;}*pphead head-next;//有多个结点free(head);}
}
*///头删(方法2)
void SLPopFront(SLTNode** pphead)
{assert(pphead);if (*pphead NULL){printf(链表内无结点);}SLTNode* head *pphead;//令结构体指针head指向起始位置if ((*pphead) ! NULL){*pphead (*pphead)-next;//令起始位置指针指向next指向的位置//若只有一个元素则(*pphead)-next为NULL,令*pphead为NULL相同效果free(head);//释放head}
}/*
//尾删(方法1双指针)
void SLPopBack(SLTNode** pphead)
{if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;SLTNode* flag NULL;//找倒数第二个结点//while (tail-next ! NULL)//{// flag tail;// tail tail-next;//}while (tail-next)//指针整型可以直接做条件逻辑判断{flag tail;tail tail-next;}free(tail);if (flag ! NULL){flag-next NULL;}//此处加上判断是为了防止报警告
}
*//*
//尾删(方法2,直接找倒数第二个节点)
void SLPopBack(SLTNode** pphead)
{if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;while ((tail-next)-next)//两次解引用找到tail指向的结点的next指向的结点的next{tail tail-next;}free((tail-next));//更加巧妙tail-next NULL;
}
*///以上两种尾删的方法都是不完美的当出现只有一个元素的情况是该如何处理呢//尾删(方法3分两种情况)
void SLPopBack(SLTNode** pphead)
{assert(pphead);if (*pphead NULL)//判断链表是否为空{printf(链表内无结点);}SLTNode* tail *pphead;if (tail ! NULL){if (tail-next NULL)//当前结点为唯一结点{free(tail);*pphead NULL;return;}while ((tail-next)-next)//当前节点非唯一结点{tail tail-next;}free((tail-next));tail-next NULL;}//此处的判断是为了防止报警告
}//查
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur)//遍历链表查找{if (cur-data x){return cur;}cur cur-next;}return NULL;
}//任意位置前插入
void SLInsertBefore(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);//判断目标位置是否为空SLTNode* prev *pphead;if (*pphead pos)//若目标位置为起始位置{SLPushFront(pphead, x);//头插return;}while (prev-next ! pos)//找到pos节点的上一个节点地址{prev prev-next;}SLTNode* newnode BuyLTNode(x);prev-next newnode;newnode-next pos;
}//任意位置后插入
void SLInsertAfter(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);SLTNode* newnode BuyLTNode(x);if (pos-next NULL)//如果目标位置为最后一个节点{pos-next newnode;newnode-next NULL;return;}newnode-next pos-next;pos-next newnode;
}//任意位置删除
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);//判断目标位置是否为空if (pos *pphead)//判断是否为头{SLPopFront(pphead);return;}SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}prev-next pos-next;free(pos);pos NULL;
}
//test.c#define _CRT_SECURE_NO_WARNINGS 1#include SList.hvoid test1()
{SLTNode* pplist NULL;SLPushFront(pplist, 1);SLPushFront(pplist, 2);SLPushFront(pplist, 3);SLPushFront(pplist, 4);SLTPrint(pplist);//ps此处需要通过pphead的地址修改
}void test2()
{SLTNode* pplist NULL;SLPushFront(pplist, 1);SLPushFront(pplist, 2);SLPushFront(pplist, 3);SLPushFront(pplist, 4);SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTPrint(pplist);
}void test3()
{SLTNode* plist NULL;SLPushBack(plist, 5);SLPushBack(plist, 6);SLPushBack(plist, 7);SLPushBack(plist, 8);SLTPrint(plist);
}void test4()//测试尾插
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTPrint(pplist);
}void test5()//测试尾删
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLPopBack(pplist);SLPopBack(pplist);SLPopBack(pplist);SLTPrint(pplist);
}void test6()//测试尾删
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLPopBack(pplist);SLPopBack(pplist);SLPopBack(pplist);SLPopBack(pplist);//SLPopBack(pplist);SLTPrint(pplist);
}void test7()//测试头删
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLPopFront(pplist);SLPopFront(pplist);SLPopFront(pplist);//SLPopFront(pplist);//SLPopFront(pplist);SLTPrint(pplist);
}void test8()//测试查找
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTNode* pos STFind(pplist, 10);assert(pos);//判断是否为空printf(%d %p, pos-data, pos-next);
}void test9()//测试任意位置前插入
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTNode* pos1 STFind(pplist, 5);SLInsertBefore(pplist, pos1, 66);//在5前插入SLTNode* pos2 STFind(pplist, 7);SLInsertBefore(pplist, pos2, 88);//在7前插入SLTPrint(pplist);
}void test10()//测试任意位置后插入
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTNode* pos1 STFind(pplist, 5);SLInsertAfter(pplist, pos1, 66);//在5后插入SLTNode* pos2 STFind(pplist, 7);SLInsertAfter(pplist, pos2, 88);//在7后插入SLTPrint(pplist);
}void test11()//测试任意删除
{SLTNode* pplist NULL;SLPushBack(pplist, 5);SLPushBack(pplist, 6);SLPushBack(pplist, 7);SLPushBack(pplist, 8);SLTNode* pos1 STFind(pplist, 5);SLErase(pplist, pos1);SLTNode* pos2 STFind(pplist, 7);SLErase(pplist, pos2);SLTPrint(pplist);
}//记住你要改变的是什么东西
int main()
{//test1();//test2();//test3();//test4();//test5();//test6();//test7();//test8();//test9();//test10();test11();return 0;
}
