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

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

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

#1

投稿記事 by mrte » 6日前

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

コード:

#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].....

かずま

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

#2

投稿記事 by かずま » 6日前

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個のデータがあるものとします。

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

mrte

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

#3

投稿記事 by mrte » 5日前

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

返信

“C言語何でも質問掲示板” へ戻る