//雙向鏈表的類型描述 
typedef int ElemType; 
typedef struct node{ 
 ElemType data; 
 struct node *prior,*next; 
}DuLNode,*DuLinkList; 

//頭插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表 
DuLinkList Create_DLinkListF(int n){ 
 DuLinkList L,p; 
 int i = n - 1; 
 ElemType x; 
 //新建頭結(jié)點(diǎn) 
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 //添加第一個(gè)結(jié)點(diǎn) 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 //加入其他結(jié)點(diǎn) 
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 p->next = L->next; 
 L->next->prior = p; 
 p->prior = L; 
 L->next = p; 
 
 i--; 
 } 
 return L; 
} 

//尾插法創(chuàng)建帶頭結(jié)點(diǎn)的雙向鏈表 
DuLinkList Create_DLinkListR(int n){ 
 DuLinkList L,p,lastNode; 
 int i = n - 1; 
 ElemType x; 
 //新建頭結(jié)點(diǎn) 
 L = (DuLinkList)malloc(sizeof(DuLNode)); 
 L->prior = NULL; 
 L->next = NULL; 
 
 //添加第一個(gè)結(jié)點(diǎn) 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 L->next = p; 
 p->prior = L; 
 p->next = NULL; 
 
 lastNode = p; 
 //加入其他結(jié)點(diǎn) 
 while(i > 0){ 
 scanf("%d",&x); 
 p = (DuLinkList)malloc(sizeof(DuLNode)); 
 p->data = x; 
 
 lastNode->next = p; 
 p->prior = lastNode; 
 p->next = NULL; 
 
 lastNode = p; 
 i--; 
 
 } 
 return L; 
 
} 

//在指定結(jié)點(diǎn)之前插入新結(jié)點(diǎn) 
void Insert_DLinkListBefore(DuLinkList p,ElemType x){ 
 DuLinkList newNode; 
 //判斷結(jié)點(diǎn)p之前的結(jié)點(diǎn)的合法性： 
 if(p->prior == NULL) 
 printf("結(jié)點(diǎn)不合法，不能在該結(jié)點(diǎn)之前插入結(jié)點(diǎn)\n"); 
 else{ 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 newNode->next = p; 
 p->prior->next = newNode; 
 newNode->prior = p->prior; 
 p->prior = newNode; 
 } 
} 

//在指定結(jié)點(diǎn)之后插入新結(jié)點(diǎn) 
void Insert_DLinkListAfter(DuLinkList p,ElemType x){ 
 
 DuLinkList newNode; 
 newNode = (DuLinkList)malloc(sizeof(DuLNode)); 
 newNode->data = x; 
 
 //當(dāng)插入位置是最后一個(gè)結(jié)點(diǎn)之后時(shí) 
 if(p->next == NULL){ 
 p->next = newNode; 
 newNode->prior = p; 
 newNode->next = NULL; 
 } 
 else{ 
 newNode->next = p->next; 
 p->next->prior = newNode; 
 p->next = newNode; 
 newNode->prior = p; 
 } 
} 

//刪除指定結(jié)點(diǎn) 
void Delete_DLinkList(DuLinkList p){ 
 //如果刪除的是最后一個(gè)元素 
 if(p->next == NULL) 
 p->prior->next = NULL; 
 
 else{ 
 p->prior->next = p->next; 
 p->next->prior = p->prior; 
 
 } 
 free(p); 
} 

//后鏈輸出雙向鏈表 
void Print_DLinkListN(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p->next; 
 } 
 printf("\n"); 
 
} 

//前鏈輸出雙向鏈表 
void Print_DLinkListP(DuLinkList p){ 
 
 while(p != NULL){ 
 printf("%d\t",p->data); 
 p = p-prior; 
 } 
 printf("\n"); 
}