单链表操作

键盘输入英语单词的个数 n 及 n 个单词，编一程序，建立一个单向链表，实现：
（ 1 ）如果单词重复出现，则只在链表上保留一个。
（ 2 ）除满足（ 1 ）的要求外。链表结点还应有一个计数域，记录该单词重复出现的次数，然后输出出现次数最多的前 k(k<=n) 个单词。

---

#include <stdio.h>
#include "stdlib.h"
#include "string.h"
#define M 30
typedef struct LNode{
    char *word;
    int count;
    struct LNode *next;
}LNode;

//判断当前链表中是否已经存在某个单词，如果有，该节点的count++，返回1，否则返回0
int isWordInList(LNode *head, char *word) {
    LNode *node = head->next;
    while (NULL != node && strcmp(word, node->word)) {
        node = node->next;
    }
    if (NULL != node) {
        node->count++;
        return 1;
    }
    return 0;
}

//头插法插入一个新的节点
void insertWordInList(LNode *head, char *word) {
    if (isWordInList(head, word)) {
        return;
    }
    LNode *node = (LNode*)malloc(sizeof(LNode));
    node->word = word;
    node->count = 1;
    node->next = head->next;
    head->next = node;
    head->count++;
}

//输出整个链表
void printList(LNode *head) {
    LNode *node = head->next;
    while (NULL != node) {
        printf("word is %s, and cout is %d\n", node->word, node->count);
        node = node->next;
    }
}

void printListByK(LNode *head, int k) {
    int count = head->count;
    if (k >= count) {
        printList(head);
    } else {
        LNode *node = head->next;
        for (int i = 0; i < k; i++) {
            printf("word is %s, and count is %d", node->word, node->count);
            node = node->next;
        }
    }
}

//交换两个节点的值
void swapTwoLNode(LNode *nodeA, LNode *nodeB) {
    int countA = nodeA->count;
    char *wordA = nodeA->word;
    nodeA->word = nodeB->word;
    nodeA->count = nodeB->count;
    nodeB->word = wordA;
    nodeB->count = countA;
}

//效率更高的方法
void printKthWords(LNode *head, int k) {
    int i = 0;
    //选择排序，把前k的单词从大到小排列
    for (LNode *node = head->next; NULL != node && i < k; node = node->next, i++) {
        LNode *maxNode = node;
        for (LNode *nodeA = node->next; NULL != nodeA; nodeA = nodeA->next) {
            if (nodeA->count > maxNode->count) {
                maxNode = nodeA;
            }
        }
        swapTwoLNode(node, maxNode);
    }
    printListByK(head, k);
}

int main(int argc, const char * argv[]) {
    int n;
    LNode *head;
    while (n <= 0) {
        printf("Please input the count n of words:\n");//保证(n > 0)
        scanf("%d", &n);
    }
    head = (LNode *)malloc(sizeof(LNode));
    head->next = NULL;
    head->count = 0;
    for (int i = 0; i < n; i++) {
        char *word = (char *)malloc(sizeof(char) * M);
        printf("输入第%d个单词：", (i + 1));
        scanf("%s", word);
        insertWordInList(head, word);
    }
    int k;
    while (k <= 0 || k > n) {
        printf("Please input k([1,n]):");//保证k值有效
        scanf("%d", &k);
    }
    printKthWords(head, k);
    return 0;
}