当前位置：文档库 › 线性表及其应用

线性表及其应用

集美大学数据结构课程实验报告

课程名称：数据结构班级：实验成绩：指导教师：姓名：

实验项目名称：线性表及其应用学号：2011872070上机时间：

一、目的

理解线性表数据结构及其应用

二、实验内容

1．线性表的抽象数据类型的定义

2．顺序表类定义(包括方法实现)及测试（要求：main中要测试每个方法）

测试如下：

定义一个顺序表，最大50,存储以下数据元素(1,-9,6,10,400,30,60),输出之。查找的测试如下：元素30存在否，测试元素67存在否。插入测试如下：在表的第5个位置插入元素值为12，在第10个元素后插入元素值为18。删除测试:……。.

注：附录中可参考部分

3．链表的类定义(包括方法实现)及测试（要求：main中要测试每个方法）注：见附录，运行并对程序加注释

4．使用顺序表实现有序集合的合并，并分析其时间与空间复杂度。测试LA('a,e,g,h,x,y )与LB(c,d,e,r)的合并并输出。

5．使用链表实现一元多项式运算，并测试以下两个一元多项的加法，输出实现加法后的结果表示。并分析其时间与空间复杂度

pa=1+10x3-2x100+1000x1300,pb=-1+13x15+2x100-10x1010

6．设计一个循环链表类，完成约瑟夫问题的解决。测试共10个人围成一圈，每个人都有一个表示其身份的号牌，从第1个人开始报数，报到3的人出列，求出列的号牌顺序。可简化用1….10分别表示第1个人至第10个人的号牌。

三、实验使用环境

Microsoft Visual C++ 6.0

四、实验关键代码与结果展示（部分截图）

顺序表：

#ifndef SEQLIST_H

#define SEQLIST_H

#include

using namespace std;

const int defaultSize = 100;

template class SeqList{

protected:

T *data;

int maxSize;

int last;

public:

SeqList(int sz = defaultSize);

SeqList(SeqList &L);

~SeqList(){

delete []data;}

void reSize(int newSize);

int Size() const { //计算表最大可容纳表项个数

return maxSize;}

int Length()const{

return last+1; }

int tig();

int Search(T &x) const;

int Locate(int i) const;

bool getData(int i,T&x) const{ //取第i个表项的值

if(i>0 && i<=last+1){

x=data[i-1];

return true;}

else return false;}

void setData(int i, T &x) { //用X修改第i个表项的值

if (i>0 && i<=last+1){

data[i-1] = x;}}

bool Insert(int i, T &x);

bool Remove(int i, T &x);

bool IsEmpty(){ //判表空

return (last == -1);}

bool IsFull(){ //判表满

return (last == maxSize-1);}

void Sort();

void input();

void output();

SeqList operator = (SeqList &L);

friend istream& operator >> (istream &in, SeqList &R){

https://www.wendangku.net/doc/264093217.html,st = -1;

while (!in.eof()){

https://www.wendangku.net/doc/264093217.html,st++;

if (https://www.wendangku.net/doc/264093217.html,st == R.maxSize) R.reSize(2*R.maxSize);

assert(in >> R.data[https://www.wendangku.net/doc/264093217.html,st]);

} return in; }

friend ostream& operator << (ostream &out, SeqList &R){ for (int i = 0; i <= https://www.wendangku.net/doc/264093217.html,st; i++){

cout << "#" << i+1 << ":\t" << R.data[i] << endl;} return out; }};

template SeqList::SeqList(int sz){ //构造函数if (sz > 0){

maxSize = sz;

last = -1;

data = new T[maxSize];

if (data == NULL){

cerr << "存储分配错误!" << endl;

exit(1); }}}

template SeqList::SeqList(SeqList &L) {//复制构造函数maxSize = L.Size();

last = L.Length() - 1;

data = new T[maxSize];

if (data == NULL){

cerr << "存储分配错误!" << endl;

exit(1);}

for (int i = 1; i <= last+1; i++) data[i-1] = *(L.getData(i));} templatevoid SeqList::reSize(int newSize) {

//扩充顺序表的存储空间大小

if (newSize <= 0){

cerr << "无效的数组大小!" << endl;

return;}

if (newSize != maxSize) {

T *newarray = new T[newSize];

if (newarray == NULL) {

cerr << "存储分配错误!" << endl;

exit(1);}

int n = last;

T *srcptr = data;

T *destptr = newarray;

while (n--) *destptr++ = *srcptr++;

delete []data;

data = newarray;

maxSize = newSize; }}

templateint SeqList::Search(T &x)const {

//搜索X在表中的位置，函数返回表项序号

for (int i = 0; i <= last; i++) {

if (data[i] == x) return i+1;

} return 0; }

templateint SeqList::Locate(int i)const { //定位第i个表项，函数返回表项序号

if (i >= 1 && i <= last+1) return i;

else return 0; }

templatebool SeqList::Insert(int i, T &x) { //插入操作if (last == maxSize-1) return false;

if (i < 0 || i > last+1) return false;

for (int j = last; j >= i; j--) data[j+1] = data[j];

data[i] = x; last++; return true;}

templatebool SeqList::Remove(int i, T &x) {//删除操作if (last == -1) return false;

if (i < 1 || i > last+1) return false;

x = data[i-1];

for (int j = i; j <= last; j++) data[j-1] = data[j];

last--; return true;}

templatevoid SeqList::Sort(){

//排序操作

for (int i = 1; i <= last; i++){

for (int j = last; j >= i; j--){

if (data[j-1] > data[j]) {

T tmp = data[j-1];

data[j-1] = data[j];

data[j] = tmp;

}}}}

templatevoid SeqList::input(){//输入操作

cout << "开始建立顺序表，请输入表中元素个数:";

while (1) {

assert(cin >> last);

last--;

if (last < 0) {

cout << "表元素个数输入有误!\n";

cout << "请重新输入，并且大小不能小于0:";}

else if (last > maxSize-1){

cout << "表元素个数输入有误!\n";

cout << "请重新输入，并且大小不能超过:"<

else break; }

cout << "\n请逐个输入表元素:" << endl;

for (int i = 0; i <= last; i++){

cout << "#" << i+1 << ":";

assert(cin >> data[i]);

}}

templatevoid SeqList::output(){

//输出操作

cout << "\n顺序表当前元素最后位置为:" << last+1 << endl;

for (int i = 0; i <= last; i++)

cout << "#" << i+1 << ":\t" << data[i] << endl; }

templateSeqList SeqList::operator = (SeqList &L) {

//重载操作

maxSize = L.Size();

last = L.Length()-1;

delete []data;

data = new T[maxSize];

if (data == NULL) {

cerr << "存储分配错误!" << endl;

exit(1); }

for (int i = 1; i <= last+1; i++) data[i-1] = L.getData(i); }

templateint SeqList::tig(){

int num;

cout<<"请输入你所要操作的模块编号：【1:打印顺序表 2:排序 3:插入 4:删除 5:查询】"<<"=";

cin>>num;

return num;

}#endif

main测试模块

#include "SeqList.h"

#include

using namespace std;

int main(){

SeqList list(5);

SeqList LA(5);

SeqList LB(5);

ifstream fin("list.txt");

assert(fin);

fin >> list;

int i,elem;

cout << " 打印顺序表，排序,插入，删除，查询操作模块测试\n";

cout << "------------------------------------------------\n";

int num=list.tig();

if(num==1) {

cout << "当前的顺序表元素为:\n" << list << endl;

main();}

else if(num==2){

cout << "2. 排序模块:\n";

list.Sort();

cout << "排序操作后的表元素为:\n" << list << endl;

cout << "========================================\n";

main();}

else if(num==3){

while(1){

cout << "3. 插入模块:\n";

cout << "请输入你所要插入的位置和元素: ";

cin >> i >> elem;

if (list.Insert(i, elem)){

cout << "插入成功!\n";

cout << "\n插入后的元素列表\n" << list << endl;}

else cout << "插入失败!\n"; }

main();}

else if(num==4){

while(1){

cout << "----------------------------------------\n";

cout << "4. 删除模块:\n";

cout << "请输入你所要删除的位置: ";

cin >> i;

if (list.Remove(i, elem)){

cout << "元素 " << elem << " 删除成功!\n";

cout << "\n删除后的元素列表\n" << list << endl; } else cout << "删除失败!\n";}}

else if(num==5){

while(1){

cout << "----------------------------------------\n";

cout << "5. 查找模块:\n";

cout << "请输入你所要查询的元素: ";

cin >> elem;

i = list.Search(elem);

if (i != 0)

cout << "你查询的元素为 " << elem << " 处于第 " << i <<"个位置上" ".\n";

else cout << "你所要查找的元素不存在!\n";

cout << "\n----------------------------------------\n";}}

else cout<<"输入错误，请重新输入你所要进行的操作!";

cout << "\n测试结束!" << endl;

return 0;}

测试结果截图

单链表#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include

using namespace std;

#ifndef INSMOD_INF_INR

#define INSMOD_INF_INR

enum InsMod {INF, INR};

#endif

template struct LinkNode{

T data;

LinkNode *link;

LinkNode(LinkNode *ptr = NULL){

link = ptr;}

LinkNode(const T &item, LinkNode *ptr = NULL){

data = item; link = ptr;}};

template class List{

public:

List(){

first = new LinkNode; } //构造函数

List(const T &x){ //构造函数first = new LinkNode(x);}

List(List &L);

~List(){

makeEmpty();delete first;}

void makeEmpty();

int tig(); //将链表置为空

int Length()const;

LinkNode *getHead()const{

return first;}

LinkNode *Search(const T &x);

LinkNode *Locate(int i);

bool getData(int i,T&x)const;

void setData(int i, T &x);

bool Insert(int i, T &x);

bool Remove(int i, T &x);

bool IsEmpty()const{

return (first->link == NULL)?true:false;}

bool IsFull()const{

return false;}

void Sort();

void Inverse();

void input(T endTag, InsMod im = INR);

void output();

List &operator = (List &L);

friend ostream& operator << (ostream &out, List &L){ LinkNode *current = L.first->link;

while (current){

out << current->data <<" ";

current = current->link;}

out<

friend istream& operator >> (istream &in, List &L){

LinkNode *newNode,*last; T val;

L.makeEmpty();

last = L.first;

while (!in.eof()){

in >> val;

newNode = new LinkNode(val);

assert(newNode);

last->link = newNode;

last = newNode;}

last->link = NULL; return in;}

protected:

LinkNode *first;

void inputFront(T endTag);

void inputRear(T endTag); };

template List::List(List &L){ //复制构造函数T value;

LinkNode *srcptr = L.first();

LinkNode *destptr = first = new LinkNode;

while (srcptr->link){

value = srcptr->link->data;

destptr->link = new LinkNode(value);

destptr = destptr->link;

srcptr = srcptr->link;}

destptr->link = NULL;}

template void List::makeEmpty(){ //将链表置为空LinkNode *q;

while (first->link) {

q = first->link; first->link = q->link; delete q;}}

template int List::Length()const{

LinkNode *p = first->link;

int count = 0;

while (p){

p = p->link; count++;}

return count;}

template LinkNode *List::Search(const T &x){ //查找LinkNode *current = first->link;

while (current && current->data != x){

current = current->link;}

return current;}

template LinkNode *List::Locate(int i){ //定位元素位置if (i < 0) return NULL;

LinkNode *current = first; int k = 0;

while (current && k < i){

current = current->link; k++;}

return current;}

template bool List::getData(int i,T&x)const{ //取出链表这两个第i个元素的值

if (i <= 0) r eturn NULL;

LinkNode *current = Locate(i);

if (!current) return false;

else{ x=current->data

return true;}}

template void List::setData(int i, T &x){ //给链表中第i个元素赋值if (i <= 0) r eturn;

LinkNode *current = Locate(i);

if (!current) return;

else current->data = x;}

template bool List::Insert(int i, T &x){ //插入

LinkNode *current = Locate(i);

if (!current) return false;

LinkNode *newNode = new LinkNode(x);

if (!newNode){

cerr << "Memory allocating error!" << endl;

exit(1);}

newNode->link = current->link;

current->link = newNode; return true;}

template bool List::Remove(int i, T &x){ //删除

LinkNode *current = Locate(i-1);

if (!current || !current->link) return false;

LinkNode *del = current->link;

current->link = del->link;

x = del->data; delete del; return true;}

template void List::output(){ //输出

LinkNode *current = first->link;

while (current){

cout << current->data << endl;

current = current->link;}}

template List &List::operator = (List &L){ //重载函数T value;

LinkNode *destptr=first,*srcptr = L.first;

makeEmpty();

while (srcptr->link){

value = srcptr->link->data;

destptr->link = new LinkNode(value);

destptr = destptr->link;

srcptr = srcptr->link;}

destptr->link = NULL; return *this;}

template void List::input(T endTag, InsMod im){ //输入if (im == INF) inputFront(endTag);

else inputRear(endTag);}

template void List::inputFront(T endTag){ //前插法链表建立函数LinkNode *newNode; T val;

cin >> val;

while ( val != endTag){

newNode = new LinkNode(val);

if (!newNode){

cerr << "Memory allocating error!" << endl;

exit(1);}

newNode->link = first->link;

first->link = newNode;

cin >> val;}}

template void List::inputRear(T endTag){ //后插法链表建立函数LinkNode *newNode, *last=first; T val;

while(last->link!=NULL) last=last->link;

cin >> val;

while (val != endTag){

newNode = new LinkNode(val);

if (!newNode){

cerr << "Memory allocating error!" << endl;

exit(1);}

last->link = newNode; last = newNode; cin >> val;

} last->link = NULL;}

template void List::Sort(){} //排序

template void List::Inverse(){ //反向输出链表

LinkNode *h, *p, *pr;

h = NULL; p = first->link;

while (p){

pr = h; h = p; p = h->link; h->link = pr;}

first->link = h;}

template int List::tig(){ i nt num;

cout<<"请输入你所要操作的模块编号：【1:打印链表2:插入3:删除4:查询】"<<"＝";

cin>>num;

return num;}

#endif

Main测试模块

#include

#include "LinkedList.h"

using namespace std;

int main(){

List list;

ifstream fin("list.txt");

assert(fin); fin >> list; int i, elem;

cout << "\n 打印链表，排序,插入，删除，查询操作模块测试\n";

cout << "------------------------------------------------\n";

int num=list.tig();

if(num==1){

cout << "当前链表:\n" << list << endl; main();}

if(num==0){

cout<<"1.反向输出链表模块:\n"; list.Inverse();

cout << "排序后的链表:\n" << list << endl;

cout << "========================================\n";

main();}

if(num==2){

cout << "2. 插入模块:\n";

cout << "请输入你所要插入的位置和元素: ";

cin >> i >> elem;

if (list.Insert(i, elem)){

cout << "\n插入成功!\n";

cout << "\n插入后的链表\n" << list << endl;}

else cout << "\n插入失败!\n";

cout << "----------------------------------------\n"; main();}

if(num==3){

cout << "3. 删除模块:\n";

cout << "请输入你所要删除的位置: "; cin >> i;

if (list.Remove(i, elem)){

cout << "\n元素" << elem << " 删除成功!\n";

cout << "\n删除后的链表\n" << list << endl;}

else cout << "\n删除失败!\n";

cout << "----------------------------------------\n"; main();}

if(num==4){

cout << "4. 查找模块:\n";

cout << "请输入你所要查询的元素: "; cin >> elem;

LinkNode *p = list.Search(elem);

if (p) cout << "\n你查询的元素: 【" << elem <<"】查询成功!\n";

else cout << "\n你所要查找的元素: 【"<

cout << "\n----------------------------------------\n"; main();} if(num<0 || num>4){

cout<<"\n输入错误，请重新输入你所要进行的操作!\n"; main(); } cout << "\n测试结束!" << endl; return 0;

}

测试结果截图