单链表结构
头结点不存放数据, 开始存放数据的节点为开始节点.
带头结点的单链表相关操作
- /*
- * @file 单链表. cpp
- * @brief 单链表的创建及其相关操作
- * @author linzijie
- * @platform Ubuntu 16.04 gcc version 5.4.0
- * @date 2019/11/9
- */
- #include <iostream>
- #include <vector>
- using namespace std;
- // 单链表节点存储的数据类型定义
- typedef int ElemType;
- // 单链表结构体定义如下
- typedef struct LNode
- {
- ElemType data;
- struct LNode * next;
- }LinkList;
- /*
- * @brief 头插法建立单链表
- * @param list 单链表头结点指针的引用
- * datas 需要放入节点的数据
- * @note list 指针为空, 建立时初始化, 头结点不保存数据
- * 采用头插法, 数据的顺序与 datas 相反
- * 动态申请内存空间, 需要调用 DestroyLinkList 函数手动销毁
- * @Sample LinkList *list = nullptr;
- * vector<ElemType> datas{1, 2, 3, 4, 5};
- * CreateLinkListF(list, datas);
- */
- void CreateLinkListF(LinkList *&list,
- vector<ElemType>& datas)
- {
- list = new LinkList;
- list->next = nullptr;
- LinkList *tmp = nullptr;
- for(auto iter = datas.begin();
- iter != datas.end(); iter++)
- {
- tmp = new LinkList;
- tmp->data = (*iter);
- tmp->next = list->next;
- list->next = tmp;
- }
- }
- /*
- * @brief 尾插法建立单链表
- * @param list 单链表头结点指针的引用
- * datas 需要放入节点的数据
- * @note list 指针为空, 建立时初始化, 头结点不保存数据
- * 采用尾插法, 数据的顺序与 datas 一致
- * 动态申请内存空间, 需要调用 DestroyLinkList 函数手动销毁
- * @Sample LinkList *list = nullptr;
- * vector<ElemType> datas{1, 2, 3, 4, 5};
- * CreateLinkListR(list, datas);
- */
- void CreateLinkListR(LinkList *&list,
- vector<ElemType>& datas)
- {
- list = new LinkList;
- list->next = nullptr;
- LinkList *tmp = nullptr;
- LinkList *now = list;
- for(auto iter = datas.begin();
- iter != datas.end(); iter++)
- {
- tmp = new LinkList;
- tmp->data = (*iter);
- now->next = tmp;
- now = tmp;
- }
- now->next = nullptr;
- }
- /*
- * @brief 打印单链表
- * @param list 单链表头结点指针的引用
- * @note 头结点不保存数据, 所以不打印头结点
- * @Sample PrintLinkList(list)
- */
- void PrintLinkList(LinkList *list)
- {
- LinkList *ptr = list;
- // 头结点不放数据
- if (ptr != nullptr)
- ptr = ptr->next;
- while(ptr != nullptr)
- {
- cout <<ptr->data <<" ";
- ptr = ptr->next;
- }
- cout <<endl;
- }
- /*
- * @brief 销毁单链表
- * @param list 单链表头结点指针的引用
- * @note 销毁动态申请的内存空间, 防止内存泄露
- * @Sample DestroyLinkList(list)
- */
- void DestroyLinkList(LinkList *& list)
- {
- LinkList *now = list;
- LinkList *next = list->next;
- while(next != nullptr)
- {
- delete(now);
- now = next;
- next = now->next;
- }
- delete(now);
- }
- /*
- * @brief 单链表的数据插入
- * @param list 单链表头结点指针的引用
- * data 需要插入的数据
- * index 需要插入的位置
- * @note index 从 1 开始, 插入成功返回真, 插入错误返回假
- * @Sample ElemType data = 12;
- * int index = 2;
- * InsertData(list, data, index);
- */
- bool InsertData(LinkList *& list, ElemType data,
- int index)
- {
- int count = 1;
- LinkList *iter = list;
- while(iter != nullptr)
- {
- if(count == index)
- {
- LinkList *node = new LinkList;
- node->data = data;
- node->next = iter->next;
- iter->next = node;
- return true;
- }
- else
- {
- iter = iter->next;
- count++;
- }
- }
- return false;
- }
- /*
- * @brief 单链表的数据删除
- * @param list 单链表头结点指针的引用
- * index 需要删除的位置
- * @note index 从 1 开始, 删除成功返回真, 删除错误返回假
- * @Sample int index = 2;
- * IDeleteData(list, index);
- */
- bool DeleteData(LinkList *& list, int index)
- {
- int count = 1;
- LinkList *iter = list;
- while(iter != nullptr)
- {
- if(count == index)
- {
- LinkList *tmp = iter->next;
- iter->next = iter->next->next;
- delete(tmp);
- return true;
- }
- else
- {
- iter = iter->next;
- count++;
- }
- }
- return false;
- }
- /*
- * @brief 单链表按位置查找元素值
- * @param list 单链表头结点指针的引用
- * index 需要定位的元素位置
- * elem 获取的元素值存放的对象
- * @note index 从 1 开始, 定位成功返回真, 并且值保存在 elem 中, 定位失败返回假
- * @Sample GetElem(list, 1, elem);
- */
- bool GetElem(LinkList *& list, int index, ElemType &elem)
- {
- LinkList *iter = list;
- if(iter != nullptr)
- iter = iter->next;
- int count = 1;
- while(iter != nullptr)
- {
- if(index == count)
- {
- elem = iter->data;
- return true;
- }
- else
- {
- iter = iter->next;
- count++;
- }
- }
- return false;
- }
- /*
- * @brief 单链表根据值定位节点
- * @param list 单链表头结点指针的引用
- * elem 元素值的引用
- * result 保存定位到的 LinkList 指针
- * @note index 从 1 开始, 定位成功返回真, 并且值存放在 result 中, 定位失败返回假
- * result 需清空后进行存放
- * @Sample LocateElem(list, elem, result);
- */
- bool LocateElem(LinkList *& list, const ElemType &elem,
- vector<LinkList*>& result)
- {
- LinkList *iter = list;
- if(iter != nullptr)
- iter = iter->next;
- result.clear();
- while(iter != nullptr)
- {
- if(iter->data == elem)
- {
- result.push_back(iter);
- }
- iter = iter->next;
- }
- return !result.empty();
- }
- /*
- * @brief 获取单链表节点数
- * @param list 单链表头结点指针的引用
- * @note 节点数包含头结点 (未存放值的节点)
- * @Sample int length = GetLinkListLength(list);
- */
- int GetLinkListLength(LinkList *& list)
- {
- int length = 0;
- LinkList *iter = list;
- while(iter != nullptr)
- {
- length++;
- iter = iter->next;
- }
- return length;
- }
来源: http://www.bubuko.com/infodetail-3279645.html