问追踪分段故障11

EN

/*
 * File:        set.h
 *
 * Copyright:   2015, Darren C. Atkinson
 *
 * Description: This file contains the public function and type
 *              declarations for a set abstract data type for strings.  A
 *              set is an unordered collection of distinct elements.
 *
 *              Note that this file uses the bool type, but does not define
 *              it.  You should include <stdbool.h> beforehand.
 */

# ifndef SET_H
# define SET_H

typedef struct set 
{
    char **elts; //char * array containing strings
    int length; //total length of array
    int size; //number of strings within array
}SET;


SET *createSet(int maxElts);

void destroySet(SET *sp);

int numElements(SET *sp);

bool hasElement(SET *sp, char *elt);

bool addElement(SET *sp, char *elt);

bool removeElement(SET *sp, char *elt);

# endif /* SET_H */

/*
 * File:        unique.c
 *
 * Copyright:   2015, Darren C. Atkinson
 *
 * Description: This file contains the main function for testing a set
 *              abstract data type for strings.
 *
 *              The program takes two files as command line arguments, the
 *              second of which is optional.  All words in the first file
 *              are inserted into the set and the counts of total words and
 *              total words in the set are printed.  If the second file is
 *              given then all words in the second file are deleted from
 *              the set and the count printed.
 */

# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <stdbool.h>
# include "set.h"


/* This is sufficient for the test cases in /scratch/coen12. */

# define MAX_SIZE 18000


/*
 * Function:    main
 *
 * Description: Driver function for the test application.
 */

int main(int argc, char *argv[])
{
    FILE *fp;
    char buffer[BUFSIZ];
    SET *unique;
    int words;


    /* Check usage and open the first file. */

    if (argc == 1 || argc > 3) {
        fprintf(stderr, "usage: %s file1 [file2]\n", argv[0]);
        exit(EXIT_FAILURE);
    }

    if ((fp = fopen(argv[1], "r")) == NULL) {
        fprintf(stderr, "%s: cannot open %s\n", argv[0], argv[1]);
        exit(EXIT_FAILURE);
    }


    /* Insert all words into the set. */

    words = 0;
    unique = createSet(MAX_SIZE);

    while (fscanf(fp, "%s", buffer) == 1) {
        words ++;
        addElement(unique, buffer);
    }

    printf("%d total words\n", words);
    printf("%d distinct words\n", numElements(unique));
    fclose(fp);


    /* Try to open the second file. */

    if (argc == 3) {
        if ((fp = fopen(argv[2], "r")) == NULL) {
            fprintf(stderr, "%s: cannot open %s\n", argv[0], argv[2]);
            exit(EXIT_FAILURE);
        }


        /* Delete all words in the second file. */

        while (fscanf(fp, "%s", buffer) == 1)
            removeElement(unique, buffer);

        printf("%d remaining words\n", numElements(unique));
    }

    destroySet(unique);
    exit(EXIT_SUCCESS);
}

/*
 * File:        unsorted.c
 *
 *
 * Description: This file contains the definitions for a simple interface for a SET structure that contains a list of strings as well as the list size.
 */
#include <assert.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include "set.h"

int findElement(SET *sp,char *elt);

struct SET
{
    char **elts; //char * array containing strings
    int length; //total length of array
    int size; //number of strings within array
};

//initializes SET
//O(1) efficiancy
SET *createSet(int maxElts)
{
    SET *sp; 
    sp->elts = (char **) malloc(sizeof(char*)*maxElts);
    assert(sp->elts!=NULL);
    sp->size = 0;
    sp->length = maxElts;
    return sp;
}

//frees all strings from memory and then the containing array
//O(n) efficiancy n==sp->size
void destroySet(SET *sp)
{
    while (sp->size > 0) free(sp->elts[--sp->size]);
    free(sp->elts);
}

//return the number of strings within the array
//O(1) efficiency
int numElements(SET *sp)
{
    return sp->size;
}

//Sequentially searches SET for elt and return the array location, if not found -1 is returned
//O(n) efficiency n=sp->size
int findElement(SET *sp,char *elt)
{
    int i =0;
    for (i; i < sp->size; i++)
    {
        if (strcmp(sp->elts[i],elt) == 0) return i;
    }
    return -1;
}

//appends elt on the end of the array within SET
//O(1) efficiency
bool addElement(SET *sp, char *elt)
{
    if (findElement(sp, elt) != -1) return false;
    if (sp->size == sp->length) return false;
    sp->elts[sp->size] = (char*) malloc(sizeof(char)*(strlen(elt)+1));
    assert(sp->elts[sp->size]!=NULL);
    sp->size = sp->size +1;
    return true;
}

//returns true if SET contains elt otherwise return false
//O(n) efficiency n=sp->size
bool hasElement(SET *sp, char *elt)
{
    if (findElement(sp,elt) == -1) return true;
    return false;
}

//finds elt and removes it from array if present, then moves all following strings forward in the array
//O(n) efficiency n=sp->size
bool removeElement(SET *sp,char *elt)
{
    int loc = findElement(sp,elt);
    if (loc == -1) return false;
    free(sp->elts[loc]);
    while (loc <sp->size)
    {
        sp->elts[loc] = sp->elts[loc+1];
        loc++;
    }
    sp->size=sp->size-1;
    return true;
}