C言語関係掲示板

過去ログ

No697 リストを使用した簡易文字列辞書の作成

[戻る] [ホームページ]
No.8198

どなたか助けてください
投稿者---悩める大学生(2003/07/10 00:25:29)


授業の課題で、
「文字列を節点の項目として持つリストを用いて、次のようなコマンドを持つ辞書システムを作りなさい。
・辞書に単語を登録するコマンド"Insert"
・辞書から単語を削除するコマンド"Delete"
・ある単語が辞書の中にあるかどうかを判定するコマンド"Lookup"
・辞書の中に登録されているすべての単語をプリントするコマンド"Print"
文字列の比較には標準関数"strcmp"を用いなさい。

という課題が出されました。ヒントとなるソースプログラムをもとに作ってみたのですが、文字列ではなく数字(int型)の辞書になってしまいました。
 他教科のテスト勉強の時間がどんどん削られてしまい、本当に焦っています。
 どなたかよろしければ教えてください。お願いします。


No.8199

Re:どなたか助けてください
投稿者---悩める大学生(2003/07/10 00:38:23)


ちなみに、数字版は次のようなソースプログラムです。
ここから、どの様にすればよいのかさっぱり分かりません。
#include<stdio.h>

struct node
{
int key;
struct node *next;
};

struct node *head,*tail;

void listinitialize(void)
{
head=(struct node *) malloc(sizeof(*head));
tail=(struct node *) malloc(sizeof(*tail));
head->next=tail;
tail->next=NULL;
};

struct node *insertafter(int v,struct node *p)
{
struct node *x;

x=(struct node *) malloc(sizeof(*x));
x->key=v;
x->next=p->next;
p->next=x;
return x;
};

void deletenext(struct node *p)
{
struct node *x;
x=p->next;
p->next=p->next->next;
free(x);
};

struct node *searchnode(int v)
{
struct node *x;

x=head;
while(x->next->next!=NULL)
{
if(x->next->key==v) break;
x=x->next;
};
return x;
};

int main(void)
{
struct node *x;
char com;
int n;

listinitialize();

printf("please choose number\n");
printf("(1)Insert, (2) Delete, (3) Lookup, (4)Print,(0) End ?");

scanf(" %c",&com);
while(com!='0')
{
switch(com)
{
case '1':
printf("Word?");
scanf("%d",&n);
insertafter(n,head);
printf("input OK!\n");
break;

case '2':
printf("Word?");
scanf("%d",&n);
x=searchnode(n);
if(x->next->next!=NULL) deletenext(x);
printf("delete OK!\n");
break;

case '3':
printf("Word?");
scanf("%d",&n);
x=searchnode(n);
if(x->next->next!=NULL)
printf("%d is in the dictionary.\n",n);
else
printf("%d is NOT in the dictionary.\n",n);
break;

case '4':
x=head->next;
while(x->next!=NULL)
{printf("%d",x->key);
x=x->next;
};
printf("\n");
break;
};
printf("(1)Insert,(2)Delete,(3)Look up,(4)Print,(0)End");
scanf(" %c",&com);
};
return 0;
}
(END)


No.8202

リストを使用した簡易文字列辞書の作成 (Was: Re:どなたか助けてください)
投稿者---YuO(2003/07/10 02:14:31)


題名が不正です。
題名とは内容の要約を書くものですよ。


>ちなみに、数字版は次のようなソースプログラムです。
>ここから、どの様にすればよいのかさっぱり分かりません。

まず,keyの型をintから文字列用の型にする必要があります。
a.) char * key;
mallocで文字列用のメモリを確保する。
+メモリの無駄が少ない
+長い文字列に対応できる
−プログラムが複雑になる
b.) char key[N + 1];
固定長でN文字分のメモリを最初からとっておく。
+プログラムが簡単になる
−メモリの無駄が大きい
−N文字を越える文字列を扱えない

次に,比較を数値の比較から文字列の比較に変更する必要があります。
#これは出題時にヒントが出ているようなので割愛します。

あとは,入力が数値だったり出力が数値だったりする部分をすべて文字列に変更すればよいです。


とりあえず,preで囲ったソースを貼り付けておきます。
次回からはちゃんとpreで囲ってください。
#include<stdio.h>

struct node
{
  int key;
  struct node *next;
};

struct node *head,*tail;

void listinitialize(void)
{
  head=(struct node *) malloc(sizeof(*head));
  tail=(struct node *) malloc(sizeof(*tail));
  head->next=tail;
  tail->next=NULL;
};

struct node *insertafter(int v,struct node *p)
{
  struct node *x;

  x=(struct node *) malloc(sizeof(*x));
  x->key=v;
  x->next=p->next;
  p->next=x;
  return x;
};

void deletenext(struct node *p)
{
  struct node *x;
  x=p->next;
  p->next=p->next->next;
  free(x);
};

struct node *searchnode(int v)
{
  struct node *x;

  x=head;
  while(x->next->next!=NULL)
    {
      if(x->next->key==v) break;
      x=x->next;
    };
  return x;
};

int main(void)
{
  struct node *x;
  char com;
  int n;

  listinitialize();

  printf("please choose number\n");
  printf("(1)Insert, (2) Delete, (3) Lookup, (4)Print,(0) End ?");

  scanf(" %c",&com);
  while(com!='0')
    {
      switch(com)
        {
        case '1':
          printf("Word?");
          scanf("%d",&n);
          insertafter(n,head);
          printf("input OK!\n");
          break;

        case '2':
          printf("Word?");
          scanf("%d",&n);
          x=searchnode(n);
          if(x->next->next!=NULL) deletenext(x);
          printf("delete OK!\n");
          break;

        case '3':
          printf("Word?");
          scanf("%d",&n);
          x=searchnode(n);
          if(x->next->next!=NULL)
            printf("%d is in the dictionary.\n",n);
          else
            printf("%d is NOT in the dictionary.\n",n);
          break;

        case '4':
          x=head->next;
          while(x->next!=NULL)
            {printf("%d",x->key);
            x=x->next;
            };
          printf("\n");
          break;
        };
      printf("(1)Insert,(2)Delete,(3)Look up,(4)Print,(0)End");
      scanf(" %c",&com);
    };
  return 0;
}




No.8248

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/10 19:00:03)


さっそくのアドバイスとご注意ありがとうございました。以後、気をつけます。
アドバイスの通り、それぞれの部分を変更してみたのですが、やはり正常に動きません。まだまだ初心者なので、どこが間違っているのか見当がつきません。自己参照構造体と初期化までのプログラムを以下に貼り付けておくので、具体的に指摘していただければと思います。

#include<stdio.h>
#include<string.h>

struct node
{
const int i=11;
char key[i];
struct node *next[i];
};

struct node *head,*tail;

void listinitialize(void)
{
head=(struct node *) malloc(sizeof(*head));
tail=(struct node *) malloc(sizeof(*tail));
head->next=tail;
tail->next=NULL;
};




No.8249

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/10 20:07:48)


1)keyをchar型のポインタ変数に変更した後、なぜ文字列を扱えるようになるのですか?あらかじめ決まった文字列ならば可能でしょうが、これから入力する 文字列に 対しても同様に扱ってくれるのでしょうか。

2)また、ポインタ変数を使用した場合、入出力の書式指定子は%c、さらにwhile文による繰り返しが必要ですよね。

3)mallocによる動的記憶領域の確保の文は、どこに入れればいいのですか?

4)文字列操作関数strcpyを初期化、挿入、削除、参照に用いる場合のかき方について教えてください。その際、NULLはそのまま用いてよろしいのでしょうか?

5)insertafter,deletenext,searchnodeの引数であるvは、どうすればいいのでしょうか?

6)next,p,xの変更もするのでしょうか?

7)strcmpをこのプログラムのどこで、どのように使えばよいのか分かりません。

No.8252

Re:リストを使用した簡易文字列辞書の作成
投稿者---YuO(2003/07/10 20:52:37)


>1)keyをchar型のポインタ変数に変更した後、なぜ文字列を扱えるようになるのですか?あらかじめ決まった文字列ならば可能でしょうが、これから入力する 文字列に 対しても同様に扱ってくれるのでしょうか。

keyにmallocで記憶領域を割り付けてそれをcharの配列であるかのように扱えば,
長さ自由で文字列を扱えます。
このあたりはC言語で可変の文字列を扱うための基本のテクニックです。


>2)また、ポインタ変数を使用した場合、入出力の書式指定子は%c、さらにwhile文による繰り返しが必要ですよね。

書式指示子は%sですし,入出力のための繰り返しは不要です。
また,scanfを使わない,という選択肢もあります。
#単に%sでscanfを使うのは危険です。


>3)mallocによる動的記憶領域の確保の文は、どこに入れればいいのですか?

リストの要素へ代入するときに使います。


>4)文字列操作関数strcpyを初期化、挿入、削除、参照に用いる場合のかき方について教えてください。その際、NULLはそのまま用いてよろしいのでしょうか?

何がわからないのですか?
そもそも,リストの要素の処理においてNULLは使っていないように見えますが。


>5)insertafter,deletenext,searchnodeの引数であるvは、どうすればいいのでしょうか?

const char *あたりが無難です。
どうせ変更しないのですから。


>6)next,p,xの変更もするのでしょうか?

なぜ変更しないといけないのですか?
それらはリスト構造を扱うための変数・メンバ変数です。
リスト構造自体の処理に,リストの要素は関係しません。


>7)strcmpをこのプログラムのどこで、どのように使えばよいのか分かりません。

strcmpは文字列,つまりリスト要素の比較のために使います。


No.8271

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/11 01:55:13)


>#単に%sでscanfを使うのは危険です。
それはなぜですか?また、それを回避するためには具体的にどのようにすればよろしいのですか?

このプログラムに"Lookup"のコマンドを持たせるようにするためには、strcmpを用いてどのように記述すればよいのですか。また、入力した文字列と比較するべきものが分かりません(既に入力済みの文字列がどの文字で表されているのかがわかりません)。




No.8250

Re:リストを使用した簡易文字列辞書の作成
投稿者---YuO(2003/07/10 20:40:28)


>アドバイスの通り、それぞれの部分を変更してみたのですが、やはり正常に動きません。
>まだまだ初心者なので、どこが間違っているのか見当がつきません。
>自己参照構造体と初期化までのプログラムを以下に貼り付けておくので、具体的に指摘していただければと思います。

貼り付けられた部分についての指摘は後にするとして……。

とりあえず,最初のintのリストのプログラムについて,
・リスト構造に対する操作
と,
・リストの要素に対する操作
を分離してみてください。

intをリストの要素とするプログラムから文字列をリストの要素とするプログラムに変更するには,
リストの要素に対する操作を変更することになります。
構造部分に手を付ける必要はないです。

struct node
{
  const int i=11;
  char key[i];
  struct node *next[i];
};

いくらiがconstでも,これは不正……。
Cでは構造体内部で初期化することはできません。
#C++でもiがstaticでないと違反だし。

でもって,
・keyはリストの要素
・struct node,nextはリストの構造
です。

つまり,nextはstruct node *next;と宣言してやれば十分です。


No.8285

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/11 21:09:53)


もう一度以下のようにプログラムを作り直してみましたがコンパイルしてもエラーメッセージが出てきて、実行しても文字列を認識してくれません。どうしてでしょうか?
 また、入力した文字列と既に入力されている文字列を比較するとき、strcmpを使ってどのようにすればいいのでしょうか?


#include<stdio.h>
#include<string.h>

struct node
{
  char *key;
  key=(char *) malloc(sizeof(*key));
  struct node *next;
};

struct node *head,*tail;

void listinitialize(void)
{
  head=(struct node *) malloc(sizeof(*head));
  tail=(struct node *) malloc(sizeof(*tail));
  head->next=tail;
  tail->next=NULL;
};

struct node *insertafter(const char *v,struct node *p)
{
  struct node *x;
  
  x=(struct node *) malloc(sizeof(*x));
  x->key=v;
  x->next=p->next;
  p->next=x;
  return x;
};

void deletenext(struct node *p)
{
  struct node *x;
  x=p->next;
  p->next=p->next->next;
  free(x);
};

struct node *searchnode(const char *v)
{
  struct node *x;
  
  x=head;
  while(x->next->next!=NULL)
    {
      if(x->next->key==v) break;
      x=x->next;
    };
  return x;
};

int main(void)
{
  struct node *x;
  char com;
  int a;
  char *n;
  n=(char *) malloc(sizeof(*n));

  listinitialize();
  
  printf("please choose number\n");
  printf("(1)Insert, (2) Delete, (3) Lookup, (4)Print,(0) End ?");
  
  scanf(" %c",&com);
  while(com!='0')
    {
      switch(com)
	{
	case '1':
	  printf("Word?");
	  scanf("%s",n);
	  insertafter(n,head);
	  printf("input OK!\n");
	  break;

	case '2':
	  printf("Word?");
	  scanf("%s",n);
	  x=searchnode(n);
	  if(x->next->next!= NULL) deletenext(x);
	  printf("delete OK!\n");
	  break;
	  
	case '3':
	  printf("Word?");
	  scanf("%s",n);
	  a=strcmp(n, x);
	  if(a==0)
	    printf("%s is in the dictionary.\n",n);

	  else
	    printf("%s is NOT in the dictionary.\n",n);
	  break;
	  
	case '4':
	  x=head->next;
	  while(x->next!=NULL)
	    {
	      printf("%s",x->key);
	      x=x->next;
	    };
	  printf("\n");
	  break;
	};
      printf("(1)Insert,(2)Delete,(3)Look up,(4)Print,(0)End");
      scanf(" %c",&com);
    };
  return 0;
}


No.8287

Re:リストを使用した簡易文字列辞書の作成
投稿者---YuO(2003/07/11 21:34:29)


>もう一度以下のようにプログラムを作り直してみましたがコンパイルしてもエラーメッセージが出てきて、実行しても文字列を認識してくれません。どうしてでしょうか?

コンパイルエラーの内容は?
#だいたい予測できていますが。

構造体の使い方とか,勉強し直した方がいいと思います。


No.8292

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/12 11:34:20)


>コンパイルエラーの内容は?
>#だいたい予測できていますが。
エラーの内容が長すぎて一部しかわかりません。mallcもfree関数も認識されていないようです。ちなみにMeadowでソースプログラムを、Cygwinでコンパイルを行っています。
 エラーの内容は以下の通りです。
18: dereferencing pointer to incomplete type
 In function `insertafter':
25: dereferencing pointer to incomplete type
26: dereferencing pointer to incomplete type
27: dereferencing pointer to incomplete type
27: dereferencing pointer to incomplete type
28: dereferencing pointer to incomplete type
 In function `deletenext':
35: dereferencing pointer to incomplete type
36: dereferencing pointer to incomplete type
36: dereferencing pointer to incomplete type
37: warning: implicit declaration of function `free'
 In function `searchnode':
45: dereferencing pointer to incomplete type
47: dereferencing pointer to incomplete type
48: dereferencing pointer to incomplete type
 In function `main':
82: dereferencing pointer to incomplete type
89: warning: passing arg 2 of `strcmp' from incompatible pointer type
98: dereferencing pointer to incomplete type
99: dereferencing pointer to incomplete type
101: dereferencing pointer to incomplete type
102: dereferencing pointer to incomplete type



>構造体の使い方とか,勉強し直した方がいいと思います。
不勉強で申し訳ありません。構造体ポインタ変数の参照と代入がいまいちよくわからないもので…


No.8294

Re:リストを使用した簡易文字列辞書の作成
投稿者---かずま(2003/07/12 13:59:42)


> もう一度以下のようにプログラムを作り直してみましたがコンパイルしても
> エラーメッセージが出てきて、実行しても文字列を認識してくれません。

コンパイルエラーが出たものを、どうやって実行できるんですか。

構造体の宣言の中に実行文を書くなんて、トホホですね。

最初の数値の辞書のプログラムも気に入らないので、次のように書き換えます。
#include <stdio.h>
#include <stdlib.h>

typedef struct Node Node;
struct Node { int key; Node *next; };

void insertafter(Node *p, int v)
{
    Node *x = malloc(sizeof(*x));
    x->key = v;
    x->next = p->next;
    p->next = x;
}

void deletenext(Node *p)
{
    Node *x = p->next;
    p->next = x->next;
    free(x);
}

Node *searchnode(Node *p, int v)
{
    for (; p->next; p = p->next)
        if (p->next->key == v) break;
    return p;
}

void printnode(Node *p)
{
    while (p = p->next) printf(" %d", p->key);
    printf("\n");
}

int main(void)
{
    Node head = { 0 }, *x;
    int com;
    int n;

    for (;;) {
        printf("please choose number\n"
               "(1)Insert, (2)Delete, (3)Lookup, (4)Print, (0)End ? ");
        if (scanf("%d", &com) != 1 || com == 0) break;
        switch (com) {
        case 1:
            printf("Number? "); if (scanf("%d", &n) != 1) return 1;
            insertafter(&head, n);
            printf("input OK!\n");
            break;

        case 2:
            printf("Number? "); if (scanf("%d", &n) != 1) return 1;
            x = searchnode(&head, n);
            if (x->next) deletenext(x);
            printf("delete OK!\n");
            break;

        case 3:
            printf("Number? "); if (scanf("%d", &n) != 1) return 1;
            x = searchnode(&head, n);
            if (x->next)
                 printf("%d is in the dictionary.\n", n);
            else
                 printf("%d is NOT in the dictionary.\n", n);
            break;

        case 4:
            printnode(&head);
            break;
        }
    }
    return 0;
}

これを文字列の辞書のプログラムに変えたかったら、変更箇所は次のとおり。
・構造体を struct Node { char *key; Node *next; }; に
・関数の引数の int v を const char *v に
・x->key = v; を x->key = strdup(v); に。#include <string.h> を先頭に置く。
・if (p->next->key == v) break; を if (strcmp(p->next->key, v) == 0) break; に
・int n; を char word[100]; に
・printf("Number? "); if (scanf("%d", &n) != 1) return 1; を
  printf("Word? "); if (scanf("%99s", word) != 1) return 1; に
・すべての n を word に
・printf の "%d" を "%s" に

No.8303

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/12 21:51:12)


非常に助かりました。どうも有り難うございます。
しかし、提案されたプログラムを実際にコンパイルしてみても次のようなメッセ−ジが出てきてしまいました。これは、どういう意味なのでしょうか?

 In function `insertafter':
16: warning: passing arg 1 of `strdup' makes pointer from integer without a cast
 In function `searchnode':
31: warning: passing arg 2 of `strcmp' makes pointer from integer without a cast
 In function `printnode':
 warning: suggest parentheses around assignment used as truth value
 In function `main':
59: warning: passing arg 2 of `insertafter' makes integer from pointer without a cast
67: warning: passing arg 2 of `searchnode' makes integer from pointer without a cast
76: warning: passing arg 2 of `searchnode' makes integer from pointer without a cast



No.8310

Re:リストを使用した簡易文字列辞書の作成
投稿者---YuO(2003/07/12 22:53:58)


>しかし、提案されたプログラムを実際にコンパイルしてみても次のようなメッセ−ジが出てきてしまいました。これは、どういう意味なのでしょうか?
16: warning: passing arg 1 of `strdup' makes pointer from integer without a cast

16行目: 警告: "strdup"関数の第一引数で,キャストなしに整数からポインタへの変換が行われている

他にも
 In function `main':
59: warning: passing arg 2 of `insertafter' makes integer from pointer without a cast
67: warning: passing arg 2 of `searchnode' makes integer from pointer without a cast
76: warning: passing arg 2 of `searchnode' makes integer from pointer without a cast
なんかを見ていると,関数の基礎からやり直しかな……?

かずまさんが書かれた,
> ・関数の引数の int v を const char *v に
> ・x->key = v; を x->key = strdup(v); に。#include <string.h> を先頭に置く。
もやっていないようですし。
#16行目の警告は後者が原因。mainのは前者が原因。


No.8313

Re:リストを使用した簡易文字列辞書の作成
投稿者---悩める大学生(2003/07/13 00:35:36)


>かずまさんが書かれた,
>> ・関数の引数の int v を const char *v に
>もやっていないようですし。

おっしゃるとおり、const char *vとかくべきところを誤ってconst char vとしてしまいポインタ変数にすることをし忘れていました。本当に情けないですよね。

訂正して再びコンパイルしてみましたところ、また次のようなエラーメッセージが出てきました。parenthesesは挿入語句(前後を括弧やダッシュで区切る)という意味だそうですが、しっかり括弧でくくってるんですけど、どうしてこのようなメッセージがでてきたのでしょうか?

 In function `printnode':
c:37: warning: suggest parentheses around assignment used as truth value