廊坊网站建设公司墨子,网页设计的毕业设计,苏州建设公司,国外自助建站系统目录
一、链表
1、链表的概念及结构
2、分类
二、实现单向链表
1、声明链表结构体
2、输出
3、头插尾插
4、头删尾删
5、查找
6、指定位置插入
7、删除指定节点
8、删除指定节点的后一个节点
9、单链表的销毁
完整版
LList.h
LList.c
text.c 一、链表 …目录
一、链表
1、链表的概念及结构
2、分类
二、实现单向链表
1、声明链表结构体
2、输出
3、头插尾插
4、头删尾删
5、查找
6、指定位置插入
7、删除指定节点
8、删除指定节点的后一个节点
9、单链表的销毁
完整版
LList.h
LList.c
text.c 一、链表 1、链表的概念及结构 概念链表是一种物理存储结构上非连续、非顺序的存储结构数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。 这张图生动形象地呈现了链表的结构。 如同高铁一般从头到尾一个连着一个。 2、分类 主要有两种类型的链表单向链表和双向链表。在 单向链表中每个节点包含一个数据元素和一个指向下一个节点的引用。而在 双向链表中每个节点有两个引用一个指向前一个节点另一个指向后一个节点。 从上图可看出链式结构在逻辑上是连续的但是在物理上不一定连续。现实中的结点一般都是从堆上申请出来的。从堆上申请的空间是按照一定的策略来分配的两次申请的空间可能连续也可能不连续 本次讲解基础的单向链表。 二、实现单向链表 我们创建三个文件 头文件LList.h用于调用库函数、声明结构体和函数。源文件LList.c存储函数。源文件text.c进行测试。 每个源文件都必须包含LList.h。 1、声明链表结构体
#include stdio.htypedef int SLTDataType;
typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;
将链表的数据类型用SLTDatatype这个别名代TT替int以后程序中使用到元素数据类型时都替换成SLTDatatype方便日后修改顺序表数据类型。将结构体struct SListNode定义别名为SLTNode。结构体成员data为链表节点数据数据类型是 SLTDataType。next表示一个指向同类型结构体的指针它指向单向链表下一个结点。
2、输出
void SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL) {printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
} 接收传入参数为结构体的地址结构体指针cur指向头结点phead循环遍历链表当cur不指向尾节点则打印输出当前节点数据cur指向下一个节点。cur指向尾节点打印NULL。
3、头插尾插
头插
void SLPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode BuyLTNode(x);newnode-next *pphead;*pphead newnode;
} 插入数据会修改头结点所以传入头结点指针的地址使用二级指针接收。assert判断传入头节点指针的地址是否合法为空则报错。需要包含头文件assert.h*pphead 不需要断言如果传入的链表为空也可以进行插入数据。 为新节点newnode开辟空间并将x储存其中因为后续经常用到开辟空间所以将这部分操作放入函数中。新节点newnode的next指针指向头结点*pphead头结点更新为newnode。 接下来讲解为新节点开辟空间的函数 BuyLTNode 新节点开辟空间
SLTNode* BuyLTNode(SLTDataType x)
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL) {perror(malloc fall);return;}newnode-data x;newnode-next NULL;return newnode;
}
为新节点开辟空间返回值为新节点的地址所以函数类型为 SLTNode* 结构体指针类型。malloc函数为newnode开辟结构体大小个字节。判断是否开辟成功失败则打印错误信息结束函数运行。将新节点的数据data赋值为传入参数 x。next赋值为空。
尾插
void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); SLTNode* newnode BuyLTNode(x);if (*pphead NULL){*pphead newnode;}else {SLTNode* tail *pphead;while (tail-next ! NULL)tail tail-next;tail-next newnode;}
} assert判断传入头节点指针的地址是否合法为空则报错。为新节点newnode开辟空间并将x储存其中。插入时分两种情况空链表 非空链表如果链表为空则直接将*pphead 指向新节点 newnode使其成为新的链表的头节点。如果链表不为空则创建变量tail指向头结点循环遍历链表使tail指向尾节点将新节点地址赋值给tail的next成功将新节点添加到链表尾部。
4、头删尾删
头删
void SLPopFront(SLTNode** pphead)
{assert(pphead); assert(*pphead);SLTNode* del *pphead;*pphead (*pphead)-next;free(del);
}
第一个assert判断传入头节点指针的地址是否合法为空则报错。第二个assert判断链表头节点是否为空为空无法删除则报错。定义变量del指向头节点以便稍后释放该节点的内存。头节点指向头节点的next也就是指向后一个节点。使用free函数释放del指向的已删除头节点空间。需要包含头文件stdlib.h
尾删
void SLPopBack(SLTNode** pphead)
{assert(pphead);assert(*pphead);if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;}else {SLTNode* tail *pphead;while (tail-next-next) {tail tail-next;}free(tail-next);tail-next NULL;}
}
第一个assert判断传入头节点指针的地址是否合法为空则报错。第二个assert判断链表头节点是否为空为空则报错。链表只有一个节点时直接释放头节点空间然后置空。链表有多个节点使通过循环使变量 tail-next 找到尾节点然后释放tail后一个节点的空间也就是尾节点的空间同时将其置空。
5、查找
SLTNode* STFind(SLTNode* phead, SLTDataType x)
{SLTNode* cur phead;while (cur) {if (cur-data x)return cur;cur cur-next;}return NULL;
} 函数在单链表中查找包含特定数据值 x 的节点。变量cur通过循环找到数据data等于x的节点。找到则返回指向当前节点的指针 cur否则返回值为空。
6、指定位置插入
指定位置之前 void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead pos){SLPushFront(pphead, x);}else {SLTNode* prev *pphead;while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuyLTNode(x);prev-next newnode;newnode-next pos;}
}
第一个assert判断传入头节点指针的地址是否合法为空则报错。第二个assert判断传入指向链表中某个节点的指针pos是否合法不存在则报错。如果在头节点位置之前插入则调用头插解决。如果不是头节点位置则创建一个指向链表头节点的指针 prev然后使用循环找到要插入位置 pos 前面的节点。 创建一个新的节点 newnode 并将数据值 x 存储在其中。 修改 prev 节点的 next 指针使其指向新节点 newnode从而将新节点插入到 pos 前面。 指定位置之后
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuyLTNode(x);newnode-next pos-next;pos-next newnode;
}assert判断传入指向链表中某个节点的指针pos是否合法不存在则报错。创建一个新的节点 newnode 并将数据值 x 存储在其中。newnode的next指针指向pos的后一项。pos的next指向新节点newnode。
7、删除指定节点
void SLErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(*pphead);if (pos *pphead){SLPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos) {prev prev - next;}prev-next pos-next;free(pos);}
}
第一个assert判断传入头节点指针的地址是否合法为空则报错。第二个assert判断链表头节点是否为空为空则报错。pos节点为头节点则调用头删解决。pos不为头节点则创建变量prev指向头节点通过循环找到pos节点的前一个节点。将prev的next指向要删除的pos节点的下一个节点。释放pos空间
8、删除指定节点的后一个节点
void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);SLTNode* next pos-next;pos-next next-next;free(next);
} 创建一个指向要删除的节点 pos 后面节点的指针 next以便稍后释放该节点的内存。 修改 pos 节点的 next 指针将其指向 next 的下一个节点从而绕过要删除的节点使链表不再包含它。 最后使用 free 函数释放 next 指向的节点的内存完成删除操作。
9、单链表的销毁
void SListDestroy(SLTNode* pphead)
{SLTNode* cur pphead;SLTNode* tmp NULL;while (cur ! NULL) {tmp cur;cur cur-next;free(tmp);}
}
定义了两个指针cur 和 tmp用于遍历链表并释放内存。开始时cur 被初始化为链表的头节点指针 pphead。 这是一个循环它会一直执行直到 cur 变为 NULL也就是遍历到链表的末尾。 在循环中首先将 cur 赋值给 tmp以便稍后释放 cur 指向的节点的内存。 然后将 cur 移动到下一个节点即 cur cur-next; 最后使用 free 函数释放 tmp 指向的节点的内存即释放链表中的一个节点接着进行循环依次释放节点直到链表最后。
完整版
LList.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 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);// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
void SLInsertAfter(SLTNode* pos, SLTDataType x);// 删除pos位置的值
void SLErase(SLTNode** pphead, SLTNode* pos);// 删除pos位置后面的值
void SLEraseAfter(SLTNode* pos);// 单链表的销毁
void SListDestroy(SLTNode* plist);
LList.c
#define _CRT_SECURE_NO_WARNINGS 1
#include LList.hvoid SLTPrint(SLTNode* phead)
{SLTNode* cur phead;while (cur ! NULL) {printf(%d-, cur-data);cur cur-next;}printf(NULL\n);
}SLTNode* BuyLTNode(SLTDataType x)//为新元素开辟空间
{SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));if (newnode NULL) {perror(malloc fall);return;}newnode-data x;newnode-next NULL;return newnode;
}void SLPushFront(SLTNode** pphead, SLTDataType x)//头插
{assert(pphead); // 链表为空pphead也不为空因为他是头指针plist的地址//assert(*pphead); // 不能断言链表为空也需要能插入SLTNode* newnode BuyLTNode(x);//newnode是局部变量newnode-next *pphead;//头插后首节点next指向原有的首节点*pphead newnode;//将链表的头指针 *pphead 指向新插入的节点
}void SLPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead); // 链表为空pphead也不为空因为他是头指针plist的地址SLTNode* newnode BuyLTNode(x);//两种情况//空链表 非空链表if (*pphead NULL)//链表为空改变结构体指针*pphead newnode;else {//不为空则改变结构体的节点SLTNode* tail *pphead;while (tail-next ! NULL)tail tail-next;tail-next newnode;}
}void SLPopFront(SLTNode** pphead)
{assert(pphead); // 链表为空pphead也不为空因为他是头指针plist的地址assert(*pphead); // 链表为空不能头删。当然你还可以用温柔的检查SLTNode* del *pphead;//指针del用于释放节点空间*pphead (*pphead)-next;free(del);
}void SLPopBack(SLTNode** pphead)
{assert(pphead); // 链表为空pphead也不为空因为他是头指针plist的地址assert(*pphead); // 链表为空不能头删。当然你还可以用温柔的检查//只有一个节点if ((*pphead)-next NULL) {free(*pphead);*pphead NULL;//修改头节点为空}else {//第一种增加前项变量//SLTNode* prev NULL;//SLTNode* tail *pphead;//while (tail-next) {// prev tail;// tail tail-next;//}//free(tail);//prev-next NULL;//第二种不新增变量//改变结构体的节点SLTNode* tail *pphead;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;
}// 在pos之前插入
void SLInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (*pphead pos){//在头节点前插入等于头插SLPushFront(pphead, x);}else {SLTNode* prev *pphead;//用于找到pos前的位置while (prev-next ! pos){prev prev-next;}SLTNode* newnode BuyLTNode(x);prev-next newnode;//pos前一个位置next指向新开辟节点newnode-next pos;//新节点next指向pos}
}// 在pos之后插入
void SLInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode BuyLTNode(x);//下面两行不能调换顺序否则无法链接新节点后项节点newnode-next pos-next;pos-next newnode;
}void SLErase(SLTNode** pphead, SLTNode* pos)// 删除pos位置的值
{assert(pphead);assert(*pphead);//链表为空则不能删除if (pos *pphead){SLPopFront(pphead);}else {SLTNode* prev *pphead;while (prev-next ! pos) {//找到pos前一个节点prev prev - next;}prev-next pos-next;//将pos前一个节点的next指向pos后一个节点free(pos);//释放pos空间}
}void SLEraseAfter(SLTNode* pos)
{assert(pos);assert(pos-next);//后项为空则不能删除SLTNode* next pos-next;pos-next next-next;free(next);
}void SListDestroy(SLTNode* pphead)
{SLTNode* cur pphead;SLTNode* tmp NULL;while (cur ! NULL) {tmp cur;cur cur-next;free(tmp);}
}
text.c
#define _CRT_SECURE_NO_WARNINGS 1#include LList.hvoid test1()
{SLTNode* plist NULL;SLPushFront(plist, 5);SLPushFront(plist, 4); SLPushFront(plist, 3);SLPushBack(plist, 6);//SLPopFront(plist);SLTNode* pos STFind(plist, 3);SLInsert(plist, pos, 99);//pos STFind(plist, 2);//if (pos)//{// SLInsertAfter(pos, 20);//}//SLPopBack(plist);//SLPopBack(plist);//SLPopBack(plist);//SLPopBack(plist);//SLPopBack(plist);SLTPrint(plist);
}int main()
{test1();return 0;
}
