C/C++

..

Exercise 1

Write a program in C Language that implement 2 functions:

a) convertDoublyToCircular that takes in a doubly linked list and converts it into a circular list

b) convertCircularToStack that takes in a circular linked list and returns a stack with all the

nodes of the linked list on the stack

.

//////////////////////////////////////////////////

////

Exercise 2

Using only the given implementation of SinglyLinkedList class and Stack class add method into

SinglyLinkedList that received as a parameter another SinglyLinkedList and checks if the

received list is a subset of the current list and return either true or false based on the result. You must use the

given Stack implementation to perform this check.

Implementations :

1) Doubly LinkedList
2) Singly LinkedList
3) Stack

Will be given in another attachment.

//////////////////////////////////////////////////

Exercise 3

(Solve in C LANGUAGE) instead of c++

Using only std::queue do the following:

a. Write a recursive C++ method recursiveDisplayReverseOrder that takes as parameters a

Queue of strings, where each element is a word and display the words in reverse order.

b. Write a C++ method iterativeDisplayReverseOrder which behaves just like the method in

part a but doesn’t use recursion.

Note that std::queue has a slightly different way to access data. Function pop() will only remove the

first element from the queue without returning anything. To get the data you have to use function front()

then do pop() to remove it. For more details:

https://en.cppreference.com/w/cpp/container/queue

//////////////////////////////////////////////////////////

Exercise 4

Write a C program that implements a dequeue (double ended queue) abstract data type using 1) an unsorted

doubly linked list, and 2) using a sorted doubly linked list. You must use the DoublyLinkedList provided

to you with this assignment.

.

Example of how my C program syntaxes are like:

(please try to follow them as much as possible)

1)Linked Lists:

#include

#include

typedef struct Node

{

int data;

struct Node *next;

}

node;

node *head=NULL;

////// LINKED LISTS //////

void insertAtFirst(node **head,int x)

{

node *p;

p=(node*)malloc(sizeof(node));

p->data=x;

p->next=NULL;

if(*head==NUll)

*head=p;

else

{

p->next=(*head);

*head=p;

}

}/

/

void insertAtEnd(node **head,int x)

{

node *p,*q;

p=(node*)malloc(sizeof(node));
p->data=x;
p->next=NULL;

if(*head==NULL)

*head=p;
else
{

q=*head;

while(q->next!=NULL)

q=q->next;

q->next=p;

p->next=NULL;

}

}/

/

void deleteFrist(node **head)

{
node *p;
if(*head==NULL)
{

printf(“Linked List is Empty”);

return;

}
else
{

p=*head;

*head=(*head)->next;

free(p);

}
}//

void deleteLast(node **head)

{
node *p,*q;
if(*head==NULL)
{
printf(“Linked List is Empty”);
return;
}
else
{
q=*head;

p=(*head)->next;

while(p->next!=NULL)

{

p=p->next;

q=q->next;

}

q->next=NULL;

free(p);

}
}

2)Stacks:

#include
#include

typedef struct Node{

int data;
struct Node *next;

}stack;

stack *Top=NULL;

////// Stacks //////

void push(stack **Top,int x)

{

stack *p;

p=(stack*)malloc(sizeof(stack));

p->data=x;
p->next=NULL;

if(*Top==NULL)

*Top=p;

else
{

p->next=*Top;

*Top=p;
}
}//

int pop(stack **Top)

{
stack *p;

int x=-1;

if(*Top==NULL)
{

printf(“Stack is Empty\n”);

returnx;

}
else
{

p=*Top;

x=(*Top)->data;

*Top=(*Top)->next;

return x;

}
}//

void printStack(stack *Top)

{
stack *p;

for(p=Top;p!=NULL;p=p->next)

printf(“%d”,p->data);

}//

3)Queues:

#include
#include

typedef struct Node{
int data;
struct Node *next;

}Queue;

Queue *front=NULL;

Queue *rear=NULL;

////// Queues //////

void enqueue(Queue **front,Queue **rear,int x)

{

Queue *p;

p=(Queue*)malloc(sizeof(Queue));

p->data=x;
p->next=NULL;

if(*front==NULL)

*front=*rear=p;

else
{

(*rear)->next=p;

*rear=p;

}
}//

int dequeue(Queue **front,Queue **rear)

{
int x=-1;
Queue *p;

if(*front==NULL)
{

printf(“Queue is Empty.\n”);

return x;
}
else

{

x=(*front)->data;

p=(*front);

if( (*front)->next==NULL )

{

*front=*rear=NULL;

free(p);

return x;

}

else

{

*front=(*front)->next;

free(p);
}
}

}/

//Singly LinkedList
#include
#include
using namespace std;
class SinglyNode {
public:
int data;
SinglyNode *next;
SinglyNode(int d, SinglyNode *ptr = 0) {
data = d;
next = ptr;
}
};
class SinglyLinkedList {
public:
SinglyNode *head, *tail;

SinglyLinkedList() {
head = tail = 0;
}

~SinglyLinkedList() {
for(SinglyNode *p; !isEmpty();) {
p = head->next;
delete head;
head = p;
}
}

int isEmpty() {
return head == 0;
}
void addToBack(int data) {
if (tail != 0) {
tail->next = new SinglyNode(data);
tail = tail->next;
} else head = tail = new SinglyNode(data);
}

void addToFront(int data) {
/* to be implemented… */
}

int removeFromBack() {
/* to be implemented… */
return -1;
}

int removeFromFront() {
/* to be implemented… */
return -1;
}

bool isSubset(SinglyLinkedList& otherlist) {
/* to be implemented… */
return false;
}

int size() {
SinglyNode *p = head;
int counter=0;
while (p != 0) {
p = p->next;
counter++;
}
return counter;
}

void print() {
SinglyNode *p = head;
while (p != 0) {
cout << p->data << " ---> ” ;
p = p->next;
}
cout << "/\n\n" ; } }; int main() { SinglyLinkedList list; list.addToBack(100); list.addToBack(5); list.addToBack(20); list.addToBack(33); list.print(); return 0; }

//Stack
#include
#include
using namespace std;
class StackNode {
private:
char data;
StackNode *next;

public :
StackNode(){
next=0;
}

StackNode(char n ,StackNode* ptr=0 ){
data =n ;
next= ptr;
}

friend class Stack;
};

class Stack
{
private:
StackNode *head,*tail;

public:
Stack() {
head=tail=0;
}

void push(char d){
head = new StackNode (d,head);

if (tail ==0)
tail = head ;
}

char pop (){
char d = head->data;
StackNode * temp = head;
if(head == tail )
head = tail = 0;
else
head = head->next;

delete temp;

return d;
}

bool isEmpty(){
if(head == 0)
return true;
else
return false;
}
};
int main(int argc, char *argv[]) {
Stack s;

s.push(‘m’);
s.push(‘o’);
s.push(‘c’);
s.push(‘l’);
s.push(‘e’);
s.push(‘W’);

while(!s.isEmpty()) {
cout << s.pop(); } cout << endl ; return 0; }

//Doubly LinkedList
#include
#include
using namespace std;
class DoublyNode {
public:
int data;
DoublyNode *next;
DoublyNode *prev;

DoublyNode(int d, DoublyNode *ptr_n = 0, DoublyNode *ptr_p = 0) {
data = d;
next = ptr_n;
prev = ptr_p;
}
};
class DoublyLinkedList {
public:
DoublyNode *head, *tail;

DoublyLinkedList() {
head = tail = 0;
}

~DoublyLinkedList() {
for(DoublyNode *p; !isEmpty();) {
p = head->next;
delete head;
head = p;
}
}

int isEmpty() {
return head == 0;
}
void add(int data) {
if (tail != 0) {
tail->next = new DoublyNode(data, 0, tail);
tail = tail->next;
} else head = tail = new DoublyNode(data);
}

int size() {
DoublyNode *p = head;
int counter=0;
while (p != 0) {
p = p->next;
counter++;
}
return counter;
}

void print() {
DoublyNode *p = head;
while (p != 0) {
cout << p->data ;
if(p->next != 0)
cout << " <---> ” ;
p = p->next;
}
cout << "\n\n" ; } void printInReverse() { DoublyNode *p = tail; while (p != 0) { cout << p->data;
if(p->prev != 0)
cout << " <---> ” ;
p = p->prev;
}
cout << "\n\n" ; } }; int main() { DoublyLinkedList list; int const size1=5; int data1[size1]; list.add(100); list.add(27); list.add(13); list.add(4); list.print(); list.printInReverse(); return 0; }