Linked Lists and Pointer Arrays - Sorted insertion.

[Xpl0ReRChR]

The input file contains the titles and prices of books, in this form:

<TITLE><space><PRICE><comma>
<TITLE><space><PRICE><comma>
...

for example, if it contained 3 books, it would look like this:

ABC 12.31,
KDASD 35,
OPI 93.58,

So, what I want to do is: there is an array of pointers where each book will be inserted, sorted by letter and in ascending order. So this array's size will be 26.

There is an array of pointers where each book will be inserted, sorted by price and in ascending order. Prices range from 0 (not included) to 100, and this array's size will be 10, as prices will be sorted from 0-10, 10-20, etc.

How am I supposed to do this without making the code unnecessarily large? Here is what I've done so far:

    // Data read and call of function 'insert' for each book.
    for (i = 0, pos = 0; (feof(f) == 0); i++) {
        
        fseek(f, pos, SEEK_CUR);
        fscanf(f, "%s %lf", temp_title, &temp_price);
        insert(ptr_titles, ptr_prices, temp_title, temp_price);
    }
    return 0;
}

    // Memory allocation for new node and insertion.
void insert (char ptr_titles[26], int ptr_prices[10], char tmp_title[], double tmp_price) {
    booksT *newnode;
    
    newnode = (booksT*)malloc(sizeof(booksT*));
    if (newnode == NULL) {
        printf("Memory allocation error.\n");
        exit(1);
    }
    
    strcpy(newnode->title, tmp_title);
    newnode->price = tmp_price;
    
    switch (newnode->title[0]) {  // According to the first letter of the tile...:
        case 'A': if (ptr_titles[0] == NULL) { ptr_titles[0] = newnode; } else do { if (strcmp(newnode->title, ptr_titles)) > 0) { 
        case 'B':
        case 'C':
        case 'D':
        case 'E':
        case 'F':
        case 'G':
        case 'H':
        case 'I':
        case 'J':
        case 'K':
        case 'L':
        case 'M':
        case 'N':
        case 'O':
        case 'P':
        case 'Q':
        case 'R':
        case 'S':
        case 'T':
        case 'U':
        case 'V':
        case 'W':
        case 'X':
        case 'Y':
        case 'Z':

// and then do the same for prices

Would you have a better idea as to how to do this?

[Salem]

Well your first two parameters should be booksT*[], as in say

void insert (booksT *titles[26], booksT *prices[10], char title[], double price);

Your lists are like

booksT *titles[26] = { 0 };
booksT *prices[10] = { 0 };

So your initial call to insert data would be something like

insert(titles, prices, temp_title, temp_price);

In the actual insert function itself, you need to create TWO identical nodes, since you'll be adding one node to a title list, and the other node to a price list.

Then in your insert function, you would make use of a sub-function (to be written) which inserts a node into a list.
For example, your entire case statement could be

// assuming titles are always upper case in the first letter, and the ASCII character set
insertIntoList( titles[temp_title[0]-'A'], newNode1 );

[Xpl0ReRChR]

I don't get why

char ptr_titles[26] and int ptr_prices[10] should be booksT*...

It was:

typedef struct books {
    char title[50];
    double price;
    struct books *nxt_price;
    struct books *nxt_title;
} booksT;

so each node to be inserted, containing the above elements. is booksT *newnode.

Then there are two arrays containing pointers, which are the ones I mention at the beggining of this reply. ptr_titles[0] is about 'A', ptr_titles[1] is about 'B' and so on. Then ptr_prices[0] is about books that are in the price range of 0-10, ptr_prices[1] is about 10-20, and so on.

Can you explain?

[Salem]

> I don't get why
> char ptr_titles[26] and int ptr_prices[10] should be booksT*...
Well what else apart from say "hello world" or "this is my book" do you think you can store in an array of 26 chars?

You're creating a whole bunch of objects whose type is booksT, so you need some kind of data structure whose type also includes booksT.

The only part of my previous reply which doesn't apply is the "create two nodes" part, since your booksT contains TWO 'next' pointers.

Initially say, you would have
titles[0] = newNode;

When your next 'A' title comes along, you then decide whether "Aarvarks for beginners" comes before or after "Amateur ant keeping", at which point you would do either
newNode->nxt_title = titles[0]; titles[0] = newNode;
or
titles[0]->nxt_title = newNode;

Read some previous posts on how to manage a single linked list, before trying to grasp arrays of linked lists (if you're still stuck).

[Xpl0ReRChR]

> I don't get why
> char ptr_titles[26] and int ptr_prices[10] should be booksT*...
Well what else apart from say "hello world" or "this is my book" do you think you can store in an array of 26 chars?

The pointer array of 26 chars will contain a pointer to the first node whose title begins with 'A', the first node whose title begins with 'B', 'C',...'Z', and so on.
The pointer array of 10 ints will contain a pointer to the first node whose price is in the 0-10 range, the first node whose price is in the 10-20 range, and so on.

The title array itself, which is contained in each node, has a size of 50. The price array itself, which is contained in each node, has a size of 10.

I understand what you're saying after that, and thanks for the tip, will try it out!

[quzah]

array of 26 chars will contain a pointer to the first node

Why would an array of characters store a pointer to the first node?


Quzah.

[Xpl0ReRChR]

It's supposed to look something like this.


<<< malware link snipped >>>

[MK27]

Why would an array of characters store a pointer to the first node?

I think the OP means this is an array of 26 char pointers, each representing a char(acter) from the alphabet; the list is kept sorted and these point to the appropriate nodes (or: there are 26 separate lists). Confusingly put tho.

@ Xpl0ReRChR: You don't have to use a massive repetitive switch/case there, you can do arithmetic with the ascii value. Eg., 'A' - 65 = 0, 'B' - 65 = 1, etc.

[quzah]

Sounds like he wants an array of 26 node pointers. Each spot in the bucket representing those titles that begin with the associated letter. Each node is a linked list for that letter of the alphabet.


Quzah.

[Xpl0ReRChR]

@ Xpl0ReRChR: You don't have to use a massive repetitive switch/case there, you can do arithmetic with the ascii value. Eg., 'A' - 65 = 0, 'B' - 65 = 1, etc.

I'm sure that a repetitive switch/case is definitely the wrong way to go, but could you develop what you're suggesting? It seems to me that I would still need to develop awfully similar code for each case, even if I did that.

EDIT: I get what you're saying, it's a great idea!

[MK27]

Sounds like he wants an array of 26 node pointers. Each spot in the bucket representing those titles that begin with the associated letter. Each node is a linked list for that letter of the alphabet.

I think so. That's what I meant anyway, just I got caught up in the madness

could you develop what you're suggesting?

Let's say "FirstL" here is the 0 element of the title, capitalized, "AZlist" is the array of 26 node pointers, and "NewNode" is the node containing the title...

int index = FirstL - 65; // 65 == ascii 'A'
if (AZlist[index] == NULL) {
    AZlist[index] = NewNode;
} else {
    insertNode(&(AZlist[index]), NewNode);
}

Make sense? If you aren't familiar with ascii values:

Ascii Table - ASCII character codes and html, octal, hex and decimal chart conversion

They are fundamentally useful. The prototype for insertNode() would look like:

insertNode(node **head, node *new);

[Salem]

Right, so look at your diagram and figure out what TYPE those unlabeled pointers are supposed to be.

And thanks for using some malware site that pops up "you've won a free iDontCare"

[Xpl0ReRChR]

So this is what I tried to do:

void insert (char ptr_titles[26], int ptr_prices[10], char tmp_title[], double tmp_price) {
    booksT *newnode, *runner, *prev;
    int index;
    
    newnode = (booksT*)malloc(sizeof(booksT*));
    if (newnode == NULL) {
        printf("Memory allocation error.\n");
        exit(1);
    }
    
    strcpy(newnode->title, tmp_title);
    newnode->price = tmp_price;
    
    
    // Find right place according to title.
    index = newnode->title[0] - 65;
    if (ptr_titles[index] == NULL) {
        ptr_titles[index] = newnode;
        newnode->nxt_title = newnode;
    }
    else {
        runner = (booksT*)malloc(sizeof(booksT*));
        if (runner == NULL) {
            printf("Memory allocation error.\n");
            exit(1);
        }
        
        strcpy(runner->title, newnode->title);
        runner = ptr_titles[newnode->title[0] - 65];
        
        prev = (booksT*)malloc(sizeof(booksT*));
        if (prev == NULL) {
            printf("Memory allocation error.\n");
            exit(1);
        }
        
        do {
            prev = runner;
            runner = runner->nxt_title;
        } while ((runner->nxt_title != NULL) && (strcmp(runner->title, runner->nxt_title->title) < 0));
        
        prev->nxt_title = newnode->title;
        newnode->nxt_title = runner->nxt_title;
        free(prev->title);
        free(prev);
        free(runner->title);
        free(runner);
    }
    
}

And I'm getting:

hw4.c: In function ‘insert’:
hw4.c:17:24: warning: comparison between pointer and integer [enabled by default]
hw4.c:18:21: warning: assignment makes integer from pointer without a cast [enabled by default]
hw4.c:29:10: warning: assignment makes pointer from integer without a cast [enabled by default]
hw4.c:42:19: warning: assignment from incompatible pointer type [enabled by default]


Why is this? And do you think the whole idea is correct (this is the process for sorting according to title)?

PS. I'm really sorry for the link. I thought that site was safe. :/

[MK27]

hw4.c: In function ‘insert’:
hw4.c:17:24: warning: comparison between pointer and integer [enabled by default]
hw4.c:18:21: warning: assignment makes integer from pointer without a cast [enabled by default]
hw4.c:29:10: warning: assignment makes pointer from integer without a cast [enabled by default]

This is because you are still thinking that the array should be 26 char pointers. But that's not what you want. You want an array of 26 pointers to linked list nodes.

booksT *titles[26];

Salem pointed this out in post #2. Note that I used "node" as the type in my previous posts.

So each pointer in "titles" would point to a booksT with an appropriate title.

hw4.c:42:19: warning: assignment from incompatible pointer type [enabled by default]

Because you want the nxt_title pointer to point to the bookT node with that title, not to the title itself.

Think about the diagram. Notice how arrows from the prices array and the titles array connect to the same box, but on the basis of different criteria in the box. They do not connect to the criteria, they connect to the box.

[iMalc]

int index = FirstL - 65; // 65 == ascii 'A'

Grrr - No!
If you need to subtract 'A' then just subtract 'A'. You never have to go and look up whatever the ASCII value of it is.

int index = FirstL - 'A';

Xpl0ReRChR, please change all those random 65 "magic numbers" to 'A' and give MK27 a slap on the wrist for teaching you bad habbits.