顺序表的应用.doc

五邑大学实验报告实验课程名称数据结构院系名称： 计算机学院专业名称： 电子信息工程实验项目名称： 堆栈及其操作班级： 学号：报告人： 实验地点: 一 实验目的1、掌握顺序表的概念，理解顺序表的顺序、链式存储。 2、掌握顺序表的基本操作，插入、删除、查找，以及顺序表合并等运算在顺序存储结构和链接存储结构上的运算。二 实验内容几个重要函数及其实现功能： void Insert(int i, int x); /在线性表中第i个位置插入值为x的元素 int Get(int i); /返回第i个元素的值 int Delete(int i); /删除线性表的第i个元素 int Locate(int x); /按值查找，求线性表中值为x的元素序号 void PrintList( ); /遍历线性表，按序号依次输出各元素 void InsertOrder(int x); /有序插入三 内容分析线性表的构造：class SeqListpublic: SeqList( )length=0; /无参构造函数，创建一个空表 SeqList(int a , int n); /有参构造函数 void Insert(int i, int x); /在线性表中第i个位置插入值为x的元素 int Get(int i); /返回第i个元素的值 int Delete(int i); /删除线性表的第i个元素 int Locate(int x); /按值查找，求线性表中值为x的元素序号 void PrintList( ); /遍历线性表，按序号依次输出各元素 void InsertOrder(int x); /有序插入 int *pd();/返回data的地址 int Length();/返回表长private: int dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;四 实验步骤要点1、 函数算法的实现：如： /合并A+B-C产生新的链表template void MergeList(LinkList A,LinkList B,LinkList &C)Node *p,*q,*s;p=A.FirstNode()-next;q=B.FirstNode()-next;while(p & q)if(p-datadata)C.InsertOrder(p-data);p=p-next;elseC.InsertOrder(q-data);q=q-next;while(p)C.InsertOrder(p-data);p=p-next;while(q)C.InsertOrder(q-data);q=q-next;2、 循环条件的控制五 实验结果分析六 体会与总结此次上机实验，不仅对此次编译程序的算法思想有了新的认识，还让我深刻的体会到了线性表的重要性以及其应用的方便，并且对指针加深了映象，应用了书本中的算法思想，对我以后的编译以及完成新的程序有很大的帮助。附录：程序代码#include /引用输入输出流库函数的头文件using namespace std;#include seqListlib.h /引用顺序表的类声明和定义/数组a0.n-1中 axay,循环左移y-x+1位 void Reverse(int a,int x,int y)int i,j=y;int temp;for(i=x;ij;i+,j-)temp=ai;ai=aj;aj=temp;/线性表的实现template void MergeList(LinkList A,LinkList B,LinkList &C)Node *p,*q,*s;p=A.FirstNode()-next;q=B.FirstNode()-next;while(p & q)if(p-datadata)C.InsertOrder(p-data);p=p-next;elseC.InsertOrder(q-data);q=q-next;while(p)C.InsertOrder(p-data);p=p-next;while(q)C.InsertOrder(q-data);q=q-next;void ReV(int a,int n,int m)Reverse(a,0,m-1);Reverse(a,m,n-1);Reverse(a,0,n-1);void Odd_Even(int a,int n)int i=0,j=n-1;int temp;for(;i=j;i+) while(ai%2=1)i+;while(aj%2=0)j-;if(ij)temp=ai;ai=aj;aj=temp;void main( ) /* int r5=1, 2, 3, 4, 5; SeqList L(r, 5); cout执行插入操作前数据为：endl; L.PrintList( ); /输出所有元素 try L.Insert(2,3); catch (char *s) coutsendl; cout执行插入操作后数据为：endl; L.PrintList( ); /输出所有元素 cout值为3的元素位置为:; coutL.Locate(3)endl; /查找元素3，并返回在单链表中位置 /* cout执行删除第一个元素操作，删除前数据为：endl; L.PrintList( ); /输出所有元素 try L.Delete(1); /删除第1个元素 catch (char *s) coutsendl; cout删除后数据为：endl; L.PrintList( ); /输出所有元素*/int r11=23,46,6,7,45,67,45,55,66,5,44;SeqList L;L.PrintList();for(int i=0;i11;i+)try L.InsertOrder(ri);catch (char *s)coutsendl;L.PrintList();ReV(L.pd(),L.Length(),2);L.PrintList();Odd_Even(L.pd(),L.Length();L.PrintList();/#ifndef SeqList_H#define SeqList_Hconst int MaxSize=20; /10只是示例性的数据，可以根据实际问题具体定义class SeqListpublic: SeqList( )length=0; /无参构造函数，创建一个空表 SeqList(int a , int n); /有参构造函数 void Insert(int i, int x); /在线性表中第i个位置插入值为x的元素 int Get(int i); /返回第i个元素的值 int Delete(int i); /删除线性表的第i个元素 int Locate(int x); /按值查找，求线性表中值为x的元素序号 void PrintList( ); /遍历线性表，按序号依次输出各元素 void InsertOrder(int x); /有序插入 int *pd();/返回data的地址 int Length();/返回表长private: int dataMaxSize; /存放数据元素的数组 int length; /线性表的长度;#endif/#ifndef SeqList_HL#define SeqList_HL#include /引用输入输出流库函数的头文件using namespace std;#include SeqList.hSeqList:SeqList(int a , int n) if (nMaxSize) throw 参数非法; for (int i=0; i=MaxSize) throw 上溢; if (ilength+1) throw 位置非法; for (int j=length; j=i; j-) dataj=dataj-1; /注意第j个元素存在数组下标为j-1处 datai-1=x; length+;int SeqList:Delete(int i) if (length=0) throw 下溢; if (ilength) throw 位置非法; int x=datai-1; for (int j=i; jlength; j+) dataj-1=dataj; /注意此处j已经是元素所在的数组下标 length-; return x;int SeqList:Locate(int x) for (int i=0; ilength; i+) if (datai=x) return i+1 ; /下标为i的元素等于x，返回其序号i+1 return 0; /退出循环，说明查找失败void SeqList:PrintList( ) for (int i=0; ilength; i+)coutdatai ; cout0)while(dataix & i=i;j-)data