C/C++リニアテーブル---シーケンステーブルアルゴリズム全解析
9913 ワード
レッスンノートのソース:
MOOCネットワーク
カクビンデータ構造
前に一度データ構造を学んだことがありますが、面接の時は本当に忘れてしまいました.前に中国に行って簡単なチェーンテーブル削除アルゴリズムを書いても書いていません.CSをしたいなら、データ構造をマスターしなければなりません.もう一度来てください.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
順序テーブル定義
シーケンステーブルとは、線形テーブルのすべての要素を論理的に順次、コンピュータメモリに指定された記憶位置から始まる連続記憶空間に格納することである.
シーケンステーブルの格納タイプ:リニアテーブルのヘッダアドレス、リニアテーブルの合計長さ、リニアテーブルの有効長さ.
利点:任意の要素がランダムにアクセスできる
欠点:挿入と削除操作時に大量の要素を移動する必要がある
シーケンステーブルのキーンアルゴリズム
イニシャルシーケンステーブル
空のシーケンステーブルを構築し、線形テーブルにlen個の長さを割り当て、有効長cntは0個である.
注意:malloc配分の場合は、成功するか否かの判断を行います.
順序テーブルが空かどうかを判断します.線形テーブルの有効長が0の場合、線形テーブルは空です.
リニア・テーブルがフルかどうかを判断
リニアテーブルの有効長さがlenの場合、リニアテーブルはフルです.
線形テーブルのループ線形テーブルが空の場合、出力する必要はありません.そうしないと、forループループで出力されます.
リニアテーブル追加要素リニアテーブルがいっぱいになったら追加できません.そうでない場合は、要素を追加し、有効な要素に1を追加します.
注意:要素を追加した後、有効なビットに1を追加します.
指定した位置要素を削除
空かどうかを判断するには、論理位置が1以上で、cnt以下でなければなりません.指定された位置posからcntまで、順番に1つ前に移動します.
注意:論理位置を入力し、eleの下付き位置と区別する必要があります.例を挙げてよく区別できます.
場所を指定して要素を追加
満タンであるか否かを判断し、位置は1とcnt+1でなければならない
全体のCコード:
C++コード:
テンプレートクラスを使用して、汎関数を実現し、コードの重複性を強化します.
MOOCネットワーク
カクビンデータ構造
前に一度データ構造を学んだことがありますが、面接の時は本当に忘れてしまいました.前に中国に行って簡単なチェーンテーブル削除アルゴリズムを書いても書いていません.CSをしたいなら、データ構造をマスターしなければなりません.もう一度来てください.
--------------------------------------------------------------------------------------------------------------------------------------------------------------------
順序テーブル定義
シーケンステーブルとは、線形テーブルのすべての要素を論理的に順次、コンピュータメモリに指定された記憶位置から始まる連続記憶空間に格納することである.
シーケンステーブルの格納タイプ:リニアテーブルのヘッダアドレス、リニアテーブルの合計長さ、リニアテーブルの有効長さ.
利点:任意の要素がランダムにアクセスできる
欠点:挿入と削除操作時に大量の要素を移動する必要がある
typedef struct Arr
{
int *pBase; //
int len; //
int cnt; //
}SqList;シーケンステーブルのキーンアルゴリズム
イニシャルシーケンステーブル
空のシーケンステーブルを構築し、線形テーブルにlen個の長さを割り当て、有効長cntは0個である.
注意:malloc配分の場合は、成功するか否かの判断を行います.
void InitArr(SqList *pArr,int len)
{
pArr->pBase = (int*)malloc(sizeof(int)*len);
if(NULL == pArr)
{
printf("
");
exit(-1);
}
pArr->cnt = 0;
pArr->len = len;
}順序テーブルが空かどうかを判断します.線形テーブルの有効長が0の場合、線形テーブルは空です.
int is_empty(SqList *pArr)
{
if( 0 == pArr->cnt)
return true;
else
return false;
}リニア・テーブルがフルかどうかを判断
リニアテーブルの有効長さがlenの場合、リニアテーブルはフルです.
int is_full(SqList *pArr)
{
if(pArr->cnt == pArr->len)
return true;
else
return false;
}線形テーブルのループ線形テーブルが空の場合、出力する必要はありません.そうしないと、forループループで出力されます.
void showArr(SqList *pArr)
{
int i;
if( true ==is_empty(pArr))
{
printf("
");
}
else
{
for(i=0;icnt;i++)
printf("%d\t",pArr->pBase[i]);
puts("
");
}
} リニアテーブル追加要素リニアテーブルがいっぱいになったら追加できません.そうでない場合は、要素を追加し、有効な要素に1を追加します.
注意:要素を追加した後、有効なビットに1を追加します.
void appendArr(SqList *pArr,int ele)
{
if(is_full(pArr))
printf("
");
else
{
pArr->pBase[pArr->cnt] = ele;
pArr->cnt++;
}
}指定した位置要素を削除
空かどうかを判断するには、論理位置が1以上で、cnt以下でなければなりません.指定された位置posからcntまで、順番に1つ前に移動します.
注意:論理位置を入力し、eleの下付き位置と区別する必要があります.例を挙げてよく区別できます.
void deleteArr(SqList *pArr,int pos)
{
int i;
if(true == is_empty(pArr))
printf("
");
if(pos < 1 || pos > pArr->cnt)
printf("
");
else
{
for(i=pos;icnt;i++)
pArr->pBase[i-1] = pArr->pBase[i];
pArr->cnt--;
}
} 場所を指定して要素を追加
満タンであるか否かを判断し、位置は1とcnt+1でなければならない
void insertEle(SqList *pArr,int pos,int ele)
{
int i;
if(is_full(pArr))
printf("
");
if(pos<1 || pos > pArr->cnt+1)
printf("
");
else
{
for(i= pArr->cnt-1;i>=pos-1;i--)
pArr->pBase[i+1] = pArr->pBase[i];
pArr->pBase[pos-1] =ele;
pArr->cnt++;
}
}全体のCコード:
#include
#include
#include
#include
#define ListMax 10
#define true 1
#define false 0
typedef struct Arr
{
int *pBase; //
int len; //
int cnt; //
}SqList;
//
void InitArr(SqList *pArr,int len)
{
pArr->pBase = (int*)malloc(sizeof(int)*len);
if(NULL == pArr)
{
printf("
");
exit(-1);
}
pArr->cnt = 0;
pArr->len = len;
}
//
int is_empty(SqList *pArr)
{
if( 0 == pArr->cnt)
return true;
else
return false;
}
//
int is_full(SqList *pArr)
{
if(pArr->cnt == pArr->len)
return true;
else
return false;
}
//
void showArr(SqList *pArr)
{
int i;
if( true ==is_empty(pArr))
{
printf("
");
}
else
{
for(i=0;icnt;i++)
printf("%d\t",pArr->pBase[i]);
puts("
");
}
}
//
void appendArr(SqList *pArr,int ele)
{
if(is_full(pArr))
printf("
");
else
{
pArr->pBase[pArr->cnt] = ele;
pArr->cnt++;
}
}
//
void deleteArr(SqList *pArr,int pos)
{
int i;
if(true == is_empty(pArr))
printf("
");
if(pos < 1 || pos > pArr->cnt)
printf("
");
else
{
for(i=pos;icnt;i++)
pArr->pBase[i-1] = pArr->pBase[i];
pArr->cnt--;
}
}
// pos ele
// pos 1 pArr->len
void insertEle(SqList *pArr,int pos,int ele)
{
int i;
if(is_full(pArr))
printf("
");
if(pos<1 || pos > pArr->cnt+1)
printf("
");
else
{
for(i= pArr->cnt-1;i>=pos-1;i--)
pArr->pBase[i+1] = pArr->pBase[i];
pArr->pBase[pos-1] =ele;
pArr->cnt++;
}
}
//
int getArr(SqList *pArr,int pos)
{
if(true == is_empty(pArr))
printf("
");
if(pos < 1 || pos > pArr->cnt)
printf("
");
return pArr->pBase[pos-1];
}
// ele
int locateEle(SqList *pArr, int ele)
{
int i=0;
while(icnt && pArr->pBase[i]!= ele) i++;
if(i >=pArr->cnt) return 0;
else return i+1;
}
//
void inversionArr(SqList *pArr)
{
int i=0;
int j=pArr->cnt-1;
int temp;
while(ipBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = temp;
i++;
j--;
}
}
//
void sortArr(SqList *pArr,int m)
{
switch(m)
{
case 1: //
{
int i,j,temp;
for(i=0;icnt-1;i++)
{
for(j=i+1;jcnt;j++)
{
if(pArr->pBase[i] > pArr->pBase[j])
{
temp = pArr->pBase[i];
pArr->pBase[i] = pArr->pBase[j];
pArr->pBase[j] = temp;
}
}
}
break;
}
case 2: //
{
int n = pArr->cnt;
while(n >1)
{
int i,temp,pos=0;
int max=pArr->pBase[0];
for(i=0;ipBase[i])
{
max = pArr->pBase[i];
pos = i;
}
}
temp = pArr->pBase[pos];
pArr->pBase[pos] = pArr->pBase[n-1];
pArr->pBase[n-1] = temp;
n--;
}
break;
}
case 3: //
{
int i;
for(i=1;icnt;i++)
{
int temp = pArr->pBase[i];
while(i>0 && pArr->pBase[i-1] > temp)
{
pArr->pBase[i] = pArr->pBase[i-1];
i--;
}
pArr->pBase[i] = temp;
}
}
}
}
void main()
{
int i;
SqList arr;
srand( (unsigned)time( NULL ) );
InitArr(&arr, ListMax);
for(i=0;i<7;i++)
appendArr(&arr,rand()%100+1);
showArr(&arr);
insertEle(&arr,8,11);
showArr(&arr);
deleteArr(&arr,6);
showArr(&arr);
printf("%d
",getArr(&arr,5));
printf("%d
",locateEle(&arr,4));
inversionArr(&arr);
sortArr(&arr,3);
showArr(&arr);
}
C++コード:
テンプレートクラスを使用して、汎関数を実現し、コードの重複性を強化します.
#include
#include
#include
#define MAXSIZE 20
using namespace std;
// ，
//
template
class SqList
{
public:
SqList(){cnt = 0;}//
SqList(T a[],int len);//
~SqList(){} //
bool isEmpty();//
bool isFull(); //
void showArr(); //
T getArr(int pos); // ele
void appendArr(T ele);//
void deleteArr(int pos);//
void insertEle(int pos,T ele); // ele
private:
T data[MAXSIZE]; //
int cnt; //
};
//
template
SqList::SqList(T a[],int len)
{
if(len>MAXSIZE)
cout<
void SqList::showArr()
{
for(int i=0;i
bool SqList::isEmpty()
{
if(cnt == 0)
return true;
else
return false;
}
template
bool SqList::isFull()
{
if(cnt == MAXSIZE)
return true;
else
return false;
}
template
void SqList::appendArr(T ele)
{
if(isFull())
cout<
void SqList::deleteArr(int pos)
{
if(isEmpty())
cout<cnt)
cout<
T SqList::getArr(int pos)
{
if(pos<1 || pos>cnt)
{
cout<
void SqList:: insertEle(int pos,T ele)
{
if(isEmpty())
cout<cnt)
cout<=pos; i--)
{
data[i] = data[i-1];
}
data[pos-1] = ele;
cnt++;
}
}
int main()
{
int a[10];
for(int i=0;i<10;i++)
a[i]=rand()%100+1;
SqList arr(a,10);
arr.showArr();
arr.appendArr(9);
arr.appendArr(39);
arr.showArr();
arr.deleteArr(12);
arr.deleteArr(1);
arr.showArr();
cout<