- ベストアンサー
今度は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
- ginkgo
- お礼率94% (132/139)
- Java
- 回答数2
- ありがとう数3
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
メソッドを追加する元のクラス自体が分からないので、なんとも言えません…。 が、前の質問と同様に、nextの考慮が足りないと思われます。 新しく追加するノードのnextは、今まで先頭のノードになっていたもののはずですので、少なくともnew IntNode(el, tail) は間違いでしょう。 tailの次が新しく追加したノードで、新しく追加したノードの次がこれまで先頭(?)であったノードになる、ということをプログラムで正しく表現できれば良いでしょう。
その他の回答 (1)
- kacchann
- ベストアンサー率58% (347/594)
つまり「挿入」ですね…。 「鎖のつなぎ変え」を、絵的に直感的に理解してくだされ。 （No.1の方が最後に書かれている手順のとおりです） ↓かろうじてみつけた図解入り解説。 ■http://www.mybrain.jp/java/DS/DS_linkedList_insert.html (このページを文字列 "挿入するコード"で検索) ■http://www.mars.dti.ne.jp/~torao/program/structure/linklist.html (このページを文字列 "データの追加"で検索)
お礼
ありがとうございました。
補足
先ほどはどうもありがとうございました。 実はもうそろそろ行かなくちゃ、の時間なので それらのURLを少しだけ拝見させていただきました。 分かりやすいですね。 私らの教科書よりずっと見やすいです。 …それで考えると下に補足した内容であってますよね?
関連するQ&A
- Singly linked listで最後から二番目に挿入
先週、テストがありました。 結構自信があったんですが、教授によるとすごく悪かったそうです…(結果はまだもらっていません)。 それで「問題全部、もう一度家でやり直してこい」と言われました。 下がその問題の一つです。 Write a method to insert a new node into a singly linked list before the tail node. If the list is empty, then the new node will be both the head and the tail node. This method will be a member of IntSLList class given on page 74. public void addBeforeTail(int el) { // ブランク そのIntSLList.javaはIntNode.javaとセットで使われます(でもどちらもmainがないんです)。 そしてここ↓にあります。 http://www.mathcs.duq.edu/drozdek/DSinJava/. (きっと)基となるメソッド(IntSLList.java内) public void addToTail(int el) { if (!isEmpty()) { tail.next = new IntNode(el); tail = tail.next; } else head = tail = new IntNode(el); } 私自作のメソッド public void addBeforeTail(int el) { if (!isEmpty()) { tail = new IntNode(el); tail.next = tail; } else head = tail = new IntNode(el); } リストの最後の一つ手前に挿入するんでしょうが Double linked listならnextとpreviousがあって tail.previous = new IntNode(el); tail = tail.previous; にすれば解決だと思うのですが、 Singlyだとnextしかないのでどうすればいいのかはっきり分かりません。 勘で基となるだろうメソッドを逆にしてみました。 上の私自作のメソッドであってますでしょうか? Javaの神様、どうかお助け下さい。m(__)m
- ベストアンサー
- Java
- リストがわかりません。
下のプログラムはリストに昇順になるように 入力された要素を挿入するプログラムですが、うまくいきません。どうか教えてください。 #include<stdio.h> static int count; struct node_tag{ int data; struct node_tag *next; }; typedef struct node_tag node_t; node_t *insert_node( node_t *t, int d ); node_t *print_list( node_t *r ); int main( void ) { node_t root; int data; root.next = NULL; for ( ;; ) { printf( "> " ); if ( scanf( "%d", &data ) != 1 ) break; insert_node( &root, data ); print_list( &root ); } return; } node_t *insert_node( node_t *t, int d ) { node_t *new_node; new_node = (node_t *)malloc( sizeof(node_t) ); if( new_node == NULL ) return NULL; if(count == 0) { new_node -> data = d; new_node -> next = NULL; t -> next = new_node; count++; } else { for(; t -> next != NULL; t = t -> next) { if(t -> next -> data >= d) break; } if(t -> next -> data == d) return; else if(t -> next -> data > d) { new_node -> data = d; new_node -> next = t -> next; t -> next = new_node; } else if(t -> next == NULL) { new_node -> data = d; t -> next = new_node; new_node -> next = NULL; } } return new_node; } node_t *print_list( node_t *r ) { node_t *p; printf("[ "); for( p = r -> next; p != NULL; p = p -> next) { printf("%d ", p -> data); } printf("]\n"); }
- ベストアンサー
- C・C++・C#
- 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言語 二分木探索
今、int型の二分木にデータを追加する関数(引数は二分木へのポインタと追加する値、追加されたノードへのポインタを返す)をつくろうとしてます。 以前リストにデータを追加する関数をつくったのでそれを変更してつくろうとしているのですが途中までいってつまってしまいました。 つくりかたを教えてください。 よろしくお願いします！ struct BinaryTreeNode{ int data; struct BinaryTreeNode *l_next; struct BinaryTreeNode *r_next; }; struct BinaryTree{ int node_num; struct BinaryTreeNode *root; }; BinaryTreeNode *BinaryTreeNodeAlloc(void) { BinaryTreeNode *node; node = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode)); if (node == NULL) { return (NULL); } node->l_next = NULL; node->r_next = NULL; return (node); } BinaryTreeNode *BinaryTreeDataAdd(BinaryTree *list, int x) { BinaryTreeNode *ptr; BinaryTreeNode *prev; BinaryTreeNode *new_node; ptr = list->root; prev = NULL; while (ptr) { ←？？ if (ptr->data < x) { prev = ptr; ptr = ptr->next; } else if (ptr->data == x) { return (NULL); } else { new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); ←？？ } new_node->data = x; new_node->next = ptr; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); } } new_node = BinaryTreeNodeAlloc(); if (new_node == NULL) { exit (0); } new_node->data = x; new_node->r_next = NULL; new_node->l_next = NULL; if (prev != NULL) { prev->next = new_node; } else { list->head = new_node; } list->node_num++; return (new_node); }
- 締切済み
- C・C++・C#
- 単方向リストの昇順ソートについて
単方向リストに値を入れるところまでは何とか切り抜けることができましたが、次はソートにてこずっています。this.value と this.next.valueの値を比べて入れ替えるというところまでは何とか想像つきますが、どうやってソートが完了するまでまわしてあげればいいかが分かりません。 class Chain3{ public static void main(String args[]){ Node start = new Node(Integer.parseInt(args[0])); for(int i = 1; i < args.length; i++){ start.append(Integer.parseInt(args[i])); } start.sort(); } } class Node{ private int value; private Node next; public Node(int value, Node next){ this.value = value; this.next = next; } public Node(int value){ this.value = value; } public Node(){ this.value = 0; this.next = null; } public int getValue(){ return value; } public void setValue(int value){ this.value = value; } public Node getNext(){ return next; } public void setNext(Node n){ this.next = n; } public void append(int v){ if(this.next == null) this.next = new Node(v); else this.next.append(v); } //昇順にソートする public void sort(){ int tmp; /*ここで私はバブルソートで行おうと思っているのだが、どう回数制限していいか分からない*/ if(this.value > this.next.value){ tmp = this.value; this.value = this.next.value; this.next.value = tmp; } this.next.sort(); } }
- ベストアンサー
- Java
- 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したつもりなのですが、どうもそうではないようで、困っています。 どうか、御指導の程、お願いします。
- ベストアンサー
- C・C++・C#
- Javaで単方向リスト作成に行き詰まり
Javaで単方向リストを作成しようとしているのですが、append()で１件目のvalueやnextの値をアクセスするにはどうしたらいいか分かりません。ちなみにmain関数は変更しなくていいようです。 class Chain{ public static void main(String args[]){ //1件目のノードの作成 if(args.length == 0){ System.out.println("パラメータを指定してください"); return; } Node start = new Node(Integer.parseInt(args[0])); //2件目のノード作成 for(int i = 1; i < args.length; i++){ start.append(Integer.parseInt(args[i])); } } } class Node{ //メンバ変数（インスタンス変数） private int value; private Node next; //コンストラクタ public Node(int value, Node next){ this.value = value; this.next = next; } public Node(int value){ this.value = value; } public Node(){ this.value = 0; this.next = null; } //アクセスメソッド(setter, getter) public int getValue(){ return value; } public void setValue(int value){ this.value = value; } public Node getNext(){ return next; } public void setNext(Node n){ this.next = n; } //通常のメソッド //追加する public void append(int v){ Node chain = new Node(); chain.value=chain.getValue(); System.out.println(chain.value); } }
- ベストアンサー
- Java
- 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・C++・C#
- 線形リストのコードでどーしても理解できない個所があります。
線形リストのコードでどーしても理解できない個所があります。 (以下、コード部分) 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文部分について、何をやっているのかわからないです。Ｃの基本的な部分（ポインタも含めて）については充分に理解しているつもりです。 どなたか御教授頂けないでしょうか。 長々と書いてしまいましたがよろしくお願いします。
- 締切済み
- C・C++・C#
- 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です
- ベストアンサー
- C・C++・C#
お礼
ありがとうございました。
補足
ご回答、ありがとうございます。 無い知恵を振り絞って考えたところ、下のようになりました。 else { tail.next = new IntNode(el, tail.next); //tail = tail.next; ←いらない } つまり、AddToTailとほとんど同じコードなのですがTailの位置を移動させない、 よって新しく追加されたノードは先頭として認識される…こんな解釈でよろしいでしょうか? あってます…よね?