データ構造の順序表の基本演算

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
つまり、順序表に挿入演算を行い、平均的に半分の結点を移動します.