跟我学数据结构：（3）单向链表

跟我学数据结构：（3）单向链表

摘要：

本文通过示例，演示了用C++实现数据结构的单向链表。

读者对象：

对C++有一定基础的同学。

技术要点:

C++数据抽象

构造函数

析构函数

运算符重载

编码规范初步

指针

友元

声明

本文中相关数据结构及代码是为教学需要而设计，不适用于商业产品。

链表的引入

我们在上节课“数组”是，讲到了对数据的遍历、查找、插入和删除。当我们在对数组进行插入或删除操作的时候，会引起操作点之后的元素整体移动，大量的数据移动（内存复制）会产生能下降的问题。链表正是避免了这一问题。

注：本系列教程以代码，示例演示为主，关于链表的数学定义请参考其它书籍。

链表的设计

链表一般提供了以下操作：

1) 创建链表 creaList()

2) 在指定节点后面插入一个新的节点 insertAfter()

3) 删除指定的值的节点 remove()

4) 遍历所有节点 operator

5) 销毁所有链表

插入节点的操作示意图

操作前

操作过程

(1)

(2)

(3)

删除节点的操作示意图

操作前

操作步骤

(1)

(2)

代码及运行结果

//file: main.cpp
//desc: this program illustrate how to use linked-list
//date: 2009-6-1
//author: Stone Jiang <jiangtao></jiangtao>

#include <iostream><span style="color: #0000ff">using</span> <span style="color: #0000ff">namespace</span> std;

<span style="color: #0000ff">typedef</span>  <span style="color: #0000ff">int</span>  Data_T;
<span style="color: #0000ff">class</span> Node_T
{
<span style="color: #0000ff">public</span>:
	<span style="color: #008000">// [1]</span>
	<span style="color: #0000ff">explicit</span> Node_T(Data_T x);
	Node_T();
	~Node_T();
<span style="color: #0000ff">public</span>:
	<span style="color: #008000">// public interface</span>
	<span style="color: #0000ff">void</span> next(Node_T* next);
	Node_T* next(<span style="color: #0000ff">void</span>);
	Data_T value();
    <span style="color: #008000">// [2]</span>
	<span style="color: #0000ff">friend</span> ostream&amp; <span style="color: #0000ff">operator</span> private:
    Data_T value_;
	Node_T* next_;
};


Node_T::Node_T()
:value_(0),next_(0)
{
	<span style="color: #008000">//cout value_ 

}

Node_T::Node_T(Data_T x)
:value_(x),next_(0)
{
	<span style="color: #008000">//cout value_ 

}

Data_T Node_T::value()
{
	<span style="color: #0000ff">return</span> <span style="color: #0000ff">this</span>-&gt;value_;
}

Node_T::~Node_T()
{
	<span style="color: #008000">//cout value_ 
}

<span style="color: #0000ff">void</span> Node_T::next(Node_T* next)
{
	<span style="color: #0000ff">this</span>-&gt;next_ = next;
}

Node_T* Node_T::next()
{
	<span style="color: #0000ff">return</span> <span style="color: #0000ff">this</span>-&gt;next_;
}


<span style="color: #008000">//= create List</span>
Node_T*  createList();

<span style="color: #008000">//= Insert a new node @<node> after @<x> in the list 0</x></node></span>
<span style="color: #008000">//  success return 0,otherwise  return non-zero</span>
<span style="color: #0000ff">int</span> insertAfter(Node_T* header,Data_T x,Node_T* node);

<span style="color: #008000">//= Remove @<x> from list</x></span>
<span style="color: #0000ff">int</span> remove(Node_T* header,Data_T x);

<span style="color: #008000">//= destroyList</span>
<span style="color: #0000ff">int</span> destroyList(Node_T* header);

ostream&amp; <span style="color: #0000ff">operator</span> int</span> main(<span style="color: #0000ff">int</span>, <span style="color: #0000ff">char</span>**)
{

	Node_T* header = createList();
	cout new</span> Node_T(1);
	insertAfter(header,0,one);
    cout new</span> Node_T(3);
	insertAfter(header,1,three);
	cout new Node_T(2);
	insertAfter(header,1,two);
	cout new Node_T(5);
	insertAfter(header,3,five);
	cout remove :"return 0;
}


Node_T* createList()
{
	Node_T* header = <span style="color: #0000ff">new</span> Node_T(0);
	<span style="color: #0000ff">return</span> header;
}

<span style="color: #0000ff">int</span> insertAfter(Node_T* header,Data_T x,Node_T* node)
{
	<span style="color: #0000ff">int</span> result = -1;
	<span style="color: #0000ff">if</span> (header)
	{
		Node_T* current = header;
		<span style="color: #0000ff">if</span> (current-&gt;value() == x || current-&gt;next() == 0)
		{
			<span style="color: #008000">// [1]</span>
			node-&gt;next(current-&gt;next());
			current-&gt;next(node);
			result = 0;
		}
		<span style="color: #0000ff">else</span>
		{
			<span style="color: #0000ff">return</span> insertAfter(current-&gt;next(),x,node);
		}
	}

	<span style="color: #0000ff">return</span> result;
}

<span style="color: #0000ff">int</span> remove(Node_T* header,Data_T x)
{
	<span style="color: #0000ff">int</span> result = -1;

	<span style="color: #0000ff">if</span> (header)
	{
		Node_T* prev = header;
		Node_T* current = header-&gt;next();
		<span style="color: #0000ff">if</span> (current-&gt;value() == x)
		{
			prev-&gt;next(current-&gt;next());
			<span style="color: #0000ff">delete</span> current;
			current  = 0;
			result = 0;
		}
		<span style="color: #0000ff">else</span>
		{
			<span style="color: #0000ff">return</span> remove(current,x);
		}
	}
	<span style="color: #0000ff">return</span> result;
}

<span style="color: #0000ff">int</span> destroyList(Node_T* header)
{

	Node_T* current = header;
	<span style="color: #0000ff">while</span> (current)
	{
		Node_T* temp = current;
		current = current-&gt;next();
		<span style="color: #0000ff">delete</span> temp;
		temp = 0;
	}

	<span style="color: #0000ff">return</span> 0;
}

ostream&amp; <span style="color: #0000ff">operator</span> if (header)
	{
		Node_T* current = header;
		os ( " value()  ) ---&gt; ";
		
		<span style="color: #0000ff">return</span>  os next();
	}
	<span style="color: #0000ff">else</span>
	{
		cout  ( END )" return os;

}</iostream>

( 0 ) --->  ( END )
( 0 ) ---> ( 1 ) --->  ( END )
( 0 ) ---> ( 1 ) ---> ( 3 ) --->  ( END )
( 0 ) ---> ( 1 ) ---> ( 2 ) ---> ( 3 ) --->  ( END )
( 0 ) ---> ( 1 ) ---> ( 2 ) ---> ( 3 ) ---> ( 5 ) --->  ( END )
remove :
( 0 ) ---> ( 1 ) ---> ( 2 ) ---> ( 5 ) --->  ( END )
( 0 ) ---> ( 2 ) ---> ( 5 ) --->  ( END )

代码说明

（1） 部分收入C++面向对象的特性。示例中演示了构造函数，重载了构造函数。

（2） 代码中使用了递归算法。由于链表的定义可以通过递归来定义，并且在之后的课程中我们将广泛的使用递归算法，所以，我们在本代码中使用了递归算法。

您能找出我们在哪些地方用到了递归吗？

（3） 重载

（4）

埋个伏笔

我们并没有对链表作完合的面向对象封装，所以在使用代码的时候，额外的增加了对链表是否有效作了判断。另外，为了使代码简洁，我们并对函数调用的返回值作检查。在创建和删除节点的时候，我们都使用了动态内存分配。如果我们插入从栈上的临时节点到链表中，将收内存问题。这些，我们都将在后续的课程中为大家解决。