用类模板封装链表

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。

相关文章

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 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
csu1329(双向链表)

csu1329(双向链表)

题意：给n个盒子，编号为1到n，四个操作：1、将x盒子移到y的左边；2、将x盒子移到y的右边；3、交换x和y盒子的位置；4、将所有的盒子反过来放。 思路分析：用双向链表解决。每个操作的时间复杂度为O(1)，用数组来模拟链表，下面的代码是参考刘老师的标程写的。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#
阅读更多...
poj 1258 Agri-Net（最小生成树模板代码）

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n
阅读更多...
uva 1342 欧拉定理（计算几何模板）

uva 1342 欧拉定理（计算几何模板）

题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
poj 2104 and hdu 2665 划分树模板入门题

poj 2104 and hdu 2665 划分树模板入门题

题意： 给一个数组n（1e5）个数，给一个范围（fr， to， k），求这个范围中第k大的数。 解析： 划分树入门。 bing神的模板。 坑爹的地方是把-l 看成了-1........ 一直re。 代码： poj 2104： #include <iostream>#include <cstdio>#include <cstdlib>#include <al
阅读更多...
最大流、 最小费用最大流终极版模板

最大流、 最小费用最大流终极版模板

最大流  const int inf = 1000000000 ;const int maxn = 20000 , maxm = 500000 ;struct Edge{int v , f ,next ;Edge(){}Edge(int _v , int _f , int _next):v(_v) ,f(_f),next(_next){}};int sourse , mee
阅读更多...
深入手撕链表

深入手撕链表

链表 分类概念单链表增尾插头插插入 删尾删头删删除 查完整实现带头不带头 双向链表初始化增尾插头插插入 删查完整代码 数组 分类 #mermaid-svg-qKD178fTiiaYeKjl {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-
阅读更多...
建立升序链表

建立升序链表

题目1181：遍历链表 时间限制：1 秒 内存限制：32 兆 特殊判题：否 提交：2744 解决：1186 题目描述： 建立一个升序链表并遍历输出。 输入： 输入的每个案例中第一行包括1个整数：n(1<=n<=1000)，接下来的一行包括n个整数。 输出： 可能有多组测试数据，对于每组数据， 将n个整数建立升序链表，之后遍历链表并输出。 样例输
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2