プログラミングのネタ帳

30代からプログラミングをはじめた。記憶力が悪いのでメモ代わりに。

C の構造体でリスト形式のデータ構造をつくる

アルゴリズムやデータ構造の勉強もした方がいいのだろうなと思ってちょくちょくやっています。

そして、同時にC実践プログラミングも読み進めていて、構造体で表題のことができるのかと感心しました。

 

構造体のポインタで操作するので慣れるまではだいぶ苦労しましたが、実際、絵でかいてみるのがいいかもしれません。

慣れてきて思ったことは、

・メモリの行先を常に把握し(構造体の先頭なのか、構造体の変数なのか)、指示する

・実装上同じ名前の変数で新しくメモリを確保するので、ポインタを一時保管する必要がある

というところ。半ばパズルなのだなと思いました(プログラミングがそもそもそういうものだと言われればそうですが。)

 

以下はおそらく最もシンプルであるろう方向のリストの実装です。

しかし、

・行先の構造体データのメモリ確保する際に同じ変数名を使うため、ひとつ前の構造体のアドレスをtmp_ptrで保管したり、

・whileの中でデータの代入を完結するために dummy_ptr ( malloc()でメモリ上に実体のある) を使用したりと工夫はあります。 


#include 
#include 
#include 

//構造体の宣言
struct tfield{
    char hantei[8];
    int score;
    struct tfield *pointer;
};

//プロトタイプ宣言
struct tfield *genlist();
void display(struct tfield *p);

int main(){
    struct tfield *p;
    //リストを生成する関数、
    //引数:なし 戻り値:リスト先頭のアドレス
    p=genlist();

    //リストの先頭のポインタを与えるとNULLになるまで表示する関数 
    //引数:リストの先頭のアドレス 戻り値:なし
    display(p);
}

struct tfield *genlist(){
    int i=0;
    int array_score[]={90,80,70,60};
    char array_hantei[][2]={"A","B","C","D"};
    struct tfield *head_ptr,*mydata_ptr,*dummy_ptr;
    
    //実体のあるdummyを作ることで、dummpy->pointerを使用できる
    //これを挟むことでwhileの中でmydataを繰り返し使える
    dummy_ptr=malloc(sizeof(struct tfield));
    //リストの先頭のアドレスは後々displayの際に使用するので保管する
    head_ptr=dummy_ptr;
    while(1){
        mydata_ptr=malloc(sizeof(struct tfield));
        //データの代入
        strcpy(mydata_ptr->hantei,array_hantei[i]);
        mydata_ptr->score=array_score[i];
        
        //dummyu->pointerにmydataの先頭のアドレスをいれて、
 //_dummy->pointer次のデータにアクセスできるようにする
        dummy_ptr->pointer=mydata_ptr;
        //dummyポインタに次のデータ(mydata)のアドレスを格納する(更新する)
        dummy_ptr=mydata_ptr;

        if(strcmp(mydata_ptr->hantei,"D")==0){break;}
        i=i+1;  //配列のカウンタ用
    }
    mydata_ptr->pointer=NULL;
    return head_ptr;
}

void display(struct tfield *p){
    while(1){
        //dummy_ptrの中身はみなくていいので、いきなりp->pointerとしている
        p=p->pointer;
        printf("%s %d %p \n",p->hantei,p->score,p->pointer);  
        if(p->pointer==NULL){break;}
    }
}
 
実行結果
A 90 0x56173d88c2e0 
B 80 0x56173d88c300
C 70 0x56173d88c320
D 60 (nil)