Structure pointer operator

Question

Code is meant to create an array of pointers to student structure in order to use the array of pointers in other functions. I'm not sure how to use the arrow operator in binary function. It doesn't return a value for the index where id is found.

typedef struct{
    int IDno;
    char name[20];
    int project;
    int exam;
    double final;
} student;

student **create_class_list(char*filename, int *sizePtr);
void print_list(student**list,int *sizePtr);
int find_binsrch(int idNo, student **list, int size,int low, int high);

int main(void){

    int i, n; 
    student **listPtr;
    listPtr = create_class_list("student.txt", &n);
    print_list(listPtr,&n); 
    index2 = find_binsrch(searchID, listPtr, n, 1200, 4580);     
}

student **create_class_list(char *filename, int *sizeptr){

    int n,i;
    FILE *fptr; 
    fptr=fopen(filename,"r");
    if(fptr==NULL)
        printf("The file could not be opened.\n");
    else
        fscanf(fptr, "%d",sizeptr);

    n=*sizeptr;

    student **list;
    list = (student**)calloc(1, sizeof(student*));


    for(i=0;i<n;i++){
        list[i]=(student*)calloc(n,sizeof(student));
        fscanf(fptr,"%d %[^\n]s", &(list[i]->IDno),(list[i]->name));
    }

    return list;
}

void print_list(student**list,int *sizePtr){
    int i; 
    for(i=0; i<*sizePtr; i++){
        printf("%d %s\n",&(list[i]->IDno),(list[i]->name));
    }
}

int find_binsrch(int idNo, student **list, int size, int low, int high){
    int middle, i;

    while(low<=high){
        middle =(low+high)/2;

        printf("%d\n", middle); 

        if(idNo==list[middle]->IDno)
            return list[i]->IDno;

        if(idNo<list[middle]->IDno)
            high = middle -1;
        else
            low = middle +1;
    return -1;    
    }
}

Answer 1

What you must learn to do is enable Warnings every time you compile. This allows the compiler to identify many areas in your code that need attention. You should not accept code that compiles with warnings. There are only very, very rare circumstances where it is acceptable to rely on code that compiles with warnings (none that you will likely encounter in your first year of programming) So always enable -Wall -Wextra as part of your compile string. (you can also enable -pedantic to see additional warnings as well as some specific warning requests, but for general use -Wall -Wextra will do)

Had you compiled with warnings you would have seen:

students3.c: In function ‘main’:
students3.c:23:5: error: ‘index2’ undeclared (first use in this function)
    index2 = find_binsrch(searchID, listPtr, n, 1200, 4580);
    ^
students3.c:23:5: note: each undeclared identifier is reported only once for each function it appears in
students3.c:23:27: error: ‘searchID’ undeclared (first use in this function)
    index2 = find_binsrch(searchID, listPtr, n, 1200, 4580);
                        ^
students3.c:19:9: warning: unused variable ‘i’ [-Wunused-variable]
    int i, n;
        ^
students3.c: In function ‘print_list’:
students3.c:53:9: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘int *’ [-Wformat=]
        printf("%d %s\n",&(list[i]->IDno),(list[i]->name));
        ^
students3.c: In function ‘find_binsrch’:
students3.c:57:48: warning: unused parameter ‘size’ [-Wunused-parameter]
int find_binsrch(int idNo, student **list, int size, int low, int high){
                                                ^
students3.c: In function ‘main’:
students3.c:24:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
students3.c: In function ‘find_binsrch’:
students3.c:74:1: warning: control reaches end of non-void function [-Wreturn-type]
}
<snip>

Simply addressing the warnings/errors and recompiling (and addressing new warnings/errors disclosed from fixing the first list) will allow you to systematically correct your code. Taking these basic steps will allow you to correct your code to the point it will compile without warnings:

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

typedef struct{
    int IDno;
    char name[20];
    int project;
    int exam;
    double final;
} student;

student **create_class_list(char*filename, int *sizePtr);
void print_list(student**list,int *sizePtr);
int find_binsrch(int idNo, student **list, int size,int low, int high);

int main(void){

    int n, index2, searchID = 2; 
    student **listPtr = NULL;
    listPtr = create_class_list("student.txt", &n);
    if (!listPtr) {
        fprintf (stderr, "error: create_class_list failed.\n");
        return 1;
    }
    print_list(listPtr,&n); 
    index2 = find_binsrch(searchID, listPtr, n, 1200, 4580);

    if (index2) {} /* stub to eliminate unused warning */

    return 0;
}

student **create_class_list(char *filename, int *sizeptr){

    int n,i;
    FILE *fptr; 
    fptr=fopen(filename,"r");
    if(fptr==NULL)
        printf("The file could not be opened.\n");
    else
        fscanf(fptr, "%d",sizeptr);

    n=*sizeptr;

    student **list;
    list = (student**)calloc(n, sizeof(student*));


    for(i=0;i<n;i++){
        list[i]=(student*)calloc(n,sizeof(student));
        fscanf(fptr,"%d %[^\n]s", &(list[i]->IDno),(list[i]->name));
    }

    return list;
}

void print_list(student**list,int *sizePtr){
    int i; 
    for(i=0; i<*sizePtr; i++){
        printf("%d %s\n",list[i]->IDno, list[i]->name);
    }
}

int find_binsrch(int idNo, student **list, int size, int low, int high)
{
    int middle;

    if (size) {}  /* stub to eliminate unused warning */

    while(low<=high){
        middle =(low+high)/2;

        printf("%d\n", middle); 

        if(idNo==list[middle]->IDno)
            return list[middle]->IDno;

        if(idNo<list[middle]->IDno)
            high = middle -1;
        else
            low = middle +1;
    }
    return -1;    
}

Note: whether it runs correctly is a different question indeed, that depends on your data and the elimination of any logic errors.

Answer 2

In your binary search routine, your if's are comparing idNo against list[middle] when they need to compare against list[middle].idNo

You could simplify a bit by using a 1D array that gets realloc'ed rather than a 2D array of pointers. The entire code will be simpler and you won't lose any functionality.

UPDATE

I've switched your code to use an array of structs rather than an array of pointers to structs. It simplifies things and the two level lookup was just adding complexity that was probably tripping you up. Also, cleaned up more style-wise--Sorry about that but it's how I was able to see enough of your logic in order to make the changes.

Note: I agree completely with David [and many others] about compiler warnings. They are your friends. They usually show bugs that are 10x harder to find with a running program. I've been doing C for many years, I [still] always use -Wall -Werror

If you'd like to learn more about pointers to structs, arrays of structs, see my recent answer Issue implementing dynamic array of structures It has a primer on the various ways to switch between arrays, pointers to arrays, indexing of pointers, etc. that may be useful.

Added a full diagnostic suite that proves the binsrch algorithm, including edge cases that might not appear for a given set of data before turning it loose on real/large data. A good technique to remember.

Note that I'm not sure why you passed low/high as arguments as they serve no purpose for binary search in general. They're useful if you wanted a specific subset of the data. If so, comment out my extra code resetting them.

// binsrch -- program to do binary search

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

typedef struct {
    int IDno;
    char name[20];
    int project;
    int exam;
    double final;
} student;

student *
create_class_list(char *filename,int *sizeptr)
{

    int n;
    int i;
    FILE *fptr;
    student *cur;
    student *list;

    fptr = fopen(filename,"r");
    if (fptr == NULL)
        printf("The file could not be opened.\n");
    else
        fscanf(fptr,"%d",sizeptr);

    n = *sizeptr;

    list = calloc(n,sizeof(student));

    for (i = 0; i < n; i++) {
        cur = &list[i];
        fscanf(fptr,"%d %[^\n]s",&cur->IDno,cur->name);
    }

    fclose(fptr);

    return list;
}

void
print_list(student *list,int count)
{
    int i;
    student *cur;

    for (i = 0; i < count; i++) {
        cur = &list[i];
        printf("%d %s\n",cur->IDno,cur->name);
    }
}

student *
find_binsrch(int idNo,student *list,int count,int low,int high)
{
    student *cur;
    int middle;
    student *match;

    match = NULL;

    // what is the purpose of the limited range? -- ignore for now
    low = 0;
    high = count - 1;

    while (low <= high) {
        middle = (low + high) / 2;
        cur = &list[middle];

        //printf("find_binsrch: TRACE middle=%d\n",middle);

        if (idNo == cur->IDno) {
            match = cur;
            break;
        }

        if (idNo < cur->IDno)
            high = middle - 1;
        else
            low = middle + 1;
    }

    return match;
}

#define RAND0(_lim) \
    (rand() % _lim)
#define RAND1(_lim) \
    (RAND0(_lim) + 1)

// diag_binsrch -- run diagnostic on single array size
void
diag_binsrch(int count)
{
    student *list;
    student *cur;
    int searchidx;
    student *match;
    int err;

    list = calloc(count,sizeof(student));

    searchidx = 0;
    cur = &list[searchidx];
    cur->IDno = RAND1(30);

    // create interesting data
    ++searchidx;
    for (;  searchidx < count;  ++searchidx)
        list[searchidx].IDno = list[searchidx - 1].IDno + RAND1(137);

    err = 0;

    // search for something lower that the lowest -- we _want_ it to fail
    searchidx = 0;
    cur = &list[searchidx];
    match = find_binsrch(cur->IDno - 1,list,count,1200,4580);
    if (match != NULL) {
        printf("DIAG: expected failure -- searchidx=%d cur=%d match=%d\n",
            searchidx,cur->IDno - 1,match->IDno);
        ++err;
    }

    // search for something higher that the highest -- we _want_ it to fail
    searchidx = count - 1;
    cur = &list[searchidx];
    match = find_binsrch(cur->IDno + 1,list,count,0,count - 1);
    if (match != NULL) {
        printf("DIAG: expected failure -- searchidx=%d cur=%d match=%d\n",
            searchidx,cur->IDno + 1,match->IDno);
        ++err;
    }

    // search for all remaining entries -- they should all match
    cur = list;
    for (searchidx = 0;  searchidx < count;  ++searchidx, ++cur) {
        match = find_binsrch(cur->IDno,list,count,0,count - 1);

        if (match == NULL) {
            printf("DIAG: null return -- searchidx=%d IDno=%d\n",
                searchidx,cur->IDno);
            ++err;
            continue;
        }

        if (match->IDno != cur->IDno) {
            printf("DIAG: mismatch -- searchidx=%d cur=%d match=%d\n",
                searchidx,cur->IDno,match->IDno);
            ++err;
            continue;
        }
    }

    free(list);

    if (err)
        exit(1);
}

// diag_binsrch_full -- run full diagnostic
void
diag_binsrch_full(void)
{
    int count;

    printf("diag_binsrch_full: start ...\n");

    for (count = 1;  count < 1000;  ++count)
        diag_binsrch(count);

    for (count = 1000;  count <= 10000000;  count *= 10)
        diag_binsrch(count);

    printf("diag_binsrch_full: complete\n");
}

int
main(void)
{

    int listCount;
    student *listPtr;
    //student *cur;
    //student *match;

    // run diagnostic
    diag_binsrch_full();
    exit(0);

    listPtr = create_class_list("student.txt",&listCount);
    print_list(listPtr,listCount);

#if 0
    match = find_binsrch(searchID,listPtr,n,1200,4580);
    if (match != NULL)
        printf("main: MATCH IDno=%d name='%s'\n",match->IDno,match->name);
#endif

    return 0;
}