Liren Large Software Subsidy 7/07.iso/c/c100/3.ddi/LLIST.ZIP/LLIST.ASD

Text File | 1990-09-27 | 6.1 KB | 275 lines

_C PROGRAMMING COLUMN_
by Al Stevens

[LISTING ONE]

// -------- linklist.h

#ifndef LINKLIST
#define LINKLIST

#include <stdio.h>

class LinkedList {
    typedef struct list_entry    {
        struct list_entry *NextEntry;
        struct list_entry *PrevEntry;
        void *entrydata;
    } ListEntry;
    ListEntry *FirstEntry;
    ListEntry *LastEntry;
    ListEntry *CurrEntry;
public:
    // ---- constructor
    LinkedList(void)
        { FirstEntry = LastEntry = CurrEntry = NULL; }
    // ---- destructor
    ~LinkedList(void);
    // ---- add an entry
    void addentry(void *newentry, int size);
    // ---- delete the current entry
    void delete_entry(void);
    // ---- get the first entry in the list
    void *getfirst(void);
    // ---- get the next entry in the list
    void *getnext(void);
    // ---- get the previous entry in the list
    void *getprev(void);
    // ---- get the last entry in the list
    void *getlast(void);
    // ---- get the current entry in the list
    void *getcurr(void)
        {return CurrEntry==NULL ? NULL : CurrEntry->entrydata;}
};

#endif




[LISTING TWO]

// -------------- linklist.cpp

#include <string.h>
#include "linklist.h"

// ------- linked list destructor
LinkedList::~LinkedList(void)
{
    ListEntry *thisentry = FirstEntry;

    while (thisentry != NULL)    {
        delete thisentry->entrydata;
        ListEntry *hold = thisentry;
        thisentry = thisentry->NextEntry;
        delete hold;
    }
}

// --------- add an entry to the list
void LinkedList::addentry(void *newentry, int size)
{
    /* ------- build the new entry ------- */
    ListEntry *thisentry = new ListEntry;
    thisentry->entrydata = new char[size];
    memcpy(thisentry->entrydata, newentry, size);

    if (CurrEntry == NULL)    {
        thisentry->PrevEntry = NULL;
        // ---- adding to the beginning of the list
        if (FirstEntry != NULL)    {
            /* ---- already entries in this list ---- */
            thisentry->NextEntry = FirstEntry;
            FirstEntry->PrevEntry = thisentry;
        }
        else    {
            // ----- adding to an empty list
            thisentry->NextEntry = NULL;
            LastEntry = thisentry;
        }
        FirstEntry = thisentry;
    }
    else    {
        // ------- inserting into the list
        thisentry->NextEntry = CurrEntry->NextEntry;
        thisentry->PrevEntry = CurrEntry;
        if (CurrEntry == LastEntry)
            // ---- adding to the end of the list
            LastEntry = thisentry;
        else
            // ---- inserting between existing entries
            CurrEntry->NextEntry->PrevEntry = thisentry;
        CurrEntry->NextEntry = thisentry;
    }
    CurrEntry = thisentry;
}

// ---------- delete the current entry from the list
void LinkedList::delete_entry(void)
{
    if (CurrEntry != NULL)    {
        if (CurrEntry->NextEntry != NULL)
            CurrEntry->NextEntry->PrevEntry = CurrEntry->PrevEntry;
        else
            LastEntry = CurrEntry->PrevEntry;
        if (CurrEntry->PrevEntry != NULL)
            CurrEntry->PrevEntry->NextEntry = CurrEntry->NextEntry;
        else
            FirstEntry = CurrEntry->NextEntry;
        delete CurrEntry->entrydata;
        ListEntry *hold = CurrEntry->NextEntry;
        delete CurrEntry;
        CurrEntry = hold;
    }
}

// ---- get the first entry in the list
void *LinkedList::getfirst(void)
{
    CurrEntry = FirstEntry;
    return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}

// ---- get the next entry in the list
void *LinkedList::getnext(void)
{
    if (CurrEntry == NULL)
        CurrEntry = FirstEntry;
    else
        CurrEntry = CurrEntry->NextEntry;
    return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}

// ---- get the previous entry in the list
void *LinkedList::getprev(void)
{
    if (CurrEntry == NULL)
        CurrEntry = LastEntry;
    else
        CurrEntry = CurrEntry->PrevEntry;
    return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}

// ---- get the last entry in the list
void *LinkedList::getlast(void)
{
    CurrEntry = LastEntry;
    return CurrEntry == NULL ? NULL : CurrEntry->entrydata;
}



[LISTING THREE]

// -------- demolist.cpp

#include <stream.hpp>
#include "strings.h"
#include "linklist.h"

void collectnames(LinkedList& namelist);
int menu(void);
void displaynames(LinkedList& namelist);
void stepforward(LinkedList& namelist);
void stepbackward(LinkedList& namelist);
string insertname(LinkedList& namelist);

void main(void)
{
    cout << "Enter some names followed by \"end\"\n";
    // ------ a linked list of names
    LinkedList namelist;
    collectnames(namelist);
    int key = 0;
    while (key != 6)    {
        switch (key = menu())    {
            case 1:
                displaynames(namelist);
                break;
            case 2:
                stepforward(namelist);
                break;
            case 3:
                stepbackward(namelist);
                break;
            case 4:
                insertname(namelist);
                break;
            case 5:
                namelist.delete_entry();
                break;
            case 6:
                cout << "Quitting...";
                break;
            default:
                break;
        }
    }
}

void collectnames(LinkedList& namelist)
{
    // ------- until the user types "end"
    while (insertname(namelist) != "end")
        ;
}

int menu(void)
{
    cout << "\n1 = display the names";
    cout << "\n2 = step forward through the names";
    cout << "\n3 = step backward through the names";
    cout << "\n4 = insert a name";
    cout << "\n5 = delete the current name";
    cout << "\n6 = quit";
    cout << "\nEnter selection: ";
    int key;
    cin >> key;
    return key;
}

// ------ read the names in a list and display them
void displaynames(LinkedList& namelist)
{
    cout << "------ NAME LIST ------\n";
    char *name = namelist.getfirst();
    while (name != NULL)    {
        cout << name << "\n";
        name = namelist.getnext();
    }
    cout << "-----------------------\n";
}

// ------- step forward through the list of names
void stepforward(LinkedList& namelist)
{
    char *name = namelist.getnext();
    cout << (name ? name : "-- End of list --") << "\n";
}

// ------- step backwardward through the list of names
void stepbackward(LinkedList& namelist)
{
    char *name = namelist.getprev();
    cout << (name ? name : "-- Beginning of list --") << "\n";
}

// ------- insert a name into the list
string insertname(LinkedList& namelist)
{
    cout << "Enter a name: ";
    // ----- a string to hold one name
    string name(80);
    // ------- read a name
    cin >> name.stradr();
    // ------- add it to the list
    if (name != "end")
        namelist.addentry(name.stradr(), name.length());
    return name;
}