シーケンススタック/チェーンスタック

8070 ワード
C データ構造
スタックは、線形テーブルの挿入と削除をテーブルの一端のみに限定する限定的な線形テーブルです.テーブルの挿入と削除を許可する一端をスタックトップにします.したがって、スタックトップの位置は常に動的に変化します.「後進先出」という特徴があります.スタックはリニアテーブルによって実現されるため、スタックには2つのストレージ構造があります.シーケンスストレージとチェーンストレージです.対応するスタックはシーケンススタックとチェーンスタックとなる.以下では,この2つのスタックに関する動作をそれぞれ紹介する.
一、シーケンススタック
シーケンステーブルと同様に、スタック内の要素をアドレスのセットで連続的に格納します.以前のシーケンステーブルは配列によって実現され、配列の長さは図の前に定数に設定する必要があります.要素の個数が配列の最大長を超えると、挿入に失敗します.
次に、拡張可能なシーケンススタックを実現する.すなわち、要素数が設定された最大長を超えると、より大きなメモリを申請して要素を格納することができる.
1.シーケンススタックの構造
まず,このシーケンススタックは拡張を実現するため,配列では実現できない.したがって、メモリを動的に申請し、スタック内の要素を入れることができます.スタック内の要素には、動的メモリ申請で返されたポインタを使用して配列形式でアクセスします.
次に、このダイナミックメモリのサイズは初期にデフォルト値に設定できます.デフォルト値を超えると、より大きなメモリを再申請して拡張の目的を達成できます.
最後に、スタック内の実際の要素の数を知る必要があります.で行ないます.および既定の長さと比較します.
したがって、シーケンススタックの構造は次のように定義されます.
typedef char SeqStackType;                                                                                                            
//        
typedef struct SeqStack
{
    SeqStackType* data;//            
    int size;//        
    int capacity;//        
}SeqStack;

2.初期化順序スタック
シーケンススタックに要素を格納するには、まずメモリ領域があり、申請時にメモリサイズを指定し、初期に1000 char型の空間サイズをデフォルトで申請します.この空間は動的に申請され、スタック内のメンバーdataによって指向される.スタック内の要素にアクセスします.初期時はスタックにノードがないため,実際の長さsizeは0である.
コードは次のとおりです.
//      ，stack        
void InitSeqStack(SeqStack* stack)
{
    if(stack == NULL)
    {
        //    
        return;
    }

    stack->size = 0;//        0                                                                                               
    stack->capacity = 1000;//            1000
    stack->data = (SeqStackType*)malloc(sizeof(SeqStackType)*(stack->capacity));//          
}

スタックは「後進先出」の特徴があるため、出、入スタック時にスタックの一端で行わなければならない.シーケンステーブルのヘッダでスタックに入る場合は、スタック内の要素を順次後方に移動する必要があります.この場合、シーケンススタック全体を巡回する必要があります.同じように、スタックを出るときも、遍歴する必要があります.
したがって,シーケンススタックの末尾に出て,スタックに入る.size-1は、シーケンススタックの最後の要素が存在する下付き文字を表すために使用できるため、スタックに入るときにsizeとして下付き文字を直接指定した要素に設定できます.スタックを出るときは、size-1と表示されている値を削除するだけです.シーケンススタック全体を渡る必要はありません.
3.末尾挿入スタック
(1)まず,シーケンススタックの長さがデフォルト長に等しいか否かを判定する必要がある.等しい場合は、拡張が必要な場合はスタックに入ることができます.待たない場合は、直接スタックに入ります.
(2)拡張時には,元のメモリスペースが限られているため,より大きなスペースを動的に申請する必要があり,新しいスペースのサイズをカスタマイズできる.申請に成功したら、元の空間の内容を新しい空間にコピーし、元の空間にコピーし、最後にシーケンススタックのdataを新しい空間に指し示せばよい.
(3)スタックに入るときは、sizeと表記された位置の値を指定値に設定し、スタック長に1を順次加算するだけでよい.
コードは次のとおりです.
//    
void SeqStackPush(SeqStack* stack,SeqStackType value)
{
    if(stack == NULL)
    {
        //    
        return;
    }
    if(stack->size >= stack->capacity)
    {
        //        ,      
        stack->capacity = stack->capacity*2 + 1;
        //          
        SeqStackType* new_data = (SeqStackType*)malloc(sizeof(SeqStackType)*(stack->capacity));
        //               
        int i = 0;
        for(;i < stack->size;i++)
        {
            new_data[i] = stack->data[i];
        }

        //          
        free(stack->data);
        //                 
        stack->data = new_data;
    }                                                                                                                                 
    //    
    stack->data[stack->size++] = value; 
    return;
}

4.末尾削除スタック
(1)まずシーケンススタックの中が空であるか否かを判定し,空であるとスタックを出て失敗する.
(2)空でなければ,直接シーケンススタック長を1だけ減らせばよい.この時点で、元の末尾要素は無効な要素になりました.
コードは次のとおりです.
//    
void SeqStackPop(SeqStack* stack)
{
    if(stack == NULL)
    {
        //    
        return;
    }
    if(stack->size == 0)
    {
        //    
        return;
    }
    //             
    --stack->size;
}

5.スタックトップ要素を取る
(1)順序スタックが空であるか否かを判断し、空であると失敗する
(2)は空ではなく,シーケンススタックの末尾がスタックトップの位置であるため,size-1と表記された要素を保存するだけでよい.
コードは次のとおりです.
//     ,   ：-1      ，0      
int SeqStackTop(SeqStack* stack,SeqStackType* value)
{
    if(stack == NULL || value == NULL) 
    {
        //    
        return -1;
    }

    if(stack->size == 0)
    {
        //    
        return -1;
    }

    *value = stack->data[stack->size - 1];
    return 0;
}

6.廃棄順序スタック
シーケンススタックは、初期化前に申請されたメモリ領域と要素がないため、破棄後にシーケンススタックを初期化前の状態に戻します.すなわちdataが指す動的申請のメモリを解放し,有効長と実際長をともに0にすればよい.
コードは次のとおりです.
//     
void Destory(SeqStack* stack)
{
    stack->size = 0;
    stack->capacity = 0;
    free(stack->data);
    return;
}

二、チェーンスタック
チェーンスタックは、単一チェーンテーブルによって実現される.スタックに要素を入れるたびに、チェーンテーブルにノードを追加し、要素をスタックし、ノードを解放します.スタックには「後進先出」という特徴があるため、チェーンテーブルの末尾に挿入および削除するたびに、チェーンテーブル全体を巡回して末尾ノードを見つけます.ヘッダを挿入および削除する場合は、ヘッダポインタに基づいてチェーンテーブルのヘッダ要素ノードを見つけるだけです.チェーンテーブルを巡回する必要はありません.したがって,チェーンスタックの出,入スタックはチェーンテーブルのヘッダ削除とヘッダ挿入によって実現される.
1.チェーンスタックの接点構造
チェーンスタックは単一チェーンテーブルで実現されるので、単一チェーンテーブルのノード構造と同じである.データドメインと次のノードを指すnextドメインから構成されます.
typedef char LinkStackType;                                                                                                           
//         
typedef struct LinkStackNode
{
    LinkStackType data;
    struct LinkStackNode* next;
}LinkStackNode;

2.チェーンスタックの初期化
シングルチェーンテーブルの初期化と同様に、ブログ「シングルチェーンテーブルの基本操作」を参照して詳細に説明します.
//     
void LinkStackInit(LinkStackNode** pstack)
{
    if(pstack == NULL)
    {
        //    
        return;
    }
    *pstack = NULL;
}

3.チェーンスタックのインスタック操作
チェーンスタックのインスタックは、単一チェーンテーブルのヘッダ挿入によって実現される.ここでも詳しくは説明しません.
//    
LinkStackNode* CreateNode(LinkStackType value)
{
    LinkStackNode* new_node = (LinkStackNode*)malloc(sizeof(LinkStackNode));
    new_node->data = value; 
    new_node->next = NULL;
    return new_node; 
}   

//    
void LinkStackPush(LinkStackNode** pstack,LinkStackType value)
{
    if(pstack == NULL)
    {
        //    
        return;
    }   
    
    //    
    LinkStackNode* new_node = CreateNode(value);
   //     next                  
    new_node->next = *pstack;
    //                                                                                                                    
    *pstack = new_node;
    return;
}

4.チェーンスタックの出庫操作
チェーンスタックのスタックアウト操作は、単一チェーンテーブルのヘッダ削除によって実現される.
(1)まず,チェーンテーブルが空であるか否かを判断し,空であるとスタックアウトに失敗する.
(2)空ではなく,ヘッダポインタが2番目のノードを指し,2番目のノードを新しい先頭ノードとする.
(3)元のヘッダノードを解放する
コードは次のとおりです.
//    
void DestoryNode(LinkStackNode* node)
{
    free(node);
}   

//    
void LinkStackPop(LinkStackNode** pstack)
{
    if(pstack == NULL)
    {
        //    
        return;
    }   
    if(*pstack == NULL)
    {
        //   
        return;
    }   
    //          
    LinkStackNode* to_delete = *pstack;
    //            
    *pstack = to_delete->next;
    //                                                                                                                        
    DestoryNode(to_delete);
    return;
}

5.スタックトップ要素を取る
このときのスタックトップはチェーンテーブルのヘッダにあります.
(1)チェーンテーブルが空の場合は失敗
(2)空でなければ,ヘッダ元ノードのデータドメインを保存すればよい.
コードは次のとおりです.
//     
int LinkStackTop(LinkStackNode* stack,LinkStackType* value)
{
    if(stack == NULL)
    {
        //   
        return -1;
    }
    *value = stack->data;                                                                                                             
    return 0;

}

6.チェーンスタックの廃棄
初期化前のチェーンスタックにはヘッダポインタが1つしかないので、破棄後は初期化前の状態に戻ります.だから
(1)チェーンテーブルを巡回して各ノードを解放する
(2)ヘッドポインタが野ポインタにならないようにヘッドポインタを空にする
コードは次のとおりです.
//     
void LinkStackDetory(LinkStackNode** stack)                                                                                           
{
    if(stack == NULL)
    {   
        //    
        return;
    }   
    //             
    LinkStackNode* to_delete = *stack;
    while(to_delete != NULL)
    {   
        LinkStackNode* next_node = to_delete->next;
        free(to_delete);
        to_delete = next_node;
    }   
    //      
    *stack = NULL;
    return;
}
fetch postパラメータ
mui JSONによる動的生成リスト