头文件及结构体定义
#include <stdio.h>
#include <stdlib.h>
typedef struct Node* node;
1.双向链表的结构体定义
struct Node
{
int value;
struct Node *next;
struct Node *prev;
};
2.插入新的双向结构体
nt init(node *head)
{
node newnode = (node)malloc(sizeof(struct Node));
if (NULL == newnode)
{
return -1;
}
3.打印函数（将打印功能模块化，方便下面的操作)
int print(node head)
{
if (head == NULL)
{
printf("It is empty!\n");
return 0;
}
while (head ->next != NULL)
{
printf("%d ", head ->next ->value);
head = head ->next;
}
printf("\n");
}
4.双向链表的倒序打印
int reprint(node head)
{
if (head == NULL)
{
printf("It is empty!\n");
return 0;
}
while (head ->next != NULL)
{
head = head ->next;
}
while (head ->prev != NULL)
{
printf("%d ", head ->value);
head = head ->prev;
}
printf("\n");
}
5.计算双向链表的长度
int length (struct Node *head)
{
int count = 0;
while (head -> next !=NULL)
{
count ++;
head = head ->next;
}
return count;
}
6.双向链表的尾插法
int insert_tail(node head, int x)
{
node newnode = (node )malloc(sizeof(struct Node));
if (NULL == newnode)
{
return -1;
}
newnode ->value = x;
newnode ->next = NULL;
while (head->next != NULL)
{
head = head->next;
}
head->next = newnode;
newnode ->prev = head;
return 0;
}
7.双向链表的头插法
int insert_head(node head, int x)
{
node newnode = (node)malloc(sizeof(struct Node));
if (NULL == newnode)
{
return -1;
}
newnode ->value = x;
if (NULL == head ->next)
{
newnode ->next = NULL;
head ->next = newnode;
newnode ->prev = head;
}
else
{
newnode ->next = head ->next;
head ->next ->prev = newnode;
head ->next = newnode;
newnode ->prev = head;
}
return 0;
}
8.双向链表的中间插入（按照位置插入）
int insert_index(node head, int x, int index)
{
if (index < 0 || index > length(head))
{
printf("index is error!\n");
return -1;
}
for (int i = 1; i < index ; i++)
{
head = head ->next;
}
node newnode = (node)malloc(sizeof(struct Node));
if (NULL == newnode)
{
return -1;
}
newnode ->value = x;
newnode ->next = head ->next;
head ->next ->prev = newnode;
head ->next = newnode;
newnode ->prev = head;
}
9.按照位置更新双向链表
int update_index(node head, int x, int index)
{
if (index < 0 || index > length(head))
{
printf("index is error!\n");
return -1;
}
for (int i = 0; i < index ; i++)
{
head = head ->next;
}
head -> value = x;
}
10.按照位置删除双向链表
int delete_index(node head, int index)
{
if (index < 0 || index > length(head))
{
printf("index is error!\n");
return -1;
}
for (int i = 1; i < index; i++)
{
head = head ->next;
}
node newnode = (node)malloc(sizeof(struct Node));
if (NULL == newnode)
{
return -1;
}
node ptr = head -> next;
head -> next = ptr -> next;
ptr ->next ->prev = head;
free(ptr);
}
11.按照数值更新双向链表
int update_value(node head , int x, int value)
{
while (head -> next != NULL)
{
if (head -> next -> value == value)
{
head -> next -> value = x;
}
head = head ->next;
}
if (head ->value == value)
{
head ->value = x;
}
return 0;
}
12.按照数值删除双向链表
int delete_value(node head, int value)
{
int len = length(head);
for (int i = 0; i < len - 1; i++)
{
if (head -> next -> value == value)
{
node str = head ->next;
head -> next = str -> next;
str ->next ->prev = head;
free(str);
}
else
{
head = head -> next;
}
}
if (head ->next ->value == value)
{
head ->next = NULL;
}
}
13.按照数值查找双向链表
int search_value(node head, int value)
{
int count = 0;
int index = 1;
while (head ->next != NULL)
{
if (head ->next -> value == value)
{
count ++;
printf("The index of the number is :%d\n", index);
}
head = head ->next;
index++;
}
printf("The sum of the number is:%d\n", count);
}
14.按照位置查找双向链表
int search_index(node head, int index)
{
if (index < 0 || index > length(head))
{
printf("index is error!\n");
}
for (int i = 0; i < index; i++)
{
head = head ->next;
}
printf("The value of the index %d is :%d\n", index, head ->value);
return 0;
}
15.双向链表的排序
int sort(node head)
{
int i = 0;
int j = 0;
node p = head;
int len = length(head);
for ( i = 0; i < len - 1; i++)
{
int flag = 0;
head = p;
for ( j = 0; j < len - i - 1; j++)
{
if (head ->next ->value > head ->next ->next ->value)
{
node ptr1 = head ->next;
node ptr2 = head ->next ->next;
if (ptr2 ->next !=NULL)
{
ptr1 ->next = ptr2 ->next;
ptr2 ->next ->prev = ptr1;
ptr2 ->next = ptr1;
ptr1 ->prev = ptr2;
ptr2 ->prev = head;
head ->next = ptr2;
flag = 1;
}
else
{
ptr1 ->next = NULL;
ptr2 ->next = ptr1;
ptr1 ->prev = ptr2;
ptr2 ->prev = head;
head ->next = ptr2;
flag = 1;
}
}
head = head ->next;
}
if (flag ==0)
{
break;
}
}
}
16.释放双向链表所占的空间
node freeall(struct Node *head)
{
while (head ->next != NULL)
{
struct Node *ptr = head;
head = head ->next;
free(ptr);
}
free(head);
head = NULL;
return head;
}
测试以上所有功能的主函数
int main()
{
int i = 0;
node head;
init(&head);
for ( i = 0; i < 10; i++)
{
insert_tail(head, i);
}
print(head);
reprint(head);
for ( i = 0; i < 10; i++)
{
insert_head(head, i);
}
print(head);
reprint(head);
insert_index(head, 99, 6);
print(head);
reprint(head);
update_index(head , 88, 6);
print(head);
reprint(head);
delete_index(head, 9);
print(head);
reprint(head);
update_value(head, 0, 9);
print(head);
reprint(head);
delete_value(head, 0);
print(head);
reprint(head);
search_value(head, 5);
search_index(head, 8);
sort(head);
print(head);
reprint(head);
head = freeall(head);
print(head);
reprint(head);
return 0;
}