严蔚敏 《数据结构》第二章线性表 2.3节线性表的链式表示 C++实现

本文主要是介绍严蔚敏 《数据结构》第二章线性表 2.3节线性表的链式表示 C++实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

严蔚敏 《数据结构》第二章线性表 2.3节线性表的链式表示 C++实现

代码没有怎么测试过,可能有些地方有BUG

// link_list.h
// By Envirian
#ifndef LINK_LIST_H_
#define LINK_LIST_H_
#include <iostream>
using std::cin;
using Status         = int;  // 返回值类型
const int TRUE       = 1;
const int FALSE      = 0;
const int OK         = 1;
const int ERROR      = 0;
const int INFEASIBLE = -1;
using ElemType       = int;  // 数据项类型
// LinkList为带头节点的单链表,第0个元素不储存信息,第1个元素开始储存信息
// 使用之前必须先调用InitList()!!!!!
class LinkList {
private:struct LNode{ElemType data;LNode* next{nullptr};};public:// 以下是P37到P38的函数Status InitList(){// 构造一个空的线性链表if (head_)return ERROR;  // 已经存在线性链表了head_ = new LNode;tail_ = nullptr;len_  = 0;return OK;}Status DestroyList(){// 销毁线性链表,使其回到InitList()之前的状态,并释放空间if (!head_)return OK;LNode* p = head_;// 回到初始化之前状态head_ = tail_ = nullptr;len_          = 0;// 释放空间LNode* q = p->next;while (p) {delete p;p = q;q = p->next;}return OK;}Status ClearList(){// 将线性链表重置为初始化后的空表DestroyList();if (!InitList())return ERROR;return OK;}Status InsFirst(const ElemType& e){// 把e插入到链表头部if (!ListInsert(1, e))return ERROR;return OK;}Status DelFirst(ElemType& e){// 删除链表的第一个节点并以e返回if (!ListDelete(1, e))return ERROR;return OK;}Status InsLast(const ElemType& e){if (!ListInsert(len_ + 1, e))return ERROR;return OK;}Status DelLast(ElemType& e){// 删除链表的尾节点并以e返回if (!ListDelete(len_, e))return ERROR;return OK;}Status GetHead(ElemType& e){// 获取第一个元素,用e返回if (!head_->next)return ERROR;e = head_->next->data;return OK;}Status GetBack(ElemType& e){// 获取最后一个元素,用e返回if (!tail_)return ERROR;e = tail_->data;return OK;}Status ListEmpty(){// 若链表为空表,则返回TRUE,否则返回FALSEif (len_ == 0)return TRUE;return FALSE;}int ListLength(){// 返回线性表中的元素个数return len_;}// 以下是P29到P31的函数Status GetElem(int i, ElemType& e){// 当第i个元素存在时,其值赋给e并返回OK,否则返回ERRORLNode* p = head_->next;int ctr  = 1;           // 初始化,p指向第一个节点,ctr为计数器while (p && ctr < i) {  // 顺指针向后查找,直到p指向第i个元素或p为空p = p->next;++ctr;}if (!p || ctr > i)return ERROR;  // 第i个元素不存在e = p->data;       // 取第i个元素return OK;}Status ListInsert(int i, const ElemType& e){// 在带头结点的单链线性表中第i个位置之前插入元素eLNode* p = head_;int ctr  = 0;while (p && ctr < i - 1) {  // 寻找i-1个节点p = p->next;++ctr;}if (!p || ctr > i - 1)return ERROR;      // i大于表长加1或i小于1LNode* s = new LNode;  // 生成新节点s->data  = e;          // 赋值if (p->next == nullptr)tail_ = s;      // 如果是插入后成为最后一个节点,更新尾节点s->next = p->next;  // 插入L中,注意顺序p->next = s;++len_;return OK;}Status ListDelete(int i, ElemType& e){// 在带头结点的单链线性表L中,删除第i个元素,并由e返回其值LNode* p = head_;int ctr  = 0;while (p->next && ctr < i - 1) {// 寻找第i个节点并令p指向其前驱p = p->next;++ctr;}if (!p->next || ctr > i - 1)return ERROR;  // 删除位置不合理if (!p->next->next)tail_ = p;       // 如果要删除的是尾节点,那么更新尾节点LNode* q = p->next;  // 删除并释放节点p->next  = q->next;e        = q->data;delete q;--len_;return OK;}Status CreateList(int n){// 逆位序输入n个元素的值,建立带表头结点的单链线性表(头插法)if (head_)return ERROR;  // 单链线性表非空// TODO(@Envirian): 等写了清空操作之后把这里改写成先清空head_ = new LNode;  // 建立带头结点for (int i = 0; i < n; ++i) {LNode* p = new LNode;  // 生成新节点cin >> (p->data);if (i == 0)tail_ = p;              // 第一个插入的节点也是尾节点p->next     = head_->next;  // 放到表头head_->next = p;}return OK;}private:LNode* head_{nullptr};  // 头节点LNode* tail_{nullptr};  // 尾节点int len_{0};            // 线性表中数据元素的个数
};#endif

这篇关于严蔚敏 《数据结构》第二章线性表 2.3节线性表的链式表示 C++实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075574

相关文章

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<

C++包装器

包装器 在 C++ 中,“包装器”通常指的是一种设计模式或编程技巧,用于封装其他代码或对象,使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍,可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型: 1. 函数包装器 函数包装器用于封装一个或多个函数,使其接口更统一或更便于调用。例如,std::function 是一个通用的函数包装器,它可以存储任意可调用对象(函数、函数

C++11第三弹:lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页: 南桥几晴秋 🌈C++专栏: 南桥谈C++ 🌈C语言专栏: C语言学习系列 🌈Linux学习专栏: 南桥谈Linux 🌈数据结构学习专栏: 数据结构杂谈 🌈数据库学习专栏: 南桥谈MySQL 🌈Qt学习专栏: 南桥谈Qt 🌈菜鸡代码练习: 练习随想记录 🌈git学习: 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo

06 C++Lambda表达式

lambda表达式的定义 没有显式模版形参的lambda表达式 [捕获] 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 有显式模版形参的lambda表达式 [捕获] <模版形参> 模版约束 前属性 (形参列表) 说明符 异常 后属性 尾随类型 约束 {函数体} 含义 捕获:包含零个或者多个捕获符的逗号分隔列表 模板形参:用于泛型lambda提供个模板形参的名