数据结构学习(C++)之单链表

节点类

#ifndef Node_H
#define Node_H
template <class Type> class Node //单链节点类
{
　public:
　　Type data;
　　Node<Type> *link;
　　Node() : data(Type()), link(NULL) {}
　　Node(const Type &item) : data(item), link(NULL) {}
　　Node(const Type &item, Node<Type> *p) : data(item), link(p) {}
　};
#endif

【说明】因为数据结构里用到这个结构的地方太多了，如果用《数据结构》那种声明友元的做法，那声明不知道要比这个类的本身长多少。不如开放成员，事实上，这种结构只是C中的struct，除了为了方便初始化一下，不需要任何的方法，原书那是画蛇添足。下面可以看到，链表的public部分没有返回Node或者Node*的函数，所以，别的类不可能用这个开放的接口对链表中的节点操作。

【重要修改】原书的缺省构造函数是这样的Node() : data(NULL), link(NULL) {} 。我原来也是照着写的，结果当我做扩充时发现这样是不对的。当Type为结构而不是简单类型（int、……），不能简单赋NULL值。这样做使得定义的模板只能用于很少的简单类型。显然，这里应该调用Type的缺省构造函数。 这也要求，用在这里的类一定要有缺省构造函数。在下面可以看到构造链表时，使用了这个缺省构造函数。当然，这里是约定带表头节点的链表，不带头节点的情况请大家自己思考。

【闲话】请不要对int *p = new int(1);这种语法有什么怀疑，实际上int也可以看成一种class。

单链表类定义与实现

#ifndef List_H
#define List_H
#ifndef TURE
　#define TURE 1
#endif
#ifndef FALSE
　#define FALSE 0
#endif
typedef int BOOL;
#include "Node.h"
template <class Type> class List //单链表定义
{
　//基本上无参数的成员函数操作的都是当前节点，即current指的节点
　//认为表中“第1个节点”是第0个节点，请注意，即表长为1时，最后一个节点是第0个节点
　public:
　　List() { first = current = last = new Node<Type>; prior = NULL; }
　　~List() { MakeEmpty(); delete first; }
　　 void MakeEmpty() //置空表
　　{
　　　Node<Type> *q;
　　　while (first->link != NULL)
　　　{
　　　　q = first->link;
　　　　first->link = q->link;
　　　　delete q;
　　　}
　　　Initialize();
　　}
　　BOOL IsEmpty()
　　{
　　　if (first->link == NULL)
　　　{
　　　　Initialize();
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　int Length() const //计算带表头节点的单链表长度
　　{
　　　Node<Type> *p = first->link;
　　　int count = 0;
　　　while (p != NULL)
　　　{
　　　　p = p->link;
　　　　count++;
　　　}
　　　return count;
　　}
　　Type *Get()//返回当前节点的数据域的地址
　　{
　　　if (current != NULL) return &current->data;
　　　else return NULL;
　　}
　　BOOL Put(Type const &value)//改变当前节点的data，使其为value
　　{
　　　if (current != NULL)
　　　{
　　　　current->data = value;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　Type *GetNext()//返回当前节点的下一个节点的数据域的地址，不改变current
　　{
　　　if (current->link != NULL) return &current->link->data;
　　　else return NULL;
　　}
　　Type *Next()//移动current到下一个节点，返回节点数据域的地址
　　{
　　　if (current != NULL && current->link != NULL)
　　　{
　　　　prior = current;
　　　　current = current->link;
　　　　return &current->data;
　　　}
　　　else
　　　{
　　　　return NULL;
　　　}
　　}
　　void Insert(const Type &value)//在当前节点的后面插入节点，不改变current
　　{
　　　Node<Type> *p = new Node<Type>(value, current->link);
　　　current->link = p;
　　}
　　BOOL InsertBefore(const Type &value)//在当前节点的前面插入一节点，不改变current，改变prior
　　{
　　　Node<Type> *p = new Node<Type>(value);
　　　if (prior != NULL)
　　　{
　　　　p->link = current;
　　　　prior->link = p;
　　　　prior = p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　BOOL Locate(int i)//移动current到第i个节点
　　{
　　　if (i <= -1) return FALSE;
　　　　current = first->link;
　　　　for (int j = 0; current != NULL && j < i; j++, current = current->link)
　　　　　prior = current;
　　　　　if (current != NULL) return TURE;
　　　　　else return FALSE;
　　}
　　void First()//移动current到表头
　　{
　　　current = first;
　　　prior = NULL;
　　}
　　void End()//移动current到表尾
　　{
　　　if (last->link != NULL)
　　　{
　　　　for ( ;current->link != NULL; current = current->link)
　　　　　prior = current;
　　　　　last = current;
　　　}
　　　current = last;
　　}
　　BOOL Find(const Type &value)//移动current到数据等于value的节点
　　{
　　　if (IsEmpty()) return FALSE;
　　　for (current = first->link, prior = first; current != NULL && current->data != value;
　　　current = current->link)
　　　　prior = current;
　　　　if (current != NULL) return TURE;
　　　　else return FALSE;
　　}
　　BOOL Remove()//删除当前节点，current指向下一个节点，如果current在表尾，执行后current = NULL
　　{
　　　if (current != NULL && prior != NULL)
　　　{
　　　　Node<Type> *p = current;
　　　　prior->link = p->link;
　　　　current = p->link;
　　　　delete p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　BOOL RemoveAfter()//删除当前节点的下一个节点，不改变current
　　{
　　　if (current->link != NULL && current != NULL)
　　　{
　　　　Node<Type> *p = current->link;
　　　　current->link = p->link;
　　　　delete p;
　　　　return TURE;
　　　}
　　　else return FALSE;
　　}
　　friend ostream & operator << (ostream & strm, List<Type> &l)
　　{
　　　l.First();
　　　while (l.current->link != NULL) strm << *l.Next() << " " ;
　　　　strm << endl;
　　　　l.First();
　　　　return strm;
　　}
　　protected:
　　/*主要是为了高效的入队算法所添加的。因为Insert()，Remove()，RemoveAfter()有可能改变last但没有改变last所以这个算法如果在public里除非不使用这些，否则不正确。但是last除了在队列中非常有用外，其他的时候很少用到，没有必要为了这个用途而降低Insert()，Remove()的效率所以把这部分放到protected，实际上主要是为了给队列继承*/ void LastInsert(const Type &value)
　{
　　Node<Type> *p = new Node<Type>(value, last->link);
　　last->link = p;
　　last = p;
　}
　void Initialize()//当表为空表时使指针复位
　{
　　current = last = first;
　　prior = NULL;
　}
　//这部分函数返回类型为Node<Type>指针,是扩展List功能的接口
　
　Node<Type> *pGet()
　{
　　return current;
　}
　Node<Type> *pNext()
　{
　　prior = current;
　　current = current->link;
　　return current;
　}
　Node<Type> *pGetNext()
　{
　　return current->link;
　}
　Node<Type> *pGetFirst()
　{
　　return first;
　}
　Node<Type> *pGetLast()
　{
　　return last;
　}
　Node<Type> *pGetPrior()
　{
　　return prior;
　}
　void PutLast(Node<Type> *p)
　{
　　last = p;
　}
//这部分插入删除函数不建立或删除节点，是原位操作的接口
　void Insert(Node<Type> *p)
　{
　　p->link = current->link;
　　current->link = p;
　}
　void InsertBefore(Node<Type> *p)
　{
　　p->link = current;
　　prior->link = p;
　　prior = p;
　}
　void LastInsert(Node<Type> *p)
　{
　　p->link = NULL;
　　last->link = p;
　　last = p;
　}
　Node<Type> *pRemove()
　{
　　if (current != NULL && prior != NULL)
　　{
　　　Node<Type> *p = current;
　　　prior->link = current->link;
　　　current = current->link;
　　　return p;
　　}
　　else return NULL;
　}
　Node<Type> *pRemoveAfter()
　{
　　if (current->link != NULL && current != NULL)
　　{
　　　Node<Type> *p = current->link;
　　　current->link = current->link->link;
　　　return p;
　　}
　　else return NULL;
　}
　private:
　　List(const List<Type> &l);
　　Node<Type> *first, *current, *prior, *last;
　　//尽量不要使用last，如果非要使用先用End()使指针last正确
};
#endif

【说明】我将原书的游标类Iterator的功能放在了链表类中，屏蔽掉了返回值为Node以及Node*类型的接口，这样的链表简单、实用，扩充性能也很好。

时间： 2024-08-10 09:29:04

数据结构学习(C++)之单链表的相关文章

c++ 数据结构-数据结构c＋＋单链表问题 急！！

问题描述 数据结构c++单链表问题 急!! 5C SinglyList& operator*=(SinglyList &list) //仅保留那些也包含在list中的元素,集合交 解决方案 单链表逆序的C++实现 解决方案二: http://ask.csdn.net/questions/253462

@数据结构大神，单链表的插入，56行怎么错了？求解释~

问题描述 @数据结构大神,单链表的插入,56行怎么错了?求解释~ include include typedef struct Node { char data; struct Node *next; }Node,*Linklist;//先定义.后使用 //定义数据L-分配头节点-插入数据,连-接-返回 Linklist Createfromhead() { Linklist L;Node*s;int flag=1;char c; L=(Linklist)malloc(sizeof(Node))

c++ 数据结构-实现以下对单链表的操作，要求单链表一次遍历效率(数据结构c＋＋)

问题描述 实现以下对单链表的操作,要求单链表一次遍历效率(数据结构c++) double averageExceptMaxMin(SinglyList &list) ?//去掉最高分和最低分,再求平均值 解决方案 double averageExceptMaxMin(SinglyList &list){ double d = 0.0; int n = 0; double max = 0.0; double min = 0.0; Node * node = &list.head; w

数据结构体模版---循环单链表

版权声明:本文为博主原创文章 && 转载请著名出处 @ http://blog.csdn.net/gatieme [cpp] view plain copy print? #include <stdio.h>   #include <stdlib.h>   #include <stdbool.h>   #include <assert.h>      //#define DEBUG             // 调试插桩信息宏      //

数据结构C#版笔记--单链表(LinkList)

上一篇学习了"顺序表(SeqList)",这一篇来看下"单链表(LinkList)".在上一篇的最后,我们指出了:顺序表要求开辟一组连续的内存空间,而且插入/删除元素时,为了保证元素的顺序性,必须对后面的元素进行移动.如果你的应用中需要频繁对元素进行插入/删除,那么开销会很大.   而链表结构正好相反,先来看下结构: 每个元素至少具有二个属性:data和next.data用来存放数据,而next用来指出它后面的元素是谁(有点"指针"的意思). 链

用java学习数据结构--单链表

数据|数据结构 /* * Created on 2004-9-10 * * 单链表中的结点类型声明. */package org.arliang;/** * @author 李梁 * * 单链表中的结点. */public class node{ private int data; //存放数据 private node link; //链接的下一个接点. public static void main(String[]args) { } /** * @return Returns the da

C++数据结构分别用顺序表和单链表的存储形式

问题描述 C++数据结构分别用顺序表和单链表的存储形式 分别用顺序表和单链表的存储形式实现将输入的两个大整数(超过20位)相加并打印和值:自行设计基本操作,要求两种存储结构中操作接口相同 解决方案 数据结构-----顺序表与单链表的实现 解决方案二: 存储结构的引入是为了将大数字分解成若干个小数字么? 解决方案三: 大数相加必须,分解成若单个小数字呀,采用哪个储存结构只是题目要求而已,用数组也可以实现代码如下#include #include int main() { char str1[100

struct-@数据结构大神，单链表的插入，47行怎么错了？求解释~

问题描述 @数据结构大神,单链表的插入,47行怎么错了?求解释~ include include typedef struct Node { char data; struct Node *next; }Node,*Linklist;//先定义.后使用 //定义数据L-分配头节点-插入数据,连接-返回 Linklist Createfromhead() { Linklist L;Node*s;int flag=1;char c; L=(Linklist)malloc(sizeof(Node));

C语言数据结构单链表之温故而知新

抛弃繁杂的定义,以实用,实战的角度来学习数据结构,这将使得数据结构的学习非常的简单. 前面已经学习了单链表的创建操作:http://blog.csdn.net/morixinguan/article/details/68951912 这节,将单链表温习的笔记共享出来,然后写一个例子,以防自己忘记. 1.单链表的数据结构的定义: 创建节点函数原型可定义如下: struct list *create_node(int data) ; 如何创建单链表的节点,主要分以下步骤: (1)给当前的每个节点的数