Lesedatei in verketteten Liste

Question

Ich versuche, eine Textdatei zu lesen, ich in einer verknüpften Liste gemacht, sieht die Textdatei wie folgt aus:

around 1 2 1 
bread 2 4 3 5 1 
four 1 3 2 
head 3 1 2 2 1 5 1 
has 2 3 1 5 2 

Wenn die erste Zeichenfolge jeder Zeile sind nur Worte aus einem Absatz . Die erste Zahl nach dem Wort ist die Anzahl der Zeilen, in denen das Wort im Absatz gefunden wurde. Dann sind die folgenden Zahlen Paare von (Zeile, Vorkommen) im Absatz.

Zum Beispiel für das Wort bread:

Es wurde in 2 Zeilen im Absatz gefunden. In der ersten Zeile, Zeile 4, wurde 3 mal gefunden. Dann wurde in der zweiten Zeile, Zeile 5, 1 Zeit gefunden.

Ich versuche, eine verknüpfte Liste aus dieser Textdatei zu erstellen, sieht mein Programm wie diese bisher:

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

#define MAXWORD 999 

typedef struct node node_t; 

struct node { 
    char *word; 
    int num_lines; 
    int paragraph; 
    int freq; 
    node_t *next; 
}; 

int 
main(int argc, char *argv[]) { 
    FILE *fp; 
    char word[MAXWORD+1]; 
    int ch, line_count = 0, len = 0; 
    node_t *node = (node_t*)malloc(sizeof(*node)); 
    node_t *curr, *prev; 

    fp = fopen(argv[1], "r"); 

    if (fp == NULL) { 
     fprintf(stderr, "Error reading file\n"); 
     exit(EXIT_FAILURE); 
    } 

    /* Just trying to store the string so far */ 
    while ((ch = getc(fp)) != EOF) { 
     if (ch == '\n') { 
      line_count++; 
      strcpy(node->word, word); 
     } 

     if (isalpha(ch)) { 
      word[len] = ch; 
      len++; 
      word[len] = '\0'; 
     } 

     if (isdigit(ch)) { 
      len = 0; 
     } 
    } 

    printf("line count = %d", line_count); 

    free(node) 

    fclose(fp); 

    return 0; 
} 

In diesem Code-Schnipsel, ich habe die Zeichenfolge in der verknüpften Listendatenstruktur zu speichern versucht, , aber ich habe noch nicht dynamische Arrays verwendet, um die Zahlen nach dem Wort zu speichern, die in der Textdatei vorkommen. Ich weiß, dass ich diese Datenstruktur mit malloc() und realloc() bauen muss, aber ich bin mir nicht sicher, wie man das macht.

Wie soll ich das tun?

Meine gewünschte Ausgabe würde wie folgt aussehen:

There are five words in the text file, 
and 9 pairs of (line, occurences) 

Word: pairs 
"around": 2,1 
"bread": 4,3; 5,1 
"four": 3,2 
"head": 1,2; 2,1; 5,1 
"has": 3,1; 5,2 

UPDATE

Ich habe dies erforscht, und es scheint mit dem invertierten Index Problem sehr ähnlich zu sein, wo ich, dass die Verwendung gesehen habe ein binärer Suchbaum wäre am besten.

Könnte ich meine binäre Suchbaum wie folgt implementieren:

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

#define MAXWORD 999 

typedef char word_t[MAXWORD+1]; 

typedef struct node node_t; 

struct node { 
    void *data; 
    int *ints; 
    node_t *rght; 
    node_t *left; 
}; 

typedef struct { 
    node_t *root; 
    int (*cmp)(void*, void*); 
} tree_t; 

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

    fp = fopen(argv[1], "r"); 

    if (fp == NULL) { 
     fprintf(stderr, "Error reading file\n"); 
     exit(EXIT_FAILURE); 
    } 

    while ((ch = getc(fp)) != EOF) { 
     if (ch == '\n') { 
      line_count++; 
     } 
    } 

    fclose(fp); 

    return 0; 
} 

Answer 1

Hier ist meine Version mit binärer Suchbaum (BST):

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

typedef struct internal_node in_node; 

struct internal_node{ 
    int line; 
    int freq; 
    in_node* next; 
}; 

struct tree{ 
    char *word; 
    int num_lines; 
    in_node* in_nodeptr; 
    in_node* current; 
    struct tree* right; 
    struct tree* left; 
}; 

typedef struct tree* treeptr; 

void free_list(in_node* in_nodeptr){ 
    if(in_nodeptr!=NULL) { 
    free(in_nodeptr); 
    } 
} 

void free_bst(treeptr head){ 
    if (head!=NULL) { 
    free_bst(head->right); 
    free_bst(head->left); 
    free_list(head->in_nodeptr); 
    free(head->word); 
    free(head); 
    } 
} 

void print_list(in_node* in_nodeptr){ 
    while(in_nodeptr!=NULL){ 
     printf("%d %d; ",in_nodeptr->line,in_nodeptr->freq); 
     in_nodeptr=in_nodeptr->next; 
    } 
} 

void print_bst(treeptr head){ 
    if(head!=NULL){ 
    printf("%s: ",head->word); 
    print_list(head->in_nodeptr); 
    printf("\n"); 
    print_bst(head->right); 
    print_bst(head->left); 
    } 
} 

void input_to_bst(treeptr* head,char* word,int line){ 
    if((*head)==NULL){ 
     (*head)=(treeptr)malloc(sizeof(struct tree)); 
     (*head)->word=(char*)malloc(50*sizeof(char)); 
     strcpy(((*head)->word),word); 

     (*head)->num_lines=1; 
     (*head)->right=NULL; 
     (*head)->left=NULL; 
     (*head)->in_nodeptr=(in_node*)malloc(sizeof(in_node)); 
     (*head)->in_nodeptr->line=line; 
     (*head)->in_nodeptr->freq=1; 
     (*head)->in_nodeptr->next=NULL; 
     (*head)->current=(*head)->in_nodeptr; 
    } 
    else{ 
     int check=strcmp(((*head)->word),word); 
     if(check>0) input_to_bst(&((*head)->left),word,line); 
     else if(check<0) input_to_bst(&((*head)->right),word,line); 
     else{ 
      if((*head)->current->line==line) (*head)->current->freq++; 
      else { 
       (*head)->current->next=(in_node*)malloc(sizeof(in_node)); 
       (*head)->current->next->line=line; 
       (*head)->current->next->freq=1; 
       (*head)->current->next->next=NULL; 
      } 
     } 
    } 
} 

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

    treeptr head=NULL; 
    FILE *fp=fopen(argv[1], "r"); 
    char word[50],ch; 
    int len=0,lines=1; 

    if (fp == NULL) { 
     fprintf(stderr, "Error reading file\n"); 
     exit(1); 
    } 

    while ((ch = getc(fp)) != EOF) { 
     if (ch == '\n') { 
      word[len]='\0'; 
      if(len>0) input_to_bst(&head,word,lines); 
      len=0; 
      lines++; 
     } 
     else if (ch==' '){ 
      word[len]='\0'; 
      if(len>0) input_to_bst(&head,word,lines); 
      len=0; 
     } 
     else if (isalpha(ch)){ 
      word[len]=ch; 
      len++; 
     } 
    } 
    if(len>0) { 
     word[len]='\0'; 
     input_to_bst(&head,word,lines); 
    } 
    print_bst(head); 
    fclose(fp); 
    free_bst(head); 
    return 0; 
} 

Jedes Wort gehalten wird als ein Knoten der BST und auch jeder Knoten von BST außer dem Wort, hält eine Liste mit allen Erscheinungen (Zeilen und Häufigkeit) des Wortes. Um so effizient wie möglich zu sein, halten wir einen Zeiger (in_node* current) auf das letzte Element der Erscheinungsliste, so dass wir nicht jedes Mal, wenn wir eine Erscheinung hinzufügen müssen, durchqueren müssen.

Als Beispiel:

Text:

C is an imperative procedural language. It was designed to be compiled 
using a relatively straightforward compiler and to require minimal 
runtime support. 

Ausgang:

C: 1 1; 
is: 1 1; 
procedural: 1 1; 
was: 1 1; 
to: 1 1; 2 1; 
using: 2 1; 
relatively: 2 1; 
straightforward: 2 1; 
support: 3 1; 
require: 2 1; 
runtime: 3 1; 
language: 1 1; 
minimal: 2 1; 
an: 1 1; 
imperative: 1 1; 
designed: 1 1; 
be: 1 1; 
compiled: 1 1; 
compiler: 2 1; 
and: 2 1; 
It: 1 1; 
a: 2 1; 

Beachten Sie, dass die obige Implementierung Groß- und Kleinschreibung ist zum Beispiel "Und" unterscheidet sich von "und". Wenn Sie nicht zwischen Groß- und Kleinschreibung unterscheiden möchten, ersetzen Sie einfach die Zeile word[len]=ch; durch word[len]=tolower(ch); und funktioniert gut. Die Komplexität des oben genannten Algorithmus ist O (n^2), die die gleiche wäre, wenn Sie nur verknüpfte Listen verwendet, aber im Durchschnitt Fall BST ist O (nlogn) was viel besser als verknüpfte Listen ist und dies ist der Grund dafür gilt als der bessere. Beachten Sie auch, dass, da wir eine Liste für Aussehen jedes Wortes halten müssen, die Komplexität am schlimmsten wäre, wenn wir nicht den Zeiger in_node* current behalten würden, der uns Zugang zum Ende jeder Erscheinungsliste in konstanter Zeit gibt (O (1)). Also denke ich, dass man als Terme der Komplexität nicht besser gehen kann als O (nlogn).

Answer 2

Sie so etwas tun könnte:

typedef struct { 
    int paragraph; 
    int freq; 
} stats_t; 

struct node { 
    char *word; 
    int num_lines; 
    stats_t *stats; 
    node_t *next; 
}; 

Dann, nachdem Sie die Zeichenfolge analysieren Sie tun können:

ps = calloc(line_count, sizeof(stats_t)); 

, um einen Zeiger auf ein Array von stats_t Strukturen zu erhalten, die Sie mit Zeilenpositionen und Frequenz füllen können cies. Dann können Sie den Zeiger ps in Ihrer Struktur node speichern.

Answer 3

Ich schrieb ein Programm, das tut, was ich denke, dass Sie suchen. Ich änderte die structs Ich dachte an vor:

typedef node node_t; 

struct node { 
    char *word; 
    int num_lines; 
    int *location; 
    int *frequency; 
    node_t *next; 
}; 

diese Weise können die Knoten Zeiger auf Arrays von int enthalten den Ort und die Frequenzinformationen zu speichern. Knoten und Speicher für die Wortstrings, Standortarrays und Frequenzarrays werden alle dynamisch zugewiesen. Hier ist der Code:

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

#define MAXLINE 1000 
#define MAXWORD 30 

typedef struct node node_t; 

struct node { 
    char *word; 
    int num_lines; 
    int *location; 
    int *frequency; 
    node_t *next; 
}; 

void strip(char *pln); 
void normalize_word(char *pstr); 
struct node * update_word(char *pwd, int lnum, struct node *phead); 
struct node * find_in_list(char *pwd, struct node *phead); 
int find_line_pair(int lnum, struct node *pwn); 
int list_len(struct node *phead); 
int num_pairs(struct node *phead); 

int main(int argc, char *argv[]) 
{ 
    FILE *fp; 
    struct node *head, *current; 
    char *pline, *pword; 
    char line[MAXLINE + 1]; 
    char word[MAXWORD + 1]; 
    int i, n, line_count = 0; 

    head = NULL; 

    if (argc < 2) { 
     fprintf(stderr, "Usage: %s filename\n", argv[0]); 
     exit(EXIT_FAILURE); 
    } else {   
     if ((fp = fopen(argv[1], "r")) == NULL) { 
      fprintf(stderr, "Unable to open file %s\n", argv[1]); 
      exit(EXIT_FAILURE); 
     } 
    } 

    /* Read in lines and process words */ 
    pline = line; 
    pword = word; 
    while (fgets(pline, MAXLINE, fp) != NULL) { 
     ++line_count; 
     strip(pline); 
     while ((pword = strtok(pline, " ")) != NULL) { 
      normalize_word(pword); 
      if (*pword != '\0')  // don't add empty words 
       head = update_word(pword, line_count, head); 
      pline = NULL; 
     } 
     pline = line; 
    } 

    /* Display list contents */ 
    printf("There are %d words in the text file,\n", 
      list_len(head)); 
    printf("and %d pairs of (line, occurrences)\n", 
      num_pairs(head)); 
    printf("Word: pairs\n"); 
    current = head; 
    while (current != NULL) { 
     n = current->num_lines; 
     printf("%s:", current->word); 
     for (i = 0; i < n; i++) { 
      printf(" %d, %d;", 
        current->location[i], current->frequency[i]); 
     } 
     putchar('\n'); 
     current = current->next; 
    } 

    /* Cleanup */ 
    // close file 
    if (fclose(fp) != 0) 
     fprintf(stderr, "Error closing file %s\n", argv[1]); 

    // free all allocated memory 
    current = head; 
    while (current != NULL) { 
     free(current->word); 
     free(current->location); 
     free(current->frequency); 
     current = current->next; 
     free(head); 
     head = current; 
    } 

    return 0; 
} 

/* Remove trailing newlines */ 
void strip(char *pln) 
{ 
    while (*pln != '\0') { 
     if (*pln == '\n') 
      *pln = '\0'; 
     ++pln; 
    } 
} 

/* Convert word to lowercase and remove trailing 
* non-alphanumeric characters     */ 
void normalize_word(char *pstr) 
{ 
    int i = 0; 
    char ch; 

    while ((ch = pstr[i]) != '\0') { 
     pstr[i] = tolower(ch); 
     ++i; 
    } 
    while ((--i >= 0) && !isalnum(pstr[i])) { 
     pstr[i] = '\0'; 
     continue; 
    } 
} 

/* Update existing word node or create a new one, and return 
* a pointer to the head of the list */ 
struct node * update_word(char *pwd, int lnum, struct node *phead) 
{ 
    struct node *found, *newnode; 
    char *pword; 
    int *ploc, *pfreq; 
    int index; 

    /* Modify existing node if word is in list */ 
    if ((found = find_in_list(pwd, phead)) != NULL) { 
     // add new (location, freq) pair if word not in found line 
     if ((index = find_line_pair(lnum, found)) == -1) { 
      index = found->num_lines; // index for new pair 
      found->num_lines += 1;  // increment number of lines 
      ploc = realloc(found->location, (index + 1) * sizeof(int)); 
      pfreq = realloc(found->frequency, (index + 1) * sizeof(int)); 
      ploc[index] = lnum;  // new location 
      pfreq[index] = 1;   // found once in this line so far 
      found->location = ploc; // point to new location array 
      found->frequency = pfreq; // point to new frequency array 
     } 
     else { // update frequency in existing line 
      found->frequency[index] += 1; 
     } 
    /* Set up a new node */ 
    } else { 
     // allocate memory for new node 
     newnode = malloc(sizeof(struct node)); 
     // allocate memory for string pointed to from node 
     pword = malloc((strlen (pwd) + 1) * sizeof(char)); 
     strcpy(pword, pwd); 
     newnode->word = pword;  // set word pointer 
     newnode->num_lines = 1;  // only one line so far 
     ploc = malloc(sizeof(int)); 
     pfreq = malloc(sizeof(int)); 
     *ploc = lnum;    // location was passed by caller 
     *pfreq = 1;     // only one occurrence so far 
     newnode->location = ploc; 
     newnode->frequency = pfreq; 

     if (phead == NULL) {  // if wordlist is empty 
      newnode->next = NULL; // only/last link in the list 
      phead = newnode;  // newnode is the head 
     } else { 
      newnode->next = phead; // insert newnode at front of list 
      phead = newnode; 
     } 
    } 

    return phead; 
} 

/* Return pointer to node containing word, or NULL */ 
struct node * find_in_list(char *pwd, struct node *phead) 
{ 
    struct node *current = phead; 

    while (current != NULL) { 
     if (strcmp(current->word, pwd) == 0) 
      return current;   // word already in list 
     current = current->next; 
    } 

    return NULL;     // word not found 
} 

/* Return index of existing line location, or -1 */ 
int find_line_pair(int lnum, struct node *pwn) 
{ 
    int n = pwn->num_lines; 
    int index = 0; 

    while (index < n) { 
     if (pwn->location[index] == lnum) 
      return index;   // word already found in this line 
     ++index; 
    } 

    return -1;      // word not yet found in this line 
} 

/* Find number of nodes in linked list */ 
int list_len(struct node *phead) 
{ 
    int length = 0; 
    struct node *current = phead; 

    while (current != NULL) { 
     ++length; 
     current = current->next; 
    } 

    return length; 
} 

/* Find number of (line, occurrence) pairs */ 
int num_pairs(struct node *phead) 
{ 
    int num = 0; 
    struct node *current = phead; 

    while (current != NULL) { 
     num += current->num_lines; 
     current = current->next; 
    } 

    return num; 
} 

Hinweis: ich dies aus der vorherigen Version in der update_word() Funktion geändert.Der ursprüngliche Code hat am Ende der Liste einen neuen Knoten eingefügt, sodass die resultierende Liste Wörter in der Reihenfolge ihres ersten Auftretens im Eingabetext enthielt. Diese Version fügt einen neuen Knoten am Anfang der Liste ein, so dass die resultierende Liste Wörter in umgekehrter Reihenfolge ihrer ersten Erscheinung enthält. Dies beschleunigt Knoten Einfügen und vereinfacht den Knoten-Platzhalter-Code aus:

current = phead; 
while (current->next != NULL) // find tail 
    current = current->next; 
current->next = newnode;  // add newnode to end 

zu:

newnode->next = phead; // insert newnode at front of list 

habe ich keinen Zweifel, dass der Code verbessert werden kann, aber das zu funktionieren scheint. Ich würde nicht sagen, dass das genau so einfach ist, aber relativ einfach. Ich lief es gegen diese Textdatei:

Three blind mice. Three blind mice. 
See how they run. See how they run. 
They all ran after the farmer's wife, 
Who cut off their tails with a carving knife, 
Did you ever see such a sight in your life, 
As three blind mice? 

Hier sind die Ergebnisse:

There are 31 words in the text file, 
and 37 pairs of (line, occurrences) 
Word: pairs 
as: 6, 1; 
life: 5, 1; 
your: 5, 1; 
in: 5, 1; 
sight: 5, 1; 
such: 5, 1; 
ever: 5, 1; 
you: 5, 1; 
did: 5, 1; 
knife: 4, 1; 
carving: 4, 1; 
a: 4, 1; 5, 1; 
with: 4, 1; 
tails: 4, 1; 
their: 4, 1; 
off: 4, 1; 
cut: 4, 1; 
who: 4, 1; 
wife: 3, 1; 
farmer's: 3, 1; 
the: 3, 1; 
after: 3, 1; 
ran: 3, 1; 
all: 3, 1; 
run: 2, 2; 
they: 2, 2; 3, 1; 
how: 2, 2; 
see: 2, 2; 5, 1; 
mice: 1, 2; 6, 1; 
blind: 1, 2; 6, 1; 
three: 1, 2; 6, 1;