- 締切済み
連結リスト 要素の入れ替え
自分には、難しい内容なので、色々教えていただけると嬉しいです。 リスト構造で、データの入れ替え・ポインタの付け替えを行っているのですが、どこのサイトを見てもどれが、参考になるのか分かりませんでした。 例えば、宣言でgFront→a1→a2→a3→a4→a5→NULLのすでに連結されたリストがあります。 先頭には、ダミー（gFront）のセルがあり、そこからたどって入れ替えていくというものです。 a1からa5の中には、数字が入っているものとします。 a２とa5の入れ替えを行うと仮定して話します。 そして、a２をpreとして、a5をnewとして、preの一つ前をprepreとし、newの１つ前をprenewとして、ひとつ前のnextを調べてポインタの付け替えを行います。 4か所のポインタの付け替え後の結果を、gFront→a1→a5→a3→a4→a2→NULLとしたいです。 swapを使ったリストの中身入れ替えではなく、ポインタの付け替えでリスト自体の入れ替えを行いたいと考えています。 この付け替えの部分がいまいちプログラムの書き方と言いますか、よく理解できていないので、教えていただけないでしょうか？ 文章だけでは、分かりにくいところが多々あるかとは思いますが、宜しくお願いいたします。
- C・C++・C#
- 回答数11
- ありがとう数4
- みんなの回答 （11）
- 専門家の回答
関連するQ&A
- C++ 連結リストの要素の削除について
リストで任意の場所の要素を削除するプログラムを考えているのですが、どうしてもその部分のプログラムにmain関数通りの動きをさせる方法が分かりませんでした。いろいろ試してみたのですが、どこかしらでおかしくなってしまうのです。 以下に私がつくった途中までのプログラムを示すので、removeAt(int index)の中身の例を教えて頂きたいのです。よろしくお願い致します。 #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 removeAt(int index); void print(){ for (Cell *p = head; p != NULL; p = p->next){ cout << p->data << ' '; } cout << endl; } }; // 連結リストの index 番目の要素を削除する関数 void List::removeAt(int index) { //この部分です ｝ int main() { List l1; for (int i = 0; i < 10; i++) { l1.addFirst(i); } l1.print(); l1.removeAt(0); // リストの先頭要素で動作確認 l1.print(); l1.removeAt(2); l1.print(); l1.removeAt(4); l1.print(); l1.removeAt(17); // リストの要素数より大きな引数で動作確認 l1.print(); l1.removeAt(0); // リストの先頭要素で動作確認 l1.print(); l1.removeAt(6); // リストの要素数より大きな引数で動作確認 l1.print(); l1.removeAt(5); l1.print(); return 0; } 要求される実行結果は以下の通りです リストの内容: 9 8 7 6 5 4 3 2 1 0 リストの内容: 8 7 6 5 4 3 2 1 0 リストの内容: 8 7 5 4 3 2 1 0 リストの内容: 8 7 5 4 2 1 0 リストの内容: 8 7 5 4 2 1 0 リストの内容: 7 5 4 2 1 0 リストの内容: 7 5 4 2 1 0 リストの内容: 7 5 4 2 1
- ベストアンサー
- C・C++・C#
- 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
- ベストアンサー
- 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言語 片方向連結リスト
c言語の片方向連結リストのプログラムについて質問があります． 下記のプログラムの関数int get_index(ListPtr l, int value)に以下のようなコードを書く．リストl において値value を持つセルの位置を返す．返り値は，最初のセルが値value を持っていれば0，次のセルが値value を持っていれば1，...，値value を持っているセルが存在しなければ–1とする． また，関数void add(ListPtr l, int index, int value)に以下のようなコードを書く．リストl の位置index に値value を持つセルを挿入．挿入前のリストに対して：index が0 のときは先頭に挿入，index が1 のときは（0から数えて）1番目のセルの前に挿入，index が2 のときは（0から数えて）2番目のセルの前に挿入，...，index がリストのサイズと等しいときはリストの末尾に挿入，それ以外の場合は何もしなくてよい． これらのコードはどのように書けばよいのでしょうか？ #include <stdio.h> #include <stdlib.h> #include <assert.h> /* 連結リスト中のノードの構造体 */ struct node { int val; /* 値 */ struct node *next; /* 次ノード */ }; /* セルとそのポインタの型 */ typedef struct node Node; typedef Node *NodePtr; /* セルを一つ生成 */ NodePtr create_node(int v) { NodePtr n = NULL; n = malloc(sizeof(Node)); n->val = v; n->next = NULL; return n; } /* セルを表示 */ void print_node(NodePtr n) { if (n != NULL) { printf("<%d>", n->val); } else { printf("(null)"); } } /* 連結リストの構造体 */ struct list { /* 先頭セルへのポインタ */ NodePtr head; }; /* 連結リストとそのポインタの型 */ typedef struct list List; typedef List *ListPtr; /* 空の連結リストを生成 */ ListPtr create_list(void) { ListPtr l = NULL; l = malloc(sizeof(List)); l->head = NULL; return l; } /* 連結リスト l が空かどうか判定 */ int is_empty(ListPtr l) { return (l->head == NULL); } /* リスト l の内容を表示 */ void print_list(ListPtr l) { NodePtr n = NULL; if (is_empty(l)) { printf("(empty)\n"); return; } n = l->head; while (n != NULL) { print_node(n); n = n->next; } printf("\n"); } /* リスト l の先頭にセルを挿入 */ void add_first(ListPtr l, int val) { NodePtr n = NULL; n = create_node(val); n->next = l->head; l->head = n; } /* リスト l の先頭セルを削除 */ int delete_first(ListPtr l) { NodePtr n = NULL; int v; /* リストが空なら -1 を返す（負の値はリストに含まれないと仮定）*/ if (is_empty(l)) return -1; v = l->head->val; n = l->head; l->head = l->head->next; free(n); n = NULL; return v; } /* 連結リスト l のサイズを取得 */ int get_list_size(ListPtr l) { NodePtr n = NULL; int size; size = 0; n = l->head; while (n != NULL) { size++; n = n->next; } return size; } /* * 連結リスト l における index 番目のセルの値を取得 * （そのようなセルが存在しなければ -1 を返す） */ int get_value(ListPtr l, int index) { NodePtr n = NULL; if (index < 0) return -1; n = l->head; while (index > 0 && n != NULL) { n = n->next; index--; } return (n == NULL) ? -1 : n->val; } /* リスト l 中の全セルを削除（ループ版）*/ void delete_all(ListPtr l) { NodePtr n = NULL, m = NULL; n = l->head; while (n != NULL) { m = n; n = n->next; free(m); } l->head = NULL; } /* セル n 以降を全て削除（内部処理用の再帰関数）*/ void delete_rest(NodePtr n) { if (n->next != NULL) delete_rest(n->next); free(n); } /* リスト l 中の全セルを削除（再帰版）*/ void delete_all_recursively(ListPtr l) { if (l->head == NULL) return; delete_rest(l->head); l->head = NULL; } /* リスト l 全体を削除 */ #define delete_list(l) (delete_list0(l),l=NULL) void delete_list0(ListPtr l) { delete_all(l); free(l); } /* リスト l において値 val を持つセルの位置を返す */ int get_index(ListPtr l, int value) { return -1; } /* リスト l の位置 index に値 val を持つセルを挿入 */ void add(ListPtr l, int index, int value) { } /* 連結リストの使用例 */ int main(void) { FILE *fp = NULL; char buf[10]; int age; ListPtr l = NULL; l = create_list(); add_first(l, 28); add_first(l, 40); add_first(l, 33); add_first(l, 15); print_list(l); delete_first(l); print_list(l); delete_first(l); print_list(l); delete_first(l); print_list(l); delete_first(l); print_list(l); return 0; }
- ベストアンサー
- C・C++・C#
- [C言語]単連結リストにおける着目ノードの操作
http://www.bohyoh.com/Books/CalgoA/EX/ALGOEX0901.html 上の線形リストのプログラムにおいて、着目ノードを１個次にずらす操作と、１個前にずらす操作を追加したいのですが、単連結リストでは後者の実現は少しばかりややこしく、困っています。 おそらく先頭ノードから後続ノードへのポインタを辿って行って、着目ノードを探索すれば良いのでしょうが……。 尚、前者において着目ノードが末尾ノードだった場合、後者において着目ノードが先頭ノードだった場合は考えないものとします。 皆様にご教授頂けると幸いです。 /* 着目ノードを一個次のノードにする */ void NextCrnt(List *list) { if (list->crnt == NULL){ puts("着目要素はありません。"); } else { list->crnt = list->crnt->next; } }
- ベストアンサー
- C・C++・C#
- 連結リスト
下の連結リストのプログラムに、入力データを確認するための出力部分を追加するという課題が出ましたが分かりませんでした。 要するに下から3行目にあるWriteLinkedList関数を作ればよいということらしいのですが、教えてください。お願いします。 ちなみに1行目にある「pseudo10.h」は先生が作ったプログラムだそうです。ほかに必要な情報があれば教えてください。 #include "pseudo10.h" typedef struct PERSON * PtrPERSON; struct PERSON{ char name[20]; //name long year; //age PtrPERSON next; //pointer }; int MakeLinkedList(PtrPERSON head){ PtrPERSON girl; New(PtrPERSON, girl) InputString(girl->name); InputInt(girl->year); while(girl->year > 0){ girl->next = head -> next; head->next = girl; New(PtrPERSON, girl); InputString(giel->name); InputInt(girl->year); } return 0; } int main(void){ PtrPERSON head; New(PtrPERSON, head); head->next = NULL; MakeLinkedList(head); WriteLinkedList(head); return 0; }}
- 締切済み
- C・C++・C#
- 連結リスト
下の連結リストのプログラムに、入力データを確認するための出力部分を追加するという課題が出ましたが分かりませんでした。 要するに下から3行目にあるWriteLinkedList関数を作ればよいということらしいのですが、教えてください。お願いします。 ちなみに1行目にある「pseudo10.h」は先生が作ったプログラムだそうです。ほかに必要な情報があれば教えてください。 #include "pseudo10.h" typedef struct PERSON * PtrPERSON; struct PERSON{ char name[20]; //name long year; //age PtrPERSON next; //pointer }; int MakeLinkedList(PtrPERSON head){ PtrPERSON girl; New(PtrPERSON, girl) InputString(girl->name); InputInt(girl->year); while(girl->year > 0){ girl->next = head -> next; head->next = girl; New(PtrPERSON, girl); InputString(giel->name); InputInt(girl->year); } return 0; } int main(void){ PtrPERSON head; New(PtrPERSON, head); head->next = NULL; MakeLinkedList(head); WriteLinkedList(head); return 0; }}
- 締切済み
- 情報工学
- 連結リストについて
連結リストについて アルゴリズムの本を買って勉強しているのですが、わからない箇所がありまして。 構造体宣言で (1)struct CELL { struct CELL *next; int val; }; (2)struct CELL { struct CELL *next; int val; }*header; 順番をたどって行く書き方で struct CELL *p; for (p=header; p!=NULL; p=p->next) printf("%d\n", p->value); なぜこれでp->valueの値が変動していくのですか？ それと上記の(1)の書き方でこのforを回すとき、headerはどのように定義すればよいのですか？ よろしくお願いします。
- ベストアンサー
- C・C++・C#
- C言語 線形探索
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXBUFFERSIZE 256 struct LinkedListNode{ int data; struct LinkedListNode *next; }; struct LinkedList{ int node_num; struct LinkedListNode *head; }; LinkedList *LinkedListMake(char *filename) { FILE *fp; LinkedList *list; char buffer[MAXBUFFERSIZE]; /* ファイル有無のチェック */ if ((fp = fopen(filename, "r")) == NULL) { fprintf(stderr, "No Such File : %s\n", filename); exit (1); } list = LinkedListAlloc(); if (list == NULL) { /* 領域確保失敗 */ exit (0); /* 終了 */ } while (fgets(buffer, MAXBUFFERSIZE, fp)) { /* ファイル終端に到達するまでループ */ buffer[strlen(buffer) - 1] = '\0'; /* 改行文字を削除 */ LinkedListDataAdd(list, atoi(buffer)); } fclose(fp); return (list); } LinkedList *LinkedListAlloc(void) { LinkedList *list; list = (LinkedList *)malloc(sizeof(LinkedList)); if (list == NULL) { /* 領域確保失敗 */ return (NULL); } list->node_num = 0; list->head = NULL; return (list); } LinkedListNode *LinkedListDataAdd(LinkedList *list, int x) { LinkedListNode *ptr; /* 注目するノードへのポインタ */ LinkedListNode *prev; LinkedListNode *new_node; ptr = list->head; prev = NULL; while (ptr) { /* 終端ノードに到達するまでループ */ if (ptr->data < x) { prev = ptr; /* 直前ノードの更新 */ ptr = ptr->next; /* 注目ノードの更新 */ } else if (ptr->data == x) { /* x は登録済み */ return (NULL); } else { /* x を注目ノードの直前に追加 */ new_node = LinkedListNodeAlloc(); 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); } } /* 終端ノードに到達 */ /* x を終端に追加 */ new_node = LinkedListNodeAlloc(); if (new_node == NULL) { /* 領域確保失敗 */ exit (0); /* 終了 */ } new_node->data = x; new_node->next = NULL; /* new_node は新たな終端ノード */ if (prev != NULL) { /* list は少なくともひとつのノードを有している */ prev->next = new_node; /* 更新前の終端ノードの直後が new_node となる */ } else { /* list は空(ノードがひとつも含まれない) */ list->head = new_node; } list->node_num++; /* ノード総数の更新 */ return (new_node); } LinkedList *LinkedListSearch(LinkedList *list, int x)←ここがわかりません★ { for(i = 0; i < node_num) ？？？ int main(int argc, char *argv[]) { int a, i, x; printf("xの値を入力"); scanf("%d", &x); LinkedListMake(argv[1]); LinkedListSearch(list, x); 連結リストに格納されたint型データから目的の値を線形探索するプログラムをつくってます。 連結リスト作成関数まではできたので、あと連結リストにおいて目的の値を線形探索する関数LinkedListSearchをつくればだいたい完成だと思うのですが、関数LinkedListSearchの作り方がわかりません。 引数で連結リストのポインタと目的値をとって、目的値が存在すればそのノードのポインタ、存在しない場合はNULLを返すようにするつもりです。 わかる方、是非とも教えてください！ お願いいたします。
- ベストアンサー
- C・C++・C#
- (構造体)双方向連結リストの作成！
ダミーノードを先頭に、双方向連結リストを作成したいのですがなかなかうまくできません。とりあえず、ダミーノード無しのものはなんとか出来ましたが、循環連結がうまくいっていない次第です。 どうかお力添え願います。 #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; }
- ベストアンサー
- C・C++・C#
補足
p1というポインタを使ってたどっていくので、もっと複雑になりませんか？ 入れ替えを複数回行いたいので、 a1->next=a5; のように固定して書けません・・・