This is the code form section 6.5 of K&R2:
struct tnode
{
char *word;
int count;
struct tnode *left;
struct tnode *right;
};
struct tnode *add_node( struct tnode *p, char *w )
{
int cond;
if ( !p )
{
p = talloc();
p->word = strdup( w );
p->count = 1;
p->left = p->right = NULL;
}
else if( !(cond = strcmp( w, p->word )) )
{
p->count++;
}
else if( cond < 0 )
{
p->left = add_node( p->left, w );
}
else if( cond 0 )
{
p->right = add_node( p->right, w );
}
return p;
}
/* aloocate memory for new node */
struct tnode *talloc( void )
{
return malloc( sizeof( struct tnode ) );
}
for input:
"Now is the time for all good men to come to the aid
of their party"
This produces a tree like this:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
This is an unbalanced-tree, where balanced factor is:
(1 - 3) = -2
balance factor = (height of right-subtree) - (height of left-subtree)
right-subtree starts with word "the" which has only 1 child-node.
left-subtree starts with "is" and it has 3 nodes
Can I convert this binary-tree into an AVL tree which has a balance factor
of 1, 0 or -1 ? I am not able to change the code to do that
conversion.
-- http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :) 8  1587 
On Mon, 12 May 2008 11:44:18 +0500, arnuld wrote:
This is the code form section 6.5 of K&R2:
...SNIP...
This produces a tree like this:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
..SNIP..
eh... I don't understand why the tree is not looking like the way I typed.
Si I type again:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
BTW, most folks have K&R2 already. Though Ben Bacarisse has K&R only ;) .
-- http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)
arnuld <su*****@see.si gs.invalidwrite s:
now
/ \
is the
/ \ / \
for men of time
/ \ \ / \
all good party their to
/ \
aid come
This is an unbalanced-tree, where balanced factor is:
(1 - 3) = -2
balance factor = (height of right-subtree) - (height of left-subtree)
I don't see how you get a balance factor of -2 from that tree. I
see a balance factor of -1:
now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come
The right child of "now" has height 3. The left child of "now"
has height 4. The difference is -1.
right-subtree starts with word "the" which has only 1 child-node.
"the" has two children: "of" and "time".
left-subtree starts with "is" and it has 3 nodes
"is" also has two children: "for" and "men".
--
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void){unsi gned long b[]
={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,0xa67f6aaa,0xa a9aa9f6,0x11f6} ,*p
=b,i=24;for(;p+ =!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)bre ak;else default:continu e;if(0)case 1:putchar(a[i&15]);break;}}}
On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:
I don't see how you get a balance factor of -2 from that tree. I
see a balance factor of -1:
now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come
The right child of "now" has height 3. The left child of "now"
has height 4. The difference is -1.
I thought you don't count the nodes with single-child but I was wrong.
Now it has a balance factor of -1 but cab I call it an AVL tree ?
-- http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)
On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:
...SNIP...
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void)
{unsignedlong b[]={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,
0xa67f6aaa,0xaa 9aa9f6,0x11f6}, *p=b,i=24;for(; p+=!*p;*p/=4)switch
(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+ 2:{i++;if(i)bre ak;else
default:continu e;if(0)case1:pu tchar(a[i&15]);break;}}}
gcc -ansi -pedantic -Wall -Wextra test.c
: In function `main':
: warning: control reaches end of non-void function
;)
-- http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)
arnuld said:
>On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:
>...SNIP...
>char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void)
{unsignedlon g b[]={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,
0xa67f6aaa,0xa a9aa9f6,0x11f6} ,*p=b,i=24;for( ;p+=!*p;*p/=4)switch
(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+ 2:{i++;if(i)bre ak;else
default:contin ue;if(0)case1:p utchar(a[i&15]);break;}}}
gcc -ansi -pedantic -Wall -Wextra test.c
: In function `main':
: warning: control reaches end of non-void function
;)
gcc is mistaken. Control does not reach the end of that function at all,
except via the return statement in line 16 (after indenting with the
canonical options, i.e. mine).
--
Richard Heathfield <http://www.cpax.org.uk >
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999
arnuld <su*****@see.si gs.invalidwrite s:
>On Mon, 12 May 2008 09:17:46 -0700, Ben Pfaff wrote:
>I don't see how you get a balance factor of -2 from that tree. I
see a balance factor of -1:
now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come
The right child of "now" has height 3. The left child of "now"
has height 4. The difference is -1.
I thought you don't count the nodes with single-child but I was wrong.
Now it has a balance factor of -1 but cab I call it an AVL tree ?
No, because "is" has a balance factor of -2 (1 minus 3).
--
char a[]="\n .CJacehknorstu" ;int putchar(int);in t main(void){unsi gned long b[]
={0x67dffdff,0x 9aa9aa6a,0xa77f fda9,0x7da6aa6a ,0xa67f6aaa,0xa a9aa9f6,0x11f6} ,*p
=b,i=24;for(;p+ =!*p;*p/=4)switch(0[p]&3)case 0:{return 0;for(p--;i--;i--)case+
2:{i++;if(i)bre ak;else default:continu e;if(0)case 1:putchar(a[i&15]);break;}}}
On Tue, 13 May 2008 10:15:01 -0700, Ben Pfaff wrote:
now
/ \
^ is the ^
| / \ / \ |
height | for men of time | height
4 | / \ \ / \ | 3
| all good party their to V
| / \
V aid come
No, because "is" has a balance factor of -2 (1 minus 3).
Oh... Now I got it, every node ( whether child or root) in AVL tree must
have a balance factor of -1,0 or 1.
right ?
-- http://lispmachine.wordpress.com/
my email ID is @ the above blog.
just check the "About Myself" page :)
arnuld <su*****@see.si gs.invalidwrite s:
Oh... Now I got it, every node ( whether child or root) in AVL tree must
have a balance factor of -1,0 or 1.
right ?
Correct.
--
"We put [the best] Assembler programmers in a little glass case in the hallway
near the Exit sign. The sign on the case says, `In case of optimization
problem, break glass.' Meanwhile, the problem solvers are busy doing their
work in languages most appropriate to the job at hand." --Richard Riehle This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics | |
by: David |
last post by:
this phrase has been mentioned many times in this NG and it seems like
everyone know what it's. is it a book? a standard? or a guide of some
sort? where can i read more about K&R2? thanks!
|
by: Chris Readle |
last post by:
Ok, I've just recently finished a beginning C class and now I'm working
through K&R2 (alongside the C99 standard) to *really* learn C.
So anyway, I'm working on an exercise in chapter one which give me
strange behavior. Here is the code I've written:
/******************************************************************************
* K&R2 Exercise 1-9
* Write a program to copy its input to its output, replacing strings
of blanks
* with a...
|
by: Merrill & Michele |
last post by:
Section 2.3 of K&R enumerates the complete set of escape sequences.
Q1) Is it possible to ask the following question without getting into
implementation/platform talk?
Q2) What on earth is the difference between newline and carriage return?
MPJ
|
by: aegis |
last post by:
page 45 "consider the function getbits(x,p,n) that returns
the (right adjusted) n-bit field of x that begins at
position p. We assume that bit position 0 is at the right
end and that n and p are sensible positive values.
For example, getbits(x,4,3) returns the three bits in
positions 4, 3 and 2, right-adjusted."
1. What does he mean by right adjusting the value
and in what way is it right adjusted?
|
by: Deniz Bahar |
last post by:
Hi,
My english is not top notch and I am trying to understand what K&R2 Ex
5-11 is asking for (pg 118).
It says: Modify the programs entab and detab (which I completed from
chapter 1 and have on hand) to accept a list of tab stops as arguments.
Use the default tab settings if there are no arguments.
I am having difficulty understanding the question (not asking for
answer to it). Any help would be helpful (thus the common root "help").
| | |
by: Sunny |
last post by:
Hi,
Well this might look like a dumb question to 99.99% of u but what
exactly is K&R2 and where can I get it?
Secondly alot of people say that you can learn by reading good books on
C. I know the one by Dennis Ritchie is good but can any one mention
some other books as well
Thanx.
|
by: arnuld |
last post by:
i am learning C and doing the exercise 1-1 of K&R2, where K&R ask to
remove some parts of programme and experiment with error, so here i
go:
#include <stdio.h>
int main () {
printf('hello world\n');
}
|
by: Anthony Irwin |
last post by:
Hi all,
I have been going through the k&r2 book and all the examples are done
with main() instead of int main(void) and k&r2 in the start of chapter
1 does not return 0 so I haven't yet either.
I did two compiles shown below.
$ gcc -std=c89 -Wall exercise_1-9.c -o exercise_1-9
exercise_1-9.c:5: warning: return type defaults to `int'
|
by: santosh |
last post by:
Hello all,
In K&R2 one exercise asks the reader to compute and print the limits for
the basic integer types. This is trivial for unsigned types. But is it
possible for signed types without invoking undefined behaviour
triggered by overflow? Remember that the constants in limits.h cannot
be used.
|
by: arnuld |
last post by:
STATEMENT: Write the function strindex(s, t), which returns the position of the
rightmost occurence of t in s, or -1 if there is none.
PURPOSE: this program prints the index of the rightmost match on the line.
The match we have to find is a char array named pattern. We also print out
the number of matches we have found. We will take the input from
command-line.
PROBLEM: Segmentation Fault
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
| | |
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own....
Now, this would greatly impact the work of software developers. The idea...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
| | |
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated we have to send another system
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| | |
