数据结构--顺序表

目录

前言

代码

前言

  今天在翻看以前的数据结构顺序表的内容，以前写过一个C语言版本的，今天想来用C++重新完成并且封装了一个通讯录。在C语言的时候由于结构体没有类和对象这个概念，所以结构体和一些需要使用的函数都是分开写的，每次在调用的时候还要将结构体指针传入，(也可以使用引用，但是当时并没有学习到)，而且数据也是公有的，对于数据的保护不高(提到一下，我此次写的顺序表的数据也是公开的，为了方便通讯录的封装，当然可以在顺序表中写函数获取对应的数据提高代码的保护性)。

  写这个小项目虽然不困难，但是也花了两个多小时进行编写和调试修改，其中有意思的是发现了以前一些不会注意到的东西，对于自身来说也能够对顺序表这个部分理解更加深厚。这个项目分为了三个部分，SqList类，实现顺序表的基本功能，PersonInfo类储存联系人的数据，用Contact类来封装整个项目即SqList<T>* SL，在实现Contact类过程中始终保持尽量对SqList类减少修改，因为我觉得这只是封装的一个项，不能因为上层建筑修改下层的地基，总不能封装了另一个类就不支持上一个类，这与c++的核心思想封装冲突了，在这个过程中遇到了一些需要调整的地方。

  例如在构造Contatct类的时候，发现类的自定义成员变量如果是指针不会自动调用构造函数生成对应的指针，而是需要在当前类的构造中new SqList并完成该指针的初始化。为了完成通讯录的增删查改，对于PersonInfo类的>>和<<，==进行了重载，在Print中可以直接cout打印PersonInfo对象的数据内容，而不需要用cout<<info._name<<info._tel...这种很挫的方式实现，也不需要一个个cin>>进入Info中，比较这部分其实还可以写一个仿函数对数据进行比较，但是当时在写查找find这个函数的时候需要特化一个版本，需要单独传一个字符串，所以我选择重载了==用PersonInfo类中的_name和字符串进行比较。但是当我写到后面插入的时候突然想到发现当前的代码联系人是可以重复的，所以我在插入之前进行了find查找是否有相同的name，我一开始想用类似上面的方法用特化的字符串版本的find，但是发现咱总不能每次添加联系人的时候需要先输入一个名字来查重再添加吧，所以为了不增加代码的复杂性，我又重载了一个==，这次比较的是两个PersonInfo类中的_name，因为psuh_back接受到info数据的时候是已经初始化完的一个PersonInfo对象，可以直接用来与原来通讯录中已经存在的其他数据进行比较。我在find的特化版本中增加了一个引用参数pos来返回数据对应的下标位置，方便后续对应操作中通讯录是否为空的一个反馈。对于operator<<（流插入运算符）通常不能作为成员函数重载，原因如下：左操作数类型限制：成员函数的左操作数必须是类本身（如PersonInfo），即a.operator<<(b)等价于a << b，此时a必须是PersonInfo类型。但我们实际使用时是cout << info;，左操作数是ostream，右操作数是PersonInfo，而ostream不是我们能修改的类。

  以上就是我对于该项目重写时的一些思路和理解，以下是我写的代码，如果有误希望大家指出我进行修改，有优化的地方也可以提出.

代码

test.cpp

#include"contact.h"
#include<Windows.h>

void menu()
{
	cout << endl;
	cout << "---------------MENU--------------" << endl;
	cout << "--------1. ADD   contact --------" << endl;
	cout << "--------2.Search contact --------" << endl;
	cout << "--------3.Remove contact---------" << endl;
	cout << "--------4.Modify contact---------" << endl;
	cout << "--------5. Print contact---------" << endl;
	cout << "---------------0.EXIT------------" << endl;
	cout << endl;
}
int main()
{
	Contact<PersonInfo> ct;
	int op = 0;
	do 
	{
		Sleep(500);
		menu();
		cout << "Select an option to proceed: ";
		cin >> op;
		cout << endl;
		switch (op)
		{
			case 1:
			{
				cout << "Input name, address, age, phone (space-separated)" << endl;
				ct.push();
				break;
			}
			case 2:
			{
				cout << "Type the name to find" << endl;
				string str;
				cin >> str;
				int pos=ct.find(str);
				if(pos!=-1)
				{
					cout << ct.getptr()->_data[pos] << endl;
				}
				break;
			}
			case 3:
			{
				cout << "Type the name to delete" << endl;
				string str;
				cin >> str;
				ct.pop(str);
				break;
			}
			case 4:
			{
				cout << "Type the name to change" << endl;
				string str;
				cin >> str;
				ct.change(str);
				break;
			}
			case 5:
			{
				ct.print();
			}
			case 0:
			{
				cout << "------------- Exit --------------" << endl;
				break;
			}
			default:
			{
				cout << "------------Input Erro-----------" << endl;
			}
		}
	} while (op);

	return 0;
}

Contact.h

#pragma once
#include"sqlist.h"
#include<string.h>


struct PersonInfo
{
	PersonInfo()
		:_name(" ")
		, _addr(" ")
		, _age(0)
		, _tel(0)
	{}

	PersonInfo(string name, string addr, int age, int tel)
		:_name(name)
		,_addr(addr)
		,_age(age)
		,_tel(tel)
	{}

	~PersonInfo() = default;//没有内存开辟，直接使用了系统的默认析构

	bool operator==(const PersonInfo& pi)//重载了==用于对比两个PersonInfo对象
	{
		return _name == pi._name;
	}

	bool operator==(const string name)//重载了==用于对比对象和一个字符串
	{
		return _name == name;
	}

	friend ostream& operator<<(ostream& out, const PersonInfo& info);
	friend istream& operator>>(istream& in, PersonInfo& info);

	string _name;
	string _addr;
	int _age;
	long int _tel;
};

//operator<< 应该是非成员函数，因为它的左操作数是 ostream 对象
inline ostream& operator<<(ostream& out, const PersonInfo& info) 
{
	out << "Name:" << info._name << " Addr:" << info._addr
		<< " Age:" << info._age << " Tel:" << info._tel << endl;
	return out;
}

//重载流插入
inline istream& operator>>(istream& in, PersonInfo& info)
{
	in >> info._name >> info._addr >> info._age >> info._tel;
	return in;
}

template<class T>
class Contact
{
public:
	Contact()
		:SL(new SqList<T>())//指针：不会自动构造，必须用new
	{}

	~Contact()
	{
		delete SL;
		SL = nullptr;
	}

	void push()//增加
	{
		T data;
		cin >> data;
		SL->PushBack(data);
	}

	void print()//打印
	{
		SL->Print();
	}

	void pop(const string& name)//删除
	{
		int pos = -1;
		SL->Find(name, pos);
		int size = SL->size();
		if (pos != -1)
		{
			cout << "Sucessly Erase" << endl;
			SL->Erase(pos);
		}
		else
		{
			cout << "Erase False, NO Person" << endl;
		}

	}

	int find(const string& name)//查找
	{
		int pos = -1;
		SL->Find(name,pos);
		if (pos != -1)
		{
			cout << "Sucessly Find : " << endl;
		}
		else
		{
			cout << "No Find" << endl;
		}
		return pos;
	}

	void change(const string& name)//修改
	{
		int pos = -1;
		SL->Find(name, pos);
		int size = SL->size();
		if(pos != -1)
		{
			cin >> SL->_data[pos];
			cout << "Sucessly Change" << endl;
		}
		else
		{
			cout << "Change False, NO Person" << endl;
		}
	}
	SqList<T>* getptr()//获取内部指针
	{
		return SL;
	}
private:
	SqList<T>* SL;
};

SqList.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

template<class T>
class SqList
{
public:
	SqList()
		:_data(nullptr)
		,_size(0)
		,_capacity(0)
	{}

	SqList(const SqList& other) 
		: _data(nullptr)
		, _size(other._size)
		, _capacity(other._capacity) 
	{
		if (_capacity > 0) {
			T* tmp = new T[_capacity];
			for (int i = 0; i < _size; ++i)
			{
				tmp[i] = other._data[i];
			}
			delete[] _data;
			_data = tmp;
		}
	}

	SqList& operator=(const SqList& other) 
	{
		if (this != &other) 
		{
			delete[] _data;
			_size = other._size;
			_capacity = other._capacity;
			_data = (_capacity > 0) ? new T[_capacity] : nullptr;
			for (int i = 0; i < _size; ++i) 
			{
				_data[i] = other._data[i];
			}
		}
		return *this;
	}

	~SqList()
	{
		if(_data)
		{
			delete[] _data;
			_data = nullptr;
		}
		_size = 0;
		_capacity = 0;
		
	}

	void SqCheck()
	{
		if (_size == _capacity)
		{
			int newcapacity = _capacity == 0 ? 4 : 2 * _capacity;
			T* tmp = new T[newcapacity];
			for (int i = 0; i < _size; i++)
			{
				tmp[i] = _data[i];
			}
			delete[] _data;
			_data = tmp;
			_capacity = newcapacity;
		}
	}

	void Print()
	{
		if(!Empty())
		{
			for (int i = 0; i < _size; i++)
			{
				cout << _data[i];
			}
			cout << endl;
		}
		else
			cout << "Empty contact "<<endl;
	}

	bool Empty()
	{
		if (_size == 0)
			return true;
		else
			return false;
	}

	void PushBack(T x)//附带查重功能
	{
		SqCheck();
		int ret = 0;
		ret=Find(x);
		if (!ret)
		{
			_data[_size] = x;
			_size++;
			cout << "Sucessly Add" << endl;

		}
		else
			cout << "Data Exist,Add False" << endl;
	}

	void PushFront(T x)
	{
		SqCheck();
		for (int i = _size; i > 0; i--)
		{
			_data[i] = _data[i-1];
		}
		_data[0] = x;
		_size++;
	}

	void Popback()
	{
		if(!Empty())
		{
			_size--;
		}
		else
			cout << "Empty contact ";
	}

	void PopFront()
	{
		if(!Empty())
		{
			for (int i = 0; i < _size - 1; i++)
			{
				_data[i] = _data[i + 1];
			}
			_size--;
		}
		else
			cout << "Empty contact " << endl;
	}

	void insert(T x,int pos)
	{
		SqCheck();
		for (int i = _size; i > pos; i--)
		{
			_data[i] = _data[i - 1];
		}
		_data[pos] = x;
		_size++;
	}

	void Erase(int pos)
	{
		if(!Empty())
		{
			for (int i = pos; i < _size - 1; i++)
			{
				_data[i] = _data[i + 1];
			}
			_size--;
		}
		else
			cout << "Empty contact ";
	}

	int size()
	{
		return _size;
	}

	bool Find(T x)
	{
		if(!Empty())
		{
			for (int i = 0; i < _size; i++)
			{
				if (_data[i] == x)
				{
					return true;
				}
			}
		}
		return false;
	}

	bool Find(const string& str,int& pos)//为通讯录查找支持特化版本的find
	{
		if(!Empty())
		{
			for (int i = 0; i < _size; i++)
			{
				if (_data[i] == str)
				{
					pos = i;
					return true;
				}
			}
		}
		else
		{
			cout << "Empty contact ";
			return false;
		}
		return false;
	}
public:
	T* _data;
	int _size;
	int _capacity;
};

运行示例