• 締切済み

線形リストのコードでどーしても理解できない個所があります。

線形リストのコードでどーしても理解できない個所があります。 (以下、コード部分) typedef struct __node { char name[20]; char tel[16]; struct __node *next; } Node; typedef struct { Node *head; Node *tail; } List; Node *AllocNode(void) { return ((Node *)calloc(1, sizeof(Node))); } /*--- 新たに生成したノードを先頭へ挿入 ---*/ void InsertNode(List *list, const char *name, const char *tel) { Node *ptr = list->head; list->head = AllocNode(); strcpy(list->head->name, name); strcpy(list->haed->tel, tel); list->head->next = ptr; } /*--- pが指すノードの直前にノードを挿入 ---*/ void PutNodeP(List *list, Node *p, const char *name, const char *tel) { if (p == list->head) InsertNode(list, name, tel); else { Node *temp = AllocNode(); if (p == list->tail) list->tail = temp; else *temp = *p; strcpy(p->name, name); strcpy(p->tel, tel); temp->next = p; } } 上の29行目以降の≪pが指すノードの直前にノードを挿入≫についてです。 if文部分については理解できますが、else文部分について、何をやっているのかわからないです。Ｃの基本的な部分（ポインタも含めて）については充分に理解しているつもりです。 どなたか御教授頂けないでしょうか。 長々と書いてしまいましたがよろしくお願いします。

みんなの回答

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.4

list->tail が指しているのはダミーのノードで実はデータが入っていないと見た＞#3... あれ? でもそうするとダミーのノードが 2つもいるから無駄だ. 最初に空のリストをどのように作っていますか?

回答No.3

なるほど。Tacosanさんの説明でどのように挿入しているかがわかりました。後に挿入して中身を入れ替えているのですね。 ただ、そうなると以下の部分、elseはいらないんじゃないでしょうか？ if (p == list->tail) list->tail = temp; else *temp = *p; *temp = *pの部分、p == list->tailであるかどうかに関わらず実行されるべきだと思うのですが。

kerberosMA
質問者

補足

else文以下です。 字下げがうまく表示されないみたいなので こちら側で付け加えました （かえって見づらくなりましたがお許しください）。 else{ (タブ)Node *temp = AllocNode(); (タブ)if(p == list->tail) (タブ)(タブ)list->tail = temp; (タブ)else (タブ)(タブ)*temp = *p; (タブ)strcpy(p->name, name); (タブ)strcpy(p->tel, tel); (タブ)p->next = temp; }

  • Tacosan
  • ベストアンサー率23% (3656/15482)
回答No.2

や, 「pが指すノードの直前にノードを挿入」というコメントが紛らわしいですが, 得られるリストだけを見れば「p が指すノードの直前に挿入した『よう』」には見えます＞#1. で本題ですが, 図を描いて動作を調べてみましたか? ・p の指すノードの後に新しいノードを挿入する ・今挿入したノードに p の指すノードの内容をコピーする ・もともと p が指していたノードには新しい内容を入れる という一連の処理をしているだけです.

回答No.1

このコード、本当に正しいのでしょうか？ pが指すノードの「直後」ではなく「直前」に挿入するんですよね？ そうするとheadからlistを辿っていかないといけないと思うのですが、そうしているようには見えないですね。 詳しいコードは書きませんが、こんな流れになると思います。 if (p == list->head) InsertNode(list, name, tel); else { // p の直前のノードを見つける（仮にp0とします）。 // 新しいノードを生成する(temp)。name、telも設定します。 // tempをp0とpの間に挿入する。　 }　 直前に挿入するので、pがtailであるかどうかは気にしなくていいはずです。

kerberosMA
質問者

補足

すいません、一部誤りがありました。 44行目について （誤）temp->next = p; （正）p->next = temp; 以上です。 本当に申し訳ありませんでした。 以上です、よろしくお願い致します。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. C・C++・C#

関連するQ&A

  • アルゴリズム　線形リスト

    最近リストについて習い始めました。入力したデータと同順に並ぶリストを作成しようと思い、コードを打ったのですが…動作中止の表示がでてしまいました。どこが間違っているのか、ずっと悪戦苦闘して組んでいるのですが、全く出口が見えてきません。何が間違えているのか、はたまた根本的に違うのか、ご指導して頂けると有難いです。 以下、コードです。 #include <stdio.h> #include <stdlib.h> #include <string.h> struct hito{ char name[20]; int age; struct hito *next; }; void main(void){ struct hito *p, *head, *dummy; char new_name[20]; int new_age; dummy = (struct hito *)malloc(sizeof(struct hito)); head = dummy; dummy->next = p; dummy = p; while (scanf("%s %d" , new_name, &new_age) != EOF) { p = (struct hito *)malloc(sizeof(struct hito)); strcpy(p->name, new_name); p->age = new_age; p->next = head; head = p; } while(p != NULL) { printf("\t%-20s %3d\n" , p->name, p->age); p = p->next; } }

  • (構造体)双方向連結リストの作成！

    ダミーノードを先頭に、双方向連結リストを作成したいのですがなかなかうまくできません。とりあえず、ダミーノード無しのものはなんとか出来ましたが、循環連結がうまくいっていない次第です。 どうかお力添え願います。 #include<stdio.h> #include<malloc.h> #include<process.h> typedef struct node{ struct node *left; char name[20]; int age; struct node *right; }NODE; NODE *memalloc(void); void main(void) { NODE *head, *tail, *p; tail = NULL; while(p = memalloc(), printf("名前 年齢入力(Ctrl + Zで終了)＞"), scanf("%s %d", p -> name, &p -> age) != EOF){ p -> left = tail; tail = p; } p = tail; head = NULL; while(p != NULL){ p -> right = head; head = p; p = p -> left; } head -> left = tail; p = head; printf("リスト表示\n"); while(p != NULL){ printf("名前:%20s 年齢:%5d\n", p -> name, p -> age); p = p -> right; } } NODE *memalloc(void) { NODE *ptr; if((ptr = (NODE *)malloc(sizeof(NODE))) != NULL){ return ptr; } printf("\n動的メモリ割当に失敗しました。\n"); exit(1); return 0; }

  • 線形リスト

    どうしても解けない課題がありまして、投稿しました。 どうか、お願いします。。。。 課題内容 下記の構造体を利用した線形リストを作り、 文字列の頻度を計算するプログラムを作成することを考えます。 typedef struct node { char *str; int hindo; struct node *next; } Node; このため、以下のヘッダファイルの名前を hindo.h とするとき、 以下の課題に答えなさい。 hindo.h typedef struct node { char *str; int hindo; struct node *next; } Node; Node* newnode(); void dispHindo(Node* p); int countHindo(Node* p, char *key); void delList(Node*p); Node のポインタを与えると、そのポインタが指す線形リストを解釈し、頻度を出力した後 ---------- を出力する void dispHindo(Node* pointer) を作成しなさい。 書式は一行ずつ「文字列: 頻度」となるようにしなさい。 なお、線形リストの最終ノードの next には NULL が入っていることとし、この場合他のメンバの値は使用しないものとします。 そして下記のプログラムと結合し、実行例と同じものが出ることを確認しなさい。 テストプログラム #include <stdio.h> #include "hindo.h" int main(void){ Node x, y , z, end; x.str="abc"; x.hindo=2; x.next=&y; y.str="def"; y.hindo=3; y.next=&z; z.str="ghi"; z.hindo=1; z.next=&end; end.next=NULL; dispHindo(&end); dispHindo(&x); return 0; } 実行例 ---------- abc: 2 def: 3 ghi: 1 ----------

  • List構造

    Listの尻にノードを追加する関数で困っています。 以下に、ソースの一部を掲載させていただきます。 typedef struct __node{ int data; struct __node *next; }Node; ... /*リストの尻にノードを追加する関数 * 引数： head. リストの先頭ノードのポインタ data. リストの尻に追加したいint型の変数*/ void Insert_Tail(Node *head, int data) { Node *ptr = head; if(ptr == NULL){ /*<ノードが存在しない時には追加されない>*/ /*領域の確保*/ 　　　　　head = (Node*)calloc(1,sizeof(Node)); /*データをセット*/ head->data = data; head->next = NULL; return ; }else{ /*<ノードが存在するときには正常に動作>*/ while(ptr->next != NULL){ ptr = ptr->next; } /*領域の確保*/ ptr->next = (Node*)calloc(1,sizeof(Node)); 　　　　　/*データのセット*/ ptr->next->data = data; ptr->next->next = NULL; } } コメントアウトにも書かせていただきましたが、ノードがすでに存在するときには、正常にノードの最後に追加してくれるのですが、ノードが存在しない時にはリストに追加してくれません。 どうかご指導、ご指摘の程お願いします。

  • C言語　リスト

    (1) /* list.c */ #include <stdio.h> #include <stdlib.h> struct node { int num; struct node *next; }; main() { struct node *head, *p; int x; head = NULL; while(scanf("%d",&x) != EOF) { p = (struct node *)malloc(sizeof(struct node)); p->num = x; p->next = head; head = p; } //　リストの要素のnumの値を先頭から順に表示する p=head; while(p!=NULL) { printf("%d\n" ,p->num); p = p->next; } } (2) struct node *q; q = head; while(q->next != NULL) q = q->next; (1)を(2)を使い新しいノードをリストの最後に追加するようにしたいのですが どう書いたら良いのか教えていただきたいです

  • リストの作成と出力（C言語）

    こんにちは<_ _> リストの問題についてなのですが出力と逆順に出力するプログラムで headと前のデータの間に新しいデータを追加するように作ったのですが 入力した値が帰ってきません・・・ http://www9.plala.or.jp/sgwr-t/c/sec15-5.html などを見て見ましたが原因がいまいちよくわかりません。 どなたか教えてください おねがいします<_ _> #include<stdio.h> #include<malloc.h> struct tfield{ char name[20]; char tel[20]; struct tfield *pointer; }; struct tfield *talloc(void); int main(void) { struct tfield *head,*p; char buffer[BUFSIZ]; head=NULL; while(1){ p=talloc(); if(scanf("%s",buffer) == EOF){ break; strcpy(p->name, buffer); } if(buffer == "^Z")break; printf(" "); if(gets(buffer) == EOF){ if(scanf("%s",buffer) == EOF){ break; strcpy(p->tel, buffer); } p->pointer=head; /*今までの先頭ポインタを次のポインタに*/ head=p; } p=head; while(p!=NULL){ printf("%6s %s\n",p->name,p->tel); p=p->pointer; } return 0; } struct tfield *talloc(void) /*記憶領域の取得*/ { return (struct tfield *)malloc(sizeof(struct tfield)); } 変数は変えるなとのことです。 あと、 「name tel name tel name tel ^z name tel name tel name tel」 と表示したいのですがCtrl+zを二回押さないとできません＞＜、 当方プログラム1ヶ月の初心者です ご指導どうかよろしくお願いします<_ _>

  • リストの削除について（構造体)

    リストの削除のプログラムを実行して行ってみると、リストの削除処理中にプログラムが終わって変更後処理がうまく表示されません。どこが間違っているかが分からないしだいです。返答のほどよろしくお願いいたします。 #include<stdio.h> #include<malloc.h> #include<string.h> struct list{ char name[20]; int age; struct list *next; }; void main(void) { struct list *head, *p, *n, *old; char key[20]; /*ダミーノード作成*/ head = (struct list*)malloc(sizeof(struct list)); old = head; while(p = (struct list*)malloc(sizeof(struct list)), printf("name age入力\n"), scanf("%s %d", p -> name, &p -> age) != EOF){ old -> next = p; old = p; } free(p); old -> next = NULL; p = head -> next; printf("変更前リスト\n"); while(p != NULL){ printf("name:%s age:%d\n",p -> name, p -> age); p = p -> next; } printf("削除key入力（name)\n"); gets(key); n = head; while(n != NULL){ old = n; n = n -> next; //printf("n -> name %s\n", n -> name); if(strcmp(n -> name, key) == 0){ printf("%s削除\n", key); //printf("n -> name %s old -> name %s\n", n -> name, old -> name); old -> next = n -> next; } } p = head -> next; printf("変更後リスト\n"); while(p != NULL){ printf("name:%s age:%d\n", p -> name, p -> age); p = p -> next; } }

  • c言語の問題です。ファイルからデータを読み込み連結リストに記憶しソートするプログラムです。お願いします

    ソート部分がどうしてもできません。 またソートは以下のアルゴリズムで行うものです 与えられたリストをリストＡ、ソート済みのリストをリストＢとする。処理の開始段階では、リストＢは空である。 1.リストＡの要素の中で、最大値をもつ要素Ｃを探す。 2.要素ＣをリストＡから削除する。 3.要素ＣをリストＢの先頭に挿入する。 4.リストＡが空であれば終了。空でなければ 1. にもどる。 #include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct physical Physical; struct physical { char name[41]; int age; float height; float weight; Physical *next; }; void read_data(char *file,Physical *p,Physical *tail); int comp1(const Physical *, const Physical *); int comp2(const Physical *, const Physical *); int comp3(const Physical *, const Physical *); int comp4(const Physical *, const Physical *); void sort(char *arg,Physical *p,Physical *q); Physical *listsort(Physical *p, int (*compar)(const void *, const void *)); int main(void) { char s[20],t,u[20]; Physical *p,*tail,*q; p=malloc(sizeof(Physical)); q=malloc(sizeof(Physical)); tail=malloc(sizeof(Physical)); while(1) { printf("CMD>"); fflush(stdout); fgets(s,20,stdin); sscanf(s,"%c %s",&t,u); switch(t){ case 'q':exit(0); case 'r':read_data(u,p,tail); break; case 's':sort(u,p,q); break; case 'd': while(q!=NULL) { printf("%s %d %.1f %.1f ",q->name,q->age,q->height,q->weight ); q=q->next;} break; } } free(p); return 0; } void read_data(char *file,Physical *p,Physical *tail){ FILE *fp; char string[100]; Physical header; tail=&header; header.next = NULL; p->next = NULL; tail->next = p; tail = p; if ((fp = fopen(file, "r")) == NULL) { exit(1); } while(fgets(string,sizeof(string),fp)!= NULL) { sscanf(string,"%s %d %f %f",p->name,&p->age,&p->height,&p->weight); Physical *tail2; tail2=malloc(sizeof(Physical)); tail2->next=NULL; p->next=tail2; p=tail2; } fclose(fp); } void sort(char *arg,Physical *p,Physical *q){ if(strcmp(arg,"name") == 0) q=listsort(p,(int(*)(const void*, const void*))comp1); if(strcmp(arg,"age") == 0) q=listsort(p,(int(*)(const void*, const void*))comp2); if(strcmp(arg,"height") == 0) q=listsort(p,(int(*)(const void*, const void*))comp3); if(strcmp(arg,"weight") == 0) q=listsort(p,(int(*)(const void*, const void*))comp4); } Physical *listsort(Physical *p,int (*compar)(const void *, const void *)){ Physical *q, *max,*s,*head; s=malloc(sizeof(Physical)); head=malloc(sizeof(Physical)); head=NULL; while(p->next){max = p, q = p->next; while( q->next ) { if( compar(q->next,max->next) ) max = q; q = q->next;} s=max->next; max->next=max->next->next; if(head==NULL) {head=s;} s->next=s; } return head; } int comp1(const Physical *a, const Physical *b){ return (strncmp(a->name,b->name,sizeof(Physical))); } int comp2(const Physical *a, const Physical *b){ if(a->age > b->age) return 1; else return 0; } int comp3(const Physical *a, const Physical *b){ if(a->height > b->height) return 1; else return 0; } int comp4(const Physical *a, const Physical *b){ if(a->weight > b->weight) return 1; else return 0; }

  • 解析木

    ノードの中身を表示しながらトラバースする関数 void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); を再帰を使って書きなさい。 という問題がとけません。どなたかアドバイスをください。 ちなみに、この関数以外は下のように作りました。 #include <stdio.h> #include <stdlib.h> struct node { struct node *right; char key; struct node *left; }; typedef struct node * NodePointer; void treeinitialize(void); NodePointer makenode(char c); void preorder(NodePointer node); void inorder(NodePointer node); void postorder(NodePointer node); NodePointer head, tail; int main(){ treeinitialize(); //テスト用の木を作成 head->right=makenode('+'); head->right->left=makenode('1'); head->right->right=makenode('*'); head->right->right->left=makenode('2'); head->right->right->right=makenode('3'); //トラバース printf("preorder: "); preorder(head->right); printf("\n"); printf("inorder: "); inorder(head->right); printf("\n"); printf("postorder: "); postorder(head->right); printf("\n"); return 0; } void treeinitialize(void){ head=makenode(-1); tail=makenode(-1); head->right=tail; head->left=tail; } //ノードを作成し、そのノードへのポインタを返す。 NodePointer makenode(char c){ NodePointer x; x=malloc(sizeof(struct node)); x->key=c; x->right=tail; x->left=tail; return x; } void preorder(NodePointer node){ } void inorder(NodePointer node){ } void postorder(NodePointer node){ }

  • 線形リスト

    ファイルから単語を読み込んでいき、単語とその単語の数を出力するプログラムです。単語の区切り方は英文字以外の時です。 例 http://www.sig.sig.org だったとしたら http 1回 www 1回 sig 2回 org 1回 という課題なのですが、while文で読み込んで英文字以外が入力されるたびにif文でぬけ、単語の登録、比較するプログラムを作ったのですが、まったく動きません。（たぶん関数への引渡しとかがおかしいのだと思うのですが） どこがどうちがうのか教えてくださいお願いします。 #include<stdio.h> struct node{//構造体 int count; char tango[20]; struct node *next; }; struct node *new(char t[20]) {//単語の入力 struct node *p; strcpy(p->tango,t); p->count=0; return p; } struct node *in(struct node *p,char t[20]) {//単語の比較 int c; c=strcmp(p->tango,t); if(c==0){ p->count++; return p; } else if(p->next==NULL) {p->next=new(t);} else {in(p->next,t);} } int *pt(struct node *p){//出力 if(p==NULL)return; else printf("%s:%d\n",p->tango,p->count); pt(p->next); } int main() { FILE *fp; int b,i; char a[20],ch; struct node *root; i=0;b=0; for(i=0;i<20;i++) a[i]=0;//初期化 i=0; fp=fopen("data1.txt","r"); if(fp==NULL)//ファイルを開く return; while((ch=fgetc(fp)) != EOF){//文字の読み込み if(!((97<=ch)&&(ch<=122)&&(65<=ch)&&(ch<=90))){//英字以外の時 b=b+1; if(b==0)//初期のみ root=new(a); else//それ以降 in(root,a); for(i=0;i<20;i++){//初期化 a[i]=0; i=0; } } else{//英文字の時 a[i]=ch; i=i+1; } } pt(root);//出力関数へ fclose(fp); }

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する