C言語によるリニア・テーブルの実装を学ぶ

リニア・テーブルは、最も一般的で最も簡単なデータ構造です.1つの線形テーブルはn個のデータ要素の有限シーケンスであり、シーケンス内の各データ要素は、1つの数字であってもよいし、1つの文字であってもよいし、複雑な構造体であってもよいし、オブジェクトであってもよい.例えば:1,2,3,4,5は線形表で、A,B,C,D...Zはリニアメーターで、1列の列車の車両1、車両2...車両nはリニアメーターである.
 
リニアテーブルの機内表示法(記憶構造とも呼ばれる)は2種類あり,1つは順次記憶構造,もう1つはチェーン記憶構造である.
 
順次記憶構造は、その名の通り、線形テーブル(1,2,3,4,5)の計5要素を順次記憶する記憶構造である.
各int型のデータ要素は4個のメモリセルを占有すると仮定し、1番目の要素番号1のメモリアドレスが1000であると仮定すると、2番目の要素番号2のメモリアドレスは1004、3番目の要素番号3のメモリアドレスは1008である、このように、n番目のデータ要素のメモリアドレスはLOC(an)=LOC(a 1)+(n-1)kである(kは各データ要素が占有するメモリセルの長さを示す).
このような記憶構造は、隣接する要素が物理的位置においても隣接していることが明らかである.
通常,このようなストレージ構造を用いた線形テーブルを「シーケンステーブル」と呼ぶ.
 
チェーンストレージ構造は、隣接する要素が物理的に隣接することを必要としないため、任意の位置にあるストレージユニットのセットで線形テーブルのデータ要素を格納することができる.それなら、データ要素間の論理関係をどのように表現すればいいのでしょうか.
データ要素間の論理関係を表すためには、データ要素a 1にとって、自身の情報を格納するほか、その直接後継を示す情報を格納する必要があるため、データ要素情報を格納するドメインをデータドメインと呼び、直接後継アドレス情報を格納するドメインをポインタドメインと呼ぶポインタの概念を導入する.
我々は,このような自己データ情報と,その直接後続アドレス情報とを含むデータ要素を「ノード」とイメージする.
このような記憶構造は、隣接する要素が物理的に隣接しているとは限らず、論理関係をポインタで表すことが明らかになった.
通常、このようなストレージ構造を採用したリニアテーブルを「リニアチェーンテーブル」と呼ぶ.
 
基本的な概念があれば、プログラミング言語を使って説明することができます.C、C++、C#、Javaなどを使ってもいいです.この文章はC言語で説明します.
 
一、順序表
順序テーブルを記述するには、まず次のような構造を宣言します.
 

#define LIST_INIT_SIZE 100 //             
#define LISTINCREMENT 10   //            (           )
typedef int ElemType;      //       ，   int  
typedef struct{
    ElemType *elem;       //        
    int length;      //        
    int listsize;    //         
}SqList;

 
線形テーブルを定義すると、それを操作できます.一般的な線形テーブルの基本的な操作は、線形テーブルの作成、要素の検索、要素の挿入、要素の削除、クリア、集計などです.
リニア・テーブルの基本的な操作は、シーケンス・テーブルで実行されます.
1.線形テーブルの作成
 

int InitList(SqList &L)
{
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));//        ，               elem
    if (!L.elem)
    {
        return -1; //      
    }
    
    L.length = 0; //    
    L.listsize = LIST_INIT_SIZE; //     
    return 0;
}

 
2.エレメントの検索(値で検索)
線形テーブルの値別検索とは、線形テーブルで所与の値xに等しいデータ要素を検索することである.この操作を完了する最も簡単な方法は、最初の要素a 1から順にxと比較し、等しい場合、その要素の下付き文字を返すことである.
テーブル全体を調べてもxに等しい要素が見つからない場合は、-1を返します.
時間複雑度:アルゴリズムの基本操作(xとLのi<1,n>個目の要素を比較する)は、表中の要素xの位置に関係し、表長にも関係する.a 1=xの場合、比較は1回成功し、an=xの場合、比較はn回成功し、平均比較回数はn+1/2、時間複雑度はO(n)である.
 

int LocateElem(SqList L, ElemType x)
{
    int pos = -1;
    for (int i = 0; i < L.length; i++)
    {
        if (L.elem[i] == x)
        {
            pos = i;
        }
    }
    return pos;
}

 
3.要素の挿入
時間複雑度O(L.length)すなわちO(n)
 

int ListInsert(SqList &L, int i, ElemType e)
{
    //          
    if (i<1 || i>L.length+1) return -1; 
    //          
    if (L.length >= L.listsize)
    {
        ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType));
        if (!newbase) return -1;//        
        L.elem = newbase;//   
        L.listsize += LISTINCREMENT;//      
    }
    //    
    ElemType *q, *p; //  2     
    q = &(L.elem[i-1]); //q     (    i   ，     1   ，     0   ，          i-1)
    for (p = &(L.elem[L.length - 1]); p >= q; --p) // ai an-1    ，             
    {
        *(p + 1) = *p;
    }
    *q = e;
    ++L.length;//   1
    return 0;
}

 
4.要素の削除
時間複雑度O(L.length)すなわちO(n)
 

int ListDelete(SqList &L, int i, ElemType &e)
{
    //          
    if (i<1 || i>L.length) return -1; 
    //    
    ElemType *q, *p;//  2      
    p = &(L.elem[i - 1]);//p         (    i   ，     1   ，     0   ，          i-1)
    e = *p; //         e(     ，     ，     e )
    q = L.elem + L.length - 1;//q          (q          )
    for (++p; p <= q; ++p) // p            
    {
        *(p - 1) = *p;
    }
    
    --L.length;//   1
    return 0;
}

 
テストコードは次のとおりです.
 

#include <stdio.h>
#include <stdlib.h>
int main()
{
    SqList list;
    InitList(list);
 
    int n = 10;
    
    //  10       list
    for (int i = 0; i < 10; i++)
    {
        ListInsert(list, i+1, i+1);
    }
    //   5 
    ElemType e;
    ListDelete(list, 5, e);
    printf("      ：%d
", e);
 
    //  2         -1
    ListInsert(list, 2, -1);
    
    //     
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", list.elem[i]);
    }
    //     ：1 -1 2 3 4 6 7 8 9 10
 
    system("pause");
}

小僧は初めてデータ構造を学び、不足点があれば、大神の指摘を歓迎します.