双链表

问题：在分配空间时，遇到问题

定义一个结构体：

typedef struct dLinkListNode
{
 int data;
 struct dLinkListNode *prior;
 struct dLinkListNode *next;
}*dLinkList,dListNode;

 dList=(dLinkList)malloc(sizeof(dListNode));与dList=(dLinkList)malloc(sizeof(dLinkList));是不一样的，即指针和结构体的大小不一样，不要想当然。

指针的问题真的小心，一不小心就出错。

代码：

#include <iostream>
#include <cstdlib>
using namespace std;

typedef struct dLinkListNode
{
	int data;
	struct dLinkListNode *prior;
	struct dLinkListNode *next;
}*dLinkList,dListNode;

void CreateDlinklist(dLinkList &dList)    //尾插入法建立双链表
{
	 dLinkList node;
	 int elem;
	 dList=(dLinkList)malloc(sizeof(dListNode));
	 if(!dList)
	 {
		 cout<<"allocate fail"<<endl;
	 }
	 else
	 {
	 dList->data=0;
	 dList->next=NULL;
	 dList->prior=NULL;
	 }
	 cin>>elem;
	 while(elem!=EOF)
	 {
		 node=(dLinkList)malloc(sizeof(dListNode));
		 if(!node)
		 {
			 cout<<"allocate fail"<<endl;
			 exit(-1);
		 }
		 else
		 {
	   if(dList->next==NULL)
	   {
		 node->data=elem;
		 node->next=dList->next;
		 dList->next=node;
		 node->prior=dList;
	   }
	   else
	   {
		   node->data=elem;
		   node->next=dList->next;
		   dList->next->prior=node;
		   dList->next=node;
		   node->prior=dList;
	   }
		 cin>>elem;
		 }
	 }

}
void insertDNode(dLinkList dList,int elem)
{
	dLinkList node,pre,tempNode;
	node=(dLinkList)malloc(sizeof(dListNode));
	if(node==NULL)
	{
		cout<<"allocate fail"<<endl;
		exit(0);
	}
	else
	{
	node->data=elem;
	node->next=NULL;
	node->prior=NULL;
	}
	pre=dList;
	tempNode=dList->next;
	while(tempNode)
	{
		if(tempNode->data<elem)
		{
			pre=tempNode;
			tempNode=tempNode->next;
			if(tempNode==NULL)
	       {
		      pre->next=node;
		      node->prior=pre;
		      node->next=NULL;
	       }
		}
		else
		{
			node->next=pre->next;
			pre->next->prior=node;
			pre->next=node;
			node->prior=pre;
			break;
		}
	}
	
	    

}

void deleteDNode(dLinkList dList,int elem)
{
	dLinkList node,pre;
	pre=dList;
	node=dList->next;
	while(node)
	{
		if(node->data==elem)
		{
			pre->next=node->next;
			node->next->prior=pre;
			break;
		}
		else
		{
			pre=node;
			node=node->next;
			if(node==NULL)
			{
				cout<<"there is no the element"<<endl;
			}
		}
	}
}
void display(dLinkList dList)
{
	dLinkList node;
	node=dList->next;
	while(node)
	{
		if(node->next==NULL)
		{
			cout<<node->data;
		}
		else
		{
		    cout<<node->data<<"->";
		}
		node=node->next;
	}
	cout<<endl;
}

int main()
{
	dLinkList dList;
	cout<<"创建双链表:"<<endl;
	CreateDlinklist(dList);
	cout<<"输出双链表"<<endl;
	display(dList);

	deleteDNode(dList,3);
	cout<<"输出双链表"<<endl;
	display(dList);

	insertDNode(dList,9);      //插入元素
	cout<<"输出双链表"<<endl;
	display(dList);
	return 0;
}

运行结果：