用类模板封装链表

2024-09-07 08:08
文章标签 模板 链表 封装 用类

本文主要是介绍用类模板封装链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

闲来无聊，用类的模板封装的链表，记录下来，说不定哪天用得上那。

template <typename VALUE_TYPE>

class List
{
public:
//定义节点类型
typedef struct Node
{
VALUE_TYPE data;    //数据域
struct Node *next;  //指针域：直接后继的指针
// struct Node *prior; //指针域：直接前驱的指针

} Node,*LINK_LIST;


private:
LINK_LIST ll;   //链表的头指针
LINK_LIST tail; //尾节点指针
int size;       //链表长度

public:
//构造函数：创建一个空链表（带头结点）
List()
{
ll=(struct Node*)malloc(sizeof(struct Node));
ll->next=NULL;

tail=ll;
size=0;
}


//析构函数：销毁链表
~List()
{
struct Node *p=ll,*q=NULL;

while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}

ll=NULL;
tail=NULL;
size=0;
}


//判断链表是否为空
int IsEmpty()
{
return (int)(ll->next);
}

//获取链表长度，即节点个数
int GetLength()
{
/*
struct Node *p=ll->next;
int cnt=0;


while(p!=NULL)
{
cnt++;
p=p->next;
}

return cnt;
*/
return size;
}

//尾部插入节点
void Append(VALUE_TYPE v)
{
struct Node *q=(struct Node*)malloc(sizeof(struct Node));
q->data=v;
q->next=NULL;

tail->next=q;
tail=q;
size++;
/*
struct Node *p=ll;

while(p->next!=NULL)
{
p=p->next;
}

p->next=q;
*/
}


//头部插入节点
void InsertHead(VALUE_TYPE v)
{
struct Node *q=(struct Node*)malloc(sizeof(struct Node));
q->data=v;
q->next=ll->next;

if(ll->next==NULL) tail=q;
ll->next=q;

size++;
}


//在任意位置处插入节点
int Insert(int pos,VALUE_TYPE v)
{
struct Node *p=ll;
int i=0;

while(p!=NULL && i<pos-1)
{
p=p->next;
i++;
}

if(p==NULL || i>pos-1) return 0;

struct Node *q=(struct Node*)malloc(sizeof(struct Node));
q->data=v;
q->next=p->next;

p->next=q;
size++;

return 1;
}


//删除指定节点，根据节点索引（即节点位置，头结点的索引为0，第一个节点的索引为1，以此类推）
int Delete(int pos,VALUE_TYPE *v)
{
struct Node *p=ll;
int i=0;

while(p!=NULL && i<pos-1)
{
p=p->next;
i++;
}

//pos大于链表长度或小于1就失败返回
if(p==NULL || i>pos-1) return 0;

if(NULL!=v) *v=p->next->data;

if(p->next==tail) tail=p;

/*
struct Node *q=p->next->next;
free(p->next);
p->next=q;
*/
//和上面的处理等效
struct Node *q=p->next;
p->next=q->next;
free(q);
size--;

return 1;
}


//删除指定节点，根据节点的数据域，删除成功返回被删除节点的索引，否则返回0
int Delete(VALUE_TYPE v)
{
struct Node *p=ll;
int pos=1;

while(p->next!=NULL && p->next->data!=v) //此时&&的两个操作数不能颠倒位置
{
pos++;
p=p->next;
}


//如果没有找到满足条件的节点就失败返回
if(p->next==NULL) return 0;

if(p->next==tail) tail=p;

/*
struct Node *q=p->next->next;
free(p->next);
p->next=q;
*/

//和上面的处理等效
struct Node *q=p->next;
p->next=q->next;
free(q);

size--;
return pos;
}


//修改指定节点，根据索引
int UpdateByIndex(int pos,VALUE_TYPE v)
{
struct Node *p=ll;
int i=0;

while(p!=NULL && i<pos)
{
p=p->next;
i++;
}

//pos大于链表长度或小于1就失败返回
if(p==NULL || i>pos-1) return 0;

p->data=v;
return 1;
}


//修改指定节点，根据数据值
//修改成功返回被修改节点的索引，否则返回0
int UpdateByValue(VALUE_TYPE old_v,VALUE_TYPE new_v)
{
struct Node *p=ll->next;
int i=1;

while(p!=NULL && p->data!=old_v)
{
p=p->next;
i++;
}


if(p==NULL) return 0;

p->data=new_v;

return i;
}


//查找指定节点，根据索引获取数据值
VALUE_TYPE* GetElemByIndex(int index)
{
struct Node *p=ll;
int i=0;

while(p!=NULL && i<index)
{
p=p->next;
i++;
}

//pos大于链表长度或小于1就失败返回
if(p==NULL || i>index-1) return NULL;

return &(p->data);
}


//查找指定节点，根据数据值获取索引值
int GetElemByValue(VALUE_TYPE v)
{
struct Node *p=ll->next;
int i=1;


while(p!=NULL && p->data!=v)
{
p=p->next;
i++;
}

if(p==NULL) return 0;

return i;
}


//遍历链表
void Traverse(int(*visit)(VALUE_TYPE*))
{
struct Node *p=ll->next;

while(p!=NULL)
{
if(!visit(&(p->data))) break;
p=p->next;
}
}


//排序
//时间复杂度：O(n*n)
void Sort(int (__cdecl *compare )(const VALUE_TYPE &elem1, const VALUE_TYPE &elem2 ))
{
int i,j;
Node *p=NULL;
VALUE_TYPE v;

for(i=0;i<size-1;i++)
{
p=ll->next;


for(j=0;j<size-i-1;j++)
{
if(compare(p->data,p->next->data))
{
memcpy(&v,&(p->data),sizeof(VALUE_TYPE));
memcpy(&(p->data),&(p->next->data),sizeof(VALUE_TYPE));
memcpy(&(p->next->data),&v,sizeof(VALUE_TYPE));
}

p=p->next;
}
}
}


//逆序
//时间复杂度：O(n)
void Reverse()
{
/*
//算法一：相邻节点依次反向
Node* p=ll->next;
Node* q=p->next;
Node* t=NULL;

while(q!=NULL)
{
t=q->next;
q->next=p;
p=q;
q=t;
}


ll->next->next=NULL;
ll->next=p;
*/


//算法二：从第二个节点开始依次插入到链表头
Node* p=ll->next->next;
Node* q=NULL;

//逆序前的第一个节点处理后变为尾节点，所以它的next要赋值为NULL
ll->next->next=NULL;

while(p!=NULL)
{
q=p->next;
p->next=ll->next;
ll->next=p;
p=q;
}
}


//合并
//时间复杂度：O(1)
void Merge(List& l)
{
tail->next=l.ll->next;
tail=l.tail;

l.ll->next=NULL;

/*
Node *p=l.ll->next;


while(p!=NULL)
{
tail->next=p;
tail=p;

p=p->next;
}
*/
}

};


以上链表经本人测试没有问题。

这篇关于用类模板封装链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1144525。

相关文章

利用Python打造一个Excel记账模板

利用Python打造一个Excel记账模板

《利用Python打造一个Excel记账模板》这篇文章主要为大家详细介绍了如何使用Python打造一个超实用的Excel记账模板,可以帮助大家高效管理财务,迈向财富自由之路,感兴趣的小伙伴快跟随小编一... 目录设置预算百分比超支标红预警记账模板功能介绍基础记账预算管理可视化分析摸鱼时间理财法碎片时间利用财
阅读更多...
如何在 Spring Boot 中实现 FreeMarker 模板

如何在 Spring Boot 中实现 FreeMarker 模板

《如何在SpringBoot中实现FreeMarker模板》FreeMarker是一种功能强大、轻量级的模板引擎,用于在Java应用中生成动态文本输出（如HTML、XML、邮件内容等）,本文... 目录什么是 FreeMarker 模板？在 Spring Boot 中实现 FreeMarker 模板1. 环
阅读更多...
IDEA自动生成注释模板的配置教程

IDEA自动生成注释模板的配置教程

《IDEA自动生成注释模板的配置教程》本文介绍了如何在IntelliJIDEA中配置类和方法的注释模板,包括自动生成项目名称、包名、日期和时间等内容,以及如何定制参数和返回值的注释格式,需要的朋友可以... 目录项目场景配置方法类注释模板定义类开头的注释步骤类注释效果方法注释模板定义方法开头的注释步骤方法注
阅读更多...
鸿蒙中Axios数据请求的封装和配置方法

鸿蒙中Axios数据请求的封装和配置方法

《鸿蒙中Axios数据请求的封装和配置方法》：本文主要介绍鸿蒙中Axios数据请求的封装和配置方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.配置权限 应用级权限和系统级权限2.配置网络请求的代码3.下载在Entry中 下载AxIOS4.封装Htt
阅读更多...
SpringBoot中封装Cors自动配置方式

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》：本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties
阅读更多...
C++中函数模板与类模板的简单使用及区别介绍

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中，模板是实现泛型编程
阅读更多...
Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

《Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)》：本文主要介绍Java导入、导出excel的相关资料,讲解了使用Java和ApachePOI库将数据导出为Excel文件,包括... 目录前言一、引入Apache POI依赖二、用法&步骤2.1 创建Excel的元素2.3 样式和字体2.
阅读更多...
JAVA封装多线程实现的方式及原理

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》：本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中，封装多线程的原理主要围绕着将多线程相关的操
阅读更多...
使用C++实现链表元素的反转

使用C++实现链表元素的反转

《使用C++实现链表元素的反转》反转链表是链表操作中一个经典的问题,也是面试中常见的考题,本文将从思路到实现一步步地讲解如何实现链表的反转,帮助初学者理解这一操作,我们将使用C++代码演示具体实现,同... 目录问题定义思路分析代码实现带头节点的链表代码讲解其他实现方式时间和空间复杂度分析总结问题定义给定
阅读更多...
C++实现封装的顺序表的操作与实践

C++实现封装的顺序表的操作与实践

《C++实现封装的顺序表的操作与实践》在程序设计中,顺序表是一种常见的线性数据结构,通常用于存储具有固定顺序的元素,与链表不同,顺序表中的元素是连续存储的,因此访问速度较快,但插入和删除操作的效率可能... 目录一、顺序表的基本概念二、顺序表类的设计1. 顺序表类的成员变量2. 构造函数和析构函数三、顺序表
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2