数据结构实验报告—链表.docx

《算法与数据结构》课程
实 验 报 告
教师评阅意见：
签名：
年 月
日
实验成绩：
一、 实验目的
1、 实现线性表的链式存储结构（链表）。
2、 熟悉C++程序的基本结构，掌握程序中的头文件、实现文件和主:
List () (
first 二 new LinkNode<T>;
}
List (const T& x) (
first 二 new LinkNode < T >(x);
}
//复制构造函数
〃析构函数
//将链表置为空表
//计算链表的长度
List(List<T>& L);
~List() { makeEmptyO ; } void makeEmpty ();
int Length ();
LinkNode<T> *getHead() ( return first;
} 〃返回附加头结点地址
LinkNode<T> *Search(T x); 〃搜索含数据x的元素 LinkNode<T> *Locate(int i) ; //搜索第i个元素的地址
bool getData(int i, T& x) ; //取出第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 () (
return first->link == NULL ? true : false;
} 〃判表空否？空则返回true
bool IsFull () ( return false;
} 〃判表满否？不满则返回false
void SortO ; //排序
void inputFront (T endTag); 〃前插法输入
void inputRear (T endTag); 〃后插法插入
void previousData(T endTag); 〃打开原有链表数据文件数据文件
void output () ; //输出
void outputFile() ; //输出到文件
List<T>& operator= (List<T>& L); 〃重载函数：赋值
}；
/**
*复制构造函数
*/
template<class T>
List<T>::List(List<T>& L) (
T value;
LinkNode<T> *srcptr = L. getHeadO ;
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 List<T>::makeEmptyO (
LinkNode<T> *q;
while (first->link != NULL) ( q = first~>link; first->link = q->link; delete q;
)
}
/**
*计算带附加结点的单链表的长度
*/
template<class T> int List<T>::Length() {
LinkNode<T> *p = first->link; int count = 0; while (p != NULL) ( p = p->link; count++;
}
return count;
}
/**
*在表中搜索含数据x的结点，搜索成功时函数返回该结点地址，否则返回NULL值
*/
template<class T>
LinkNode<T> *List<T>::Search(T x) { LinkNode<T> ^current = first->link; while (current != NULL) { if (current->data == x) break; else
current = current->link;
}
return current;
)
/**
*定位函数：返回表中第i个元素的地址。若i<0或i超出表中的结点个数，则返回NULL