Simulate a linear linked-list by an array Let L be a linear linked list. We will

Question

Simulate a linear linked-list by an array

Let L be a linear linked list. We will use array A to represent L. Your task is to write a C++ program that simulates operations on L by using A, and outputs results.

The following is an example snapshot of L and A at some given time:

struct node {

   int data;

   int next;

};

struct node A[100] ;

ASSUME THAT THE LIST DOES NOT CONTAIN MORE THAN 100 ELEMENTS, AND ALL ELEMENTS IN THE LIST ARE DISTINCT

Again, we assume that each node in L contains a distinct data value

Do the following operations on A:

HERE WE IMAGINE OPERATIONS ON L, BUT ACTUALLY DO THEM ON A

NEVER USE A[0]

THE next field in A[i] GIVES YOU THE SUCCESSOR NODE

YOU MAY USE ADDITIONAL VARIABLES FOR HEAD AND LAST NODES

YOU MAY USE -1 IN THE NEXT FIELD TO MARK THE FREE CELLS IN A, AND WHEN YOU NEED A CELL FOR NEW NODE YOU CAN USE THESE FREE CELLS

A y : Create a new node with data value y, and append this node to L

I x y : Find the node t with value x, create a new node p with data value y, and insert node p after t in L

D y : Find the node with data value y, and delete that node from L

P: Double (multiply by two) all existing values (not indices) in nodes of L.

R : Reverse L

T : Output all data values in L

Sample Input/Output:

A 5

A 1

I 5 4

I 1 9

A 7

I 9 8

D 9

D 8

T

5 4 1 7

R

T

7 1 4 5

P

T

14 2 8 10

head L: A: 0 never used 2 1 5 2 4 3 3 1 4 4 7 0 5 assigned 7 0

Explanation / Answer

#include #include using namespace std; struct node { int data; int prev; int next; // Constructor: node() { data = -1; prev = -1; next = -1; } }; node A[100]; // Array of nodes used to simulate the linked list int slot = 1; // Array index of the next free space (beginning from index 1 initially) int head = -1; // Array index of the starting element in the list (-1 implies no entries yet) int tail = -1; // Array index of the tail in the list int elements = 0; // Number of elements in the list // Function prototypes: void insert(int); void insertAfter(int,int); void deleteElement(int); void reverse(); void print(); int findIndex(int); int main() { int a, b; char c; cout > c; switch(c) { case 'A': cin >> a; insert(a); break; case 'I': cin >> a >> b; insertAfter(a,b); break; case 'D': cin >> a; deleteElement(a); break; case 'R': reverse(); cout

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---