双方向チェーンテーブルの関連操作C++実現

循環双方向チェーンテーブルの場合
チェーンテーブルが空かどうかを判断する条件は、head->next=head(ヘッダポインタ)です.
判断*pが最後のノードである条件は、p->next=head

#include<iostream>
using namespace std;

/*     */
typedef struct node
{
	int data;
	struct node *prior;
	struct node *next;

}DNode; 
/*            */
void CreateDLink(DNode *&head)
{
	int x;
	DNode *p,*s;
    s=(DNode *)malloc(sizeof(DNode));
	if(s==NULL)
	{
		cout<<"Fail to malloc the head node!"<<endl;
		
	}
	   s->data=0;
	    s->prior=NULL;
		s->next=NULL; //        head    
	head=s;   //          ：s->next=s->prior=s;
    cout<<"please input the data of the node"<<endl;
  cin>>x;
	while(x!=0)
	{
      p=(DNode *)malloc(sizeof(DNode));
     if(p==NULL)
	 {
        cout<<"Fail to malloc a new  node!"<<endl;
		
	 }
     
	 p->data=x;
	 s->next=p;
	 p->prior=s;
	 p->next=NULL;
	 s=p;

	 
	cin>>x;
	}

}

void PrintLink(DNode *head)
{
	if(head->next==NULL)
	{
		cout<<"The list is NULL"<<endl;
		return ;
	}
	DNode *p;
	p=head->next;
	while(p!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;
		
	}
   cout<<endl;
}
int Length(DNode *head) //      
{
	int len=0;
	DNode * p=head->next;
	while(p!=NULL)
	{
		len++;
		p=p->next;
	}
	return len;

}
DNode * Get(DNode *head,int i) //     i     
{
	int j=0;
	DNode *p=head->next;
	while(j<i&&p!=NULL)
	{
		p=p->next;
		j++;
	}
	if(p!=NULL)
		return p;
	else 
		return NULL;
}
int InsertNode(DNode *head,int x,int i)//  i         
{
	DNode *s,*p;
	s=(DNode *)malloc(sizeof(DNode));
	s->data=x;
	if(i==0)
	{
		s->next=head->next;
		if(head->next!=NULL)
			head->next->prior=s;
		s->prior=head;
		head->next=s;
		
	}
	else
	{
		p=Get(head,i-1); //            
		if(p==NULL)
			return 0;
		else
		{
			s->next=p->next;
			if(p->next!=NULL)
				p->next->prior=s;
			s->prior=p;
			p->next=s;
		}
	}

	return 1;
}

void DeleteNode(DNode *head,int index) //   index   
{
	if(head->next==NULL)
	{
		cout<<"The list is NULL"<<endl;
		return;
	}
	DNode *p,*s/*        */;
	if(index==0)
	{
		s=head->next;
		head->next=s->next;
		if(s->next!=NULL)
			s->next->prior=head;
		 free(s);
	}
	else
	{
		p=Get(head,index-1);
        if(p==NULL)
			cout<<"The Node "<<index<<"is not exist"<<endl;
		else
		{
			s=p->next;
			p->next=s->next;
			if(s->next!=NULL)
				s->next->prior=p;
			free(s);
		}
	}

}
int main(int argc,char *argv[])
{
  DNode *head;
  CreateDLink(head); 
  cout<<"     ："<<Length(head)<<endl;
   PrintLink(head);
   cout<<" 3      :"<<Get(head,3)->data<<endl;
 
   cout<<"           ："<<endl;
    int value, index;
	cin>>index>>value;
   InsertNode(head,value,index);
   cout<<"       ："<<endl;
	   PrintLink(head);

	   cout<<"           ："<<endl;
	   cin>>index;
	   DeleteNode(head,index);
   PrintLink(head);
	return 0;
}

検索のコピー
検索のコピー