网站建设制作 南京公司哪家好,启业网查询官网,沈阳网站搜索排名,公路局网站建设方案目录
1.链表的基本概念及结构
1.1基本概念
1.2结构
2.链表的分类
3.链表的实现#xff08;循环链表增删查改实现#xff09; 1.动态申请节点#xff08;结点#xff09;编辑
2.单链表打印
3.单链表尾插
4.单链表头插
5.单链表尾删
6.单链表头删
7.单链表查找 …目录
1.链表的基本概念及结构
1.1基本概念
1.2结构
2.链表的分类
3.链表的实现循环链表增删查改实现 1.动态申请节点结点编辑
2.单链表打印
3.单链表尾插
4.单链表头插
5.单链表尾删
6.单链表头删
7.单链表查找
8.在指定位置之前插入数据
9.在指定位置之后插入数据
10.删除pos节点
11.删除pos之后的节点
12.销毁链表 1.链表的基本概念及结构 链表是一种常见的基础数据结构它由一系列节点Node组成每个节点包含数据和到下一个节点的引用指针。以下是链表的基本概念及其结构
1.1基本概念 节点Node链表的基本单元每个节点包含两部分一部分是存储数据的域称为数据域另一部分是存储下一个节点地址的域称为指针域或链接域。 头节点Head链表的第一个节点通常用于表示整个链表。 尾节点Tail链表的最后一个节点其指针域通常指向NULL表示链表的结束。 链表的长度链表中节点的数量。 链表的遍历按照节点间的链接顺序访问链表中的每个节点。 动态性链表的大小不是固定的可以在运行时动态地增加或减少节点。
1.2结构 在C语言中链表节点通常使用结构体struct来定义。以下是链表节点的一个基本结构 链表的结构就像是火车一样一节一节的连在一起。 但是每个节点的地址并不像顺序表一样是连续的而是随机存储的因此每个节点才需要下一个节点的地址来找到下一节点。 2.链表的分类 单向链表Singly Linked List: 每个节点包含一个数据域和一个指向下一个节点的指针。遍历链表只能从头节点开始并且只能向一个方向进行。 双向链表Doubly Linked List: 每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。可以从两个方向遍历链表。 循环链表Circular Linked List: 单向链表的变种最后一个节点的指针指向头节点形成一个环。可以从任意节点开始遍历整个链表。 双向循环链表Doubly Circular Linked List: 双向链表的变种头节点的前一个指针指向最后一个节点最后一个节点的下一个指针指向头节点形成一个环。可以从任意节点开始向前或向后遍历整个链表。
3.链表的实现循环链表增删查改实现 1.动态申请节点结点 SLTNode* newnode (SLTNode*)malloc(sizeof(SLTNode));使用malloc函数动态分配一个SLTNode大小的内存块并将其强制转换为SLTNode*类型的指针。sizeof(SLTNode)获取SLTNode结构体的大小。 if (newnode NULL)检查malloc是否成功分配了内存。如果newnode是NULL说明内存分配失败。 perror(malloc fail!);如果内存分配失败使用perror函数打印错误消息。 exit(1);如果内存分配失败终止程序执行返回错误代码1。 newnode-data x;将传入的参数x赋值给新节点的数据域。 newnode-next NULL;将新节点的指针域初始化为NULL表示当前节点后面没有其他节点。 return newnode;返回新创建的节点。 2.单链表打印 3.单链表尾插 assert(pphead);使用assert宏来确保传入的头节点指针的指针不是NULL。如果pphead是NULL程序将终止执行。 SLTNode* newnode SLTBuyNode(x);调用之前定义的SLTBuyNode函数来创建一个新的节点并将数据x存储在新节点的数据域。 if (*pphead NULL)检查链表是否为空。如果链表为空即头节点指针为NULL则将新节点设置为头节点。 else如果链表不为空则需要找到链表的最后一个节点。 SLTNode* ptail *pphead;初始化一个指针ptail指向头节点。 while (ptail-next)遍历链表直到找到最后一个节点即节点的next指针为NULL。 ptail ptail-next;在循环中将ptail移动到下一个节点。 ptail-next newnode;当找到最后一个节点时将其next指针指向新创建的节点从而将新节点添加到链表的末尾。
4.单链表头插 assert(pphead);使用assert宏来确保传入的pphead不是NULL。如果pphead是NULL程序将在这里终止。 SLTNode* newnode SLTBuyNode(x);调用SLTBuyNode函数创建一个新的节点并将数据x存储在新节点的数据域中。 newnode-next *pphead;将新节点的next指针指向原来的头节点。这一步是为了将新节点插入到链表的头部。 *pphead newnode;更新头节点指针使其指向新创建的节点。这样新节点就成为了链表的新头部。
5.单链表尾删 这个接口的实现一开始先要判断链表是否为单节点链表如果是则直接释放头节点不是则进行相应的操作。 assert(pphead *pphead);使用assert宏来确保传入的pphead不是NULL且链表不为空。如果这些条件不满足程序将在这里终止。 if ((*pphead)-next NULL)检查链表是否只有一个节点。如果是直接释放这个节点并将头节点指针设置为NULL。 else如果链表有多个节点需要遍历链表找到最后一个节点。 while (ptail-next)遍历链表直到ptail指向最后一个节点。 free(ptail);释放最后一个节点的内存。 ptail NULL;将ptail指针设置为NULL防止野指针。 prev-next NULL;将倒数第二个节点的next指针设置为NULL断开与已删除节点的连接。
6.单链表头删 这里的(*pphead)-next不能写成*pphead-next 因为-预算符优先级是高于*的。 assert(pphead *pphead);使用assert宏来确保传入的pphead不是NULL且链表不为空。如果这些条件不满足程序将在这里终止。 SLTNode* next (*pphead)-next;保存头节点的下一个节点指针。这是因为一旦释放头节点我们就无法访问链表的其余部分。 free(*pphead);释放头节点的内存。 *pphead next;更新头节点指针使其指向原来的第二个节点现在成为新的头节点。
7.单链表查找 assert(phead);使用assert宏来确保传入的phead不是NULL。如果phead是NULL程序将在这里终止。 SLTNode* plist phead;初始化一个指针plist使其指向头节点。 while (plist)开始循环当plist不为NULL时继续执行。 if (plist-data x)检查当前节点的数据是否与要查找的值x匹配。 return plist;如果找到匹配的节点返回该节点。 plist plist-next;如果没有找到匹配的节点移动plist到下一个节点。 return NULL;如果在链表中没有找到匹配的节点返回NULL。
8.在指定位置之前插入数据 9.在指定位置之后插入数据 assert(pphead *pphead);使用assert宏来确保传入的pphead不是NULL且链表不为空。如果这些条件不满足程序将在这里终止。 assert(pos);使用assert宏来确保传入的pos不是NULL。如果pos是NULL程序将在这里终止。 SLTNode* newnode SLTBuyNode(x);调用SLTBuyNode函数创建一个新的节点并将数据x存储在新节点的数据域中。 if (pos *pphead)检查插入的位置是否是头节点。如果是使用SLTPushFront函数在头节点位置插入新节点。 else如果插入的位置不是头节点需要找到pos的前一个节点。 SLTNode* prev *pphead;初始化prev指针指向头节点。 while (prev-next ! pos)遍历链表直到找到pos的前一个节点。 newnode-next pos;将新节点的next指针指向pos。 prev-next newnode;将pos的前一个节点的next指针指向新节点。
10.删除pos节点 assert(pphead *pphead);使用assert宏来确保传入的pphead不是NULL且链表不为空。如果这些条件不满足程序将在这里终止。 assert(pos);使用assert宏来确保传入的pos不是NULL。如果pos是NULL程序将在这里终止。 if (pos *pphead)检查要删除的节点是否是头节点。如果是使用SLTPopFront函数执行头删操作。 else如果要删除的节点不是头节点需要找到该节点的前一个节点。 SLTNode* prev *pphead;初始化prev指针指向头节点。 while (prev-next ! pos)遍历链表直到找到pos的前一个节点。 prev-next pos-next;将pos的前一个节点的next指针指向pos的下一个节点完成删除操作。 free(pos);释放pos节点的内存。 pos NULL;将pos指针设置为NULL防止野指针。
11.删除pos之后的节点 assert(pos);使用assert宏来确保传入的pos不是NULL。如果pos是NULL程序将在这里终止。 SLTNode* newnode SLTBuyNode(x);调用SLTBuyNode函数创建一个新的节点并将数据x存储在新节点的数据域中。 newnode-next pos-next;将新节点的next指针指向pos的下一个节点这样新节点就位于pos的后面。 pos-next newnode;将pos的next指针指向新节点完成新节点的插入操作。
12.销毁链表 assert(pphead *pphead);使用assert宏来确保传入的pphead不是NULL且链表不为空。如果这些条件不满足程序将在这里终止。 SLTNode* pcur *pphead;初始化一个指针pcur使其指向头节点。 while (pcur)开始循环当pcur不为NULL时继续执行。 SLTNode* next pcur-next;保存pcur的下一个节点的指针因为pcur将被释放。 free(pcur);释放pcur节点的内存。 pcur next;移动pcur指针到下一个节点。 *pphead NULL;循环结束后将头指针设置为NULL表示链表已被销毁。
