Data Structures Exercises Dr$.$ Bellehsen

Spring $2024$

C$++$

struct node or class node

$\{$

int value; $//$ value of a list element

node $*$ next; $//$ link to the next node in the list

$\}$;

Java

class Node

$\{$

int value;

Node next;

Node$($int val, Node n$)$

$\{$

value $=$ val;

next $=$ n;

$\}$

Node$($int val$)$

$\{$

value $=$ val;

next $=$ null;

$\}$

$\}$

$1.$ Write a program that traverses a linked list and prints the contents of the value field. Assume that the linked list is defined as follows:

a$.$ Using a for loop

b$.$ Using a while loop

$2.$ Write a program that uses a for loop to find the sum of all contents of the value fields stored in a linked list sums. Label the three nodes a$,$ b$,$ c where a$.$value $=3\mathrm{.}5,$ b$.$value $=4\mathrm{.}5,$ and d$.$value $=9\mathrm{.}9$

$3.$ Rewrite the last program to add node c to the above list sums. This node should be inserted between b and d$.$ It contains the value $6\mathrm{.}2.$

$4.$ Write the statement to delete node b from the above list sums.

$5.$ Write a program that contains a doubly$-$linked list and features three nodes n$1,$ n$2,$ and n$3,$ a pointer named ptr$,$ which points to n$1($the first node$),$ and a do$-$while loop that prints out the value stored in each node. The structure of each node consists of a value of type int and two pointers named prior and next. The contents of the value members are $50,60,$ and $70$ respectively.

$6.$ We want to sort three values in a linked list. Create a linked list of nodes having the structure

struct node class Node

$\{\{$

int info; double value;

node$*$ link; Node next;

$\}$; $\}$

Write a program to sort the list. Do not move the values in info, but change the pointers in link.

The algorithm to sort is basically:

Given list of values n$1,$ n$2$ and n$3$:

a$.$ if n$1>$n$2,$ swap n$1$ and n$2$

b$.$ if n$1($after swap$)>$ n$3,$ swap n$1$ and n$3$

c$.$ if n$2>$ n$3($after swap$),$ swap n$2$ and n$3$

$7.$ Smiley Pharmaceutical, Inc. needs a program that sorts customers by account number. Write a program that accepts customer names and account numbers and sorts the account numbers in ascending order. Be sure to include the following:

$$ Declare a node structure that holds data for the customer name and account number $($Cinfo$),$ then the list Clist.

$$ On the first entry, prompt the user for account number and name. Allocate storage using head $=$ new Clist; and store each entry in the correct node member. Set the pointer to NULL.

$$ On subsequent entries, prompt the user to type an account number or $999$ to quit. Allocate storage using temp $=$ new Clist;

If the user does not type $999,$ call search for comparison with the previous account number entries.

$$ If a match is found in search, indicate that the input is a duplicate. Otherwise, set the next pointer to NULL.

$$ Set the head and tail to the variables p and q$.$

$$ Use a while loop to traverse the linked list to see whether the new entry is larger than previous entries.

$$ Use nested if and else statements to insert the new entry in the proper position in the list.

$$ Write the search function to see whether the account number has already been entered.

$$ Write a printlist function that allows you to print the customer list.