Double Linked List - Help Again

[chugger93]

Im seriously not even sure what this proj is suppposed to do, but we're supposed to create an ordered double linked list data structure. Its gonna have insert, traverse, search and delete. The program is gonna use static file names. I have code for a single linked list, but I dont know how to do double.

Heres most of the code so far I believe, but I have to do it with files in the insert function

#include "stdafx.h"
#include <fstream>
#include <iostream>

using namespace std;

struct record
{
    record *next
    record *prev;
};


int delete_item(record *head, int);
void traverse(record *head);
record *search(record *head, int);

int main(int argc, char* argv[])
{

    record *head;
    record *tail;
    head = NULL;
    tail = NULL;
    

    return 0;
}


int insert(record *head, record *item)
{
    if(item==NULL)
        return -1;
    if(head==NULL)
    {
        item->next = NULL;
        head = item;
        return 0;
    }
    if(item->key < head->key)
    {
        item->next = head;
        head = item;
        return 0;
    
        record *temp = head;
        while((temp->next !=NULL) &&
             (temp->next->key <= item->key))
             temp = temp->next;
        item->next = temp->next;
        temp->next = item;


void traverse(record *head)
{
    record *temp = head;
    while(temp !=NULL)
    {
        cout << temp->key << endl;
        temp = temp->next;
    }
    return;
}


record *search(record *head, int key)
{
    record *temp = head;
    while(temp !=NULL)
    {
        if(temp->key == key)
            return temp;
        temp = temp->next;
    }
    return NULL;
}
    

int delete_item(record *head, int key)
{
    if(head == NULL)
        return -1;
    if(head->key == key)
    {
        record *temp2 = head;
        head = head->next;
        delete temp2;
        return 0;
    }

        record *temp = head;
        while((temp->next !=NULL) &&
            (temp->next->key !=key))
            temp = temp->next;
        if(temp->next == NULL)
            return -1;
        record *temp2 = temp->next;
        temp->next = temp2->next;
        delete temp2;
        return 0;
} 

I beelive that somwhere in the insert fuction I need to add this

while (!infile.eof)
{
item = new record;
infile.getline(item->name)
infile.getline(item->ssn.item)
insert(head,tail,item) 

[CornedBee]

This is already a double linked list (your record struct has both a prev and a next pointer). You need a data member in the record.
You should make another struct that holds the head and tail pointers, not make them stack variables of main. Like this:

struct LList {
  record *head;
  record *tail;
};

Is the insert function supposed to read in the file or should it only add a node to the list?

[jim mcnamara]

/* A simple mailing list program that illustrates the
   use and maintenance of doubly linked lists.
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct address {
  char name[30];
  char street[40];
  char city[20];
  char state[3];
  char zip[11]; 
  struct address *next;  /* pointer to next entry */
  struct address *prior;  /* pointer to previous record */
};

struct address *start;  /* pointer to first entry in list */
struct address *last;  /* pointer to last entry */
struct address *find(char *);

void enter(void), search(void), save(void);
void load(void), list(void);
void mldelete(struct address **, struct address **);
void dls_store(struct address *i, struct address **start,
               struct address **last);
void inputs(char *, char *, int), display(struct address *);
int menu_select(void);

int main(void)
{
  start = last = NULL;  /* initialize start and end pointers */

  for(;;) {
    switch(menu_select()) {
      case 1: enter(); /* enter an address */
        break;
      case 2: mldelete(&start, &last); /* remove an address */
        break;
      case 3: list(); /* display the list */
        break;
      case 4: search(); /* find an address */
        break;
      case 5: save();  /* save list to disk */
        break;
      case 6: load();  /* read from disk */
        break;
      case 7: exit(0);
    }
  }
  return 0;
}

/* Select an operation. */
int menu_select(void)
{
  char s[80];
  int c;

  printf("1. Enter a name\n");
  printf("2. Delete a name\n");
  printf("3. List the file\n");
  printf("4. Search\n");
  printf("5. Save the file\n");
  printf("6. Load the file\n");
  printf("7. Quit\n");
  do {
    printf("\nEnter your choice: ");
    gets(s);
    c = atoi(s);
  } while(c<0 || c>7);
  return c;
}

/* Enter names and addresses. */
void enter(void)
{
  struct address *info;

  for(;;) {
    info = (struct address *)malloc(sizeof(struct address));
    if(!info) {
      printf("\nout of memory");
      return;
    }

    inputs("Enter name: ", info->name, 30);
    if(!info->name[0]) break;  /* stop entering */
    inputs("Enter street: ", info->street, 40);
    inputs("Enter city: ", info->city, 20);
    inputs("Enter state: ", info->state, 3);
    inputs("Enter zip: ", info->zip, 10);

    dls_store(info, &start, &last);
  } /* entry loop */
}

/* This function will input a string up to
   the length in count and will prevent
   the string from being overrun.  It will also
   display a prompting message. */
void inputs(char *prompt, char *s, int count)
{
  char p[255];

  do {
    printf(prompt);
    fgets(p, 254, stdin);
    if(strlen(p) > count) printf("\nToo Long\n");
  } while(strlen(p) > count);

  p[strlen(p)-1] = 0; /* remove newline character */
  strcpy(s, p);
}

/* Create a doubly linked list in sorted order. */
void dls_store(
  struct address *i,   /* new element */
  struct address **start, /* first element in list */
  struct address **last /* last element in list */
)
{
  struct address *old, *p;

  if(*last==NULL) {  /* first element in list */
    i->next = NULL;
    i->prior = NULL;
    *last = i;
    *start = i;
    return;
  }
  p = *start; /* start at top of list */

  old = NULL;
  while(p) {
    if(strcmp(p->name, i->name)<0){
      old = p;
      p = p->next;
    }
    else {
      if(p->prior) {
        p->prior->next = i;
        i->next = p;
        i->prior = p->prior;
        p->prior = i;
        return;
      }
      i->next = p; /* new first element */
      i->prior = NULL;
      p->prior = i;
      *start = i;
      return;
    }
  }
  old->next = i; /* put on end */
  i->next = NULL;
  i->prior = old;
  *last = i;
}

/* Remove an element from the list. */
void mldelete(struct address **start, struct address **last)
{
  struct address *info;
  char s[80];

  inputs("Enter name: ", s, 30);
  info = find(s);
  if(info) {
    if(*start==info) {
      *start=info->next;
      if(*start) (*start)->prior = NULL;
      else *last = NULL;
    }
    else {
      info->prior->next = info->next;
      if(info!=*last)
          info->next->prior = info->prior;
      else
        *last = info->prior;
    }
    free(info);  /* return memory to system */
  }
}

/* Find an address. */
struct address *find( char *name)
{
  struct address *info;

  info = start;
  while(info) {
    if(!strcmp(name, info->name)) return info;
    info = info->next;  /* get next address */
  }
  printf("Name not found.\n");
  return NULL;  /* not found */
}

/* Display the entire list. */
void list(void)
{
  struct address *info;

  info = start;
  while(info) {
    display(info);
    info = info->next;  /* get next address */
  }
  printf("\n\n");
}

/* This function actually prints the fields in each address. */
void display(struct address *info)
{
    printf("%s\n", info->name);
    printf("%s\n", info->street);
    printf("%s\n", info->city);
    printf("%s\n", info->state);
    printf("%s\n", info->zip);
    printf("\n\n");
}

/* Look for a name in the list. */
void search(void)
{
  char name[40];
  struct address *info;

  printf("Enter name to find: ");
  gets(name);
  info = find(name);
  if(!info) printf("Not Found\n");
  else display(info);
}

/* Save the file to disk. */
void save(void)
{
  struct address *info;

  FILE *fp;

  fp = fopen("mlist", "wb");
  if(!fp) {
    printf("Cannot open file.\n");
    exit(1);
  }
  printf("\nSaving File\n");

  info = start;
  while(info) {
    fwrite(info, sizeof(struct address), 1, fp);
    info = info->next;  /* get next address */
  }
  fclose(fp);
}

/* Load the address file. */
void load()
{
  struct address *info;
  FILE *fp;

  fp = fopen("mlist", "rb");
  if(!fp) {
    printf("Cannot open file.\n");
    exit(1);
  }

  /* free any previously allocated memory */
  while(start) {
    info = start->next;
    free(info);
    start = info;
  }

  /* reset top and bottom pointers */
  start = last = NULL;

  printf("\nLoading File\n");
  while(!feof(fp)) {
    info = (struct address *) malloc(sizeof(struct address));
    if(!info) {
      printf("Out of Memory");
      return;
    }
    if(1 != fread(info, sizeof(struct address), 1, fp)) break;
    dls_store(info, &start, &last);
  }
  fclose(fp);
}

[chugger93]

Originally posted by CornedBee
This is already a double linked list (your record struct has both a prev and a next pointer). You need a data member in the record.
You should make another struct that holds the head and tail pointers, not make them stack variables of main. Like this:

struct LList {
  record *head;
  record *tail;
};

Is the insert function supposed to read in the file or should it only add a node to the list?

Yah its supposed to read it in I beelive and write it out to another file. Its basically like the last project, I posted about, ( structures ) look below on main page

I guess this linked list is just supposed to take in that info from one file again and write it out in order. Guess linked list is just another way of ordereing the info ?! Not sure.


How is the code I have so far a double linked list? All those functions so far are for only a single list.

[CornedBee]

A linked list is a group of memory block that have cross references.
In a single linked list each element only has a reference to the next element. This means you can only traverse the list in one direction.
In a double linked list each element contains references to both the next and the previous element. You can traverse this kind of list in both directions.

What you've written is a double linked list. You nodes have links to both the previous and the next elements. But your nodes contain no data...

[chugger93]

but isnt my code supposed to also have the prev pointer in it? It only has next throughout it and it doesnt have the tail part of it anywhere. The only data code I need is to read the info from a file from my structures project, and write it out to another file. Which I beleive then would only go in the insert part.

LOL, Im gonna have to skip class today and work on it more thats for sure. Gonna have to turn it in late.

[CornedBee]

Look, here are two double linked lists for you. One is a C++ class, the other is real plain C.

Here's the C one. You need to insert it directly into your code.

// remove the __fastcall and register keywords if you use this, they are optimizing features

typedef struct _llistNode
{
	struct _llistNode *prev;
	struct yourStruct data;
	struct _llistNode *next;
} llist_node;

typedef struct _llistMain
{
	llist_node *head;
	llist_node *tail;
	unsigned int size;
} llist;

// warning: this function is likely to create memory leaks if any of the content
// has dynamically allocated data
void __fastcall ClearLList(llist *ll)
{
	register llist_node *q, *p = ll->head;
	while(p != NULL)
	{
		q = p->next;
		free(p);
		p = q;
	}
	InitLList(ll);
}

void __fastcall InitLList(llist *ll)
{
	ll->size = 0;
	ll->head = ll->tail = NULL;
}

llist_node * InsertNode(llist *ll, llist_node *at, const struct yourStruct *pData)
{
	llist_node *newnode = malloc(sizeof(llist_node));
	if(newnode == NULL)
		return NULL;
	++(ll->size);
	llist_node *after = at->next;
	at->next = after->prev = newnode;
	newnode->prev = at;
	newnode->next = after;
	newnode->data = *pData;
	return newnode;
}

void DeleteNode(llist *ll, llist_node *at)
{
	--(ll->size);
	at->prev->next = at->next;
	at->next->prev = at->prev;
	free(at);
}

The C++ one is in the attached header file. It's not as simple, the teacher won't believe you did it, but you get the idea. It's a templated version supporting iterators.

All you need to do is reading the file (you already know how, look at the previous exercise) and search the list for the right inserting position.

[chugger93]

Cornedbee, why cant we just take my code way up above and modify it? Instead of giving me all this other stuff which is kinda throwing me off. In my code above I must be on the right track.

and where in the insert funciton do i put the code to read and write out the info? does it matter? Should I put in the beginning of the insert funciton or end. Also aint I gonna need this again?

struct record
{
char name[50];
char ssn[12]
};

[CornedBee]

Yes you need this struct again, as the type of the data member of the llist_node struct (instead of 'struct yourStruct').

The main problem of your code above is the lack of seperation and the resulting bad readability. You should seperate the logic of the linked list from the logic of the real problem. The InsertNode function is only there to insert a node at a given position. You need a ReadFile function that reads the file record by record, searches the linked list for the correct place to insert and inserts the record there using InsertNode. Then it reads the next record.

The universal way to traverse a list is this for-loop:
llist_node *p;
for(p=ll->head;p!=NULL;p=p->next) {
// do things here, p points to the current node
}

[chugger93]

so could I still use the same read_in funciton I used in my last project?

void read_in(record items[], int &count, char src[])
{
  ifstream is(src);
  int i;
  for(i=0; !is.eof(); ++i) {
    is.getline(items[i].name, 50);
    is.getline(items[i].ssn, 12);
  }
  count = i; 
  cout << count << endl;
  
} 

and how do u declare the funciton right above main?
I put something like this
void __fastcall ClearLList(*ll);

and it wont still work



B.T.W teacher just announced that we can make our head and tail pointers global

[CornedBee]

Remove the __fastcall, it was something for me to try out.

You need to place InitLList before ClearLList.

And where has the type of the pointer come to?

You can use the read_in function with a little modification. It now needs to read into the linked list, not into an array. And it needs to take care of sorting, remove the sort function.

[CornedBee]

What I mean is that read_in doesn't just stupidly inserts one entry after the other into the linked list but rather searches for the right place every time.

[chugger93]

So corned, am I using ur code up above and thats all? Or am I incorporating it into my existing code?

so far its this?:

typedef struct _llistNode
{
    struct _llistNode *prev;
    char name[50];
    char ssn[12];
    struct _llistNode *next;
} llist_node;


typedef struct _llistMain
{
    llist_node *head;
    llist_node *tail;
    unsigned int size;
} llist;



int main(int argc, char* argv[])
{



llist_node * InsertNode(llist *ll, llist_node *at, const struct yourStruct *pData)
{
    llist_node *newnode = malloc(sizeof(llist_node));
    if(newnode == NULL)
        return NULL;
    ++(ll->size);
    llist_node *after = at->next;
    at->next = after->prev = newnode;
    newnode->prev = at;
    newnode->next = after;
    newnode->data = *pData;
    return newnode;
}

void DeleteNode(llist *ll, llist_node *at)
{
    --(ll->size);
    at->prev->next = at->next;
    at->next->prev = at->prev;
    free(at);
}


void read_in(llist *ll, llist_node *at char src[])
{
  ifstream infile(src);
  while (!infile.eof)
  {
      item = new record;
    infile.getline(item -> name, 50);
    infile.getline(items -> ssn, 12);
 insert (head, tail, item)

  
}

    return 0;
} 

[CornedBee]

Why do you have functions inside the main?

Here's a better way to store the data:

struct record {
  char name[50];
  char ssn[12];
};

typedef struct _llistNode
{
    struct _llistNode *prev;
    record data;
    struct _llistNode *next;
} llist_node;

Ok, here's pseudocode for the main function:

main
{
  llist data;
  InitLList(&data);

  // just take it from the last project
  read filename1;
  read filename2;

  read_in(parameters);
  // the list is sorted, read_in must guarantee that
  write_out(parameters);
}

Here are prototypes for read_in and write_out:

void read_in(llist *ll, const char *filename);
void write_out(llist *ll, const char *filename);

Here's the logical flow of read_in:

00 open file filename
10 if end of file then end function
20 read input from file
30 search for the correct insert position in list
40 insert the data into the list

Here's an adjusted version of InsertNode. The current version has a problem that is now solved.

llist_node * InsertNode(llist *ll, llist_node *at, const struct yourStruct *pData)
{
	llist_node *newnode = malloc(sizeof(llist_node));
	if(newnode == NULL)
		return NULL;
	++(ll->size);
	llist_node *after;
	if(at != NULL) {
		after = at->next;
		at->next = newnode;
	} else {
		after = ll->head;
		ll->head = newnode;
	}
	if(after != NULL)
		after->prev = newnode;
	else
		ll->tail = newnode;
	newnode->prev = at;
	newnode->next = after;
	newnode->data = *pData;
	return newnode;
}

This version can insert a node at the start of the list.

[CornedBee]

For finding the insertion point you must traverse the list and compare the data against your new data.

[chugger93]

OMG seriously, linked lists suck

[CornedBee]

No, they rule and are very easy to use.

[chugger93]

Originally posted by CornedBee
No, they rule and are very easy to use.

Thats because u've been programming for god knows how many years, me on the other hand, have been donig it for almost 2 months. Really harder on someone like me. Thankgod I only have one more project to do after this one. Im not even gonna totally complete this one, problay just turn in what I have done

[CornedBee]

Just because you're not very good at C++ doesn't change the fact that linked lists rock and are far easier to use than, say, binary trees.

I've been programming for 2-3 years now, so not that long.

Here you have the read_in function, but I won't help you on the write_out anymore.

void read_in(llist *ll, const char *filename)
{
  ifstream is(filename);
  llist_node *p;
  record temp;
  while(!is.eof()) {
    is.getline(temp.name, 50);
    is.getline(temp.ssn, 12);
    // find the place to insert
    for(p=ll->tail; p != NULL; p = p->prev) {
      if(strcmp(temp.name, p->data.name) >= 0) {
        AddNode(ll, p, &temp);
        break;
      }
    }
    if(p == NULL)
      AddNode(ll, NULL, &temp);
  }
}

[chugger93]

alright thanx man, ill see what i can do with the write_out, since its somewhat probaly similar to the readin