c-iaq.html

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

		<H4><A NAME="question-4.1"></A>4.1: What is this infamous null statement, anyway? </H4>
		<P>A null statement is an expression statement consisting solely
		of the terminating semicolon. The optional expression is dropped.
		It can be distinguished from any other statement by byte count
		or study of side-effects. </P>
		<H4><A NAME="question-4.2"></A>4.2: How do I ``get'' a null statement in my programs? </H4>
		<P>In ANSI C, there are six types of statements; labeled statements,
		compound statements, expression-statements, selection statements,
		iteration statements, and jump statements. All of them, except
		the jump and expression statments, are defined in terms of optional
		preceeding text, and other statements. The jump statements are
		never null statements. An expression statement is considered to
		be ``a null statement'' if the optional expression part of it
		has been left out. A null statement can appear on its own, or
		(most frequently) as the statement body of an iteration statement.
		These two null statements are equivalent, though neither of them
		is equivalent to any non-null statement. [*] </P>
		<P>You may accidentally get a null statement by deleting the body
		of a non-null statement. </P>
		<P>[*] Actually, they are functionally equivalent to a large set
		of non-null statements, namely, those with no side-effects. However,
		the FDA has yet to approve any such, as their lack of side effects
		is conjectured, and not clinically proven. This applies only to
		the ANSI standard, and not the ISO standard, as the FDA has no
		jurisdiction outside the U.S. [<A HREF="c-iaq-a.html#question-4.2">a</A>]</P>
		<H4><A NAME="question-4.3"></A>4.3: Is there more than one null statement?</H4>
		<P>Sort of. You can use ``;'', ``0;'', or ``1;'' - they will all
		act like a null statement. Only the first is a ``true'' null statement
		(all bits zero). They are basically equivalent. Note that (void
		*) 0; is a null statement of type pointer to void, for instance.
		[<A HREF="c-iaq-a.html#question-4.3">a</A>]</P>
		<H4><A NAME="question-4.4"></A>4.4: But I thought <CODE>{ }</CODE> was a null statement!</H4>
		<P>No. <CODE>{ statement-list[opt] }</CODE> is a compound statement. An empty block is not the same as a
		null statement, however, although it can be used in many of the
		same places. It's really a null block. (You can convert it with
		a cast, but it's not directly compatible. For instance, you can't
		use a null block as one of the controlling statements of a for
		loop.) </P>
		<H4><A NAME="question-4.5"></A>4.5: I use the statement <CODE>#define NULLSTMT(F) (F) ;</CODE> to allow me to cast a null statement to an appropriate type.</H4>
		<P>This trick, though popular in some circles, does not buy much.
		The resulting code is invalid, and will not compile. This (in
		the author's opinion) outweighs any arguable type consistency.
		It may be more common in industrial code. If it becomes common
		practice, C++ will probably legalize it. [<A HREF="c-iaq-a.html#question-4.5">a</A>]</P>
		<H4><A NAME="question-4.6"></A>4.6: I use the statement <CODE>#define NULLSTMT(F) (F) 0;</CODE> to allow me to cast a null statement to an appropriate type.</H4>
		<P>This trick will likely work, but think: what does it really buy
		you? Mostly, it will indicate to even the most casual observer
		that you are shakey on the concept of null statements, making
		it harder for them to check your code. </P>
		<H4><A NAME="question-4.7"></A>4.7: But wouldn't it be better to use <CODE>;</CODE> (rather than <CODE>0;</CODE>) in case the value of 0 changes, perhaps on a machine with nonzero
		no-op instructions? </H4>
		
<P>No. The '<CODE>0</CODE>' of '<CODE>0;</CODE>' is not evaluated as an instruction, 
  rather, it is just ignored. The only reason to use '<CODE>0;</CODE>' instead 
  of '<CODE>;</CODE>' is to help keep 1-heavy code properly balanced (in C, which 
  uses binary representations for numbers, it is possible for code to become unbalanced; 
  an unbalanced binary tree is a common source of poor performance.</P>
		<H4><A NAME="question-4.8"></A>4.8: Is a null statement a null pointer? </H4>
		<P>No. A null pointer is a pointer where all of the address bits
		are zero (no matter what the segment bits are), and can be obtained
		by typing '(char *) (int) 0'. A null statement is not a pointer
		to anything. They are not interchangeable, although you can combine
		them to get an effectively-null statement, such as <CODE>NULL;</CODE>. This does not buy you anything. [<A HREF="c-iaq-a.html#question-4.8">a</A>]</P>
		<H4><A NAME="question-4.9"></A>4.9: I'm still confused. I just can't understand all this null
		statement stuff. </H4>
		<P>Follow these two simple rules: </P>
		<OL>
			<LI>When you don't want to do anything in source code, don't write
			it. 
			<LI>If you need a null statement to round out an expression, use an
			unadorned <CODE>;</CODE> to provide it. 
			<LI>Send large donations, checks, and money orders to the author of
			the FAQ, or the moderator of the group, whichever you prefer.
			Then, cross the top question off the FAQ, answer the question
			at the bottom, and mail it to three people. Within two weeks,
			you will receive 729 answers to various questions! Do not break
			the chain; Emily Postnews broke the chain, and now no one listens
			to her. [<A HREF="c-iaq-a.html#question-4.9">a</A>] 
		</OL>
		<H3><A NAME="section-5"></A>Section 5: Arrays and Pointers</H3>
		<H4><A NAME="question-5.1"></A>5.1: I had the definition <CODE>char a[6]</CODE> in one source file, and in another I declared <CODE>extern char a[]</CODE>. Why did it work?</H4>
		<P>The declaration <CODE>extern char a[]</CODE> simply matches the actual definition. The type ``array-of-type-T''
		is the same as ``array-of-type-T.'' Go ahead and use <CODE>extern char a[]</CODE>. (For greater portability, use it in both files, not only in
		one of them.) [<A HREF="c-iaq-a.html#question-5.1">a</A>]</P>
		<H4><A NAME="question-5.2"></A>5.2: But I heard that <CODE>char a[]</CODE> was different from <CODE>char a[6]</CODE>.</H4>
		<P>This is true. However, the declaration <CODE>a[]</CODE> is compatible with the definition <CODE>a[6]</CODE>.</P>
		<H4><A NAME="question-5.3"></A>5.3: So what is meant by the ``equivalence of pointers and arrays''
		in C?</H4>
		<P>Very little.</P>
		<H4><A NAME="question-5.4"></A>5.4: Then why are array and pointer declarations interchangeable
		as function formal parameters?</H4>
		<P>Classism. We consider arrays ``second class objects''. They don't
		vote, and they get treated as pointers. Additionally, they're
		merely objects, not citizens. Marx wrote about this a lot. [<A HREF="c-iaq-a.html#question-5.4">a</A>]</P>
		<H4><A NAME="question-5.5"></A>5.5: Why doesn't sizeof properly report the size of an array which
		is a parameter to a function? </H4>
		<P>Part of the ANSI conspiracy to restrict people to passing pointers;
		this was undertaken after the first discovery that passing large
		arrays recursively could cause crashes. Since then, with the passing
		of MS-DOS, it has become a non-issue; since all serious machines
		have virtual memory, you can pass as much data as you want on
		the stack without detectable problems. [<A HREF="c-iaq-a.html#question-5.5">a</A>]</P>
		<H4><A NAME="question-5.6"></A>5.6: Someone explained to me that arrays were really just constant
		pointers. </H4>
		<P>Cool. Someone I know says he saw Elvis in a local bar. [<A HREF="c-iaq-a.html#question-5.6">a</A>]</P>
		<H4><A NAME="question-5.7"></A>5.7: Practically speaking, what is the difference between arrays
		and pointers? </H4>
		<P>About the difference between alcohol and marijuana; they have
		different characteristics, and that's not a problem if you don't
		mix them too carelessly. </P>
		<H4><A NAME="question-5.8"></A>5.8: I came across some ``joke'' code containing the ``expression''
		<CODE>5[&quot;abcdef&quot;]</CODE>. How can this be legal C? </H4>
<P>It was added to allow people to avoid the character constant 'f' which may 
  not be available on some systems. (Actually, it's a side-effect of the equivalence 
  of arrays and pointers.) [<A HREF="c-iaq-a.html#question-5.8">a</A>]</P>
		<H4><A NAME="question-5.9"></A>5.9: How would I initialize an entire array from standard input?
		</H4>
		<P>You have to use a loop. For instance, the following code reads
		the numbers zero through 99 into the array a. </P>
		<PRE>for (i = 0; i &lt; 100; ++i)
	a[i] = (scanf, (&quot;%d&quot;, i));</PRE>
		<P>Make sure to include <CODE>&lt;stdio.h&gt;</CODE>, or this may not work. [<A HREF="c-iaq-a.html#question-5.9">a</A>]</P>
		<H3><A NAME="section-6"></A>Section 6: Memory Allocation</H3>
		<H4><A NAME="question-6.1"></A>6.1: Why doesn't this fragment work? </H4>
		<PRE>	char *answer
	printf(&quot;Type something:\n&quot;);
	gets(answer);
	printf(&quot;You typed \&quot;%s\&quot;\n&quot;, answer);</PRE>
<P>The semicolon after ``answer'' is missing. [<a href="c-iaq-a.html#question-6.1">a</a>]</P>
		<H4><A NAME="question-6.2"></A>6.2: I have a function that is supposed to return a string, but
		when it returns to its caller, the returned string is garbage.
		</H4>
		<P>You probably returned a pointer to a local array. That doesn't
		work. Try using a temporary file, instead. For instance: </P>
		<PRE>char *getstr(void) {
	FILE *fp = tmpfile();
	fputs(gets(NULL), fp);
	return (char *) fp;
}</PRE>
		<H4><A NAME="question-6.3"></A>6.3: Why does some code carefully cast the values returned by
		malloc to the pointer type being allocated? </H4>
		
<P>In interrupt-riddled code, it may be necessary to cast values to force the 
  CPU to resolve pointer types. [<a href="c-iaq-a.html#question-6.3">a</a>]</P>
		<H4><A NAME="question-6.4"></A>6.4: You can't use dynamically-allocated memory after you free
		it, can you? </H4>
		<P>Yes. However, what happens when you do is not clearly defined.
		</P>
		<H4><A NAME="question-6.5"></A>6.5: How does free() know how many bytes to free? </H4>
		
<P>Interrupt 41h. On macs, amigas, and other ``big-endian'' processors, that would 
  be interrupt 14h; be wary of portability problems. [<a href="c-iaq-a.html#question-6.5">a</a>]</P>
		<H4><A NAME="question-6.6"></A>6.6: So can I query the malloc package to find out how big an
		allocated block is? </H4>
		<P>Not exactly; because the objects are dynamically allocated, their
		size can change at run time, so this will not be reliable. If
		you restrict your allocation to allocating sizeof(void *) bytes
		at a time, you will find that you can use sizeof() to get the
		size of a block, in the obvious way. </P>
		<H4><A NAME="question-6.7"></A>6.7: I'm allocating structures which contain pointers to other
		dynamically-allocated objects. When I free a structure, do I have
		to free each subsidiary pointer first? </H4>
		<P>No. You just have to keep track of them somewhere else also. </P>
		<H4><A NAME="question-6.8"></A>6.8: Was Proust's masterwork, <CITE>A Remembrance of Things Past</CITE>, the basis for the C library's allocation scheme, based largely
		on contextual analysis? </H4>
		<P>The standard does not specify an allocation scheme; the famous
		author the allocation scheme is based on is implementation specified.
		Proust is a common choice, however. </P>
		<H4><A NAME="question-6.9"></A>6.9: I have a program which mallocs but then frees a lot of memory,
		but memory usage (as reported by ps) doesn't seem to go back down.
		</H4>
		<P>You're probably not freeing the memory completely. Try replacing
		'<CODE>free(foo);</CODE>' with</P>
		<PRE>free(foo);
free(foo);
free(foo);</PRE>
		
<P>in case the first <code>free()</code> frees the memory only partially. (Unix 
  wizards may recognize the parallel with syncing three times before rebooting.) 
</P>
		<P>Alternatively, free(foo) + 4; may free the remaining four bytes.
		(Before using this, make sure realloc(foo, 0) returned 4). </P>
		<H3><A NAME="section-7"></A>Section 7: Characters and Strings</H3>
		<H4><A NAME="question-7.1"></A>7.1: How can I get the numeric (character set) value corresponding
		to a character, or vice versa? </H4>
		<P>The obvious way is to write a function to do the conversion. (Error
		checking has been omitted for brevity.) </P>
		<PRE>int ctoi(char c) {
	static unsigned char *ary;
	/* initialize the array */
	if (!ary) {
		int i;

		ary = malloc(UCHAR_MAX + 2);
		for (i = 0; i &lt; UCHAR_MAX + 1; ++i) {
			ary[i] = i;
		}
		ary[UCHAR_MAX + 1] = '\0';
	}
	if (c) {
		unsigned char *t;

		/* we have to skip the leading NUL */
		t = strchr(ary + 1, c);
		if (!t)
			return 0;
		return t - ary;
	} else {
		/* special case for NUL character */
		return 0;
	}
}</PRE>
<P>There are various clever tricks you can use to get around writing the function, 
  but most are too complicated for beginners. [<a href="c-iaq-a.html#question-7.1">a</a>]</P>
		<H3><A NAME="section-8"></A>Section 8: Boolean Expressions and Variables</H3>
		<H4><A NAME="question-8.1"></A>8.1: What is the right type to use for boolean values in C? Why
		isn't it a standard type? Should <CODE>#define</CODE>s or <CODE>enum</CODE>s be used for the true and false values? </H4>
		<P><CODE>int (*)(int, char **)</CODE> makes a good boolean type. You can use <CODE>main</CODE> for true, and <CODE>exit</CODE> for false. On some compilers, you may need to cast <CODE>exit()</CODE> to an appropriate type. </P>
		<H4><A NAME="question-8.2"></A>8.2: Isn't <CODE>#defining</CODE> TRUE to be 1 dangerous, since any nonzero value is considered
		``true'' in C? What if a built-in boolean or relational operator
		``returns'' something other than 1? </H4>
		<P>Very good! For instance, one program I saw used </P>
		<PRE>#define TRUE(x) ((x) &amp; 0x100)</PRE>
		<P>for compatability with a specific release of a FORTRAN compiler,
		which used 0 for .FALSE. and 256 for .TRUE. - this allowed them
		to change their code with every new release of the FORTRAN compiler,
		and kept them alert to changes. This has no relationship to the
		boolean or logical operators in C, which always return 0 or 1.
		</P>
		<H4><A NAME="question-8.3"></A>8.3: What is truth? </H4>
		
<P>It is not a saffron-robed monk, pissing in the snow. [<a href="c-iaq-a.html#question-8.3">a</a>]</P>
		<H3><A NAME="section-9"></A>Section 9: C Preprocessor</H3>
		<H4><A NAME="question-9.1"></A>9.1: How can I use a preprocessor <CODE>#if</CODE> expression to tell if a machine is big-endian or little-endian?
		</H4>
		
<P><CODE>#ifdef __BIG_ENDIAN</CODE> should work on all known machines; Borland 
  defines it. [<a href="c-iaq-a.html#question-9.1">a</a>]</P>
		<H4><A NAME="question-9.2"></A>9.2: I've got this tricky processing I want to do at compile time
		and I can't figure out a way to get cpp to do it. </H4>
		<P>Poor baby. </P>
		<H4><A NAME="question-9.3"></A>9.3: How can I list all of the pre-<CODE>#define</CODE>d identifiers? </H4>
		<P><CODE>#define __ALL_CPP_IDS</CODE> - put this in a source file, and run it through your C preprocessor.
		</P>
		<H4><A NAME="question-9.4"></A>9.4: How can I write a cpp macro which takes a variable number
		of arguments? </H4>
		<P>Try something like this: </P>
		<PRE>

#define add(x) (x)
#define add(x, y) (x + y)