数据结构实验报告
顺序表实验
1.实验目标
a.熟练掌握线性表的顺序存储结构。
b.熟练掌握顺序表的有关算法设计。
c.根据具体问题的需要，设计出合理的表示数据的顺序结构，并设计相关算法。
2.实验内容和要求
a.顺序表结构和运算定义，算法的实现以库文件方式实现，不得在测试主程序中直接实现；
b.实验程序有较好可读性，各运算和变量的命名直观易懂，符合软件工程要求；
c.程序有适当的注释。
3.数据结构设计
顺序表
4.算法设计
1.i表示要在顺序表中查找的位置，x表示查找到后返回的值。
int search(seqlist A,int i,elementType &x)
{
if(i<1||i>A.Len)//查找的范围不在顺序表中
return 0;
else
{
x=A.data[i-1];//复制要查找的值
return 1;
}
}
2.i表示要在顺序表中插入的位置，x表示要插入的元素。
void insert(seqlist &A,int i,elementType x)
{
if(i<1||i>A.Len)//超出顺序表范围
cout<<"error"<<endl;
else
{
for(int j=A.Len;j>=i;j--)//找到第i-1个结点擦，并后移元素
A.data[j]=A.data[j-1];
A.data[i-1]=x;//插入元素数据
A.Len++;//改变顺序表长度
}
}
3.先利用循环找到顺序表中第i个结点，然后进行删除操作。
void del(seqlist *L,int i)
{
int j;
if(i<1||i>L->Len+1)//超顺序表范围
cout<<"超出表范围"<<endl;
else
{
for(j=i-1;j<L->Len;j++)
L->data[j]=L->data[j+1];//删除第i个结点
L->Len--;
cout<<"删除元素后的表为：";
for(int k=0;k<L->Len;k++)//输出顺序表
cout<<L->data[k]<<" ";
cout<<endl;
}
}
4.因为顺序表是递增有序的，所以利用循环从顺序表的表尾进行比较，比X值大的元素则后移，一直到遇到小于等于X的元素，进行插入操作。
int insertlist(seqlist *L,elementType x)
{
if (L->Len==MAXLEN)
return 0;
else
{
int i=L->Len-1;
L->Len++;
while(x<=L->data[i])
{
L->data[i+1]=L->data[i];//查找待插入的位置
i--;
}
L->data[i+1]=x;//插入元素
return 1;
}
}
5．申请两个新的顺序表，然后对原表进行遍历，由 A.data[i]%2进行及奇偶的分离，并分别存入顺序表B,C中。
void separatelist(seqlist A,seqlist *B,seqlist *C)
{
int b(0),c(0);
for(int i=0;i<A.Len;i++)
{
if(A.data[i]%2)//奇数
{
B->data[b]=A.data[i];
b++;
B->Len++;
}
else//偶数
{
C->data[c]=A.data[i];
c++;
C->Len++;
}
}
}
5.因为顺序表L1和L2是递增有序的，所以对表L1设置个i指示，对表L2设
置个j指示，然后利用循环，如果L1.data[i]==L2.data[j],则复制元素，如果L1.data[i]>L2.data[j],则j++,如果 L1.data[i]<L2.data[j]，则i++;
直到其中一表遍历完；
void Newlist(seqlist A,seqlist B,seqlist *L)
{
int i(0),j(0),k(0);
while(i<A.Len&&j<B.Len)
{
if(A.data[i]==B.data[j])
{
L->data[k]=A.data[i];
i++;
j++;
k++;
L->Len++;
}
else if(A.data[i]>B.data[j])
j++;
else
i++;
}
}
6.因为顺序表是递增有序的，所以从顺序表的表尾进行操作，使用双重循环，
如果遇到两元素相等，则进行删除操作，并移动元素，统计移动次数。
void del(seqlist *A,int &n)
{
for(int i=A->Len-1; i>0;i--)
for(int j=i-1;j>=0;j--)
{
if(A->data[i]==A->data[j])
{
for(int k=i;k<A->Len;k++)
{
A->data[k]=A->data[k+1];//删除相同元素
n++;//统计次数
}
A->Len--;
}
}
}
7.运行和测试
1.
2.
3.
4.
5.
6.
7.
8.总结和心得
对于顺序表的基本操作，如查找，插入，删除等，大都是用循环操作来实现的，当然，在进行这些操作时，要时刻注意表中元素的移动及表中元素个数的操作；同时在进行对顺序表的操作时，可以采取指针和地址引用两种方法。
在进行算法的编写时，要注意时间复杂度，尽量少用多重循环。