데이터 구조 엄 할머니 버 전 - 선형 표 (3) 더 블 순환 링크 전체 소스 코드

데이터 구조 - 선형 표 (3) 더 블 순환 링크 전체 소스 코드

/*
1)            、    ；
*/
#include 
#include 

using namespace std;

typedef int ElemType;

typedef struct Dlinklist{
	
	ElemType data;
	struct Dlinklist *prior;
	struct Dlinklist *next;

}DNode,*DLinkList;

bool create_list(DLinkList &dl);//    
bool trave_dl(DLinkList &dl);//      
bool traved_dl(DLinkList &dl);//      
bool insert_data(DLinkList &dl,ElemType data,int addr);//    
bool delete_data(DLinkList &dl,ElemType data);//           
bool delete_addr(DLinkList &dl,int addr);//            
bool get_addr(DLinkList &dl,ElemType data);//         
bool get_data(DLinkList &dl,int addr);//         


void show();
void switch_channel(int channel);

DLinkList dl;

int main()
{
	int channel;
	int temp;
	ElemType data;
	/*do{
		show();
		cin>>channel;
		system("cls");
		switch_channel(channel);
		system("pause");
		
	}while(1);*/
	cout<<"     "<<endl;
	create_list(dl);
	trave_dl(dl);
	traved_dl(dl);
	cout<<"          ：";
	cin>>temp;
	get_data(dl,temp);
	cout<<"        ：";
	cin>>data;
	cout<<"          ：";
	cin>>temp;
	insert_data(dl,data,temp);
	trave_dl(dl);
	cout<<"         ：";
	cin>>data;
	delete_data(dl,data);//           
	trave_dl(dl);
	cout<<"            ：";
	cin>>temp;
	delete_addr(dl,temp);//            
	trave_dl(dl);
	cout<<"       ：";
	cin>>temp;
	get_addr(dl,temp);//         
	cout<<"     ：";
	cin>>data;
	get_data(dl,data);//         

	return 0;
}

void show()
{
	cout<<endl<<endl<<"\t         
";
	cout<<"\t1--    
";
	cout<<"\t2--      
";
	cout<<"\t3--      
";
	cout<<"\t4--           
";
	cout<<"\t5--           
";
	cout<<"\t6--            
";
	cout<<"\t7--         
";
	cout<<"\t8--         
";

}

void switch_channel(int channel)
{
	switch(channel)
	{
	case 1:
		{
			create_list(dl);
			
		}break;
	case 2:
		{
			trave_dl(dl);

		}break;
	case 3:
		{
			traved_dl(dl);
		}break;
	case 4:
		{
			int addr;
			ElemType data;
			cout<<"        ：";
			cin>>data;
			cout<<"          ：";
			cin>>addr;
			insert_data(dl,data,addr);
			trave_dl(dl);
		}break;	
	case 5:
		{
			ElemType data;
			cout<<"         ：";
			cin>>data;
			delete_data(dl,data);//           
			trave_dl(dl);	
		}break;
	case 6:
		{
			int addr;
			cout<<"          ：";
			cin>>addr;
			delete_addr(dl,addr);//            
			trave_dl(dl);
		}break;
	case 7:
		{	
			ElemType data;
			cout<<"         ：";
			cin>>data;
			get_addr(dl,data);//         

		}break;
	case 8:
		{	
			int addr;
			cout<<"          ：";
			cin>>addr;
			get_data(dl,addr);//         */
		}break;
	
	}


}

//    
bool create_list(DLinkList &dl)
{
	int count;
	cout<<"            ：";
	cin>>count;
	if(count <= 0)
	{
		cout<<"        "<<endl;
		return false;
	}


	dl = new DNode;
	dl->next = dl;
	dl->prior = dl;
	cout<<"    1   ：";
	cin>>dl->data;
	
	DLinkList p = dl;
	int i;
	for(i = 2; i <= count; i++)
	{
		DLinkList q = new DNode;
		
		cout<<"    "<<i<<"   ：";
		cin>>q->data;	
		
		q->prior = p;
		p->next = q;
		p = q;
	}

	dl->prior = p;
	p->next = dl;

	return true;
}
//      
bool trave_dl(DLinkList &dl)
{
	DLinkList p = dl;
	cout<<"      ：";
	do{
		cout<<p->data<<" ";
		p = p->next;
	
	}while(p != dl);
	cout<<endl;
	return true;
}
//      
bool traved_dl(DLinkList &dl)
{
	DLinkList p = dl->prior;
	cout<<"      ：";

	do
	{
		cout<<p->data<<" ";
		p = p->prior;
	
	}while(p != dl->prior);

	cout<<endl;
	return true;
}
//    
bool insert_data(DLinkList &dl,ElemType data,int addr)
{
	if(addr <= 0)
	{
		cout<<"       "<<endl;
		return false;
	}
	
	DLinkList p = dl;
	
	if(addr == 1)
	{
		DLinkList q = new DNode;

		q->data = data;
		q->prior = p->prior;
		p->prior->next = q;
		p->prior = q;
		q->next = p;

		return true;
	}

	int i = 1;

	do{
		p = p->next;
		i++;
		
	}while(i < addr && p != dl);
	
	
	if(p == dl)
	{
		cout<<"    ，      "<<endl;
		DLinkList q = new DNode;
		q->data = data;
		q->prior = p->prior;
		p->prior->next = q;
		q->next = p;
		p->prior = q;
		return true;
	}

	DLinkList q = new DNode;
	q->data = data;
	q->prior = p->prior;
	p->prior->next = q;
	q->next = p;
	p->prior = q;

	return true;
}
//           
bool delete_data(DLinkList &dl,ElemType data)
{
	DLinkList p = dl;
	DLinkList q;

	if(p->data == data)
	{
		q = p;
		p = p->next;
		p->prior = q->prior;
		q->prior->next = p;
		dl = p; 
		delete q;

		return true;
	}

	do{

		p = p->next;
		
	}while(p != dl && p->data != data);

	if(p == dl)
	{
		cout<<"     "<<endl;
		return false;	
	}

	q = p;
	p = p->next;
	p->prior = q->prior;
	q->prior->next = p;

	delete q;

	return true;
}
//            
bool delete_addr(DLinkList &dl,int addr)
{
	if(addr <= 0)
	{
		cout<<"     "<<endl;
		return false;
	}
	
	DLinkList p = dl;
	
	if(addr == 1)
	{
		p->prior->next=p->next;
  		p->next->prior=p->prior;
		dl = p->next;
		delete p;

		return true;
	}

	int i = 1;

	do{
		p = p->next;
		i++;
		
	}while(i < addr && p != dl);
	
	
	if(p == dl)
	{
		cout<<"     "<<endl;

		return true;
	}

	p->prior->next=p->next;
  	p->next->prior=p->prior;
	delete p;

	return true;
}
//         
bool get_addr(DLinkList &dl,ElemType data)
{
	DLinkList p = dl;

	if(p->data == data)
	{
		cout<<"       ：1"<<endl;
		return true;
	}

	int i = 1;

	do{

		p = p->next;
		i++;

	}while(p != dl && p->data != data);

	if(p == dl)
	{
		cout<<"     "<<endl;
		return false;	
	}

	cout<<"       ："<<i<<endl;

	return true;
}
//         
bool get_data(DLinkList &dl,int addr)
{
	if(addr <= 0)
	{
		cout<<"     "<<endl;
		return false;
	}

	DLinkList p = dl;
	int i = 1;
	
	if(addr == 1)
	{
		cout<<"        ："<<p->data<<endl;
		return true;
	}

	//for(i = 1; i < addr && p->next != dl; i++,p = p->next);

	do{
		p = p->next;
		i++;
	}while(i < addr && p != dl);

	if(p == dl)
	{
		cout<<"              "<<endl;
		return true;
	}

	cout<<"        ："<<p->data<<endl;

	return true;
}