devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——单链表的实现_构造单链表实例

作者：繁依Fanyi0 | 2024-06-04 06:37:12

赞

踩

构造单链表实例

文章目录

一、单链表的定义
template <typename DataType>
class LinkList
{
public:
	LinkList();				//建立只有头结点的单链表；
	LinkList(DataType a[], int n);		//建立n个元素的单链表；
	~LinkList();				//析构函数；
	int Length();				//求单链表的长度；
	DataType Get(int i);			//按位查找，查找第i个结点的元素值；
	int Locate(DataType x);			//按值查找，查找值为x的元素序号；
	void Insert(int i,DataType x);		//在第 i个位置插入值为x的结点；
	DataType Delete(int i);			//删除操作，删除第i个结点；
	int Empty();				//判断线性表是否为空；
	void PrintList();			//遍历操作，按序号依次输出各元素；

private:
	Node<DataType> *first;			//单链表的头指针；
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17



二、单链表的初始化
template<typename DataType>
LinkList<DataType>::LinkList()
{
	first = new Node<DataType>;	//生成头结点；
	first->next = nullptr;		//头结点的指针域置空；
}
  • 1
  • 2
  • 3
  • 4
  • 5



三、单链表的判空操作
template<typename DataType>
int LinkList<DataType>::Empty()
{
	if(first->next == nullptr)
		return 1;
	else		
		return 0;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7



四、单链表的遍历操作
template<typename DataType>
void LinkList<DataType> :: PrintList()
{	
	Node<DataType> *p = frist->next;	//工作指针P初始化；
	while(p != nullptr)			//如果p指针的值不为空，执行以下代码；
	{	
		cout<<p->data<<"\t";		//依次输出p指针所指向的值；
		p = p->next;			//工作指针P后移，注意不能写作P++；
	}
	cout<<endl;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10



五、求单链表的长度
template<typename DataType()>
int LinkList<DataType>::Length()
{
	Node<DataType> *p = frist->next;	//指针p初始化；
	int count = 0；				//累加器初始化；
	while(p != nullptr)
	{
		p = p->next;             	//p不等于空，指针指向下一个；
		count++;			//每循环一次，count+1；
	}
	return count;				//循环结束，返回count中记录单链表长度的值；
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11



六、按位查找
template<typename DataType>
DataType LinkList<DataType>::Get(int i) 	//按位查找，查找第i个位置所对应的值；
{	
	Node<DataType> *p = frist->next;	//指针p初始化；
	int count = 1;				//累加器初始化；
	while(p != nullptr && count<i)		//当p指针不为空，且累加器的位置<i结点的位置时，执行以下循环查询语句；
	{	
		p = p->next;			//指针p往后移；
		count++;			//每循环一次，count+1;
	}
	if(p == nullptr)			//如果指针p为空，提示“查找位置出错”；
		throw "查找位置出错"；
	else 					//否则，返回第i个结点，p指针所指向的数据；
		return p->data;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14



七、按值查找
template<typename DataType>
int LinkList<DataType>::Locate(DataType x)	//查找x值所在的位置序号；
{	
	Node<DataType> *p = first->next;	//指针p初始化；
	int count = 1;				//累加器初始化；
	while(p ！= nullptr)			//当p指针的值不为空，执行以下代码；
	{	
		if(p->data == x)		//先判断一下p指针所指位置的值是否等于x,如果等于x,则返回累加器count所记录的位置序号；
			return count;
		p = p->next;			//如果不等于x的值，则p指针往后移，继续查询；
		count++;			//每循环一次，count+1;
	}
	return 0;				//否则结果返回0，退出循环，表示查找失败；
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13



八、单链表的插入操作
template<typename DataType>
void LinkList<DataType>::Insert(int i, DataType x)	//在第i个结点，插入值为x的数据；
{
	Node<DataType> *p = frist, *s = nullptr;	//先定义p指针，s指针，为插入操作做准备；
	int count = 0;					//累加器初始化；
	while(p != nullptr && count<i-1)		//当p指针不为空，查找第i-1个结点的位置；
	{
		p = p->next;				//p指针往后移，继续查询；
		count++;				//每循环一次，count+1;
	}
	if(p == nullptr)				//如果p指针为空，表示未找到第i-1个结点的位置；
		throw "插入位置错误"；
	else						//否则，表示查询成功，准备执行插入操作；
	{
		s = new Node<DataType>;			//申请一个结点s;
		s->data = x;				//把值为x的数据，放入s的数据域中储存；
		s->next = p->next;			//先修改s->next的值，使s结点的下一个指针，指向原来p->next,进而插入s新结点；
		p->next = s;				//然后再把s结点的数据，放在p->next中存储，完成插入操作；
	}	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19



九、构造函数—建立单链表

设给定的数据元素存放在“数组a[n]”中，建立单链表就是生成存储这n个数据元素的单链表。

  • 头插法： 每次将“新申请的结点”插到“头结点”的后面；
template<typename DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{	
	first = new Node<DataType>;		//生成头结点；
	first->next = nullptr;			//初始化一个新链表；
	for(int i=0; i<n; i++)			//当i<n时，执行以下循环；
	{
		Node<DataType> *s = nullptr;	//定义一个s指针；
		s = new Node<DataType>;		//申请一个s结点；
		s->next = a[i];			//将数组a[i]的数据元素，放入s->next中；
		s->next = first->next;		///先修改s->next的值，使s结点的下一个指针，指向头结点的first->next,进而插入s新结点；
		first->next = s;		//然后再把s结点的数据，放在first->next中存储，完成头插入操作；
	}
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

  • 尾插法： 每次将“新申请的结点”插到“终端结点”的后面，因此，需要设“尾指针”指向“当前的终端结点”。
template<typename DataType>
LinkList<DataType>::LinkList(DataType a[], int n)
{	
	first = new Node<DataType>;		//生成头结点；
	Node<DataType> *r = nullptr;		//尾指针初始化；
	for(int i=0; i<n; i++)			//当i<n时，执行以下循环；
	{
		s = new Node<DataType>;         //申请一个s结点；
		s->data = a[i];			//将数组a[i]的数据元素，放入s->data数据域中；
		r->next = s;
		r = s;				//将结点s插入到终端结点之后；
	}
	r->next = nullptr;			//单链表建立完毕，将终端结点的指针域置空；
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13



十、单链表的删除操作
template<typename DataType>
DataType LinkList<DataType>::Delete(int i)		//删除第i个结点的数据；
{
	DataType x;					//定义一个变量x;
	Node<DataType> *p = first, *q = nullptr;	//先定义p指针，q指针，为删除操作做准备；
	int count = 0;					//累加器初始化；
	while(p != nullptr && count<i-1)		//当p不为空时，查找第i-1个结点的位置；
	{
		p = p->next;				//p指针往后移，继续查询；
		count++;				//每循环一次，count+1;
	}
	if(p == nullptr || p->next == nullptr)		//如果p指针为空或者p的后继结点不存在时，表示未找到第i-1个结点的位置；
		throw "删除位置错误"；
	else						//否则，执行删除操作；
	{
		q = p->next;				//先用q指针，记录下p->next的位置；
		x = p->data;				//再用x变量，保存下p里面的数据；
		p->next = q->next;			//p->next直接跳转到p->next->next,即跳过中间的i结点，删除了i结点上的数据；
		delete q;				//相当于free q ,释放q的内存空间；
		return x;				//返回删除i结点前，保存下来i的数据；
	}
	/*else
	{
		p->next = p->next->next;		//如果不需要返回删除结点i的数据，else删除语句可以简化为一句；
	}*/
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25



十一、析构函数—销毁单链表
template<typename DataType>
LinkList<DataType>::~LinkList()
{
	Node<DataType> *p = first;		//定义一个p指针指向first;
	while(first != nullptr)			//当first不为空时，释放每一个结点的存储空间；
	{
		first = first->next;		//first指向被释放结点的下一个结点；
		delete p;			//释放p指针指向的结点空间；
		p = first;			//工作指针p往后移；
	}	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10



十二、总结—单链表实例（C++）
#include<iostream>
using namespace std;

struct Node
{
	DataType data;	//定义一个数据域；
	Node *next;	//定义一个指针域；
};

class LinkList
{
	public:
		LinkList();			 //无参构造函数，建立只有头结点的空链表；
		LinkList(DataType a[], int n);   //建立n个元素的单链表；
		~LinkList();   			 //析构函数；
 		int Length();                   //求单链表的长度；
		DataType Get(int i);   		//按位查找，查找第i个结点的元素值；
 		int Locate(DataType x); 	//按值查找，查找值为x的元素序号；
 		void Insert(int i,DataType x);  //在第 i个位置插入值为x的结点；
 		DataType Delete(int i);  	//删除操作，删除第i个结点；
		int Empty();    		//判断线性表是否为空；
		void PrintList();   		//遍历操作，按序号依次输出各元素；
	private:
		Node<DataType> *first;  	//单链表的头指针；
}；

LinkList::LinkList()
{
		 first = new Node; 	//生成头结点；
		 first->next = nullptr;  //头结点的指针域置空；
}

LinkList::~LinkList()
{
		 Node *q = NULL;  	//定义一个q指针指向NULL;
 	while(first != NULL)   		//当first不为空时，释放每一个结点的存储空间；
 	{
 		  q =first; 		//暂时存放被释放的结点；
		  first = first->next; 	//first指向被释放结点的下一个结点；
		  delete q;   		//释放p指针指向的结点空间；
 	} 
}

void LinkList::Empty()
	{
		 if(first->next == nullptr)
		  	return 1;
		 else  
		  	return 0;
	}
	
void LinkList :: PrintList()
{ 
 Node *p = frist->next; 	//工作指针P初始化；
	 while(p != nullptr)   		//如果p指针的值不为空，执行以下代码；
	 { 
		  cout<<p->data<<"\t";  	//依次输出p指针所指向的值；
		  p = p->next;   		//工作指针P后移，注意不能写作P++；
	 }
}
	
int LinkList::Length()
{
	 Node *p = frist->next;      //指针p初始化；
	 int count = 0；    	    //累加器初始化；
	 while(p != nullptr)
	 {
		  p = p->next;              //p不等于空，指针指向下一个；
		  count++;   		    //每循环一次，count+1；
	 }
	 return count;    	   //循环结束，返回count中记录单链表长度的值；
	}
	
DataType LinkList::Get(int i)  //按位查找，查找第i个位置所对应的值；
{ 
	 Node *p = frist->next; 	//指针p初始化；
	 int count = 1;    		//累加器初始化；
	 while(p != nullptr && count<i)  //当p指针不为空，且累加器的位置<i结点的位置时，执行以下循环查询语句；
	{ 
		  p = p->next;   		//指针p往后移；
		  count++;   			//每循环一次，count+1;
	}
	 if(p == nullptr)   		//如果指针p为空，提示“查找位置出错”；
	  	throw "查找位置出错"；
	 else      			//否则，返回第i个结点，p指针所指向的数据；
	 	 return p->data;
}
	
int LinkList::Locate(DataType x)   //查找x值所在的位置序号；
{ 
	 Node *p = first->next;       //指针p初始化；
	 int count = 1;    	     //累加器初始化；
	 while(p ！= nullptr)  	    //当p指针的值不为空，执行以下代码；
	 { 
		  if(p->data == x)  	 //先判断一下p指针所指位置的值是否等于x,如果等于x,则返回累加器count所记录的位置序号；
	  		 return count;
		  p = p->next;   	//如果不等于x的值，则p指针往后移，继续查询；
		  count++;   		//每循环一次，count+1;
	 }
	 return 0;    		//否则结果返回0，退出循环，表示查找失败；
	}
	
void LinkList::Insert(int i, DataType x) //在第i个结点，插入值为x的数据；
{
	 Node *p = frist, *s = nullptr; 	//先定义p指针，s指针，为插入操作做准备；
	 int count = 0;     			//累加器初始化；
	 while(p != nullptr && count<i-1)  	//当p指针不为空，查找第i-1个结点的位置；
	 {
		  p = p->next;    	//p指针往后移，继续查询；
		  count++;    		//每循环一次，count+1;
	 }
	if(p == nullptr)    	//如果p指针为空，表示未找到第i-1个结点的位置；
  		throw "插入位置错误"；
 	else      		//否则，表示查询成功，准备执行插入操作；
 	{
		  s = new Node;   	//申请一个结点s;
		  s->data = x;    	//把值为x的数据，放入s的数据域中储存；
		  s->next = p->next;   //先修改s->next的值，使s结点的下一个指针，指向原来p->next,进而插入s新结点；
		  p->next = s;         //然后再把s结点的数据，放在p->next中存储，完成插入操作；
	 } 
}

LinkList::LinkList(DataType a[], int n)
{ 
	 first = new Node;  	//生成头结点；
	 first->next = nullptr;   	//初始化一个新链表；
 	for(int i=0; i<n; i++)   	//当i<n时，执行以下循环；
	{
  		Node *s = nullptr; 	//定义一个s指针；
		 s = new Node;  	//申请一个s结点；
		 s->next = a[i];   	//将数组a[i]的数据元素，放入s->next中；
		 s->next = first->next;  //先修改s->next的值，使s结点的下一个指针，指向头结点的first->next,进而插入s新结点；
		 first->next = s;  	//然后再把s结点的数据，放在first->next中存储，完成头插入操作；
 	}
}

LinkList::LinkList(DataType a[], int n)
{ 
	 first = new Node;  	//生成头结点；
	 Node *r = nullptr;  	//尾指针初始化；
 	for(int i=0; i<n; i++)   //当i<n时，执行以下循环；
 	{
		  s = new Node<DataType>;        //申请一个s结点；
		  s->data = a[i];   //将数组a[i]的数据元素，放入s->data数据域中；
		  r->next = s;
		  r = s;    //将结点s插入到终端结点之后；
	}
	r->next = nullptr;   //单链表建立完毕，将终端结点的指针域置空；
}

DataType LinkList::Delete(int i)  //删除第i个结点的数据；
{
	 DataType x;     //定义一个变量x;
	 Node *p = first, *q = nullptr; //先定义p指针，q指针，为删除操作做准备；
	 int count = 0;     //累加器初始化；
	 while(p != nullptr && count<i-1)  //当p不为空时，查找第i-1个结点的位置；
	 {
		  p = p->next;    //p指针往后移，继续查询；
		  count++;    //每循环一次，count+1;
	 }
	if(p == nullptr || p->next == nullptr)  //如果p指针为空或者p的后继结点不存在时，表示未找到第i-1个结点的位置；
  		throw "删除位置错误"；
 	else      //否则，执行删除操作；
 	{
		  q = p->next;    //先用q指针，记录下p->next的位置；
		  x = p->data;    //再用x变量，保存下p里面的数据；
		  p->next = q->next;   //p->next直接跳转到p->next->next,即跳过中间的i结点，删除了i结点上的数据；
		  delete q;    //相当于free q ,释放q的内存空间；
		  return x;    //返回删除i结点前，保存下来i的数据；
	 }
}

int main()
{
	int[6] = {1,2,3,4,5,6},i,x;
	LinkList<int> L{r,6};
	cout<<"当前线性表的数据为："；
	L.PrintList();		//输出当前链表的数据：1 2 3 4 5 6；
	try
	{
		L.Inset(3,9);	//在第3个位置插入值为9的结点；
		cout<<"插入数据9后，链表中数据为："；	
		L.PrintList();		//输出插入数据9后的链表：1 2 9 3 4 5 6；
	}
	catch(char *str)
	{
		cout<<str<<endl;
	}
	cout<<"输出当前链表的长度为："<<L.Length()<<endl;	   //输出链表的长度为：7；
	cout<<"请输入想要查找的元素的值："；
	cin>>x;
	i = L.Locate(x);	//调用Locate()函数,按值查找x的位置；
	if(i>0)
		cout<<"元素"<<x<<"的位置为："<<i<<endl;
	else
		cout<<"单链表中没有"<<x<<"元素"<<endl；
	try
	{
		cout<<"请输入想要删除第几个元素的位置序号："；
		cin>>i;
		x = L.Delete(i);	//删除第i个元素；
		cout<<"删除了"<<x<<"元素值"<<endl;
		cout<<"删除完元素后，链表中数据为："；
		L.PrintList();		//遍历链表，输出删除完元素后的链表数据；
	}
	catch(char *str)
	{	
		cout<<str<<endl;
	}
return 0;
}
	

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/670772
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号