【掲示板ご利用上の注意】

 ※題名は具体的に!
 ※学校の課題の丸投げ禁止!
 ※ソースの添付は「HTML変換ツール」で字下げ!
 ※返信の引用は最小限に!
 ※環境(OSとコンパイラ)や症状は具体的に詳しく!
 ※返信付き投稿の削除は禁止!
 ※マルチポスト(多重投稿)は慎んで!

 詳しくはこちら


本当はこんなに大きく書きたくはないのですが、なかなか守っていただけなくて…。
 守ってくださいね。お願いします。(by管理人)

C言語ソース⇒HTML形式ツール掲示板2こちら


管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧

No.21330

連結リストの入れ替え
投稿者---加奈子(2005/06/11 00:55:25)


1.連結リストにランダムに数字をいれる。
2.そしてリストの中の数字を小さい順にリストに入れなおす。

例:ランダムに 2,39,21,78,10,22,0,1,8,31
それを   0,1,2,8,10,21,22,31,39,78
のように入れなおしたいのですが方針が全然わかりません。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

typedef struct node{
  int item;
  struct node *next;
}*LIST;

void initialize(LIST *p);
LIST add_to_list(LIST p,int element);
void print_list(LIST p);
void sort_list(LIST p);

int main(){

  int x,i=0;
  LIST p;

  initialize(&p);
  srand((unsigned int) time(NULL));
  x=rand()%100;

  while(i<10){
    p=add_to_list(p,x);
    i++;
    x=rand()%100;
  }

  sort_list(p);

  print_list(p);
  putchar('\n');
  return(0);
}

void initialize(LIST *p){
  *p=NULL;
}

LIST add_to_list(LIST p,int element){
  LIST q;

  q=(LIST)malloc(sizeof(struct node));

  q->item=element;
  q->next=p;

  p=q;
  return(p);
}

void print_list(LIST p){

  while(p!=NULL){
    printf("%d ",p->item);
    p=p->next;
  }
}

void sort_list(LIST p){

ここが全然わかりません。


}




この投稿にコメントする

削除パスワード

発言に関する情報 題名 投稿番号 投稿者名 投稿日時
<子記事> Re:連結リストの入れ替え 21331 Blue 2005/06/11 01:06:13
<子記事> Re:連結リストの入れ替え 21341 まきじ 2005/06/11 13:36:54


No.21331

Re:連結リストの入れ替え
投稿者---Blue(2005/06/11 01:06:13)


とりあえず、掲示板ご利用上の注意は読みましょう。
(※環境(OSとコンパイラ)や症状は具体的に詳しく!が守られてません)

過去ログ検索してみたらそれぽいのがありました。
リストのバブルソートについて
参考にどうぞ。



この投稿にコメントする

削除パスワード

No.21332

Re:連結リストの入れ替え
投稿者---加奈子(2005/06/11 01:37:58)


ごめんなさい。
OSは windows XP
コンパイラは gccです。

お願いします。


この投稿にコメントする

削除パスワード

No.21334

Re:連結リストの入れ替え
投稿者---si(2005/06/11 03:25:46)


下記は、もっとも単純な方法です。
rootとすべてを比較、小さければ入れ替えていく。
次にroot->nextと同様に比較、これを繰り返す。比較回数は (n-1)! ?
データ数が少なければ問題にはなりませんが、多くなると非常に時間がかかります。
ソートに関しては、いろんなところにサンプルがありますので検索して下さい。
また、皆が知ってるもの以外に新しいソート法が見つかるかも知れません。
void sort_list(LIST p){
	LIST q;
	int i;
	while (p != NULL) {
		q = p->next;
		while (q != NULL){
			if (p->item > q->item) { /* swap */
				i = p->item;
				p->item = q->item;
				q->item = i;
			}
			q = q->next;
		}
		p = p->next;
	}
}



この投稿にコメントする

削除パスワード

No.21372

Re:連結リストの入れ替え
投稿者---かずま(2005/06/13 08:58:18)


> rootとすべてを比較、小さければ入れ替えていく。
> 次にroot->nextと同様に比較、これを繰り返す。比較回数は (n-1)! ?
n-1
k = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2
k=1
計算量は、O(n2)です。


この投稿にコメントする

削除パスワード

No.21376

Re:連結リストの入れ替え
投稿者---si(2005/06/13 14:36:29)


>> rootとすべてを比較、小さければ入れ替えていく。
>> 次にroot->nextと同様に比較、これを繰り返す。比較回数は (n-1)! ?
>n-1
>k = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2
>k=1
>計算量は、O(n2)です。

かずま さん <−−−− エクセレント!


この投稿にコメントする

削除パスワード

No.21341

Re:連結リストの入れ替え
投稿者---まきじ(2005/06/11 13:36:54)


>1.連結リストにランダムに数字をいれる。
>2.そしてリストの中の数字を小さい順にリストに入れなおす。
>
>例:ランダムに 2,39,21,78,10,22,0,1,8,31
> それを   0,1,2,8,10,21,22,31,39,78
>のように入れなおしたいのですが方針が全然わかりません。

ソート以前に、連結リストもできていない様ですが?
ソースをコンパイルしてみると、コンパイルエラーでますし。


この投稿にコメントする

削除パスワード

No.21349

Re:連結リストの入れ替え
投稿者---かずま(2005/06/11 22:34:25)


> ソート以前に、連結リストもできていない様ですが?
> ソースをコンパイルしてみると、コンパイルエラーでますし。

どんなエラーが出ますか?
sort_list() の中の「ここが全然わかりません。」をそのままにしていませんか?
これを削除すると、連結リストはできていますよ。


この投稿にコメントする

削除パスワード

No.21350

Re:連結リストの入れ替え
投稿者---まきじ(2005/06/11 23:09:18)


>sort_list() の中の「ここが全然わかりません。」をそのままにしていませんか?
>これを削除すると、連結リストはできていますよ。

すいません。私の勘違いです(^^;


この投稿にコメントする

削除パスワード

管理者用メニュー    ツリーに戻る    携帯用URL    ホームページ    ログ    タグ一覧