关于Clifford A.Shaffer老师数据结构与算法分析中里用链表实现线性表的具体实现的感想

53 阅读 0 评论 35 点赞

我是靠谱客的博主孝顺外套，最近开发中收集的这篇文章主要介绍关于Clifford A.Shaffer老师数据结构与算法分析中里用链表实现线性表的具体实现的感想，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

看了shaffer老师的代码，觉得这里面有很多值得学习的地方，下面一一阐述。

（单链表）

template<typename E>class Link{
public:
	E element;
	Link *next;
	Link(const E&elemval,Link*nextval=NULL)
	{
		element =elemval;next=nextval;
	}
	Link(Link*nextval=NULL)
	{
		next=nextval;	
	}
} ;

这一段代码是关于节点的定义的。我们可以发现，一个节点有两个数据成员，一个是数据域，另外一个是指向下一个节点的指针。

这里值得注意的是，我们的Link的构造函数有两个，一个是带有数据域初始值的，另外一个是不带的。

Link*nextval=NULL这个语句的含义就是，如果没有输入相关的参数，那么就会默认NULL，否则将会以你输入的参数为准。

为什么这样子设，后面会有具体的应用。

其实我也有想过把element和next都放在public里面方便修改，但是这样子就违反了我们关于类的封装了

另外Link*nextval=NULL这个可能有点陌生，我们可以转换为我们熟悉的int*p=NULL来理解，其实Link*无非就是声明这是个Link（节点）的指针罢了

template<typename E>class LList::public List<E>{
private:
	Link<E>*head;
	Link<E>*tail;
	Link<E>*curr;
	int cnt; 
};

我们的LList公有继承了List，它有了我们之前List包含的所有数据成员和成员函数。

另外我们另外增加定义了几个private成员

头指针、尾指针、当前指针还有容量大小。

之所以要设置这些东西，无非是想要让我们的程序可以加快访问一些内容。

void init()
{
	curr=tail=head=new Link<E>;
	cnt=0;
}

简单的初始化操作，不加赘述，给后面的基本操作服务。

void removeall()
{
	while(head!=NULL)
	{
		curr=head;
		head=head->next;
		delete curr;
	}
}

我们这里的removeall操作，其实就是把所有线性表里面的节点都释放掉。

怎么做呢？从头开始一个一个向下找，寻找后继。

寻找了以后不断的释放释放释放。

在这里我曾经有一个想法，因为我刚刚用顺序表实现了一个线性表，其实，那时候的删除操作完全可以不用另外定义一个函数，但是为什么这里要大费周章呢？

因为我们之前使用顺序表的时候，完完全全就是new了一块连续的内存，只要delete[]这样子处理就好了，但是这里可不同，这里的链表可是离散的内存，所以我们在运用诸如removeall()这样子的操作的时候，如果每一次的手打一次，将会十分麻烦。因此我们就另外封装成一个函数。

public:
	LList()
	{
		init();
	}

这里和书上有所修改

书上是

LList(int size=defaultSize)
{
   init();
}

这是LList的构造函数

之所以这样子是我觉得在这里这样子做完全没有必要。。。。。。因为我们连size这个数据成员都没有。

	~LList()
	{
		removeall();
	}

析构函数，调用了之前实现的removeall（）函数。

	void print()const;

打印我们的链表，但是书上这样子只有声明没有实现真是让人感到困惑呢。。。。。。

	void clear()
	{
		removeall();
		init();
	}

我觉得这个思路和之前shaffer老师用顺序表实现线性表时的思路是完全一致的。有兴趣可以看看我之前的blog

	void insert(const E&it)
	{
		curr->next=new Link<E>(it,curr->next);
		if(tail==curr)tail=curr->next;
		cnt++;
	}

谈起这个函数的时候，我们要明确一个东西。我们的当前位置是"你想的当前位置"的前一个位置。

例如

(1,2,3,4,5)

你想在2和3中间插入一个8

这时候当前位置指向的应该是元素2，而不是元素3。

我们来解读一下这段代码

curr->next=new Link<E>(it,curr->next);

插入操作，意味着有新节点在进入当中，所以我们就调用了new函数来分配一段内存，Link（）的构造函数调用了带数据域初始值的构造函数，这也是可以理解的。因为我们要插入的元素肯定有具体的值的。

shaffer老师考虑周全的还有tail指针，我们想一下，如果我们在整个线性表的内部进行插入，那么我们完全不用管tail指针，因为tail指针完全不会受到影响。

但是假如我们当前的位置就是tail指针，也就是说5了，插入了之后就是(1,2,3,4,5,8)这时候tail指针就要变了，变成当前位置的后继。

然后我们想一下，head指针有没有问题呢？

这就是另外一个问题，我们这里实现的线性表，其实是有一个头节点的（head）。但是这个头节点起不到任何实际作用，仅仅是为了维持我们全部基本操作的合法性。假如没有这个头节点。那么，我们就无法在（1，2，3，4，5）中的1前插入我们的元素，我们的节点。

	void append(const E&it)
	{
		tail=tail->next=new Link<E>(it,NULL);
		cnt++;
	}

类比之前的insert操作就好了

	E remove()
	{
		Assert(curr->next!=NULL,"No element");
		E it=curr->next->element;
		Link<E>*ltemp=curr->next;
		if(tail==curr->next)tail=curr;
		curr->next=curr->next->next;
		delete ltemp;
		cnt--;
		return it;
	}

这段函数其实也非常的有意思，有意思在哪呢？

首先我们的断言（assert）无非就是一个判断，判断是不是空表。这部分不熟悉的同学完全可以利用if来替代。

之后我们要回想起我们之前定义的一个东西，那就是我们线性表的当前位置，是“你想的位置”的前一个位置。

而且要明确，我们的insert和remove函数都是基于当前位置来进行操作的。

所以说呀，我们如果想要删除

（1，2，3，4，5）中的4，我们其实就是对于3进行操作。

1、我们应该把4赋值给一个变量，删除成功后返回出去。

2、我们对3后面的4这个节点进行一次存储。如果我们不存储直接delete的话，就会出现断链！我们应该重新连接后再删除。

3、当前位置的后继应该是当前位置的后继的后继，也就是5（我们如果直接delete，如何寻找后继的后继呢？

4、释放3后面的节点4，这里释放了ltemp，其实效果是一样的，因为都是存储了那个指针。

5、整体线性表的大小--

这里对于tail指针还有一个判断，假如我们的tail指针就是我们当前位置的后继，那么我们就“往前”给当前位置。