線形リストの課題がわかりません

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

線形リストの課題がわかりません

#1

投稿記事 by 大学生 » 13年前

大学で次のような課題がでました

市のデータ（cities.txt）を対象として、以下の各機能を持ったプログラムを作成し、提出してください。

1. 情報の登録と一覧表示
2. 情報の削除
3. cities.txt からの情報の読み込み
4. citiesDB.txtへのリスト内容の書き出し
5. 人口でソート
関数の穴埋め形式の課題です。コメントがある部分の関数を完成させるのですが、自分でよくわからないまま入力してみました。
間違っている部分を教えていただきたいです。
コンパイル結果はコメントで書いてあります。
あと、insertCityByPopl()の部分は全くわかりませんでした。こちらもできればお願いします。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define STRLEN 32
#define BUF_LEN 128
#define CITYDB_R_FILE "cities.txt" // 読み込み用ファイル
#define CITYDB_W_FILE "citiesDB.txt" // 書き出し用ファイル

struct cities{
char pref[STRLEN];
char city[STRLEN];
int popl;
float area;
float dens;
char founded[STRLEN];
struct cities *next;
};

struct cities *root=NULL; // rootへのポインタは大域変数として定義

void *mymalloc(size_t sz){
void *p = (void *)malloc(sz);
if(p == NULL){
fprintf(stderr,"ERR: Can't malloc memory %d bytes.",(int)sz);
exit(1);
}
memset(p,0,sz);
return p;
}

void showCity(struct cities *c, FILE *fp){
fprintf(fp,"%s\t%s\t%d\t%.2f\t%.2f\t%s\n",
c->pref, c->city, c->popl, c->area, c->dens, c->founded);
}

struct cities *genNewCityCell(char *pref, char *city, int popl, float area, float dens, char *founded ){
struct cities *c;
c = mymalloc(sizeof(struct cities));
//メモリを確保したｃに対して値を代入する

c->pref = pref; //代入に互換性のない？
c->city = city;//代入に互換性のない？
c->popl = popl;
c->area = area;
c->dens = dens;
c->founded = founded;//代入に互換性のない？

return c;
}

void showList(FILE *fp){
struct cities *cur= root;
while(cur != NULL){
showCity(cur,fp);
cur = cur->next;
}
}

void saveList(){
//書き込み用ファイルを開きそのファイルポインタｆｐに対して
//showList(fp)を呼べばよい。void showList()は１２行上で定義している
FILE *fp;
if((fp=fopen(CITYDB_W_FILE,"w"))==NULL){
printf("cannot open!\n");
exit(1);
}
showList(fp);

fclose(fp);

printf("File saved to %s\n",CITYDB_W_FILE);
}

struct cities *line2City(char *buf){
struct cities *c=NULL;
int popl;
char pref[STRLEN], city[STRLEN], founded[STRLEN];
float area, dens;

sscanf(buf, "%s %s %d %f %f %s", pref, city, &popl, &area, &dens, founded);

c = genNewCityCell(pref,city,popl,area,dens,founded);
return c;
}

void addCity(struct cities *c){
struct cities **cur= &root;

//rootから順にたどって末尾に挿入する
while(*cur!=NULL){
cur = &((*cur)->next);
}
*cur = c;

}

void inputStr(char *buf,int len){
fgets(buf,len,stdin);
buf[strlen(buf)-1]='\0';
}

void addNewCity(){
char buf[BUF_LEN] = "";
struct cities *c;

while(strlen(buf)<=0){
printf("Input one line:\n");
inputStr(buf, BUF_LEN);
}
if(strncmp(buf, "Prefecture", 10) == 0) return;

c = line2City(buf);
addCity(c);
}

void deleteCityFromList(char *delcity){
/*
要加筆
順にたどり，当該項目を削除する．
*/
struct cities **cur = &root;

while(*cur!=NULL){
if(delcity==(*cur)->city){
free(*cur);
}
else{
cur = &((*cur)->next);
}
}

}

void deleteCity(){
char buf[STRLEN];

showList(stdout);

printf("Select Delete City Name:");
inputStr(buf, STRLEN);
deleteCityFromList(buf);
}

void readListFILE(FILE *fp){
char buf[BUF_LEN];
struct cities *c;
while( fgets(buf,BUF_LEN,fp) != NULL){
if(strncmp(buf, "Prefecture", 10) == 0) continue;
c = line2City(buf);
if(c != NULL) addCity(c);
}
}


void readList(){
/*
要加筆
ファイルCITYDB_R_FILEを読み取り用で開く
ファイルが開けない場合のエラー処理
readListFILE(fp);
ファイルをクローズ
*/
FILE *fp;

if((fp=fopen(CITYDB_R_FILE,"r"))==NULL){
printf("cannot open!\n");
exit(1);
}
readListFILE(fp);

fclose(fp);

printf("File loaded\n");
}

void insertCityByPopl(struct cities *sc){
struct cities **cur= &root;

/*
要加筆
順にたどり、挿入すべき箇所に sc を挿入
*/

}


void sortList(){

struct cities *cur,*fr;
cur = root;
root = NULL;
while(cur != NULL){
insertCityByPopl(genNewCityCell(cur->pref, cur->city, cur->popl, cur->area, cur->dens, cur->founded));
fr = cur;
cur = cur->next;
free(fr);
}

showList(stdout);

}

int main(int argc, char *argv[]){
char buf[BUF_LEN];

while(1){
printf("Menu(a:add, d:delete, l:list, s:sort, w:write file, r:read file q:quit):\n");

fgets(buf,BUF_LEN,stdin);
switch(buf[0]){
case 'a':
addNewCity();
break;
case 'd':
deleteCity();
break;
case 'l':
showList(stdout);
break;
case 's':
sortList();
break;
case 'w':
saveList();
break;
case 'r':
readList();
break;
case 'q':
exit(0);
break;
}
}
}


cities.txt
Prefecture City Population Area Density Founded
Aichi Nagoya 2239464 326.45 6860 1889-10-01
Aichi Toyohashi 377045 261.35 1443 1906-08-01
Aichi Okazaki 371380 387.24 959 1916-07-01
Aichi Ichinomiya 375939 113.91 3300 1921-09-01
Aichi Seto 132311 111.61 1185 1929-10-01
Aichi Handa 117927 47.24 2496 1937-10-01
Aichi Kasugai 300713 92.71 3244 1943-06-01
Aichi Toyokawa 161595 150.71 1072 1943-06-01
Aichi Tsushima,Aichi 65646 25.08 2617 1947-03-01
Aichi Hekinan 73024 35.86 2036 1948-04-05
Aichi Kariya 145117 50.45 2876 1950-04-01
Aichi Toyota 420286 918.47 458 1951-03-01
Aichi Anjo 176046 86.01 2047 1952-05-05
Aichi Nishio 106643 75.78 1407 1953-12-15
・
・
・
・
・
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 線形リストの課題がわかりません

#2

投稿記事 by non » 13年前

元の穴が空いている状態のプログラムも載せてください。
どの部分までが正しいのかわかりません。

それから、投稿のルールを守ってください。
non
ページトップ
大学生

Re: 線形リストの課題がわかりません

#3

投稿記事 by 大学生 » 13年前

ごめんなさい
元のプログラムです

コード: 

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

#define STRLEN   32
#define BUF_LEN 128
#define CITYDB_R_FILE "cities.txt" // 読み込み用ファイル
#define CITYDB_W_FILE "citiesDB.txt" // 書き出し用ファイル

struct cities{
  char pref[STRLEN];
  char city[STRLEN];
  int popl;
  float area;
  float dens;
  char founded[STRLEN];
  struct cities *next;
};

struct cities *root=NULL; // rootへのポインタは大域変数として定義

void *mymalloc(size_t sz){
  void *p = (void *)malloc(sz);
  if(p == NULL){
    fprintf(stderr,"ERR: Can't malloc memory %d bytes.",(int)sz);
    exit(1);
  }
  memset(p,0,sz);
  return p;
}

void showCity(struct cities *c, FILE *fp){
  fprintf(fp,"%s\t%s\t%d\t%.2f\t%.2f\t%s\n",
          c->pref, c->city, c->popl, c->area, c->dens, c->founded);
}

struct cities *genNewCityCell(char *pref, char *city, int popl, float area, float dens, char *founded ){
  struct cities *c;
  c = mymalloc(sizeof(struct cities));



  // メモリを確保した c に対して、値を代入する



  return c;
}

void showList(FILE *fp){
  struct cities *cur= root;
  while(cur != NULL){
    showCity(cur,fp);
    cur = cur->next;
  }
}

void saveList(){



  /* 要加筆 */
  // 書き込み用のファイルを開き、そのファイルポインタ fp に対して、
  // showList(fp) を呼べばよい。 void showList() は12行上で定義している



  printf("File saved to %s\n",CITYDB_W_FILE);
}

struct cities *line2City(char *buf){
  struct cities *c=NULL;
  int popl;
  char pref[STRLEN], city[STRLEN], founded[STRLEN];
  float area, dens;

  sscanf(buf, "%s %s %d %f %f %s", pref, city, &popl, &area, &dens, founded);

  c = genNewCityCell(pref,city,popl,area,dens,founded);
  return c;
}

void addCity(struct cities *c){
  struct cities **cur= &root;



  /*
    要加筆
    rootから順にたどって，末尾に挿入する
   */



}

void inputStr(char *buf,int len){
  fgets(buf,len,stdin);
  buf[strlen(buf)-1]='\0';
}

void addNewCity(){
  char buf[BUF_LEN] = "";
  struct cities *c;

  while(strlen(buf)<=0){
    printf("Input one line:\n");
    inputStr(buf, BUF_LEN);
  }
  if(strncmp(buf, "Prefecture", 10) == 0) return;
  
  c = line2City(buf);
  addCity(c);
}

void deleteCityFromList(char *delcity){



  /*
    要加筆
    順にたどり，当該項目を削除する．
    mylist-nodelete.c と同様にするなら，引数を2つにし，
    最も外の呼び出し箇所で &root から始める再帰呼び出しにする．
    addCity() も同様．
   */



}

void deleteCity(){
  char buf[STRLEN];

  showList(stdout);

  printf("Select Delete City Name:");
  inputStr(buf, STRLEN);
  deleteCityFromList(buf);
}

void readListFILE(FILE *fp){
  char buf[BUF_LEN];
  struct cities *c;
  while( fgets(buf,BUF_LEN,fp) != NULL){
    if(strncmp(buf, "Prefecture", 10) == 0) continue;
    c = line2City(buf);
    if(c != NULL) addCity(c);
  }
}


void readList(){



  /*
    要加筆
    ファイルCITYDB_R_FILEを読み取り用で開く
    ファイルが開けない場合のエラー処理
    readListFILE(fp);
    ファイルをクローズ
   */



  printf("File loaded\n");
}

void insertCityByPopl(struct cities *sc){
  struct cities **cur= &root;



  /*
    要加筆
    順にたどり、挿入すべき箇所に sc を挿入
   */



}


void sortList(){

  struct cities *cur,*fr;
  cur = root; 
  root = NULL;
  while(cur != NULL){
    insertCityByPopl(genNewCityCell(cur->pref, cur->city, cur->popl, cur->area, cur->dens, cur->founded));
    fr = cur;
    cur = cur->next;
    free(fr);
  }
  
  showList(stdout);

}

int main(int argc, char *argv[]){
  char buf[BUF_LEN];

  while(1){
    printf("Menu(a:add, d:delete, l:list, s:sort, w:write file, r:read file q:quit):\n");
    
    fgets(buf,BUF_LEN,stdin);
    switch(buf[0]){
    case 'a':
      addNewCity();
      break;
    case 'd':
      deleteCity();
      break;
    case 'l':
      showList(stdout);
      break;
    case 's':
      sortList();
      break;
    case 'w':
      saveList();
      break;
    case 'r':
      readList();
      break;
    case 'q':
      exit(0);
      break;
    }
  }
}
ページトップ
かずま

Re: 線形リストの課題がわかりません

#4

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

大学生 さんが書きました: c->pref = pref; //代入に互換性のない？
文字列を char配列に入れるのは、代入ではできません。
strcpy(c->pref, pref); のように strcpy を使います。

文字列の比較には strcmp を使います。

コード: 

    struct cities *p, **prev = &root;
    for (p = root; p && strcmp(delcity, p->city); p = p->next)
        prev = &p->next;
    if (p) {
        *prev = p->next;
        free(p);
    }
popl は int ですから < で比較できます。

コード: 

    while (*cur && (*cur)->popl < sc->popl)
        cur = &(*cur)->next;
    sc->next = *cur;
    *cur = sc;
ページトップ
かずま

Re: 線形リストの課題がわかりません

#5

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

大学生 さんが書きました: 元のプログラムです

コード: 

void sortList(){

  struct cities *cur,*fr;
  cur = root; 
  root = NULL;
  while(cur != NULL){
    insertCityByPopl(genNewCityCell(cur->pref, cur->city, cur->popl, cur->area, cur->dens, cur->founded));
    fr = cur;
    cur = cur->next;
    free(fr);
  }
  
  showList(stdout);

}
穴埋めだから、元のプログラムの変更はできないんですよね。
でも、上記の while 文の中は、無駄な malloc と コピーと free を実行しています。
次のコードで十分です。

コード: 

    while (cur != NULL) {
        fr = cur;
        cur = cur->next;
        insertCityByPopl(fr);
    }
ページトップ
大学生

Re: 線形リストの課題がわかりません

#6

投稿記事 by 大学生 » 13年前

>かずまさん
ご回答ありがとうございました。
本当に助かりました。

あと、コンパイルエラーは出なかったのですが、addCity()と、deleteCityFromList()も合っている自信がありません。
一度見ていただけないでしょうか？
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 線形リストの課題がわかりません

#7

投稿記事 by non » 13年前

まず、addCity()ですが、

root=NULLのときと、既にリストにnodeが存在するときに分けて考えます。

また、追加は必ず最後尾に行うのですから、
genNewCityCellの関数で、next=NULLにしておいた方がいいでしょう。

最初から指定されている
struct cities **cur= &root;　のポインタのポインタですが、これは何のためにこうしているのか、
何に使うのか、先生に聞いてください。
こうする理由が私にはわかりません。こんなものいりません。
私なら
struct cities *cur=root;
と、します。
　
また、genNewCityCell関数のmallocですが、キャストすべきです。
c = (struct cities *)mymalloc(sizeof(struct cities));
non
ページトップ
かずま

Re: 線形リストの課題がわかりません

#8

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

non さんが書きました:最初から指定されている
struct cities **cur= &root;　のポインタのポインタですが、これは何のためにこうしているのか、
何に使うのか、先生に聞いてください。
こうする理由が私にはわかりません。こんなものいりません。
理由は、「root=NULLのときと、既にリストにnodeが存在するときに分けて考え」
なくて済み、プログラムが簡潔になるからです。

分けて考える場合

コード: 

	if (root == NULL)
		root = c;
	else {
		struct cities *cur = root;
		while (cur->next != NULL)
			cur = cur->next;
		cur->next = c;
	}
	c->next = NULL;
分けない場合

コード: 

	struct cities **cur = &root;
	while (*cur != NULL)
		cur = &(*cur)->next;
	*cur = c;
	c->next = NULL;
ページトップ
non
記事: 1097
登録日時: 15年前

Re: 線形リストの課題がわかりません

#9

投稿記事 by non » 13年前

かずまさん
なるほどですね。気がつきませんでした。勉強になりました。
non
ページトップ
大学生

Re: 線形リストの課題がわかりません

#10

投稿記事 by 大学生 » 13年前

>かずまさん
>nonさん
ありがとうございました。今回はいつもの課題より難易度が上がっていて
自分では全く分からなかったので助かりました＾＾;

あと、最後にdeleteCityFromList()を

コード: 

void deleteCityFromList(char *delcity){
struct cities **cur = &root;

while(*cur!=NULL){
if(delcity==(*cur)->city){
*cur =NULL;
}
else{
cur = &((*cur)->next);
ページトップ
大学生

Re: 線形リストの課題がわかりません

#11

投稿記事 by 大学生 » 13年前

>かずまさん
>nonさん
ありがとうございました。今回はいつもの課題より難易度が上がっていて
自分では全く分からなかったので助かりました＾＾;

あと、最後にdeleteCityFromList()を

コード: 

void deleteCityFromList(char *delcity){
struct cities **cur = &root;

while(*cur!=NULL){
if(delcity==(*cur)->city){
*cur =NULL;
}
else{
cur = &((*cur)->next);
}
}
}
と書き直したのですが、*cur = NULL
以降どう書けばいいかわかりません・・・
このままだとそれ以降全部リストが消えてしまうのはわかってるんですけど
ページトップ
かずま

Re: 線形リストの課題がわかりません

#12

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

大学生 さんが書きました:

コード: 

if(delcity==(*cur)->city){
文字列の比較には strcmp を使うと回答したところで、
deleteCityFromList()　のコードを提示しているのですが
読まなかったのですか？

改良版です。

コード: 

    struct cities **cur = &root;
    while (*cur && strcmp(delcity, (*cur)->city))
        cur = &(*cur)->next;
    if (*cur) {
        struct cities *p = *cur;
        *cur = p->next;
        free(p);
    }
insertCityByPopl() のコードも回答済みですが、それも読んでいないのですか？
ページトップ
大学生

Re: 線形リストの課題がわかりません

#13

投稿記事 by 大学生 » 13年前

>かずまさん
ごめんなさい。
その部分だけ何故か見逃してました。
Insertの方はちゃんと見てます。

改良版ありがとうございます
ページトップ
閉鎖

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