ファイル中の文字を読み込み、出現回数をカウントするプログラム例について

Question

前提・実現したいこと

C言語で、二つ以上のファイル（英字だけのテキストファイル）から文字列を読み込み、出現回数をカウントして、出現回数が多い順に並べ替えて出力するプログラムを線形リスト構造を用いて書け、という問題のコードの例を教えてほしいです。。

例えば、
file1.txt

abc
def
abc

file2.txt

abc
hil
def

ならば、実行して

abc 3
def 2
hil 1

と出力されるようなプログラムを作りたいです。
初心者なので助けてください！

■■な機能を実装中に以下のエラーメッセージが発生しました。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

C

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

struct cell{
struct cell *next;
};

int main(int argc, char *argv[])
{
FILE *fp;
int i,chr;

for(i=1;i<argc;i++){
fp=fopen(argv[i], "r");
if(fp==NULL){
fprintf(stderr, "cannot open %s\n", argv[i]);
exit(1);
}

試したこと

ここに問題に対して試したことを記載してください。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[Zuishin]

自分で作りたいのであって、答えを教えて欲しいわけではないんですね？

[dodox86]

初心者さんにとってはまあまあテーマが多そうな課題ですね。（ポインタの扱い必須、ファイル入出力、文字列トークン分割、キー／値マップ、線形リスト、ソート等？）　ですが、今のままですとさすがに丸投げ扱いで、回答がつくのは難しいと思いますよ。

[termae]

答えを教えてほしいです。。
まだまだできないことが多いので、教えてもらった後に分析しようと思っています。。。

[termae]

アドバイスありがとうございます。
丸投げは良くないのは分かっているのですが、何をどうして良いか全然分かららないのです、、、

[Zuishin]

解き方なら教えられますが、答えは教えられません。そのようなサイトでもありません。

https://teratail.com/help/avoid-asking

> 何かを作りたいのでコードを書いてほしい、学校の課題を解いてほしい等の質問は、具体的にプログラミングで困っている質問ではないと考え、推奨していません。

[cateye]

ここ（telatail）で、“文字数カウント”で検索すると100以上回答が見れますが・・・見ましたか？
・・・どうも皆さん、質問をするのは良いのですが、過去の事例を確認することが苦手のようで・・・

Answer 1

Cの初心者がやるような課題とは思えません。6時間ぐらいかかりました。

コードだけ欲しいようですので下記にあげますが、著作権は放棄していません。Copyrightとその下の条項を決して削除しないでください。

/**
 * 単語カウントアッププログラム v1.0 2019-10-19
 *
 * このプログラムはteratailの下記質問の回答のために作成された物です。
 * https://teratail.com/questions/218076
 *
 * 質問の内容では明記されていない部分について、下記の仕様としています。
 *
 * - 空白切りの単語をカウントします。空白文字は[ \t\r\n\f\v]とします。
 * - メモリの許す限り長い文字列も扱います。
 *   ただし、`SIZE_MAX - BUFF_SIZE_INC`を越えることはできませんが、
 *   64bit環境ではそれだけのメモリを用意することは現実的ではありません。
 * - null文字が含まれる場合、エラーで終了します。
 *   "テキスト"にはnull文字が含まれていないからです。
 * - テキストの文字コードは考慮しませんが、エラーメッセージはUTF-8固定で
 *   あるため、UTF-8環境で実行する必要があります。
 *   そのため、テキストファイルの文字コードもUTF-8でなければ、
 *   文字化けを起こす可能性があります。
 * - 次期バージョンでは既存文字検索にハッシュテーブルを使用して、
 *   爆速になる予定です。
 * - 次期バージョンの開発予定は未定です。
 *
 * このプログラムのラインセンスはGPLv3です。
 * プログラムをコピーする際はライセンスの遵守をお願いします。
 *
 * ---
 * Copyright (c) 2019 raccy
 * GNU General Public License
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 */

#include <errno.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdnoreturn.h>
#include <string.h>

#define BUFF_SIZE_INC 256

struct count_list;
struct str_list;

struct count_list {
	uint32_t count;
	struct count_list *next;
	struct count_list *prev;
	struct str_list *slp;
};

struct str_list {
	uint32_t hash;
	size_t len;
	struct str_list *next;
	struct str_list *prev;
	struct count_list *clp;
	char *str;
};

static inline noreturn void die(const char *message)
{
	perror(message);
	exit(1);
}

struct str_list *create_slp_from_stream(FILE *stream);
void free_slp(struct str_list *slp);
void free_clp(struct count_list *clp);
void add_slp_to_clp(struct str_list *slp, struct count_list *clp);
void remove_slp_from_clp(struct str_list *slp);
void add_or_countup_slp_to_first_clp(struct str_list *slp,
				     struct count_list *first_clp);
struct count_list *get_or_create_next_clp(struct count_list *clp);
void countup_slp(struct str_list *slp);
struct str_list *search_slp_in_clp(struct str_list *slp,
				   struct count_list *clp);

int main(int argc, char *argv[])
{
	struct count_list *first_clp =
	    (struct count_list *)malloc(sizeof(struct count_list));
	if (first_clp == NULL) die(u8"メモリ取得に失敗しました。");
	first_clp->count = 0;
	first_clp->next = first_clp;
	first_clp->prev = first_clp;
	first_clp->slp = NULL;

	for (int i = 1; i < argc; i++) {
		FILE *fp = fopen(argv[i], "r");
		if (fp == NULL) {
			perror(u8"ファイルを開けませんでした。");
			continue;
		}
		struct str_list *slp;
		while ((slp = create_slp_from_stream(fp)) != NULL) {
			add_or_countup_slp_to_first_clp(slp, first_clp);
		}
	}

	for (struct count_list *curr_clp = first_clp->prev;
	     curr_clp != first_clp; curr_clp = curr_clp->prev) {
		if (curr_clp->slp == NULL) continue;
		struct str_list *curr_slp = curr_clp->slp;
		do {
			printf("%s %d\n", curr_slp->str, curr_clp->count);
			curr_slp = curr_slp->next;
		} while (curr_slp != curr_clp->slp);
	}

	free_clp(first_clp);
	return 0;
}

struct str_list *create_slp_from_stream(FILE *stream)
{
	int c = getc(stream);
	switch (c) {
	case EOF:
		return NULL;
	case ' ':
	case '\t':
	case '\r':
	case '\n':
	case '\f':
	case '\v':
		return create_slp_from_stream(stream);
	}
	ungetc(c, stream);

	struct str_list *slp =
	    (struct str_list *)malloc(sizeof(struct str_list));
	if (slp == NULL) die(u8"メモリ取得に失敗しました。");
	slp->hash = 0;
	slp->len = 0;
	slp->next = NULL;
	slp->prev = NULL;
	slp->clp = NULL;
	slp->str = NULL;

	size_t buff_size = 0;
	bool line_end = false;
	while (!line_end) {

		if (buff_size <= slp->len) {
			if (buff_size > SIZE_MAX - BUFF_SIZE_INC)
				die(u8"サイズの限界を超えています");
			buff_size = buff_size + BUFF_SIZE_INC;
			slp->str = (char *)realloc(slp->str, buff_size);
			if (slp->str == NULL)
				die(u8"メモリ取得に失敗しました。");
		}
		int c = getc(stream);
		switch (c) {
		case EOF:
		case ' ':
		case '\t':
		case '\r':
		case '\n':
		case '\f':
		case '\v':
			line_end = true;
			break;
		case '\0':
			die(u8"null文字 '\0' "
			    u8"が含まれたファイルは読み込みません。");
			break;
		default:
			slp->str[slp->len] = c;
			slp->hash ^= (uint32_t)c << (slp->len % 4) * 8;
			slp->len++;
			break;
		}
	}
	if (slp->len != 0) {
		slp->str[slp->len] = '\0';

		return slp;
	} else {
		free_slp(slp);
		return create_slp_from_stream(stream);
	}
}

void free_slp(struct str_list *slp)
{
	free(slp->str);
	free(slp);
}

void free_clp(struct count_list *clp)
{
	if (clp->next->count != 0) free_clp(clp->next);
	if (clp->slp != NULL) {
		struct str_list *curr_slp = clp->slp;
		do {
			struct str_list *next_slp = curr_slp->next;
			free_slp(curr_slp);
			curr_slp = next_slp;
		} while (curr_slp != clp->slp);
	}
	free(clp);
}

void add_slp_to_clp(struct str_list *slp, struct count_list *clp)
{

	if (clp->slp == NULL) {
		clp->slp = slp;
		slp->next = slp;
		slp->prev = slp;
	} else {
		struct str_list *last_slp = clp->slp->prev;
		slp->next = clp->slp;
		slp->prev = last_slp;
		last_slp->next = slp;
		clp->slp->prev = slp;
	}
	slp->clp = clp;
}

void remove_slp_from_clp(struct str_list *slp)
{
	struct count_list *clp = slp->clp;
	struct str_list *next_slp = slp->next;
	struct str_list *prev_slp = slp->prev;
	if (next_slp == slp) {
		next_slp = NULL;
	} else {
		next_slp->prev = prev_slp;
		prev_slp->next = next_slp;
	}
	if (clp->slp == slp) clp->slp = next_slp;

	slp->next = NULL;
	slp->prev = NULL;
	slp->clp = NULL;
}

void add_or_countup_slp_to_first_clp(struct str_list *slp,
				     struct count_list *first_clp)
{
	struct str_list *found_slp = search_slp_in_clp(slp, first_clp);
	if (found_slp == NULL) {
		add_slp_to_clp(slp, get_or_create_next_clp(first_clp));
	} else {
		countup_slp(found_slp);
		free_slp(slp);
	}
}

struct count_list *get_or_create_next_clp(struct count_list *clp)
{
	if (clp->next->count == 0) {
		if (clp->count >= UINT32_MAX)
			die(u8"数え上げる個数の限界を超えました。");
		struct count_list *next_clp =
		    (struct count_list *)malloc(sizeof(struct count_list));
		if (next_clp == NULL) die(u8"メモリ取得に失敗しました。");
		next_clp->count = clp->count + 1;
		next_clp->slp = NULL;

		next_clp->next = clp->next;
		next_clp->prev = clp;
		clp->next = next_clp;
		next_clp->next->prev = next_clp;
	}
	return clp->next;
}

void countup_slp(struct str_list *slp)
{
	struct count_list *next_clp = get_or_create_next_clp(slp->clp);
	remove_slp_from_clp(slp);
	add_slp_to_clp(slp, next_clp);
}

struct str_list *search_slp_in_clp(struct str_list *slp, struct count_list *clp)
{
	if (clp->slp != NULL) {
		struct str_list *curr_slp = clp->slp;
		do {
			if (slp->hash == curr_slp->hash &&
			    strcmp(slp->str, curr_slp->str) == 0) {
				return curr_slp;
			}
			curr_slp = curr_slp->next;
		} while (curr_slp != clp->slp);
	}
	if (clp->next->count == 0) return NULL;
	return search_slp_in_clp(slp, clp->next);
}

プログラムを書くだけで疲れたので、解説はありません。私の計算が間違ってなければ、検索がハッシュテーブルじゃ無いので、O(n + m^2)(nは総文字数、mは見つかる単語数)ぐらいだと思います。ハッシュテーブルを採用したら、O(n)にできると思われます。

手元では動きましたが、テストはそんなにしていないので、バグはたくさん残っていると思います。もし、見つかったら、テストケースを含めてご指摘下さい。

Comments

[termae]

ありがとうございます！