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

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

（单链表）

1
2
3
4
5
6
7
8
9
10
11
12
13
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（节点）的指针罢了

1
2
3
4
5
6
7
template<typename E>class LList::public List<E>{
private:
	Link<E>*head;
	Link<E>*tail;
	Link<E>*curr;
	int cnt; 
};

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

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

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

1
2
3
4
5
void init()
{
	curr=tail=head=new Link<E>;
	cnt=0;
} 

1
2
3
4
5
6
7
8
9
void removeall()
{
	while(head!=NULL)
	{
		curr=head;
		head=head->next;
		delete curr;
	}
}

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

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

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

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

1
2
3
4
5
public:
	LList()
	{
		init();
	}

书上是

1
2
3
4
LList(int size=defaultSize)
{
   init();
}

这是LList的构造函数

1
2
3
4
	~LList()
	{
		removeall();
	}

1
	void print()const;

1
2
3
4
5
	void clear()
	{
		removeall();
		init();
	}

1
2
3
4
5
6
	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。

我们来解读一下这段代码

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
	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指针就是我们当前位置的后继，那么我们就“往前”给当前位置。

为什么不给后面？因为有可能你删的就是最后一个节点呀！

后面的基本操作就其实没有什么要特别注明的啦~谢谢大家

最后

以上就是孝顺外套最近收集整理的关于关于Clifford A.Shaffer老师数据结构与算法分析中里用链表实现线性表的具体实现的感想的全部内容，更多相关关于Clifford内容请搜索靠谱客的其他文章。