数据结构学习记录1(单链表)

**

数据结构(C++)学习记录1(单链表)

**
才开始学习数据结构,开始用博客记录一下学习过程,方便以后复习。写的单链表的代码可能功能还不太完善,还有很多不足,以后应该会回过头来优化。要是有大佬碰巧看到了希望能提点建议。代码如下:

#include<iostream>
using namespace std;
//生成对象a指向first,而first的成员才有link和data,一定不要搞错,因为这样的错误又基础又有点隐晦,而且编译也能通过,但得不到想要的结果
struct Node {    //链表结点
	int data;
	Node* link;
	Node()
	{
		this->link = NULL;
		this->data = 0;
	}
	Node(const int& data, Node* link = NULL)
	{
		this->data = data;
		this->link = link;
	}
};

class Link :public Node {     //单链表
public:
	Node* first;
	Link()
	{
		first = new Node;
	}
	Link(const int& d)
	{
		first = new Node(d);
	}
	int lenth();  //返回列表长度,要加上first
	Node* Locate(int i);  //定位,返回地址
	bool Create(int d);  //创造一个新结点
	bool Search(int d);  //输入查找值,返回个数和位置
	bool Insert(int i, int d);  //插入新节点,传递index和data
	bool Remove(int i);  //传递index,删除该结点
	bool MakeEmpty();  //清空单链表
	void SetData(int i, int d);  //重置结点的值,传递index和data
	void GetValue(int i);  //得到结点值
	void GetValue(int i,int r);  //传递index和range,得到结点值
	void GetValue();  //得到所有的结点值
};

int Link::lenth()
{
	int lenth = 1;
	Node* current = first;
	while (current->link != NULL)
	{
		lenth++;
		current = current->link;
	}
	return lenth;
}

Node* Link::Locate(int i)
{
	if (i < 0||i>this->lenth())
	{
		cout << "error when locating !" << endl;
		exit(1);
	}
	int count = 0;
	Node* current = first;
	while (count < i && current->link != NULL)
	{
		current = current->link;
		count++;
	}
	return current;
}

bool Link::Create(int d)
{
	Node* current = Locate(lenth());
	Node* newnode = new Node(d);
	if (newnode == NULL && current == NULL)
	{
		cout << "存储分配错误" << endl;
		exit(1);
	}
	current->link = newnode;
	return true;
}
bool Link::Search(int d)
{
	int lenth = this->lenth();
	int count = 0;
	int* array = new int[lenth];  //动态建立数组记录相同元素的位置
	Node* current = first;
	for (int i = 0; i < lenth; i++)
	{
		if (current->data == d)
		{
			array[count] = i;
			count++;
		}
		current = current->link;
	}
	if (count == 0)  //控制界面输出
	{
		cout << "The link has no the same element" << endl;
	}
	else if (count == 1)
	{
		cout << "The link has only one " << count << " element,";
		cout << "and the position is " << array[0] << endl;
	}
	else
	{
		cout << "The link has " << count << " elements ";
		cout << "and the positions are ";
		for (int i = 0; i < count; i++)
		{
			cout << array[i] << ' ';
		}
		cout << '.' << endl;
	}
	delete[]array;
	return true;
}

bool Link::Insert(int i, int d)
{
	if (i<0 || i>this->lenth())
	{
		cerr << "error when inserting !";
		exit(1);
	}
	Node* current = this->Locate(i-1);
	Node* newnode = new Node(d);
	if (newnode == NULL)
	{
		cerr << "error when creating new node !";
		exit(1);
	}
	newnode->link = current->link;
	current->link = newnode;
	return true;
}

bool Link::Remove(int i)
{
	if (i<0 || i>this->lenth())
	{
		cerr << "error when remove the element you want !" << endl;
		exit(1);
	}
	Node* current = this->Locate(i - 1);
	Node* del = new Node;
	del = current->link;
	current->link = del->link;
	delete del;
	return true;
}

bool Link::MakeEmpty()
{
	int count = 0;
	Node* current = first;
	while (count < this->lenth())
	{
		count++;
		Node* del = new Node;
		if (del == NULL)
		{
			cerr << "error when creating a new node !" << endl;
			exit(1);
		}
		del = current->link;
		current->link = del->link;
		delete del;
	}
	delete first->link;
	first->link = NULL;
	return true;
}
void Link::SetData(int i, int d)
{
	if (i<0 || i>this->lenth())
	{
		cerr << "error when setting data !";
		exit(1);
	}
	else
	{
		Node* current = this->Locate(i);
		current->data = d;
	}
}

void Link::GetValue(int i)
{
	if (i<0 || i>this->lenth())
	{
		cerr << "error when getting value" << endl;
		exit(1);
	}
	Node* current = this->Locate(i);
	cout<<current->data<<endl;
}
void Link::GetValue(int i, int r)
{
	if (i<1 || i + r>this->lenth())
	{
		cerr << "gived wrong range,causing error when get value !" << endl;
		exit(1);
	}
	Node* current = this->Locate(i);
	for (int count = i; count < i + r + 1; count++)
		{
			cout << current->data << ' ';
			current = current->link;
		}
	cout << endl;
}

void Link::GetValue()
{
	Node* current = first;
	while (current != NULL)
	{
		cout << current->data<<' ';
		current = current->link;
	}
	cout << endl;
}
int main()  //一些测试
{
	Link* a = new Link;  //a指向first,first的成员才有link和data
	cout <<"first data: "<< a->data <<endl;
	for (int i = 1; i < 4; i++)
	{
		a->Create(i);
	}  //创建3个结点,共四个(要算first)
	cout << "a->lenth(): "<< a->lenth() << endl;
	cout << "a->Search(1)调用结果(如上): " << a->Search(1)<<endl;
	cout << "a->Insert(1, 3)调用结果(如下):" << a->Insert(1, 3)<<endl;
	cout << "a->GetValue() :";
	a->GetValue();
	cout << "a->Remove(2) :"<<endl;
	a->Remove(2);
	cout << "a->GetValue() :"; 
	a->GetValue();
	cout << "a->GetValue(1) :";
	a->GetValue(1);
	cout << "a->GetValue(1, 2) :";
	a->GetValue(1, 2);
	a->MakeEmpty();
	cout << "清空表后观察链表的长度: ";
	cout << a->lenth() << endl;
	a->GetValue();
	return 0;
}
上一篇:Java中lenth、lenth()和size()的区别是什么?


下一篇:python数据类型之int