双向链表的初始化，建立，添加节点和删除节点（注意插入和删除要分三种情况）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
/*双向循环链表*/
#include "declaration.h"
typedef struct DulNode
{
int data;
struct DulNode *next,*prior;
}DulNode,*DulLinkList;
Status InitList_DUL(DulLinkList &L)//初始化一个带头结点的双向循环链表,ok
{
L=(DulNode*)malloc(sizeof(DulNode));
L->next=L;
L->prior=L;
if (!L)
exit(OVERFLOW);
return OK;
}
void DestoryList_DUL(DulLinkList &L)//销毁一个带头结点的双向循环链表,ok
{
DulNode *p;
while(L)
{
p=L->next;
free( L);
L=p;
}
}
void CreateList_DUL(DulLinkList &L)//正序创建一个带头结点的双向循环链表,ok
{
DulLinkList p,s;//中间变量
int n,i;
printf("input Length: n");
scanf("%d",&n);
p=L;
printf("input value with enter:");
for(i=n;i>0;i--)
{
s=(DulLinkList)malloc(sizeof(DulNode));
scanf("%d",&s->data);
p->next=s;
s->prior=p;
p=s;
}
p->next=L;
L->prior=p;
}
DulLinkList LocateELem_DUL(DulLinkList L,ElemType x)
{//定位值为e的结点的位置
DulNode *p;
p=L->next;
while(p!=L)
{
if(!compare(x,p->data))
return p;
p=p->next;
}
printf("the element is not existsn");
return NULL;
}
Status InsertAfter_DUL(DulLinkList &L,ElemType y)//在带头结点的双向循环链表中的x值后插入y值,李大友2.15
{
DulLinkList p,s;
ElemType x;
printf("value you want to find is :");
scanf("%d",&x);
p=LocateELem_DUL(L,x);
if(!p)
{
printf("%d not exists.n",x);
return ERROR;
}
s=(DulLinkList)malloc(sizeof(DulNode));
s->data=y;
s->next=p->next;
p->next->prior=s;
p->next=s;
s->prior=p;
return OK;
}//LinkList_L
//删除
DulNode* deleteTheNode(DulNode* head,int num)
{
DulNode* p1,*p2;
p1=head;
while (p1->next&&num!=p1->data)
{
p1=p1->next;
}
if (num==p1->data)
{
if (p1==head)//找到的是头节点
{
head=head->next;
head->prior=NULL;
}
else if(p1->next)//不是头结点,也不是尾节点
{
p1->next->prior=p1->prior;
p1->prior->next=p1->next;
}
else
{
p1->prior->next=NULL;
free(p1);
}
}
else
{
//cout<<"节点未找到"<<endl;
printf("节点未找到");
}
return head;
}
//主函数如下
void main()
{
DulLinkList p;
DulLinkList L;
InitList_DUL(L);
//	NCreateList_L(L);//逆位序建立链表
CreateList_DUL(L);//正序建立双向循环链表
ListTraverse_DUL(L);
//	ListPrint_L(L);
//	Reverse_DulLinkList(L);//OK
//	ListTraverse_DUL(L);
//	ListPrint_DUL(L);
ElemType y;
printf("the insert value is :");
scanf("%d",&y);
//	InsertBefore_DUL(L,y);//OK
InsertAfter_DUL(L,y);
//OK
ListTraverse_DUL(L);
//	ListPrint_DUL(L);
ElemType z;
printf("the delete value is :");
scanf("%d",&z);
deleteTheNode(L,z);
ListTraverse_DUL(L);
}