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

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

list=[]
list.append(Node(1))
list.append(Node(2))
list[0].next=list[1]
list.append(Node(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]

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]

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]

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])



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).cursor);
}

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

element PreviousL(element p, list *Li){
if ((p>(*Li).cursor) || (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!=x))
i++;
return(i);
}

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


int RetrieveL(element p, list *Li){
if ((p<(*Li).cursor) && (p>=0))
return((*Li).values[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]

| 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]

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]

|
| 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]

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(object):
def __init__(self):
self.head = None

def append(self, node):
...

def remove(self, node):
...

(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(Node(1))
list.append(Node(2))
list[0].next=list[1]
list.append(Node(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:
<__main__.Node 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]

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

 

[Dennis Lee Bieber]

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

I suspect you could have used Python very well -- by NOT using the
easy stuff Python does for you.

I recall you said you sort of gave up on C when it came to learning
"struct"s... Well, an assignment to implement a linked list pretty much
comes down to nothing but "struct"s. The closest equivalent to a C
struct is a class in Python (the difference between a struct and a class
in C++ is basically that struct defaults to publicly accessible members
and class to private members).

A class in "data structures and algorithms" is all about creating
structures for storing data, and how to manipulate those structures, at
the basic level. For a linked list, that tends to be one primary item --
the list header; and possible a secondary item -- the "current" node.

Back in the seventies I implemented the assignment for a "hashed
head, multiple-linked, list" using Xerox Sigma BASIC (which only
permitted four open files at a time -- and this assignment tended to use
them all <G>). The instructor learned his lesson: no more assignments
done in "any language I <instructor> can understand" {basically, he got
hit with BASIC, FORTRAN, COBOL, Pascal, and assembly -- SNOBOL and APL
were on the "don't understand" list} The language didn't matter -- I'd
have had to implement the same data structures and algorithms in any of
them.

--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Beej]

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]

The instructor learned his lesson: no more assignments
done in "any language I <instructor> can 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

 

[Dennis Lee Bieber]

Hy, i am a student and in 2 days I am writing a test in data

Presuming this is accurate, then "today" was the day in question, so
posting sample code will arrive after the event (and probably not be
read by the original poster who probably gave up on the language in a
bout of depression).

Not fully tested, but something scratched together during an hour or
two...

llist.py
-=-=-=-=-=-=-=-=-
"""
Implements a doubly-linked list class (and associated node class)
with priority ordering capability.

This class is NOT thread safe, nor is it fully protected against
external manipulation of nodes
"""

class Node(object):
"""
Basic component of the doubly-linked list:
defines attributes for next and previous links,
priority (only meaningful if ALL inserts are via
insertPriority()
and the user payload
"""
def __init__(self, data=None, priority=0):
self._priority = priority
self._next = self
self._previous = self
self.data = data

def insertAfter(self, aNode):
aNode._next = self._next #new node points to old next
aNode._previous = self #new node points back to current
self._next._previous = aNode #old next points back to new
self._next = aNode #current points to new
return aNode

def insertBefore(self, aNode):
return self.previous().insertAfter(aNode)

def next(self):
return self._next

def previous(self):
return self._previous

def unlink(self):
self._next._previous = self._previous
self._previous._next = self._next

class LList(Node):
"""
List header; essentially a Node with no payload
"""
def __init__(self):
super(LList, self).__init__()

def insertPriority(self, aNode):
"""
Performs a priority based insertion, in which the list
is maintained in descending order of priority, and inserts
are made to the end of segments of equal priority -- this
allows for round-robin processing with priorities
"""
currentNode = self._next #start with first node
while ((currentNode != self) #end-of-list
and (aNode._priority <= currentNode._priority)):
currentNode = currentNode._next
return currentNode.insertBefore(aNode)

def first(self):
return self._next

def last(self):
return self._previous



if __name__ == "__main__":
myList = LList()

myList.insertPriority(Node("Just some data", 5))
myList.insertPriority(Node("Just more data", 5))
myList.insertPriority(Node("Just high data", 10))
myList.insertPriority(Node("Just low data", 0))
myList.insertPriority(Node("Just negative data", -5))
myList.insertPriority(Node("Just normal data"))

node = myList.first()
while node != myList:
print id(node), node.data, node._priority
node = node.next()

node = myList.last()
node = node.previous()
node = node.previous()
node.unlink()
print "unlinked: ", id(node), node.data
node = myList.first()
while node != myList:
print id(node), node.data, node._priority
node = node.next()

-=-=-=-=-=-=-=-=-
E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>python llist.py
10296432 Just high data 10
10296624 Just some data 5
10296656 Just more data 5
10296752 Just low data 0
10296880 Just normal data 0
10296816 Just negative data -5
unlinked: 10296752 Just low data
10296432 Just high data 10
10296624 Just some data 5
10296656 Just more data 5
10296880 Just normal data 0
10296816 Just negative data -5

E:\UserData\Dennis Lee Bieber\My Documents\Python Progs>

Observe how traversing the list shows that the data IS in descending
priority order (as I only used .insertPriority() which acts on the list
header, and it uses .insertBefore() which in turn uses .insertAfter(),
thereby sort of testing all the insert methods <G>). Then, going to the
end of the list, backing up twice, and unlinking that node... A second
traverse of the list shows that the unlinked node is no longer in the
list.
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/