C言語実装スタック(チェーンテーブルベース)

スタックの下位データ構造は配列であってもチェーンテーブルであってもよく,チェーンテーブルでスタックを実現することは理論的に無限大である.
次に、チェーンスタックの実装コードを示します.

#include
#include
typedef int datatype;

//Link Stack      ，       

// struct LinkList
// {
//     datatype data;
//     struct LinkList *next;
// };

struct stack
{
    datatype data;
    struct stack *next;
};

typedef struct stack Stack;
//   
Stack *s;
//    
void init()
{
    s=NULL;
}

//       
bool Empty()
{
    if(s==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//        
// void full(Stack *s)
// {
//     if(s->top==realsize-1)
//     {
//         realsize++;
//         s->data=(datatype *)realloc(s->data,realsize);
//     }
// }

//  
void Push(datatype element)
{
    Stack *p = (Stack *)malloc(sizeof(Stack));
    p->data=element;
    p->next=s;
    s=p;             
}

//  
void Pop()
{
    if(!Empty(s))
    {
        s=s->next;
    }
    else
    {
        printf("  
");
    }
}

//     
datatype Top()
{
    if(!Empty(s))
    {
        return s->data;
    }
    else
    {
        printf("  
");
    }
}

//   
void Destroy()
{
    free(s);//         
    s=NULL;
    // free(s.data); //      
}

テストコード

#include
#include "LinkStack.h"
int main()
{
    int i=0;
    // struct stack s;
    //    
    printf("
###########    ###########
");
    init();
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=10;i++)
    {
        Push(i);
    }
    printf("----------------------------------");
    printf("
###########     ###########
");
    printf("%d
",Top());
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=12;i++)
    {
        Pop();
    }  
    printf("----------------------------------");    
    printf("
###########     ###########
");
    Top();
    printf("----------------------------------");
    printf("
###########   ############
"); 
    Push(10);
    Destroy();
    Top();
}

このようなスタックと以前の配列で実現されたスタックには共通の欠点があり,複数のスタックを自分で定義することはできないが,グローバル変数はエラーを回避する点であり,以下で述べる.
ここでは、前の配列実装スタックとの自己定義複数のスタックを実装し、前の方法を適用すると、スタックがパラメータとして直接関数に渡され、スタックの修正によって元のスタックの要素値が変更されるエラーが発生します.
しかし、ここでチェーンスタックは、ポインタをパラメータとして関数に入力し、パラメータポインタの指向を修正し、元のポインタを変更することはありません.
ポインタを関数値として返す方法と、2次ポインタを使用する方法の2つがあります.
まず最初の方法のスタックの実現を見てみましょう

#include
#include
// #define maxsize 10
typedef int datatype;

//Link Stack      ，       

// struct LinkList
// {
//     datatype data;
//     struct LinkList *next;
// };

struct stack
{
    datatype data;
    struct stack *next;
};

typedef struct stack Stack;

// Stack *s;
//    
Stack* init(Stack *s)
{
    s=NULL;
    return s;
}

//       
bool Empty(Stack *s)
{
    if(s==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//        
// void full(Stack *s)
// {
//     if(s->top==realsize-1)
//     {
//         realsize++;
//         s->data=(datatype *)realloc(s->data,realsize);
//     }
// }

//  
Stack* Push(Stack *s,datatype element)
{
    Stack *p = (Stack *)malloc(sizeof(Stack));
    p->data=element;
    p->next=s;
    s=p;             //        ，         ，        ，        
    return s;
}

//  
Stack* Pop(Stack *s)
{
    if(!Empty(s))
    {
        s=s->next;
    }
    else
    {
        printf("  
");
    }
    return s;
}

//     
datatype Top(Stack *s)
{
    if(!Empty(s))
    {
        return s->data;
    }
    else
    {
        printf("  
");
    }
}

//   
Stack* Destroy(Stack *s)
{
    free(s);//         
    s=NULL;
    return s;
    // free(s.data); //      
}

スタックのテストコード

#include
#include "LinkStack1.0.h"
int main()
{
    int i=0;
    Stack p; 
    Stack *s;
    s=&p;
    // struct stack s;
    //    
    printf("
###########    ###########
");
    s=init(s);
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=10;i++)
    {
        s=Push(s,i);
    }
    printf("----------------------------------");
    //     
    printf("
###########     ###########
");
    printf("%d
",Top(s));
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=12;i++)
    {
        s=Pop(s);
    }  
    printf("----------------------------------");
    //         
    printf("
###########     ###########
");
    Top(s);
    printf("----------------------------------");
    //   
    printf("
###########   ###########
"); 
    s=Push(s,10);
    s=Destroy(s);
    Top(s);
}

この方法は比較的面倒で,使用者の負担を増やし,コード量を増やした.
第2の方法を見て、2級ポインタ(ポインタのポインタ)スタックの実現

#include
#include
// #define maxsize 10
typedef int datatype;

//Link Stack      ，       

struct LinkList
{
    datatype data;
    struct LinkList *next;
};

typedef struct stack* Stack;

//    
void init(Stack *s)
{
    *s=NULL;

}

//       
bool Empty(Stack *s)
{
    if(*s==NULL)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//        
// void full(Stack *s)
// {
//     if(s->top==realsize-1)
//     {
//         realsize++;
//         s->data=(datatype *)realloc(s->data,realsize);
//     }
// }

//  
void Push(Stack *s,datatype element)
{
    Stack *p = (Stack *)malloc(sizeof(struct LinkList));
    p->data=element;
    p->next=*s;
    *s=p;             //        ，         ，        ，        
}

//  
void Pop(Stack *s)
{
    if(!Empty(s))
    {
        *s=(*s)->next;
    }
    else
    {
        printf("  
");
    }
}

//     
datatype Top(Stack *s)
{
    if(!Empty(s))
    {
        return (*s)->data;
    }
    else
    {
        printf("  
");
    }
}

//   
void Destroy(Stack *s)
{
    free(s);//         
    *s=NULL;
    // free(s.data); //      
}

スタックのテストコード

#include
#include "LinkStack2.0.h"
int main()
{
    int i=0;
    Stack p; 
    Stack *s;
    s=&p;
    // struct stack s;
    //    
    printf("
###########    ###########
");
    init(s);
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=10;i++)
    {
        Push(s,i);
    }
    printf("----------------------------------");
    //     
    printf("
###########     ###########
");
    printf("%d
",Top(s));
    printf("----------------------------------");    
    //    
    printf("
###########    ###########
");
    for(i=0;i<=12;i++)
    {
        Pop(s);
    }  
    printf("----------------------------------");
    //         
    printf("
###########     ###########
");
    Top(s);
    printf("----------------------------------");
    //   
    printf("
###########   ###########
"); 
    Push(s,10);
    Destroy(s);
    Top(s);
}

これにより、チェーンスタックが実現されます.ここでポインタはパラメータとして関数に渡されますが、実際にはコピーにすぎません.ただ、このコピーは元のポインタと同じ指向なので、ポインタが指す内容を変えることは可能ですが、ポインタ自体を変えるのは間違いなので、二次ポインタが必要です.