構造体
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;
}
構造体を用いたポインタのランダムソート
Re: 構造体を用いたポインタのランダムソート
ソースコードはよく読んでいませんが、上の文を読むと「昇順降順するプログラム」は既にあるんですよね。苦C さんが書きました:昇順降順するプログラムは以下のようになっていてこれを改良して作成したいと思っています。
何をやりたいんですか?
フォーラムルールをご一読ください。インデントされていないコードは詳細に読む気がしません。
なお、構造体のメンバにnext,prev があるということは双方向リストだと思いますが、google君で「双方向リストのソート」で検索するといくつか例が出てきます。
それらを参考にするのはどうでしょうか。
私は「リストのソート」が必要ならstd::list::sort()を使用します(c++ですが...)。
Re: 構造体を用いたポインタのランダムソート
そのプログラムは、苦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;
}
もっと簡潔なコードが書けるんですが。
Re: 構造体を用いたポインタのランダムソート
挿入ソートですね。かずま さんが書きました:改良したものは
求めているものと異なるかもしれませんが、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;
}
乱数のシードを毎回変更すると、デバッグがやりにくいし、結果が毎回変わってしまうのでアルゴリズムの検証には不向きです。
固定化することをお勧めします。
ゲーム等で本当に乱数が必要な場合は別ですが...
Re: 構造体を用いたポインタのランダムソート
かずま さんが書きました:ダミーの 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;
}
Re: 構造体を用いたポインタのランダムソート
かずまさんご回答ありがとうございます・・・!
環状リストというものは初めて聞いたためよく理解できなかったですが、改良していただいたプログラムは大まかには理解できました!
疑問点がありまして、35行目の for (point = start; point; point = point->next)
の部分のpoint;のみ書かれている条件は何のために存在しているのでしょうか??
環状リストというものは初めて聞いたためよく理解できなかったですが、改良していただいたプログラムは大まかには理解できました!
疑問点がありまして、35行目の for (point = start; point; point = point->next)
の部分のpoint;のみ書かれている条件は何のために存在しているのでしょうか??
Re: 構造体を用いたポインタのランダムソート
for (point = start; point; point = point->next)苦C さんが書きました:疑問点がありまして、35行目の for (point = start; point; point = point->next)
の部分のpoint;のみ書かれている条件は何のために存在しているのでしょうか??
は
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」を実行するので、同じです。