用类模板封装链表

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。

相关文章

Linux链表操作方式

Linux链表操作方式

《Linux链表操作方式》：本文主要介绍Linux链表操作方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、链表基础概念与内核链表优势二、内核链表结构与宏解析三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势六、典型应用场景七、调试技巧与
阅读更多...
Java如何根据word模板导出数据

Java如何根据word模板导出数据

《Java如何根据word模板导出数据》这篇文章主要为大家详细介绍了Java如何实现根据word模板导出数据,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... pom.XML文件导入依赖 <dependency> <groupId>cn.afterturn</groupId>
阅读更多...
一文详解如何在Vue3中封装API请求

一文详解如何在Vue3中封装API请求

《一文详解如何在Vue3中封装API请求》在现代前端开发中,API请求是不可避免的一部分,尤其是与后端交互时,下面我们来看看如何在Vue3项目中封装API请求,让你在实现功能时更加高效吧... 目录为什么要封装API请求1. vue 3项目结构2. 安装axIOS3. 创建API封装模块4. 封装API请求
阅读更多...
Python中Flask模板的使用与高级技巧详解

Python中Flask模板的使用与高级技巧详解

《Python中Flask模板的使用与高级技巧详解》在Web开发中,直接将HTML代码写在Python文件中会导致诸多问题,Flask内置了Jinja2模板引擎,完美解决了这些问题,下面我们就来看看F... 目录一、模板渲染基础1.1 为什么需要模板引擎1.2 第一个模板渲染示例1.3 模板渲染原理二、模板
阅读更多...
利用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++中，模板是实现泛型编程
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2