データ構造の順序表の基本演算
1705 ワード
//
void InitList(SeqList *L){
L.length=0;// 0
}
//
int getListLength(SeqList *L){
return L.length;
}
// i
DataType GetNode(L,i){
if(i<1 || i>L.length)// i>L.length-1 。 L 3.length-1 2. ?
{
System.out.println("position error");
}
return L.data[i-1];
}
// x
DataTyoe GetNode(L,v){
for(int i=0;i<L.length;++i){
if(GetNode(L,i).value==v){
return GetNode(L,i);
}
}
}
5.挿入(1)演算の論理記述を挿入する
線形表の挿入とは、表のi番目(0=ListSizeの場合は、空間がいっぱいで挿入できないことを示します.
(2)手順表の挿入過程
i=nの場合は、直接端に挿入します.
そうでなければ、i及び後のすべてのノードを全部後に一桁移動し、位置をiにする.
(3)ダミーコードの説明
//
void InsertNode(SeqList *L,DataType x,int i){
int j;
if(i<0 || i>L.length-1){
System.out.println(" ");
return false;
}
if(L.length>=ListSize){
System.out.println(" ");
return false;
}
for(j=L.length-1;j>=i;--j){
L.data[j+1]=L.data[j];//
}
L.data[i] = x;
++L.lenth;
}
アルゴリズム解析:1、問題の規模
表の長さL.length(nに設定)は問題の規模です.
2、移動結点の回数は表長n(未挿入前)と挿入位置iで決定されます.
アルゴリズムの時間は主にforサイクル中の結点を使って文を移動します.この文の実行回数はn-iです.
i=n;移動結点数は0です.最後に挿入します.すなわち、最も良いアルゴリズムの時間複雑さはO(1)である.
i=1;移動結点数はnです.つまり、アルゴリズムは最悪の場合、時間複雑度はO(n)である.
3、移動結点の平均回数E(n):
E(n)=ΣPi(n-i)
ここで、表にiと表示されている位置に結点を挿入します.結点移動の回数はn-iです.
Piは、iとラベリングされた位置に結点を挿入する確率を表します.各位置に挿入する位置が平等であると仮定します.
P 0=p 1...=1/(n+1)
E(n)=Σ(n-i)/(n+1)=n/2
つまり、順序表に挿入演算を行い、平均的に半分の結点を移動します.