CS 2213/2211
|
Answer: I wasn't familiar with splint. It's on the Fedora systems in the Linux lab. (My SuSE system is a couple of years old now and doesn't seem to have splint.) Yes, of course you can use splint. However, a few test runs on my own programs produce an amazing number of warnings. These bring up issues that I don't want to discuss in class at all, since we are trying to learn the basics of C. For example, splint refers repeatedly to type "boolean" in its messages, and I guess the newest C standards have a boolean type, but I don't know the status of this. For us in this course, C has no boolean type separate from int. In summary, splint seems pretty high-tech and may not be useful for this course.
Update to answer (Mon Jan 24 09:56:02 CST 2005): On investigation, it doesn't seem as if splint will be usable in this course. It simply displays too many high-tech messages. Perhaps it can be configured to be useful, but for now I want you to use lint (on the Sun system) and NOT splint.
Hugh Maynard says that gcc with option -Wall will give some of the warnings of lint, but not all.
However, when I replace the call to rand() in the roll function with, say, Knuth's double generator algorithm the output looks like this... (every roll is a 2). I declared the seed1, seed2, and seed variables and tried it with and without srand doing the seeding. I tried all kinds of different scenarios and different RNG algorithmss, none of which are working. Can you give me any assistance with using a RNG other than the library one?
Answer: You didn't include the code you are using, but still there seems to be a likely answer. In the program craps.c as it is in the write-up for Recitation 2, the call rand() to the built-in RNG should return an integer between 1 and RAND_MAX inclusive. Then when you divide this by RAND_MAX + 1 as doubles, the result should be a double between 0 and 1.
In contrast, the function I called "Knuth's double generator" is designed to return a double between 0 and 1 directly. If you put it into the expresssion rand()/(double)RAND_MAX) + 1.0 this will always be 1, since 1/(double)RAND_MAX) will always be 0. So even though both functions are called rand(), they return quite different things.
If you seed either one of these generators with 0, you should get the same incorrect result. Also, using srand() to seed Knuth's generator doesn't make sense because srand() is connected to the built-in generator.
[jason@cs24174183-228 ~]$ cd rec1 [jason@cs24174183-228 rec1]$ gcc -o dice dice.c [jason@cs24174183-228 rec1]$ dice -bash: dice: command not found [jason@cs24174183-228 rec1]$
I am using fedora. Am I missing a package or something? Could you please let me know what the problem is asap? Thanx
Answer: This is not really a problem (it's a feature!). All the versions of Unix and all the various shells (and Zzzzzindows also) have the concept of a "PATH" variable, saying where to look for commands that are typed at the command line. This variable gives a sequence of directories to search for the command. This is what happens when you type a Unix command, say,
[wagner@gateway19 ~]$ date # print the day and time Fri Jan 28 08:22:53 CST 2005 [wagner@gateway19 ~]$ which date # exactly where is the command? /bin/date [wagner@gateway19 ~]$ /bin/date # fully qualified version (complete path) Fri Jan 28 08:23:03 CST 2005
Normally this path variable has a dot (which stands for the current directory) as its last entry. In the case of your system, this dot is missing. So all you have to do is type ./dice and it will work. Sometimes students give their executable the name of a common command, and have the same trouble you are having. The same solution works. Here's a little demo:
[wagner@gateway19 ~]$ mkdir rec1 # new directory rec1
[wagner@gateway19 ~]$ cd rec1 # change to the new directory
[wagner@gateway19 ~/rec1]$ vi hello.c # create hello.c
i#include <stdio.h> # first "i" is for "insert"
main() {printf("Hello World!\n");}
[Esc] ZZ
"hello.c" 3L, 53C written
[wagner@gateway19 ~/rec1]$ cat hello.c # check the program
#include <stdio.h>
main() {printf("Hello World!\n");}
[wagner@gateway19 ~/rec1]$ cc -o date hello.c # insane to call the executable "date", but ...
[wagner@gateway19 ~/rec1]$ date
Fri Jan 28 08:39:46 CST 2005 # got the system date
[wagner@gateway19 ~/rec1]$ ./date
Hello World! # our "date" this time
I consulted with Dan Smolenski a bit. In the Linux lab you are using the shell tcsh (a version of csh). It must have dot on its path. You are at home, and are using bash, which evidently doesn't have dot on its path. It is more secure to not have the dot there, and Dan says he's used to always typing ./ in front of commands. Each shell has an initialization file that lets you change the path variable; you'll learn more about this in the Systems Programming course.
Answer: Yeah, I meant for you to use these functions, and I assumed you would figure it out, since almost the same functions are available in the Character class in Java. You'll have to look up the proper functions to use (the names vary a little from Java). Of course you have to include <ctype.h>. Notice that there is a function that will convert uppercase letters to lowercase and will leave lowercase letters alone.
In general, I want you to do a lot of C programming. I'm never going to be too uptight with some detail about the way you do your programming, as long as you're learning.
Answer: No, I didn't intentionally leave stuff out, although reading in books and digging stuff out is always good for you (the best way to learn). I should have emphasized these matters more because it's a very important part of Unix at the command line. When you read in C with getchar() or with scanf(), the input is coming from the Standard Input, known in C as stdin. At the Unix command line, this means just to type the input at the terminal. However, Unix (and also Zzzzindows) allows re-direction of the input. If you follow the command to execute some file with < somefile.txt, this means to take the input from this file, rather than from the terminal. Think of the < as an arrow pointing from the input into the file to execute. The program reads from this file, and if it keeps reading, eventually it will come to the end of the file, and you will be able to test for this using EOF, since getchar() returns EOF when you try to read a character and there are no more characters left.
You should look at the webpage on copying: Copy Programs, since this stuff is illustrated there (although not fully explained). On that page, one of the commands reads: copy < copy.c > copy2.c. This means that the program copy when it executes and tries to read data will find the file copy.c provided to it for reading, just as if the characters of this file were being typed at the terminal. The othre re-direction above sends the output to the file copy2.c, instead of to the terminal. If a file copy2.c had already existed, it would have been trashed, and the new output would take its place. It's a little weird that I'm copying the C source for the copy program itself, but I like weird things.
Answer: Ctrl-C sends a "break" signal to halt execution of the program (process) that is executing, whether it is Java or C. We don't normally want to plan to terminate execution of our programs using Ctrl-C. Instead, if we are reading from a file, we want to properly check for end-of-file so that we can stop executing the read (or getchar() in this case) by checking to see if there is any more to read (in this case checking if EOF is returned). The while above is not my code but is the way this has been done in C since pre-historic times.
Now in case you are reading directly from the terminal, there's not exactly an end-of-file, since you could always keep typing, but in the Unix world, you can simulate an end-of-file by typing Ctrl-D (the letter after C). To your executing program, it seems exactly the same as if it had come to an end-of-file on the file it was reading. For Recitation 3 and elsewhere, do NOT use Ctrl-C, but either redirect a file in as the standard input or use Ctrl-D to simulate end-of-file.
int isbasedigit(int c,int base){
if ( c > 0 && isdigit(c))
if (c < (base-1))
return 1;
return 0;
}
Answer:
There are several problems with your function:
Answer: We will go over how these main parameters work later. (They are an int and an array of strings.) I assumed that you would just use my code "as is". This is just another convenient way to get numbers into an executable file without directly reading them as input: instead put them on the command line. In this case we are only putting one number, the base to use, on the commmand line. The variable argc holds the number of items on the command line -- in this case it should be 2. What we want is the second argument, the 8, and we get that with the mysterious statement base = atoi(argv[1]); which we will explain later.
In my demonstration program, I just printed "Command-line argument: 8" to show that the code was working properly. In case you use an 8 on the command line, your program is supposed to print "Base: 8" instead. Then you will go on to process the input, either in a file or by typing the input. In case it is in a file, your commands might look like:
% getint_test 8 < rec4_input.txt
Or like:
% getint_test 8 77 100 101 7777 [Enter] [Ctrl-D]
So the base is really separate from the other numbers provided for reading, since the base is on the command line, while any other numbers are either in a file directed in for reading, or are on subsequent lines typed in and read by the program. In case you enter data at the terminal without redirecting, the reading of the data will commence with what follows the command line, after you type [Enter].
I have tried a test:
and also where
I get a number either negative or not even close to the given base. Is there something else I am missing. I have had this error before in other classes I programmed before, but it never affected my results. Can you suggest anything.
Answer: We are going to talk about this stuff. For now I meant for you just to use the code I gave you, namely base = atoi(argv[1]); This converts your input integer value, whatever it is, to an internal int.
Just as a "preview" of things we will discuss shortly, argv[1] is a string in C, which (it turns out), is the same as the address of the first character of the string. Thus dereferencing, ... , *argv[1] will be the first character of the string. If you type 8, then you get the character '8', while if you type 16, then you get the character '1'. All this will be clear soon in the course.
Answer: For Step 2, you need relatively minor changes to the isdigit function, available when you include <ctype.h>, along with several other changes: picking up the command line argument and using it for the number base.
For Step 3 you need heavier-duty changes. I did this part by replacing the isdigit function with my lookup function. This is certainly not the only way to do this part.
Answer: Yeah, this is the way this particular program behaves. Once you get an invalid input (a 0 returned), you have to terminate. This is because the getint() function does an ungetch() in case of an invalid character and returns 0, so if you keep calling getint() in this case you will be in an infinite loop. Your program (not shown above) doesn't even check for a returned 0.
Answer: Remember that the int being read is returned in the reference parameter, not as the value of the function. The function returns either a 0 (could not read an int), or an end-of-file code (actually EOF or -1), or else a positive value to indicate an integer was successfully read. The positive value is the Ascii code for the last character of the integer. So if the function reads a 0, then an integer 0 is returned in the parameter, and the character code for a 0, namely a 48, is returned as the function value. (Wheh!)
The reason I was asking because when I output the string, I have the sentence with no spaces. I was only inserting characters and ignoring everything else and my output looked messy. I was just wondering.
I was also wondering if we can use rec4 since it handles everything and all I need is to include the reverse and strncopy functions, and maybe other modifications.
Answer: Just as you pushed and inserted only letters (converted to lowercase) in Recitation 4, you should insert only letters (converted to lowercase) into the string to be reversed. You will be comparing the original string with the reversed string (letters only) to check for a palindrome. Separately you must output the original characters of the possible palindrome, as we did before. You can construct your program from scratch or by modifying your code for Recitation 4.
Answer: What you say is true only in the case of a "normal" C 2-dimensional array, say declared with a[5][4]. When passing it as a parameter, C needs to know the length of a row, because it is represented as just a 1-dimensional array internally, so the length of a row is needed to pick off the correct row and column.
However, Part C involves the case of an array of pointers to 1-dimensional arrays, where things are quite different. C basically needs to know how many rows there are, and it needs to know the length of each row, since they don't have to be the same length. But knowing these lengths is just to keep from going out of bounds in the array. No lengths are needed to pick off the correct row and column, since for row i and column j, C needs to go to the ith pointer to arrays, and following that pointer, it needs to go to the jth element. The storage for the original array of pointers, and for each 1-dimensional array pointed to must each be contiguous storage, but otherwise this storage can be all over the place.
Arithm Expr RPN Evaluated Result 3^2^2^2$ 3222^^^$ 43046721.000000000000
Is this 3^8 because the result is 3^16 to get 4304... so should it be 3^2^2^2^2?
Answer: No. The exponentiation operator ^ associates right-to-left, so that 3^2^2^2 = 3^(2^(2^2)) = 3^(2^4) = 3^16 = 43046721.
Answer: Yes, first follow Rule 2 and always push a left parenthesis. Otherwise, Rule 3 would say not to push before popping, because a left parenthesis has lower priority than other operators.
Answer: Here goes:
| Output | Stack | Rest of Input | Action | Rule and details |
|---|---|---|---|---|
| 2+3*4-(5^6^7)$ | ||||
| 2 | +3*4-(5^6^7)$ | Output 2 | 1 | |
| 2 | + | 3*4-(5^6^7)$ | Push + | 3 empty stack |
| 23 | + | *4-(5^6^7)$ | Output 3 | 1 |
| 23 | +* | 4-(5^6^7)$ | Push * | 3 + lower prec than * |
| 234 | +* | -(5^6^7)$ | Output 4 | 1 |
| 234* | + | -(5^6^7)$ | Pop * | 4 * higher prec than - |
| 234*+ | -(5^6^7)$ | Pop + | 4 + equal prec to -, L assoc | |
| 234*+ | - | (5^6^7)$ | Push - | 3 empty stack |
| 234*+ | -( | 5^6^7)$ | Push ( | 2 |
| 234*+5 | -( | ^6^7)$ | Output 5 | 1 |
| 234*+5 | -(^ | 6^7)$ | Push ^ | 3 ( lower prec than ^ |
| 234*+56 | -(^ | ^7)$ | Output 6 | 1 |
| 234*+56 | -(^^ | 7)$ | Push ^ | 4 + equal prec to -, R assoc |
| 234*+567 | -(^^ | )$ | Output 7 | 1 |
| 234*+567^ | -(^ | )$ | Pop ^ | 4 ^ higher prec than ) |
| 234*+567^^ | -( | )$ | Pop ^ | 4 ^ higher prec than ) |
| 234*+567^^ | -() | $ | Push ) | 4 ( equal prec to ), R assoc |
| 234*+567^^ | - | $ | Delete () | 6 delete adjacent () on top |
| 234*+567^^- | $ | Pop - | 7 first part | |
| 234*+567^^-$ | Output $ | 7 second part |
Answer: As I wrote in the Recitation, you need two separate stacks, and if they are going to be in the same directory, even function names like empty() need to be different for the two stacks. One holds doubles and the other holds chars. You should use separate files for the implementation of each stack. You should also use separate header files. Thus translate.c will include one header file, and evaluate.c will include the other. The sample stack in Stack can serve as a model for either of the new stacks, except that you should check for underflow and overflow.
Answer: During RPN evaluation, there is no collection of operators. Each operator is immediately applied to two previous operands (on the stack at the time that the operator is encountered), and then you are done with that operator forever.
int pop(Stacktype *ch) {
struct snode *ssave;
if (empty()) return -1;
*ch = s -> c;
ssave = s;
s = s -> next;
free(ssave);
return 0;
}Answer: You need to look at the whole file stack.c. It has a global variable s, which is actually the key variable. This is the stack itself, initialized to NULL (an empty stack). When you push something on, you malloc storage and store a pointer to it in the variable t. Eventually t's value gets assigned to s, and now s points to a non-empty stack. (Here, s is a "global variable", but it is really more like a data member of a stack class.)
#include <stdio.h>
void fopens(FILE *fp, FILE *sp);
int main(void) {
FILE *fp1, *fp2;
char buf[10];
fopens(fp1,fp2);
while (fscanf(fp1,"%s",buf) != EOF) {
fprintf(fp2,"%s\n",buf);
fprintf(stdout,"%s\n",buf);
}
}
void fopens(FILE *fp, FILE *sp) {
fp = fopen("./wordlist","r");
sp = fopen("./swords","w");
}
and it works when I remove my function call and initialize fp1 and fp2 directly. If I try to run as is, I get a core dump.
Answer: This is not correct. C passes parameters by value, meaning that the value of the parameter is copied into the function. In this case, two unitialized file pointers are passed into the function fopens. They are given values inside the function, but these values are lost when you return from the function. You could use a FILE ** parameter, or better, just return the file parameter after opening, but this is what fopen already does.
You can pass the file pointer after opening to a function to read from the file.
Answer: You need to check uppercase for all the letters, and not just the first one. I promised a hint about how to do this. The adding and subtracting 32 works, but it gets unwieldy if you handle more than the first letter. A much better solution is to write your own version of the strcmp function. Inside this function, you should apply the tolower function to each character that you handle (including the characters in the final return). This way no words are changed, but you just have a different string comparison.
Answer: If a 2-dimensional array is declared int a[M][N], where M and N are constants defined with #define, then the general formula for array element a[i][j] is a + N*i + j. In other words, we start at the address of the 0th element of a, then skip over i rows each of length N, and go j further on the row number i. We must know the number N, the length of a row = the number of columns. The formula doesn't need M, the number of rows. You should also have the array subscripts in bounds, that is 0 <= i && i < M && 0 <= j && j < N.
In the special case of the example on the web page, the length of each row is 4. The formual for a[i][j] in this case is a + 4*i + j and NOT just 4*i + j. There is no mention of j = 4 on this page.
Notice that you must not use this formula for an array of pointers to 1-dimensional arrays.
Answer: I looked at your code, and you are making a fairly subtle mistake that others may make also: You are reading each string into a single buffer c in your main function. A pointer to this buffer eventually gets passed to your newnode function:
static struct tnode *newnode(char *c) {
struct tnode *p1 = (struct tnode *)
malloc(sizeof(struct tnode));
p1 -> ch = c;
p1 -> left = p1 -> right = NULL;
printf("Inside newnode: %s\n", p1 -> ch);
return p1;
}
Think about this function carefully. It allocates new storage for the struct, but then the ch is set to point to the original buffer back in main! The first time you do this, it is for the root node. When you read a different word into the buffer, the root node still points to the same buffer, so the root node acts like it has the second word in it, rather than the first.
I hope the fix for this problem will be clear to you. If not, ask me again.
struct hashtable{
int hindex;
int invalid;
struct hnode *hash_node_Table;
}
struct hnode {
char *license; /* license plate number */
int num; /* number of times parked without paying */
}
to create a dynamic hashtable with dynamic nodes, and the table will contain a invalid index to inform me which lic plate is invalid. so I can skip over that plate and look for a new entry point, but if the array is full I can identify an invalid plate, free the location and insert the new plate.
Will this interfere with the lookup of the plate? I was thinking it would, so if my array is full I was just going to print a message, free mem and quit.
Answer: You might be able to something with what you have above, but it is more complicated than I had in mind. Your struct hashtable is still just a single struct with a struct inside it. It's not an array or a collection of nodes, but just a single node.
When I said "hash table", I meant for you just to use a simple array of pointers to struct hnode, either declared as an array, or allocated dynamically with malloc.
struct hnode {
char *license; /* license plate number */
int num; /* number of times parked without paying */
};
and declare an array of these as such...
struct hnode * parking[HSIZE];
To access the license plate in array element 5 I would think it should be
parking[5].license
This is what I have read elsewhere also. However on compile I get an error.
Answer: The variable parking is an array of pointers to structs. Thus parking[5] is a pointer to a struct. You must first dereference it before you can pick off a field in the struct: (*parking[5]).license. In practice, C programmers almost never write that, but instead use the shorthand -> operator: parking[5]) -> license.
Answer: strtol is pretty high-tech, but you can use it. A simple function is just atoi. You can also use sscanf. However, I intended for you just to use fscanf to read the file.
struct gnode{
int V;
int dist;
int shortest;
int status;
struct gnode *next;
}
So when we traverse the graph, visiting the node, we can check the current node, instead of looking in the array.
Answer: This approach is not workable. The problem is that the struct defines an edge, not a vertex. (It is on a list giving all edges that start with a given vertex, and its vertex is the end of one of these edges.) There may be several edges that end in vertex 4, for example, and it won't be clear which one you should use to store the information about a vertex. (Or else it would be a lot of trouble to store the information in each one.)
void shortestpath(){
struct gnode *p;
int i =0;
while (status[i] == 0){
p = g[i];
while (p != NULL){
//brain poop
}
}
}
I just cant figure out how to run down the array and each linked list while at the same keeping track of the weights of the paths to the next vertex... Can you try to explain how to do this with a bit more elaboration?
Answer: OK, I'll take on this challenge. I'm going to be referring to the writeup for Recitation 14, in the section Computing the length of the shortest path from vertex 0 to each vertex. First give values to the two "magic" arrays: all 0's into status and all MAXPOS into shortest, except that shortest[0] is set to 0.
Now comes the part that is bothering you.
So in pseudocode, your loop starts out:
while (there's still some i with status[i] == 0) {
pick i for which shortest[i] is smallest, among those with status[i] == 0;
...
}
Of course you're going to need an inner loop to evaluate the while condition. Good luck!
#include#define N 5 /* for this particular graph */ struct gnode { /* node in the linked list following each vertex$ int v; /* vertex at the other end (at the arrow) */ int dist; /* the weigth on this edge */ struct gnode *next; /* next vertex in the linked list */ }; struct gnode *g[N]; /* the graph: an array of pointers to the list node$ int status[N]; /* vertex has not been processed (0) or has been (1$ int shortest[N]; /* final length of the shortest path to each vertex$ int main (void) { FILE *infile; infile = fopen("edges.dat","r"); int i=0; int cv; /* cv = current vertex */ for (i=0; i<1; i++) { cv = getnum(infile); (*g[cv]).v = getnum (infile); (*g[cv]).dist = getnum (infile); } printf ("v: %i dist: %i\n", (*g[cv]).v, (*g[cv]).dist); return (0); } void dumpgraph(struct gnode *g[]) { int i; struct gnode *p; for (i = 0; i < N; i++) { printf("g[%i]: ", i); p = g[i]; while (p != NULL) { printf("--> (%i,%i) ", p -> v, p -> dist); p = p -> next; } printf("--> NULL\n"); } } int getnum (FILE *fp) { int j; char number [10]; fscanf (fp, "%s", number); j=atoi(number); return j; }
Answer: (You must be using a C++ compiler that doesn't require all declarations at the start. That's OK.) First of all, (*g[cv]).v is correct, but nobody writes this. Instead they write the equivalent: g[cv] -> v.
Your function getnum should work, but it would be easier just to write: fscanf(fp, "%i", &j); and then return j.
Your program has a fundamental flaw related to not allocating storage. First you declare struct gnode *g[N];. This is an array of N pointers to the struct, all initialized to the NULL pointer. To actually put any data into one of the structs, you will need to allocate storage: After you read a value for cv, you will need:
g[cv] = (struct gnode *)malloc(sizeof(struct gnode));
Now you could store values into the two fields.
Another problem: You should only do the above in case g[cv] is NULL. If it isn't NULL, then you already have at least one vertex patched in. For the next vertex that comes along, you will need to allocate another struct and patch it into the head of a linked list starting with g[cv]. (This means setting the next field of the new struct to point where g[cv] points, and then setting g[cv] to point to the new struct.)
I didn't debug the above code, so there may be other problems. (In particular the code above will need to read till EOF.)