構造体を用いたポインタのランダムソート

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

構造体を用いたポインタのランダムソート

#1

投稿記事 by 苦C » 6年前

構造体
struct data{
int value;
struct data *next//次の構造体へのアドレス
struct data *prev//前の構造体へのアドレス

上記の構造体を用いてvalueにランダムに1~100までの数字を与えることを10回行い、それぞれの構造体のvalueを比較して昇順、降順で並び替えて表示させるプログラムを考えたいのですがわかりません。

valueに0~9までそ昇順に代入していき、昇順降順するプログラムは以下のようになっていてこれを改良して作成したいと思っています。

どなたかお力を貸していただけるとありがたいです。
以下プログラム
=====================
#include <stdio.h>
#include <stdlib.h>

struct data{
int value;
struct data *next;
struct data *prev;
};

int main(){
struct data *start;
struct data *now;
struct data *point;
struct data *old;
struct data *x;
struct data *head;
struct data *end;

int i,j;

for(i=0;i<9;i++){
now=(struct data*)malloc(sizeof(struct data));
if(now==NULL){
for(j=i;i>0;j--){
head = start;
old=start;
head=head->next;
x=old->next;
free(old);
}
return -1;
}
now->next=NULL;
now->value=i;

if(i==0){
start=now;
}
else if(i>0){
point->next=now;
now->prev=point;
}

point=now;
}
end=point;

for (i=0;i<9;i++){
printf("%d %d\n",start->value,end->value);
start=start->next;
end=end->prev;
}

free(now);

return 0;
}

maru
記事: 150
登録日時: 13年前

Re: 構造体を用いたポインタのランダムソート

#2

投稿記事 by maru » 6年前

苦C さんが書きました:昇順降順するプログラムは以下のようになっていてこれを改良して作成したいと思っています。
ソースコードはよく読んでいませんが、上の文を読むと「昇順降順するプログラム」は既にあるんですよね。
何をやりたいんですか?

フォーラムルールをご一読ください。インデントされていないコードは詳細に読む気がしません。

なお、構造体のメンバにnext,prev があるということは双方向リストだと思いますが、google君で「双方向リストのソート」で検索するといくつか例が出てきます。
それらを参考にするのはどうでしょうか。

私は「リストのソート」が必要ならstd::list::sort()を使用します(c++ですが...)。

かずま

Re: 構造体を用いたポインタのランダムソート

#3

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

苦C さんが書きました:valueに0~9までそ昇順に代入していき、昇順降順するプログラムは以下のようになっていてこれを改良して作成したいと思っています。
そのプログラムは、
value に 0~8 を昇順に代入していき、昇順と降順で表示するものです。
また、最後に data を一つしか free していません。

改良したものは

コード:

#include <stdio.h>   // printf
#include <stdlib.h>  // malloc, free, rand, srand
#include <time.h>    // time

#define NUM_DATA   10
#define MAX_VALUE 100

struct data {
    int value;
    struct data *next;
    struct data *prev;
};

int main(void)
{
    struct data *start;
    struct data *now; 
    struct data *point;
    struct data *end;
    int i, j = 0;

    srand(time(0));
    for (i = 0; i < NUM_DATA; i++) {
        now = (struct data*)malloc(sizeof(struct data));
        if (now == NULL) {
            j = 1;
            goto release;
        }
        now->prev = NULL;
        now->next = NULL;
        now->value = rand() % MAX_VALUE + 1;
        if (i == 0)
            start = end = now;
        else {
            for (point = start; point; point = point->next)
                if (point->value >= now->value) break;
            if (point == NULL) {
                now->prev = end;
                end->next = now;
                end = now;
            }
            else if (point == start) {
                now->next = start;
                start->prev = now;
                start = now;
            }
            else {
                now->prev = point->prev;
                now->next = point;
                point->prev->next = now;
                point->prev = now;
            }
        }
    }
    for (point = start; point; point = point->next) {
        printf("%3d %3d\n", point->value, end->value);
        end = end->prev;
    }
release:
    for (point = start; point; ) {
        now = point->next;
        free(point);
        point = now;
    }
    return j;
}
ダミーの data を用意し、環状リストにすると、
もっと簡潔なコードが書けるんですが。

maru
記事: 150
登録日時: 13年前

Re: 構造体を用いたポインタのランダムソート

#4

投稿記事 by maru » 6年前

かずま さんが書きました:改良したものは
挿入ソートですね。

求めているものと異なるかもしれませんが、c++ による実装です。

コード:

#include <cstdio>
#include <iostream>
#include <list>
const size_t numberOfData = 10;
const int maxNumber = 100;
template <typename T> void print(T t)
{	for (T::const_iterator it = t.begin(); it != t.end(); ++it)
	{	std::cout << *it << std::ends;
	}
	std::cout << std::endl;
}

int main()
{
	std::list<int>	value_list;
	// 乱数データをリストに挿入
	for (int i = 0; i < numberOfData; ++i)
	{	value_list.push_back((rand() % maxNumber) + 1);
	}
	print(value_list);	// ソート前データの出力
	value_list.sort();	// 昇順でソート
	print(value_list);	// ソート後データの出力
	value_list.sort([](int x, int y) {return x > y; });	// 降順でソート
	print(value_list);	// ソート後データの出力

	return 0;
}
かずま さんが書きました:

コード:

srand(time(0));
乱数のシードを毎回変更すると、デバッグがやりにくいし、結果が毎回変わってしまうのでアルゴリズムの検証には不向きです。
固定化することをお勧めします。
ゲーム等で本当に乱数が必要な場合は別ですが...

かずま

Re: 構造体を用いたポインタのランダムソート

#5

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

かずま さんが書きました:ダミーの data を用意し、環状リストにすると、
もっと簡潔なコードが書けるんですが。

コード:

#include <stdio.h>   // printf
#include <stdlib.h>  // malloc, free, rand, srand
#include <time.h>    // time
 
#define NUM_DATA   10
#define MAX_VALUE 100
 
struct data {
    int value;
    struct data *next;
    struct data *prev;
};
 
int main(void)
{
    struct data data;  // dummy cell
    struct data *p, *q; 
    int i, j = 0;
 
    srand(time(0));
    data.next = data.prev = &data;
    for (i = 0; i < NUM_DATA; i++) {
        p = (struct data*)malloc(sizeof(struct data));
        if (p == NULL) { j = 1; goto release; }
        p->value = rand() % MAX_VALUE + 1;
        for (q = data.next; q != &data; q = q->next)
            if (q->value >= p->value) break;
        p->prev = q->prev;
        p->next = q;
        q->prev->next = p;
        q->prev = p;
    }
    for (p = data.next, q = data.prev; p != &data; p = p->next, q = q->prev)
        printf("%3d %3d\n", p->value, q->value);

release:
    for (p = data.next; p != &data; p = q) {
        q = p->next;
        free(p);
    }
    return j;
}


苦C

Re: 構造体を用いたポインタのランダムソート

#6

投稿記事 by 苦C » 6年前

かずまさんご回答ありがとうございます・・・!

環状リストというものは初めて聞いたためよく理解できなかったですが、改良していただいたプログラムは大まかには理解できました!
疑問点がありまして、35行目の for (point = start; point; point = point->next)
の部分のpoint;のみ書かれている条件は何のために存在しているのでしょうか??

かずま

Re: 構造体を用いたポインタのランダムソート

#7

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

苦C さんが書きました:疑問点がありまして、35行目の for (point = start; point; point = point->next)
の部分のpoint;のみ書かれている条件は何のために存在しているのでしょうか??
for (point = start; point; point = point->next)

for (point = start; point != NULL; point = point->next)
と同じ意味です。

「for (式1; 式2; 式3) 文」という for文は、
「式2」が 0 でない間、「文」と「式3」を実行します。

(1) 式2 が「point != NULL」のとき、
  point が NULL でないなら、演算子 != の実行結果は 1 です。
  point が NULL なら、演算子 != の実行結果は 0 です。

(2) 式2 が point のとき、
  point が NULL でないなら、それは「0 ではない」ということです。
  point が NULL なら、それは「0 である」ということです。

(1) でも (2) でも
  point が NULL でない間、「文」と「式3」を実行するので、同じです。

苦C

Re: 構造体を用いたポインタのランダムソート

#8

投稿記事 by 苦C » 6年前

かずまさんありがとうございました!!
完全に理解することができました!!

返信

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