跟我学数据结构:(3)单向链表
摘要:
本文通过示例,演示了用C++实现数据结构的单向链表。
读者对象:
对C++有一定基础的同学。
技术要点:
C++数据抽象
构造函数
析构函数
运算符重载
编码规范初步
指针
友元
声明
本文中相关数据结构及代码是为教学需要而设计,不适用于商业产品。
链表的引入
我们在上节课“数组”是,讲到了对数据的遍历、查找、插入和删除。当我们在对数组进行插入或删除操作的时候,会引起操作点之后的元素整体移动,大量的数据移动(内存复制)会产生能下降的问题。链表正是避免了这一问题。
注:本系列教程以代码,示例演示为主,关于链表的数学定义请参考其它书籍。
链表的设计
链表一般提供了以下操作:
1) 创建链表 creatList()
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& <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>->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>->next_ = next;
}
Node_T* Node_T::next()
{
<span style="color: #0000ff">return</span> <span style="color: #0000ff">this</span>->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& <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->value() == x || current->next() == 0)
{
<span style="color: #008000">// [1]</span>
node->next(current->next());
current->next(node);
result = 0;
}
<span style="color: #0000ff">else</span>
{
<span style="color: #0000ff">return</span> insertAfter(current->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->next();
<span style="color: #0000ff">if</span> (current->value() == x)
{
prev->next(current->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->next();
<span style="color: #0000ff">delete</span> temp;
temp = 0;
}
<span style="color: #0000ff">return</span> 0;
}
ostream& <span style="color: #0000ff">operator</span> if (header)
{
Node_T* current = header;
os ( " value() ) ---> ";
<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)
埋个伏笔
我们并没有对链表作完合的面向对象封装,所以在使用代码的时候,额外的增加了对链表是否有效作了判断。另外,为了使代码简洁,我们并对函数调用的返回值作检查。在创建和删除节点的时候,我们都使用了动态内存分配。如果我们插入从栈上的临时节点到链表中,将收内存问题。这些,我们都将在后续的课程中为大家解决。
分享到:
相关推荐
数据结构:单向循环链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
数据结构:单向链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
重点阐述数据结构: 结构体与链表,深入详解数据结构。
数据结构:数组和链表的区别以及各自的优缺点 数组和链表.pdf
数据结构 链表 C语言 单向链表 栈
1. 数据结构:数组、链表、栈、队列、树、堆、图; 2. 典型排序算法:冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序、桶排序、计数排序、基数排序; 3. 查找算法: 顺序查找、二分查找、哈希...
C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表C#单向链表
数据结构:图解链表,链表的插入和删除(c语言版) 我们上节讲解了链表的建立,本节讲解的是在链表中指定位置中插入一个结点,以及在指定位置中删除一个结点 指定位置插入一个结点 这里我们在第3个结点后插入一个...
数据结构第一章 第二章的一些小程序,包括单向链表,双向链表,a交b等等
包含数据结构中线性表、链表、队列、栈、串等几种结构的常见操作,以及顺序和链式存储过程
用c语言实现单向链表的数据结构,可以在编译器里直接使用的
数据结构实验报告,使用vC++ 6.0工具来进行调试单向链表。
西南交通大学 数据结构实验报告 单向链表 参考解答
数据结构:二叉树链表并遍历输出
数据结构:双向链表的基本程序
基础编程:单向循环链表操作实现_CPP
数据结构:图解链表,用链表实现栈的Pop和Push(c语言版) 出栈以及入栈我们只要可虑栈顶就可以,所以我们就只考虑对栈顶就行插入和删除就可以,上代码 void Pop(SqStack* s,Elemtype data) { assert(s); if (s->...
数据结构:双向链表源码,为了让读者有更好的体验,把源码上传上去,有任何问题,或者有任何bug可以直接私信我,我会及时回复,并且解决对应问题
数据结构:链表.ppt
数据结构:图解链表,用链表实现栈(c语言版) 栈(stack)是限定仅在表尾进行插入或者删除的线性表。对于栈来说,表尾端称为栈顶(top),表头端称为栈低(bottom)。不含元素的空表称为空栈。因为栈限定在表尾进行...