(循環)リストを逆順で表示したい

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら　　※コードを貼り付ける場合は [code] と [/code] で囲って下さい。詳しくはこちら

トピックに返信する


答えを正確にご入力ください。答えられるかどうかでスパムボットか否かを判定します。
BBCode: ON
[img]: ON
[flash]: OFF
[url]: ON
スマイリー: OFF
トピックのレビュー
   

展開ビュー トピックのレビュー: (循環)リストを逆順で表示したい

Re: (循環)リストを逆順で表示したい

#3

by mrte » 5年前

丁寧な回答ありがとうございます。
無事理解することができました、またただ動くだけでなく計算量やメモリの使用量を考えることの重要性を感じました。

Re: (循環)リストを逆順で表示したい

#2

by かずま » 5年前

main や const はそのままで、print_int_list だけを変更するなら、

O(n2)の時間がかかるやり方は、

コード: 

void print_int_list(list l) {
	for (list head = l->next, p = head; ; p = l) {
		l = p;
		while ((l = l->next)->next != p) ;
		printf("[%d]", l->element);
		if (l == head) break;
	}
    printf("\n");
}
時間は O(n) だけど、O(n) のメモリを余計に必要とするやり方は、

コード: 

void print(list p, list l) {
	if (p != l) print(p->next, l);
	printf("[%d]", p->element);
}

void print_int_list(list l) {
	print(l->next, l);
	printf("\n");
}
循環リストを逆順に繋ぎ変えることで、余計なメモリを使わず、
時間も O(n) で済むやり方

コード: 

void print_int_list(list l) {
	list head = l->next, p = head, q = l, next;
	while (1) {
		next = p->next, p->next = q, q = p;
		if (p == l) break;
		p = next;
	}
	while (1) {
		printf("[%d]", q->element);
		if (q == head) break;
		q = q->next;
	}
	printf("\n");
	while (1) {
		next = p->next, p->next = q, q = p;
		if (p == head) break;
		p = next;
	}
}
以上すべて無限に出力するのはやめています。
また、循環リストには最低 1個のデータがあるものとします。

質問に回答したので、理解できたかどうかの返信を必ずお願いします。

(循環)リストを逆順で表示したい

#1

by mrte » 5年前

単方向循環リストを実装し、その内容を表示するものを作成して、その表示順番を逆順にしたいのですが方法が分からないので教えて欲しいです。

コード: 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef int elementtype;
struct node{
    elementtype element;
    struct node *next;
};
typedef struct node* list;

list cons(elementtype e, list l){//リストlの先頭にeを追加したリストを返す
    list n = (struct node *)malloc(sizeof(struct node *));
    n->element = e;
    n->next = l;
    return n;
}

void print_int_list(list l){//リストlに含まれる要素を先頭から出力
    while(l != NULL){printf("[%d]",l->element);l = l->next;}
    printf("\n");
}

int main(){
    int i;
    char buf[128];
    list l = NULL;
    list head;
    while(fgets(buf,sizeof(buf),stdin) != NULL){
        sscanf(buf,"%d",&i);
        l = cons(i, l);
    }
    head = l;
    while(l->next != NULL){//リストを循環リストにする
        l = l->next;
    }
    l->next = head;     
    print_int_list(l);
    return 0;
}
【入力】
1
2
3
4
5
【出力(現在)】
[1][5][4][3][2][1][5][4][3][2][1]......
【出力(理想)】
[1][2][3][4][5][1][2][3][4][5].....

ページトップ