线性表——双向循环链表的设计思路与实现

双向循环链表的基本结构：

一个数据域，一个指向下一个节点的next指针域，指向前一个节点的prior指针域。

typedef struct DulNode{
	ElemType data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode, *DulLinkList;

对于ElemType,，以及用于比较的函数，我们假定有

typedef struct stu{
	char name[50];
	char id[50];
}stu;

typedef stu ElemType;

bool cmp(ElemType e1, ElemType e2)
{
	if(strcmp(e1.name, e2.name) == 0 && strcmp(e1.id, e2.id) == 0)
	    return true;
	return false;
}

初始化：

• 对头节点进行内存分配。分配失败返回NULL.
• 将前驱指针和后继指针指向头节点。
• 返回头节点的地址。

DulNode *InitList (DulLinkList L)
{
	L = (DulNode *)malloc(sizeof(DulNode));
	if(L == NULL)
		return NULL;
	
	L->next = L;
	L->prior = L;
	return L; 
}

头插法：

• 对一个节点进行内存分配，如果分配内存失败返回NULL。
• 将数据存储进入数据域。
• 将新节点的next指针指向头节点的next指针指向的地址。
• 将头节点的next指针指向的节点的前驱节点指针指向新节点的地址。
• 将新节点的前驱节点指针指向新节点。
• 将新节点的后继节点指针指向新节点。
• 返回新节点的地址。

实现代码如下：

DulNode *Insert_Head(DulLinkList L, ElemType e)			//头插法 
{
	DulLinkList p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
	    return NULL;
	p->data = e;			//将数据储存进数据域 
	p->next = L->next;		//将新结点的后继结点指针指向前驱结点的后继指针指向的地址(头结点) 
	L->next->prior = p;
	p->prior = L;
	L->next = p;			//将头结点的后继指针指向新结点 
	return p;
}

总的实现代码：

#include <stdio.h>
#include <stdbool.h>
#include <malloc.h>
#include <string.h>

 typedef struct stu{
	char name[50];
	char id[50];
}stu;

typedef stu ElemType;

typedef struct DulNode{
	ElemType data;
	struct DulNode *prior;
	struct DulNode *next;
}DulNode, *DulLinkList;

bool cmp(ElemType e1, ElemType e2)
{
	if(strcmp(e1.name, e2.name) == 0 && strcmp(e1.id, e2.id) == 0)
	    return true;
	return false;
}

//查 
int Size(DulLinkList L)				//计算结点的数目 
{
	int num = 0;
	DulLinkList p = L;
	while(p->next != L)
	{
		num++;
		p = p->next;
	}
	return num;
}

bool Empty(DulLinkList L)				//查询是否为空链表 
{
	if(L->next == L && L->prior == L)
	    return true;
	return false; 
}

bool Find(DulLinkList L, ElemType e)			//查找值 
{
	DulLinkList p = L;
	while(p->next != L)
	{
		p = p->next;
		if(cmp(p->data, e))
        	return true;
	}
	return false;
}

void GetElem(DulLinkList L, int pos, ElemType *e)			//按位置查找，按元素插入的顺序顺时针数 
{
	if(pos < 1 || pos > Size(L))		//判断位置 
	{
		e = NULL;
		return;
	}
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	*e = p->data;
}

void Display(DulLinkList L)
{
	DulLinkList p = L;
	while(p->next != L)
	{
		p = p->next;
	    printf("name: %-10s\t id: %-10s\n", p->data.name, p->data.id);
	}
}

//增 
DulNode *InitList (DulLinkList L)
{
	L = (DulNode *)malloc(sizeof(DulNode));
	if(L == NULL)
		return NULL;
	
	L->next = L;
	L->prior = L;
	return L; 
}

DulNode *Insert_Head(DulLinkList L, ElemType e)			//头插法 
{
	DulLinkList p = (DulNode *)malloc(sizeof(DulNode));
	if(p == NULL)
	    return NULL;
	p->data = e;			//将数据储存进数据域 
	p->next = L->next;		//将新结点的后继结点指针指向前驱结点的后继指针指向的地址(头结点) 
	L->next->prior = p;
	p->prior = L;
	L->next = p;			//将头结点的后继指针指向新结点 
	return p;
}

DulNode *Insert_Tail(DulLinkList L, ElemType e) 			//尾插法 
{
	DulLinkList p = (DulNode *)malloc(sizeof(DulNode)), r = L;
    if(p == NULL)
        return NULL;
    while(r->next != L)
        r = r->next;
		
	p->data = e;			//将数据储存进新结点的数据域 
	p->next = r->next;		//将新结点的后继指针指向末节点的后继指针指向的地址 
	r->next = p;			//将末结点的后继指针指向新结点的地址 
	p->prior = r;			// 将新结点的前驱指针指向末结点 
	L->prior = p;			//将头结点的前驱指针指向新结点的地址 
	return p;
}

DulNode* Insert(DulLinkList L, int pos, ElemType e)		//向循环链表中插入一个结点 
{
	if(pos < 1 || pos > Size(L))
		return NULL;
	
	int i;
	DulLinkList p = L, s = (DulNode *)malloc(sizeof(DulNode));
	for(i = 1; i < pos; i++)	//将指针移动到插入位置的前一个结点 
	    p = p->next;
	s->data = e;
	s->next = p->next;		//将s节点的后继指针指向p节点的后继指针指向的地址
	p->next->prior = s; 	//将p节点的后继节点的前驱指针指向新节点s的地址
	p->next = s;			//将p节点的后继指针指向新结点的地址
	s->prior = p;			//将新节点的前驱结点指向p节点的地址
	return s; 
} 

//删
void Destory(DulLinkList *L)			//销毁双循环链表 
{
	DulLinkList p = (*L)->next, q;
	while(p != *L)
	{
		q = p;		//将结点的地址信息赋给q 
		p = p->next;	//将p的后继结点存储放入p 
		free(q); 	//释放q结点,注意，free函数应该放于p->next之后，提前释放了p结点就会导致后面的地址丢失
	}
	free(*L);
	*L = NULL;
}

void DeleteElem(DulLinkList L, int pos)		//删除某一个元素_按位置删除 
{
	if(pos < 1 || pos > Size(L))		//位置信息判断 
		return;
	
	int i; 
    DulLinkList p = L;
    for(i = 1; i <= pos; i++)					//将指针移动到删除结点
        p = p->next;
    p->prior->next = p->next;				//将删除结点的前驱指针指向的地址的后继指针指向删除结点的后继指针指向的结点的地址 
    p->next->prior = p->prior;				//将删除结点的后继指针指向的结点的前驱指针指向删除结点的前驱指针指向的地址
    free(p);
}

//改
void ChangeElem(DulLinkList L, int pos, ElemType e)
{
	if(pos < 1 || pos > Size(L))
		return;
	
	int i;
	DulLinkList p = L->next;
	for(i = 1; i < pos; i++)
	    p = p->next;
	p->data = e;
	return;
}

//合并两个循环链表 
void UnionDulList(DulLinkList rearA, DulLinkList rearB)
{
	if(Size(rearB) > 0)
	    return;
	rearA->prior->next = rearB->next;
	rearB->next->prior = rearA->prior;
	rearA->prior = rearB->prior;
	rearB->prior->next = rearA;
	free(rearB);
	return;
}

int main()
{

	return 0;
}