Computer Science Canada

Help with linked lists
Author:  paulm [ Sun May 03, 2009 4:16 pm ]
Post subject:  Help with linked lists
What is it you are trying to achieve?
insert a single character into my list "A,B,C,D,E" alphabetically (all pointers-> data are strings length of 1)


What is the problem you are having?
the proc just ends up deleting the test string from the list when it encounters it


Describe what you have tried to solve this problem
tried tracing it on paper, got very confused


Turing:

%my type being used:
type cell :
    record
        data : string
        link : pointer to cell
    end record

% procedure in question
proc insert_cell (test : string)
    p := first
    var p2 : pointer to cell := first -> link
    var pn, temp : ^cell := nil
        loop

            put "p1= ", p -> data
            put "p2= ", p2 -> data

            if test <= p2 -> data then
                put "condition met: test >= p2  ... exiting"
                put "                  ", test, " <= ", p2 -> data
                new pn
                temp := p2 -> link
                pn -> data := test
                pn -> link := p2
                p -> link := temp
                exit
            end if
            p := p -> link
            p2 := p2 -> link
        end loop

    getch (ch)
    len += 1
end insert_cell




Please specify what version of Turing you are using
4.1
Author:  jbking [ Sun May 03, 2009 6:14 pm ]
Post subject:  Re: Help with linked lists
code:

                new pn
                temp := p2 -> link
                pn -> data := test
                pn -> link := p2
                p -> link := temp


Let's look at this sequence of steps.

Temp is assigned to whatever is after p2 in the list.
Pn is given the test data and is linked to p2.
p's link is assigned to put at temp which is after p2 in the list, which I don't think is what you want. This is basically saying that after p in the list should be what came after p2 which is like deleting it from the list.
Consider just taking the temp assignment and the p->link line and I think you should see the problem here.

Another point is that if the test string came before the start of the list or at the end of the list you aren't handling these cases I think.
Author:  paulm [ Mon May 04, 2009 4:12 pm ]
Post subject:  Re: Help with linked lists
Thanks alot jbking! you're the first to respond to any of my threads here, ever Cool

I revised the code and got it working thanks to your help:

Turing:

proc insert_cell (test : string)
    findlast                                                   %finds the last node in the list
    p := first
    var p2 : pointer to cell := first -> link
    var pn : ^cell := nil
    if len < 7 then
        if test <= first -> data then
            new pn
            first -> link := pn
            pn -> link := p2
            pn -> data := test
        elsif test >= last -> data then
            new pn
            last -> link := pn
            pn -> data := test
            pn -> link := nil
        else                               
            p := first
            loop
                if test <= p2 -> data then
                    new pn
                    p -> link := pn
                    pn -> link := p2
                    pn -> data := test
                    exit
                end if
                p := p -> link
                p2 := p2 -> link
            end loop
        end if
        len += 1
    else
        put "max linked list length reached ...exiting"
        getch (ch)
    end if
end insert_cell


thanks again Mr. Green

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy