DoublyLinkedList(双向链表)

　　本来还不会写双向链表的，但最近学习了二叉树后，突然意识到这不就是双向链表嘛，然后通过对二叉树的理解，实现了一下双向链表。

　　代码：

#define SIZE 10
DouLL * head, *n, *p;
head =（DouLL * )malloc(sizeof(DouLL));
p = head;　　/* p指针的作用很重要 */
p->Item = 1;
p->prev = p->next = NULL;
for (int i = 1; i < SIZE; i++)
{
n =（DouLL * )malloc(sizeof(DouLL));
n->Item = i + 1;
n->prev = p;　　/* 防止找不到头结点 */
p->next = n;
p = p->next;
}
n->next = NULL;
/* 若要循环应改为: n -> next = head; */
head->prev = NULL; /* head -> prev = n; */

　　code:

//双向链表
#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#define bool int
#define true 1
#define false 0;
typedef struct douLinkList
{
struct douLinkList * next;
//下一个
struct douLinkList * prev;
//前一个
int Item;
}DouLL;
/* 实现插入功能 */
bool InsertLL();
/* 实现删除功能 */
bool deleteLL();
bool InsertLL(DouLL * h, int X, int i)
{
DouLL * p;
int j;
j = 1;
while(j < i - 1 && h)
{
h = h -> next;
++ j;
}
p = malloc(sizeof(DouLL));
p -> Item = X;
p -> prev = h;
p -> next = h -> next;
h -> next -> prev = p;
h -> next = p;
return true;
}
bool deleteLL(DouLL * h, int X)
{
DouLL * temp;
if(!h)
{
fprintf(stderr, "链表已空!n");
return false;
}
while(X != h -> Item && h)
{
h = h -> next;
}
temp = h;
h -> prev -> next = h -> next;
h -> next -> prev = h -> prev;
free(temp);
return true;
}
int main()
{
char c;
int i, SIZE, X;
DouLL * head, * n, * p;
puts("初始链表长度:");
scanf("%d", &SIZE);
head = malloc(sizeof(DouLL));
p = head;
p -> Item = rand() % 100 + 50;
p -> prev = p -> next = NULL;
for(i = 1; i < SIZE; i++)
{
n = malloc(sizeof(DouLL));
n -> Item = rand() % 1000 + 50;
n -> prev = p;
p -> next = n;
p = p -> next;
}
n -> next = NULL;
head -> prev = NULL;
puts("1) 显示
2) 删除");
puts("3) 插入
4) 退出");
while(1)
{
c = getch();
if(c == '1')
{
puts("Order:");
p = head;
while(p)
{
printf("%d ", p -> Item);
p = p -> next;
}
printf("NULLn");
puts("ReveOrder:");
p = n;
while(p)
{
printf("%d ", p -> Item);
p = p -> prev;
}
printf("NULLn");
}
if(c == '2')
{
printf("n删除:");
scanf("%d", &X);
p = head;
deleteLL(p, X);
}
if(c == '3')
{
printf("n插入(数据 位置):");
scanf("%d %d", &X, &i);
p = head;
InsertLL(p, X, i);
}
if(c == '4')
break;
}
return 0;
}