C++实现顺序表和单链表（使用模板类）

顺序表
- 类定义
- 总体实现
- 分块
- - 初始化
  - 判空
  - 判满
  - 指定位置插入
  - 指定位置删除并返回被删除的元素
  - 按元素查找
  - 修改指定元素值
  - 遍历顺序表
单链表
- 结点定义
- 方法定义
- 总体实现
- 分块
- - 初始化
  - 判空
  - 插入
  - 删除
  - 按值查找
  - 按位序查找
  - 修改指定位置的元素
  - 遍历单链表
  - 销毁
测试代码
运行结果

顺序表类定义

//顺序表
#pragma once

const int MaxSize = 10;

template 
class Sq_List
{
private:
	T sl[MaxSize];
	int size;

public:
	Sq_List();

	bool isEmpty();	//判空
	bool isFull();	//判满
	bool Insert(int pos, T elem);	//指定位置插入
	bool Delete(int pos, T& elem);	//指定位置删除并返回被删除的元素
	int Find(T elem);	//按元素查找
	bool Change(T elem1, T elem2);	//修改指定元素的值
	void show();	//遍历顺序表
};

总体实现

#include "Sq_List.h"
#include 

using namespace std;

template 
Sq_List::Sq_List()
{
	size = 0;
}

template 
bool Sq_List::isEmpty()
{
	return size == 0;
}

template 
bool Sq_List::isFull()
{
	return size > MaxSize;
}

template 
bool Sq_List::Insert(int pos, T elem)
{
	if (pos < 0 || pos >= MaxSize || isFull())
		return false;
	for (int i = size; i > pos; i--)
	{
		sl[i] = sl[i - 1];	
	}
	sl[pos] = elem;
	size++;
	return true;
}

template 
bool Sq_List::Delete(int pos, T& elem)
{
	if (pos < 0 || pos >= size || isEmpty())
		return false;
	elem = sl[pos];
	for (int i = pos; i < size; i++)
		sl[i] = sl[i + 1];
	size--;
	return true;
}

template 
int Sq_List::Find(T elem)
{
	for (int i = 0; i < size; i++)
	{
		if (sl[i] == elem)
			return i;
	}
	return -1;
}

template 
bool Sq_List::Change(T elem1, T elem2)
{
	int pos = Find(elem1);
	if (pos == -1)
		return false;
	sl[pos] = elem2;
	return true;
}

template 
void Sq_List::show()
{
	for (int i = 0; i < size; i++)
		cout << sl[i] << " ";
	cout << endl;
}

分块初始化

template 
Sq_List::Sq_List()
{
	size = 0;
}

判空

template 
bool Sq_List::isEmpty()
{
	return size == 0;
}

判满

template 
bool Sq_List::isFull()
{
	return size > MaxSize;
}

指定位置插入

template 
bool Sq_List::Insert(int pos, T elem)
{
	if (pos < 0 || pos >= MaxSize || isFull())
		return false;
	for (int i = size; i > pos; i--)
	{
		sl[i] = sl[i - 1];	
	}
	sl[pos] = elem;
	size++;
	return true;
}

指定位置删除并返回被删除的元素

template 
bool Sq_List::Delete(int pos, T& elem)
{
	if (pos < 0 || pos >= size || isEmpty())
		return false;
	elem = sl[pos];
	for (int i = pos; i < size; i++)
		sl[i] = sl[i + 1];
	size--;
	return true;
}

按元素查找

template 
int Sq_List::Find(T elem)
{
	for (int i = 0; i < size; i++)
	{
		if (sl[i] == elem)
			return i;
	}
	return -1;
}

修改指定元素值

template 
bool Sq_List::Change(T elem1, T elem2)
{
	int pos = Find(elem1);
	if (pos == -1)
		return false;
	sl[pos] = elem2;
	return true;
}

遍历顺序表

template 
void Sq_List::show()
{
	for (int i = 0; i < size; i++)
		cout << sl[i] << " ";
	cout << endl;
}

单链表结点定义

template 
class Node
{
public:
	T data;
	Node* next;
};

方法定义

template 
class Link_List
{
private:
	Node* head;

public:
	int size;

	Link_List();

	bool isEmpty();	//判空
	bool Insert(int pos, T elem);	//0：头插，this->size：尾插，支持任意位置插入
	bool Delete(int pos, T& elem);	//1:头删，this->size：尾删，支持任意位置删除
	int vFind(T elem);	//按值查找并返回位序
	bool pFind(int pos, T& elem);	//按位序查找并返回值
	bool Change(int pos, T elem);	//修改指定位置元素
	void show();	//遍历

	~Link_List();
};

总体实现

//链表
#include "Link_List.h"
#include 

using namespace std;

template 
Link_List::Link_List()
{
	head = new Node;
	head->next = NULL;
	this->size = 0;
}

template 
bool Link_List::isEmpty()
{
	return this->size == 0;
}

template 
bool Link_List::Insert(int pos, T elem)
{
	if (pos < 0 || pos > this->size + 1)
		return false;
	Node* p = new Node;
	p->data = elem;
		
	Node* q = head;
	for (int i = 0; i < pos; i++)	//i:位置计数器
		q = q->next;
	p->next = q->next;
	q->next = p;
	this->size++;
	return true;
}

template 
bool Link_List::Delete(int pos, T& elem)
{
	if (pos < 1 || isEmpty())
		return false;
	Node* pre = head;
	for (int i = 0; i < pos - 1; i++)	//i:位置计数器
	{
		pre = pre->next;
	}
	Node* p = pre->next;
	pre->next = p->next;
	elem = p->data;
	delete p;
	this->size--;
	return true;
}

template 
int Link_List::vFind(T elem)
{
	if (isEmpty())
		return -1;
	Node* p = head;
	for (int i = 0; i < this->size; i++)
	{
		p = p->next;
		if (p->data == elem)
			return i + 1;
	}
	return -1;
}

template 
bool Link_List::pFind(int pos, T& elem)
{
	if (isEmpty() || pos < 1 || pos > this->size)
		return false;
	Node* p = head;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	elem = p->data;
	return true;
}

template 
bool Link_List::Change(int pos, T elem)
{
	if (isEmpty() || pos < 1 || pos > this->size)
		return false;
	Node* p = head;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	p->data = elem;
	return true;
}

template 
void Link_List::show()
{
	Node* p = head;
	for (int i = 0; i < this->size; i++)
	{
		p = p->next;
		cout << p->data << " ";
	}
	cout << endl;
}

template 
Link_List::~Link_List()
{
	delete head;
}

分块初始化

template 
Link_List::Link_List()
{
	head = new Node;
	head->next = NULL;
	this->size = 0;
}

判空

template 
bool Link_List::isEmpty()
{
	return this->size == 0;
}

插入

template 
bool Link_List::Insert(int pos, T elem)
{
	if (pos < 0 || pos > this->size + 1)
		return false;
	Node* p = new Node;
	p->data = elem;
		
	Node* q = head;
	for (int i = 0; i < pos; i++)	//i:位置计数器
		q = q->next;
	p->next = q->next;
	q->next = p;
	this->size++;
	return true;
}

删除

template 
bool Link_List::Delete(int pos, T& elem)
{
	if (pos < 1 || isEmpty())
		return false;
	Node* pre = head;
	for (int i = 0; i < pos - 1; i++)	//i:位置计数器
	{
		pre = pre->next;
	}
	Node* p = pre->next;
	pre->next = p->next;
	elem = p->data;
	delete p;
	this->size--;
	return true;
}

按值查找

template 
int Link_List::vFind(T elem)
{
	if (isEmpty())
		return -1;
	Node* p = head;
	for (int i = 0; i < this->size; i++)
	{
		p = p->next;
		if (p->data == elem)
			return i + 1;
	}
	return -1;
}

按位序查找

template 
bool Link_List::pFind(int pos, T& elem)
{
	if (isEmpty() || pos < 1 || pos > this->size)
		return false;
	Node* p = head;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	elem = p->data;
	return true;
}

修改指定位置的元素

template 
bool Link_List::Change(int pos, T elem)
{
	if (isEmpty() || pos < 1 || pos > this->size)
		return false;
	Node* p = head;
	while (pos > 0)
	{
		p = p->next;
		pos--;
	}
	p->data = elem;
	return true;
}

遍历单链表

template 
void Link_List::show()
{
	Node* p = head;
	for (int i = 0; i < this->size; i++)
	{
		p = p->next;
		cout << p->data << " ";
	}
	cout << endl;
}

销毁

template 
Link_List::~Link_List()
{
	delete head;
}

测试代码

#include 
#include "Sq_List.h"
#include "Sq_List.cpp"
#include "Link_List.h"
#include "Link_List.cpp"
using namespace std;

int main()
{
	Sq_List sl;
	for (int i = 0; i < 10; i++)
	{
		sl.Insert(i, i + 1);
	}
	sl.show();

	int pos = 2;
	int k;
	sl.Delete(pos, k);
	cout << "删除第" << pos + 1 << "个位置的元素：" << k << endl;
	cout << "剩余：";
	sl.show();

	k = 7;
	pos = sl.Find(k);
	cout << k << "所在位置为：" << pos + 1 << endl;

	int l = 7;
	k = 100;
	sl.Change(l, k);
	cout << "把元素" << l << "修改为：" << k << endl;
	sl.show();

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	Link_List ll;
	//判空
	if (ll.isEmpty())
		cout << "链表为空" << endl;

	//头插
	for (int i = 0; i < 5; i++)
	{
		cout << "头插：" << i + 11 << endl;
		ll.Insert(0, i + 11);
		cout << "插入后：";
		ll.show();
	}

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	cout << "目前剩余元素：";
	ll.show();

	//尾插
	for (int i = 0; i < 5; i++)
	{
		cout << "尾插：" << i + 101 << endl;
		ll.Insert(ll.size, i + 101);
		cout << "插入后：";
		ll.show();
	}

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	cout << "目前剩余元素：";
	ll.show();

	//任意位置插入
	for (int i = 0; i < 5; i++)
	{
		cout << "6号位置插入：" << i + 1001 << endl;
		ll.Insert(5, 1001 + i);
		cout << "插入后：";
		ll.show();
	}

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	cout << "目前剩余元素：";
	ll.show();

	int elem = 0;
	//头删
	for (int i = 0; i < 3; i++)
	{
		ll.Delete(1, elem);
		cout << "删除元素的值为：" << elem << endl;
		cout << "删除第一个结点后链表中剩余元素："; 
		ll.show();
	}

	//尾删
	for (int i = 0; i < 3; i++)
	{
		ll.Delete(ll.size, elem);
		cout << "删除元素的值为：" << elem << endl;
		cout << "删除最后一个结点后链表中剩余元素：";
		ll.show();
	}

	//任意删
	for (int i = 0; i < 3; i++)
	{
		ll.Delete(3, elem);
		cout << "删除元素的值为：" << elem << endl;
		cout << "删除第三个结点后链表中剩余元素：";
		ll.show();
	}

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	cout << "目前剩余元素：";
	ll.show();

	//按值查找，找到
	k = 1001;
	pos = ll.vFind(k);
	if (pos != -1)
		cout << "找到了" << k << "位置在：" << pos << endl;
	else
		cout << "未找到" << k << endl;

	//按值查找，未找到
	k = 1;
	pos = ll.vFind(k);
	if (pos != -1)
		cout << "找到了" << k << "位置在：" << pos << endl;
	else
		cout << "未找到" << k << endl;

	//按位序查找
	pos = 2;
	ll.pFind(pos, k);
	cout << pos << "号位置的元素为：" << k << endl;

	cout << "按任意键清屏！！" << endl;
	getchar();
	system("cls");	//清屏

	cout << "目前剩余元素：";
	ll.show();

	//按位序修改元素
	ll.Change(pos, 999);
	cout << "将" << pos << "号位置的元素修改为：" << 999 << endl;
	cout << "修改后：";
	ll.show();
	return 0;
}

运行结果

例子选择6号位置

C++实现顺序表和单链表（使用模板类）

C/C++/C#相关栏目本月热门文章