順序表練習問題

これらの問題はいずれも不定長順順表に基づいて実現された.
テーマ1:シーケンステーブルplistのデータ要素のインクリメンタル秩序を設定する.アルゴリズムを書き込み、xをシーケンステーブルの適切な位置に挿入して、テーブルの秩序性を維持します.

bool InsertVal(DSeqList plist, int x)
{
     
	assert(plist != NULL);
	if (plist == NULL)
	{
     
		return false;
	}
	//     ：     x  ,      
	int i;//     
	for (i = 0; i < GetCount(plist); ++i)
	{
     
		if (plist->elem[i] > x)
		{
     
			break;
		}
	}
	return Insert(plist, x, i);;
}

題目2:二つの順序表の大きさを比較する

//   >0--—》A ，   <0--》B ，   ==0--》  
int Cmp(DSeqList plistA, DSeqList plistB)
{
     
	int tmp;
	for (int i = 0; i < GetCount(plistA) && i < GetCount(plistB); ++i)
	{
     
		tmp = plistA->elem[i] - plistB->elem[i];
		if (tmp != 0)
		{
     
			return tmp;
		}
	}

	return GetCount(plistA) - GetCount(plistB);
}

タイトル3:A、B、C、昇順に並べて、A表に対して以下の操作を行います:あれらがB表の中でまたC表の中で現れる要素を削除します

void Sub(DSeqList plistA, DSeqList plistB, DSeqList plistC)
{
     
	assert(plistA != NULL && plistB != NULL && plistC != NULL);
	int i = 0;//A   
	int j = 0;//B   
	int k = 0;//C   

	while (i < GetCount(plistA) && j < GetCount(plistB) && k < GetCount(plistC))
	{
     
		if (plistA->elem[i] == plistB->elem[j] && plistA->elem[i] == plistC->elem[k])
		{
     
			DeletePos(plistA, i);
		}
		else if (plistA->elem[i] < plistB->elem[j])
		{
     
			i++;
		}
		else if (plistA->elem[i] > plistB->elem[j])
		{
     
			j++;
		}
		else if (plistA->elem[i] < plistC->elem[k])
		{
     
			i++;
		}
		else
		{
     
			k++;
		}
	}

}

题目4:2つの顺番表は顺番を増加して、C=AUBを実行して、アルゴリズムの时间の复雑さの要求はO(n+m)(A、Bのこの2つの顺番表はただ1回だけ遍歴することを许します);

void Union(DSeqList plistA, DSeqList plistB, DSeqList plistC)
{
     
	int i = 0;//A   
	int j = 0;//B   
	int k = 0;//C   
	//A B     
	while (i < GetCount(plistA) && j < GetCount(plistB))
	{
     
		if (plistA->elem[i] < plistB->elem[j])
		{
     
			Insert(plistC, plistA->elem[i], k);
			i++;
			k++;
		}
		else if (plistA->elem[i] == plistB->elem[j])//        
		{
     
			Insert(plistC, plistA->elem[i], k);
			i++;
			j++;
			k++;
		}
		else
		{
     
			Insert(plistC, plistB->elem[j], k);
			j++;
			k++;
		}
	}
	//A     ，B     
	while (i < plistA->count)
	{
     
		Insert(plistC, plistA->elem[i], k);
		i++;
		k++;
	}
	//B     ，A     
	while (j < plistB->count)
	{
     
		Insert(plistC, plistB->elem[j], k);
		j++;
		k++;
	}
}