dbllist.cpp

自己做的第一个算法程序

#include "ios.h"
#include "iostream.h"
#include "DblList.h"


DblList::DblList(int uniqueVal){
//构造函数：建立双向循环链表的表头结点，包含了一个用于某些特定情况的值。
	first = new DblNode(uniqueVal);
	first->rPtr = first->lPtr = first;
	current =NULL;
}

int DblList::Length() const{
//计算带表头结点的双向循环链表的长度，通过函数返回。
	DblNode *p = first->rPtr;
	int cout = 0;
	while ( p != first ){ p = p->lPtr;	cout++;	}
	return cout;
}

 int DblList::Find(const int &targetData){
//在带表头结点的双向循环链表中寻找其值等于targetData的结点，若找到，则函数放回1，同时current
//指针指向该节点，否则函数返回0。
	DblNode *p = first->rPtr;
	while ( p != first && p->data != targetData) { p = p->rPtr; }	//寻找含targetData的结点
	if ( p != first ) { current = p; return 1; }					//搜索成功，返回1
	return 0;														//没有找到，返回0
}

int DblList::First(){
//若链表非空，则将当前指针指向链表的第一个结点且返回1；若链表空，则令当前指针
//为NULL且返回0。
	if ( ! IsEmpty() ) { current = first->rPtr; return 1; }
	current = NULL; 
	return 0;
}

int DblList::Next(){
//若当前节点有后继结点，则将当前指针指向当前结点的后继节点且返回1，否则令当前指针
//为NULL且返回0。
	if ( current->rPtr == first ){ current = NULL; return 0; }
	current = current->rPtr; return 1;
}

int DblList::Prior(){
//若当前结点有前驱结点，则当前指针指向当前结点的前驱结点且返回1，否则令当前指针
//为NULL且返回0。
	if ( current->lPtr == first ) { current = NULL; return 0; }
	current = current->lPtr; return 1;
}

void DblList::Insert( const int &value){
//建立一个包含有值value的新结点，并将其插入到当前结点之后。
	if (current == NULL)													//原表为空
		current = first->rPtr = new DblNode( value,first,first );
	else{																	//原表非空
			current->rPtr =new DblNode( value, current,current->rPtr );	
			current = current->rPtr;										//新结点成为当前节点
		}
	current->rPtr->lPtr = current;											//完成链接
}

void DblList::Remove(){
//在带表头结点的双向链表中删除当前节点，同时让当前结点指到链表的下一个结点，若被
//删除的结点是链表最后一个结点，则让当前指针知道表中最前端第一个结点。如果删除后
//链表变成空表，则令当前指针为NULL
	if ( current != NULL ){
		DblNode *temPtr = current;
		current = current->rPtr;
		current->lPtr = temPtr->lPtr;
		temPtr->lPtr->rPtr = current;
		delete temPtr;
		if ( current == first )
			if ( IsEmpty() ) current =NULL;
			else current = current->rPtr;
	}
}

void DblList::FindrNode( int i ){
//若当前结点是头结点，则指向头结点的下一个结点
	DblNode *p = current->rPtr; int j = 0;
	while ( j < i )	{
		p = p->rPtr; 
		if ( p == first )	p=p->rPtr;
		j = j++;
	}
	current = p;
}

void DblList::FindlNode( int i ){
//若当前结点是头结点，则指向头结点的下一个结点
	DblNode *p = current; int j = 0;
	while ( j < i )	{
		p = p->lPtr; 
		if ( p == first )	p=p->lPtr;
		j = j++;
	}
	current = p;
}

void DblList::ShowAll(){
//显示所有结点	
	DblNode *p = first->rPtr;
	if (p == first){ cout <<"******表为空!******"; }
	while (p != first){ 
		cout << p->data << " ";
		p = p->rPtr;
	}
	cout << endl;
}

void DblList::ShowNode(){
//显示当前结点的值
	if ( IsEmpty() ) { cout <<"******表为空!******" << endl; }
	cout << current->data << endl; 
}