用类模板封装链表

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。

相关文章

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. 构造函数和析构函数三、顺序表
阅读更多...
Go语言利用泛型封装常见的Map操作

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式，允
阅读更多...
基于Java实现模板填充Word

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是：我们需要把数据库中的某些数据按照 产品经理提供的 word模板，把数据
阅读更多...
poj3468(线段树成段更新模板题)

poj3468(线段树成段更新模板题)

题意：包括两个操作：1、将[a.b]上的数字加上v；2、查询区间[a,b]上的和 下面的介绍是下解题思路： 首先介绍  lazy－tag思想：用一个变量记录每一个线段树节点的变化值，当这部分线段的一致性被破坏我们就将这个变化值传递给子区间，大大增加了线段树的效率。 比如现在需要对[a,b]区间值进行加c操作，那么就从根节点[1,n]开始调用update函数进行操作，如果刚好执行到一个子节点，
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2