📄 chapter 9 structures -- valvano.htm
字号:
data<BR> pt->next=HeadPt; //
link into
existing<BR> HeadPt=pt;<BR> return(1);<BR> }<BR> return(0); //
out of memory<BR>};</CODE></P></DIR>
<ADDRESS>Listing 9-9: Code to add a node at the beginning of a linear linked
list</ADDRESS>
<P><FONT face="Times New Roman,Times">In order to search the list we start at
the <B>HeadPt</B>, and stop when the pointer becomes <B>null</B>. The routine
<B>Search</B> will return a pointer to the node if found, and it will return a
null-pointer if the data is not found.</FONT></P>
<DIR>
<P><CODE>nodeType *Search(unsigned short info){ nodeType
*pt;<BR> pt=HeadPt;<BR> while(pt){<BR> if(pt->data==info)<BR> return
(pt);<BR> pt=pt->next; // link to
next<BR> }<BR> return(pt); //
not found<BR>};</CODE></P></DIR>
<ADDRESS>Listing 9-10: Code to find a node in a linear linked list</ADDRESS>
<P><FONT face="Times New Roman,Times">To count the number of elements, we again
start at the <B>HeadPt</B>, and stop when the pointer becomes <B>null</B>. The
routine <B>Count</B> will return the number of elements in the list.</FONT></P>
<DIR>
<P><CODE>unsigned short Count(void){ nodeType *pt;<BR> unsigned short
cnt;<BR> cnt=0;<BR> pt=HeadPt;<BR> while(pt){<BR> cnt++;<BR> pt=pt->next; //
link to next<BR> }<BR> return(cnt);<BR>};</CODE></P></DIR>
<ADDRESS>Listing 9-11: Code to count the number of nodes in a linear linked
list</ADDRESS>
<P><FONT face="Times New Roman,Times">If we wanted to maintain a sorted list,
then we can insert new data at the proper place, in between data elements
smaller and larger than the one we are inserting. In the following figure we are
inserting the element 250 in between elements 200 and 300. </FONT></P>
<P><IMG height=257 src="Chapter 9 Structures -- Valvano.files/link2.gif"
width=430></P>
<ADDRESS>Figure 9-4: Inserting a node in sorted order</ADDRESS>
<P><FONT face="Times New Roman,Times">In case 1, the list is initially empty,
and this new element is the first and only one. In case 2, the new element is
inserted at the front of the list because it has the smallest data value. Case 3
is the general case depicted in the above figure. In this situation, the new
element is placed in between <B>firstPt</B> and <B>secondPt</B>. In case 4, the
new element is placed at the end of the list because it has the largest data
value.</FONT></P>
<DIR>
<P><CODE>#include <STDLIB.H>;<BR>int InsertData(unsigned short info){
<BR>nodeType
*firstPt,*secondPt,*newPt;<BR> newPt=malloc(sizeof(nodeType)); //
create a new
entry<BR> if(newPt){<BR> newPt->data=info; //
store data<BR> if(HeadPt==0){ // case
1<BR> newPt->next=HeadPt; //
only
element<BR> HeadPt=newPt;<BR> return(1);<BR> }<BR> if(info<=HeadPt->data){ //
case
2<BR> newPt->next=HeadPt; //
first element in
list<BR> HeadPt=newPt;<BR> return(1);<BR> }<BR> firstPt=HeadPt; //
search from
beginning<BR> secondPt=HeadPt->next; <BR> while(secondPt){<BR> if(info<=secondPt->data){ //
case
3<BR> newPt->next=secondPt; //
insert element
here<BR> firstPt->next=newPt;<BR> return(1);<BR> }<BR> firstPt=secondPt; //
search
next<BR> secondPt=secondPt->next; <BR> }<BR> newPt->next=secondPt; //
case 4, insert at
end<BR> firstPt->next=newPt;<BR> return(1);<BR> }<BR> return(0); //
out of memory<BR>};</CODE></P></DIR>
<ADDRESS>Listing 9-12: Code to insert a node in a sorted linear linked
list</ADDRESS>
<P><FONT face="Times New Roman,Times">The following function will search and
remove a node from the linked list. Case 1 is the situation in which an attempt
is made to remove an element from an empty list. The return value of zero
signifies the attempt failed. In case 2, the first element is removed. In this
situation the <B>HeadPt</B> must be updated to now point to the second element.
It is possible the second element does not exist, because the list orginally had
only one element. This is OK because in this situation <B>HeadPt</B> will be set
to null signifying the list is now empty. Case 3 is the general situation in
which the element at <B>secondPt</B> is removed. The element before,
<B>firstPt</B>, is now linked to the element after. Case 4 is the situation
where the element that was requested to be removed did not exist. In this case,
the return value of zero signifies the request failed.</FONT></P>
<DIR>
<P><CODE>#include <STDLIB.H>;<BR>int Remove(unsigned short info){
<BR>nodeType *firstPt,*secondPt;<BR> if(HeadPt==0) // case
1<BR> return(0); // empty
list<BR> firstPt=HeadPt;<BR> secondPt=HeadPt->next;<BR> if(info==HeadPt->data){ //
case 2<BR> HeadPt=secondPt; // remove first element
in list<BR> free(firstPt); // return
unneeded memory to
heap<BR> return(1);<BR> }<BR> while(secondPt){<BR> if(secondPt->data==info){ //
case
3<BR> firstPt->next=secondPt->next; //
remove this
one<BR> free(secondPt); //
return unneeded memory to
heap<BR> return(1);<BR> }<BR> firstPt=secondPt; //
search
next<BR> secondPt=secondPt->next; <BR> }<BR> return(0); //
case 4, not found<BR>};</CODE></P></DIR>
<ADDRESS>Listing 9-13: Code to remove a node from a sorted linear linked
list</ADDRESS>
<P><B><I><FONT face=Helvetica,Arial><A name=HUFFMAN></A>Example of a Huffman
Code</FONT></I></B></P>
<P><FONT face="Times New Roman,Times">When information is stored or transmitted
there is a fixed cost for each bit. Data compression and decompression provide a
means to reduce this cost without loss of information. If the sending computer
compresses a message before transmission and the receiving computer decompresses
it at the destination, the effective bandwidth is increased. In particular, this
example introduces a way to process bit streams using Huffman encoding and
decoding. A typical application is illustrated by the following flow
diagram.</FONT></P>
<P><IMG height=151 src="Chapter 9 Structures -- Valvano.files/huff1.gif"
width=408></P>
<ADDRESS>Figure 9-5: Data flow diagram showing a typical application of Huffman
encoding and decoding</ADDRESS>
<P> </P>
<P><FONT face="Times New Roman,Times">The Huffman code is similar to the Morse
code in that they both use short patterns for letters that occur more
frequently. In regular ASCII, all characters are encoded with the same number of
bits (8). Conversely, with the Huffman code, we assign codes where the number of
bits to encode each letter varies. In this way, we can use short codes for
letter like "e s i a t o n" (that have a higher probability of occurrence) and
long codes for seldom used consonants like "j q w z" (that have a lower
probability of occurrence). To illustrate the encode-decode operations, consider
the following Huffman code for the letters M,I,P,S. S is encoded as "0", I as
"10", P as "110" and M as "111". We can store a Huffman code as a binary
tree.</FONT></P>
<P><IMG height=120 src="Chapter 9 Structures -- Valvano.files/huff2.gif"
width=130></P>
<ADDRESS>Figure 9-6: Huffman code for the letters S I P M</ADDRESS>
<P> </P>
<P><FONT face="Times New Roman,Times">If "MISSISSIPPI" were to be stored in
ASCII, it would require 10 bytes or 80 bits. With this simple Huffman code, the
same string can be stored in 21 bits. </FONT></P>
<P><IMG height=60 src="Chapter 9 Structures -- Valvano.files/huff3.gif"
width=191></P>
<ADDRESS>Figure 9-7: Huffman encoding for MISSISSIPPI</ADDRESS>
<P> </P>
<P><FONT face="Times New Roman,Times">Of course, this Huffman code can only
handle 4 letters, while the ASCII code has 128 possibilities, so it is not fair
to claim we have an 80 to 21 bit savings. Nevertheless, for information that has
a wide range of individual probabilities of occurrence, a Huffman code will be
efficient. In the following implementation the functions <B>BitPut() </B>and
<B>BitGet()</B> are called to save and recover binary data. The implementations
of these two functions were presented back in </FONT><A
href="http://www.ece.utexas.edu/~valvano/embed/chap2/chap2.htm#BITFIFO">Chapter
2</A><FONT face="Times New Roman,Times">.</FONT></P>
<P> </P>
<DIR>
<P><CODE>const struct Node{<BR> char Letter0; // ASCII code if binary 0<BR> char Letter1; // ASCII code if binary 1<BR>// Letter1 is NULL(0) if Link is pointer to another node<BR> const struct Node *Link;}; // binary tree pointer <BR>typedef const struct Node NodeType;<BR>typedef NodeType * NodePtr;<BR>// Huffman tree<BR>NodeType twentysixth= {'Q','Z',0};<BR>NodeType twentyfifth= {'X',0,&twentysixth}; <BR>NodeType twentyfourth={'G',0,&twentyfifth}; <BR>NodeType twentythird= {'J',0,&twentyfourth}; <BR>NodeType twentysecond={'W',0,&twentythird}; <BR>NodeType twentyfirst= {'V',0,&twentysecond}; <BR>NodeType twentyth= {'H',0,&twentyfirst}; <BR>NodeType ninteenth= {'F',0,&twentyth}; <BR>NodeType eighteenth= {'B',0,&ninteenth}; <BR>NodeType seventeenth= {'K',0,&eighteenth}; <BR>NodeType sixteenth= {'D',0,&seventeenth}; <BR>NodeType fifteenth= {'P',0,&sixteenth}; <BR>NodeType fourteenth= {'M',0,&fifteenth}; <BR>NodeType thirteenth= {'Y',0,&fourteenth}; <BR>NodeType twelfth= {'L',0,&thirteenth}; <BR>NodeType eleventh= {'U',0,&twelfth}; <BR>NodeType tenth= {'R',0,&eleventh}; <BR>NodeType ninth= {'C',0,&tenth}; <BR>NodeType eighth= {'O',0,&ninth}; <BR>NodeType seventh= {' ',0,&eighth}; <BR>NodeType sixth= {'N',0,&seventh}; <BR>NodeType fifth= {'I',0,&sixth}; <BR>NodeType fourth= {'S',0,&fifth}; <BR>NodeType third= {'T',0,&fourth}; <BR>NodeType second= {'A',0,&third}; <BR>NodeType root= {'E',0,&second};<BR>//********encode*************** <BR>// convert ASCII string to Huffman bit sequence<BR>// returns bit count if OK<BR>// returns 0 if BitFifo Full<BR>// returns 0xFFFF if illegal character<BR>int encode(char *sPt){ // null-terminated ASCII string<BR> int NotFound; char data;<BR> int BitCount=0; // number of bits created<BR> NodePtr hpt; // pointer into Huffman tree<BR> while (data=(*sPt)){<BR> sPt++; // next character<BR> hpt=&root; // start search at root<BR> NotFound=1; // changes to 0 when found<BR> while(NotFound){<BR> if ((hpt->Letter0)==data){<BR> if(!BitPut(0)) <BR> return (0); // data structure full<BR> BitCount++;<BR> NotFound=0; }<BR> else {<BR> if(!BitPut(1)) <BR> return (0); // data structure full<BR> BitCount++;<BR> if ((hpt->Letter1)==data) <BR> NotFound=0;<BR> else { // doesn't match either Letter0 or Letter1<BR> hpt=hpt->Link;<BR> if (hpt==0) return (0xFFFF); // illegal, end of tree?<BR> }<BR> }<BR> }<BR> }<BR> return BitCount; <BR> }<BR>//********decode*************** <BR>// convert Huffman bit sequence to ASCII<BR>// will remove from the BitFifo until it is empty<BR>// returns character count<BR>int decode(char *sPt){ // null-terminated ASCII string<BR> int CharCount=0; // number of ASCII characters created<BR> int NotFound; unsigned int data;<BR> NodePtr hpt; // pointer into Huffman tree<BR> hpt=&root; // start search at root<BR> while (BitGet(&data)){ <BR> if (data==0){<BR> (*sPt)= (hpt->Letter0);<BR> sPt++;<BR> CharCount++;<BR> hpt=&root;} // start over and search at root<BR> else //data is 1<BR> if((hpt->Link)==0){ <BR> (*sPt)= (hpt->Letter1);<BR> sPt++;<BR> CharCount++;<BR> hpt=&root;} // start over and search at root<BR> else { // doesn't match either Letter0 or Letter1<BR> hpt=hpt->Link;<BR> }<BR> }<BR> (*sPt)=0; // null terminated<BR> return CharCount; <BR> }</CODE></P></DIR>
<ADDRESS><FONT face="Times New Roman,Times">Listing 9-14: A Huffman code
implementation</FONT></ADDRESS>
<P> </P>
<DIR>
<DIR>
<P> </P></DIR></DIR>
<P><FONT face="Times New Roman,Times">Go to <A
href="http://www.ece.utexas.edu/~valvano/embed/chap10/chap10.htm">Chapter 10 on
Functions</A> Return to <A
href="http://www.ece.utexas.edu/~valvano/embed/toc1.htm">Table of Contents</A>
</FONT></P></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -