A C Adventure: your comments are welcome

S

spinoza1111

FIT THE FIRST: WE DEVELOP STRINGS AS A STRUCT

OK, this is spinoza1111. In this thread I shall re-learn C, being
still crazy after all these years.

To do ANYTHING with C, I need a string handler. No, I don't want
yours, Richard Heathfield. The point is this is a good way of (1)
relearning C and (2) demonstrating that C sucks.

I will take this step by step in order to give everyone a chance to
comment. Comments are welcome from all especially Navia, Heathfield,
Bacarisse and Malcolm M.

For now, I will use the Navia compiler, but shall restrict myself to
as vanilla a subset of C as is possible. I shall only use #includes I
absolutely need. I shall incorporate changes suggested by others, of
course!

OK, so here's how I represent strings:

struct TYPstring
{
long intSegmentLength;
char * strSegment;
void * usrLeftSegment;
void * usrRightSegment;
};

That is (das ist) a string is a binary tree of segments, giving it
unlimited length and avoiding Stupid Sentinels. Each segment is at
most 2^31 - 1 wide characters long, but there is no apriori bound to
the tree: therefore the above structure represents strings.

Two problems:

1. It seems I cannot include what I want to be a self-referential
struct inside a struct either as the thing itself or as a pointer
because either C or the Navia compiler is basically one-pass. I can't
do this in C Sharp either but can if I change the struct to a class.
So, void pointers raise their pretty little heads.

But: note that there's no point in a"void"ing void pointers in C
because C makes it easy to change pointer type. If there is no modern
try..catch in C then the only way of detecting whether you have a
pointer to a valid data type is to examine memory at the place where
the pointer points.

2. With minimal assumptions (that is, minimal #includes) I default to
char and not wchar.

Of course, I might be "erring" in using the Navia compiler. But my
actual situation reflects that of the real C programmer who is
confronted with mutually incompatible compilers. This is because C was
misdesigned, misbegotten, dead on arrival,

"...curtail'd of this fair proportion,
Cheated of feature by dissembling nature,
Deformed, unfinish'd, sent before my time
Into this breathing world, scarce half made up," (Shakespeare, Richard
III)

and never standardized until way too late.

Let the fun begin...
 
B

bartc

spinoza1111 said:
FIT THE FIRST: WE DEVELOP STRINGS AS A STRUCT

OK, this is spinoza1111. In this thread I shall re-learn C, being
still crazy after all these years.

To do ANYTHING with C, I need a string handler. No, I don't want
yours, Richard Heathfield. The point is this is a good way of (1)
relearning C and (2) demonstrating that C sucks.
For now, I will use the Navia compiler, but shall restrict myself to
as vanilla a subset of C as is possible. I shall only use #includes I
absolutely need. I shall incorporate changes suggested by others, of
course!

OK, so here's how I represent strings:

struct TYPstring
{
long intSegmentLength;
char * strSegment;
void * usrLeftSegment;
void * usrRightSegment;
}

If you want string handling to become a total nightmare, then that is a good
start.
 
F

Flash Gordon

spinoza1111 wrote:

OK, so here's how I represent strings:

struct TYPstring
{
long intSegmentLength;
char * strSegment;
void * usrLeftSegment;
void * usrRightSegment;
};

That is (das ist) a string is a binary tree of segments, giving it
unlimited length and avoiding Stupid Sentinels. Each segment is at
most 2^31 - 1 wide characters long, but there is no apriori bound to
the tree: therefore the above structure represents strings.

Two problems:

1. It seems I cannot include what I want to be a self-referential
struct inside a struct either as the thing itself or as a pointer
because either C or the Navia compiler is basically one-pass. I can't
do this in C Sharp either but can if I change the struct to a class.
So, void pointers raise their pretty little heads.

But: note that there's no point in a"void"ing void pointers in C
because C makes it easy to change pointer type. If there is no modern
try..catch in C then the only way of detecting whether you have a
pointer to a valid data type is to examine memory at the place where
the pointer points.

Look up any text on how to implement linked lists and don't use pointers
to void. Then you have compile time checking.
2. With minimal assumptions (that is, minimal #includes) I default to
char and not wchar.

<snip>

If you want to use wchar_t then the hearder declaring it is one of the
headers in the minimal set you need. So what you are say is...

I will use all headers I need, but no others
X is defined in a header which I am not using

So you are breaking your own rules and blaming C for the fact you are
not following your rules.


So of your two problems, one was not knowing the normal method of doing
a linked list and blaming the language for your ignorance, and the other
is you not following your rules or doing what the language says you do
in order to have what you want. So both problems are you.
 
S

spinoza1111

If you want string handling to become a total nightmare, then that is a good
start.

I'd remark that you're a coward. You smirk that this is a nightmare,
but you're afraid of being shot down in turn, and so, like a Serbian
sniper killing women and children from hiding, you make smart remarks.

The struct does need one extra element, the startindex of the segment
in the string. This is redundant but it provides a rationale for an
error check in the stringInspector() function to come.

struct TYPstring
{
int intSegmentLength;
char * strSegment;
int intSegmentStartIndex;
void * usrLeftSegment;
void * usrRightSegment;
};

This way, we need not search half the string tree preorder to find a
specific indexed location.
 
B

bartc

spinoza1111 said:
I'd remark that you're a coward. You smirk that this is a nightmare,
but you're afraid of being shot down in turn, and so, like a Serbian
sniper killing women and children from hiding, you make smart remarks.

The struct does need one extra element, the startindex of the segment
in the string. This is redundant but it provides a rationale for an
error check in the stringInspector() function to come.

struct TYPstring
{
int intSegmentLength;
char * strSegment;
int intSegmentStartIndex;
void * usrLeftSegment;
void * usrRightSegment;
};

This way, we need not search half the string tree preorder to find a
specific indexed location.

I don't know what sort of super-complicated strings you're trying to
implement. How would your string type deal with something straightforward
like:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
char
*daynames[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};
printf("Random day: %s\n",daynames[rand()%7]);
}

?
 
B

Ben Bacarisse

spinoza1111 said:
FIT THE FIRST: WE DEVELOP STRINGS AS A STRUCT

OK, this is spinoza1111. In this thread I shall re-learn C, being
still crazy after all these years.

To do ANYTHING with C, I need a string handler. No, I don't want
yours, Richard Heathfield. The point is this is a good way of (1)
relearning C and (2) demonstrating that C sucks.

I would not set this as a beginner's exercise. If your primary gaol
is learning, I would suggest you start with something simpler.

OK, so here's how I represent strings:

struct TYPstring
{
long intSegmentLength;
char * strSegment;
void * usrLeftSegment;
void * usrRightSegment;
};

I'd make the length unsigned. If you must encode the type in the
name, then I would want to distinguish between 'int' and 'long'.

I'd suggest having another think about the names, too. long names are
good, but structs essentially introduce a name space so they don't
have to be globally unique. If the whole thing is a segment of a
string, I am not sude it helps to have all the parts include the term
"Segment" -- use the name to say what distinguished the members. They
are unified by being in a struct. (I accept that this is a matter of
taste.)

All yours refer to "Segment" but the whole
struct is called a "TYPstring" you suggest (below) that you really
want a tree, so if I choose to keep this kind of naming I would want
to unify these two names; say by calling the struct StringSegment,
maybe.

1. It seems I cannot include what I want to be a self-referential
struct inside a struct either as the thing itself or as a pointer
because either C or the Navia compiler is basically one-pass. I can't
do this in C Sharp either but can if I change the struct to a class.
So, void pointers raise their pretty little heads.

No need:

struct TYPstring
{
long intSegmentLength;
char *strSegment;
struct TYPstring *usrLeftSegment;
struct TYPstring *usrRightSegment;
};

2. With minimal assumptions (that is, minimal #includes) I default to
char and not wchar.

What is wrong with an include? Anyway, C has both wchar-based strings
and multi-byte strings so you don't have to use wchar (as this stage)
to have full international character support.

I, too, think that this is an overly complex way to do strings. There
is a lot of existing work on strings and string representations and
you seem to be ditching it all without consideration.

<snip>
 
J

Julienne Walker

I, too, think that this is an overly complex way to do strings.  There
is a lot of existing work on strings and string representations and
you seem to be ditching it all without consideration.

On the contrary, I think spinoza is working toward an implementation
of ropes, which are indeed an overly complex way to do strings
compared to tradition. But assuming he *is* creating a rope library,
he's not ditching existing work without consideration, but taking
advantage of existing work to meet his personal needs.

I'm still not sure how the ability to write a library in C that does
everything you set out to do is a failing of C, but I have no doubt
he'll try to demonstrate that C sucks eventually. Personally, I think
he's doing a good job of demonstrating that if you don't like how C
handles strings, you can write your own string library that better
suits your needs. A fine example of language flexibility. ;-)
 
J

Julienne Walker

I, too, think that this is an overly complex way to do strings.  There
is a lot of existing work on strings and string representations and
you seem to be ditching it all without consideration.

On the contrary, I think spinoza is working toward an implementation
of ropes, which are indeed an overly complex way to do strings
compared to tradition. But assuming he *is* creating a rope library,
he's not ditching existing work without consideration, but taking
advantage of existing work to meet his personal needs.

I'm still not sure how the ability to write a library in C that does
everything you set out to do is a failing of C, but I have no doubt
he'll try to demonstrate that C sucks eventually. Personally, I think
he's doing a good job of demonstrating that if you don't like how C
handles strings, you can write your own string library that better
suits your needs. A fine example of language flexibility. ;-)
 
S

spinoza1111

I would not set this as a beginner's exercise.  If your primary gaol
is learning, I would suggest you start with something simpler.

I'm not a beginner, Ben.

I am relearning C but yet I know far more than thee. My claim is that
C does not in itself constitute much in the way of knowledge, and part
of C contains knowledge signed negative,
that in Buddha's words "tends not to profit" and lowers the wisdom of
the negative knowledge knower.

I feel stoopider already.

You are my student as much as I am yours, so don't get too bug for
your britches, you young whippersnapper.
I'd make the length unsigned.  If you must encode the type in the
name, then I would want to distinguish between 'int' and 'long'.

Excellent suggestions.
I'd suggest having another think about the names, too.  long names are
good, but structs essentially introduce a name space so they don't
have to be globally unique.  If the whole thing is a segment of a
string, I am not sude it helps to have all the parts include the term
"Segment" -- use the name to say what distinguished the members.  They
are unified by being in a struct.  (I accept that this is a matter of
taste.)

Got it. But disagree. Any part of the tree is represented by any node
because I have added the starting index of the segment, ergo the
struct is not a segment: it is a view of the entire tree since from
any struct node one can navigate to the entire tree.
All yours refer to "Segment" but the whole
struct is called a "TYPstring"  you suggest (below) that you really
want a tree, so if I choose to keep this kind of naming I would want
to unify these two names; say by calling the struct StringSegment,
maybe.

Disagree. See above.
No need:

  struct TYPstring
  {
      long intSegmentLength;
      char *strSegment;
      struct TYPstring *usrLeftSegment;
      struct TYPstring *usrRightSegment;
  };

<snip>

Hmm, why didn't this work. I will try it again: but note that there's
no point in avoiding void pointers in C, since anything, no matter how
hard typed in the source code, can be aliased.
What is wrong with an include?  Anyway, C has both wchar-based strings
and multi-byte strings so you don't have to use wchar (as this stage)
to have full international character support.

I, too, think that this is an overly complex way to do strings.  There
is a lot of existing work on strings and string representations and
you seem to be ditching it all without consideration.

Yup, primarily to relearn and criticise C: to show its defects. C
should NOT be credited with the hard work of people who workarounded
its numerous flaws.
 
B

Ben Bacarisse

Julienne Walker said:
On the contrary, I think spinoza is working toward an implementation
of ropes, which are indeed an overly complex way to do strings
compared to tradition. But assuming he *is* creating a rope library,
he's not ditching existing work without consideration, but taking
advantage of existing work to meet his personal needs.

Agreed. You are more generous than I am. I will try to assume the
best in future. Had that been the intent I would have expected some
reference this body of work, but that alone is no reason to assume the
reference is not implied.
I'm still not sure how the ability to write a library in C that does
everything you set out to do is a failing of C, but I have no doubt
he'll try to demonstrate that C sucks eventually. Personally, I think
he's doing a good job of demonstrating that if you don't like how C
handles strings, you can write your own string library that better
suits your needs. A fine example of language flexibility. ;-)

The trouble with ropes is that the don't easily map to native C
strings so you have trouble with external libraries and, for that
matter, other C functions like fopen. These problems are not
insurmountable, but I'd want a compelling reason to move so far from
the native representation. I have unsubstantiated doubts that ropes
are good choice for a generic string library in C.
 
B

Ben Bacarisse

spinoza1111 said:
I'm not a beginner, Ben.

We are all beginners at something. I, for example, am a beginner in
C#. You appear to be a beginner at C. This is no disrespect.
I am relearning C but yet I know far more than thee.

I would still suggest you start with simpler exercises, particularly
if you plan to use C's multi-byte string handling. This is just
advice that I would follow myself -- I would start with simple C#
exercises.

Got it. But disagree. Any part of the tree is represented by any node
because I have added the starting index of the segment, ergo the
struct is not a segment: it is a view of the entire tree since from
any struct node one can navigate to the entire tree.

This not usually true of trees. Do you plan to add further pointer
to permit this?

I'll leave that matter of naming since style arguments usually
unproductive.
Disagree. See above.

Hmm, why didn't this work.

I have snipped and compiler to check for typos and what I wrote
compiles. lcc-win32 has some bugs but I doubt this is one of them.
I will try it again: but note that there's
no point in avoiding void pointers in C, since anything, no matter how
hard typed in the source code, can be aliased.

That is a very odd argument. I would use as much type checking as
possible for as long as possible and resort to void * only when it was
needed.
Yup, primarily to relearn and criticise C: to show its defects. C
should NOT be credited with the hard work of people who workarounded
its numerous flaws.

I am not suggesting doing anything other than a quick review of what
other people have done in this area so as to learn from their
experiences. You don't have to credit C with anything.

You don't comment on the wchar/mulibyte-string issue. I hope you
won't bring up lack of Unicode support later if you ignore advice to
consider it at the very start. (I accept that the lack of comment may
simply indicate that you are considering the matter).

<snip>
 
B

Ben Bacarisse

Ben Bacarisse said:
This not usually true of trees. Do you plan to add further pointer
to permit this?

I'll leave that matter of naming since style arguments usually
unproductive.

Goodness me. Please add "is" before "not", change "pointer" to
"pointers" and add "are" before "usually". I am sure everyone can
work it out, but sometimes my typo density is so I high I have to say
something.

<snip>
 
S

spinoza1111

We are all beginners at something. I, for example, am a beginner in
C#. You appear to be a beginner at C. This is no disrespect.

I understand. But I'm remedial reading. I'm in rehab. I'm a retread.
Not a beginner. Furthermore, I believe I can illuminate C in the sense
of showing why it sucks. Part of the problem is that the
paraprofession has no way of recognizing insight untethered to some
programming language. IMO, it would be better to test programmers on
general culture, philosophical logic, and literacy than on the
mistakes of a programming language...even Java.
I would still suggest you start with simpler exercises, particularly
if you plan to use C's multi-byte string handling. This is just
advice that I would follow myself -- I would start with simple C#
exercises.




This not usually true of trees. Do you plan to add further pointer
to permit this?

I realized after I posted that this requires a parent pointer. So I
added one.
I'll leave that matter of naming since style arguments usually
unproductive.

Do.



I have snipped and compiler to check for typos and what I wrote
compiles. lcc-win32 has some bugs but I doubt this is one of them.

I forgot that the structure's type has to be expressed as the keyword
"struct" followed by its name. This ugly little bit of non-
orthogonality, along with the fact that a for without an increment
still needs the semicolon, although the semicolon is not needed after
increment, has been cleaned up in C Sharp.
That is a very odd argument. I would use as much type checking as
possible for as long as possible and resort to void * only when it was
needed.

Well, as another poster pointed out perspicuously, avoiding the void
catches more errors at compile time.
I am not suggesting doing anything other than a quick review of what
other people have done in this area so as to learn from their
experiences. You don't have to credit C with anything.

I generally don't like to read other people's code since once I'm up
to speed in a programming language (a process, by the way, that takes
good programmers hours and not days), their style generally offends
me. I was an adopter of "literate programming" before Knuth and even
before Brian Kernighan's "The Elements of Programming Style", using
systematic naming conventions and extensive line and blocked comments
in IBM 1401 SPS, even though this language only provided 15 character
line comments and six character names. I also modified the assembler
(in machine language) to skip line comments.

Therefore, I am offended by short identifiers and half-literate
comments. At the same time, this code shall be free of comments for
now since we know what it does, or fails to do.
You don't comment on the wchar/mulibyte-string issue. I hope you
won't bring up lack of Unicode support later if you ignore advice to
consider it at the very start. (I accept that the lack of comment may
simply indicate that you are considering the matter).

Let's see later how easy it is to modify the solution!

At the end of this is the untested solution, that compiles with no
errors or warnings using Mr. Navia's compiler. I will test it as you
look at it and test it yourself.

It creates an "unbalanced" tree that instead of containing the string,
maps the string in situ. This "lightweight" string may be a virtue in
avoiding copies, although problems occur when the string is modified.

The string is "unbalanced" (the top Parent points to a leftnode with
no children, and a rightnode that will probably have children: in
general and for any node, the leftnode is childless but the right node
points to the right side of the string.

This is an artifact of the left to right way in which the tree is
created, with a recursion step every time we go to the right. It means
that in using the tree, we must travel further down the tree to get to
the right most characters, but this might be a Good Thing, since the
most interesting part of most strings is at the beginning.

Then, as the string is modified, it will have different overall
shapes, or, a simple algorithm can balance it.

The questionmark colon statement from hell is the most important
statement. These Godzilla statements to me are elegant but can be hard
to debug.


#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <stddef.h>

#define SEGMENT_MAX_LENGTH 32
#define TEST_STRING_LENGTH = 2000

struct TYPstringNode
{
char * ptrNodeCharacters;
unsigned int uintStartIndex;
unsigned int uintLength;
struct TYPstringNode * ptrParent;
struct TYPstringNode * ptrLeft;
struct TYPstringNode * ptrRight;
};

struct TYPstringNode * mkStringNode
(char * ptrNodeCharacters,
unsigned int uintStartIndex,
unsigned int uintLength,
struct TYPstringNode * ptrParent,
struct TYPstringNode * ptrLeft,
struct TYPstringNode * ptrRight)
{
struct TYPstringNode * ptrNewNode;
if ((ptrNewNode =
(struct TYPstringNode *)
(malloc(sizeof(struct TYPstringNode))))
==
NULL)
{
abort();
}
(*ptrNewNode).ptrNodeCharacters = ptrNodeCharacters;
(*ptrNewNode).uintStartIndex = uintStartIndex;
(*ptrNewNode).uintLength = uintLength;
(*ptrNewNode).ptrParent = ptrParent;
(*ptrNewNode).ptrLeft = ptrLeft;
(*ptrNewNode).ptrRight = ptrRight;
return ptrNewNode;
}

struct TYPstringNode * mkString
(struct TYPstringNode * ptrParent,
char * ptrSourceChars,
unsigned int uintStartIndex,
unsigned int uintLength)
{
unsigned int uintOffset;
struct TYPstringNode * ptrLeft = NULL;
struct TYPstringNode * ptrRight = NULL;
unsigned int uintSegments;
unsigned int uintDoubleSegmentLength;
if (uintLength <= SEGMENT_MAX_LENGTH)
uintSegments = 1;
else
{
if (uintLength
<=
(uintDoubleSegmentLength = SEGMENT_MAX_LENGTH << 1))
uintSegments = 2;
else
uintSegments = 3;
}
struct TYPstringNode * ptrStringNode =
(uintSegments > 1
?
ptrSourceChars + SEGMENT_MAX_LENGTH
:
ptrSourceChars,
uintStartIndex
+
(uintSegments > 1 ? SEGMENT_MAX_LENGTH : 0), //
80
uintSegments > 1
?
min(uintLength - SEGMENT_MAX_LENGTH, uintLength)
:
uintLength,
ptrParent,
uintSegments > 1
?
(ptrLeft = mkStringNode
(ptrSourceChars,
uintStartIndex,
SEGMENT_MAX_LENGTH,
NULL, NULL, NULL))
:
NULL,
uintSegments > 2
?
(ptrRight = mkString
(NULL,
ptrSourceChars
+
uintDoubleSegmentLength,
uintStartIndex
+
uintDoubleSegmentLength,
uintLength
-
uintDoubleSegmentLength))
:
NULL);
if (ptrStringNode != NULL)
{
if (ptrLeft != NULL)
(*((*ptrStringNode).ptrLeft)).ptrParent = ptrStringNode;
if (ptrRight != NULL)
(*((*ptrStringNode).ptrRight)).ptrParent = ptrStringNode;
(*ptrStringNode).ptrLeft = ptrLeft;
(*ptrStringNode).ptrRight = ptrRight;
}
return ptrStringNode;
}

int main()
{
printf("Unlimited strings in basic C");
// ***** Insert test code *****
return 0;
}
 
S

spinoza1111

Goodness me.  Please add "is" before "not", change "pointer" to
"pointers" and add "are" before "usually".  I am sure everyone can
work it out, but sometimes my typo density is so I high I have to say
something.

<snip>

I have added a Parent pointer
 
S

spinoza1111

Agreed.  You are more generous than I am.  I will try to assume the
best in future.  Had that been the intent I would have expected some
reference this body of work, but that alone is no reason to assume the
reference is not implied.


The trouble with ropes is that the don't easily map to native C
strings so you have trouble with external libraries and, for that
matter, other C functions like fopen.  These problems are not
insurmountable, but I'd want a compelling reason to move so far from
the native representation.  I have unsubstantiated doubts that ropes
are good choice for a generic string library in C.

So...this is "Rope a Dope?"

I think it's gonna be key that the Rope does NOT include the
characters of the string, but merely maps it. Then, when the string is
modified using the Rope, the Rope will only contain the modifications.

There will be three types of Ropes: virtual ropes, modified ropes
(hawsers), and ropes that contain all the characters, such that it has
malloc'd the space for all characters (cables).
 
S

spinoza1111

spinoza1111said:



The usual reason is forgetting the asterisks. The compiler demurs when
asked to incorporate an instance of a struct into itself, but it's
fine with pointers.


Remember the asterisks.

I remembered the asterisks, dear boy. What I forgot is the ugly fact
that structs, unlike built-in data types, must be preceded when
declared by the struct keyword. I remember beautiful and orthogonal
facts but choose to forget design mistakes.
 
S

spinoza1111

spinoza1111wrote:

<snip>











Look up any text on how to implement linked lists and don't use pointers
to void. Then you have compile time checking.

OK, Flash.
<snip>

If you want to use wchar_t then the hearder declaring it is one of the
headers in the minimal set you need. So what you are say is...

    I will use all headers I need, but no others
    X is defined in a header which I am not using

So you are breaking your own rules and blaming C for the fact you are
not following your rules.

So of your two problems, one was not knowing the normal method of doing
a linked list and blaming the language for your ignorance, and the other

Gee, I thinks I know how to do a linked list (it was a question in my
1987 Microsoft interview: I didn't get the job but I knew the answer).
You see, Flash, I'm not trying to represent a string as a linked list.
I am trying to represent it as a tree. Isn't that a kiss my ass?
is you not following your rules or doing what the language says you do
in order to have what you want. So both problems are you.

Oh, the problem is you
Whoop te doo
It is never Authority
Nor the Idear, my dear:
I'm afraid of de boss
So I want none of your sauce
Ideas are bettern than people
So says the sheeple.
 
S

spinoza1111

spinoza1111wrote:
I'd remark that you're a coward. You smirk that this is a nightmare,
but you're afraid of being shot down in turn, and so, like a Serbian
sniper killing women and children from hiding, you make smart remarks.
The struct does need one extra element, the startindex of the segment
in the string. This is redundant but it provides a rationale for an
error check in the stringInspector() function to come.
struct TYPstring
{
    int intSegmentLength;
    char * strSegment;
    int intSegmentStartIndex;
    void * usrLeftSegment;
    void * usrRightSegment;
};
This way, we need not search half the string tree preorder to find a
specific indexed location.

I don't know what sort of super-complicated strings you're trying to
implement. How would your string type deal with something straightforward
like:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
 char
*daynames[7]={"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","­Saturday"};
 printf("Random day: %s\n",daynames[rand()%7]);

}

Gee, I'm not worthy. I'm scum. Didjoo write that?

So exactly what is it you propose? That all strings be handled by
arrays of 7 character strings?

Of course, for the above, I'd use an array of seven pointers to the
string struct.
 
F

Flash Gordon

spinoza1111 said:
Gee, I thinks I know how to do a linked list (it was a question in my
1987 Microsoft interview: I didn't get the job but I knew the answer).
You see, Flash, I'm not trying to represent a string as a linked list.
I am trying to represent it as a tree. Isn't that a kiss my ass?

<snip>

The coding problems are the same and linked list texts are the ones
which deal with them normally, since people normally do linked lists
first then trees.
 
S

spinoza1111

spinoza1111wrote:


<snip>

The coding problems are the same and linked list texts are the ones
which deal with them normally, since people normally do linked lists
first then trees.

OK, Flash, trees use links. But they are not "linked lists". Singly
linked lists contain the address of the next node at each node, with
the address of the first node (in a circular linked list) in the last
node, or null. Doubly linked lists contain the address of the
predecessor node in each node and are usually circular. Trees contain
n>1 links to successor (child) nodes, usually two, because an n way
tree can always be transformed into a binary tree.

Neither singly nor doubly linked lists can represent strings because
it would cost on average N/2 steps to get to a random character. Trees
are better since its, if memory serves, a logarithmic function when
the tree is balanced, and the tree can be "unbalanced" to speed up
common searches.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top