算法与数据结构 单链表

1.随机产生10个100以内的整数建立一个单链表,显示该单链表中的数据元素;
2.随机产生10个100以内的整数建立一个单链表,显示该单链表中的数据元数,随机产生1-10中的任意整数 p ,在单链表中查找第 p 个元素,并显示该元素值;
3.随机产生10个100以内的整数建立一个单链表,显示该单链表中的数据元数,输入单链表中任一元素,查找并显示该元素在单链表中的位置;
4.随机产生10个100以内的整数建立一个单链表,显示该单链表中的数据元数,将55插入到第7个元素位置,并显示更新后的单链表;
5.随机产生10个100以内的整数建立一个单链表,显示该单链表中的数据元数,输入单链表中任一元素,删除该元素,并显示更新后的单链表;

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;
template <typename DataType>
class Node {
public:
	DataType data;
	Node<DataType>* next;
};
template <typename DataType>
class LinkList {
private:
	Node<DataType>* first;
public:
	LinkList();
	~LinkList();
	void CreateList(int n);
	void Display();
	DataType GetElement(int pos);
	int LocateElement(DataType value);
	void Insert(int pos, DataType value);
	void Delete(DataType value);
};
template <typename DataType>
LinkList <DataType> ::LinkList()
{
	first = new Node<DataType>;
	first->next = nullptr;
}
template <typename DataType>
LinkList<DataType> ::~LinkList()
{
	Node<DataType>* current = first;
	while (current != nullptr)
	{
		Node <DataType>* newnode = current->next;
		delete current;
		current = newnode;
	}
}
template <typename DataType>
void LinkList <DataType>::CreateList(int n)
{
	srand((unsigned)time(0));
	for (int i = 0; i < n; i++)
	{
		Node <DataType>* newNode = new Node<DataType>;
		newNode->data = rand() % 100;
		newNode->next = first->next;
		first->next = newNode;
	}
}
template <typename DataType>
void LinkList<DataType>::Display()
{
	Node <DataType>* current = first->next;
	while (current != nullptr)
	{
		cout << current->data << '\t' ;
		current = current->next;
	}
	cout << endl;
}
template <typename DataType>
DataType LinkList<DataType>::GetElement(int pos)
{
	Node<DataType>* current = first->next;
	int count = 1;
	if (pos > 10 || pos < 0) return -1;
	while (current != nullptr && count < pos)
	{
		current = current->next;
		count++;
	}
	return current->data;
}
template <typename DataType>
int LinkList<DataType>::LocateElement(DataType value)
{
	Node <DataType>* current = first->next;
	int count = 1;
	while (current != nullptr)
	{
		if (current->data == value)
		{
			return count;
		}
		count++;
		current = current->next;
	}
	return count = -1;
}
template <typename DataType>
void LinkList<DataType>::Insert(int pos, DataType value)
{
	Node<DataType>* current = first, * s = nullptr;
	int count = 1;
	while (current!= nullptr && count < pos)
	{
		current = current->next;
		count++;
	}
	if (current == nullptr) throw"插入位置错误";
	else
	{
		s = new Node<DataType>; s->data = value;
		s->next = current->next;
		current->next = s;
	}
	
}
template <typename DataType>
void LinkList<DataType>::Delete(DataType value)
{
	Node<DataType>* current = first, * s = nullptr, * p1 = nullptr;;
	DataType  x;
	
	while (current->data !=value&&current!=nullptr )
	{
		p1 = current;
		current = current->next;
	}
	current = p1;
	
 
		s = current->next; x = current->data;
		current->next = s->next;
	
	delete s;
}
int main()
{
	LinkList<int> list;
	list.CreateList(10);
	list.Display();
	cout << "请输入要查找元素的下标" << endl;
	int c1;
	cin>>c1;
	if (list.GetElement(c1) != -1) cout << "元素" << list.GetElement(c1) << endl;
	else cout << "查找元素失败" << endl;
	cout << "请输入要查找位置的元素" << endl;
	int c2;
	cin >> c2;
	cout << "位置" << list.LocateElement(c2) << endl;
	cout << "请输入要插入元素的下标" << endl;
	int c3;
	cin >> c3;
	cout << "请输入要插入的元素" << endl;
	int c4;
	cin >> c4;
	list.Insert(c3, c4);
	list.Display();
	int c5;
	cout << "请输入要删除的元素" << endl;
	cin >> c5;
	list.Delete(c5);
	list.Display();
	return 0;
}

上一篇:前端三剑客 —— CSS (第五节)