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

发表评论

双向链表有别于单向链表，对于数据的排列、查找更加方便，但需要付出的小小代价则是在数据结构中增加一个指向上一个节点的指针，除了结构上的变化，对于我们理解也相对复杂了一些。

我们可以用下面这张非常形象的图片来想象双向链表的表现方式（来自传智播客教师课件）：

2015-05-06_213347

双向链表插入数据同样与单向链表一样，都可以使用头插法和尾插法。尾插法相对容易理解，而头插法在双向链表中非常的绕弯，为此，我制作了一个特别的PPT，演示了双向链表头插法的过程：

2015-05-06_212942

双向链表的所有操作代码如下：

#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;
}

 

发表评论