線形テーブル構造1-シーケンステーブルの初期化、挿入、削除、検索.typedef解釈,チェーンテーブル知識点まとめ

目次
一、順序表の定義と特徴
1.順序表定義
2.順序表の特徴
二、順序表定義
三、順序表挿入演算
四、順序表削除演算
五、順序表要素の検索
六、順序表は要素データを取る
七、主関数定義
注1.typedef解釈
注2.チェーンテーブルの知識点のまとめ
一、順序表の定義と特徴
 
1.順序表定義
線形テーブルを配列で格納し、線形テーブルと呼ばれる順序格納構造または順序イメージを格納し、この方法で格納する線形テーブルを順序テーブルと呼ぶ.
2.順序表の特徴
1)論理的に隣接し、物理アドレスに対応して隣接する
2)任意の要素がランダムにアクセスできる
3)容量拡張が難しく、挿入、削除操作が複雑である
二、順序表定義

//     
typedef int ElemType;           //          
const int LIST_SIZE = 1024;     //        1024
typedef struct sequen
{
    ElemType data[LIST_SIZE];   //          
    int last;                   //              
}SeqList;                       //     ，             SeqList list;
SeqList* LPtr;                  //         

typedefの解釈については、以下の注釈1を参照することができる.
三、順序表挿入演算
一般的に、i番目(1<=i<=n)の要素の前に新しい要素を挿入する場合は、まず、i番目の要素間のn-i+1要素が順次後ろに移動するまで、最後の要素から開始します.移動終了後、i番目の位置が空になり、新しい要素が挿入され、挿入終了線形テーブルの長さが1増加します.

/*=================================================
    ：     ——     
    ：     ，   ，    
    ：    —— 0：    1：  
=================================================*/
int Insert_SqList(SeqList *Lptr, ElemType x, int k)
{
    if(Lptr->last >= LIST_SIZE - 1)             //        
        return false;
    else if(k < 0 || k > (Lptr->last + 1))      //        
        return false;
    else
    {
        for(int i = Lptr->last; i >= k; i--)
            Lptr->data[i + 1] = Lptr->data[i];
        Lptr->data[k] = x;                      //  X     k    
        Lptr->last = Lptr->last + 1;            //         last
    }
    return true;
}

四、順序表削除演算
シーケンステーブル上で削除演算を実現するにも、削除操作による空きを埋めるためにノードを移動する必要があり、削除後の要素間が物理アドレスによって隣接していることを保証します.1<=i<=n-1の場合、表中の位置i+1,i+2,...,nのノードは,位置i,i+1,...,n-1では、i+1からn番目のn-1要素を前に移動します.

/*=================================================
    ：     ——     
    ：     ，    
    ：    —— 0：    1：  
=================================================*/
int Delete_SqList(SeqList *Lptr, int k)
{
    if((k >= 0 && k <= Lptr->last) && (Lptr->last != 0))
    {
        for(int i = k; i <= Lptr->last; i++)
            Lptr->data[i] = Lptr->data[i + 1];
        Lptr->last--;
        return true;
    }
    return false;
}

五、順序表要素の検索
最初の要素から、要素のキーワード値と所定の値を1つずつ比較し、ある要素のキーワード値と所定の値が等しい場合、検索に成功します.そうでなければ、n番目のレコードが等しくないまで、条件を満たすデータ要素が存在しないことを示し、検索に失敗します.

/*=================================================
    ：     ——      
    ：     ，   
    ：    ——   ：       ：-1
=================================================*/
int Locate_SqList(SeqList *Lptr, ElemType key)
{
    for(int i = 0; i < Lptr->last; i++)
        if(Lptr->data[i] == key)
            return i;
    return false;
}

六、順序表は要素データを取る
シーケンステーブルは配列構造であり、ランダムアクセス構造に属するため、下付き文字は対応する配列要素値を直接得ることができることが知られており、与えられた下付き文字が境界を出ているかどうかを判断することに注意すればよい.

/*=================================================
    ：     ——         
    ：     ，    ，      
    ：    ——   ：-1    ：      
=================================================*/
int Get_SqList(SeqList *Lptr, int k, ElemType e)
{
    if(k < 0 || k > Lptr->last)
        return false;
    if(Lptr->last < 0)
        return false;
    e = Lptr->data[k];
    return e;
}

七、主関数定義

int main(int argc, const char * argv[])
{
    //      
    //SeqList list = {{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}, 10}; //        
    SeqList* list = (SeqList *)malloc(sizeof(SeqList));    //                   
    int j = 0;
    for(int i = 0; i < 10; i++)
    {
        list->data[i] = i;
        j++;
    }
    list->last = j;
    
    //     
    Insert_SqList(list, 11, 5);
    //Insert_SqList(&list, 11, 5);
    Delete_SqList(list, 6);
    ElemType e = 0;                                        //             
    e = Get_SqList(list, 5, e);
    //ElemType e = Get_SqList(list, 5, e);                 //       
    
    //       
    for(int i = 0; i < list->last; i++)                    //       
    {
        cout<< list->data[i] << "\t"<

注1.typedef解釈
typedefはC言語のキーワードであり、データ型の新しい名前を定義する役割を果たす.ここでのデータ型には、内部データ型(int,charなど)やカスタムデータ型(structなど)が含まれる.
プログラミングでtypedefを使用する目的は一般的に2つあり、1つは変数に覚えやすく意味の明確な新しい名前を与えることであり、もう1つは比較的複雑なタイプ宣言を簡略化することである.
typedefについて微妙な点については、以下のいくつかの問題の具体的な説明を見てください.
2.typedef&構造の問題
次のコードで構造を定義すると、コンパイラはエラーを報告します.なぜですか.C言語は構造に独自のポインタを含めることが許されないのではないでしょうか.まず推測して、次の説明を見てください.

typedef　struct　tagNode
{
char*　pItem;
pNode*　pNext;
}pNode;

分析:
1、typedefの最も簡単な使用

typedef　long　byte_4;

既知のデータ型longにbyte_という新しい名前を付けます.4.
2、typedefと構造を組み合わせて使用する

typedef　struct　tagMyStruct
{
int　iNum;
long　lLength;
}MyStruct;

この文は実際に2つの操作を完了します.
1)新しい構造タイプを定義する

struct　tagMyStruct
{
int　iNum;
long　lLength;
};

分析:tag MyStructは「tag」、すなわち「ラベル」と呼ばれ、実際には一時的な名前であり、structキーワードはtag MyStructとともに、typedefがあるかどうかにかかわらず、この構造タイプを構成している.
struct tagMyStruct varNameで変数を定義できますが、structとtagMyStructを合わせて構造タイプを表すことができるため、tagMyStruct varNameを使用して変数を定義するのは間違っています.
2)typedefはこの新しい構造にMyStructという名前をつけた.
typedef struct tagMyStruct MyStruct;
したがって、MyStructは実際にstruct tagMyStructに相当し、MyStruct varNameを使用して変数を定義することができます.
答えと分析
C言語はもちろん構造に独自のポインタを含めることができ,チェーンテーブルなどのデータ構造を構築する実装において無数のこのような例を見ることができ,上述のコードの根本的な問題はtypedefの応用にある.
私たちの上の説明によると、新しい構造が構築される過程でpNextドメインの声明に出会った.タイプはpNodeであり、pNodeがタイプの新しい名前を表していることを知るには、タイプ自体がまだ構築されていないとき、このタイプの新しい名前もまだ存在しない.つまり、このときコンパイラはpNodeを全く知らない.
この問題を解決する方法はいくつかあります.

//   
typedef　struct　tagNode
{
char*　pItem;
struct　tagNode*　pNext;
}*pNode;

//   
typedef　struct　tagNode*　pNode;
struct　tagNode
{
char*　pItem;
pNode　pNext;                      //    pNode* ，pNode      struct tagNode*
};

//   ，    
struct　tagNode
{
char*　pItem;
struct　tagNode*　pNext;
};
typedef　struct　tagNode*　pNode;

注2.チェーンテーブルの知識点のまとめ
https://blog.csdn.net/qq_41291253/article/details/89218736