[数据结构]线性表之单链表的类模板实现

2024-09-08 08:08

本文主要是介绍[数据结构]线性表之单链表的类模板实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

类的具体实现如下:


/
#include"LinearList.h"
#include <iostream>
#include <cstdlib>
using namespace std;template<class T>
struct LinkNode //链表节点类
{T data;LinkNode<T>* link;LinkNode(LinkNode<T>* ptr=NULL):link(ptr){}LinkNode(const T& item,LinkNode<T>* ptr=NULL):data(item),link(ptr){}
};template<class T>
class List  //class List:public LinearList<T> 使用继承,有诸多问题
{
protected:LinkNode<T>* first;
public:List():first(new LinkNode<T>){}List(const T& item):first(new LinkNode<T>(item)){}List(const List& L);~List(){makeEmpty();delete first;}void makeEmpty();   //新增成员int Size()const{return 0;}   //空实现,这里没有实际意义int Length()const;LinkNode<T>* getHead()const{return first;}  //新增成员LinkNode<T>* Search(T& x)const;             //这2个与基类相比,返回值不同.不能进行覆盖。说明在继承类中,若基类函数和继承类函数的返回值不同,视为不同的函数,不能同名覆盖,相当于重载LinkNode<T>* Locate(int i)const;bool getData(int i,T& x)const;void setData(int i,T& x);bool Insert(int i,T& x);bool Remove(int i,T& x);bool IsEmpty()const{return (first->link==NULL)?true:false;}bool IsFull()const{return false;}void Sort(){};  //未实现void output();void inputFront(T endTag);void inputRear(T endTag);List<T>& operator=(const List<T>& L);
};template<class T>
List<T>::List(const List& L)
{LinkNode<T>* src=L.first->link;LinkNode<T>* dest=first=new LinkNode<T>;while(src!=NULL){dest->link=new LinkNode<T>(src->data);dest=dest->link;src=src->link;}//dest->link=NULL;
}template<class T>
List<T>& List<T>::operator=(const List<T>& L)
{LinkNode<T>* src=L.first->link;LinkNode<T>* dest=first=new LinkNode<T>;while(src!=NULL){dest->link=new LinkNode<T>(src->data);dest=dest->link;src=src->link;}//dest->link=NULL;return *this;
}template<class T>
void List<T>::makeEmpty()//删除了除头结点以外的所有节点,有头结点内存泄露的问题
{LinkNode<T>* del;while(first->link!=NULL){del=first->link;first->link=del->link;delete del;}
}template<class T>
int List<T>::Length()const
{int count=0;LinkNode<T>*  current=first->link;while(current!=NULL){++count;current=current->link;}return count;
}template<class T>
LinkNode<T>* List<T>::Search(T& x)const
{LinkNode<T>* current=first->link;while(current!=NULL&¤t->data!=x){current=current->link;}return current;
}template<class T>
LinkNode<T>* List<T>::Locate(int i)const
{LinkNode<T>* current=first->link;if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}int k=1;while(current!=NULL&&k<i){current=current->link;++k;}return current;
}template<class T>
bool List<T>::getData(int i,T& x)const
{if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}LinkNode<T>* current=Locate(i);if(current!=NULL){x=current->data;return true;}else{return false;}
}template<class T>
void List<T>::setData(int i,T& x)
{if(i<1||i>Length()){cerr<<"err"<<endl;exit(1);}LinkNode<T>* current=Locate(i);if(current!=NULL){current->data=x;}else{cerr<<"err"<<endl;exit(1);}
}template<class T>
bool List<T>::Insert(int i,T& x)
{LinkNode<T>* current=first;if(i<0||i>Length()){cerr<<"err"<<endl;exit(1);}int k=0;while(current!=NULL&&k<i){++k;current=current->link;}LinkNode<T>* newNode=new LinkNode<T>(x);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=current->link;current->link=newNode;return true;
}template<class T>
bool List<T>::Remove(int i,T& x)
{LinkNode<T> *current=first,*del;if(i<=0||i>Length()){cerr<<"err"<<endl;exit(1);}int k=0;while(current!=NULL&&k<i-1){++k;current=current->link;}del=current->link;current->link=del->link;x=del->data;delete del;return true;
}template<class T>
void List<T>::output()
{LinkNode<T>* current=first->link;while(current!=NULL){cout<<"# :"<<current->data<<" ";current=current->link;}cout<<endl;
}template<class T>
void List<T>::inputFront(T endTag)
{LinkNode<T>* newNode;T val;makeEmpty();cin>>val;while(val!=endTag){newNode=new LinkNode<T>(val);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=first->link;first->link=newNode;cin>>val;}
}template<class T>
void List<T>::inputRear(T endTag)
{LinkNode<T> *newNode,*last;T val;makeEmpty();last=first;cin>>val;while(val!=endTag){newNode=new LinkNode<T>(val);if(newNode==NULL){cerr<<"err"<<endl;exit(1);}newNode->link=last->link;last->link=newNode;last=newNode;cin>>val;}
}

测试程序如下:


int main(int argc, char* argv[])
{int val1=10;List<int> L1;List<int> L2(val1);cout<<"getHead(): "<<L1.getHead()->data<<endl;cout<<"getHead(): "<<L2.getHead()->data<<endl;int endTag=-1;L1.inputRear(endTag);L1.output();cout<<"Length(): "<<L1.Length()<<endl;int data=111,data1;LinkNode<int>* ptr=L1.Locate(2);cout<<"Locate: "<<ptr->data<<endl;L1.setData(2,data);L1.getData(2,data1);cout<<"getData(): "<<data1<<endl;int val2=3;ptr=L1.Search(val2);cout<<"Search(): "<<ptr->data<<endl;int data3=33;L1.Remove(3,val2);L1.Insert(3,data3);L1.output();List<int> L3(L1);L3.output();List<int> L4;L4=L1;L4.output();//L2.inputFront(endTag);// L2.output();//L2.makeEmpty();//L2.output();system("pause");return 0;
}


测试结果如下:

getHead(): -842150451
getHead(): 10
1 2 3 4 5 6 7 8 9 -1
# :1 # :2 # :3 # :4 # :5 # :6 # :7 # :8 # :9
Length(): 9
Locate: 2
getData(): 111
Search(): 3
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
# :1 # :111 # :4 # :33 # :5 # :6 # :7 # :8 # :9
请按任意键继续. . .


注意事项:

1。采用附加头结点的单链表的实现方法。可以统一插入和删除操作,从而不用区分是否是在第一个节点(或者空表)或者是其他位置处插入或者删除。

2.可以采用继承LinearList基类的方法生成派生类,但是实现比较复杂,没有必要。因为要完全覆盖基类纯虚函数的接口。

3.在继承体系结构中,即使只有返回值不同。也当作不同的函数,是不能同名覆盖的,相当于函数的重载。

4.遍历链表是要用一个current指针来遍历,让他指向不同的节点。如果有两个链表至少需要定义两个这样的指针来遍历。

5.删除节点时,需要用del指针保存要删除的节点,最后在删除。删除时当前指正指向前一个节点,插入时当期指针指向要插入的位置。

6.写程序时多画图,想清楚了在动手。可以适当举例验证。




这篇关于[数据结构]线性表之单链表的类模板实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1147576

相关文章

Spring Boot配置和使用两个数据源的实现步骤

《SpringBoot配置和使用两个数据源的实现步骤》本文详解SpringBoot配置双数据源方法,包含配置文件设置、Bean创建、事务管理器配置及@Qualifier注解使用,强调主数据源标记、代... 目录Spring Boot配置和使用两个数据源技术背景实现步骤1. 配置数据源信息2. 创建数据源Be

在MySQL中实现冷热数据分离的方法及使用场景底层原理解析

《在MySQL中实现冷热数据分离的方法及使用场景底层原理解析》MySQL冷热数据分离通过分表/分区策略、数据归档和索引优化,将频繁访问的热数据与冷数据分开存储,提升查询效率并降低存储成本,适用于高并发... 目录实现冷热数据分离1. 分表策略2. 使用分区表3. 数据归档与迁移在mysql中实现冷热数据分

linux批量替换文件内容的实现方式

《linux批量替换文件内容的实现方式》本文总结了Linux中批量替换文件内容的几种方法,包括使用sed替换文件夹内所有文件、单个文件内容及逐行字符串,强调使用反引号和绝对路径,并分享个人经验供参考... 目录一、linux批量替换文件内容 二、替换文件内所有匹配的字符串 三、替换每一行中全部str1为st

SpringBoot集成MyBatis实现SQL拦截器的实战指南

《SpringBoot集成MyBatis实现SQL拦截器的实战指南》这篇文章主要为大家详细介绍了SpringBoot集成MyBatis实现SQL拦截器的相关知识,文中的示例代码讲解详细,有需要的小伙伴... 目录一、为什么需要SQL拦截器?二、MyBATis拦截器基础2.1 核心接口:Interceptor

SpringBoot集成EasyPoi实现Excel模板导出成PDF文件

《SpringBoot集成EasyPoi实现Excel模板导出成PDF文件》在日常工作中,我们经常需要将数据导出成Excel表格或PDF文件,本文将介绍如何在SpringBoot项目中集成EasyPo... 目录前言摘要简介源代码解析应用场景案例优缺点分析类代码方法介绍测试用例小结前言在日常工作中,我们经

基于Python实现简易视频剪辑工具

《基于Python实现简易视频剪辑工具》这篇文章主要为大家详细介绍了如何用Python打造一个功能完备的简易视频剪辑工具,包括视频文件导入与格式转换,基础剪辑操作,音频处理等功能,感兴趣的小伙伴可以了... 目录一、技术选型与环境搭建二、核心功能模块实现1. 视频基础操作2. 音频处理3. 特效与转场三、高

Python实现中文文本处理与分析程序的示例详解

《Python实现中文文本处理与分析程序的示例详解》在当今信息爆炸的时代,文本数据的处理与分析成为了数据科学领域的重要课题,本文将使用Python开发一款基于Python的中文文本处理与分析程序,希望... 目录一、程序概述二、主要功能解析2.1 文件操作2.2 基础分析2.3 高级分析2.4 可视化2.5

Java实现预览与打印功能详解

《Java实现预览与打印功能详解》在Java中,打印功能主要依赖java.awt.print包,该包提供了与打印相关的一些关键类,比如PrinterJob和PageFormat,它们构成... 目录Java 打印系统概述打印预览与设置使用 PageFormat 和 PrinterJob 类设置页面格式与纸张

使用Go实现文件复制的完整流程

《使用Go实现文件复制的完整流程》本案例将实现一个实用的文件操作工具:将一个文件的内容完整复制到另一个文件中,这是文件处理中的常见任务,比如配置文件备份、日志迁移、用户上传文件转存等,文中通过代码示例... 目录案例说明涉及China编程知识点示例代码代码解析示例运行练习扩展小结案例说明我们将通过标准库 os

Python实现终端清屏的几种方式详解

《Python实现终端清屏的几种方式详解》在使用Python进行终端交互式编程时,我们经常需要清空当前终端屏幕的内容,本文为大家整理了几种常见的实现方法,有需要的小伙伴可以参考下... 目录方法一:使用 `os` 模块调用系统命令方法二:使用 `subprocess` 模块执行命令方法三:打印多个换行符模拟