[数据结构与算法]1.3 双链表

这一章是有关双链表的算法分析和代码实现。
双链表的结点数据结构：

/*双链表结点的数据结构*/
typedef struct DNode {
	ElemType data;						//数据域
	struct DNode* prior;				//前驱指针
	struct DNode* next;					//后继指针
}DNode, *DLinkList;

主要有以下实现功能的函数：

1. DLinkList CreateListbyHeadInsert(DLinkList& L)) 功能：头插法建立双链表（逆向建立双链表）；
   参数：L:链表；
   时间复杂度：O(n);

2. DLinkList CreateListbyTailInsert(DLinkList& L) 功能：尾插法建立双链表（正向建立双链表）；
   参数：L:链表；
   时间复杂度：O(n)；

3. DNode* GetNode(DLinkList& L, int i) 功能：按位查找，拿到第i个位置的结点并返回；
   参数：L:链表 , i:要查找的结点的位置;
   时间复杂度：O(n);

4. DNode* LocateNode(DLinkList L, ElemType e) 功能：按值查找,查找第一个数据域和e相等第结点并返回；
   参数：L:链表，e:要查找的结点的值；
   时间复杂度：O(n)；

5. bool DNodeInsert(DLinkList& L, int i, ElemType e) 功能：插入结点，在第i个位置插入一个结点；
   参数：L:链表 ，i:插入的位置，e:插入结点的值
   时间复杂度：O(n);

6. bool DNodeDelete(DLinkList& L, int i) 功能：删除结点,删除第i个结点；
   参数：L:链表，i:删除结点的位置；
   时间复杂度：O(n);

7. bool DNodeRevise(DLinkList& L, int i, ElemType e) 功能：修改结点,将第i个结点的数据修改为e；
   参数：L:链表，i:要修改的结点位置，e:要改成的值；
   时间复杂度：O(n)；

8. int LinkLength(DLinkList L) 功能：求表长；
   参数：L:链表；
   时间复杂度：O(n)；

9. void PrintList(DLinkList L) 功能：输出所有结点的值；
   参数：L:链表；
   时间复杂度：O(n);

完整代码：

#include<cstdio>
#include<cstdlib>
#include<iostream>

#define ElemType int

/*--------------------------------------------------------数据结构部分--------------------------------------------------------*/

/*双链表结点的数据结构*/
typedef struct DNode {
	ElemType data;						//数据域
	struct DNode* prior;				//前驱指针
	struct DNode* next;					//后继指针
}DNode, *DLinkList;

/*初始化双链表*/
void InitList(DLinkList& L) {
	L = new DNode;
	L->next = NULL;
	L->prior = NULL;
}

/*头插法建立双链表*/
DLinkList CreateListbyHeadInsert(DLinkList& L) {
	InitList(L);
	int x;
	DNode* s;
	DNode* p = L;
	scanf("%d", &x);
	while (x!=9999)
	{
		s = new DNode;
		s->data = x;
		s->next = p->next;				//注意这里的顺序
		if(p->next)						//判断p->next是否为空，若为空则不用执行下一步代码，否则NULL->prior会出错
			p->next->prior = s;
		s->prior = p;
		p->next = s;
		scanf("%d", &x);
	}
	return L;
}

/*尾插法建立双链表*/
DLinkList CreateListbyTailInsert(DLinkList& L) {
	InitList(L);						//初始化
	int x;
	DNode* s, * r = L;					//r为表尾指针，指向双链表最后一个结点
	scanf("%d", &x);
	while (x != 9999)					//输入9999结束
	{
		s = new DNode;
		s->data = x;
		s->prior = r;
		s->next = NULL;
		r->next = s;
		r = s;
		scanf("%d", &x);
	}
	return L;
}

/*按位查找，拿到第i个位置的结点并返回*/
DNode* GetNode(DLinkList& L, int i) {
	int j = 1;								//计数，初始为1
	DNode* p = L->next;						//头结点赋值给p
	if (i == 0)								//若i == 0 则返回头结点
		return L;
	if (i < 1)								//若i无效则返回NULL
		return NULL;
	while (p && j < i)						//从第一个结点开始找，找到第i个结点
	{										//在p == NULL(表遍历结束)或j == i(已找到第i个结点)时跳出循环
		p = p->next;
		j++;
	}
	return p;								//返回第i个结点的指针，若i大于表长返回NULL
}

/*按值查找,查找第一个数据域和e相等第结点并返回*/
DNode* LocateNode(DLinkList L, ElemType e) {
	DNode* p = L->next;
	while (p != NULL && p->data != e)		//从第1个结点开始查找data为e的结点
	{
		p = p->next;						//移动结点指针
	}
	return p;								//找到后返回该节点的指针，否则返回NULL
}

/*插入结点，在第i个位置插入一个结点*/
bool DNodeInsert(DLinkList& L, int i, ElemType e) {
	DNode* s;
	DLinkList p = L;
	p = GetNode(L, i - 1);					//查找插入位置的前驱结点
	if (!p)									//p == NULL未找到，返回false
		return false;
	s = new DNode;							//插入结点
	s->data = e;
	s->next = p->next;						//s->next指向原来p的下一个结点
	if (p->next)							//和头插法建立双链表同理
		p->next->prior = s;
	s->prior = p;							//s->prior指向它的前一个结点p
	p->next = s;							//p->next指向新增的s结点
	return true;
}

/*删除结点,删除第i个结点*/
bool DNodeDelete(DLinkList& L, int i) {
	DNode* q;
	DLinkList p = L;
	p = GetNode(L, i - 1);					//查找删除位置的前驱结点
	if (!p)									//未找到第i个位置的前驱结点，返回false
		return false;
	q = p->next;							//q指向被删除结点
	if (!q)									//边界判断：第i个位置有前驱结点，但是不存在第i个位置的结点，返回false
		return false;
	q = p->next;							//q指向被删除结点
	p->next = q->next;						//将*q结点从链中断开
	if(q->next)								//判断要删除的第i个结点有无后继结点
		q->next->prior = p;
	free(q);								//释放结点的存储空间
	return true;
}

/*修改结点,将第i个结点的数据修改为e*/
bool DNodeRevise(DLinkList& L, int i, ElemType e) {
	DLinkList p = L;
	p = GetNode(L, i);						//拿到要修改的结点
	if (!p || i == 0)						//结点不能为空，不能修改头结点
		return false;
	p->data = e;							//修改结点的值
	return true;
}

/*求表长并返回*/
int LinkLength(DLinkList L) {
	DNode* p = L->next;						//头节点不存放数据，不算长度
	int sum = 0;
	while (p)
	{
		p = p->next;						//移动结点指针
		sum++;
	}
	return sum;								//返回表长
}


/*打印表*/
void PrintList(DLinkList L) {
	DNode* p = L->next;					//判断是否表空
	if (!p)
		printf("表空\n");
	else {
		printf("双链表数据：\n");
		while (p) {
			printf("%d  ", p->data);
			p = p->next;
		}
		printf("\n共%d个元素\n", LinkLength(L));
	}
}

/*--------------------------------------------------------功能函数部分--------------------------------------------------------*/
/*插入结点的功能*/
void Insert(DLinkList& L) {
	int location;
	ElemType elem;
	printf("输入要插入的元素：");
	scanf("%d", &elem);
	printf("要插入的位置：");
	scanf("%d", &location);
	if (DNodeInsert(L, location, elem))
		printf("插入成功\n");
	else
		printf("插入失败\n");
}

/*删除结点的功能*/
void Delete(DLinkList& L) {
	int location;
	printf("输入要删除的元素的位置：");
	scanf("%d", &location);
	if (DNodeDelete(L, location))
		printf("删除成功\n");
	else
		printf("删除失败\n");
}

/*修改结点的功能*/
void Revise(DLinkList& L) {
	int i;
	ElemType e;
	printf("输入要修改的位置：");
	scanf("%d", &i);
	printf("修改为：");
	scanf("%d", &e);
	if (DNodeRevise(L, i, e))
		printf("修改成功\n");
	else
		printf("修改失败\n");
}

void Search(DLinkList L) {
	int searchChoice;
	printf("（1）按位查找\n");
	printf("（2）按值查找\n");
	printf("选择查找功能：\n");
	scanf("%d", &searchChoice);
	int i;
	ElemType e;
	DNode* p;
	switch (searchChoice)
	{
	case(1):
		printf("输入要查找的节点位置：");
		scanf("%d", &i);
		p = GetNode(L, i);
		if (p && i != 0)					//查找的结点不能为空，也不能查找头结点的值
			printf("第%d个结点的值为%d\n", i, p->data);
		else
			printf("查找失败\n");
		break;
	case(2):
		printf("输入要查找的结点的值：");
		scanf("%d", &e);
		p = LocateNode(L, e);
		if (p)
			printf("找到该元素,查找成功\n");
		else
			printf("找不到该元素,查找失败\n");
		break;
	default:
		break;
	}
}


void menu() {
	printf("\n\n");
	printf("①----------头插法建立双链表----------\n");
	printf("②----------尾插法建立双链表----------\n");
	printf("③----------     打印表     ----------\n");
	printf("④----------    插入结点    ----------\n");
	printf("⑤----------    删除结点    ----------\n");
	printf("⑥----------    修改结点    ----------\n");
	printf("⑦----------    查找结点    ----------\n");
	printf("\n\n");
}

int main() {
	DLinkList L;
	int choice;
	do
	{
		menu();
		scanf("%d", &choice);
		switch (choice)
		{
			case(1):
				printf("输入每个元素的值（输入9999停止建表）\n");
				CreateListbyHeadInsert(L);
				break;
			case(2):
				printf("输入每个元素的值（输入9999停止建表）\n");
				CreateListbyTailInsert(L);
				break;
			case(3):
				PrintList(L);
				break;
			case(4):
				Insert(L);
				break;
			case(5):
				Delete(L);
				break;
			case(6):
				Revise(L);
				break;
			case(7):
				Search(L);
				break;
			default:
				break;
		}

	} while (choice != 0);
}