Data structure and algorithms

[azrael]

Hy, i am a student and in 2 days I am writing a test in data
structures and algorithms. I've done my homework and understood all
the implementations and structures. My profesor was so kind to allow
us to use any programing language we want, and I'd like to use
pythhon. At the first look it looked great, but we are not allowed to
use the built in functions like append(), so i have to write my own.
I tried it like this:

class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next

def __str__(self):
return str(self.cargo)


then

>>node1 = Node(1)
>>node2 = Node(2)
>>node3 = Node(3)

>>node1.next = node2
>>node2.next = node3

but this was not dinamicly enough for me (or my prof.) so i did the
following:

>>list=[]
>>list.append(N ode(1))
>>list.append(N ode(2))
>>list[0].next=list[1]
>>list.append(N ode(3))
>>list[1].next=list[2]

but deleting the list[1] willl automaticly make the list[2] become
list[1] and list[0] will "point" new to list[1]= 3
For my prof i should be doing something like deleting movig the
pointer from pointing to list[1] to list[2]. If I would do this in C
then the old list[1] would be lost, but not in python. If i just
redirect the "pointer" then the old value is still there.

I think that my concept is wrong by using a list to create a list. Is
it possible to manage the insertation of new object like in C by
allocating new memory space.


any sugestions how to make the implementation more like in C. I never
managed the syntax of C so I stoped when structs crossed my way.
Please help. I dont want to learn C. And especialy not in 2 days.

[azrael]

Re: Data structure and algorithms

I'm not a kid who heard that Python is simple, so he wants to use it
and throw it away. I discovered it about 2 months ago, and I learnt it
better then c in 2 years.

I want to use python for this test because i love it. I am amazed
about what i can do i such little time. My god, I even printed the
python logo on my laptop. Please guys help me. I don't want to go back
to C to pass the test

[Jonathan Curran]

Re: Data structure and algorithms

What are you trying to make in the first place? A singly linked list? If so
google is littered with examples of linked lists done in python. A simple
search for 'python linked list' brings up many results.

Btw, for future reference, no need for apologetics (the second post).

- Jonathan

[azrael]

Re: Data structure and algorithms

i'd like to get more control like in c with pointers. I want to loose
the data after disabling:

>>list=[]
>>list.append(N ode(1))
>>list.append(N ode(2))
>>list[0].next=list[1]

1, 2

>>list.append(N ode(3))
>>list[1].next=list[2]

1,2,3

>>list[0].next=list[2]

1,3 (but 2 still exists as list[2])



as much simmilar as this:


#include<stdio. h>
#include<stdlib .h>
typedef int element;
struct Lis
{
int values[10000];
int cursor;
};
typedef struct Lis list;

int FirstL(list *Li){
return(0);
}

int EndL(list *Li){
return((*Li).cu rsor);
}

element NextL(element p, list *Li){
if ((p>=(*Li).curs or) || (p<0))
{
printf("Element ne postoji u listi ! \n");
exit(0);
}
else
return(p+1);
}

element PreviousL(eleme nt p, list *Li){
if ((p>(*Li).curso r) || (p<=0))
{
printf("Element ne postoji u listi ! \n");
exit(0);
}
else
return(p-1);
}


element LocateL(int x, list *Li){
int i;
i=0;
while ((i!= (*Li).cursor) && ((*Li).values[i]!=x))
i++;
return(i);
}

void InsertL(int x, element p, list *Li){
int i;
if ((p<=(*Li).curs or) && (p>=0) && ((*Li).cursor<1 0000))
{
for (i=(*Li).cursor ; i>=p; i--)
(*Li).values[i]=(*Li).values[i-1];
(*Li).cursor++;
(*Li).values[p]=x;
}
else
{
if((*Li).cursor >=10000)
printf("Lista je puna");
else
printf("Element ne postoji u listi ! \n");
exit(0);
}
}

void DeleteL(element p, list *Li){
int i;
if ((p<(*Li).curso r) && (p>=0))
{
for (i=p; i<(*Li).cursor ; i++)
(*Li).values[i]=(*Li).values[i+1];
(*Li).cursor--;
}
else
{
printf("Element ne postoji u listi ! \n");
exit(0);
}
}


int RetrieveL(eleme nt p, list *Li){
if ((p<(*Li).curso r) && (p>=0))
return((*Li).va lues[p]);
else
{
printf("Element ne postoji u listi ! \n");
exit(0);
}
}



void DeleteAllL(list *Li){
(*Li).cursor=0;
}


void InitL(list *Li){
(*Li).cursor=0;
}

[Terry Reedy]

Re: Data structure and algorithms


"azrael" <jura.grozni@gm ail.comwrote in message
news:1170024965 .321036.206010@ m58g2000cwm.goo glegroups.com.. .
| Hy, i am a student and in 2 days I am writing a test in data
| structures and algorithms. I've done my homework and understood all
| the implementations and structures. My profesor was so kind to allow
| us to use any programing language we want, and I'd like to use
| pythhon. At the first look it looked great, but we are not allowed to
| use the built in functions like append(), so i have to write my own.
| I tried it like this:
|
| class Node:
| def __init__(self, cargo=None, next=None):
| self.cargo = cargo
| self.next = next
|
| def __str__(self):
| return str(self.cargo)
|
|
| then
|
| >>node1 = Node(1)
| >>node2 = Node(2)
| >>node3 = Node(3)
|
| >>node1.next = node2
| >>node2.next = node3

This is the standard idiom in Python for linked lists and other linked
structures and perhaps what you should be doing.

|
| but this was not dinamicly enough for me (or my prof.) so

dynamic? I have no idea what you mean by 'not dynamic enough'.

Python is not C or C++. It does not have pointers. Trying to program in C
in Python does not work too well.

Terry Jan Reedy

[Diez B. Roggisch]

Re: Data structure and algorithms

azrael schrieb:

i'd like to get more control like in c with pointers. I want to loose
the data after disabling:
>

>>>list=[]
>>>list.append( Node(1))
>>>list.append( Node(2))
>>>list[0].next=list[1]

>
>
1, 2
>
>

>>>list.append( Node(3))
>>>list[1].next=list[2]

>
>
1,2,3
>
>

>>>list[0].next=list[2]

>
1,3 (but 2 still exists as list[2])

So what? Then do

del list[2]


This is what happens in C also - if you store references to structures,
they don't magically go away just because you refer to them from other
places.


Diez

[Steve Holden]

Re: Data structure and algorithms

Terry Reedy wrote:

"azrael" <jura.grozni@gm ail.comwrote in message

[...]

|
| but this was not dinamicly enough for me (or my prof.) so
>
dynamic? I have no idea what you mean by 'not dynamic enough'.
>
Python is not C or C++. It does not have pointers. Trying to program in C
in Python does not work too well.
>

Mostly because Python variables are precisely pointers to object values
allocated from a heap.

regards
Steve
--
Steve Holden +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
Blog of Note: http://holdenweb.blogspot.com
See you at PyCon? http://us.pycon.org/TX2007

[Beej]

Re: Data structure and algorithms

On Jan 28, 2:56 pm, "azrael" <jura.gro...@gm ail.comwrote:

class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next

This is OK for the node itself, but maybe you should try writing a
LinkedList class that you use:

class LinkedList(obje ct):
def __init__(self):
self.head = None

def append(self, node):
...

def remove(self, node):
...

>>ll = LinkedList()
>>ll.append(Nod e(3490))

(For extra fun, make it so you can iterate over the linked list and
call it like this: for n in ll: print n :-) )

>list=[]
>list.append(No de(1))
>list.append(No de(2))
>list[0].next=list[1]
>list.append(No de(3))
>list[1].next=list[2]

I'd classify this as "not pretty". Sure, it's more "dynamic" in that
you don't have a variable to reference every node, but it's way
cleaner to make an encapsulating LinkedList class, right?

In in Python, references to objects are very much like pointers in C:

>>foo = Node(3490) # foo is a reference to a Node instance
>>bar = foo # bar points to the same Node instance as foo
>>foo

<__main__.Nod e object at 0xb7b362ec>

>>bar

<__main__.Nod e object at 0xb7b362ec>

See? They point to the name Node object.

I think that my concept is wrong by using a list to create a list.

I agree with you, if your goal is to implement your own list. Using
the Python functionality just makes things less clear.

Is
it possible to manage the insertation of new object like in C by
allocating new memory space.

Absolutely. The "next" pointer thing is the way to go, so you're on
the right track with that.

When deleting nodes from the list, you don't explicitly delete them;
you just need to remove all your references to them. Nodes will be
garbage collected when there are no more references to them anywhere.

any sugestions how to make the implementation more like in C. I never
managed the syntax of C so I stoped when structs crossed my way.
Please help. I dont want to learn C.

Ah, it's a pity. C is my favorite compiled procedural language.

-Beej

[azrael]

Re: Data structure and algorithms

thanks guys. i see that there is no way then to go back to C to
satisfy my prof and get a grade

[Beej]

Re: Data structure and algorithms

On Jan 29, 1:50 pm, "azrael" <jura.gro...@gm ail.comwrote:

thanks guys. i see that there is no way then to go back to C to
satisfy my prof and get a grade

Seconding what Dennis says below, it is totally possible to use Python
for this.

I didn't mean to discourage you from using Python--I just wanted to
discourage you from trying to do it using the Python built-in list [].

In fact, given the time constraints and your dislike of structs,
you're likely going to rip your hair out trying to get it going in C.

-Beej

[Beej]

Re: Data structure and algorithms

On Jan 29, 10:15 pm, Dennis Lee Bieber <wlfr...@ix.net com.comwrote:

The instructor learned his lesson: no more assignments
done in "any language I <instructorca n understand"

Without naming names, there was a person at my university who gained a
certain amount of notoriety by implementing a file system for OS class
in Bourne Shell.

That prof also changed the rule the very next semester. :-)

-Beej