Sorting Strings: Binary Search for string
I need help fixing the search method for my program. I have managed to get a variety of errors from "Killed" to "Segmentation Fault: 11" when it comes time to find the number for a word, then use bit operations to toggle that number in the "Set" (array of 10 unsigned ints). I'll post the driver and search code, let me know if you need more code to diagnose the issue.
driver.c
Code:
#include "set.h"#include <stdio.h>
#include <stdlib.h>
// CSE 1040 Alexander Hollis Major Program Assignment 2, [email protected], CSP01
int main() {
printf("Initializing, scanning in your data...\n");
Set set1, set2, rset;
clearSet(set1);
clearSet(set2);
clearSet(rset);
int i, words=0;
for(i=0; (scanf("%s",&names[i]) ) != EOF; i++, words++);
qSort(names, 320);
//char *test [10][30] = {"the","hello","adam","World","car","tree","squirrel","dog","cat"};
//for(i=0; i< 320; i++)
//printf("%s\n",names[i]);
printf("Adding \"seem\" to set1.\n");
addName2Set(set1, "seem");
printf("Adding \"next\" to set1.\n");
addName2Set(set1, "next");
printf("Adding \"head\" to set2.\n");
addName2Set(set2, "head");
printf("Adding \"both\" to set2.\n");
addName2Set(set2 , "both");
printf("Adding \"seem\" to set2.\n");
addName2Set(set2, "seem");
printf("Set1: \n");
printSet(set1);
printf("\n");
printf("Set2: \n");
printSet(set2);
}
search.c
Code:
//CSE 1040 Alexander Hollis, Programming Major Assignment 2, [email protected], CSP03
#include "set.h"
int binarySearch(char *input, char *element, int left, int right) {
int middle = (left + (right - left) ) / 2;
if (left > right) {
return -1;
}
else {
if( strcmp(element,(input + middle)) == 0 ) {
return middle;
}
else {
if( strcmp(element,(input + middle)) < 0 )
{
return (binarySearch(input,element, left, middle -5));
}
else
{
return (binarySearch(input,element, middle + 5, right));
}
}
}
}
set.c (function definitions)
Code:
/* ******************************************************************** *//* */
/* Set.c --- this is the .c file associated with the (major 2) Set */
/* implementation used in Spring 2012's CSCE 1040 class. */
/* */
/* This assignment includes 10 functions to be implemented */
/* in Set.c, namely */
/* */
/* clearSet */
/* add2Set */
/* deleteFromSet */
/* isMember */
/* printSet */
/* setUnion */
/* setIntersection */
/* */
/* And new for major 2 */
/* nameIsMember */
/* addName2Set */
/* deleteNameFromSet */
/* */
/* */
/* */
/* ******************************************************************** */
//CSE 1040 Alexander Hollis, Programming Major Assignment 2, [email protected], CSP03
#include "set.h"
char names[320][30];
// include your code below.
void qSort(char names[320][], int y);
void swap(char *p, char *q);
void clearSet(Set set){
int i;
for(i=0; i<10; i++) set[i]=0;
}
void add2Set(Set set, int value) {
int loc= SetLoc(value);
if (value >= 32) value = (value % 32) -1;
set[loc] = set[loc] | (1 << value);
}
void deleteFromSet(Set set, int value) {
int loc = SetLoc(value);
if(value >=32) value= (value % 32) -1;
set[loc] = set[loc] | (1 << value );
set[loc] = set[loc] ^ (1 << value);
}
int isMember(Set set, int element) {
int loc= SetLoc(element);
if(element >=32) element = (element % 32) -1;
if(set[loc] &= (1 << ((element % 32) ) ) ) return 1;
else return 0;
}
void printSet(Set set) {
int i;
for(i=0; i< 30; i++) {
if( isMember(set, i) ) {
printf("%s\n",names[i]);
}
}
}
int SetLoc(int value) {
int i, location=0;
while(location < 10) {
if(value > 32) {
value = value -32;
location++;
}
else break;
}
return location;
}
int nameIsMember(Set set, char *name) {
int index = binarySearch(names, name, 0, 30);
if( isMember(set, index) ) return 1;
else return 0;
}
void addName2Set(Set set, char *name) {
int index = binarySearch(&names, name, 0, 320);
add2Set(set, index);
}
void deleteNameFromSet(Set set, char *name) {
int index = binarySearch(names, name, 0, 320);
deleteFromSet(set, index);
}
void setUnion(Set set1, Set set2, Set rset) {
int i;
for(i=0; i< 10; i++) {
rset[i] = set1[i] & set2[i];
}
}
void setIntersection(Set set1, Set set2, Set rset) {
int i;
for(i=0; i< 10; i++) {
rset[i] = set1[i] | set2[i];
}
}
Thank you for your feedback, and yes I plan on tiding things up before submission, especially the indentation. Thanks!
Updated Search and Driver
I went and made changes to the search and driver, the search still doesn't finish, it gets killed by linux. I removed the weird "+/- 5 parts" after thinking through what it was doing.
search.c
Code:
//CSE 1040 Alexander Hollis, Programming Major Assignment 2, [email protected], CSP03
#include "set.h"
int binarySearch(char *input, char *element, int left, int right) {
int middle;
middle= (left + (right - left) ) / 2;
if (left > right) {
return -1;
}
else {
if( strcmp(element,(input + middle)) == 0 ) {
printf("I found it yay!!\n");
return middle;
}
else {
if( strcmp(element,(input + middle)) < 0 )
{
//printf("Middle too big, shrinking bounds.\n");
right = middle;
return binarySearch(input,element, left, right);
}
else
{
//printf("Middle too small, middle to left searching...");
left = middle;
return binarySearch(input,element, left, right);
}
}
}
}
driver.c
Code:
#include "set.h"#include <stdio.h>
#include <stdlib.h>
// CSE 1040 Alexander Hollis Major Program Assignment 2, [email protected], CSP01
int main() {
printf("Initializing, scanning in your data...\n");
Set set1, set2, rset;
clearSet(set1);
clearSet(set2);
clearSet(rset);
int i, words=0;
for(i=0; (scanf("%s",names[i]) ) != EOF; i++, words++);
qSort(names, words);
//char *test [10][30] = {"the","hello","adam","World","car","tree","squirrel","dog","cat"};
//for(i=0; i< 320; i++)
//printf("%s\n",names[i]);
char seem[1][5] = {"seem"};
printf("Adding \"seem\" to set1.\n");
addName2Set(set1, seem[0]);
printf("Adding \"next\" to set1.\n");
addName2Set(set1, "next");
printf("Adding \"head\" to set2.\n");
addName2Set(set2, "head");
printf("Adding \"both\" to set2.\n");
addName2Set(set2 , "both");
printf("Adding \"seem\" to set2.\n");
addName2Set(set2, "seem");
printf("Set1: \n");
printSet(set1);
printf("\n");
printf("Set2: \n");
printSet(set2);
}
