双向链表创建/插入/删除/排序

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node
{
int data;
struct node *pre;
struct node *next;
}Node;
// 创建
Node* createList();
// 插入节点
void insertList(Node* head, int data);
// 显示所有节点
void displayList(Node* head);
// 搜索节点
Node* searchList(Node* head, int nFind);
// 删除某节点
void deleteList(Node* pFind);
// 计算链表有效节点个数
int lenList(Node* head);
// 排序
void sortList(Node* head, int len);
// 销毁链表
void destoryList(Node* head);
Node *createList()
{
// 创建头节点
Node *head = (Node*)malloc(sizeof(Node));
// 让头节点的pre和next头指向自身
head->pre = head;
head->next = head;
int tmp;
scanf(“%d”, &tmp);
while (tmp)
{
// 向链表插入数据
insertList(head, tmp);
scanf(“%d”, &tmp);
}
return head;
}
void insertList(Node *head, int data)
{
// 新建一个节点
Node* cur = (Node*)malloc(sizeof(Node));
// 给节点数据域赋值
cur->data = data;
// 头插法，让新来的节点有所指向
cur->next = head->next;
cur->pre  = head;
// 重新将新节点连接到链表中，打破原有连接关系
head->next->pre = cur;
head->next = cur;
}
void displayList(Node *head)
{
// 跳过头节点
Node *tmp = head->next;
while (tmp != head)
{
printf(“%d “, tmp->data);
tmp = tmp->next;
}
putchar(10);
}
Node* searchList(Node* head, int nFind)
{
// 双方向遍历查找，分别使用两个指针指向头节点的上一个和下一个节点
Node* pClock = head->next;
Node* pAntClock = head->pre;
// 循环直至两个节点相遇
while (pAntClock != pClock->pre)
{
// 判断是否等于查找的数据
if (pClock->data == nFind)
return pClock;
if (pAntClock->data == nFind)
return pAntClock;
// 判断是否走到了一起
if (pAntClock == pClock)
return NULL;
// 让两个指针分别前进
pClock = pClock->next;
pAntClock = pAntClock->pre;
}
return NULL;
}
void deleteList(Node* pFind)
{
if (NULL == pFind)
{
return;
}
else
{
// 把要删除的节点的上一个节点指向被删除节点的下一个节点
pFind->pre->next = pFind->next;
// 把要删除的节点的下一个节点指向被删除节点的上一个节点
pFind->next->pre = pFind->pre;
// 分别把上下节点建立关系后，删除当前节点
free(pFind);
}
}
int lenList(Node* head)
{
// 计算长度不多解释
int len = 0;
Node* pHead = head->next;
while (pHead != head)
{
len++;
pHead = pHead->next;
}
return len;
}
void sortList(Node* head, int len)
{
// 排序也是使用的冒泡交换指针的方式，参考单向链表
Node* p;
Node* q;
Node* tmp;
for (int i = 0; i < len - 1; i++)
{
p = head->next;
q = p->next;
for (int j = 0; j < len - 1 - i; j++)
{
if (p->data > q->data)
{
p->pre->next = q;
q->pre = p->pre;
p->next = q->next;
p->pre = q;
q->next = p;
p->next->pre = p;
q = p->next;
}
else
{
p = p->next;
q = p->next;
}
}
}
}
void destoryList(Node* head)
{
// 先掐断链表
head->pre->next = NULL;
Node* tmp = head->next;
// 遍历逐一释放
while (head)
{
head = head->next;
printf(“free tmp : %p\n”, tmp);
free(tmp);
}
}
int main(int argc, char *argv[])
{
Node *head = createList();
displayList(head);
Node* pFind = NULL;
if (NULL != (pFind = searchList(head, 100)))
{
printf(“search in %d\n”, pFind->data);
}
deleteList(pFind);
displayList(head);
int len = lenList(head);
printf(“%d \n”, len);
sortList(head, len);
displayList(head);
destoryList(head);
return 0;
}