Computer and Information Sciences 192

Project 5. Implementation of Linked Lists

 

Objectives:

Upon successful completion of the project, the student will be able to:

Skills assumptions:

Introduction

As historically conceived, arrays and data processing with arrays have inherent weaknesses: the potential misuse of memory due to extravagant array sizes and potential corruption of the data set by limiting the array size. In fact, the size of the data set is often unknown until after the execution of the program. To overcome this severe limitation, the concept of a "dynamically allocated" data set (linked list) has become most often used. The process of creating a linked list is to first create data structures. Memory is then allocated by the program for each record as it is needed by the program, with the data then being entered. Each structure is then connected by "pointers" from one field in a record, to the beginning memory location of a subsequent record.

Operations with linked lists are similar to those of arrays, with minor "twists". As with arrays, lists are traversed by "incrementing" a pointer value rather than a counter.

Scenario and Output

No new operations are expected except for those that might be required for pointer manipulations. The set of functions from project 4 should be minimally modified such that the array processing is converted to linked list processing. Except for the lack of a sorting option, the changes will ultimately be transparent to the user. As before, all coding should be commented as appropriate and in accordance with the Style Manual.

Program Coding

The declaration of the data structure should occur as a global (external) structure. This will make the general form of the structure available to the entire program. Think of the structure as a user-defined data type. All variables using structure data type should be declared within the functions and should be passed as parameters between functions.

The return() is typically used to return the execution status of the function. Typically, a 0 (zero) indicates an execution failure or error and a non-zero value indicates execution success.

There are two methods for creating structures - one is to create a structure and directly type variables without giving the structure an identifier, the second method is to define the structure with its own identifier then later declare variables. The second method is most often used because it gives the programmer more flexibility and allows the structure to be used as a data type for parameters of a function. We will use the second method.

Figure 14 gives an example of the declaration of a structure and the declaration of variables within the function main().

-------------------------------------------------------------

 

#include < iostream >
#include < cmath >

struct samp
{

    int idata;
    double fdata;
    string name;
};//End of struct samp

void main(void)
{

    struct samp varstr;
    struct samp *strptr;

      .
    . //Body of main( )
    .

}

Figure 14. Sample structure declaration prior to main(). Note the location of the name of the structure an the declaration of the variables within main. The declaration of the structure prior to main allows the structure to be used in the same manner as a standard data type.

------------------------------------------------------------

Pointer variables can also be used to reference a structure. The strptr variable in Figure 14 demonstrates the declaration of a pointer to a structure of type samp. Both variable types may be passed to a function (Figure 15).

------------------------------------------------------------

 

void main( )
{

    struct samp varstr;
    struct samp *strptr;

    .
    . // Body of main()
    .

    sampfn(varstr, strptr); //Function call

    .
    .// More main() stuff
    .

} //End of int main( )

void sampfn(struct samp var, struct samp *ptr)
{
    .
    .// Body of the function
    .
} //End of void sampfn(struct samp var, struct samp *ptr)

Figure 15. Pointers to structures may be created in much the same way that pointers to any standard data type are made. The only assumption is that the structure form is available to all functions within the program.

-------------------------------------------------------------

Once a variable has been declared for a structure data type it may be used in combination with a specified field (member). An example of the use of a structure variable is --

varstr.idata=25;

Note that a dot is used to separate the structure name from the field name. In a similar manner pointer variables may be used to acquire, manipulate, and output data. An example of the use of a pointer to a structure is --

(*strptr).fdata=23.46;

An alternative pointer syntax is perfered for the utilization of structure pointers; the -> symbol or "arrow". For example the assignment above samn be written as --

strptr->fdata=23.46;

The passing of structure pointers is much the same as passing a standard pointer variable. The address of the beginning of the structure is passed as an argument to a function call and the "pointer parameter" is typed in the function heading in a similar manner as a standard pointer variable. Figure 16 presents a sample program in which a pointer to a sturcture is passed to a function which allows the user to enter data.

------------------------------------------------------------

#include < iostream > // For std C++ functions

#include < string > // For string operations

struct samp

{

    int idata;
    double fdata;
    string name;

}; //End of struct samp

void input(struct samp *); // Prototype

void main ( )

{

    struct samp *strptr, strvar;
    string fstr;
    strptr= new samp;
    input(strptr);
    cout<<<"strptr string data --"<< strptr->name <<" intteger data --"<<    strptr->idata<<" double data ->"<< fdata << endl;

} //End of void main( )

/**************** Input Function *******************/

void input(struct samp *p)

{

    cout<< "\nEnter a string: ";
    getline(cin, p->name);
    cout <<"\nEnter an integer: ";
    cin>> p->idata;
    cout<<"\nEnter a double: ";
    cin >> p->fdata;

} //End of void input(struct samp *p)

Figure 16. Sample program which passes a pointer to a structure to a user-defined function.

-----------------------------------------------------------

Note the use of new in the main function. This operator dynamicly allocates memory (RAM) for the storage of data, then returns the beginning memory location of that structure to strptr. When pointers to structures are declared, memory is not automatically allocated as it is with standard pointer variables.

D. Creation of Linked Lists

A linked list is a sequence of data structures which are connected to one another by way of pointer fields. For singally linked lists (those which are connected in one direction) the pointer field typically occurs at the end of the field - though there is no requirement to do so. The pointer field is typed as a pointer to a structure of the same type as the one it is in. Figure 17 shows the declaration of a structure with a pointer field called next and the creation of a linked list. Note the declarationof pointer variables one of which is first which will be used to keep track of the first structure in the list. It should be manipulated with caution and when used, it should be used only to initialize other pointer variables.

As with arrays the process of moving from one structure to another is called traversing a list. The process is much like the process of traversing an array. The main difference is in the "incrementation" of the pointer. In the case of the program in figure 17, the incrementation is the following --

p = p->next; //"p gets the contents of p dot next".

--------------------------------------------------------------

#include < iostream > // For C++ functions

#include < string > // For string operations

struct samp

{

    int idata;
    double fdata;
    string name;
    struct samp *next;

}; //End of struct samp

void input(struct samp *);

void main ( )

{

   struct samp *first, *p, *q;
   string ans = "Y";
    first= new samp;

    p=first;
    input(p);
    p->next=NULL;

    cout<<"\n Enter another structure (Y/N): ";
    getline(cin,ans);

    while(ans.at(0) == "Y"))

    {

        q= new samp;
        input(q);
        q->next=NULL;
        p->next=q;
        p=p->next;
        cout<<"\n Enter another structure (Y/N): ";
        getline(cin, ans);

    }//End of while( ans == "Y")

    p=first; //Reinitializing p for output

    while(p)
    {

        cout<<"\n p->name:"<< p->name <<"p->idata: "<< p->idata<<
        "p->fdata: "<< p->fdata;
        p=p->next;

    } // End of while(p)

} //End of void main( )

/**************** Input Function *******************/

void input( samp *p)
{

    string fstr;

    cout << "\nEnter a string: ";
    getline(cin, p->name);
    cout<<"\nEnter an integer: ";
    cin>>p->idata;
    cout << "\nEnter a double: ";
    cin >> p->fdata;

} // End of void input( *samp p)

Figure 17. A sample program which creates a linked list of structures then prints the list using a traversing technique.

--------------------------------------------------------------

IV. Evaluation Package

All modified modules should be presented for review. Calculations should be checked and verified by annotation. Samples of any modified output should be included.