C++資料結構 ---- 循環單連結清單

環境配置

codeblocks

windows10

項目結構

代碼

CLinkListClass.h

#ifndef _CLINKLISTCLASS_H_
#define _CLINKLISTCLASS_H_

#include <iostream>

template <typename T>
class LinkListNode
{
public:
	T data;
	LinkListNode<T> *next;
};
template <typename T>
class CLinkListClass
{
public:
	CLinkListClass(void);
	~CLinkListClass(void);
	bool CreateListF(const T *a, int n) const;
	bool CreateListR(const T *a, int n);
	void Display(void) const;
	int ListLength(void) const;
	bool GetElem(int i, T &e) const;
	bool LocateElem(const T &e, int &i) const;
	bool ListInsert(int i, const T &e) const;
	bool ListDelete(int i) const;
protected:
private:
	LinkListNode<T> *rear;
};

template <typename T>
CLinkListClass<T>::CLinkListClass(void)
{
	rear = new LinkListNode<T>;
	rear->next = rear;
}
template <typename T>
CLinkListClass<T>::~CLinkListClass(void)
{
	LinkListNode<T> *p = rear;
	LinkListNode<T> *q = rear->next;

	while (q != rear)
	{
		delete p;
		p = q;
		q = q->next;
	}

	delete p;
}
template <typename T>
bool CLinkListClass<T>::CreateListF(const T *a, int n) const
{
	if (n < 0)
	{
		return false;
	}

	LinkListNode<T> *p;

	for (int i = 0; i < n; ++i)
	{
		p = new LinkListNode<T>;	// 尾節點和尾指針都不變, 頭插法
		p->data = a[i];
		p->next = rear->next;
		rear->next = p;
	}

	return true;
}

template <typename T>
bool CLinkListClass<T>::CreateListR(const T *a, int n)
{	// 修改了rear
	if (n < 0)
	{
		return false;
	}

	LinkListNode<T> *p = rear;

	for (int i = 0; i < n; ++i)
	{
		p->data = a[i];	// 尾節點變資料節點
		p->next = new LinkListNode<T>;	// 新節點做尾節點
		p = p->next;
	}

	p->next = rear;	// rear此時指向鍊首
	rear = p;	// rear指向尾節點
	return true;
}

template <typename T>
void CLinkListClass<T>::Display(void) const
{
	LinkListNode<T> *p = rear->next;

	while (p != rear)
	{
		std::cout << p->data << " ";
		p = p->next;
	}

	std::cout << std::endl;
}

template <typename T>
CLinkListClass<T>::ListLength(void) const
{
	int i = 0;
	LinkListNode<T> *p = rear->next;

	while (rear != p)	// 确定節點存在後才記錄
	{
		++i;
		p = p->next;
	}

	return i;
}

template <typename T>
bool CLinkListClass<T>::GetElem(int i, T &e) const
{
	if (i < 1)
	{
		return false;
	}

	LinkListNode<T> *p = rear->next;
	int j = 1;

	while (rear != p && j < i)
	{
		p = p->next;
		++j;
	}

	if (rear == p)
	{
		return false;
	}
	else
	{
		e = p->data;
		return true;
	}
}

template <typename T>
bool CLinkListClass<T>::LocateElem(const T &e, int &i) const
{
	LinkListNode<T> *p = rear->next;
	int j = 1;

	while (rear != p && e != p->data)
	{
		p = p->next;
		++j;
	}

	if (rear == p)
	{
		return false;
	}
	else
	{
		i = j;
		return true;
	}
}

template <typename T>
bool CLinkListClass<T>::ListInsert(int i, const T &e) const
{
	LinkListNode<T> *p = rear->next;
	LinkListNode<T> *q;
	int j = 2;	// j == 1單獨讨論, 因為循環條件rear != p很麻煩

	if (i < 1)
	{
		return false;
	}
	else if (i == 1)
	{
		q = new LinkListNode<T>;
		q->data = e;
		q->next = rear->next;
		rear->next = q;
		return true;
	}

	while (rear != p && j < i)
	{
		p = p->next;
		++j;
	}

	if (rear == p)	// 插入位置為1時要單獨考慮
	{
		return false;
	}
	else
	{
		q = new LinkListNode<T>;
		q->data = e;
		q->next = p->next;
		p->next = q;
		return true;
	}
}

template <typename T>
bool CLinkListClass<T>::ListDelete(int i) const
{
	if (i < 1)
	{
		return false;
	}

	LinkListNode<T> *p = rear;
	LinkListNode<T> *q;
	int j = 1;

	while (rear != p->next && j < i)	// 不能删除尾節點
	{
		p = p->next;
		++j;
	}

	if (rear == p->next)
	{
		return false;
	}
	else
	{
		q = p->next;
		p->next = q->next;
		delete q;
		return true;
	}
}

#endif // _CLINKLISTCLASS_H_
           

main.cpp

#include <iostream>
#include "CLinkListClass.h"

using namespace std;

int main(void)
{
	CLinkListClass<int> L1;
	CLinkListClass<int> L2;
	const int n = 10;
	int a[n] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
	int i = 1;
	int e;

	L1.CreateListF(a, n);
	L2.CreateListR(a, n);

	cout << "L1: " << endl;
	L1.Display();
	cout << "L2: " << endl;
	L2.Display();

	L1.GetElem(i, e);
	cout << "L1: i = 1, e = " << e << endl;
	L2.LocateElem(e, i);
	cout << "L2: e = " << e << ", i = " << i << endl;

	L1.ListInsert(11, 0);
	L1.ListDelete(1);
	L2.ListInsert(1, 0);
	L2.ListDelete(11);

	cout << "L1: " << endl;
	L1.Display();
	cout << "L2: " << endl;
	L2.Display();

	cout << "L1.length = " << L1.ListLength() << endl;

	system("PAUSE");
	return 0;
}