プログラマ専用SNS ミクプラ

コード:

#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;
}

コード:

#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);

}