単方向リストとは?
- 単方向リストは、データ構造の一種であり、リストの要素が一方向にのみ進むことができる。
- リストの先頭にはデータと次の要素へのポインタが入り、最後の要素のポインタには0が入る。
- 要素の追加や削除は、ポインタの操作によって行われる。
- ベストアンサー
単方向リスト
図は単方向リストを表している。“東京”がリストの先頭であり、そのポインタには次のデータのアドレスが入っている。また、“名古屋”はリストの最後であり,そのポインタには0が入っている。 先頭データへのポインタ アドレス データ ポインタ 10 10 東京 50 30 名古屋 0 50 神奈川 90 70 長野 30 90 山梨 70 150 岐阜 アドレス150に置かれた“岐阜”を、“長野”と“名古屋”の 間に挿入する処理を答よという問題なんですが答えが アドレス、 データ部分 、 ポインタ 10 東京 50 30 名古屋 0 50 神奈川 90 70 長野 150 90 山梨 70 150 岐阜 30 になるんですが解き方がわかりません。教えてください
- wakatyu1
- お礼率2% (2/90)
- その他(プログラミング・開発)
- 回答数2
- ありがとう数7
- みんなの回答 (2)
- 専門家の回答
質問者が選んだベストアンサー
10東京-50神奈川-90山梨-70長野-30名古屋-0 を 10東京-50神奈川-90山梨-70長野-150岐阜-30名古屋-0 になればいいのですよ。 ので、長野の次に150岐阜を、150岐阜の次を30名古屋に設定します。
その他の回答 (1)
- ok-kaneto
- ベストアンサー率39% (1798/4531)
「ポインタ」が次のデータの「アドレス」を指しているのは解りますか? 「岐阜」を挿入するってことは ・挿入点を見つける(この場合は「長野」→「名古屋」の間なので変更するのは「長野」と「岐阜」) ・「岐阜」のポインタを「名古屋」にする ・「長野」のポインタを「岐阜」にする です。
関連するQ&A
- 単方向リストの解釈
多数のデータが単方向リスト構造で格納されている。このリスト構造には、先頭ポインタとは別に、末尾のデータを指し示す末尾ポインタがある。次の操作のうち、ポインタを参照する回数が最も多いものはどれか。 ア リストの先頭にデータを挿入する。 イ リストの先頭のデータを削除する。 ウ リストの末尾にデータを挿入する。 エ リストの末尾のデータを削除する。 (平成24年度春期 問7) 各選択肢の参照ポインタ数はいくつになるのでしょうか。 解説書によって必要なポインタ参照数が異なっていて、理解できずにいます。 とある解説書では、 ア 2回のポインタの参照が必要 イ 1回のポインタの参照が必要 ウ 2回のポインタの参照が必要 と記述してあり、またある解説書では ア 0回のポインタの参照が必要 イ 2回のポインタの参照が必要 ウ 1回のポインタの参照が必要 エ 3回のポインタの参照が必要 と記述されていました。 先頭から末尾の一つ手前のデータまで順にたどって参照する必要のあるエが一番ポインタを参照する回数が多そうだな、と想像はできるのですが、実際の参照回数までは理解の外です。。 ご教授お願いします。
- 締切済み
- 情報処理技術者
- 双方向リストについて
*prevは前の要素へのポインタ *nextは後ろの要素へのポインタ typedef struct list_t { char line[256]; struct list_t *prev; struct list_t *next; } LIST; 削除処理 *pが削除する要素 delete_line(LIST *p) { p->prev->next = p->next; p->next->prev = p->prev; free(p) } *pが挿入する要素 *cが挿入する場所 insert_line(LIST *c, LISt *p) { /*両隣へポインターをつなぐ*/ p->prev = c->prev; p->next = c; /*両隣のポインターをつなぎ換える*/ c->prev->next = p; c->prev = p; } これは、ある本に書かれていたものなのですが、どうしても、理解ができません。図を描きながら追ってみたのですが、cは、挿入する場所を表しているのですが、図で描こうにもどこがその場なのかが、わかりません。あと挿入処理のところでpやcが代入されていますが、pやcは、どこを表しているのですか?この本の説明がおかしいのでしょうか?それとも私の考え方が違うのでしょうか・・・。ご指導いただければありがたいです。
- ベストアンサー
- C・C++・C#
- 双方向リストの関数
双方向リストにデータファイルから読み込んだ氏名と成績のデータを追加し,リストの末尾から順にデータを表示するプログラムを作成したのですが、insertLast() 関数を用いて末尾ノードの後ろに新しいノードを連結するという部分をどのようにして良いのかわからず困っています。 どのように記述して良いのかわからなかった部分を/*** ***/のコメントで示してあります。 どなたかアドバイスやヒント、その他の指摘などご教授してくださる方いましたらよろしくお願いします。 #include <stdio.h> #include <stdlib.h> #include <string.h> #define NAME_LENGTH 20 /* 名前を格納する文字列の長さ */ /* 双方向リストのノードとなる構造体の定義 */ typedef struct sList{ struct sList *prev; /* 前のノードのアドレス */ char name[NAME_LENGTH]; /* 名前 */ char grade; /* 成績 */ struct sList *next; /* 次のノードのアドレス */ } sNode; /* この構造体を sNode型 と定義する */ /* 双方向リストの先頭と末尾を格納するための構造体 */ typedef struct { sNode *firstNode; /* リストの先頭ノードのアドレス */ sNode *lastNode; /* リストの末尾ノードのアドレス */ } manageList; /* 双方向リストの末尾にノードを追加する関数 insertLast() 引数 manageList *list リストの先頭・末尾ノードを管理する構造体のアドレス sNode *node 末尾に追加したいノードのアドレス 返値 なし */ void insertLast(manageList *list, sNode *node ) { /*** リストの末尾にノードを追加する ***/ return; } /* 双方向リストの新しいノードを作成する関数 makeNewNode() 引数 char *aName 名前(文字列)の先頭アドレス char aGrade 成績 返値 sNode * 新しく作成したノードの先頭アドレス */ sNode *makeNewNode(char *aName, char aGrade ) { sNode *pNewData; /* sNode 型のメモリ領域を確保 */ pNewData = (sNode *) malloc( sizeof(sNode) ); /* 名前と成績のデータを設定する */ strcpy( pNewData->name, aName ); pNewData->grade = aGrade; pNewData->prev = NULL; pNewData->next = NULL; return( pNewData ); } /* main() 引数 なし 返値 int 正常終了の時 0 異常終了の時 -1 (ファイルの読み込み失敗など) */ int main( void ) { manageList list; /* リストの先頭・末尾ノードのアドレスを持つ構造体 */ sNode *pNew; /* 新しく作成したノードのアドレスを持つ変数 */ sNode *pNow; /* 現在見ているノードのアドレスを持つ変数 */ FILE *fp; /* データファイルのファイルポインタ */ char name[ NAME_LENGTH ]; /* ファイルから読み込んだ名前を一時的に保持する変数 */ char grade; /* ファイルから読み込んだ成績を一時的に保持する変数 */ /* 初期状態では先頭・末尾ノードともNULL */ list.firstNode = NULL; list.lastNode = NULL; /* データファイル exer6.txt を読み込み用に開く. ファイルが開けなかった場合,エラーメッセージを表示し異常終了する.*/ fp = fopen("exer6.txt","r"); if(NULL == firstNode){ printf( "ファイルが開けませんでした. \n" ); return( -1 ); } /* データをファイルの最後(EOF)まで読み込み,双方向リストにデータを追加する */ while( EOF != fscanf( fp, "%s %c", name, &grade ) ) { /* 新しいノードを作成 */ pNew = makeNewNode( name, grade ); /*** insertLast() 関数を用いて末尾ノードの後ろに新しいノードを連結する ***/ pNow->next = pNew ; pNew->prev = pNow ; pNow = pNew ; /* ファイルを閉じる */ fclose( fp ); /* 現在見ているノードを末尾ノードにセットする */ pNow = lastNode /* 末尾のノードから前のノードへたどりながらデータを出力する */ while( NULL != pNow ) { /* 出力 */ printf( "%s %c\n", pNow->name, pNow->grade ); /* 現在見ているノードを一つ前のノードにする */ pNow = pNow->prev; } return( 0 ); }
- 締切済み
- C・C++・C#
- 双方向リストのソート方法について。
単刀直入に言いまして、双方向リストのデータを入れ替えるのではなくて、リスト前後を指すポインタの繋ぎ代えをして、ある一定条件に従ったリストへのソートをしたいと思っています。 リスト構造の前後にダミーを置いて……という方法は取りたくなく、出来るだけメモリを節約した方法が知りたいです。 また、そのリスト数は大体20個くらいで、1秒間に大体50~60回くらい呼ばれるモノです。 リストのデータ数は比較的大きい物です。 参考になる書籍とかでも構いませんので、是非とも教えて下さい。
- 締切済み
- C・C++・C#
- Linked List(線形リスト)を使ったデータのソート
大学の、Cの課題で、困っています。 どこが違うのか教えていただけたら嬉しいです。 【課題】 1行に1つの数値データを、複数行入力すると、 このデータを1行ずつ読んでいって、それをひとつの構造体として保持し、 数値データの小さい順にリンクされるようなLinked Listとなるようにプログラムを作る。 入力したデータが数値だったら、Linked Listを先頭から巡り、それを挿入すべき場所を見つける。 そしてデータを格納するための構造体の領域をmalloc関数で確保し、そこにデータを入れ、実際にリストに挿入する。 読み込むべき入力データが無くなったら、最後にLinked Listで保持しているデータを1行ずつ書き出してみる。 【変な結果が出るプログラム】 #include<stdio.h> main() { int c, n, *nextp; void *malloc(size_t size); struct listdata{ int i; struct listdata *nextp; }; struct listdata *hajime; struct listdata *pointer; hajime = NULL; while ( ( c = getchar() ) != EOF ){ if ( '0' <= c && c <= '9' ){ n = n * 10 + ( n - '0' ); } pointer = ( struct listdata *) malloc ( sizeof (struct listdata) ); pointer -> i = n; hajime = pointer -> nextp; } printf ( "%d\n", nextp ); pointer = hajime; while ( pointer != NULL ){ printf ( " %d\n", pointer -> i ); pointer = pointer -> nextp; } } よろしくお願いします(>_<)
- ベストアンサー
- C・C++・C#
- 十字方向に参照するリスト構造
struct TEST{ ~ TEST pPrev;//1つ前のアドレス TEST pNext;//後ろ TEST pHigh;//1つ上 TEST pLow;//下 }; といった感じでTEST構造体が上下左右に2つの双方向のリスト構造をもち、インスタンスを作成する時は TEST *p = new TEST; TuikaYoko( p );//横方向にリストにつなげる p = new Test; TuikaTate( p );//縦につなげる ; と1つずつ作成しリストに追加していきリストを順番に参照するときは for(ENEMY *list=top; list; list=list->pNext) for(p=list; p; p=p->pLow) Draw( p ); という風にしたのですが、エラーは出ないのですが実行するとEXEが強制終了されてしまいます。 void TuikaYoko( TEST *p ){//横方向のリスト追加 if( end == NULL ){//リストの中が空の時 top = end = p; }else{ p->pPrev = end; end->pNext = p; end = p; } top->pPrev = NULL; end->pNext = NULL; head = back = end; } void TuikaTate( TEST p ){//縦方向 if( back==NULL ){//縦方向に1つも無いときは //自分が縦の先頭として横方向に繋がる TuikaYoko( p ); }else{ p->pHigh = back; back->pLow = p; back = p; } head->pHigh = NULL; back->pLow = NULL; } という風に横方向を親としてそれに連なる感じで縦方向にpをリストに繋げるイメージでやってみました。 横方向の先頭をtop、終端をend 縦方向の先頭をhead、終端をbackとしてそれぞれグローバル変数で作成しNULLで初期化しました。 横方向だけのリスト構造はうまくいったのですが、これを2重にするとどうしてもうまくいきません。どこが間違っているのでしょうか? それとも、もっといい方法があれば教えて下さい。お願いします。
- ベストアンサー
- C・C++・C#
- 双方向リストで…、
typedef struct score{ char name[40]; int eng; int math; int sci; struct score *next; struct score *prev; } SCORE; SCORE head; /* 双方向リストに要素を追加する */ void add_list(void) { SCORE *p, *new; in_file = fopen("input.txt", "r"); if ( in_file == NULL ){ printf("error: not open file.\n"); exit(0); } while( fgets(line, sizeof(line), in_file) != NULL ){ p = head.next; /* 先頭要素の次の要素のアドレス */ /* 新しく追加する要素のためのメモリ領域を確保する */ new = malloc( sizeof(SCORE) ); /* 新しい要素のデータを設定 */ sscanf(line, "%s %d %d %d", new->name, &new->eng, &new->math, &new->sci); new->next = p->next; /* 新しい要素の次の要素へのアドレスを設定 */ new->prev = p; /* 新しい要素の前の要素へのアドレスを設定 */ p->next->prev = new; /* 新しい要素の直後の要素のprevに、新しい要素のアドレスを設定 */ p->next = new; /* 新しい要素の直前の要素のnextに、新しい要素のアドレスを設定 */ } } ↑のところがうまくいきません。 何がだめか教えてください。
- 締切済み
- C・C++・C#
- リニア中央新幹線の停車駅はどうなりますか?
JR東海が、リニア中央新幹線「東京-名古屋」の停車駅は 各県に1つ建設すると発表しました。 では、その駅とはどこになるのでしょうか? 品川(東京都)-橋本(神奈川)-甲府(山梨)-飯田(長野)-中津川(岐阜)と 予想してみました。 あと、その先は発表されていませんが、 鈴鹿(三重)-伊賀(三重)-奈良(奈良)-新大阪(大阪)と 予想してみましたが、いかがでしょうか? みなさんの予想をお聞かせ願います。
- ベストアンサー
- 路線・駅・電車
- 双方向リストへのデータ登録
C言語の勉強をしております。 双方向リストへのデータの登録でうまくいかず詰まってしまいました。 <ヘッダファイル> // 構造体 typedef struct address { char names[32]; /* 名前 */ char tels[32]; /* 電話番号 */ struct address *prev; /* 前へのポインタ */ struct address *next; /* 次へのポインタ */ }Address; extern Address *top_pt; extern Address *work_pt; extern Address *w_pt; extern Address *inAdd; // ファイルからの読み込み top_pt = NULL; while(!feof(fp)) { work_pt = (Address *)malloc(sizeof(Address)); if(!work_pt){ printf("メモリ不足"); exit(1); } fscanf(fp, "%s %s", work_pt->tels, work_pt->names); work_pt->next = top_pt; top_pt = work_pt; work_pt->prev = top_pt; /* カウンタを用意して、実際のデータ件数をカウントしておく */ ++trueCount; } これで、双方向リストへファイルの内容を格納することは出来ました。 次に、構造体へデータを新規登録したいのですが、構造体を共有している別ソースファイルにて、 for(i=0; 1000>trueCount+i; i++){ inAdd = (Address *)malloc(sizeof(Address)); if(!inAdd){ printf("メモリ不足"); exit(1); } printf("登録する名前を入力してください:"); gets(inAdd->names); /* 名前が未入力でEnterされた場合 */ if(!*inAdd->names){ /* ループを抜け、トップメニューへ */ flag = 1; break; } printf("電話番号を入力してください:"); scanf("%s", inAdd->tels); /* 読み込んだ構造体へデータを追加する */ work_pt->next = inAdd; inAdd->prev = work_pt; inAdd->next = NULL; } として、構造体の中身を表示させたところ、 ファイルの最終データと、入力したデータのみになってしまいました。 なぜなのか分かりません・・・。 有識者の方でこの下手なソースを読んで指南していただける方はおられますでしょうか? また、データ登録の際に名前の入力に「gets」を使用しているんですが、 「scanf」だとその次のif文が効かないみたいで少し困っています。 (出来ればANSIC標準のscanfを使いたい) 以上、よろしくお願いいたします。
- ベストアンサー
- C・C++・C#
- エクセルで2つのリストを統合するには?
エクセルの別々のシートにある2つのリストを統合したいのですが、過去の質問などを見てもうまくいきません。具体的には 【表1】 番号 氏名 住所 A 佐藤 東京 B 高橋 神奈川 C 渡辺 埼玉 D 田中 千葉 E 小林 山梨 【表2】 番号 氏名 年齢 B 高橋 22 D 田中 45 という2つの表で、これを 番号 氏名 住所 年齢 A 佐藤 東京 B 高橋 神奈川 22 C 渡辺 埼玉 D 田中 千葉 45 E 小林 山梨 のようにまとめたいのです。 「データの統合」を使ってみましたがうまくいきませんでした。よろしくお願いします。
- 締切済み
- オフィス系ソフト