#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
/*---双向链表的存储结构---*/
typedef int ElemType;
typedef int State;
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
}DuLNode,*DuLinkList;
/*---以下双链表涉及的函数---*/
void InitDul_Node(DuLinkList *LHead,int n);//初始化一个双链表
DuLinkList GetElemP_DuL(DuLinkList *LHead,int i);
ElemType GetLeadNode_Dul(DuLinkList *L);
void ListInsert_DuL(DuLinkList *L,int i,DuLNode *node);//双链表插入函数
State ListDelete_DuL(DuLinkList *L,int i);//双链表删除某个结点
DuLNode* CreateDul_Node(ElemType e);//创建双链表中的结点
int GetLength_DulNode(DuLinkList *L);//获得双链表的长度
State DestoryLink_Dul(DuLinkList *L);
void Dul_Traverse(DuLinkList *L);
void WarnMessage(char *s);
/*---函数实现---*/
void WarnMessage(char *s)
{
printf(s);
}
void InitDul_Node(DuLinkList *LHead,int n){
/*初始化一个双链表，输入n个元素的值，建立带头结点的双链表*LHead*/
if((*LHead = (DuLNode*)malloc(sizeof(DuLNode)))==NULL){
WarnMessage("\nError:Head Node create failed!\n");
exit(0);
}
(*LHead)->next = NULL;
(*LHead)->prior = NULL;
(*LHead)->data = n;/*head Node:数据域为整个链表的长度*/
int i = 1;
DuLinkList current,first,s ;
first = current = NULL;
while(i<n){
if((s = (DuLNode*)malloc(sizeof(DuLNode)))==NULL){
printf("An error occurred when malloc new node\n");
exit(0);
}
if(i == 1){/*第一个结点的创建*/
first = s;
first->data = i++;
first->next = NULL;
first->prior = NULL;
current = first;
}
else{/*其它结点的创建*/
s->data = 3 * i;
s->next = NULL;
current->next = s;
s->prior = current;
current = s;
}
i++;
}
(*LHead)->next = first;//使头结头指向第一个结点
//(*LHead)->prior = current;
}
DuLNode* CreateDul_Node(ElemType e)//创建双链表中的结点
{
DuLNode *p;
if(( p = (DuLNode*)malloc(sizeof(DuLNode))) == NULL){
WarnMessage("error:New Node malloc failed!\n");
exit(0);
}
p->data = e;
p->prior = NULL;
p->next = NULL;
return p;
}
DuLinkList GetElemP_DuL(DuLinkList *LHead,int i){
DuLinkList current = *LHead;
int j = 0;
while(current && j<i-1){
current = current->next;
j++;
}
if(!current||j>i-1){
WarnMessage("input position error!\n");
exit(0);
}
return current;
}
void ListInsert_DuL(DuLinkList *LHead,int i,DuLNode *New_node)//双链表插入函数
{
DuLinkList current;
current = GetElemP_DuL(&(*LHead),i);
if(NULL == current->next){
/*如果是在末尾插入结点*/
current->next = New_node;//新结点作为新的尾结点
New_node->prior = current;//尾结点的前驱指向当前结点
}
else{ /*如果不是在末尾插入结点*/
New_node->next = current->next; //当前结点的后继作为新结点的后继
current->next->prior = New_node;//当前结点后继的前驱指向新结点
current->next = New_node;//将新结点作为当前结点的后继
New_node->prior = current;//当前结点作为新结点的前驱
}
}
ElemType GetLeadNode_Dul(DuLinkList *L){//获得首结点
DuLinkList p = (*L)->next;
return p->data;
}
State ListDelete_DuL(DuLinkList *L,int i)//双链表删除某个结点
{
DuLinkList current;
if(!(current = GetElemP_DuL(&(*L),i+1))){
return ERROR;
}
if( NULL == current->prior ){//如果是第一个结点
(*L)->next = current->next;//头结点指向第二个结点
current->next->prior = NULL;//置空第二个结点(新的首结点)的前驱指针
}
else if( NULL == current->next ){/*如果是删除尾结点*/
current->prior->next = NULL;//将倒数第二个结点的后继置空，以作为新的尾结点
current->prior = NULL;
}
else{ //不是第一个结点
current->prior->next = current->next;//当前结点前驱的后继指向当前结点的后继
current->next->prior = current->prior;//当前结点的后继的前驱指向当前结点的前驱
}
free(current);
return OK;
}
int GetLength_DulNode(DuLinkList *L)//获得双链表的长度
{
int count = 0;
if(NULL == *L){
count = 0;
}
DuLinkList p = *L;
while(p){
p = p->next;
++count;
}
return count;
}
State DestoryLink_Dul(DuLinkList *L)
{/*
**从头结点开始一一释放结点空间
*/
DuLinkList p = (*L)->next;
if(!p){
WarnMessage("\nNO Node to be destoried!\n");
return ERROR;
}
else{
while(p){
/*将结点的数据域和指针域全部置空，然后释放空间*/
DuLinkList current;
current = p;
current->data = 0;
current->prior = NULL;
current->next = NULL;
free(current);
p = p->next;
}
}
return OK;
}
void Dul_Traverse(DuLinkList *L){
DuLNode *p = (*L)->next;
while(p){
printf(" <-%d-> ",p->data);
p = p->next;
}
}
int main()
{
DuLinkList Dul_HeadA=NULL;
printf("Initing:.....\n");
InitDul_Node(&Dul_HeadA,5);
Dul_Traverse(&Dul_HeadA);
printf("\nthe length:%d",Dul_HeadA->data);
printf("\nInsert nodes:\n");
printf("please input the value:");
ElemType val_ins;
scanf("%d",&val_ins);
printf("please input the position:");
ElemType loc_ins;
scanf("%d",&loc_ins);
ListInsert_DuL(&Dul_HeadA,loc_ins,CreateDul_Node(val_ins));
printf("After insert new node:\n");
Dul_Traverse(&Dul_HeadA);
int len = GetLength_DulNode(&Dul_HeadA);
printf("\nthe length:%d",len);
printf("\nThe First Node is:%d",GetLeadNode_Dul(&Dul_HeadA));
printf("\nDelete Node:\n");
int del_id;
printf("please input the location:");
scanf("%d",&del_id);
int res_del = ListDelete_DuL(&Dul_HeadA,del_id);
if(!res_del){
WarnMessage("\ndelete failed!\n");
exit(0);
}
else{
WarnMessage("Success delete!\n");
}
WarnMessage("After delete:\n");
Dul_Traverse(&Dul_HeadA);
printf("\nThe New First Node is:%d",GetLeadNode_Dul(&Dul_HeadA));
printf("\nDestory the DulLink.....");
int des_res = DestoryLink_Dul(&Dul_HeadA);
if(OK == des_res){
WarnMessage("\nThe DulLink Has been destoried!\n");
}
else{
WarnMessage("\nError:Fail to destoried!\n");
}
return 0;
}
|
