Ordered Linked List Project in C You are to write the code for an ordered linked
ID: 3569552 • Letter: O
Question
Ordered Linked List Project in C
You are to write the code for an ordered linked list module.
You will be supplied with six files: main.c, orderedList.h, orderedList.c, Makefile, input0 and correct0. The only file you should modify is orderedList.c.
In the file orderedList.c, you are to supply the code for the three functions whose prototypes are in orderedList.h. The file main.c uses two command line arguments to specify an input file name and an output file name. It is used to test your implementation of these functions. It reads a list of instructions from the input file, each of which is one of the following.
i n // insert value n into the list c // clear thelist
q // quit
For example, the contents of the file input0 are:
i 1
i 2
i 3
i 4
q
After each instruction, the contents of the list are printed to the output file. The contents of correct0 (the correct output for input input0) are
1
1 2
1 2 3
1 2 3 4
Contents of orderedList.h
#include
#include
typedef struct node {
int data;
struct node *next;
} Node;
Node *orderedInsert(Node *p, int newval);
/* Allocates a new Node with data value newval
and inserts into the ordered list with
first node pointer p in such a way that the
data values in the modified list are in
nondecreasing order as the list is traversed.
*/
void printList(FILE *outfile, Node *p);
/* Prints to outfile the data values in the list with
first node pointer p from first to last,
with a space between successive values.
Prints a newline at the end of the list.
*/
void clearList(Node **p);
/* Deletes all the nodes in the list with
first node pointer *p, resulting in *p
having value NULL. Note that we are passing
a pointer by address so we can modify that
pointer.
*/
Design of the orderedInsert function
Here is a step by step description of what you should do to insert an integer newval into an ordered linked list with first node pointer p:
1. Declare a Node pointer variable q, dynamically allocate a Node as the target of q and set the data value of the new node to newval.
2. If the list is empty or newval is less than or equal to the data value in the first node of the list, set the next pointer of q to the first node pointer (p) and return q.
3. Use a Node pointer tmp to traverse the list until it either reaches the last node or reaches a Node whose following node has data value greater than or equal to newval.
4. Insert the target of q after the target of tmp and return p (the original first node pointer).
this is the file OrderedList.c
#include "orderedList.h"
Node *orderedInsert(Node *p, int newval)
/* Allocates a new Node with data value newval
and inserts into the ordered list with
first node pointer p in such a way that the
data values in the modified list are in
nondecreasing order as the list is traversed.
*/
{
}
void printList(FILE *outfile, Node *p)
/* Prints the data values in the list with
first node pointer p from first to last,
with a space between successive values.
Prints a newline at the end of the list.
*/
{
}
void clearList(Node **p)
/* Deletes all the nodes in the list with
first node pointer *p, resulting in *p
having value NULL. Note that we are passing
a pointer by address so we can modify that
pointer.
*/
{
}
Explanation / Answer
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<stdlib.h>
#include<alloc.h>
void Push(int, node **);
void Display(node **);
int Pop(node **);
int Sempty(node *);
typedef struct stack {
int data;
struct stack *next;
} node;
void main() {
node *top;
int data, item, choice;
char ans, ch;
clrscr();
top = NULL;
printf(" Stack Using Linked List : nn");
do {
printf(" The main menu");
printf(" 1.Push 2.Pop 3.Display 4.Exit");
printf(" Enter Your Choice");
scanf("%d", &choice);
switch (choice) {
case 1:
printf(" Enter the data");
scanf("%d", &data);
Push(data, &top);
break;
case 2:
if (Sempty(top))
printf(" Stack underflow!");
else {
item = Pop(&top);
printf(" The popped node is%d", item);
}
break;
case 3:
Display(&top);
break;
case 4:
printf(" Do You want To Quit?(y/n)");
ch = getche();
if (ch == 'y')
exit(0);
else
break;
}
printf(" Do you want to continue?");
ans = getche();
getch();
clrscr();
} while (ans == 'Y' || ans == 'y');
getch();
}
void Push(int Item, node **top) {
node *New;
node * get_node(int);
New = get_node(Item);
New->next = *top;
*top = New;
}
node * get_node(int item) {
node * temp;
temp = (node *) malloc(sizeof(node));
if (temp == NULL)
printf(" Memory Cannot be allocated");
temp->data = item;
temp->next = NULL;
return (temp);
}
int Sempty(node *temp) {
if (temp == NULL)
return 1;
else
return 0;
}
int Pop(node **top) {
int item;
node *temp;
item = (*top)->data;
temp = *top;
*top = (*top)->next;
free(temp);
return (item);
}
void Display(node **head) {
node *temp;
temp = *head;
if (Sempty(temp))
printf(" The stack is empty!");
else {
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
getch();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<stdio.h>
#include<conio.h>
#include<process.h>
#include<stdlib.h>
#include<alloc.h>
void Push(int, node **);
void Display(node **);
int Pop(node **);
int Sempty(node *);
typedef struct stack {
int data;
struct stack *next;
} node;
void main() {
node *top;
int data, item, choice;
char ans, ch;
clrscr();
top = NULL;
printf(" Stack Using Linked List : nn");
do {
printf(" The main menu");
printf(" 1.Push 2.Pop 3.Display 4.Exit");
printf(" Enter Your Choice");
scanf("%d", &choice);
switch (choice) {
case 1:
printf(" Enter the data");
scanf("%d", &data);
Push(data, &top);
break;
case 2:
if (Sempty(top))
printf(" Stack underflow!");
else {
item = Pop(&top);
printf(" The popped node is%d", item);
}
break;
case 3:
Display(&top);
break;
case 4:
printf(" Do You want To Quit?(y/n)");
ch = getche();
if (ch == 'y')
exit(0);
else
break;
}
printf(" Do you want to continue?");
ans = getche();
getch();
clrscr();
} while (ans == 'Y' || ans == 'y');
getch();
}
void Push(int Item, node **top) {
node *New;
node * get_node(int);
New = get_node(Item);
New->next = *top;
*top = New;
}
node * get_node(int item) {
node * temp;
temp = (node *) malloc(sizeof(node));
if (temp == NULL)
printf(" Memory Cannot be allocated");
temp->data = item;
temp->next = NULL;
return (temp);
}
int Sempty(node *temp) {
if (temp == NULL)
return 1;
else
return 0;
}
int Pop(node **top) {
int item;
node *temp;
item = (*top)->data;
temp = *top;
*top = (*top)->next;
free(temp);
return (item);
}
void Display(node **head) {
node *temp;
temp = *head;
if (Sempty(temp))
printf(" The stack is empty!");
else {
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
}
getch();
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.