数据结构学习记录连载4（上一篇中提高要求实现）

1.给出提高要求2的函数实现

/*
* 函数名称: Concatenate
* 输　入:source,target
*source:需要连接的对象
*target:被连接的对象
* 输　出:
* 功能描述: 将对象source连接到单链表target的尾部
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void Concatenate(LinkList<T>& target, LinkList<T>& source)
{
ListNode<T> *q = source.head;

while (q->next != NULL)
{
target.Insert(q->next->data, target.size);
q = q->next;
}
}

注意事项：实现时不要直接把两个链表连接起来就好了，这样造成同一块内存会释放两遍，造成运行完时报错，其实就是析构函数中出错。

而是需要用要到深拷贝的原理实现，就是取出source的数据插入到target中。上一篇中以给出测试程序。

2.提高要求2的实现：说明：本来只是修改上一篇中某些函数的实现就可以了，但是作为程序的完整性我在这里也全部给出

（1）ListNode.h结点类：

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：ListNode.h
* 摘 要：节点类的定义
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include<iostream.h>
#include<stdio.h>

template<class T> class LinkList;//前视定义，否则，无法定义友元
template<class T> class ListNode
{
friend class LinkList<T>;//定义友元
private:
ListNode<T> *next;//指向下一个结点的指针
ListNode<T> *prev;//指向上一个结点的指针
public:
T data;
ListNode(ListNode<T> *ptrNext=NULL, ListNode<T> *ptrPrev=NULL);//构造函数，用于构造头结点
ListNode(const T& item, ListNode<T> *ptrNext, ListNode<T> *ptrPrev);//构造函数，非头结点
~ListNode() {};//析构函数
friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
};

template<class T>
ListNode<T>::ListNode(ListNode<T> *ptrNext, ListNode<T> *ptrPrev)
:next(ptrNext),prev(ptrPrev)
{

}

template<class T>
ListNode<T>::ListNode(const T &item, ListNode<T> *ptrNext, ListNode<T> *ptrPrev)
{
data = item;
next = ptrNext;
prev = ptrPrev;
}

（2）LinkList.h链表类定义与实现（双向循环链表）：

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：LinkList.h
* 摘 要：双向循环链表类的定义
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include "ListNode.h"

template <class T>
class LinkList
{
private:
ListNode<T> *head;//指向头结点的指针
int size;//单链表的元素个数
ListNode<T> *currPtr;//当前结点
public:
LinkList(void);//构造函数
~LinkList();//析构函数

//线性表操作要求的成员函数
int GetListSize(void) const;//返回链表的元素个数
int ListIsEmpty(void) const;//判断单链表是否为空
ListNode<T> *Index(int pos);//定位
void Insert(const T& item, int pos);//插入
T Delete(int pos);//删除
T GetData(int pos);//取元素
void ClearList(void);//清空链表

//遍历单链表的成员函数
ListNode<T> *Reset(int pos=0);//把第pos个结点设置为当前结点currPtr
ListNode<T> *Next(void);//currPtr指向下一个结点
int EndOfList(void) const;//currPtr是否指在链表尾

friend void Concatenate(LinkList<T>& target, LinkList<T>& souce);
};

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：LinkList.cpp
* 摘 要：双向循环链表的各个功能函数的现实
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

template <class T>
LinkList<T>::LinkList(void)
{
size = 0;
head = new ListNode<T>();
head->next = head;
head->prev = head;
}

template <class T>
LinkList<T>::~LinkList()
{
ClearList();//释放所有非头结点的结点
delete head;//释放头结点
}

/*
* 函数名称: GetListSize
* 输　入:
* 输　出:
* 功能描述: 返回顺序表的元素个数size
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::GetListSize(void) const
{
return size;
}

/*
* 函数名称: ListIsEmpty
* 输　入:
* 输　出:
* 功能描述: 判断是否为空,空返回1;非返回0
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::ListIsEmpty(void) const
{
return size == 0 ? 1 : 0;
}

/*
* 函数名称: Index
* 输　入:pos
*pos:定位数据元素结点
* 输　出:
* 功能描述: 定位至第pos个数据元素结点，返回指向第pos个结点的指针
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Index(int pos)
{
if (pos < -1 || pos > size)
{
cout << "参数pos越界出错!" << endl;
exit(0);
}

if (pos == -1)
{
return head;
}

ListNode<T> *p = head->next;
int i = 0;
while (p != NULL && i <pos)
{
p = p->next;
i++;
}

return p;
}

/*
* 函数名称: Insert
* 输　入:pos
*pos:插入数据元素结点的位置
*item:插入数据结点的数据
* 输　出:
* 功能描述: 在pos个结点之前插入一个data域为item的新结点
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void LinkList<T>::Insert(const T& item, int pos)
{
if (pos < 0 || pos > size)
{
cout << "参数pos越界出错!" << endl;
exit(0);
}

ListNode<T> *p = Index(pos);
ListNode<T> *newNode = new ListNode<T>(item, NULL, NULL);

newNode->prev = p->prev;
newNode->next = p;
p->prev->next = newNode;
p->prev = newNode;

size++;
}

/*
* 函数名称: Delete
* 输　入:pos
*pos:删除数据元素结点的位置
* 输　出:
* 功能描述: 删除第pos个结点，并返回被删除结点的data
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
T LinkList<T>::Delete(int pos)
{
if (0 == size)
{
cout << "链表以空无元素可删!" << endl;
exit(0);
}
T temp;
if (pos < 0 || pos > size-1)
{
cout << "参数pos越界出错!" << endl;
exit(0);
}

ListNode<T> *p = Index(pos);
p->prev->next = p->next;
p->next->prev = p->prev;
temp = p->data;
delete p;
size--;

return temp;
}

/*
* 函数名称: ClearList
* 输　入:pos
*pos:删除数据元素结点的位置
* 输　出:
* 功能描述: 清空表为初始化状态
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void LinkList<T>::ClearList(void)
{
ListNode<T> *p = head->next;
ListNode<T> *q;

while (p != head)
{
q = p;
p = p->next;
delete q;
}
size = 0;
}

/*
* 函数名称: Reset
* 输　入:pos
*pos:数据元素结点的位置
* 输　出:
* 功能描述: 使currPtr指向结点pos，并返回currPtr
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Reset(int pos)
{
if (pos < -1 || pos > size - 1)
{
cout << "参数pos越界出错!" << endl;
exit(0);
}

if (pos == -1)
{
return head;
}

if (pos == 0)
{
currPtr = head->next;
}
else
{
currPtr = head->next;
ListNode<T> prevPtr = head;
for (int i=0; i<pos; i++)
{
prevPtr = currPtr;
currPtr = currPtr->next;
}
}

return currPtr;
}

/*
* 函数名称: Next
* 输　入:
* 输　出:
* 功能描述: 使currPtr指向下一个结点
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
ListNode<T> *LinkList<T>::Next(void)
{
if (currPtr != NULL)
{
currPtr = currPtr->next;
}

return currPtr;
}

/*
* 函数名称: EndOfList
* 输　入:
* 输　出:
* 功能描述: currPtr是否指在链表尾
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
int LinkList<T>::EndOfList(void) const
{
return currPtr == NULL ? 1 : 0;
}

/*
* 函数名称: GetData
* 输　入:pos
*pos:需要得到结点数据的位置
* 输　出:
* 功能描述: 获取pos处结点的数据
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
T LinkList<T>::GetData(int pos)
{
if (pos < 0 || pos > size-1)
{
cout << "参数pos越界出错!" << endl;
exit(0);
}

ListNode<T> *p = Index(pos);
return p->data;
}

/*
* 函数名称: Concatenate
* 输　入:source,target
*source:需要连接的对象
*target:被连接的对象
* 输　出:
* 功能描述: 将对象source连接到单链表target的尾部
* 作　者:吴友强
* 日　期:2009年10月13日
* 修　改:
* 日　期:
*/
template <class T>
void Concatenate(LinkList<T>& target, LinkList<T>& source)
{
ListNode<T> *q = source.head;

while (q->next != NULL)
{
target.Insert(q->next->data, target.size);
q = q->next;
}
}

（3）LinkListTest.cpp测试程序：

/*
* Copyright (c) 2009,FreshAir团队嵌入式软件研发组
* All rights reserved.
*
* 文件名称：LinkListTest.cpp
* 摘 要：双向循环链表类的定义
*
* 当前版本：1.0
* 作 者：吴友强
* 完成日期：2009年10月13日
*
* 取代版本：
* 原作者 ：
* 完成日期：
*/

#include <iostream.h>
#include <stdlib.h>

#include "LinkList.h"

int main(int argc, char *argv[])
{
// LinkList<int> targetList, sourceList;
//
// for (int i=0; i<10; i++)
// {
// targetList.Insert(i+10, i);
// }
//
// for (i=0; i<5; i++)
// {
// sourceList.Insert(i+5, i);
// }
// cout << "测试GetData()成员函数结果如下:" << endl;
// int n = linkList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << linkList.GetData(i) << " ";
// }
//
// cout << endl << "测试遍历成员函数结果如下:" << endl;
// ListNode<int> *p = linkList.Reset(0);
//
// while (!linkList.EndOfList())
// {
// cout << p->data << " ";
// p = linkList.Next();
// }
//
// cout << endl << "测试Delete()成员函数结果如下:" << endl;
// n = linkList.GetListSize();
// for (i=n-1; i>=0; i--)
// {
// linkList.Delete(i);
// }
//
// cout << "测试GetData()成员函数结果如下:" << endl;
// n = linkList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << linkList.GetData(i) << " ";
// }

// Concatenate(targetList, sourceList);
//
// int n = targetList.GetListSize();
// for (i=0; i<n; i++)
// {
// cout << targetList.GetData(i) << " ";
// }

LinkList<int> myList;

for (int i=0; i<100; i++)
{
myList.Insert(i+10, i);
}

cout << "插入100个元素输出如下：" << endl;
int n = myList.GetListSize();
for (i=0; i<n; i++)
{
cout << myList.GetData(i) << " ";
}

for (i=99; i>=0; i--)
{
myList.Delete(i);
}
cout << endl << "删除100个元素输出如下：" << endl;
n = myList.GetListSize();
for (i=0; i<n; i++)
{
cout << myList.GetData(i) << " ";
}
return 0;
}

说明：注释部分测试基本功能函数，其他测试提高要求。