C++双向链表(异常处理)

前言:

到今天为止,线性表的相关内容就已经更新完了.对于即将从事开发工作或者有意从事开发工作的朋友说一句话,先完成再完美 .不是所有人第一次就可以写出完美的代码,都是在后期根据要求不断地优化,有时候很多BUG就是因为在前期过度优化造成的.希望我们以后都可以成为引进时代的佼佼者.

单链表的节点都只有一个指向下一个节点的指针，单链表的数据元素无法直接访问其前驱元素。逆序访问单链表中的元素是极其耗时的操作

双向链表的定义:在单链表的结节中增加一个指向其前驱的指针

双向链表拥有单链表的所有操作

双向链表的新操作:

获取当前游标指向的数据元素

将游标重置指向链表中的第一个数据元素

将游标移动指向到列表中的下一个数据元素

将游标移动指向到列表中的上一个数据元素

直接指定删除列表中的某个数据元素

优点和缺点

优点:双向链表在单列表的基础上增加了指向前驱的指针，功能上双向链表可以完全取代单链表的使用。循环链表的三个辅助指针操作可以高效地遍历列表中的所有元素。

缺点:代码复杂

#include
#include
#include"DLinkList.h"
/*
异常处理
插入第一个元素异常处理
在0号位置插入元素异常处理
剩下的功能和循环列表都是一样的 代码就没写
*/
typedef struct _tag_DLinkList
{
	DLinkListNode header;//有个头
	DLinkListNode* slider;//有个指针
	int length;//长度
}TDLinkList;
TDLinkList*DLinkList_Create()//链表创建
{

	TDLinkList*ret = (TDLinkList*)malloc(sizeof(TDLinkList));
if (ret != NULL)
{
	ret->length = 0;
	ret->header.next = NULL;
	ret->header.pre = NULL;
	ret->slider = NULL;
}
return ret;
}
void DLinkList_Destory(DLinkList *list)
{
	if (list != NULL)
	{
		free(list);
	}

}
void DLinkList_Clear(DLinkList*list)
{
	TDLinkList*sList = (TDLinkList*)list;
	if (sList != NULL)
	{
		sList->length = 0;
		sList->header.next = NULL;
		sList->header.pre = NULL;
		sList->slider = NULL;
	}
}
int  DLinkList_Length(DLinkList* list)
{
	TDLinkList*sList = (TDLinkList*)list;
	int ret = -1;
	if (sList != NULL)
	{
		ret = sList->length;
	}
	return ret;
}
int DLinkList_Insert(DLinkList*list, DLinkListNode*node, int pos)
{
	int ret = 0, i = 0;
	TDLinkList*sList = (TDLinkList*)list;
	if (list == NULL || node == NULL || pos < 0)
	{
		return -1;
	}
	{
		DLinkListNode* current = (DLinkListNode*)sList;//首先引进辅助指针变量3个
		DLinkListNode* next = NULL;//需要增加next指针
		for (i = 0; (i < pos) && (current->next != NULL); i++)
		{
			current = current->next;//在0号位置插入 ,往后跳
		}
		next = current->next;
		//步骤1-2

		current->next = node;
		node->next = next;
		//步骤3-4
		if (next != NULL)//当链表插入第一个元素,需要特殊处理   
		{
			next->pre = node;//4
		}
		node->pre = current;//3
		if (sList->length == 0)
		{
			sList->slider = node;//当链表插入第一个元素处理游标
		}
		//若在0号位置插入 需要特殊处理 新来的结点next前pre指向null
		if (current == (DLinkListNode*)list)
		{
			node->pre = NULL;
		}
		sList->length++;
	}
	return ret;
}
DLinkListNode* DLinkList_Get(DLinkList*list, int pos)
{
	TDLinkList*sList = (TDLinkList*)list;
	TDLinkListNode* ret = NULL;
	int i = 0;
	if ((sList = NULL) && (0 <= pos) && (pos < sList->length))
	{
		DLinkListNode* current = (DLinkListNode*)sList;
		for (i = 0; i < pos; i++)
		{
			current = current->next;
		}
		ret = current->next;
	}
	return ret;
}
//插入第一个结点 删除的是最后一个结点该怎么处理
DLinkListNode* DLinkList_Delete(DLinkList*list, int pos)
{
	TDLinkList*sList = (TDLinkList*)list;
	TDLinkListNode* ret = NULL;
	int i = 0;
	if (sList = NULL) || pos < 0)
	{
	return NULL;
    }
	{
		DLinkListNode* current = (DLinkListNode*)sList;

		DLinkListNode* next = NULL;//需要增加next指针
		for (i = 0; (i < pos; i++)
		{
			current = current->next;
		}
		ret=current->next;
			next=ret->next;
			//1 连线
			current->next=next;
			//2 指向下一个
			if (next != NULL)//需要特殊处理
			{
				next->pre = current;//若第0个位置 需要特殊处理
			}
	}
	if (sList->slider == ret)
	{
		sList->slider = next;

	}
	sList->length--;
	return ret;
}

顺序表和链表的比较

存取方式

顺序表可以顺序存取，也可以随机存取。链表只能从表头顺序存取元素

逻辑结构与物理结构

采用顺序存储时，逻辑上相应的元素，其对应的物理存储位置也相邻，而采用链式存储是逻辑上相应的元素，其物理存储位置则不一定相应，其对应的逻辑关系是通过指针链接来表示的

查找、插入和删除操作

对于按值查找,顺序表无序时两者的时间复杂度均为O(n),顺序表有序时则可以采用折半查找此时的时间复杂度为N的对数.

对于按序号查找顺序表支持随机访问，其时间复杂度为一，而链表的平均时间复杂度为N。顺序表的插入删除操作平均需要移动半个表的长的元素.链表的插入删除操作，只需修改相关节点的指针域即可。对于链表的每个结点都带有指针域，因而在存储空间上要比顺序存储付出的代价更大，而存储密度不够大.

空间分配

顺序存储在静态存储分配情形下，一旦存储空间装满就不能扩充，若再加入新元素则会出现内存溢出，因此需要预先分配足够大的存储空间。预先分配过大可能会导致顺序表后部大量闲置，预先分配过小又会造成溢出。动态存储分配虽然存储空间可以扩充，但需要移动大量元素，导致操作效率低，而且如果内存中没有更大块的连续存储空间，则会导致分配失败。链式存储的节点空间只在需要时申请分配，只要内存有空间就可以分配，操作灵活高效.

那么，在实际中应该怎样选取存储结构呢？

1)基于存储的考虑

难以估计线性表的长度或存储规模时，不宜采用顺序表。链表不用事先估计存储规模，但链表的存储密度较低，显然链式存储的存储密度是小于1的。

2)基于运算的考虑

在顺序表中按序号访问访问Ai的时间复杂度为1，按序号访问的时间复杂度为N。因此若经常做的运算是按序号访问数据元素，则显然顺序表优于链表。在顺序表进行插入删除操作时，平均移动表中一半的元素，当数据元素的信息量较大且表较长，这一点是不应忽视的。在列表中进行插入、删除操作时，虽然也要找插入位置，但操作主要是比较操作。从这个角度考虑，显然后者优于前者

3)基于环境的考虑

顺序表容易实现，任何高级语言中都有数组类型，列表的操作是基于指针的，相对来讲，前者实现比较简单，这也是用户考虑的一个因素。总之，两种存储结构各有长短，选择哪一种由实际问题的主要因素决定，通常较稳定的线型表选择顺序存储 .而频繁进行插入.删除操作的线性表就选择链式存储