linklist.cpp

数据机构中的双向链表

#include <iostream>
using namespace std;

struct node
{
	int data;
	struct node *next;
	struct node *front;
};

class ADTDualLink
{
	struct node  head;
	public:
		ADTDualLink()
		{
			head.data=0;
			head.next=NULL;
			head.front=NULL;
		}

		ADTDualLink(int a[],int len)
		{
			struct node *newnode;
			head.data=0;
			head.next=NULL;
			head.front=NULL;
			
			newnode=(struct node *)malloc(sizeof(struct node));
			
			newnode->data=a[0];
			
			newnode->next=head.next;
			newnode->front=&head;
			head.next=newnode;
			head.data++;


			for(int i=1;i<len;i++)
			{
				newnode=(struct node *)malloc(sizeof(struct node));
				
				newnode->data=a[i];

				newnode->next=head.next;
				newnode->front=&head;

				head.next->front=newnode;
				head.next=newnode;

				head.data++;
			}
		}

		int GetElement(int i)
		{
			struct node *p;

			p=&head;

			if(i>head.data)
				return(0);

			for(int j=1;j<=i;j++)
				p=p->next;

			return(p->data);
		}

		int GetLengthofLink()
		{
			return(head.data);
		}

		void LinkInsert(int i,struct node *e)
		{
			struct node *p;
			p=&head;

			if(i>head.data) i=head.data+1;
			
			for(int j=1;j<=i;j++)
				p=p->next;

			e->next=p;
			e->front=p->front;

			p->front->next=e;
			p->front=e;

			head.data++;
		}

		int LinkDelete(int i)
		{
			struct node *p;
			
			p=&head;
			
			for(int j=1;j<=i;j++)
				p=p->next;

			p->front->next=p->next;
			p->next->front=p->front;
			
			int data=p->data;
			free(p);
			return(data);
			head.data--;
		}

		int LinkLocate(int e)
		{
			struct node *p;
			p=head.next;
			
			int i=1;
			
			while(e!=p->data && i<=head.data)
			{
				p=p->next;
				i++;
			}

			if(e==p->data)
				return(i);
			else
				return(0);
		}
};

void main()
{
	int a[]={1,3,5,7,9};
	int b[]={2,4,5,6,7};

	ADTDualLink link1(a,5),link2(b,5);

	for(int i=1;i<=link1.GetLengthofLink();i++)
	{
		cout<<"Link 1 data of "<<i<<" is "<<link1.GetElement(i)<<endl;
	}

	for(i=1;i<=link2.GetLengthofLink();i++)
	{
		cout<<"Link 2 data of "<<i<<" is "<<link2.GetElement(i)<<endl;
	}

	struct node *newnode;
	
	for(i=1;i<=link1.GetLengthofLink();i++)
	{
		int e=link1.GetElement(i);		
		
		if(link2.LinkLocate(e)==0)
		{
			newnode=(struct node *)malloc(sizeof(struct node));
			
			newnode->data=e;
			newnode->next=NULL;
			newnode->front=NULL;

			link2.LinkInsert(1,newnode);
		}
	}

	
	for(i=1;i<=link2.GetLengthofLink();i++)
	{
		cout<<"Link 2 data of "<<i<<" is "<<link2.GetElement(i)<<endl;
	}

}