数据结构——双向链表

一.双向链表的操作

• • 结构体
  • 初始化
  • 头插
  • 尾插
  • 在pos位置插入val
  • 判空
  • 获取结点个数
  • 在DList中查找第一个key值,找到了返回地址,没有找到返回NULL
  • 删除第一个val的值
  • 返回key的前驱地址,如果不存在返回NULL
  • 返回key的后继地址,如果不存在返回NULL
  • 输出
  • 删除pos位置的数据
  • 销毁

typedef struct DNode
{
	int data;
	DNode *next;
	DNode *prior;
}DNode,*DList;

void InitList(DList plist)//初始化
{
	assert(plist != NULL);
	plist->next = NULL;
	plist->prior = NULL;
}

bool InsertHead(DList plist, int val)//头插
{
	assert(plist != NULL);
	DNode* q = plist->next;
	DNode* p = (DNode*)malloc(sizeof(DNode));
	assert(p!=NULL);
	p->data = val;
	//插入 单指针法
	p->next = plist->next;
	plist->next = p;
	p->prior = plist;
	if (p->next)
	{
		p->next->prior = p;
	}
	return true;
	//双指针法
	
}

bool InsertTail(DList plist, int val)//尾插
{
	assert(plist != NULL);
	DNode* p = plist;
	while (p->next)
	{
		p = p->next;
	}
	DNode* q = (DNode*)malloc(sizeof(DNode));
	q->data = val;
	//插入
	q->next = NULL;
	p->next = q;
	q->prior = p;
	q->prior = NULL;
	return true;
}

bool Insert(DList plist, int pos, int val)//在pos位置插入val
{
	assert(plist != NULL);
	if (pos<0||pos>GetLength(plist))
	{
		return false;
	}
	DNode* p = plist;//pos位置的前驱指针
	DNode* r = p->next;
	//找到pos位置
	for (int i = 0; i < pos-1; i++)
	{
		p = p->next;
	}
	DNode* q = (DNode*)malloc(sizeof(DNode));
	//填入数据
	q->data = val;
	//插入
	q->next = p->next;
	p->next = q;
	q->prior = p;
	q->next->prior = q;
	return true;

}

bool IsEmDListty(DList plist)//判空
{
	assert(plist != NULL);
	return plist == NULL;
}

int GetLength(DList plist)//获取结点个数
{
	assert(plist != NULL);
	int count = 0;
	DNode* p = plist->next;
	while (p)
	{
		count++;
		p = p->next;
	}
	return count;
}

DNode* Search(DList plist, int key)
{
	assert(plist != NULL);
	DNode* p = plist;
	while (p->data != key)
	{
		p = p->next;
	}
	if (p)
	{
		return p;
	}
	else
	{
		return NULL;
	}
}

bool DelVal(DList plist, int val)//删除第一个val的值
{
	assert(plist != NULL);
	DNode* p = plist;//p是val结点的前驱指针
	while (p->next->data != val)
	{
		p = p->next;
	}
	DNode* q = p->next;//q是要删除的结点指针
	//删除操作
	p->next = q->next;
	q->next->prior = p;
	free(q);
	return true;

}

DNode* GetPrio(DList plist, int key)//返回key的前驱地址,如果不存在返回NULL;
{
	assert(plist != NULL);
	DNode* p = plist;
	while (p->next)
	{
		if (p->next->data == key)
		{
			return p;
		}
		p = p->next;
	}
		return NULL;	
}

DNode* GetNext(DList plist, int key)
{
	assert(plist != NULL);
	DNode* p = plist;
	while (p->next)
	{
		if (p->data == key)
		{
			return p->next;
		}
		p = p->next;
	}
	return NULL;

}

void Show(DList plist)//输出
{
	assert(plist != NULL);
	DNode* p = plist->next;
	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}

}

bool DelPos(DList plist, int pos)//删除pos位置的数据
{
	assert(plist != NULL);
	DNode* p = plist;
	//把p赋给pos位置的前驱指针
	for (int i = 0; i < pos-1; i++)
	{
		p = p->next;
	}
	DNode* q = p -> next;
	p->next = q->next;
	q->next->prior = p;
	free(q);
	return true;

}

void Destory(DList plist)//销毁  思路：总是删除第一个结点
{
	assert(plist != NULL);
	DNode* p = plist;
	while (plist->next != NULL)
	{
		p = plist->next;
		plist->next = p->next;
		if (p->next)
		{
			p->next->prior = plist;
		}
		free(p);
	}
}