Using linkedlist to store txt's sentences

Question

Sorry for my poor code, but I can't understand why this code causes segmentation fault 11 when I run this on my mac terminal. I want to make the program read full sentences intact one by one using linked list, but it doesn't work. I guess sentences in some.txt aren't getting inserted in linkNode. How can I fix it?

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NUMBER 1024 

typedef struct linkNode {
    char *element;
    struct linkNode *link;
} linkNode;

typedef struct {
    linkNode *top;
    int element_number;
} linkType;

void error(char* message) {
    fprintf(stderr, "%s", message);
}

void init(linkType *L) {
    L->top = NULL;
    L->element_number = 0;
}

linkNode *createStack() {
    linkNode *temp = (linkNode *) malloc(sizeof(linkNode));
    temp->element = (char *) malloc(sizeof(char) * MAX_NUMBER + 1);
    return temp;
}

void insert(linkType *L, char* new_data) {
    linkNode *temp = createStack();
    //temp->element = new_data;
    strcpy(temp->element, new_data);
    temp->link = L->top;
    L->element_number++;
    L->top = temp->link;    
}

char *delete(linkType *L) {
    if (L->element_number == 0) {
        error("list empty\n");
    }
    linkNode *temp = L->top;
    char * temp_element;
    //temp->element = L->top->element;
    strcpy(temp_element, L->top->element);
    L->top = L->top->link;
    L->element_number--;
    free(temp);
    return temp_element;
}

char *buffer_making() {
    char *buffer = (char *) malloc(sizeof(char) * MAX_NUMBER + 1);
    return buffer;
}

char *buffer_erase(char *buffer) {
    free(buffer);
    return NULL;
}

int main() {
    linkType *q = (linkType *) malloc(sizeof(linkType));
    init(q);
    FILE *file_pointer; 
    char *file1;
    file1 = (char *) malloc(sizeof(file1) + 1); 
    char *file2;
    file2 = (char *) malloc(sizeof(file2) + 1);
    printf("input file names:\n");
    scanf("%s", file1);
    getchar();
    file_pointer = fopen(file1, "r");
    while (!feof(file_pointer)) {
        char *buffer1 = buffer_making();
        fscanf(file_pointer,"%s",buffer1);
        ///////////
        printf("%s\n",buffer1);
        insert(q,buffer1);
        buffer_erase(buffer1);
    }

    printf("point3\n");
    while (!(q->element_number == 0)) {
        printf("%s\n", delete(q));
    }
    free(file1);
    free(file2);

    return 0;
}

//printf("point1\n");

Answer 1

There are quite a few different issues with your code. Let's go through them one-by-one:

It would be easier to add new elements to the linked list if you keep track of the last node of the list. So you should add another linkNode pointer called bottom to your linkType struct like so:

typedef struct {
    linkNode *top;
    linkNode *bottom;
    int element_number;
} linkType;

And initialize bottom in the init function:

void init(linkType *L) {
    L->top = NULL;
    L->bottom = NULL;
    L->element_number = 0;
}

In the insert function, temp is the new node that you want to append to the end of the list (if I understand your question correctly), so you need to point its link to NULL instead of top. Also, you should not point top to temp->link. If this is the first node you are inserting, top and bottom should both point to temp, otherwise top will keep pointing to the first node and bottom will need to be updated so that it points to temp:

void insert(linkType *L, char *new_data) {
    linkNode *temp = createStack();
    strcpy(temp->element, new_data);
    temp->link = NULL;
    L->element_number++;

    if (L->top == NULL) {
        L->top = temp;
        L->bottom = temp;
    } else {
        L->bottom->link = temp;
        L->bottom = temp;
    }
}

In delete function, you don't need to copy the whole string from element to temp_element; you can just point temp_element to element. Also, you aren't decrementing element_number correctly. The delete function should look like:

char *delete(linkType *L) {
    if (L->element_number == 0) {
        error("list empty\n");
    }
    linkNode *temp = L->top;
    char *temp_element;
    temp->element = L->top->element;
    L->top = L->top->link;
    (L->element_number)--;
    free(temp);
    return temp_element;
}

In the main function, you were not reading the input file correctly. fscanf scans for words, but since you want to extract sentences instead of words, fgetc would be a better approach. The while loop for reading should look like:

int isEof = 0;
int isEndOfSentence = 0;
int index = 0;

while (!isEof) {
    char *buffer1 = buffer_making();
    isEndOfSentence = 0;
    index = 0;

    while (!isEndOfSentence) {
        char c = fgetc(file_pointer);
        if (c == EOF) {
            isEndOfSentence = 1;
            isEof = 1;
        } else if (c == '.') {
            isEndOfSentence = 1;
        }

        // Skip leading whitespace
        if ((isEof || c == ' ' || c == '\n') && index == 0) {
          continue;
        }

        buffer1[index++] = c;
    }

    // Skip empty sentence
    if (index == 0) {
        continue;
    }

    buffer1[index] = '\0';

    printf("%s\n", buffer1);
    insert(q, buffer1);
    buffer_erase(buffer1);
}

This is not the best way to implement reading sentences, but it works. Also, this code assumes that sentences end in .. You can update this code to make it work for sentences that end in ?, !, etc.

Finally, the while loop where you delete as well as print each node's element seems to have some issues. You can instead use the following while loop:

while (!(q->element_number == 0)) {
    printf("%s\n", q->top->element);
    delete(q);
}

Hope this helps. I've tested these changes and they work for me.

Answer 2

From valgrind:

==18918== Conditional jump or move depends on uninitialised value(s)
==18918==    at 0x4C2E119: strlen (vg_replace_strmem.c:458)
==18918==    by 0x4EA4E81: puts (in /lib64/libc-2.25.so)
==18918==    by 0x108BE8: main (ll.c:74)
==18918== 

==18918== Conditional jump or move depends on uninitialised value(s)
==18918==    at 0x4C2E1FB: strcpy (vg_replace_strmem.c:510)
==18918==    by 0x108A49: insert (ll.c:31)
==18918==    by 0x108BFB: main (ll.c:75)
==18918== 

==18918== Invalid read of size 8
==18918==    at 0x108AB1: delete (ll.c:44)
==18918==    by 0x108C31: main (ll.c:82)
==18918==  Address 0x0 is not stack'd, malloc'd or (recently) free'd

gcc also reports an issue with -Wall:

ll.c: In function ‘delete’:
ll.c:44:5: warning: ‘temp_element’ is used uninitialized in this function [-Wuninitialized]
     strcpy(temp_element,L->top->element);

One problem is that you're calling strcpy without allocating memory for the destination. Another problem is that you're dereferencing L->top without verifying it's non-NULL.

Answer 3

with my friends' helps, I could make it print right outcomes in my terminals! special thanks to those who answered my questions! thank you!

Actually what I really wanted was just linked list which indicated by only linkNode *top, I edited what i intended. :)

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NUMBER 1024 
typedef struct linkNode{
    char * element;
    struct linkNode * link;
}linkNode;
typedef struct{
    linkNode *top;
    int element_number;
}linkType;

void error(char* message){
    fprintf(stderr,"%s", message);
}
void init(linkType *L){

    L->top=NULL;
    L->element_number = 0;
}
linkNode * createStack(){
    linkNode * temp = (linkNode *)malloc(sizeof(linkNode));
    temp->element = (char *)malloc(sizeof(char)*MAX_NUMBER+1);
    return temp;
}

void insert(linkType *L,char* new_data){
    linkNode *temp = createStack();
    //temp->element = new_data;
    strcpy(temp->element,new_data);
    temp -> link = NULL;
    L->element_number++;
    if(L->top ==NULL){
        L->top =temp;
    }
    else{
    temp->link = L->top;
    L->top = temp;  
    }
}
char * delete(linkType *L){
    if(L->element_number ==0)
    {
        error("list empty\n");
    }
    linkNode *temp = NULL;
    temp = L->top;
    char * temp_element;
    temp->element = L->top->element;
    L->top = L->top->link;
    (L->element_number)--;
    free(temp);
    return temp_element;
}
char * buffer_making(){
    char* buffer = (char *)malloc(sizeof(char)*MAX_NUMBER+1);
    return buffer;
}
char * buffer_erase(char * buffer){
    free(buffer);
    return NULL;
}
int main(){
    linkType q ;
    init(&q);
    FILE *file_pointer; 
    char * file1;
    file1 = (char*)malloc(sizeof(file1)+1); 
    char * file2;
    file2 = (char*)malloc(sizeof(file2)+1);
    printf("input file names:\n");
    scanf("%s",file1);
    getchar();
    file_pointer=fopen(file1,"r");

    while(1){
    char * buffer1 = buffer_making();
    if(fscanf(file_pointer,"%s",buffer1)==EOF) break;
    ///////////
    printf("%s\n",buffer1);
    insert(&q,buffer1);
    buffer_erase(buffer1);
    }

    printf("point3\n");
    while(!(q.element_number==0))
    {
        printf("%s\n", q.top->element);
        delete(&q);
    }
    free(file1);
    free(file2);
    return 0;
}