数据结构 双向链表

---------------start reading---------------

前言

双向链表是链表的一种，都是以链式结构存储。与单链表不同的是，双向链表可以向前找前驱，而单链表只能自己定义前驱而且不能倒退。双向链表有与单链表不同的结构，但实现的功能基本是一样的。

双向链表的结构

双向链表的操作一定要注意，要改前驱地址。特别注意尾结点，当需要改后继的前驱的时候，尾结点不能用p->prio->next=p->next->prio,p->next为NULL解引用会导致程序崩溃

双向链表的具体操作
头文件

#pragma once
//带头节点双向链表，非循环

typedef struct DNode
{
   int data;
   struct DNode *next;//后继指针
    struct DNode *prio;//前驱指针
}DNode,*DList;

//链表初始化
void InitList(DList plist);//Node

//头插
bool Insert_head(DList plist,int val);

//尾插
bool Insert_tail(DList plist,int val);

//查找
DNode *Search(DList plist,int key);

//删除
bool Delete(DList plist,int key);

int GetLength(DList plist);

bool IsEmpty(DList plist);

void Clear(DList plist);

void Destroy(DList plist);

void Show(DList plist);

具体实现

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "dlist.h"

//链表初始化
void InitList(DList plist)
{
	assert(plist != NULL);
	if(plist == NULL)
	{
		return ;
	}

	plist->next = NULL;
	plist->prio = NULL;
}

//头插
bool Insert_head(DList plist,int val)
{
	DNode *p = (DNode *)malloc(sizeof(DNode));
	p->data = val;

	p->next = plist->next;//1
	plist->next = p;
	p->prio = plist;
	if(p->next != NULL)
	{
		p->next->prio = p;
	}

	return true;
}
//尾插
bool Insert_tail(DList plist,int val)
{
	DNode *q = (DNode *)malloc(sizeof(DNode));

	q->data = val;

	DNode *p;
	for(p=plist;p->next!=NULL;p=p->next) ;

	//将q插入在p的后面
	q->next = p->next;//q->next = NULL;
	p->next = q;
	q->prio = p;

	return true;
}

//查找
DNode *Search(DList plist,int key)
{
	for(DNode *p=plist->next;p!=NULL;p=p->next)
	{
		if(p->data == key)
		{
			return p;
		}
	}

	return NULL;
}

//删除
bool Delete(DList plist,int key)
{
	DNode *p = Search(plist,key);
	if(p == NULL)
	{
		return false;
	}

	p->prio->next = p->next;
	if(p->next != NULL)
	{
		p->next->prio = p->prio;
	}

	free(p);
	return true;
}

int GetLength(DList plist)
{
	int count = 0;

	for(DNode *p=plist->next;p!=NULL;p=p->next)
	{
		count++;
	}

	return count;
}

bool IsEmpty(DList plist)
{
	return plist->next == NULL;
}

void Clear(DList plist)
{
	Destroy(plist);
}

void Destroy(DList plist)
{
	DNode *p;
	while(plist->next != NULL)
	{
		p = plist->next;
		plist->next = p->next;
		free(p);
	}
}

void Show(DList plist)
{
	for(DNode *p=plist->next;p!=NULL;p=p->next)
	{
		printf("%d ",p->data);
	}
	printf("\n");
}