This assign I guess should be pretty self explanitory. However, it
isnt to me. I understand I have to use linked lists, but reading the
assignment I am not sure what the instructor is expecting me to do and
what is the desired result. Im sure one of you experienced c
programmers could break this down for me.
The Assignment:
The input data file contains 2 columns of words(ie 2 words per line).
The words in each column are in alphabetic order. Your job is to read
the data file (merge.dat) and create a linked list that contains all
the words (from both columns) in alphabetic order. Do NOT just make
one list and then sort it with some sorting algorithm. Use the fact
that each column is already sorted to get a complete sorted list in
just one pass. This is called a "merge" or "merge sort" Write the list
back to the same file.
The point of this assignment is to make you use a linked list. So that
you don't kill yourself trying to get the data read in from the file,
I have a file called "merge.c" in the Code directory that has some
code you can use to read in the data. Once you have the data loaded
into two arrays of strings (2-d char arrays) then start building the
linked list.
To build the list, just compare the 2 first items from the arrays.
copy the "first" on to the linked list, and incrament the counter for
that array. Now, one array starts at index 1 and the other at 0. Now
repeat the procedure until you have copied all the strings from one of
the arrays. When this happens, simply copy the rest of the other array
to the linked list.
#include <stdio.h>
#define CHARS 30
#define NAMES 20
main()
{
struct NODE {
char name[CHARS];
struct NODE *next;
};
typedef struct NODE Node;
int count= -1;
int index1=0,index2=0;
int i;
char list1[NAMES][CHARS],list2[NAMES][CHARS];
FILE *fp;
fp=fopen("merge.dat","r");
while (!feof(fp)) {
count++;
fscanf(fp,"%s %s ",list1[count],list2[count]);
}
fclose(fp);
/* you start your code here....*/
/* just me verifying the expected results */
for (i=0;i<=count;++i){
printf ("%s %s\n", list1[i],list2[i]);
}
}
Aaron,Hank Brock,Lou
Cobb,Ty Burdette,Lou
Jenkins,Fergie Dropo,Walt
Mays,Willie Fingers,Rollie
McGowan,Sean Kaline,Al
Robinson,Frank Mantle,Mickey
Ruth,George McGowan,Bill
Ryan,Nolan Murcer,Bobby
Williams,Ted Robinson,Brooks |
Request for Question Clarification by
efn-ga
on
28 Mar 2003 09:56 PST
Hi Derek,
The instructor is giving you both a functional specification of what
is supposed to happen and a design specification of how you are
supposed to make it happen.
The functional specification is: When the program runs, it should
open a text file named "merge.dat" and read two strings per line from
it. These strings form columns that are sorted in alphabetical order
in the input. The program should write over this file with the same
strings, one per line, in a single alphabetical list. So after the
program runs, the beginning of the file should look like this:
Aaron,Hank
Brock,Lou
Burdette,Lou
Cobb,Ty
and so on.
(The instructor did not explicitly specify that the output should have
one string per line. That is my interpretation. You could check that
if you are in doubt.)
The design specification specifies the method the program should use
to achieve the desired result. The major steps are:
1. Read the input into two sorted arrays of strings.
2. Merge the arrays into a sorted linked list.
3. Write out the linked list.
Is this the kind of answer you are looking for? It would be a lot of
work to explain in detail how to do every part, and I don't want to
explain things you already know. If you are just looking for an
explanation of what the assignment means and requires, as presented
above, not how to do it, I can go into that in more detail.
--efn
|
Request for Question Clarification by
studboy-ga
on
28 Mar 2003 10:01 PST
All the instructor wants you to do is to merge the two arrays together
in alphabetical order (without using any type of sort).
Question: what type of resulting linked list is expected? Singly or
doubly?
|
Clarification of Question by
derekwtp-ga
on
28 Mar 2003 15:07 PST
efn I am not looking for answers, However I am looking for guidance as
to how to get started and what in essence should I be doing in this
program. I am very rough around the edges. Could you help me on how I
am supposed to merge these two lists? I am not supposed to use a
sorting algorithm, so i am going to take for granted everthing is in
order already. How do i move alternating each of these arrays into a
link list?
example please?
|
Request for Question Clarification by
studboy-ga
on
28 Mar 2003 16:23 PST
The instructor says--
1) Look at the top of both lists -- determine which one should go
first
(alphabetically)
2) Take the one that is supposed to go first, shove it into a *newly
created* list
3) Move the "top" indicator for the list from which you have "taken
the first element" out--move the indicator to point to the second
element.
4) Now repear--look at both lists again--until you get to the end of
*one* of
the lists. Then you just shove the remaining elements of the other
list
all at once into the new list.
This works because both lists are in order to start with.
|
Request for Question Clarification by
studboy-ga
on
28 Mar 2003 16:36 PST
So, algorithm:
create_new_list(list3) (of course, to do this, you will need to know
what the instructor
asked for -- singly or doubly linked list. Check with TA)
index1 = index2 = index3 = 0;
while (index1 < 20 && index2 < 20) {
if (list1[index1] > list2[index2]) {
list3[index3] = list2[index2]
index2++
} else {
list3[index3] = list1[index1]
index1++
}
index3++
}
if (index1 < 19) // leftover in list1
shove rest of list1 to list3
else if (index2 < 19) // leftover in list2
shove rest of list2 to list3
|
Clarification of Question by
derekwtp-ga
on
28 Mar 2003 16:45 PST
I am attempting to traverse my link list, however I am getting
segmentation errors. Could you assist?
#include <stdio.h>
#define CHARS 30
#define NAMES 20
main()
{
struct NODE {
char name[CHARS];
struct NODE *next;
};
typedef struct NODE Node;
int count= -1;
int index1=0,index2=0;
int i;
char list1[NAMES][CHARS],list2[NAMES][CHARS];
FILE *fp;
Node *node;
Node *inode;
inode= (Node*)malloc(sizeof(Node));
node=inode;
int x,o;
fp=fopen("merge.dat","r");
while (!feof(fp)) {
count++;
fscanf(fp,"%s %s ",list1[count],list2[count]);
}
fclose(fp);
/* you start your code here....*/
/* just me verifying the expected results
for (i=0;i<=count;++i){
printf ("%s \t %s\n", list1[i],list2[i]);
} */
/*what I am attempting to do is alternate arrays to load link list */
do{
node->next=(Node*)malloc(sizeof(Node));
node=node->next;
if (list1[o]>list2[x])
{
strcpy(node->name,list1[o]);
++o;
}
else strcpy(node->name,list2[x]);
++x;
}while (list1);
node=inode->next;
while (node!=NULL) {
printf("%s\n",node->name);
node=node->next;
}
}
|
Clarification of Question by
derekwtp-ga
on
28 Mar 2003 16:48 PST
studboy, I apologize i didnt see your comments below. But are they
similar to what I wrote in my code? or not. I am unsure cuz im stuck
in a segmentation problem now.
|
Request for Question Clarification by
efn-ga
on
28 Mar 2003 17:28 PST
Hi Derek,
You are using a dummy node to store the pointer to the beginning of
the list. This can work, but it would be simpler just to use a
pointer variable.
x and o are not initialized and should be.
You can't lexicographically compare C-style null-terminated character
strings with the > operator. (Well, you can, but it won't work.) Use
the library facility strcmp instead.
The code in the loop now increments x whether a string was taken from
list2 or not. I think you need some braces around the else block.
The body of your loop resembles the algorithm studboy-ga posted, but
the terminating condition won't work. You need one more like his:
run the loop until one of the arrays is exhausted.
You also need to implement the functionality he had after the loop to
copy the non-exhausted list to the output.
Finally, the list traversal for output at the end relies on having a
null next pointer in the last node to terminate the traversal, but
there is no code that ever sets any next pointer to null.
studboy-ga and I have both been politely hanging back and not posting
our comments as an answer. You might want to pick one of us to post
an answer. Otherwise, it will be whoever has the nerve first.
And just to clarify, when I said "Is this the kind of answer you are
looking for?" and you said "I am not looking for answers," I didn't
mean to imply that you were asking for the program to be written for
you. I was just using "answer" in the Google Answers sense of a
response to your question and trying to figure out how to help you.
--efn
|
Request for Question Clarification by
studboy-ga
on
28 Mar 2003 17:34 PST
I think efn you deserves the credit :) Not me... Don't pick me :)
|
Clarification of Question by
derekwtp-ga
on
28 Mar 2003 19:09 PST
okay efn i guess I got you buddy!! : ) . OKay i think i have added all
the changes that you both recommended. can you see if I am on the
right track. It compiles but still does not work
#include <stdio.h>
#define CHARS 30
#define NAMES 20
main()
{
struct NODE {
char name[CHARS];
struct NODE *next;
};
typedef struct NODE Node;
int count= -1;
int index1=0,index2=0,index3=0;
int i;
char list1[NAMES][CHARS],list2[NAMES][CHARS],list3[NAMES][CHARS];
FILE *fp;
Node *node;
Node *head;
head= (Node*)malloc(sizeof(Node));
node=head;
int x=0,o=0;
fp=fopen("merge.dat","r");
while (!feof(fp)) {
count++;
fscanf(fp,"%s %s ",list1[count],list2[count]);
}
fclose(fp);
/* you start your code here....*/
/* just me verifying the expected results
for (i=0;i<=count;++i){
printf ("%s \t %s\n", list1[i],list2[i]);
} */
/*what I am attempting to do is alternate arrays to load link list
do{
node->next=(Node*)malloc(sizeof(Node));
node=node->next;
if (list1[o]>list2[x])
{
strcpy(node->name,list1[o]);
++o;
}
else{
strcpy(node->name,list2[x]);
++x;}
}while (list1!=NULL || list2!=NULL);
node=head->next;
while (node!=NULL) {
printf("%s\n",node->name);
node=node->next;
} */
while (index1 < 20 && index2 < 20) {
if (list1[index1] > list2[index2]) {
strcpy(list3[index3],list2[index2]);
index2++;
} else {
strcpy(list3[index3],list1[index1]);
index1++;
}
index3++;
}
;
if (index1 < 19){ // leftover in list1
while (index1<19)
strcpy(list3[index3],list1[index1]);
index3++;index1++; }
// shove rest of list1 to list3
else if (index2 < 19){ // leftover in list2
strcpy(list3[index3],list2[index2]);index3++;index2++;}
// shove rest of list2 to list3
}
|
Hi Derek,
OK, we'll pick up the conversation here in the answer section. Thanks
to studboy-ga for so graciously yielding. As in our previous
transaction, I'll be willing to advise you through multiple
interactions if necessary.
It looks like one of my previous comments still applies:
"You can't lexicographically compare C-style null-terminated character
strings with the > operator. (Well, you can, but it won't work.) Use
the library facility strcmp instead."
(studboy could get away with using > because he was writing pseudocode
to explain the algorithm, but you are writing C.)
It would be better not to use constant values of 19 and 20. The
program already counts the input lines as it reads them in and stores
the strings in the arrays, so that count is the one you should use.
I assume list3 is an array while you are getting the merge working,
but eventually, you will convert it to a linked list.
In the "leftover in list1" loop, the while loop will run forever,
because the loop body is only the strcpy call and nothing changes
index1. You need some more braces to get index1 changed in the loop
body.
The "leftover in list2" code also needs a loop. As it is, it will
only copy one string, but you want it to copy all the remaining
strings.
If you need more help, please feel free to ask for a clarification.
--efn |
Request for Answer Clarification by
derekwtp-ga
on
29 Mar 2003 11:45 PST
Looking at my output:
[root@localhost eight]# ./eight
Aaron,Hank
Brock,Lou
Burdette,Lou
Jenkins,Fergie
Dropo,Walt
Fingers,Rollie
McGowan,Sean
Kaline,Al
Mantle,Mickey
Ruth,George
McGowan,Bill
Ryan,Nolan
Murcer,Bobby
Robinson,Brooks
Q??
?
the end index3=34,index1=20,index2=14
however I am still not sure what do do w/ my while loop and
understanding why my output look like that:
#include <stdio.h>
#define CHARS 30
#define NAMES 20
main()
{
struct NODE {
char name[CHARS];
struct NODE *next;
};
typedef struct NODE Node;
int count= -1;
int index1=0,index2=0,index3=0;
int i;
char list1[NAMES][CHARS],list2[NAMES][CHARS],list3[NAMES][CHARS];
FILE *fp;
Node *node;
Node *head;
head= (Node*)malloc(sizeof(Node));
node=head;
int x=0,o=0;
fp=fopen("merge.dat","r");
while (!feof(fp)) {
count++;
fscanf(fp,"%s %s ",list1[count],list2[count]);
}
fclose(fp);
/* you start your code here....*/
/* just me verifying the expected results
for (i=0;i<=count;++i){
printf ("%s \t %s\n", list1[i],list2[i]);
} */
/*what I am attempting to do is alternate arrays to load link list
do{
node->next=(Node*)malloc(sizeof(Node));
node=node->next;
if (list1[o]>list2[x])
{
strcpy(node->name,list1[o]);
++o;
}
else{
strcpy(node->name,list2[x]);
++x;}
}while (list1!=NULL || list2!=NULL);
node=head->next;
while (node!=NULL) {
printf("%s\n",node->name);
node=node->next;
} */
while (index1 < 20 && index2 < 20) {
if (strcmp(list1[index1],list2[index2])>0) {
strcpy(list3[index3],list2[index2]);
index2++;
}
else {
strcpy(list3[index3],list1[index2]);
index1++;
}
index3++;
}
for (x=0;x<=index3;++x){
node->next=(Node*)malloc(sizeof(Node));
node=node->next;
strcpy(node->name,list3[x]);
}
node=head->next;
while (node!=NULL) {
printf("%s\n",node->name);
node=node->next;
}
printf("the end index3=%d,index1=%d,index2=%d
\n",index3,index1,index2);
}
|
Clarification of Answer by
efn-ga
on
29 Mar 2003 12:54 PST
Let's see if we can get a clue from analyzing the output.
The input is:
Aaron,Hank Brock,Lou
Cobb,Ty Burdette,Lou
Jenkins,Fergie Dropo,Walt
Mays,Willie Fingers,Rollie
McGowan,Sean Kaline,Al
Robinson,Frank Mantle,Mickey
Ruth,George McGowan,Bill
Ryan,Nolan Murcer,Bobby
Williams,Ted Robinson,Brooks
The test output is:
Aaron,Hank
Brock,Lou
Burdette,Lou
Jenkins,Fergie
Dropo,Walt
Fingers,Rollie
McGowan,Sean
Kaline,Al
Mantle,Mickey
Ruth,George
McGowan,Bill
Ryan,Nolan
Murcer,Bobby
Robinson,Brooks
So we would expect the program first to compare Aaron and Brock and
pick Aaron. That seems to have worked.
Next it should compare Cobb and Brock and pick Brock. That worked
too.
Next it should compare Cobb and Burdette and pick Burdette. That also
worked.
Next it should compare Cobb and Dropo and pick Cobb. Here it went
astray and skipped Cobb and picked Jenkins. Notice that it picked the
right column, but the wrong line. That directs our attention to the
line that is supposed to copy from the first column:
strcpy(list3[index3],list1[index2]);
If we are comparing Cobb and Dropo, index1 should be 1 and index2
should be 2.
list1[index2] is indeed Jenkins, so that explains why the output shows
Jenkins after Burdette.
Can you see the problem now?
|
Request for Answer Clarification by
derekwtp-ga
on
29 Mar 2003 15:04 PST
I should have caught that oops.. but i was more concerned w/ where the
funny characters are and all of the line feeds are coming from. The
code shows that it should only print out 34 times through the link
list. Am i missing something?
[root@localhost eight]# ./eight
Aaron,Hank
Brock,Lou
Burdette,Lou
Cobb,Ty
Dropo,Walt
Fingers,Rollie
Jenkins,Fergie
Kaline,Al
Mantle,Mickey
Mays,Willie
McGowan,Bill
McGowan,Sean
Murcer,Bobby
Robinson,Brooks
9??
Robinson,Frank
Ruth,George
Ryan,Nolan
Williams,Ted
@??
??2
@
{???w??p???0(@
@i
??????
?
the end index3=34,index1=20,index2=14
|
Clarification of Answer by
efn-ga
on
29 Mar 2003 16:03 PST
I see you're getting output in alphabetical order now, so that's a
good sign.
In the last code you posted, it looks like you lost the part after the
merge loop that copies over the unexhausted input to the output.
You also have not paid due heed to my previous words of wisdom:
"It would be better not to use constant values of 19 and 20. The
program already counts the input lines as it reads them in and stores
the strings in the arrays, so that count is the one you should use."
The input consists of nine lines, but your program merges twenty pairs
of strings. Therefore, you are treating eleven pairs of garbage
strings as input. That is likely to give you empty lines and funny
characters in the output.
|
,
0 Comments
)