双向链表的操作1

双向链表相比较于单链表多了一个前驱指针prior

例1：完成DList  CreateList()函数，该函数创建一个不带头节点的空双向链表，并返回链表

的指针。

#include <stdio.h>
#include <stdlib.h>
typedef  int ElemType;
typedef struct Node * PtrToNode;
typedef PtrToNode Position;
struct DListNode;
typedef DListNode * DList;


typedef struct Node
{
ElemType data; /*数据域*/
PtrToNode previous; /*指向前驱*/
PtrToNode next; /*指向后继*/
}Node;


struct DListNode
{
PtrToNode head; /*指向头节点*/
PtrToNode tail; /*指向尾节点*/
int size;  //链表中数据项数
};
void ClearList(DList L);
int main()
{
    DList L=CreateList();
    /*   此处由测试代码自动添加，在双向链表中插入数据并测试void ClearList(DList L)函数*/
    return 0;
}

DList CreateList()
{
DList L=(DList)malloc(sizeof(DList));//开辟空间
L->head=NULL; //头结点为空
L->tail=NULL;
L->size=0;
return L;
}
void ClearList(DList L) 清空双向链表相当于将链表恢复到最初。代码相似。
{
L->head=NULL;
L->tail=NULL;
L->size=0;
}

例2：双向链表求表长度与单链表相似。从头结点开始指针往后移，计数变量++。

例3：双向链表的销毁即将节点前驱后继域置为空，并且free。

例4：双向链表的正序输出

p=L->head; p=p->next;

双向链表的逆序输出

p=L->tail; p=p->previous;

例5：完成Position Locate(DList L,ElemType x);函数，该函数在双向链表中按从头到尾的顺序查找是否存在结点的数值为x，如果存在返回该结点的指针，否则返回NULL，其中L是一个不带头节点的空双向链表。

Position Locate(DList L,ElemType x)
{
	Node *p;
	p=L->head;
	while(p!=NULL&&p->data!=x)
	{
		p=p->next;
	}
	if(p==NULL)
	{
		return NULL;
	}
	else
	return p;
}

例6：完成Position GetItem(DList L,int k)函数，该函数在双向链表中按从头到尾的顺序查找链表中的第k(从1开始计数)个节点，如果存在返回该结点的指针，否则返回NULL，其中L是一个不带头节点的空双向链表。

Position GetItem(DList L,int k)
{
	Node *p;
	int i=0;
for(p=L->head;p!=NULL;p=p->next)
{
	i++;
	if(i==k) 
	return p;
}
	return NULL;
}
例7：完成void InsertAtHead(DList L,ElemType x)函数，该函数在双向链表的表头的插入一个结点，该结点数据为x，其中L是一个不带头节点的双向链表。

void InsertAtHead(DList L,ElemType x)         //插入第一步申请新的节点。
{
	Node *p,*q;
	p=(Node*)malloc(sizeof(Node));
	p->data=x;
if(L->head==NULL)           //考虑初始为空链表
{
	L->head=p;
	L->tail=p;
	L->size=1;
}
p->next=L->head;
L->head->previous=p;
L->head=p;
}