|
|
/* LinkedList.h*/
|
|
|
/**
|
|
|
* LinkedList.h实现单链表结点类LinkNode和单链表（带头结点）类LinkedList
|
|
|
**/
|
|
|
#ifndef LINKEDLIST_H //#ifndef、#define、#endif确保LinkNode类和LinkedList类的代码仅被包含和编译一次
|
|
|
#define LINKEDLIST_H
|
|
|
#include "PerfCounter.h"
|
|
|
#include <iostream>
|
|
|
using namespace std;
|
|
|
#include "LinearList.h"
|
|
|
#include <stdlib.h>
|
|
|
;
|
|
|
template <class T>
|
|
|
struct LinkNode
|
|
|
{
|
|
|
T data; //数据域，数据元素类型为T
|
|
|
LinkNode<T> *link; //指针域，指向下一结点的指针
|
|
|
LinkNode(LinkNode<T> *ptr = NULL) //仅初始化指针成员的构造函数
|
|
|
{
|
|
|
link = ptr;
|
|
|
}
|
|
|
LinkNode(const T &item, LinkNode<T> *ptr = NULL) //初始化数据与指针成员的构造函数
|
|
|
{
|
|
|
data = item;
|
|
|
link = ptr;
|
|
|
}
|
|
|
void printToEnd()
|
|
|
{
|
|
|
for (LinkNode<T> *p = this; p; p = p->link)
|
|
|
cout << p->data << " ";
|
|
|
cout << endl;
|
|
|
}
|
|
|
};
|
|
|
template <class T>
|
|
|
class LinkedList : public LinearList<T> //定义单链表类 :
|
|
|
{
|
|
|
public:
|
|
|
PerfCounter counter;
|
|
|
LinkedList() //构造函数1
|
|
|
{
|
|
|
first = new LinkNode<T>;
|
|
|
}
|
|
|
LinkedList(const T &x) //构造函数2
|
|
|
{
|
|
|
first = new LinkNode<T>(x);
|
|
|
}
|
|
|
LinkedList(LinkedList<T> &L); //复制构造函数
|
|
|
~LinkedList() //析构函数
|
|
|
{
|
|
|
makeEmpty();
|
|
|
}
|
|
|
void makeEmpty(); //将链表置为空表
|
|
|
int Length() const; //计算链表的长度
|
|
|
LinkNode<T> *getHead() const
|
|
|
{
|
|
|
return first;
|
|
|
} //返回附加头结点指针
|
|
|
void setHead(LinkNode<T> *p)
|
|
|
{
|
|
|
first = p;
|
|
|
} //设置附加头结点指针
|
|
|
LinkNode<T> *Search(T x); //搜索含数据x的元素
|
|
|
LinkNode<T> *Locate(int i) const; //搜索第i个元素的地址
|
|
|
bool getData(int i, T &x) const; //取出第i个元素
|
|
|
void setData(int i, T &x); //用x修改第i个元素的值
|
|
|
bool Insert(int i, T &x); //在第i个元素后插入x
|
|
|
bool Remove(int i, T &x); //删除第i个元素，x返回该元素的值
|
|
|
bool IsEmpty() const //判断表空否，空返回true
|
|
|
{
|
|
|
return first->link == NULL ? true : false;
|
|
|
}
|
|
|
bool IsFull() const //表不会满
|
|
|
{
|
|
|
return false;
|
|
|
}
|
|
|
//void Sort(); //排序
|
|
|
void inputFront(T endTag); //前插法建立单链表
|
|
|
void inputRear(T endTag); //后插法建立单链表
|
|
|
void output(); //输出
|
|
|
LinkedList<T> &operator=(LinkedList<T> &L); //重载操作符：赋值
|
|
|
///增加部分///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
|
|
void input(); //前插法或后插法建立单链表
|
|
|
void output(FILE *fp); //输出
|
|
|
void OrderInsert(const T &item); //有序插入：将x插入到单链表，且插入后单链表所有结点按值从小到大有序。
|
|
|
void Uniquify(); //踢除有序单链表中所有重复的结点
|
|
|
void Uniquify(int &mn, int &cn, int &memn); //踢除有序单链表中所有重复的结点，返回元素值比较次数、元素移动次数和内存字节数
|
|
|
void Merge(const LinkedList<T> &La, const LinkedList<T> &Lb); //将有序单链表La和Lb归并为表*this，且表*this按照值从小到大有序。
|
|
|
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
|
|
|
protected:
|
|
|
LinkNode<T> *first; //链表头指针
|
|
|
};
|
|
|
template <class T>
|
|
|
LinkedList<T>::LinkedList(LinkedList<T> &L)
|
|
|
//复制构造函数
|
|
|
{
|
|
|
T value;
|
|
|
LinkNode<T> *srcptr = L.getHead();
|
|
|
LinkNode<T> *destptr = first = new LinkNode<T>;
|
|
|
while (srcptr->link != NULL)
|
|
|
{
|
|
|
value = srcptr->link->data;
|
|
|
destptr->link = new LinkNode<T>(value);
|
|
|
destptr = destptr->link;
|
|
|
srcptr = srcptr->link;
|
|
|
}
|
|
|
destptr->link = NULL;
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::makeEmpty()
|
|
|
{ //将链表置为空
|
|
|
LinkNode<T> *q;
|
|
|
if (first == NULL)
|
|
|
return;
|
|
|
while (first->link != NULL)
|
|
|
{
|
|
|
q = first->link;
|
|
|
first->link = q->link;
|
|
|
delete q;
|
|
|
}
|
|
|
}
|
|
|
template <class T>
|
|
|
int LinkedList<T>::Length() const
|
|
|
{ //计算带附加头结点的单链表长度
|
|
|
LinkNode<T> *p = first->link;
|
|
|
int count = 0;
|
|
|
while (p != NULL)
|
|
|
{
|
|
|
p = p->link;
|
|
|
count++;
|
|
|
}
|
|
|
return count;
|
|
|
}
|
|
|
template <class T>
|
|
|
LinkNode<T> *LinkedList<T>::Search(T x)
|
|
|
{ //在表中搜索含数据x的结点，搜索成功时函数返回该结点地址，否则返回NULL值。
|
|
|
LinkNode<T> *current = first->link;
|
|
|
while (current != NULL)
|
|
|
{
|
|
|
if (current->data == x)
|
|
|
break;
|
|
|
else
|
|
|
current = current->link;
|
|
|
}
|
|
|
return current;
|
|
|
}
|
|
|
template <class T>
|
|
|
LinkNode<T> *LinkedList<T>::Locate(int i) const
|
|
|
{ //定位函数，返回表中第i个元素的地址。若i<0或i超出表中结点个数，则返回NULL
|
|
|
if (i < 0) return NULL;
|
|
|
LinkNode<T> *current = first;
|
|
|
int k = 0;
|
|
|
while (current != NULL && k < i)
|
|
|
{
|
|
|
current = current->link;
|
|
|
k++;
|
|
|
}
|
|
|
return current;
|
|
|
}
|
|
|
template <class T>
|
|
|
bool LinkedList<T>::getData(int i, T &x) const
|
|
|
{ //取出链表第i个元素的值
|
|
|
if (i < 0)
|
|
|
return false;
|
|
|
LinkNode<T> *current = Locate(i);
|
|
|
if (current == NULL)
|
|
|
return false;
|
|
|
else
|
|
|
{
|
|
|
x = current->data;
|
|
|
return true;
|
|
|
}
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::setData(int i, T &x)
|
|
|
{ //给链表第i个元素赋值x
|
|
|
if (i <= 0) return;
|
|
|
LinkNode<T> *current = Locate(i);
|
|
|
if (current == NULL)
|
|
|
return;
|
|
|
else
|
|
|
current->data = x;
|
|
|
}
|
|
|
template <class T>
|
|
|
bool LinkedList<T>::Insert(int i, T &x)
|
|
|
{ //将新元素x插入在链表中第i个结点之后
|
|
|
LinkNode<T> *current = Locate(i);
|
|
|
if (current == NULL)
|
|
|
return false;
|
|
|
LinkNode<T> *newNode = new LinkNode<T>(x);
|
|
|
if (newNode == NULL)
|
|
|
{
|
|
|
cout << "内存分配错误！" << endl;
|
|
|
exit(1);
|
|
|
}
|
|
|
newNode->link = current->link;
|
|
|
current->link = newNode;
|
|
|
return true;
|
|
|
}
|
|
|
template <class T>
|
|
|
bool LinkedList<T>::Remove(int i, T &x)
|
|
|
{ //将链表中第i个元素删除，通过引用类型参数x返回该元素的值
|
|
|
LinkNode<T> *current = Locate(i - 1);
|
|
|
if (current == NULL || current->link == NULL)
|
|
|
return false;
|
|
|
LinkNode<T> *del = current->link;
|
|
|
current->link = del->link;
|
|
|
x = del->data;
|
|
|
delete del;
|
|
|
return true;
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::output()
|
|
|
{ //单链表的输出函数：将单链表中所有数据按逻辑顺序输出到屏幕上
|
|
|
LinkNode<T> *current = first->link;
|
|
|
while (current != NULL)
|
|
|
{
|
|
|
cout << current->data << " ";
|
|
|
current = current->link;
|
|
|
}
|
|
|
cout << endl;
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::output(FILE *fp)
|
|
|
{ //单链表的输出函数：将单链表中所有数据按逻辑顺序输出到fp文件上
|
|
|
LinkNode<T> *current = first->link;
|
|
|
while (current != NULL)
|
|
|
{
|
|
|
fprintf(fp, "%d ", current->data);
|
|
|
current = current->link;
|
|
|
}
|
|
|
fprintf(fp, "\n");
|
|
|
}
|
|
|
template <class T>
|
|
|
LinkedList<T> &LinkedList<T>::operator=(LinkedList<T> &L)
|
|
|
{ //重载操作符：赋值操作
|
|
|
T value;
|
|
|
LinkNode<T> *srcptr = L.getHead();
|
|
|
LinkNode<T> *destptr = first = new LinkNode<T>;
|
|
|
while (srcptr->link != NULL)
|
|
|
{
|
|
|
value = srcptr->link->data;
|
|
|
destptr->link = new LinkNode<T>(value);
|
|
|
destptr = destptr->link;
|
|
|
srcptr = srcptr->link;
|
|
|
}
|
|
|
destptr->link = NULL;
|
|
|
return *this;
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::input()
|
|
|
{
|
|
|
T endTag;
|
|
|
int frontORrear; //前插或后插,值为0前插，值为1后插
|
|
|
cout << "建立单链表使用前插法输入0，使用后插法输入1:";
|
|
|
cin >> frontORrear;
|
|
|
cout << "输入建立结束标志:";
|
|
|
cin >> endTag;
|
|
|
cout << "输入各个数据元素值（最后一个值是结束标志值）:";
|
|
|
if (frontORrear == 0)
|
|
|
inputFront(endTag);
|
|
|
else
|
|
|
inputRear(endTag);
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::inputFront(T endTag)
|
|
|
{ //endTag是约定的输入序列结束标志
|
|
|
LinkNode<T> *newNode;
|
|
|
T val;
|
|
|
makeEmpty();
|
|
|
cin >> val;
|
|
|
while (val != endTag)
|
|
|
{
|
|
|
newNode = new LinkNode<T>(val);
|
|
|
if (newNode == NULL)
|
|
|
{
|
|
|
cerr << "存储分配错误！" << endl;
|
|
|
exit(1);
|
|
|
}
|
|
|
newNode->link = first->link;
|
|
|
first->link = newNode;
|
|
|
cin >> val;
|
|
|
}
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::inputRear(T endTag)
|
|
|
{ //endTag是约定的输入序列结束标志
|
|
|
LinkNode<T> *newNode, *last;
|
|
|
T val;
|
|
|
makeEmpty();
|
|
|
cin >> val;
|
|
|
last = first;
|
|
|
while (val != endTag)
|
|
|
{
|
|
|
newNode = new LinkNode<T>(val);
|
|
|
if (newNode == NULL)
|
|
|
{
|
|
|
cerr << "存储分配错误！" << endl;
|
|
|
exit(1);
|
|
|
}
|
|
|
last->link = newNode;
|
|
|
last = newNode;
|
|
|
cin >> val;
|
|
|
}
|
|
|
last->link = NULL;
|
|
|
}
|
|
|
template <class T>
|
|
|
void LinkedList<T>::OrderInsert(const T &x) //有序插入数据元素x
|
|
|
{
|
|
|
LinkNode<T> *curr, *pre;
|
|
|
//初始化
|
|
|
curr = first->link; //curr指向首元结点
|
|
|
pre = first; //pre指向头结点
|
|
|
//定位插入位置
|
|
|
while (curr != NULL && curr->data <= x)
|
|
|
{
|
|
|
pre = curr;
|
|
|
curr = curr->link;
|
|
|
}
|
|
|
LinkNode<T> *newNode = new LinkNode<T>(x, pre->link); //申请一个结点并赋值
|
|
|
pre->link = newNode; //把新结点插入在pre所指结点后
|
|
|
}
|
|
|
/***********************************
|
|
|
作业中要实现的部分
|
|
|
***********************************/
|
|
|
//踢除有序单链表中所有重复的结点，要求单链表每个结点被访问一次，且仅被访问一次。尽可能高效。无返回值
|
|
|
template <class T>
|
|
|
void LinkedList<T>::Uniquify()
|
|
|
{
|
|
|
int _;
|
|
|
Uniquify(_, _, _);
|
|
|
//在此添加完成任务1.1的代码
|
|
|
}
|
|
|
//踢除有序单链表中所有重复的结点，要求单链表每个结点被访问一次，且仅被访问一次。尽可能高效。返回元素值比较次数、元素移动次数和内存字节数
|
|
|
template <class T>
|
|
|
void LinkedList<T>::Uniquify(int &mn, int &cn, int &memn)
|
|
|
{
|
|
|
//在此添加完成任务1.2的代码。在（任务1.1）Uniquify()函数的基础上，增加合计并返回算法中元素移动总次数、元素值比较总次数和辅助空间字节总数的代码，测试Uniquify()的高效性。
|
|
|
//算法中如果结点的data域或link域被改变，则mn需累加一次。
|
|
|
//凡出现两个结点的数据域的值比较大小，则cn需累加一次。
|
|
|
//凡出现定义辅助的变量或数组，则memn需累加相应的字节数。C++中sizeof(LinkNode<T>*)为4个字节。
|
|
|
memn = 8;
|
|
|
free(malloc(11));
|
|
|
decltype(first) cur = first, nxt;
|
|
|
while (cur && (nxt = cur->link))
|
|
|
{
|
|
|
while (nxt && cur->data == nxt->data)
|
|
|
{
|
|
|
cur->link = nxt->link;
|
|
|
mn++;
|
|
|
cn++;
|
|
|
delete nxt;
|
|
|
nxt = cur->link;
|
|
|
}
|
|
|
cn++;
|
|
|
cur = nxt;
|
|
|
}
|
|
|
}
|
|
|
//将有序单链表La和Lb归并为表*this，且表*this按照值从小到大有序。要求3个单链表La,Lb,*this每个结点被访问一次，且仅被访问一次。算法尽可能高效。
|
|
|
template <class T>
|
|
|
void LinkedList<T>::Merge(const LinkedList<T> &La, const LinkedList<T> &Lb)
|
|
|
{ //在此添加完成任务2的代码
|
|
|
counter.inc_mem(12);
|
|
|
auto pa = La.first->link, pb = Lb.first->link;
|
|
|
auto nxt = &first->link;
|
|
|
for (; pa && pb; nxt = &(*nxt)->link)
|
|
|
{
|
|
|
if (pa->data < pb->data)
|
|
|
*nxt = new LinkNode<T>(pa->data), pa = pa->link;
|
|
|
else
|
|
|
*nxt = new LinkNode<T>(pb->data), pb = pb->link;
|
|
|
counter.inc_cmp(1);
|
|
|
counter.inc_mov(1);
|
|
|
}
|
|
|
while (pa) *nxt = new LinkNode<T>(pa->data), pa = pa->link, nxt = &(*nxt)->link, counter.inc_mov(1);
|
|
|
while (pb) *nxt = new LinkNode<T>(pb->data), pb = pb->link, nxt = &(*nxt)->link, counter.inc_mov(1);
|
|
|
}
|
|
|
#endif |
