常連

注目の的

社会貢献

回答者

拍手喝采

自己紹介

有名人

### パンケーキ問題のアルゴリズム

3,7,5,6,2,4,8,1　を昇順に並べ替える．
条件　先頭の部分列を逆さにする操作しか使わないこと．
例えば，1回目は 最大値8であるため3から8を入れ替える　　　　8,4,2,6,5,7,3,1 
 　　　その次に　全体を入れ替える　　　　　　　      　　　1,3,7,5,6,2,4,8
       2回目は　次の最大値7であるから1から7を入れ替える．　7,3,1,5,6,2,4,8
       その次に　全体を入れ替える　　　　　　　　　　　　　4,2,6,5,1,3,7,8
　　　　
これを繰り返していくプログラムを考えているのですが，うまく出力されません
 どなたかわかりますでしょうか．



/#include <stdio.h>
/#include <stdlib.h>

void swap(int a,int b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
	return;
}


void print_array(int *list,int length){
        for(int i=0;i<length;i++)
                printf("%d ",list[i]);
        printf("\n");
}

//回転
void do_flip(int *list,int length,int num){
        for(int i=0;i<--num;i++)
                swap(list[i],list[num]);
}

//パンケーキ食べたい
int pancake_sort(int *list,unsigned int length){
        if(length<2)
                return 0;
        int i,j;
        int max_num_pos;
        int moves=0;//ソート回数
        for(i=length;i>1;i--){
                max_num_pos=0;
                for(j=0;j<i;j++){
                        if(list[j]>list[max_num_pos])
                                max_num_pos=j;
                }
                if(max_num_pos==i-1)
                        continue;
                if(max_num_pos){
                        moves++;
                        do_flip(list,length,max_num_pos+1);
                }
                moves++;
                do_flip(list,length,i);
        }
        return moves;
}



int main(int argc, char **argv){

       // 初期値
        int moves[7];
        int list[7]={3,7,5,6,2,4,8,1};


        printf("Before\n");
        print_array(list,8);

        moves[7] = pancake_sort(list,8);

        printf("After\n");
        print_array(list,8);
}

出力
Before
3 7 5 6 2 4 8 0 8 
After
3 7 5 6 2 4 8 0 8

パンケーキ問題のアルゴリズム

### 前提・実現したいこと
※初投稿です。不手際がありましたら申し訳ございません。
①2つの文字列(char *a,char *b)に対して、辞書順を判定する関数int hantei(char *a,char *b)を作成せよ。この関数の戻り値として、aがbより前(辞書順で)にくる場合は1、aとbが同じ文字列の場合は0、それ以外の場合は-1とする。
②バブルソートを用いて文字列配列(char ＊＊argv)を辞書順に並び替える関数void sort(char ＊＊argv,int n)を作成せよ。また、引数nは文字列の個数を表し、①のhantei関数を用いること。
バブルソートの参考として以下のコードが書いてありました。
```C
void bubble(int list[],int n)
{
	int i,t;
	
	for(n=n-1;n>=0;n--){
		for(i=0;i<n;i++){
			if(list[i]>list[i+1]){
				t=list[i];
				list[i]=list[i+1];
				list[i+1]=t;
			}
		}
	}
}
 
```
### 発生している問題・エラーメッセージ
①については自力でコードをかけました。(一度間違えましたが)
```C
#include<stdio.h>

#define N 100

int hantei(char *a,char *b);

int main(void)
{
	int ans;
	char a[N],b[N];
	
	printf("辞書順を判定するぞー！\n");
	printf("文字列aを入力してくれ。");
	gets(a);
	printf("文字列bを入力してくれ。");
	gets(b);
	
	ans=comp_d(a,b);
	if(ans==1){
		printf("aの文字列の方が前だぞ。\n");
	}
	else if(ans==0){
		printf("aとbは同じ文字列だぞ。\n");
	}
	else if(ans==-1){
		printf("bの方が前だぞ。\n");
	}
	
	return 0;
}

int hantei(char *a,char *b)
{   
	int i;
	for ( i = 0; *(a+i) != '\0' && *(b+i) != '\0'; i++ ) {
		if(*(a+i)<*(b+i)){
			return 1;
		}
		if(*(a+i)>*(b+i)){
			return -1;
		}
	}
	if(*(a+i)!='\0'){
		return 1;
	}
	if(*(b+i)!='\0'){
		return -1;
	}
	return 0;
}


```
②についてが、正直に言うとほとんどわかりませんでしたが、回答者の皆様のおかげですこしずつイメージ自体はつかめるようになってきました。そこで、コードを書いてみましたがいくつかエラーが出てしまいました。
具体的な書き方がつかめておらず、何点か不明な点があります。

〇わからないこと

　・//str=(char *)malloc(sizeof(char)*n);では、エラーがでなかったがその直下にあるようにfor文でループさせるとエラーがでます。なぜでしょうか？また、このnは文字列の個数(何個の文字列を入力するか)なのですが、本来は1つ1つの文字列の長さ(文字が何個あるか)を入れるべきなのですが、文字列の長さを計算するにはまず文字列を入力しなければならないわけで、？？となっております。
　・sort関数内で、tはint型で宣言されています。ここに代入するには文字列の先頭アドレスを代入すればいい、という認識であっているのでしょうか？(問題には参考としてバブルソートが書かれているだけなので無理して合わせる必要はない、とは思いますが)

〇わかったこと
　・//str=(char *)malloc(sizeof(char)*n);の意味
char型のサイズ(1バイト)×n(ここでは文字列の個数(何個の文字列を入力するか)ですが)分のメモリをmalloc関数で確保し、それを(char *)に明示的に変換している。(左辺のポインタ変数strにあわせている?)
　・関数sortの引数にポインタのポインタ(アドレス)があるが、そこにはポインタ変数のアドレスを渡せばよい。
　・参考として↑にあるバブルソートには文字列がint型に入っているが、そこにはポインタのアドレスを渡せばよい。
```C
#include<stdio.h>
#include<stdlib.h>

int hantei(char *a, char *b);
void sort(char **argv,int n);

int main(void)
{
	char *str;
	char enter;
	int i,n;
	
	printf("複数の文字列配列を辞書順に並び替えるぞ\n");
	printf("文字列の個数入力して→");
	scanf("%d",&n);
	
	enter=getchar();
	
	//str=(char *)malloc(sizeof(char)*n);		//下記にて説明有り	
	for(i=0;i<n;i++){
		(str+i)=(char *)malloc(sizeof(char)*n);		//「左辺値が必要」とエラーがでます
	}
	
	for(i=0;i<n;i++){
		printf("%dつ目の文字列を入力しよ> ",i+1);
		scanf("%s",str+i);
	}
	
	sort(&str,n);
	
	for(i=0;i<n;i++){
		printf("辞書順に文字列を出力します。\n");
		printf("%s\n",str+i);
	}

	return 0;
}

void sort(char **argv,int n)
{
	int i,j,t;
	
	if(n==1){
		printf("データ1個しかないですよ\n");
	}
	else{
		for(i=n-1;i>=0;i--){		//「char *型はint型に変換できない」とエラーが出ます。
			for(j=0;j<n;j++){
				if(hantei(*(argv+j),*(argv+j+1))==-1){
					t=*(argv+j);
					*(argv+j)=*(argv+j+1);
					*(argv+j+1)=t;
				}
			}
		}
	}
}

int hantei(char *a,char *b)
{
	int i;
	
	for(i=0;*(a+i)!='\0' && *(b+i)!='\0';i++){
		if(*(a+i)<*(b+i)){
			return 1;
		}
		else if(*(a+i)>*(b+i)){
			return -1;
		}
	}
	if(*(a+i)!='\0'){
		return -1;
	}
	else if(*(b+i)!='\0'){
		return 1;
	}
	return 0;
}
```

### 試したこと

まずポインタのポインタ(ダブルポインタ)のイメージがわかなかったため以下のようなコードを拾ってて、どのような動きをしているのか自分で図を描いて理解しました。(以下参照)
```C
#include<stdio.h>

#define N 50

int main(void)
{
	//普通のポインタ
	int t;
	char *str1,*str2,*str3;
	char fig[]="abcdefghijk";
	
	str1=fig;
	printf("%c\n",*str1);			//文字の出力
	
	str2=fig;
	for(t=0;*(str2+t)!='\0';t++){
		printf("%c",*(str2+t));		//文字列の出力
	}
	printf("\n");
	
	str3=fig;
	printf("%s\n",fig);		//文字列の出力
	 
	//ダブルポインタの理解1
	char *figure1,**figure2;
	char buf1[N]="あいうえお";
	char buf2[N]="かきくけこ";
	
	figure1=buf1;
	figure2=&figure1;
	*figure2=buf2;
	
	printf("%s\n",figure1);
	
	//ダブルポインタの理解2
	char *month[3]={"January","February","March"};
	char **p1,**p2,**p3;
	int i,j;
	
	p1=month;
	p2=month;
	p3=month;
	
	for(i=0;i<3;i++){
		printf("%s\n",*(p1+i));
	}
	
	for(i=0;i<3;i++){
		printf("%s\n",*p2);
		p2++;
	}
}
```
![![イメージ説明](ab2772d16cb4b30402644276537476e2.png)
↑上のプログラム内の　//ダブルポインタの理解1　の図解

他にも様々なサイトを見ましたが、よくわからず
　・配列だと要素数を宣言しないといけないが、ポインタのポインタとmalloc関数を使えばメモリを余分に使うことなく処理できる。
ということくらいしかわかりませんでした。
また、普通のポインタについてはアドレスなど、動きが理解しやすいのですがポインタのポインタについてはどのような考えをしながらコードを追っていけばいいのかがわかりません。

未熟者ですがどうかご指導よろしくお願いします。
### 補足情報（FW/ツールのバージョンなど）

使用しているツールは、BCC Developerで、コンパイラはBorland C++ Compilerを使用しています。

ポインタのポインタがよくイメージできない

qsortに関する演習問題の解答で、以下のようなコードがあります。

```C
/*--- xおよびyが指す文字列の比較関数 ---*/
static int pstrcmp(const void *x, const void *y)
{
	return strcmp(*(const char **)x, *(const char **)y);
}

/*--- 文字列を指すポインタの配列pを昇順にソート ---*/
void sort_pvstr(char *p[], int n)
{
	qsort(p, n, sizeof(char *), pstrcmp);
}
```

ここの、
```C
(*(const char **)x, *(const char **)y)
```
の意味がわかりません。

char * → 文字列
char ** → 文字列を格納したアドレス
というのはわかりますが、その後どのように式を解釈したらいいかわかりません。

よろしくお願いします。

char **を含む式の意味がわからない

大学の講義でmalloc関数を学習したのですが，いまいち使い方がわからないため，どこを理解できていないのかを確認したいです．

まず，以下の「修正前のコード」では，char型のポインタaと，文字列b="cd"を用意しています．

その下で，malloc関数等を利用して，char型のアドレスをポインタaに代入しています．

aはポインタなので，*a=" ~ "として，ポインタaの示す変数*aに文字列を代入しています．

その後，*aの値の中にbの値が入っているかを調べて，その値のアドレスをポインタpに格納しています．

最後に，ポインタpが示す文字列を出力しています．


という流れでテストコードを作成したのですが，エラーがでてしまいます．

一応，下の修正後のコードでコンパイルした場合は，うまく動きました．
しかし，なぜaはポインタであるはずなのに，文字列を格納できたのか，という点が疑問です．
おそらく，何か根本的に勘違いをしていると思うので，正しい理解へ導いてほしいです．

```C
// 修正前のコード
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char *a;
    char b[10] = "cd";

    a = (char*)malloc(sizeof(char));
    *a = "abcdefgh";
    char *p;

    p = strstr(*a, b);

    printf("%s", *p);

    return 0;
}
```

```C
// 修正後のコード
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(void) {
    char *a;
    char b[10] = "cd";

    a = (char*)malloc(sizeof(char));
    // *a → a   文字列は*aに格納するのではないのか？
    a = "abcdefgh";
    char *p;

    // *a → a
    p = strstr(a, b);

    // *p → p
    printf("%s", p);

    return 0;
}
```