本文最后更新于 2020年4月7日 下午
顺序表就是将元素放入一个连续的内存空间里，它的优点是可以快速访问，缺点是插入和删除操作时间复杂度高
建立
1
2
3
4
5
6
7
8
| #include<iostream>
#define datasize 100
using namespace std;
struct node
{
int* p;
int length;
};
|
初始化
1
2
3
4
5
6
7
8
9
10
| void init(node& a)
{
a.p=new int[datasize];
if(a.p==NULL)
{
cout<<"储存分配失败"<<endl;
delete [] a.p;
}
a.length=0;
}
|
初始化有两点要注意的地方，第一点是用了传引用，第二点是动态分配内存，这就表示如果使用完了要delete
查找
1
2
3
4
5
6
7
8
9
10
11
| int find(node& a,int x)
{
for(int i=0;i<a.length;i++)
{
if(a.p[i]==x)
{
return i;
}
}
return -1;
}
|
插入
插入操作是把一个数插入第i位，其他位顺序后移
如果插入某一位概率相同，那么在第0位插入需要移动n个数，第一位插入需要移动n-1个数……在第n位插入需要移动0个数，总共有n-1中可能，总共需要移动的次数为n(n+1)/2,所以平均需要移动次数为n/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| int insert(node& a,int x,int i)
{
if(i<0||i>a.length||a.length==datasize)
{
return 0;
}
for(int j=a.length;j>i;j--)
{
a[j]=a[j-1];
}
a[i]=x;
a.length++;
return 1;
}
|
删除
与上面操作类似，这里需要前移，并且平均操作次数为(n-1)/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| int Delete(node& a,int i)
{
if(i<0)
{
return 0;
}
else
{
for(int k=i;k<a.length-1;k++)
{
a.p[k]=a.p[k+1];
}
a.length--;
return 1;
}
}
|