데이터 구조의 양 방향 순환 링크 (엄 울 민 데이터 구조 정리 참조)

#include
using namespace std;

typedef int ElemType;
typedef struct DNode
{
	ElemType data;
	DNode *pPrior;
	DNode *pNext;
}DNode;
typedef DNode * DLink;

void InitList(DLink &L)
{
	L = new DNode;
	L->pNext = L->pPrior = L;
}

void DestroyList(DLink &L)
{
	DLink q = NULL, p = L->pNext;
	while (p != L)
	{
		q = p->pNext;
		delete p;
		p = q;
	}
	delete L;
	L = NULL;
}

void ClearList(DLink &L)
{
	DLink q, p = L->pNext;
	while (p != L)
	{
		q = p->pNext;
		delete p;
		p = q;
	}
	L->pNext = L->pPrior = L;
}

bool ListEmpty(DLink L)
{
	if (L->pNext == L&&L->pPrior == L)
		return true;
	else
		return false;
}

int ListLength(DLink L)
{
	int i = 0;
	DLink p = L->pNext;
	while (p != L)
	{
		++i;
		p = p->pNext;
	}
	return i;
}

bool GetElem(DLink L, int pos, ElemType &e)
{
	int i = 1;
	DLink p = L->pNext;
	while (p != L&&i < pos)
	{
		p = p->pNext;
		++i;
	}
	if (p == L || i > pos)
		return false;
	else
	{
		e = p->data;
		return true;
	}
}

DLink GetElemP(DLink L, int pos)
{
	int i;
	DLink p = L;
	for (i = 1; p&&i <= pos; ++i)
		p = p->pNext;
	return p;
}

int LocateElem(DLink L, ElemType e)
{
	int i = 0;
	DLink p = L->pNext;
	while (p != L)
	{
		++i;
		if (e == p->data)
			return i;
		else
			p = p->pNext;
	}
	return 0;
}

bool PriorElem(DLink L, ElemType cur_e, ElemType &pre_e)
{//cur_e      
	DLink p = L->pNext;
	if (p != L)
	{
		p = p->pNext;//if(p!=L), p       
		while (p != L)
		{
			if (p->data == cur_e)
			{
				pre_e = p->pPrior->data;
				return true;
			}
			p = p->pNext;
		}
	}
	return false;
}

bool NextElem(DLink L, ElemType cur_e, ElemType &next_e)
{//cur_e       
	DLink p = L->pNext;
	if (p != L)
	{
		p = p->pNext;//p      
		while (p != L)
		{
			if (p->pPrior->data == cur_e)
			{
				next_e = p->data;
				return true;
			}
			else
				p = p->pNext;
		}
	}
	return false;
}

bool ListInsert(DLink L, int pos, ElemType e)
{
	DLink p, q;
	if (pos<1 || pos>ListLength(L)+1)
		return false;
	else
	{
		p = GetElemP(L, pos - 1);//   pos-1      
		if (!p)
			return false;
		q = new DNode;
		q->data = e;
		q->pPrior = p;
		q->pNext = p->pNext;
		p->pNext->pPrior = q;
		p->pNext = q;
		p = q = NULL;
		return true;
	}
}

bool ListDelete(DLink L, int pos, ElemType &e)
{
	DLink p;
	if (pos<1 || pos>ListLength(L))
		return false;
	p = GetElemP(L, pos);//  pos     
	if (!p)
		return false;
	e = p->data;
	p->pPrior->pNext = p->pNext;
	p->pNext->pPrior = p->pPrior;
	delete p;
	p = NULL;
	return true;
}

void ListPrintDe(DLink L)
{
	DLink p = L->pPrior;
	while (p != L)
	{
		cout << p->data << " ";
		p = p->pPrior;
	}
	cout << endl;
}

void ListPrintAs(DLink L)
{
	DLink p = L->pNext;
	while (p != L)
	{
		cout << p->data << " ";
		p = p->pNext;
	}
	cout << endl;
}


int main(void)
{
	DLink L;
	ElemType e;
	InitList(L);
	ListInsert(L, 1, 1);
	ListInsert(L, 2, 2);
	ListInsert(L, 3, 3);
	ListInsert(L, 4, 4);
	ListInsert(L, 5, 5);
	ListInsert(L, 6, 6);
	ListInsert(L, 7, 7);
	ListPrintAs(L);
	GetElem(L, 2, e);
	cout << e << endl;
	ListDelete(L, 7, e);
	cout << e << endl;
	ListPrintAs(L);
	ListPrintDe(L);
	cout << LocateElem(L, 3)<

좋은 웹페이지 즐겨찾기