配列によるリニア・テーブルの実装

線形構造については、C言語に内蔵された配列を用いてシーケンステーブルとなる2つの保存方法がある.もう1つの使用ポインタは、このような構造がチェーンテーブルとなる.
    線形構造では、初期化、順序テーブルの削除、順序テーブルのクリア、空かどうかを判断する、遍歴、テーブルの長さを求める、テーブル内の要素の位置を求める、特定のシーケンス番号を返す要素を求める、要素の前の要素を求める、要素の後の要素を求める、要素を挿入する、要素を削除する12の基本的な操作があります.
    ほとんどのプログラムは簡単ですが、唯一説明しなければならないのは、要素を挿入するときに線形テーブルがいっぱいになったら、メモリ領域を再割り当てする必要があります.新しく割り当てられたメモリ領域は元の2倍に設定されています.この倍数も私が勝手に与えたものではありません.C++のSTLのvectorを参考にして与えました.それらの専門家を信じて、きっと倍数が小さすぎて何度もメモリとメモリの割り当てが大きすぎる折衷を考慮して、私も猫の虎のようにしました.
     配列を用いて線形構造を表す最大の利点は,配列が連続的に格納されているため,ランダムアクセス速度が非常に速く,配列のヘッダアドレス+下付き*sizeof(構造体)だけで指定要素のアドレスを計算できることである.多くの要素を移動したり、メモリを再割り当てしたりする必要があるため、挿入、削除の効率が低いという欠点も明らかです.

//        
#include
#include

typedef int ElemType;

typedef struct arraylist
{
	ElemType *Array;//         
	int length;//            
	int size;//     
}arrayList;

//      ：       
bool initialArray(arrayList *arrLst,int len)
{
	arrLst->length=0;
	arrLst->size=len;
	arrLst->Array=(ElemType *)malloc(len*sizeof(ElemType));
	if(NULL==arrLst->Array)
		return false;
	else
		return true;
}

//     
void deleteArray(arrayList* arrLst)
{
	arrLst->length = 0;  
    arrLst->size = 0;  
    free(arrLst->Array);  
    arrLst->Array = NULL;  
}

//       
void clearArray(arrayList *arrLst)  
{  
    arrLst->length = 0;  
} 

//      
bool is_empty(arrayList *arrLst)
{
	if(0==arrLst->length)
	{
		printf("the arrayList is empty!
");  
		return true;
	}		
	else
	{
		printf("the arrayList is not empty!
");
		return false;
	}
		
}

//         
int arrayLength(arrayList *arrLst)  
{  
    return arrLst->length;  
}  
//      
bool getElem(arrayList* arrLst,int index,ElemType *e)
{
	if(index<0||index>arrayLength(arrLst)-1)
	{
		printf("    !
");
		return false;
	}
	else
	{
		*e=arrLst->Array[index];
		return true;
	}
}

//     ，    
void printfArray(arrayList *arrLst)
{
	printf("array elements are: ");  
	for(int i=0;ilength;i++)
	{
		printf("%d\t",arrayList->Array[i]);
	}
	printf("
");
}

//         
int locateElem(arrayList *arrLst,ElemType e)
{
	for(int i=0;iArray[i])
			return i;
	}
	return -1;
}

//        ：       -2；        。  -1；             
int preElement(arrayList *arrLst,ElemType e,ElemType *preElem)  
{
	for(int i=0;iArray[i])
		{
			if(i==0)
			{
				return -1;
			}
			else
			{
				preElem=arrLst->Array[i-1];
				return i-1;
			}
		}
	}
	return -2;	
}

  
//        ：     ，  -2,         ，  -1；             
int nextElement(arrayList *arrLst,ElemType e,ElemType *nxtElem)  
{  
    for(int i = 0; i < arrayLength(arrLst); ++i)  
    {  
        if(e == arrLst->Array[i])  
        {  
            if(arrayLength(arrLst) -1 == i)  
            {  
                return -1;  
            }  
            else  
            {  
                *nxtElem = arrLst->Array[i+1];  
                return i+1;  
            }  
        }  
    }  
    return -2;  
} 

//          
bool insertElem(arrayList *arrLst,int index,ElemType e)
{
	//             
	if(index<0||index>arrayLength(arrLst)-1)
	{
		return false;
	}
	 //           ，           
	 if(arrLst->length==arrLst->size)
	 {
		arrLst->Array=(ElemType*)reolloc(arrLst->Array,2*arrLst->size*sizeof(ElemType));
		if(NULL==arrLst->Array)
			return false;//      
		else
		{
			arrLst->size*=2;
		}
	 }
	for(int i = index; i < arrayLength(arrLst); ++i) 
	{
		arrLst->Array[i+1]=arrLst->Array[i];
	}
	arrLst->Array[index]=e;
	++arrLst->length;
	
	return true;
}

//      
bool deleteElem(arrayList *arrLst,int index ,ElemType *e) 
{
	//             
	if(index<0||index>arrayLength(arrLst)-1)
	{
		return false;
	}
	*e=array->Array[index];
	for(int i = index; i < arrayLength(arrLst); ++i) 
	{
		arrLst->Array[i]=arrLst->Array[i+1];
	}
	
	--arrLst->length;
	
	return true;
}

原文住所:http://blog.csdn.net/thefutureisour/article/details/7830062