C言語/英単語のソート/リスト

[よなぺん]

当方一年間プログラミングをサボり続けていた情報系の大学生です。
少しづつ学んではいるのですが少し手詰まりしており、手を借りたいのです。
今回txtファイルに
dsad
fsfdg
fgah
dhhasfsa
gdaghfhs
saafaf
のように100000個の英単語を読み込んで辞書式にC言語でソートするようにとの課題でして
ポインタを用いたリストでプログラムを組もうとしているのですがリストの使い方がいまいちわかっていないのでご教授願いたいです。
細かく言うと
どのように記述していくとリストに英単語を格納できるのか、リストのメモリ確保の方法（ここらへんはダメダメなので詳しくおねがいします。）について教えて下さい。

[usao]

「自分ではここまではできているが，ここがうまくいかない」とかいう形を提示して質問すると良いです．

>リストの使い方
→リストとは何ぞや？ということであれば，とりあえず検索してもらったほうが早いです．

>メモリの確保
→malloc(), free() について調べるとよいでしょう．

オフトピック

100000個の英単語なファイルを用意するのがまず大変そうな課題ですね．

[みけCAT]

オフトピック

100000個の英単語なファイルを用意するのがまず大変そうな課題ですね．

例を見ると「英単語」にはなっていないようなので、単にランダムな英小文字からなる文字列を出力するだけではないでしょうか？
重複しないように制御しようと思うと、C言語では少し難しくなりそうですね。

[box]

リスト構造を用いることは必須条件ですか？

[よなぺん]

英単語に関しては教授がtxtデータで送ってくれています。
リストについてはある程度は調べたのですが、実際に用いる記述が曖昧で煮詰まっております。
配列リストは使っては行けないそうです。ポインタリストを用いなければなりません。

質問の仕方が悪いようなので少し質問を変えます。
chair
dog
apple
という3つの文字列をListに格納する記述を具体的に書いていただけるとありがたいです。

[usao]

単方向リストで最低限のコード例です．
（エラーチェックとかは省略してます）

► スポイラーを表示

コード:

typedef
struct ListNode
{
    struct ListNode *pNextNode;
    char *pDataStr;
} ListNode;

//
ListNode *CreateNode( const char *pDataStr )
{
    ListNode *pNewNode = (ListNode*)malloc( sizeof(ListNode) );
    pNewNode->pNextNode = NULL;
    {
        const int StrLen = strlen( pDataStr ) + 1;
        pNewNode->pDataStr = (char*)malloc( sizeof(char)*StrLen );
        strcpy( pNewNode->pDataStr, pDataStr );
    }
    return pNewNode;
}

//
ListNode *DeleteNode( ListNode *pNode )
{
    ListNode *Ret = pNode->pNextNode;
    free( pNode->pDataStr );
    free( pNode );
    return Ret;
}

//
ListNode *LinkNode( ListNode *pNodeA, ListNode *pNodeB )
{
    pNodeA->pNextNode = pNodeB;
    return pNodeB;
}

//
void ShowList( const ListNode *pRoot )
{
    while( pRoot )
    {
        printf( "%s\n", pRoot->pDataStr );
        pRoot = pRoot->pNextNode;
    }
}

//
int main()
{
    //作成
    ListNode *pRoot = CreateNode( "chair" );
    {
        ListNode *pTail = pRoot;
        pTail = LinkNode( pTail, CreateNode( "dog" ) );
        pTail = LinkNode( pTail, CreateNode( "apple" ) );
    }

    //表示
    ShowList( pRoot );

    //全破棄
    while( pRoot )
    {
        pRoot = DeleteNode( pRoot );
    }
    
    return 0;
}

[かずま]

オフトピック

100000個の英単語なファイルを用意するのがまず大変そうな課題ですね．

http://www.infochimps.com/datasets/word ... l-readable
ここからダウンロードできます。

[かずま]

オフトピック

重複しないように制御しようと思うと、C言語では少し難しくなりそうですね。

その根拠は何でしょうか？

重複を許すプログラムを書いた後、重複を削除するように
少し変更するだけでよいのでは？
例えば、次のプログラムは、40行目がないと重複を許し、
40行目があると重複を削除します。

コード:

#include <stdio.h>  // puts, fscanf
#include <stdlib.h> // malloc
#include <string.h> // strdup

typedef struct Node Node;
struct Node {
    char *word;
    Node *next;
};

void PrintWords(const Node *node)
{
    for (; node; node = node->next)
        puts(node->word);
}

int GetWord(FILE *fp, char *word)
{
    fscanf(fp, "%*[^a-z]");
    return fscanf(fp, "%255[a-z]", word) == 1;
}

Node *AddWord(Node *node, const char *word)
{
    Node *np = malloc(sizeof(Node));
    np->word = strdup(word);
    np->next = node;
    return np;
}

Node *Merge(Node *a, Node *b)
{
    Node head, *tail = &head;
    while (a && b) {
        int diff = strcmp(a->word, b->word);
        if (diff < 0)
            tail->next = a, tail = a, a = a->next;
        else {
            tail->next = b, tail = b, b = b->next;
            if (diff == 0) a = a->next;
        } 
    }
    tail->next = a ? a : b;
    return head.next;
}

Node *SortWords(Node *node)
{
    Node *a, *b;
    if (!node || !node->next) return node;
    a = node, b = node->next;
    while (b && b->next)
        node = node->next, b = b->next->next;
    b = node->next, node->next = NULL;
    a = Merge(SortWords(a), SortWords(b));
    return a;
}

int main(void)
{
    Node *root = NULL;
    char word[256];
    while (GetWord(stdin, word))
        root = AddWord(root, word);
    root = SortWords(root);
    PrintWords(root);
    return 0;
}

なお、このプログラムは、
- malloc や strdup のエラーをチェックしていない
- malloc や strdup が確保した領域を free していない
- strdup は標準関数ではない
- scanf の [a-z] という書式は規格書にはない
など、不完全なものなので、課題の解答としては不適切です。

[よなぺん]

おかげさまで格納することが出来ました。ありがとうございます。
ソートなんですが、クイックソートを取ろうと考えており大まかなプログラムはできましたがエラーでSegmentation
fault (core dumped)
と表示され煮詰まっております。95行目を削除するとエラーは起きません
またこのプログラムで正しくソートできるのでしょうか
お願いします。

コード:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define WORDSIZE 50

typedef struct List {
	char word[WORDSIZE]; /* 英単語  */
	struct List *next; /* 次データのポインタ */
}list;


list *add(char *word, list *head) { // add関数の定義

	list *p;

	// 記憶領域の確保
	p = (list *) malloc(sizeof(list));
	// リストにデータを登録
	strcpy(p->word, word);

	// ポインタのつなぎ変え
	p->next = head;/* 今までの先頭ポインタを次ポインタへ */
	head = p;/* 新たな領域を先頭ポインタへ */

	return (head);/* 返り値は新先頭ポインタ */
}


// show関数の定義
void show(list *p) {
	while(p->next != NULL) {   /* 次ポインタがNULL、からになるまで行う */
		printf("%s\n", p->word);
		p = p->next; /* 次のポインタへ変更 */
	}

}

list *findshow(list *p, int k) { //リストpのk番目のポインタを返す,+その内容の表示
	int i;
	for(i = 0; i < k-1 ; i++) {
		p = p->next;
	}
	printf("%s\n", p->word);
	return (p);

}
int length(list *p) { 
	int i = 0;
	while(p->next != NULL) {
		p = p->next;
		i++;
	}
	return (i);
}

list *find(list *p, int k) { //リストpのk番目のポインタを返す
	int i;
	for(i = 0; i < k-1 ; i++) {
		p = p->next;
	}
	return (p);

}

void swap(list *p, int k, int l) { //リストpのk番目とl番目を交換する
	char tmp[WORDSIZE];
	strcpy(tmp, find(p, k)->word);
	strcpy(find(p,k)->word, find(p,l)->word);
	strcpy(find(p, l)->word, tmp);

}

void sort(list *p, int begin, int end) { // begin からendまでをQSortする
	int pivot = (end - begin + 1)/2;
	int i = begin;
	int j = end;

	while(1) {
		while(strcmp(find(p, i)->word, find(p, pivot)->word) > 0){ // pivot以下が現れるまでくり返す
			i++;
		}
		while(strcmp(find(p, j)->word, find(p, pivot)->word) < 0){ // pivot以下が現れるまでくり返す
			j--;
		}
		if(i >= j)break;
		swap(p, i, j);
		i++;
		j--;
		
	}
	if( begin < i - 1) {
		sort( p, begin, i-1);	
	}
	if( j + 1 < end ) {
		sort( p, j+1, end);
	}

	
	
}



int main(void)
{
	list *p;
	char word[WORDSIZE];
	p = 0;

	do {
		
	p = add(word, p);

		
	}while(scanf("%s", word) != EOF);
	sort(p,1,10);

	show(p);

}

[かずま]

ソートなんですが、クイックソートを取ろうと考えており大まかなプログラムはできましたがエラーでSegmentation
fault (core dumped)
と表示され煮詰まっております。95行目を削除するとエラーは起きません
またこのプログラムで正しくソートできるのでしょうか

pivot の求め方が間違っています。
例えば、begin = 7, end = 10 のとき
pivot が 2 になってしまいます。
7 から 10までの値であるべきなのに。

また、pivot の位置にある word の値も swap の対象に
なるので、ループを回るうちにその値が変わってしまいます。
ループを回る前に取り出しておきましょう。

main で word が初期化されていないので、
最初の add が失敗する可能性があります。

find でリストの k番目の要素を求めていますが、
こんなことをやっていたら、100000個のデータに
対してはとんでもない時間がかかってしまいます。

クイックソートは、データをきっちり二分割するわけでは
ないので、かたよりがあると再帰呼び出しが深くなり、
スタックオーバーフローが起きる可能性があります。