Question

Lists are members of a general category of abstract data types (ADTs) called containers (i.e., objects...

Lists are members of a general category of abstract data types (ADTs) called containers (i.e., objects whose purpose is to hold other objects). A list is a collection of items having the following defining characteristics:

  1. Homogeneity: All the items are of the same type.
  2. Linearity: Each item has a unique predecessor (except the first) and a unique successor (except the last).
  3. Variable Length: The number of items can vary over time.
  4. Order: Items may be ordered (i.e., as in a sorted list) or unordered (i.e., as in an unsorted list).
  5. Keys: A member or combination of members describing an item may be unique (i., there is only one item matching the description) or duplicated (i., more than one item matches the description).

           SECTION 1 :

Implement a C++ class for an array representation of a list. The methods must be based upon the pseudocode provided on the Algorithms page. Use the following declarations as a starting point for your implementation :

const int MAX_LENGTH = some application-specific max value;

typedef <some data type> DataType;

class List

{

public:

    methods go here

private:

    int p;

    int length;

    DataType a [MAX_LENGTH];

};

Note : Any other variable or constant declarations required would be local to the methods.

     SECTION 2 :

Implement a C++ class for a linked list representation of a list. The methods must be based upon the pseudocode provided on the Algorithms page. Use the following declarations as a starting point for your implementation :

typedef <some data type> DataType ;

struct Node;

struct Node

{

    DataType value;

    Node* next;

};

class List

{

    public:

    methods go here

   private:

    Node* head;

    int length;

    Node* p;

    Node* prevP;

};

Note: Any other variable or constant declarations required would be local to the methods.

             SECTION 3 :

Implement a C++ program that can be used to demonstrate that the list classes implemented in SECTION 1 and 2 are correct. To simplify the demonstration, set some application-specific max value to 10 and some data type to int.

( Submit : all source code files i.e., only the .cpp and .h files)

Engineering   Computer-Science   
0 0
Add a commentTranscribed image text
Next >

Homework Answers

Answer #1

SECTION-1

#include<iostream.h>
#include<constream.h>
template<class T>
class LinearList
{
    public:
        LinearList(int MaxLinearSize=10);
        ~LinearList(){delete[]element;}
        int isEmpty()const{return length==0;}
        int Length()const{return length;}
        int Find(int k,T&x)const;
        int Search(const T&x)const;
        void Delete(int k,T&x);
        void Insert(int k,const T&x);
        void Output()const;
    private:
        int length;
        int MaxSize;
        T *element;
};
    template<class T>
LinearList<T>::LinearList(int MaxListSize)
{
    MaxSize=MaxListSize;
    element=new T[MaxSize];
    length=0;
}
template<class T>
int LinearList<T>::Find(int k,T&x)const
{
    if(k<1||k>length)
        return 0;
    x=element[k-1];
    return 1;
}
template<class T>
int LinearList<T>::Search(const T&x)const
{
    for(int i=0;i<length;i++)
        if(element[i]==x)
            return ++i;
    return 0;
}
    template<class T>
void LinearList<T>::Delete(int k,T&x)
{
    if(Find(k,x))
    {
        for(int i=k;i<length;i++)
            element[i-1]=element[i];
        length--;
    }
    else
        cout<<"out of bounds\n";
}
    template<class T>
void LinearList<T>::Insert(int k,const T&x)
{
    if(k<0||k>length)
        cout<<"out of bounds\n";
    if(length==MaxSize)
        cout<<"no memory\n";
    for(int i=length-1;i>=k;i--)
        element[i+1]=element[i];
    element[k]=x;
    length++;
}
template<class T>
void LinearList<T>::Output()const
{
    if(isEmpty())
        cout<<"list is empty\n";
    else
        for(int i=0;i<length;i++)
            cout<<element[i]<<"\t";
}
void menu()
{
    cout<<"\n MENU\n" ;
    cout<<"-----------\n";
    cout<<"1.Length\n";
    cout<<"2.Find\n";
    cout<<"3.Search\n";
    cout<<"4.Delete\n";
    cout<<"5.Insert\n";
    cout<<"6.Output\n";
    cout<<"-------------\n";
}
void main()
{
    int ch;
    int k,x,len,p;
    clrscr();
    LinearList <int> obj;
    do
    {
        menu();
        cout<<"enter choice\t";
        cin>>ch;
        switch(ch) {
            case 1:
                len=obj.Length();
                if(len==0)
                    cout<<"List is empty\n";
                else
                    cout<<"length of linearlist is "<<len<<endl;
                break;
            case 2:
                cout<<"enter k,x(position and value)\n";
                cin>>k>>x;
                p=obj.Find(k,x);
                if(p==1)
                    cout<<"found"<<endl;
                if(p==0)
                    cout<<"not found"<<endl;
                break;
            case 3:
                cout<<"enter x(value)\n";
                cin>>x;
                p=obj.Search(x);
                if(p)
                    cout<<"searching is sucessful and found at"<<p<<endl;
                else
                    cout<<"searching not sucessful"<<endl;
                break;
            case 4:
                cout<<"enter k,x(position and value)\n";
                cin>>k>>x;
                obj.Delete(k,x);
                break;
            case 5:
                cout<<"enter k,x(index and value)\n";
                cin>>k>>x;
                obj.Insert(k,x);
                break;
            case 6:
                cout<<"elements in the list are:\n\n";
                obj.Output();
                break;
            default:
                cout<<"invalid choice\n";
                break;
        } } while(ch>=1&&ch<=6);
        getch();
}


SECTION-2

#include<iostream>

#include<cstdio>

#include<cstdlib>
using namespace std;
/*
 * Node Declaration
 */
struct node
{
    int info;
    struct node *next;
}*start;
 
/*
 * Class Declaration
 */
class single_llist
{
    public:
        node* create_node(int);
        void insert_begin();
        void insert_pos();
        void insert_last(); 
        void delete_pos();
        void sort();
        void search();
        void update();
        void reverse();
        void display();
        single_llist() 
        {
            start = NULL;
        }
};
 
/*
 * Main :contains menu 
 */
main()
{
    int choice, nodes, element, position, i;
    single_llist sl;
    start = NULL;
    while (1)
    {
        cout<<endl<<"---------------------------------"<<endl;
        cout<<endl<<"Operations on singly linked list"<<endl;
        cout<<endl<<"---------------------------------"<<endl;
        cout<<"1.Insert Node at beginning"<<endl;
        cout<<"2.Insert node at last"<<endl;
        cout<<"3.Insert node at position"<<endl;
        cout<<"4.Sort Link List"<<endl;
        cout<<"5.Delete a Particular Node"<<endl;
        cout<<"6.Update Node Value"<<endl;
        cout<<"7.Search Element"<<endl;
        cout<<"8.Display Linked List"<<endl;
        cout<<"9.Reverse Linked List "<<endl;
        cout<<"10.Exit "<<endl;
        cout<<"Enter your choice : ";
        cin>>choice;
        switch(choice)
        {
        case 1:
            cout<<"Inserting Node at Beginning: "<<endl;
            sl.insert_begin();
            cout<<endl;
            break;
        case 2:
            cout<<"Inserting Node at Last: "<<endl;
            sl.insert_last();
            cout<<endl;
            break;
        case 3:
            cout<<"Inserting Node at a given position:"<<endl;
            sl.insert_pos();
            cout<<endl;
            break;
        case 4:
            cout<<"Sort Link List: "<<endl;
            sl.sort();
            cout<<endl;
            break;
        case 5:
            cout<<"Delete a particular node: "<<endl;
            sl.delete_pos();
            break;
        case 6:
            cout<<"Update Node Value:"<<endl;  
            sl.update();
            cout<<endl;
            break;
        case 7:
            cout<<"Search element in Link List: "<<endl;
            sl.search();
            cout<<endl;
            break;
        case 8:
            cout<<"Display elements of link list"<<endl;
            sl.display();
            cout<<endl;
            break;
        case 9:
            cout<<"Reverse elements of Link List"<<endl;
            sl.reverse();
            cout<<endl;
            break;
        case 10:
            cout<<"Exiting..."<<endl;
            exit(1);
            break;  
        default:
            cout<<"Wrong choice"<<endl;
        }
    }
}
 
/*
 * Creating Node
 */
node *single_llist::create_node(int value)
{
    struct node *temp, *s;
    temp = new(struct node); 
    if (temp == NULL)
    {
        cout<<"Memory not allocated "<<endl;
        return 0;
    }
    else
    {
        temp->info = value;
        temp->next = NULL;     
        return temp;
    }
}
 
/*
 * Inserting element in beginning
 */
void single_llist::insert_begin()
{
    int value;
    cout<<"Enter the value to be inserted: ";
    cin>>value;
    struct node *temp, *p;
    temp = create_node(value);
    if (start == NULL)
    {
        start = temp;
        start->next = NULL;          
    } 
    else
    {
        p = start;
        start = temp;
        start->next = p;
    }
    cout<<"Element Inserted at beginning"<<endl;
}
 
/*
 * Inserting Node at last
 */
void single_llist::insert_last()
{
    int value;
    cout<<"Enter the value to be inserted: ";
    cin>>value;
    struct node *temp, *s;
    temp = create_node(value);
    s = start;
    while (s->next != NULL)
    {         
        s = s->next;        
    }
    temp->next = NULL;
    s->next = temp;
    cout<<"Element Inserted at last"<<endl;  
}
 
/*
 * Insertion of node at a given position
 */
void single_llist::insert_pos()
{
    int value, pos, counter = 0; 
    cout<<"Enter the value to be inserted: ";
    cin>>value;
    struct node *temp, *s, *ptr;
    temp = create_node(value);
    cout<<"Enter the postion at which node to be inserted: ";
    cin>>pos;
    int i;
    s = start;
    while (s != NULL)
    {
        s = s->next;
        counter++;
    }
    if (pos == 1)
    {
        if (start == NULL)
        {
            start = temp;
            start->next = NULL;
        }
        else
        {
            ptr = start;
            start = temp;
            start->next = ptr;
        }
    }
    else if (pos > 1  && pos <= counter)
    {
        s = start;
        for (i = 1; i < pos; i++)
        {
            ptr = s;
            s = s->next;
        }
        ptr->next = temp;
        temp->next = s;
    }
    else
    {
        cout<<"Positon out of range"<<endl;
    }
}
 
/*
 * Sorting Link List
 */
void single_llist::sort()
{
    struct node *ptr, *s;
    int value;
    if (start == NULL)
    {
        cout<<"The List is empty"<<endl;
        return;
    }
    ptr = start;
    while (ptr != NULL)
    {
        for (s = ptr->next;s !=NULL;s = s->next)
        {
            if (ptr->info > s->info)
            {
                value = ptr->info;
                ptr->info = s->info;
                s->info = value;
            }
        }
        ptr = ptr->next;
    }
}
 
/*
 * Delete element at a given position
 */
void single_llist::delete_pos()
{
    int pos, i, counter = 0;
    if (start == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    cout<<"Enter the position of value to be deleted: ";
    cin>>pos;
    struct node *s, *ptr;
    s = start;
    if (pos == 1)
    {
        start = s->next;
    }
    else
    {
        while (s != NULL)
        {
            s = s->next;
            counter++;  
        }
        if (pos > 0 && pos <= counter)
        {
            s = start;
            for (i = 1;i < pos;i++)
            {
                ptr = s;
                s = s->next;
            }
            ptr->next = s->next;
        }
        else
        {
            cout<<"Position out of range"<<endl;
        }
        free(s);
        cout<<"Element Deleted"<<endl;
    }
}
 
/*
 * Update a given Node
 */
void single_llist::update()
{
    int value, pos, i;
    if (start == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    cout<<"Enter the node postion to be updated: ";
    cin>>pos;
    cout<<"Enter the new value: ";
    cin>>value;
    struct node *s, *ptr;
    s = start;
    if (pos == 1)
    {
        start->info = value; 
    }
    else
    {
        for (i = 0;i < pos - 1;i++)
        {
            if (s == NULL)
            {
                cout<<"There are less than "<<pos<<" elements";
                return;
            }
            s = s->next;
        }
        s->info = value;  
    }
    cout<<"Node Updated"<<endl;
} 
 
/*
 * Searching an element
 */
void single_llist::search()
{
    int value, pos = 0;
    bool flag = false;
    if (start == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    cout<<"Enter the value to be searched: ";
    cin>>value;
    struct node *s;
    s = start;
    while (s != NULL)
    {
        pos++;
        if (s->info == value)
        {
            flag = true;
            cout<<"Element "<<value<<" is found at position "<<pos<<endl;
        }
        s = s->next;
    }
    if (!flag)
        cout<<"Element "<<value<<" not found in the list"<<endl;  
}
 
/*
 * Reverse Link List
 */
void single_llist::reverse()
{
    struct node *ptr1, *ptr2, *ptr3;
    if (start == NULL)
    {
        cout<<"List is empty"<<endl;
        return;
    }
    if (start->next == NULL)
    {
        return;
    }  
    ptr1 = start;
    ptr2 = ptr1->next;
    ptr3 = ptr2->next;
    ptr1->next = NULL;
    ptr2->next = ptr1;
    while (ptr3 != NULL)
    {
        ptr1 = ptr2;
        ptr2 = ptr3;
        ptr3 = ptr3->next;
        ptr2->next = ptr1;         
    }
    start = ptr2;
}
 
/*
 * Display Elements of a link list
 */
void single_llist::display()
{
    struct node *temp;
    if (start == NULL)
    {
        cout<<"The List is Empty"<<endl;
        return;
    }
    temp = start;
    cout<<"Elements of list are: "<<endl;
    while (temp != NULL)
    {
        cout<<temp->info<<"->";
        temp = temp->next;
    }
    cout<<"NULL"<<endl;
}
0 0
Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Log In

Sign Up

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract...
Use Java: Also: Please include screenshots if possible. Create a class called AbstractStackTest. Write an abstract method called makeStack that returns a Stack of Strings. Use the Stack interface as the return type, not a specific implementation! Write a class named NodeStackTest that extends your AbstractStackTest class. Implement the makeStack method to return a NodeStack. Repeat parts 1 and 2 for the Queue interface and the NodeQueue implementation. Write a new stack implementation, ArrayStack. It should be generic and use...
Write in Java (Not Javascript) Provide an implementation of priority queue using double-ended doubly linked lists....
Write in Java (Not Javascript) Provide an implementation of priority queue using double-ended doubly linked lists. Recall that double-ended means keeping first and last references and doubly linked feature allows us to go backwards, using a prev reference at each Link. Also, note that the greater the number, the lower the priority. For instance, 2 is of higher priority compared to 5. Specifically, write a class LinkedListPriorityQ which implements the priority queue methods: boolean isEmpty() void enqueue(int item) int dequeue()...
Finish the code wherever it says TODO /**    * Node type for this list. Each...
Finish the code wherever it says TODO /**    * Node type for this list. Each node holds a maximum of nodeSize elements in an    * array. Empty slots are null.    */    private class Node {        /**        * Array of actual data elements.        */        // Unchecked warning unavoidable.        public E[] data = (E[]) new Comparable[nodeSize];        /**        * Link to next node.       ...
Create a C++ project. Download and add the attached .h and .cpp to the project. Write...
Create a C++ project. Download and add the attached .h and .cpp to the project. Write an implementation file to implement the namespace declared in the attached CSCI361Proj5.h. Name the implementation file as YourNameProj5.cpp and add it to the project. Run the project to see your grade. .h file: // Provided by: ____________(your name here)__________ // Email Address: ____________(your email address here)________ // FILE: link.h // PROVIDES: A toolkit of 14 functions for manipulating linked lists. Each // node of...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix...
Data Structure in C++ I keep getting the same warning, and I cant seem to fix it.. Can you explain to me what I am doing wrong? Warning: dlist.cc: In function 'std::ostream& operator<<(std::ostream&, dlist&)': dlist.cc:66:10: error: invalid initialization of reference of type 'std::ostream& {aka std::basic_ostream&}' from expression of type 'dlist::node*' dlist.cc: In function 'dlist operator+(dlist&, dlist&)': dlist.cc:93:8: error: invalid operands of types 'dlist::node*' and 'dlist::node*' to binary 'operator+' dlist.cc:97:8: error: could not convert 'result' from 'int' to 'dlist' My code:...
Goal:   Manage the inventory of objects sold in an online or brick and mortar store. If...
Goal:   Manage the inventory of objects sold in an online or brick and mortar store. If you can't implement all of the features of Project described in this document, implement what you can. Start by implementing the StockItem class, and its derived classes. Then add in the InventoryManager class later. In each case, the test files must be in separate classes. UML Diagram: Use Violet or other drawing software to draw the UML diagrams of each class that you use...
The main goal is to implement two recursive methods, each is built to manipulate linked data...
The main goal is to implement two recursive methods, each is built to manipulate linked data structures. To host these methods you also have to define two utterly simplified node classes. 1.) Add a class named BinaryNode to the project. This class supports the linked representation of binary trees. However, for the BinaryNode class Generic implementation not needed, the nodes will store integer values The standard methods will not be needed in this exercise except the constructor 2.) Add a...
Cpp Task: Create a class called Mixed. Objects of type Mixed will store and manage rational...
Cpp Task: Create a class called Mixed. Objects of type Mixed will store and manage rational numbers in a mixed number format (integer part and a fraction part). Details and Requirements Your class must allow for storage of rational numbers in a mixed number format. Remember that a mixed number consists of an integer part and a fraction part (like 3 1/2 – “three and one-half”). The Mixed class must allow for both positive and negative mixed number values. A...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called...
This laboratory assignment involves implementing a data structure called a map. A map associates objects called keys with other objects called values. It is implemented as a Java class that uses arrays internally. 1. Theory. A map is a set of key-value pairs. Each key is said to be associated with its corresponding value, so there is at most one pair in the set with a given key. You can perform the following operations on maps. You can test if...
You can complete this assignment individually or as a group of two people. In this assignment...
You can complete this assignment individually or as a group of two people. In this assignment you will create a ​​Sorted Singly-Linked List​ that performs basic list operations using C++. This linked list should not allow duplicate elements. Elements of the list should be of type ‘ItemType’. ‘ItemType’ class should have a private integer variable with the name ‘value’. Elements in the linked list should be sorted in the ascending order according to this ‘value’ variable. You should create a...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT