/*=============================================================================
  |
  |  Assignment:  Test #2

  |        Class:  Programming Basics
  |         Date:  December 20th,2017
  |
  |     Language:  GNU C (using gcc),OS: Arch Linux x86_64)
  |     Version:   0.0
  |   To Compile:  gcc -Wall -xc -g -std=c99 kontrolinis2.c -o kontrolinis_2
  |
  +-----------------------------------------------------------------------------
  |
  |  Description:  The program which gets the input number,which indicates how
  |                many words there will be,then prompts the user to enter
  |                those words,and then displays a histogram in descending 
  |                order by times the word is repeated. The words with the 
  |                same duplicate count are sorted in lexicographical order
  |
  +===========================================================================*/

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

#include "dbg.h"
#include "lib_riddle.h"

#define MAX_STRING 50

// Frequency structure. Contains the word and the times
// it is repeated
typedef struct Freq {
    char* word;
    int times;
} Freq;

// Histogram structure. Contains the list of frequencies (struct)
// and the size of the list.
typedef struct Histogram {
    Freq** freqs;
    int size;
} Histogram;

// sort the portion of the given array of frequency structs
// in lexicographically reverse order (from z to a) by Freq->word attribute.
//
// ::params: target - array continaing frequency structs
// ::params: first - first index of the portion of the array
// ::params: last - last index of the portion of the array
// ::return: Array of frequency structs (portion of which is
// sorted in lexicographically reverse order)
Freq** sort_rlexicographical(Freq** target,int first,int last);

// sort the frequency structs array by their Freq->times
// attribute,using quicksort
//
// ::params: target - the frequency array
// ::params: first - first index of the array
// ::params: first - last index of the array
// ::return: Sorted array of frequency structs
Freq** quicksort_freqs(Freq** target,int last);

// print Frequency array in reverse order,which displays
// the data as in historgram (from bigger to smaller)
//
// ::params: target - the frequency array
// ::params: size - size of the array
void print_reverse(Freq** target,int size);



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

    // get number from the user
    int size = get_pos_num("Please enter a number of words > ",0);

    Histogram* histogram = malloc(sizeof(Histogram));
    histogram->freqs = malloc(size * sizeof(Freq*));
    histogram->size = 0;

    char** words = (char**)malloc(size * sizeof(char*));
    for (int i = 0; i < size; i++) {
        words[i] = (char*)malloc(MAX_STRING * sizeof(char));
    }

    // get words from the user
    for (int i = 0; i < size; i++) {
        words[i] = get_word("Enter word > ",words[i]);
    }

    int duplicates;
    int is_duplicate;
    int hist_size = 0;

    // initialize the array of duplicates
    char** duplicated = (char**)malloc(size * sizeof(char*));
    for (int i = 0; i < size; i++) {
        duplicated[i] = (char*)calloc(MAX_STRING+1,sizeof(char));
        /*duplicated[i] = (char*)malloc(MAX_STRING);*/
        /*duplicated[i] = (char*)calloc(MAX_STRING + 1,sizeof(char));*/
    }

    // count the duplicates of each word and add the word with its duplicate count
    // to the frequency array,and then - to the histogram struct. Each word is
    // writtern once,without duplication.
    for (int i = 0; i < size; i++) { 
        is_duplicate = 0;

        // if the word is already added to the duplicate list,// it means that its duplicates are already counted,// so the loop iteration is skipped
        for (int k = 0; k < size; k++) {
            if (strcmp(duplicated[k],words[i]) == 0) {
                is_duplicate = 1;
            }
        }

        // skipping the loop iteration
        if (is_duplicate) {
            continue;
        }

        // found the word about which we are not yet sure
        // whether it has any duplicates.
        duplicates = 1;
        Freq* freq = malloc(sizeof(Freq));
        freq->word = (char*)malloc(sizeof(MAX_STRING * sizeof(char)));
        freq->word = words[i];
        // searching for the duplicates
        for (int j = i + 1; j < size; j++) {
            if (strcmp(words[i],words[j]) == 0) {
                // in case of a duplicate
                // put word in duplicates array
                // and increase its duplicates count
                duplicated[i] = words[i];
                duplicates++;
            }
        }
        freq->times = duplicates;
        histogram->freqs[histogram->size++] = freq;
        hist_size++;
    }

    debug("Frequency table:");
    for (int i = 0; i < hist_size; i++) {
        debug("%s %d",histogram->freqs[i]->word,histogram->freqs[i]->times);
    }
    debug("-----------------------");

    histogram->freqs = quicksort_freqs(histogram->freqs,hist_size - 1);

    debug("Sorted frequency table:");
    for (int i = hist_size - 1; i >= 0; i--) {
        debug("%s %d",histogram->freqs[i]->times);
    }
    debug("-----------------------");

    int max_count = histogram->freqs[hist_size - 1]->times;
    int index = hist_size - 1;
    int index_max;

    // partition the frequency array by the same duplicate times,and
    // pass the partitioned array to reverse lexicographical sort
    // on the go.
    for (int i = max_count; i > 0 && index >= 0; i--) {
        index_max = index;
        if (histogram->freqs[index]->times == i) {
            while (index - 1 >= 0 && histogram->freqs[index - 1]->times == i) {
                index--;
            }
            if (index != index_max) {
                histogram->freqs = sort_rlexicographical(
                    histogram->freqs,index,index_max);
            }
            index--;
        }
    }

    printf("\nLexicographically sorted frequency table:\n");
    print_reverse(histogram->freqs,hist_size);




    for (int i = 0; i < size; i++) {
        free(duplicated[i]);
    }
    free(duplicated);

    for (int i = 0; i < size; i++) {
        free(words[i]);
    }
    free(words);

    for (int i = 0; i < hist_size; i++) {
        free(histogram->freqs[i]->word);
    }

    for (int i = 0; i < hist_size; i++) {
        free(histogram->freqs[i]);
    }
    free(histogram->freqs);
    free(histogram);


    return 0;
}

Freq** quicksort_freqs(Freq** target,int last)
{
    Freq* temp;
    int pivot,j,i;

    if (first < last) {
        pivot = first;
        i = first;
        j = last;

        while (i < j) {
            while (target[i]->times <= target[pivot]->times && i < last) {
                i++;
            }
            while (target[j]->times > target[pivot]->times) {
                j--;
            }
            if (i < j) {
                temp = target[i];
                target[i] = target[j];
                target[j] = temp;
            }
        }
        temp = target[pivot];
        target[pivot] = target[j];
        target[j] = temp;

        quicksort_freqs(target,first,j - 1);
        quicksort_freqs(target,j + 1,last);
    }
    return target;
}

Freq** sort_rlexicographical(Freq** target,int last) 
{
    int i,j;
    Freq* temp;

    for (i = first; i < last; ++i)

        for (j = i + 1; j < last + 1; ++j) {

            if (strcmp(target[i]->word,target[j]->word) < 0) {
                temp = target[i];
                target[i] = target[j];
                target[j] = temp;
            }
        }

    debug("In lexicographical reverse order:");
    for (i = 0; i < last + 1; ++i) {
        debug("%s",target[i]->word);
    }
    debug("-----------------------");

    return target;
}

void print_reverse(Freq** target,int size) {
    for (int i = size - 1; i >= 0; i--) {
        printf("%s ",target[i]->word);
        printf("%d \n",target[i]->times);
    }
}

积分无效：

196    for (int i = 0; i < size; i++) {
197        free(words[i]);
198    }

和：

201    for (int i = 0; i < hist_size; i++) {
202        free(histogram->freqs[i]->word);
203    }

我的行动计划：

➜  tmp1 ./kontrolinis2
Please enter a number of words > 4
Enter word > test1
Enter word > test1
Enter word > test2
Enter word > test2
DEBUG kontrolinis2.c:150: Frequency table:
DEBUG kontrolinis2.c:152: test1 2
DEBUG kontrolinis2.c:152: test2 2
DEBUG kontrolinis2.c:154: -----------------------
DEBUG kontrolinis2.c:158: Sorted frequency table:
DEBUG kontrolinis2.c:160: test1 2
DEBUG kontrolinis2.c:160: test2 2
DEBUG kontrolinis2.c:162: -----------------------
DEBUG kontrolinis2.c:264: In lexicographical reverse order:
DEBUG kontrolinis2.c:266: test2
DEBUG kontrolinis2.c:266: test1
DEBUG kontrolinis2.c:268: -----------------------

Lexicographically sorted frequency table:
test1 2
test2 2

Valgrind输出(使用相同的“用户”输入)：

Lexicographically sorted frequency table:
test1 2
test2 2
==9430== Invalid free() / delete / delete[] / realloc()
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x1091D4: main (kontrolinis2.c:197)
==9430==  Address 0x51f19d0 is 0 bytes inside a block of size 50 free'd
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109194: main (kontrolinis2.c:192)
==9430==  Block was alloc'd at
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108C77: main (kontrolinis2.c:89)
==9430==
==9430== Invalid free() / delete / delete[] / realloc()
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109217: main (kontrolinis2.c:202)
==9430==  Address 0x51f1ad0 is 0 bytes inside a block of size 50 free'd
==9430==    at 0x4C2E14B: free (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x109194: main (kontrolinis2.c:192)
==9430==  Block was alloc'd at
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108C77: main (kontrolinis2.c:89)
==9430==
==9430==
==9430== HEAP SUMMARY:
==9430==     in use at exit: 118 bytes in 4 blocks
==9430==   total heap usage: 18 allocs,18 frees,2,612 bytes allocated
==9430==
==9430== 16 bytes in 2 blocks are definitely lost in loss record 1 of 2
==9430==    at 0x4C2CE5F: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108DC7: main (kontrolinis2.c:133)
==9430==
==9430== 102 bytes in 2 blocks are definitely lost in loss record 2 of 2
==9430==    at 0x4C2EF35: calloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==9430==    by 0x108D23: main (kontrolinis2.c:104)
==9430==
==9430== LEAK SUMMARY:
==9430==    definitely lost: 118 bytes in 4 blocks
==9430==    indirectly lost: 0 bytes in 0 blocks
==9430==      possibly lost: 0 bytes in 0 blocks
==9430==    still reachable: 0 bytes in 0 blocks
==9430==         suppressed: 0 bytes in 0 blocks
==9430==
==9430== For counts of detected and suppressed errors,rerun with: -v
==9430== ERROR SUMMARY: 6 errors from 4 contexts (suppressed: 0 from 0)

纠正我是否应该粘贴整个程序,而不是它的主要部分,或某种工作原型.但是,这里的主要细节
是包含关键字“malloc”和“free”的行.

更新：
从库中添加两个函数,用于此处：“get_pos_num”和“get_word”：

char* get_word(char* message,char* output)
{

    while (1) {
        printf("%s",message);
        if (scanf("%s",output) == 1 && getchar() == '\n') {
            break;
        } else {
            while (getchar() != '\n')
                ;
            printf("Error: not a string,or too many arguments\n");
        }
    }

    return output;
}

int get_pos_num(char* message,int zero_allowed)
{
    int num;
    int margin;

    if (zero_allowed) {
        margin = 0;
    } else {
        margin = 1;
    }

    while (1) {
        printf("%s",message);
        if (scanf("%d",&num) == 1 && getchar() == '\n') {
            if (num >= margin) {
                break;
            } else {
                printf("Error: number is not positive");
                if (zero_allowed) {
                    printf(" or zero");
                }
                printf("\n");
            }
        } else {
            while (getchar() != '\n')
                ;
            printf("Error: not a number\n");
        }
    }

    return num;
}