数据结构实验报告(实验一)

1、；深 圳 大 学 实 验 报 告 课程名称： 数据结构实验与课程设计 实验项目名称： 实验一：顺序表的应用 学院： 计算机与软件学院 专业： 指导教师： 蔡平 报告人： 文成 学号： 2011150259 班级： 5 实验时间： 2012-9-17 实验报告提交时间： 2012-9-24 教务部制一、实验目的与要求：目的：1.掌握线性表的基本原理2.掌握线性表地基本结构3.掌握线性表地创建、插入、删除、查找的实现方法要求：1.熟悉C+语言编程2.熟练使用C+语言实现线性表地创建、插入、删除、查找的实现方法二、实验内容：Problem A: 数据结构实验1顺序表例程Description实现顺序

2、表的创建、插入、删除、查找Input第一行输入顺序表的实际长度n第二行输入n个数据第三行输入要插入的新数据和插入位置第四行输入要删除的位置第五行输入要查找的位置Output第一行输出创建后，顺序表内的所有数据，数据之间用空格隔开第二行输出执行插入操作后，顺序表内的所有数据，数据之间用空格隔开第三行输出执行删除操作后，顺序表内的所有数据，数据之间用空格隔开第四行输出指定位置的数据Sample Input611 22 33 44 55 66888 352Sample Output11 22 33 44 55 66 11 22 888 33 44 55 66 11 22 888 33 55 66 2

3、2HINT第i个位置是指从首个元素开始数起的第i个位置，对应数组内下标为i-1的位置Problem B: 数据结构实验1顺序表的数据交换Description实现顺序表内的元素交换操作Input第一行输入n表示顺序表包含的·n个数据第二行输入n个数据，数据是小于100的正整数第三行输入两个参数，表示要交换的两个位置第四行输入两个参数，表示要交换的两个位置Output第一行输出创建后，顺序表内的所有数据，数据之间用空格隔开第二行输出执行第一次交换操作后，顺序表内的所有数据，数据之间用空格隔开第三行输出执行第二次交换操作后，顺序表内的所有数据，数据之间用空格隔开注意加入交换位置的合法性检

4、查，如果发现位置不合法，输出error。Sample Input511 22 33 44 552 40 1Sample Output11 22 33 44 55 11 44 33 22 55 errorHINT本题执行两次交换操作，注意写好输入接口。Problem C: 数据结构实验1顺序表的合并Description假定两个顺序表的数据已经按照从小到大的顺序排列，实现两个顺序表的合并Input第一行输入n表示顺序表A包含的·n个数据第二行输入n个数据，数据是小于100的正整数第三行输入m表示顺序表B包含的·n个数据第二行输入m个数据，数据是小于100的正整数Output输

5、出合并后的顺序表内的所有数据，数据之间用空格隔开Sample Input311 33 55422 44 66 88Sample Output11 22 33 44 55 66 88 问题 D: 数据结构实验1顺序表的循环移位题目描述顺序表的移位是循环移位，例如顺序表：1，2，3，4，5，6。如果左移1位，即原来的头元素移动到末尾，其它元素向左移1位，变成2，3，4，5，6，1。同理，如果右移1位，即原来的尾元素移动到头，其它元素向右移1位，变成6，1，2，3，4，5。以下是移位的多个例子：原数据：1，2，3，4，5，6左移3位：4，5，6，1，2，3，与原数据对比右移4位：3，4，5，6，1，

6、2，与原数据对比请编写程序实现顺序表的循环移位操作输入第一行输入n表示顺序表包含的·n个数据第二行输入n个数据，数据是小于100的正整数第三行输入移动方向和移动的位数，左移方向为0，右移方向为1第三行输入移动方向和移动的位数，左移方向为0，右移方向为1输出第一行输出创建后，顺序表内的所有数据，数据之间用空格隔开第二行输出执行移位操作后，顺序表内的所有数据，数据之间用空格隔开第三行输出执行移位操作后，顺序表内的所有数据，数据之间用空格隔开如果发现输入的移动方向或位数不合法，不执行移位操作，输出error样例输入511 22 33 44 550 21 4样例输出11 22 33 44 5

7、5 33 44 55 11 22 44 55 11 22 33 3、 实验步骤与过程：思路：1. 顺序表类定义2.顺序表的创建、插入、删除、查找等功能的实现3.顺序表的测试运行源代码：A：#include<iostream>using namespace std;class Listprivate:int *elem;/数组元素int listsize;/顺序表最大长度int length;/顺序表当前长度public:List(int size);/构造函数List();/析构函数int ListLength();/获取顺序表的实际长度int ListInsert(int i,i

8、nt e);/插入一个元素int ListDelete(int i);/删除一个元素，返回删除的元素int GetElem(int i);/获取一个元素，返回元素值;List:List(int size)/构造函数listsize=size;length=0;elem=new intlistsize;List:List()/析构函数deleteelem;/回收空间int List:ListLength()/获取顺序表的实际长度return length;int List:ListInsert(int i,int e)/插入一个元素if (length=listsize)return 0;/顺序

9、表已满if (i<1 | i>length+1)return 0;/i值不合法if (i=length+1)elemlength=e;elsefor (int j=length;j>i-1;j-)elemj=elemj-1;/位置i后面的元素全部后移一位elemi-1=e;length+;return 1;int List:ListDelete(int i)/删除一个元素，返回删除的元素if (length=0)return 0;if (i<1 | i>length)return 0;int temp=elemi-1;for (int j=i-1;j<len

10、gth;j+)/位置i后面的元素全部前移一位elemj=elemj+1;length-;return temp;int List:GetElem(int i)/获取一个元素，返回元素值if(i<1 | i>length)return 0;return elemi-1;int main()int i,len,temp;List myList(20);/创建一个顺序表，最大长度为20cin>>len;for(i=1;i<len+1;i+)cin>>temp;myList.ListInsert(i,temp);for(i=1;i<myList.List

11、Length()+1;i+)/打印顺序表cout<<myList.GetElem(i)<<" "cout<<endl;int elem,j;cin>>elem>>j;/输入插入数以及插入的位置myList.ListInsert(j,elem);/执行插入操作for(i=1;i<myList.ListLength()+1;i+)/打印插入后的结果cout<<myList.GetElem(i)<<" "cout<<endl;cin>>j;/输入删

12、除的位置myList.ListDelete(j);/执行删除操作for(i=1;i<myList.ListLength()+1;i+)/打印插入后的结果cout<<myList.GetElem(i)<<" "cout<<endl;cin>>j;cout<<myList.GetElem(j)<<endl;/输出指定位置的数据return 0;B：#include<iostream>using namespace std;class Listprivate:int *elem;/数组元素i

13、nt listsize;/顺序表最大长度int length;/顺序表当前长度public:List(int size);/构造函数List();/析构函数int ListLength();/获取顺序表的实际长度int ListInsert(int i,int e);/插入一个元素int ListDelete(int i);/删除一个元素，返回删除的元素int GetElem(int i);/获取一个元素，返回元素值int s a,int b);/交换二个元素;List:List(int size)/构造函数listsize=size;length=0;elem=new intlistsize

14、;List:List()/析构函数deleteelem;int List:ListLength()/获取顺序表的实际长度return length;int List:ListInsert(int i,int e)/插入一个元素if (length=listsize)return 0;/顺序表已满if (i<1 | i>length+1)return 0;/i值不合法if (i=length+1)elemlength=e;elsefor (int j=length;j>i-1;j-)/位置i后面的元素全部后移一位elemj=elemj-1;elemi-1=e;length+;r

15、eturn 1;int List:ListDelete(int i)/删除一个元素，返回删除的元素if (length=0)return 0;if (i<1 | i>length)return 0;int temp=elemi-1;for (int j=i-1;j<length;j+)/位置i后面的元素全部前移一位elemj=elemj+1;length-;return temp;int List:GetElem(int i)/获取一个元素，返回元素值if(i<1 | i>length)return 0;return elemi-1;int List:s a,in

16、t b)/交换二个元素if (a<1 | a>length | b<1 | b>length | a=b)cout<<"error"/输入不合法，则报错return 0;elseint temp=elema-1;/交换元素elema-1=elemb-1;elemb-1=temp;return 1;int main()int i,len,temp;List myList(100);/创建一个顺序表，最大长度为100cin>>len;for(i=1;i<len+1;i+)cin>>temp;myList.List

17、Insert(i,temp);for(i=1;i<myList.ListLength()+1;i+)/打印顺序表cout<<myList.GetElem(i)<<" "cout<<endl;int x,y;/输入交换元素的位置cin>>x>>y;if (myList.s)/交换这二个元素for(i=1;i<myList.ListLength()+1;i+)/打印交换元素后的顺序表cout<<myList.GetElem(i)<<" "cout<<e

18、ndl;cin>>x>>y;if (myList.s)/交换这二个元素for(i=1;i<myList.ListLength()+1;i+)/打印交换元素后的顺序表cout<<myList.GetElem(i)<<" "cout<<endl;return 0;C:#include<iostream>using namespace std;class Listprivate:int *elem;int listsize;/顺序表最大长度int length;/顺序表当前长度public:List(i

19、nt size);/构造函数List();/析构函数int ListLength();/获取顺序表的实际长度int ListInsert(int i,int e);/插入一个元素int ListDelete(int i);/删除一个元素，返回删除的元素int GetElem(int i);/获取一个元素，返回元素值friend int func(List &a,List &b);/实现两个顺序表的合并;List:List(int size)/构造函数listsize=size;length=0;elem=new intlistsize;List:List()/析构函数delet

20、eelem;/回收空间int List:ListLength()/获取顺序表的实际长度return length;int List:ListInsert(int i,int e)/插入一个元素if (length=listsize)return 0;/顺序表已满if (i<1 | i>length+1)return 0;/i值不合法if (i=length+1)elemlength=e;elsefor (int j=length;j>i-1;j-)elemj=elemj-1;/位置i后面的元素全部后移一位elemi-1=e;length+;return 1;int List:

21、ListDelete(int i)/删除一个元素，返回删除的元素if (length=0)return 0;if (i<1 | i>length)return 0;int temp=elemi-1;for (int j=i-1;j<length;j+)elemj=elemj+1;/位置i后面的元素全部前移一位length-;return temp;int List:GetElem(int i)/获取一个元素，返回元素值if(i<1 | i>length)return 0;return elemi-1;int func(List &A,List &B

22、)/实现两个顺序表的合并int a; for (int i=0;i<B.ListLength();i+) a=-1;for(int j=0;j<A.ListLength();j+)if (B.elemi<A.elemj)/寻找插入的位置a=j;break;if(a=-1)A.elemA.length=B.elemi;/B.elemi是最大的，插到末尾A.length+;/顺序表当前长度+1elsefor(int k=A.length-1;k>=a;k-)/位置i后面的元素全部前移一位 A.elemk+1=A.elemk; A.elema=B.elemi;/将B.elem

23、i插到位置i处 A.length+;/顺序表当前长度+1 return 0;int main()int i,len,temp;List myList1(100);/创建一个顺序表1，最大长度为100List myList2(100);/创建一个顺序表2，最大长度为100cin>>len;/输入顺序表1长度for(i=1;i<len+1;i+)/输入数据cin>>temp;myList1.ListInsert(i,temp);cin>>len;/输入顺序表2长度for(i=1;i<len+1;i+)/输入数据cin>>temp;myLi

24、st2.ListInsert(i,temp);func(myList1,myList2);/将顺序表1与顺序表2合并for(i=1;i<myList1.ListLength()+1;i+)/输出合并后的结果cout<<myList1.GetElem(i)<<" "cout<<endl;return 0;D:#include<iostream>using namespace std;class Listprivate:int *elem;int listsize;/顺序表最大长度int length;/顺序表当前长度pub

25、lic:List(int size);/构造函数List();/析构函数int ListLength();/获取顺序表的实际长度int ListInsert(int i,int e);/插入一个元素int ListDelete(int i);/删除一个元素，返回删除的元素int GetElem(int i);/查找一个元素，返回元素值int Move(int a,int b);List:List(int size)/构造函数listsize=size;length=0;elem=new intlistsize;List:List()/析构函数deleteelem;/回收空间int List:L

26、istLength()/获取顺序表的实际长度return length;int List:ListInsert(int i,int e)/插入一个元素if (length=listsize)return 0;/顺序表已满if (i<1 | i>length+1)return 0;/i值不合法if (i=length+1)elemlength=e;elsefor (int j=length;j>i-1;j-)elemj=elemj-1;/位置i后面的元素全部后移一位elemi-1=e;length+;return 1;int List:ListDelete(int i)/删除一

27、个元素，返回删除的元素if (length=0)return 0;if (i<1 | i>length)return 0;int temp=elemi-1;for (int j=i-1;j<length;j+)elemj=elemj+1;/位置i后面的元素全部前移一位length-;return temp;int List:GetElem(int i)/查找一个元素，返回元素值if(i<1 | i>length)return 0;return elemi-1;int List:Move(int a,int b)int i,j;int *p=new int2*length;/先构造一个2倍长度的空间for (i=0;i<length;i+)pi=elemi;for (j=0;j<length;j+,i+)pi=elemj;/实际上p指向的是elem*2的数组if (a=0)/若a=0，则向左移for(i=0;i<length;i+)elemi=pi+b;/将向左移b位后的结果给elemif (a=1)/若a=1，则向右移for(i=0;i<length;i+)elemi=pi+length-b;/将向右移b位后的结果给elemreturn 0;int main()int i,len,t