Data Structures in C / C ++: Exercises and Solved Problems

By Fulbia Torres

Data structures constitute one of the main areas of study within the field of computing and this includes knowing how information is organized, that is to say, the storage, handling and recovery of it. Efficiency in the Information management depends to a great extent on the designed structures and the manipulation methods that are implanted on them.
The following book is intended for computer engineering students, computing, systems and careers, where Data Structures are compulsory or elective.
The objective of the book is to serve as an exercise text in which a series of solved exercises of data structures, both at the design level and at the level of implementation, this allows the student to see the application in real problems and practice to obtain skills and develop any exercise proposed. Also includes a series of exercises proposed to be analyzed and developed by students.
The language chosen for the implementation of the exercises is C ++, given its enormous diffusion in the computer medium, its efficiency and its standardization. Each exercise has a part of analysis of the problem posed, the solution, a graphical run and the implementation (source code), this allows the student to see in the language of chosen programming for each of the proposed exercises, as well as reusing the software for the development of their own projects.

• Language: English
• Publisher: Fulbia Torres
• Release date: Nov 21, 2021
• ISBN: 9781005250867

Fulbia Torres

Fulbia Josefina Torres de Delgado (1964) nació en Valera, estado Trujillo, Venezuela. Estudio en el Colegio María Rafols la básica y en el liceo Rafael Rangel el diversificado, en Valera. Se graduó de Ingeniero en Informática en la UCLA, Barquisimeto, estado Lara, Venezuela. Se graduó de Magister en Sistemas de Información en la UCLA, Barquisimeto, estado Lara, Venezuela. Cursa estudios de Doctorado en Ciencias de la Ingeniería: mención Productividad en la UNEXPO, Barquisimeto, estado Lara, Venezuela, por terminar.Trabajó como analista de PDE I (1991-1992), en la ULA, estado Mérida. En la Universidad Fermín Toro (1992-1995)(2000-2002) Docente Instructor. En la Universidad Yacambú (1994-1995) Docente Instructor, desde el año 1995 trabajo en la UNEXPO como Docente Agregado a dedicación exclusiva. Hoy jubilada. www.el.bqto.unexpo.edu.ve >ftorres.Trabajos de investigación realizados: Modelo Integral de Información de la Dirección de Investigación y Postgrado de la UNEXPO. Noviembre, 1999. Sistema de Información Presupuestario para la unidad de Contabilidad. ULA. 1991. Diseño Asistido por Computador de Libros Electrónicos en Computación. Noviembre 2001. Texto de Ejercitación de Problemas de Estructuras de Datos. Octubre 2006.Publicaciones: Estudios Comparativos de Datos Nítidos y Difusos en Estructuras de Datos. Publicado en Redip. UNEXPO. VRB. Venezuela (2011) y en el portal de Difusión de la Producción Científica Hispana revista Dialnet.

Book preview

STACKS

DEFINITION

A STACK is an ordered and homogeneous structure, in which we can add or remove elements at one end called TOP following a LIFO (Last In, First Out) policy. It has only one pointer TOP, that points the last or top the most recently added element of the Stack.

It is an ordered structure, because its elements are placed in a certain order, not according to their value.

It is a homogeneous structure, because all of its elements are of the same type, they can be both simple (integers, reals, ...) and compound (registers, vectors, .....).

ADT STACK

Let's see what is the formal specification of the abstract data type stack:

ADT:stack

Operations:

CONSTRUCTORS

Create an empty stack.

CreateStack: --- Stack

MODIFIERS

Given a stack p and a value e, of the base type, it modifies the stack by piling up the new element on p above the position indicated by the value of the top.

AdicStack: Stack x base_type--- Stack

Given a stack p, it removes the element indicated by the value of the top and modifies the stack.

ElimStack: Stack --- Stack

ANALYZERS

Returns the value of the element that is pointed at by the top.

InfoStack: Stack --- base_type

Returns true if the stack is empty and false otherwise.

EmptyStack: Stack --- logical

Returns true if the stack is full and false otherwise.

FullStack: Stack --- logical

DESTRUCTORS

Destroy the stack by returning all occupied memory.

Does not apply

STATIC IMPLEMENTATION OF STACKS (Using struct)

Definition

# define MAXELEM // maximum number of elements

struct typestack

{

int top;

base_type element[MAXELEM];

}

struct typestack p;

With this definition of Stack the associated operations specified in the ADT would be as follows:

Create an empty stack

int CreateStack (struct typestack *p)

{

return (*p).top = -1;

}

Given a stack p and a value of the base type, modify the stack by building up the new element on p at the position indicated by the value of the top.

void AdicStack (struct typestack *p, base_type value)

{

if FullStack(p) { cout << Stack Overflow << endl;

exit (1); }

else (*p).element[++ ((*p).top)] = value;

}

Given a stack p, it removes the element indicated by the value of the top, the stack is modified.

base_type ElimStack (struct typestack *p)

{

if EmptyStack(p) { cout << Stack Underflow << endl;

exit (1); }

return ((*p).element[((*p).top)--]);

}

Returns the value of the element that is pointed at by the top.

base_type InfoStack (struct typestack *p)

{

if EmptyStack(p) { cout << Stack Underflow << endl;

exit (1); }

else return ((*p).element[(*p).top]);

}

Returns true if the stack is empty and false otherwise.

int EmptyStack(struct typestack *p)

{

if ( (*p).top == -1)

return (1);

else return (0);

}

Returns true if the stack is full and false otherwise.

int FullStack(struct typestack *p)

{

if ( (*p).top == MAXELEM-1)

return (1);

else return (0);

}

SOLVED EXERCISES

The exercises below are coded in the C++ high-level language using struct.

1. Implement a function that calculates and returns the sum of the stack integers.

Analysis:

Inputs: stack with integer elements.

Outputs: sum of the elements.

An implementation for this function could be:

int SumStack(struct typestack *p)

{ declaration of variables to use

int elem=0;

int s=0;

// Cycle where the element elem is removed

// from the stack to add it to the variable s

while (!EmptyStack(p))

{ elem=ElimStack(p);

s=s+elem;

}

// Returns the content of the variable s

return s;

}

Another implementation for this function could be:

int SumStack(struct typestack *p)

{ int s=0;

While (!EmptyStack(p))

s = s + ElimStack(p);

return (s);

}

2. Implement a function that verifies if two stacks are equal, without destroying their content.

Analysis:

Inputs: stack1, stack2.

Outputs: boolean value if stacks are equal or not.

An implementation for this function could be:

void EqualStacks( struct typestack *p1, struct typestack *p2)

{

int diferent=0;

while ((!EmptyStack(p1)) && (!diferent))

// Checks if the elements at the top of the stack are different

{ if (InfoStack(p1) != InfoStack(p2))

{ cout << Stacks are different ;

diferent = 1; }

// If the elements are equal it removes them from the stack

ElimStack(p1);

ElimStack(p2);

}

// If the stack reaches empty, verified all its elements returns 1

// indicating that the stacks are the same

if (diferent == 0)

cout << Stacks are the same ;

}

3. Implement a function that counts the occurrences of the elem element on the stack.

Analysis:

Inputs: stack, elem.

Outputs: number of occurrences of the element elem.

An implementation for this function could be:

int ContOccur(struct typestack *p, int elem)

{

// variable cont stores the number of occurrences of the element

// elem on the stack

int cont=0;

while (!EmptyStack(p))

// checks if the element at the top of the stack equals to the

// element elem

if (InfoStack(p)==elem)

// counting the number of occurrences of elem in the stack

{ cont+=1;

// and takes the elements from the stack

ElimStack(p); }

else ElimStack(p);

return cont;

}

4. Implement a replace function that has as arguments an integer element of a stack and two new and old integer values so that if the second value appears somewhere on the stack it will be replaced by the new one.

Analysis:

Inputs: stack of integers, new integer value, old one.

Outputs: stack with new value already replaced.

An implementation for this function could be:

struct typestack Replace (struct typestack *p, int nu, int old)

{

struct typestack q;

struct typestack r;

int aux;

CreateStack(&q);

CreateStack(&r);

// elements of p are removed and placed in q

// except in the case of removing old, which is inserted new

while (!EmptyStack(p))

{

aux=ElimStack(p);

if (aux == old)

AdicStack(&q,nu);

else AdicStack(&q,aux);

}

// the result is already in q but on the contrary

// therefore it only remains to empty q in r.

while (!EmptyStack(&q))

{

aux=ElimStack(&q);

AdicStack(&r,aux);

}

return r;

}

5. Implement a function to insert an integer element into an ascending ordered stack.

Analysis:

Inputs: ordered stack with integer elements.

Outputs: ordered stack with new integer element.

An implementation for this function could be:

struct typestack StackOrdered(struct typestack *stack, int value)

{

struct typestack paux;

int found =1;

int elem;

CreateStack(&paux);

// elements are removed from the stack and it is verified if it is greater than value

while ( found )

{

elem=ElimStack(stack);

// if elem is greater than the incoming value, elem gets into the auxiliary

// stack

if ( elem > value )

AdicStack(&paux,elem);

else { found=0;

// elem is added to the original stack and incoming value is added

// to the original stack remaining in order

AdicStack(stack,elem);

AdicStack(stack,value); }

}

// External cycle to return the elements of the auxiliary stack to the original stack

while ( ! EmptyStack(&paux) )

{ elem=ElimStack(&paux); // Pops the auxiliary stack

AdicStack(stack,elem); } // Does an elem push to the original stack

return (*stack);

}

6. Implement a mix(p.q) function that generates the stack resulting from stacking the elements of p and q alternately from their respective bottoms to the tops.

Analysis:

Inputs: p and q stacks with integer elements.

Otputs: stack with the mixture of the two input stacks.

An implementation for this function could be:

struct typestack Mixture(struct typestack *p, struct typestack *q)

{

struct typestack r;

struct typestack paux;

int valuep;

int valueq;

int value;

CreateStack(&r);

CreateStack(&paux);

// elements of p and q are removed and inserted

// alternatively in the paux auxiliary stack

while (!EmptyStack(p))

{

valuep=ElimStack(p); // ElimStack makes a pop

valueq=ElimStack(q);

AdicStack(&paux,valueq); // AdicStack makes a push

AdicStack(&paux,valuep);

}

// elements are passed from the auxiliary stack to the resulting stack r

while(!EmptyStack(&paux))

{

value=ElimStack(&paux);

AdicStack(&r,value);

}

// the resulting stack is returned r

return r;

}

7. Implement a function that multiplies the elements of the p and q stacks and accumulates the results on a third r stack. Print the original stacks and the resulting stack.

Analysis:

Inputs: p and q stacks with integer elements.

Outputs: stack r, with the result of multiplying the elements of the two stacks.

An implementation for this function could be:

struct typestack Mult(struct typestack *p, struct typestack *q)

{

typestack r, paux;

int value, valuep, valueq;

CreateStack(&r);

CreateStack(&paux);

// elements of p and q are removed and multiplied

// the result is saved in the paux auxiliary stack

while (!EmptyStack(p))

{ valuep=ElimStack(p); // ElimStack makes a pop

valueq=ElimStack(q);

AdicStack(&paux,valuep * valueq); // AdicStack makes a push

}

// elements are passed from the auxiliary stack to the resulting stack r

while (!EmptyStack(&paux))

{ value=ElimStack(&paux);

AdicStack(&r,value);

return r;

}

8. Implement a function that, given a stack and a threshold value, creates two other stacks, in one of which the values less than the threshold have been entered, and in the other one, the values greater than or equal to the threshold. The initial stack does not disappear.

Analysis:

Inputs: stack p with integer elements.

Outputs: stack1 with values less than threshold and stack2 with values greater than or equal to threshold.

An implementation for this function could be:

void SplitStack(struct tystack *p; int valueum)

{

typestack p1, p2;

int value;

CreateStack(&p1);

CreateStack(&p2);

// elements of p are taken out and compared with the threshold value

// if it is less it gets into stack p1 and if it is greater than or equal it gets into

// the p2 stack

while (!EmptyStack(p))

{ value=ElimStack(p);

if (value < valueum)

AdicStack(&p1,value);

else AdicStack(&p2,value);

}

// MosElem procedure prints the elements stored in the stack sent as A parameter

cout<< STACK 1; cout << \n; MosElem(&p1); cout << \n;

cout<< STACK 2 ; cout << \n; MosElem(&p2); cout << \n;

}

For the exercises presented below, do the cold run.

9.Implement a function that uses only two stacks of characters to decide whether or not a phrase is palindrome. A phrase is called a palindrome if the sequence of characters obtained by traversing it from left to right (ignoring blanks) is the same as if the traversal is done from right to left.

Analysis:

Inputs: character string.

Outputs: Print whether the word is palindrome or not.

An implementation for this function could be:

void palindrome(void)

{

char cade[50];

struct typestack p1;

CreateStack(&p1);

struct typestack p2;

CreateStack(&p2);

int x; char value; char value1, value2;

int count=0;

printf(Enter the character string:);

gets(cade);

// places the string read character by character on p1

// ignoring whites and zeros

for (x=0;x<=(strlen(cade));x++)

if ((cade[x]!=' ')&&(cade[x]!='\0'))

AdicStack(&p1,cade[x]);

// it takes the characters out of p1 and puts them in p2

// ignoring whites and zeros

while (!EmptyStack(&p1))

{

value=ElimStack(&p1);

if ((value!=' ')&&(value!='\0'))

AdicStack(&p2,value);

}

// places the string read character by character on p1

// ignoring whites and zeros

for (x=0;x<=(strlen(cade));x++)

if ((cade[x]!=' ')&&(cade[x]!='\0'))

AdicStack(&p1,cade[x]);

// takes character from p1 and stores it in value1

// takes character from p2 and stores it in value2

// compares value1 and value2 if they are different count is increased

// otherwise, conta remains at 0

while (!EmptyStack(&p1))

{ value1=ElimStack(&p1);

value2=ElimStack(&p2);

if (value1 != value2)

conta++;

}

// if counter is increased the phrase is not a palindrome

// otherwise it is a palindrome

if (conta) cout << IS NOT A PALINDROME ;

else cout << IS A PALINDROME ;

cout << \n;

}

10.Implement a function that decides if a succession of read characters contains, among other symbols, open and closed parentheses, braces and brackets, and if it is balanced with respect to them.

Analysis:

Inputs: character string.

Outputs: prints if the string is balanced in its symbols.

An implementation for this function could be:

void balanced (void)

{

const tam = 50; // tam is the size of the character string

char cade[tam];

int x; int Resp1; int Resp2; int Resp3;

struct tytestack paux;

for (x=0;x<=tam;x++)

cade[x]='\0';

cout << Enter the character string: ;

cin >> cade;

//***************************************************

// MANIPULATING THE CHARACTER STRING TO CHECK IF IT IS BALANCED

//***************************************************

// STEP 1: The character string is traced from left to right.

// STEP 2: Every time a left parenthesis is found it gets into the stack.

// STEP 3: Each time a right parenthesis is found, the content is reviewed

// from the stack. If it is empty then we will have found a