數據結構-線性表的一些基礎操作 c++代碼

數據結構-線性表的一些基礎操作 c++代碼

//線性表的順序存儲結構
template 
class Linearlist
{
	public:
		Linearlist(int MaxListSize == 10);
		~Linearlist() 
		{
			delete []element;
		}

		bool IsEmpty() const 
		{
			return length == 0;
		}
		bool IsFull() const 
		{
			return length == MaxSize;
		}
		int Length() const 
		{
			return length;
		}

		bool Find(int k, T &item) const;
		int search(const T &item) const;
		void Delete(int k, T &item);
		void Insert(int k, const T &item);
	private:
		int MaxSize, length, T *element;
};

template 
Linearlist::Linearlist(int MaxListSize == 10)
{
	MaxSize = MaxListSize;
	element = new T[MaxSize];   //申請規模為MaxSize的數組空間
	length = 0;                // 初始時沒有真正的表結點，故表長度為0
}

//存取：將下標為k的結點的字段值賦給item並返回true,若不存在則返回false;
template 
bool Linearlist::Find(int k, T &item)  const
{
	if (k < 0 || length == 0 || k >length-1)
	{
		cout << " unreasonable position or empty list!" << endl;
		return false;
	}
	else
	{
		item = element[k];
		return true;
	}
}

//查找：在表中查找字段值為item的結點並返回其下標；若表中沒有item，則返回-1；
template 
int Linearlist::search(const T &item) const
{
	for (int k = 0; k <= length-1; k++)
	{
		if(element[k] == item)
			return k;
	}
	return -1;
}

//刪除表中下表為k的結點並將其值賦給item
template 
void Linearlist::Delete(int k, T &item)
{
	if (find(k, item))   //若找到下標為k的結點，則將其後面所有結點均向前移動一個位置
	{
		for (int i=k; i
void Linearlist::Insert(int k, const T &item)
{
	if(IsFull())                   //若表已滿，無法插入新結點
	{
		cout << "The list is full!" << endl;
		exit(1);
	}
	else if (k<0 || k>length-1)
	{
		cout << "The node does not exist!" << endl;
		exit(1);
	}
	else
	{
		for (i=length-1; i>=k+1; i--)
		{
			element[i+1] = element[i];
		}
	}
	element[k+1] = item;
	length++;
}

//單鏈表結點結構SLNode
template
struct SLNode
{
	T data;                      //數據域
	SLNode *next;             //指針域

	SLNode(SLNode *nextNode = NULL)
	{
		next = nextNode;
	}

	SLNode(const T &item, SLNode *nextNode = NULL)
	{
		data = item;
		next = nextNode;
	}
};

// SLNode 的定義參考博文數據結構-棧的一些基礎操作c++代碼
//單鏈表的鏈式存儲結構
template 
class SLList
{
	public:
		SLList(){	head = new SLNode()};   //構造函數，構造一個只有哨位結點的空表
		SLList(T &item);                       //構造函數
		~SLList();
		bool IsEmpty() const {return head->next == NULL;};
		int length() const;
//		bool Find(int k, T &item) const;
		int Search(const T &item) const;
		void Delete(int k, T &item);
		void Insert(int k, const T &item);
	private:
		SLNode *head;
		SLNode *tail;
		SLNode *currptr;
};

//單鏈表的構造函數，生成一個只有哨位結點的空表
template
SLList::SLList()
{
	head = tail = currptr = new SLNode();
	size = 0;
}

//單鏈表的構造函數，生成含有哨位結點和一個表結點的表
template
SLList::SLList(T &item)
{
	tail = currptr = new SLNode(item);         //生成一個表結點
	head = new SLNode(currptr);               //生成哨位結點
	size = 1;
}

//單鏈表的析構函數
template 
SLList::~SLList()
{
	while (!IsEmpty())
	{
		currptr =  head->next;
		head->next = currptr->next;
		delete currptr;
	}
	delete head;
}

//算法Insert
//在當前結點後插入一個data域值為item的結點
template 
void SLList::Insert(const T &item)
{
	currptr->next = new SLNode(item, currptr->next);
	if (tail == currptr)
		tail = currptr->next;
	size++;
}

//在表尾插入一個data域值為item的結點
template 
void SLList::InsertFromTail(const T &item)
{
	tail->next = new SLNode(item, NULL);
	tail = tail->next;
	size++;
}

//在哨位結點後插入
template 
void SLList::InsertFromHead(const T &item)
{
	if(IsEmpty())
	{
		head->next = new SLNode(item, head->next);
		tail = head->next;
	}
	else
	{
		head->next = new SLNode(item, head->next);
	}
	size++;
}

//算法Delete
//刪除當前結點的後繼結點並將其data值返回給變量de_item

template 
bool SLList::Delete(T &de_item)
{
	if(currptr == tail || IsEmpty())
	{
		cout << "No next node or empty list!";
		return false;
	}
	SLNode *temp = currptr->next;
	currptr->next = temp->next;
	size--;
	de_item = temp->data;
	
	if(temp == tail)
		tail = currptr;
	delete temp;
	return true;
}

// 刪除哨位結點後的第一個真正表結點並將其data值返回給變量de_item
template 
bool SLList::DeleteFromHead(T &de_item)
{
	if (IsEmpty())
	{
		cout << "Empty list!";
		return false;
	}

	SLNode *temp = head->next;
	head->next = temp->next;
	size--;
	de_item = temp->data;
	if (temp == tail)
	{
		tail = head;
	}
	delete temp;
	return true;
}

//刪除表尾結點並將其data值返回給變量de_item

template 
bool SLList::DeleteFromTail(T &de_item)
{
	if (IsEmpty())
	{
		cout << "Empty list!";
		return false;
	}
	//令當前指針指向表尾結點的前驅結點
	SetEnd();
	Prev();
	de_item = tail->data;
	currptr->next = NULL;
	size--;
	delete tail;
	tail = currptr;
	return true;
}