链表数据结构的C++实现:类模板实现线性表的链式存储

简介: 链表数据结构的C++实现:类模板实现线性表的链式存储

类的定义

在类的内部包含一个结构体,结构体包含一个指向下一结点的指针,以及一个数据域,用于存储插入链表的用户数据。

1. #pragma once
2. #include <iostream>
3. using namespace std;
4. 
5. template<typename MyType>
6. class LinkedList
7. {
8. public:
9.  LinkedList();
10.   ~LinkedList();
11. public:
12.   int get_length();
13.   MyType get_data(int pos);
14.   int insert(MyType& node, int pos);
15.   MyType delet(int pos);
16.   void clear();
17. public:
18.   typedef struct ListNode
19.   {
20.     struct ListNode* next;
21.     MyType data;
22.   }ListNode;
23. private:
24.   int length;
25.   ListNode* head;
26. };

成员函数的实现

1. template<typename MyType>
2. LinkedList<MyType>::LinkedList()
3. {
4.  this->head = new ListNode;
5.  this->head->next = NULL;
6.  this->length = 0;
7. }
8. 
9. template<typename MyType>
10. LinkedList<MyType>::~LinkedList()
11. {
12.   ListNode* pCurrent = this->head;
13.   while (pCurrent != NULL)
14.   {
15.     ListNode* pTemp = pCurrent;
16.     pCurrent = pCurrent->next;
17.     delete pTemp;
18.   }
19.   this->length = 0;
20. }
21. 
22. template<typename MyType>
23. int LinkedList<MyType>::get_length()
24. {
25.   return this->length;
26. }
27. 
28. template<typename MyType>
29. MyType LinkedList<MyType>::get_data(int pos)
30. {
31.   ListNode* pCurrent = this->head;
32.   for (int i = 0; i < pos; i++)
33.   {
34.     pCurrent = pCurrent->next;
35.   }
36.   return pCurrent->next->data;
37. }
38. 
39. template<typename MyType>
40. int LinkedList<MyType>::insert(MyType& node, int pos)
41. {
42.   ListNode* pCurrent = this->head;
43.   for (int i = 0; i < pos; i++)
44.   {
45.     pCurrent = pCurrent->next;
46.   }
47.   ListNode* pNode = new ListNode;
48.   pNode->data = node;
49.   pNode->next = pCurrent->next;
50.   pCurrent->next = pNode;
51.   this->length++;
52.   return 0;
53. }
54. 
55. template<typename MyType>
56. MyType LinkedList<MyType>::delet(int pos) 
57. {
58.   ListNode* pCurrent = this->head;
59.   for (int i = 0; i < pos; i++)
60.   {
61.     pCurrent = pCurrent->next;
62.   }
63.   MyType temp_data = pCurrent->next->data;
64.   ListNode* pTemp = pCurrent->next;
65.   pCurrent->next = pCurrent->next->next;
66.   delete pTemp;
67.   this->length--;
68.   return temp_data;
69. }
70. 
71. template<typename MyType>
72. void LinkedList<MyType>::clear()
73. {
74.   ListNode* pCurrent = this->head;
75.   while (pCurrent != NULL)
76.   {
77.     ListNode* pTemp = pCurrent;
78.     pCurrent = pCurrent->next;
79.     delete pTemp;
80.   }
81.   this->head = new ListNode;
82.   this->head->next = NULL;
83.   this->length = 0;
84. }

因为链表的结点是动态分配的,插入一个数据,就用动态构造一个结点,并把要插入的数据存到结点的数据域。所以,在插入元素和删除元素的时候需要使用new和delete来管理内存。

C语言实现链表请参考文章

image.png

另外,代码资源已经上传,可在我的资源免费下载。


目录
打赏
0
0
0
0
13
分享
相关文章
|
1月前
|
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
141 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
144 77
㉿㉿㉿c++模板的初阶(通俗易懂简化版)㉿㉿㉿
㉿㉿㉿c++模板的初阶(通俗易懂简化版)㉿㉿㉿
|
1月前
|
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
【数据结构——树】哈夫曼树(头歌实践教学平台习题)【合集】目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果:任务描述 本关任务:编写一个程序构建哈夫曼树和生成哈夫曼编码。 相关知识 为了完成本关任务,你需要掌握: 1.如何构建哈夫曼树, 2.如何生成哈夫曼编码。 测试说明 平台会对你编写的代码进行测试: 测试输入: 1192677541518462450242195190181174157138124123 (用户分别输入所列单词的频度) 预
62 14
【C++数据结构——树】哈夫曼树(头歌实践教学平台习题) 【合集】
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
47 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
1月前
|
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
【数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】 目录 任务描述 相关知识 测试说明 我的通关代码: 测试结果: 任务描述 本关任务:实现二叉排序树的基本算法。 相关知识 为了完成本关任务,你需要掌握:二叉树的创建、查找和删除算法。具体如下: (1)由关键字序列(4,9,0,1,8,6,3,5,2,7)创建一棵二叉排序树bt并以括号表示法输出。 (2)判断bt是否为一棵二叉排序树。 (3)采用递归方法查找关键字为6的结点,并输出其查找路径。 (4)分别删除bt中关键
55 11
【C++数据结构——查找】二叉排序树(头歌实践教学平台习题)【合集】
深入理解C++模板编程:从基础到进阶
在C++编程中,模板是实现泛型编程的关键工具。模板使得代码能够适用于不同的数据类型,极大地提升了代码复用性、灵活性和可维护性。本文将深入探讨模板编程的基础知识,包括函数模板和类模板的定义、使用、以及它们的实例化和匹配规则。
【C++数据结构——图】最短路径(头歌教学实验平台习题) 【合集】
任务描述 本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。 相关知识 为了完成本关任务,你需要掌握:Dijkst本关任务:编写一个程序,利用Dijkstra算法,实现带权有向图的最短路径。为了完成本关任务,你需要掌握:Dijkstra算法。带权有向图:该图对应的二维数组如下所示:Dijkstra算法:Dijkstra算法是指给定一个带权有向图G与源点v,求从v到G中其他顶点的最短路径。Dijkstra算法的具体步骤如下:(1)初始时,S只包含源点,即S={v},v的距离为0。
63 15
|
1月前
|
【C++数据结构——树】二叉树的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现二叉树的基本运算。​ 相关知识 创建二叉树 销毁二叉树 查找结点 求二叉树的高度 输出二叉树 //二叉树节点结构体定义 structTreeNode{ intval; TreeNode*left; TreeNode*right; TreeNode(intx):val(x),left(NULL),right(NULL){} }; 创建二叉树 //创建二叉树函数(简单示例,手动构建) TreeNode*create
49 12
|
1月前
|
C++
【C++数据结构——树】二叉树的性质(头歌实践教学平台习题)【合集】
本文档介绍了如何根据二叉树的括号表示串创建二叉树,并计算其结点个数、叶子结点个数、某结点的层次和二叉树的宽度。主要内容包括: 1. **定义二叉树节点结构体**:定义了包含节点值、左子节点指针和右子节点指针的结构体。 2. **实现构建二叉树的函数**:通过解析括号表示串,递归地构建二叉树的各个节点及其子树。 3. **使用示例**:展示了如何调用 `buildTree` 函数构建二叉树并进行简单验证。 4. **计算二叉树属性**: - 计算二叉树节点个数。 - 计算二叉树叶子节点个数。 - 计算某节点的层次。 - 计算二叉树的宽度。 最后,提供了测试说明及通关代
47 10
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等