• ベストアンサー

今度はdoubly linked listの問題です…

今日はかなり崖っぷちなのでどんどん質問します、すみません。 今回はdoubly linked listの質問です。 Consider the doubly linked list below. After each of the following statements, redraw the list to show the changes that have been made. Process the statements in sequence, that is, each statement should make changes in the list modified by the previous statement. ｈｅａｄ－＞｜１０｜　｜／｜ 　　　　　　　　　　　↓　↑ 　　　　　　｜　５｜　｜　｜ 　　　　　　　　　　　↓　↑ 　　　　　　｜２０｜　｜　｜ 　　　　　　　　　　　↓　↑ ｔａｉｌ　－＞｜３０｜　｜　｜ 1. head.next.next.prev.info = 100; 2. head.next.next.next = tail.prev.prev; 3. heat.next.prev = head.next.next.next.next; ※／はヌル(=Null)の意味です。 (これで分かってくださるといいんですが) 1.と2.は正解だそうです: 1.は上から二番目の5を100に変えました。 2.は上から三番目のnextが今変えたばかりの100を参照するようにしました。 そして問題の3.です。 head.next.prevですからnext(一番目)が二番目を参照して、 prevが今度は一番目を参照するので今現在"／"があるところを… head.next.next.next.nextに変更ですから 最初のnext(一番目)が二番目を参照して、 二番目のnextが三番目を参照して、 三番目のnextは2.で変更したとおり、二番目を参照して、 四番目のnextは三番目を参照するので… "／"のprevがずーーーっと伸びて20を参照するように書きました。 でも、間違っているらしいです。 どこがおかしいのでしょうか? プログラミングの神様、どうかお助け下さい。m(__)m

  • ginkgo
  • お礼率94% (132/139)

質問者が選んだベストアンサー

  • ベストアンサー
  • bikkuri
  • ベストアンサー率33% (23/68)
回答No.1

ぱっと見、あっているように思いますが、 >"／"のprevがずーーーっと伸びて20を参照するように書きました。 は、「１番目のデータのprevが（を）３番目のデータを参照するように変更」 （つまり、１番目のデータのprevの値であったnullを変更） の意味にとれます。（ずーーーっと伸びては少々意味不明） だとすると、たしかに間違ってますね。 更新されるのは、１番目のデータじゃないです それにしても、2と3の操作の意味って？？

ginkgo
質問者

お礼

ご回答、ありがとうございます。 あ、自分で書いたのをよくよく読んでみると 仰る通り、更新されるのは一番目じゃなくて 二番目のprevですね。 更新する場所は参照先じゃなくて参照元でした。 これで正解です…よね? 2.と3.の操作の意味は本当に謎ですね。 最初見たときは四番目のデータでも消すのかと思いました。

その他の回答 (1)

  • kacchann
  • ベストアンサー率58% (347/594)
回答No.2

＞更新されるのは一番目じゃなくて ＞二番目のprevですね。 うーん、たぶん、それが正解。 左辺head.next.prev。 これは「head.next(で指されたオブジェクト)のprev変数」のこと。 つまり2段目のprev変数。

ginkgo
質問者

お礼

Linked listは私にとってはまだややこしいです。 頭の中がスパゲティーのようになってました(@_@) ようやく解けてきました。 確認して下さってありがとうございました。

  1. カテゴリ
  2. [技術者向] コンピューター
  3. プログラミング・開発
  4. その他（プログラミング・開発）

関連するQ&A

  • 双方向リストのバブルソートについて

    双方向リストをバブルソートを用いてソートしたいです。 下記がプログラム(一部)ですが、ソートした後にリスト表示すると 無限ループに陥ります。 どこがいけないのでしょうか。 #include <stdio.h> #include <stdlib.h> struct cell{ int data; struct cell *next, *prev; }; void insert_head(struct cell **head, int num){ struct cell *p, *p1; p = *head; p1 = make_cell(); *head = p1; p1->data = num; p1->next = p; if(p1->next != (struct cell *)NULL){ p1->next = p; p->prev = p1; } } void print_list(struct cell *head){ struct cell *p; p = head; printf("data = \n"); while(p != (struct cell *)NULL){ printf("%d\n", p->data); p = p->next; } } void sort_list(struct cell **head){ struct cell *p, *p2; int i, n; n = 0; p = *head; while(p->next != (struct cell *)NULL){ p = p->next; n++; } for(i = 0, p = *head; i < n-2; i++){ if(p->data > p->next->data){ if(p == *head){ *head = p->next; }else{ p->prev->next = p->next; } p2 = p->next; p->next = p->next->next; p->next->next = p; p->next->next->prev = p; p->next->prev = p->prev; p->prev = p2; }else p = p->next; } } int main(void){ struct cell *head = (struct cell *)NULL; int n; while(1){ printf("1:Insert head 2:Insert tail 3:Delete 4:List 5:Sort 6:Exit\n"); scanf("%d", &n); switch(n){ case 1: printf("num = "); scanf("%d", &n); insert_head(&head, n); break; case 2: printf("num = "); scanf("%d", &n); insert_tail(&head, n); break; case 3: printf("num = "); scanf("%d", &n); delete_cell(&head, n); break; case 4: print_list(head); break; case 5: sort_list(&head); break; case 6: return 0; break; } } }

  • 双方向リストのプログラミングのチェック

    指定したファイルを読み込み、一行ずつ構造体に保存し、表示させる。その後、キーボードから指定した行を削除し、処理後の結果を表示させる・・・といったプログラミングを作成しています。 通常の表示の部分はできましたが、後は指定した行の削除の部分ができません。 あらかじめＨＰで調べてあるので、削除するときは、その削除したい行をまたいで、前後のリストを繋げるといった概念的なのは大体理解できました。 自分なりに考えたり調べて、下のように打ちました。 ですが、キーボードから入力した値をどう関数に対応させていくのか、 delete_head,delete_tailの関数の部分に出る、head,tailは使えない的なエラーの対処の仕方がわからなく、詰まってます。 アドバイス、他にも直す場所等ありましたらお願いします。 #include<stdio.h> #include<stdlib.h> #define LINE 1000 typedef struct num{ char line[LINE]; struct num *next; struct num *prev; }Num; void normal(Num **,Num **,char *); void reverse(Num *,Num *,char *); void delete_head(void); void delete_tail(void); void delete(Num *target); int main(int argc,char *argv[]) { FILE *fp; char line[LINE]; int i=0,j; Num *head,*tail,*p; head=NULL; tail=NULL; fp=fopen("test.txt","r"); if(fp==NULL){ fprintf(stdout,"File not found.\n"); exit(1); } while(fgets(line,LINE,fp)!=NULL) { normal(&head,&tail,line); } p=head; while(p!=tail){ printf("%s\n",p->line); p=p->next; } printf("%s\n",p->line); p=tail; while(p!=head){ printf("%s\n",p->line); p=p->prev; } printf("%s\n",p->line); printf("input number\n"); scanf("%d",&j); p=head; for(i=0;i<=j;i++);{ p=p->next; } if(p==head){ delete_head(void); } else if(p==tail){ delete_tail(void); } else{ delete(p->prev); } p=head; while(p!=tail){ printf("%s\n",p->line); p=p->next; } printf("%s\n",p->line); fclose(fp); return 0; } void normal(Num **s,Num **e,char *g){ Num *tmp; int i; if(*s==NULL){ *s=(Num *)malloc(sizeof(Num)*1); (*e)=(*s); for(i=0;((g[i]!='\0')&&(g[i]!='\n'));i++){ (*s)->line[i]=g[i];} (*s)->next=*e; (*s)->prev=*s; } else{ tmp=(Num *)malloc(sizeof(Num)*1); for(i=0;((g[i]!='\0')&&(g[i]!='\n'));i++){ tmp->line[i]=g[i];} tmp->prev=(*e); (*e)->next=tmp; tmp->next=(*e); (*e)=tmp; } return ; } void reverse(Num *kan1,Num *kan2,char *g){ Num *tmp; int i; tmp=(Num *)malloc(sizeof(Num)*1); for(i=0;((g[i]!='\0')&&(g[i]!='\n'));i++){ tmp->line[i]=g[i];} tmp->prev=kan1; kan1->next=tmp; tmp->next=kan2; kan2->prev=tmp; return ; } void delete_head(void){ Num *second=head->next; if(secound==NULL){ free(head); head=NULL; tail=NULL; } else{ second->prev=NULL; free(head); head=second; } } void delete_tail(void){ Num *second_last=head->prev; if(second_last==NULL){ free(tail); head=NULL; tail=NULL; } else{ second_last->next=NULL; free(tail); tail=second_last; } } void delete(Num *target){ Num *after_target; Num *before_target; after_target=target->next; before_target=target->prev; after_target->prev=target->prev; before_target->next=target->next; free(target); }

  • 今度はcircular singly linked listです…

    度々、すみません。切羽詰っています(汗)。 Write a method to insert a node at the front of a circular singly linked list. The circular list maintains only one reference to the tail node as shown in figure 3.15 on page 91. 　　　　　　　　　　　　　　　　　　　　ｔａｉｌ 　　　　　　　　　　　　　　　　　　　　↓ 　→｜１０｜→．．．→｜５｜→｜２０｜－ ｜　　　　　　　　　　　　　　　　　　　　　　　　｜ 　－－－－－－－－－－－－－－－－－ Ａｄｄ　１００ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　ｔａｉｌ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　↓ 　→｜１００｜→｜１０｜→．．．→｜５｜→｜２０｜－ ｜　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　｜ 　－－－－－－－－－－－－－－－－－－－－－ (きっと)基となるメソッド public void addToTail(int el) { if (isEmpty()) { tail = new IntNode(el); tail.next = tail; else { tail.next = new IntNode(el, tail.next); tail = tail.next; } } 私自作のメソッド public void addToFront(int el) { if (isEmpty()) { tail = new IntNode(el); tail.next = tail; else { tail = new IntNode(el, tail); tail.next = tail; } } if文のisEmptyの部分は正解だそうです。 ただ、else文の中が間違っているそうです。 勘でtailとtail.nextをそっくり逆にしたんですけど 駄目だったようです。 でも他にもう案は浮かびません。 リンクの神様、どうかお助け下さい。m(__)m

    • ベストアンサー
    • Java
  • C++ リストの末尾要素の削除

    連結リストの末尾の要素を削除するプログラムを教えてください。 自分で何度も書き直してみたのですが、どうしてもうまくうごきません。 自分で書いた現状が以下のものですが、止まってしまいます。 void List::removeLast(){ if (head == NULL)return; Cell *p = head; Cell *prev = NULL; while (p!= NULL){ prev = p; p = p->next; } delete prev; } 以下のプログラムが動かすにはremoveLast()をどう変えたらよいのでしょうか？ よろしくお願いします。 #include <iostream> using namespace std; // クラスの宣言 class Cell { friend class List; // Listクラスから，このクラスに自由にアクセスできるようにする private: int data; // データ Cell *next; // 次のセルのアドレスを指すポインタ public: Cell(int _data, Cell *n = NULL){ data = _data; next = n; } }; class List { private: Cell *head; // 連結リストの先頭要素のアドレスを指すポインタ public: List(){ head = NULL; }; ~List(){ while (head != NULL)removeFirst(); } void addFirst(int data){ head = new Cell(data, head); } void removeFirst(){ if (head == NULL)return; Cell *removed = head; head = head->next; delete removed; } void removeLast(); void print(){ for (Cell *p = head; p != NULL; p = p->next){ cout << p->data << ' '; } cout << endl; } }; // 連結リストの末尾要素を削除する関数 void List::removeLast() { //この部分です ｝ int main() { List l1; for (int i = 0; i < 10; i++) { l1.addFirst(i); } l1.print(); l1.removeLast(); l1.print(); l1.removeLast(); l1.print(); l1.removeLast(); l1.print(); return 0; } 要求される実行結果は以下の通りです リストの内容: 9 8 7 6 5 4 3 2 1 0 リストの内容: 9 8 7 6 5 4 3 2 1 リストの内容: 9 8 7 6 5 4 3 2 リストの内容: 9 8 7 6 5 4 3

  • list構造。。。

    リストの末尾にデータを追加すると、最後に追加したデータで今までのリストのデータが上書きされてしまいます。。 以下に、ソースを掲載させていただきます。 void SetNode(List* node_first, List* node_second, int *data) { node_first->move = data; node_first->next = node_second; return ; } /*末尾に挿入*/ void Insert_Tail(List **head, int* data) { List *ptr = *head; if(ptr == NULL){ *head = (List*)calloc(1,sizeof(List)); SetNode(*head, NULL, data); return ; }else{ while(ptr->next != NULL){ ptr = ptr->next; } ptr->next = (List*)calloc(1,sizeof(List)); SetNode(ptr->next, NULL, data); } return ; } void show_list(List *list) { List *ptr = list; while(ptr != NULL){ printf("%d\n",*(ptr->move)); ptr = ptr->next; } return ; } int main(int argc, char** argv) { /*宣言*/ Node* root; /**/ List* top; /* 手順のリスト */ int judge; top = NULL; do{ printf("num:"); scanf("%d",&judge); switch(judge){ case 1: /*データを末尾に追加*/ printf("mem:"); scanf("%d",mem); root->board = mem; Insert_Tail(&top, root->board); break; case 2: /*リストを頭から表示*/ show_list(top); break; default: break; } }while(judge != 0); return 0; } 自分は最後のリストまでたどって、callocしたつもりなのですが、どうもそうではないようで、困っています。 どうか、御指導の程、お願いします。

  • リスト構造の挿入と削除について

    ある本にリストについてのっていたのですが、その本に ソースがのっていたのですが、わかりません。 ソースは、下記に載せたのがすべてです。 リストについてですが、char line[256];は、データの部分で すか？p->prev->next = p->next;これは、かなり複雑ですね こんな参照の方法ありましたっけ？ p->next->prev = p->prev;これも同じです。 p->next = c c->prev = p c->prev->next = p; 上記の３つですが、pとcを代入していますよね、pとcというのは 要素のどの部分でもないですよね。 prevやnextだったら、要素の部分なのでそれをつなぎ換えたり して、リストを組むというのは想像がつくのですが、pとcっていう のは、ただ漠然としていますよね。どこを指しているかわかりま せんよね。char ptr[20];と同じようにptrには、先頭のアドレスが 入っていたように、pとcには、何か具体的な情報が入っている のでしょうか？ /* 両隣へポインターをつなぐ */ p->prev = c->prev; p->next = c; /* 両隣のポインターをつなぎ換える */ c->prev->next = p; c->prev = p; 上記も複雑ですね・・・ 解説お願いします・・・ free(p);はメモリの解放ですか？ リスト *prevは前の要素へのポインター *nextは後ろの要素へのポインター typedef struct list_t { char line[256]; struct list_t *prev; struct list_t *next; } LIST; delete_line(LIST *p) { p->prev->next = p->next; p->next->prev = p->prev; free(p); } insertt_line(LIST *c, LIST *p) { /* 両隣へポインターをつなぐ */ p->prev = c->prev; p->next = c; /* 両隣のポインターをつなぎ換える */ c->prev->next = p; c->prev = p; } ご指導よろしくお願いします。

  • 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; } } コメントアウトにも書かせていただきましたが、ノードがすでに存在するときには、正常にノードの最後に追加してくれるのですが、ノードが存在しない時にはリストに追加してくれません。 どうかご指導、ご指摘の程お願いします。

  • 双方向リストで…、

    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#をちゃんとやろうと思い、勉強のためのコードを見ていたのですが以下の連結リストについてわかりません。わからないところにコメントをつけました。呼び出しメソッドはList.Add(2);です。よろしくお願いいたします。 using System; using System.IO; class Node { public int elem; public Node next; public Node() : this(0, null){}//このメソッドがある意味がわかりません。 public Node(int val, Node next) { this.elem = val; this.next = next;//なぜか最初にnextにデバッグするとnullになりますが2回目デバッグからはNodeになります。そもそもなぜクラスにクラスを代入しているかもわかりません。 } } /// <summary> /// 連結リストクラス /// </summary> class List { public Node head; public List() { head = null; } public void Add(int val) { Node node = new Node(val, this.head); this.head = node; } }

  • C++ 連結リストの結合について

    現在、C++で連結リストの結合を実現しようとしているのですが、自分のやり方ではどうしてもエラーになってしまい、他にうまい実現方法が思いつかないので質問させていただきます。 以下が私が作ったプログラムなのですが、どこをどう変えたらうまく行くのか、具体的に教えて頂けたら嬉しいです。結合関数はaddAll(List &l)です。よろしくお願いします。 #include <iostream> using namespace std; class Cell{ private: int data; Cell *next; public: Cell(int d, Cell *n = NULL){ data = d; next = n; } friend class List; }; class List{ private: Cell *head; public: List(){ head = NULL; } ~List(){ while (head != NULL)removeFirst(); } void addLast(int data); void removeFirst(); void print(); void addAll(List &l); }; void List::addLast(int data){ if (head == NULL){ head = new Cell(data); } else{ Cell *p = head; while (p->next != NULL){ p = p->next; } p->next = new Cell(data); } } void List::removeFirst(){ if (head == NULL){ return; } else if (head->next == NULL){ delete head; return; } Cell *removed = head; head = head->next; delete removed; } void List::print(){ if (head == NULL){ return; } for (Cell *p = head; p != NULL; p = p->next){ cout << p->data << ' '; } cout << endl; } void List::addAll(List &l){ if (l.head == NULL){ return; } else if (head == NULL){ if (l.head == NULL){ return; } else{ head = l.head; return; } } else{ Cell *p = head; while (p->next != NULL){ p = p->next; } p->next = l.head; } return; } int main(){ List l1; l1.addLast(1); l1.addLast(2); l1.addLast(3); l1.print(); List l2; l2.addLast(4); l2.addLast(5); l2.addLast(6); l1.addAll(l2); l1.print(); return 0; } 実行結果は 1 2 3 1 2 3 4 5 6 と表示されればOKです

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

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

質問する