您的位置：首页 > 新闻 > 资讯 > 浅谈【数据结构】链表之其他形态

浅谈【数据结构】链表之其他形态

2024/10/5 13:52:56 来源：https://blog.csdn.net/weixin_67526434/article/details/141502239  浏览:  次   关键词：浅谈【数据结构】链表之其他形态

目录

1、带头结点的链表

2、创建步骤

3、循环链表

3.1创建循环链表

3.2循环链表的遍历

3.3链表中的闭环

4、静态链表

4.1静态链表初始化

谢谢帅气美丽且优秀的你看完我的文章还要点赞、收藏加关注

没错，说的就是你，不用再怀疑！！！

希望我的文章内容能对你有帮助，一起努力吧！！！

1、带头结点的链表

引入：链表的操作起来比较舒服，但是如果记录（获取）链表长度比较麻烦。需要遍历链表，一个一个 计数，比较费时间（占CPU资源）

所以可以不可以用一个比较特殊一点的结点来保存链表相关的信息？->头结点

  • 头结点

头节点其实就是一个特殊的结点，它的类型和其他的结点不一样的，它是专门用来存储链表的一些属性 信息。

struct head {

        int length; // 链表长度

        结点类型*first; // 首结点地址

        结点类型*final; // 尾结点地址

};

注意：

  • 头节点不参与链表的长度计数
  • 头节点也是不参与链表遍历
  • 头节点也不会作为链表的结点

带头结点链表，头节点是在链表中存储链表信息的作用。

注意：当对链表进行增删操作的时候需要对头节点进行及时的更新。

2、创建步骤

  • 从无到有
    • 创建一个头结点
  • 从少到多
    • 一个一个正常增加（注意：及时更新头节点的信息）

图示：

***增加节点***

***删除节点(4种情况)***

代码示例：

#include <iostream>// 结点类型
struct node
{int data;struct node *next;
};// 头节点类型
struct head
{int length;struct node *first;struct node *final;
};/*@brief 创建链表@return 链表的头节点地址
*/
struct head *createNewList()
{// 申请一个空间struct head *newList = new struct head;// 初始化链表属性信息newList->length = 0;newList->first  = nullptr;newList->final  = nullptr;// 返回创建好的链表头节点地址return newList;
}/*@brief 头插法增加结点进链表@param list 需要增加结点的链表的地址@param data 新结点数据
*/
void addNodeHead(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 申请新结点空间struct node *newNode = new struct node;// 结点数据的初始化newNode->data = data;newNode->next = nullptr;// 开始头插法// 让新节点的next指针指向头节点里面的首结点newNode->next = list->first; // list->first 表示首结点地址// 更新头结点中首结点（first）和长度list->first = newNode; // 让newNode成为新的首结点list->length++;// 更新链表长度
}/*@brief 尾插法增加结点进链表@param list 需要增加结点的链表的地址@param data 新结点数据
*/
void addNodeTail(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 申请新结点空间struct node *newNode = new struct node;// 结点数据的初始化newNode->data = data;newNode->next = nullptr;// 进行尾插法增加list->final->next = newNode; // list->final 表示尾结点地址// 更新头结点中尾结点（final）和长度list->final = newNode;list->length++;
}/*@brief 删除一个置顶的结点@param list 需要删除结点的链表地址@param data 需要删除的那个结点的数据@return true表示成功，false表示失败
*/
bool delListNode(struct head*list,int data)
{// 先判断链表是否存在if(!list)return;// 遍历查找元素struct node *node_ptr = list->first;// 一个结点的时候if(list->first->data == data&&list->length == 1){// 直接释放空间delete list->first;// 更新首尾结点信息list->first = nullptr;list->final = nullptr;list->length--;return ;}// 判断是否为首结点且数量大于1if(list->first->data == data&&list->length > 1){// 更新首结点list->first = node_ptr->next; node_ptr->next = nullptr;delete node_ptr;list->length--;return true;}while(node_ptr->next){// 找到了需要删除的元素if(node_ptr->next->data == data){// 判断是不是尾结点且数量大于1if(node_ptr->next == list->final&&list->length > 1){// 更新尾结点list->final = node_ptr; // 释放需要删除的元素，再置空// 原因：node_ptr并非需要删除的元素，它是被删除元素的前一个元素。delete node_ptr->next;node_ptr->next = nullptr;list->length--;return true;}else if(list->length > 1){// 临时存储被删除元素的地址struct node *delNode = node_ptr->next;// 更新被被删除元素的next指针：实际就是跳过被删除元素node_ptr->next = node_ptr->next->next;// 断开被删除元素的链接delNode->next = nullptr;// 释放元素空间delete delNode;list->length--;return ;}}}
}

3、循环链表

循环链表：第一个数据结点和最后一个数据结点相连链表

循环单链表：最后一个数据结点往后就到了第一个数据结点

循环双链表：最后一个数据结点往后就到了第一个数据结点，第一个数据结点往前走就到了最后数据结 点

3.1创建循环链表

3.2循环链表的遍历

用两个指针，一个指针跑，另一个指针不动，当两个指针重叠的时候就跑完了。

代码示例：

#include <iostream>typedef struct node 
{int data;struct node *next;
}NodeType;/*@brief 为循环链表增加结点@param list 需要增加结点的循环链表@param data 新结点数据
*/
NodeType *addNewNode(NodeType *list,int data)
{// 如果为空作为第一个结点插入if(!list){list = new NodeType;list->data = data;// 自己指向自己，这个就是形成循环的关键了list->next = list;return list; }// 不是第一结点NodeType *newNode = new NodeType;newNode->data = data;newNode->next = nullptr;// 如果list指向的是最后加入链表结点(头插/尾插)newNode->next = list->next;list->next = newNode;return newNode;
}/*@brief 创建循环链表@return 返回新循环链表的地址
*/
NodeType *createLoopList()
{NodeType *loopList = nullptr;int data = -1;do{std::cin >> data;if(data == -1)break;// 增加结点loopList = addNewNode(loopList,data);}while(1);return loopList;
}/*@brief 打印循环链表
*/
void PrintLoopList(NodeType *looplist)
{if(!looplist){std::cout << "空的" << std::endl;return;}NodeType *node_ptr = looplist;do{std::cout << node_ptr->data << std::endl;node_ptr = node_ptr->next;}while(node_ptr != looplist);
}int main()
{NodeType*looplist = createLoopList();PrintLoopList(looplist);return 0;
}

3.3链表中的闭环

链表的尾结点指向了链表中的任意一个随机的结点

求闭环的算法

  • 使用两个指针
    • 一个移动步数快
    • 一个移动步数慢
  • 如果两者发生重叠 就形成闭环
  • 如果其中一个指针出现空指针的情况 ，就是没有环的

代码示例：

***形成闭环示例***

#include <iostream>typedef struct node 
{int data;struct node *next;
}NodeType;/*@brief 为循环链表增加结点@param list 需要增加结点的循环链表@param data 新结点数据
*/
NodeType *addNewNode(NodeType *list,int data)
{// 如果为空作为第一个结点插入if(!list){list = new NodeType;list->data = data;// 自己指向自己，这个就是形成循环的关键了list->next = list;return list; }// 不是第一结点NodeType *newNode = new NodeType;newNode->data = data;newNode->next = nullptr;// 如果list指向的是最后加入链表结点(头插/尾插)newNode->next = list->next;list->next = newNode;return newNode;
}/*@brief 创建循环链表@return 返回新循环链表的地址
*/
NodeType *createLoopList()
{NodeType *loopList = nullptr;int data = -1;do{std::cin >> data;if(data == -1)break;// 增加结点loopList = addNewNode(loopList,data);}while(1);return loopList;
}/*@brief 打印循环链表
*/
void PrintLoopList(NodeType *looplist)
{if(!looplist){std::cout << "空的" << std::endl;return;}NodeType *node_ptr = looplist;do{std::cout << node_ptr->data << std::endl;node_ptr = node_ptr->next;}while(node_ptr != looplist);
}/*求闭环的算法
*/
bool IsHaveCircle(NodeType *looplist)
{if(!looplist)return true;// 是否有圈NodeType *fast = looplist;    // 慢NodeType *slow = looplist;    // 快// 循环操作do{// 移动指针if(fast->next)fast = fast->next->next;   // 移动两步else  // 如果不能移动表示其中一个next是为空return false;slow = slow->next; // 移动一步// 判断有没有为空的指针if(!fast||!slow) // 只要任意一个指针为空那么就没有环return false;}while(fast != slow);// 相等退出，就是有环return true;
}int main()
{NodeType *looplist = createLoopList();if(IsHaveCircle(looplist))std::cout << "有环" << std::endl;elsestd::cout << "没环" << std::endl;// destoryList();return 0;
}

***无闭环示例***

/*无头结点的单链表
*/#include <iostream>/*结点类型
*/
typedef struct nodeData
{// 用来存储数据的空间（成员）称为：数据域int data;       // 用来保存其他结点的地址（关系）称为：指针域struct nodeData *next;
}NodeType;/*@brief:创建一个新链表@return:返回新链表的首结点的地址
*/
struct nodeData *createNewList()
{// 新链表的首结点指针struct nodeData *newList = nullptr;// 循环通过数据不断的去增加新结点到链表中while(1){int data = -1;// 通过键盘获取数据std::cin >> data;// 判断退出条件if(data == -1)break;// 申请了一个新结点的空间struct nodeData *newNode = new struct nodeData;newNode->data = data; // 将通过键盘获取到的数据存入结构体的数据域中newNode->next = nullptr; // 因为它是一个新结点，暂时是没有后继结点// 增加到链表里面:向后增加（尾插法）// 做第一次判断：链表中有没有结点if(newList == nullptr){// 如果newList是nullptr说明该链表里面为空，当前的新节点就是首届点newList = newNode;continue; // 继续增加新结点}// 搞一个临时指针，来指向首结点struct nodeData *node_ptr = newList;// 找尾结点while(node_ptr->next)node_ptr = node_ptr->next;// 到这个位置 node_ptr 此时指向的结点是尾结点// 就可以把newNode作为尾结点的后继结点添加到链表里面去了node_ptr->next = newNode;}return newList;
}// 打印链表（遍历方法）
void printList(struct nodeData *list)
{// 判断是不是空链表if(list == nullptr){std::cout << "链表为空" << std::endl;return;}std::cout << "List( ";// 如果不为空打印链表元素while(list) // 只要list不为空就一直循环{// list本来就可以表示首结点std::cout << list->data << " ";// 让list移动到下一个结点list = list->next;}std::cout << ")" << std::endl;
}bool IsHaveCircle(NodeType *looplist)
{if(!looplist)return true;// 是否有圈NodeType *fast = looplist;    // 慢NodeType *slow = looplist;    // 快// 循环操作do{// 移动指针if(fast->next)fast = fast->next->next;   // 移动两步else  // 如果不能移动表示其中一个next是为空return false;slow = slow->next; // 移动一步// 判断有没有为空的指针if(!fast||!slow) // 只要任意一个指针为空那么就没有环return false;}while(fast != slow);// 相等退出，就是有环return true;
}int main()
{// 不在栈空间里面申请结点空间// 创建一个链表struct nodeData *newList = createNewList();// 打印链表元素printList(newList); // 传入的值是newList存储的地址，并非newList自己的地址if(IsHaveCircle(newList))std::cout << "有环" << std::endl;elsestd::cout << "没环" << std::endl;return 0;
}

4、静态链表

静态链表是一种使用数组来实现链表概念的数据结构。它通过在每个元素中存储下一个元素的索引来实 现链式存储，从而在有限的空间内实现对大量元素的有效管理。

普通链表

struct node {

        int data;

        struct node *next;

}; // 结点

静态链表

struct node {

        int data;

        int next; // 不是指针，而是下标

};

struct node static_list[100]={0};

4.1静态链表初始化

for(int i = 0;i < 100;i ++)

{

        static_list[i].data = i+1;

        if(i!=99)

                static_list[i].next = i+1;

        else

                 static_list[i].next = -1; // 下标不会出现-1

}

插入元素

// 尾插法

int i = 0;

for(i < 100;i++)

if(static_list[i].next == -1)

        break;

// 找空位

for(int l = 0; l < 100;l++)

{

         if(static_list[l] == NULL)

         {

                static_list[l] = newNode;

                static_list[i].next = l;

        }

}

注意事项：

  • 静态链表是一种在内存空间有限时使用的数据结构。
  • 使用数组和指针来实现链表的功能。
  • 初始化静态链表时，需要正确设置每个节点的 data 和 next 指针。
  • 在向静态链表添加元素时，需要检查是否已满。
  • 访问静态链表元素时，要确保索引有效。
  • 静态链表的大小是固定的，因此在设计时需要合理估计最大元素数量。

代码实例：

#include <iostream>struct node
{int data;   // 数据int next_index; // 下标
};#define MAXLEN 20void addNode(struct node *staticlist[],int data)
{// 插入元素if(staticlist[0] == nullptr){staticlist[0] = new struct node;staticlist[0]->data = 1;staticlist[0]->next_index = -1;return;}std::cout << __LINE__ << std::endl;// 找尾元素插入int pos = 0; // 第一个while(1){if(staticlist[pos]->next_index == -1)break;pos = staticlist[pos]->next_index;}// 找到尾元素了int newPos = 0;while(staticlist[newPos] != nullptr)newPos++;// 将新结点加入staticlist[newPos] = new struct node;staticlist[newPos]->data = data;staticlist[newPos]->next_index = -1;staticlist[pos]->next_index = newPos;
}int main()
{// 新建一个静态链表struct node *staticlist[MAXLEN] = {0};for(int i = 0;i < 10;i++)addNode(staticlist,i+2);// 正常打印for(int i = 0;i < MAXLEN;i++)std::cout << staticlist[i] << " ";std::cout << std::endl;int pos = 0;// 链表遍历形式打印do{std::cout << staticlist[pos]->data << " ";pos =staticlist[pos]->next_index;} while (pos != -1);std::cout << std::endl;}

版权声明:

本网仅为发布的内容提供存储空间，不对发表、转载的内容提供任何形式的保证。凡本网注明“来源：XXX网络”的作品，均转载自其它媒体，著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处。

我们尊重并感谢每一位作者，均已注明文章来源和作者。如因作品内容、版权或其它问题，请及时与我们联系，联系邮箱：809451989@qq.com，投稿邮箱：809451989@qq.com

最新新闻

热搜词

使用A＊算法进行无人机路径规划的优化 企业的IT 建设的三个过程 美通企业周刊 | 中国平安将深度参与深圳公共住房建设；北京环球度假区将引入IMAX影院... 博达网站 学习 博达站群链接使用注意事项 人工智能未来10年神经网络的发展趋势

声明：本站所有新闻及新闻图片来源于其他网站，如有侵权，请及时联系我们！

客户服务 | 关于我们 | 版权声明

版权所有：

Copyright 2024 尧图网 All Rights Reserved.QQ:809451989