首页 > > 程序设计 > C/C++ >

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

2008-02-23 05:25:14来源：互联网阅读 ()

　节点类

#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;
　　}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有