DSA Digital Assignment-1
Question 1:
AIM:
To implement a program to reverse the given string us-
ing Stack (Implement it using linked list) and get re-
quired output.
ALGORITHM/PSEUDO CODE:
1]Define a node structure with a character value and a next pointer
structure node:
char value
node pointer next
2] Define a stack type as a pointer to node
typedef node pointer stack
3] Initialize a new stack by setting the top pointer to NULL
procedure newstack(reference to stack top):
top = NULL
4]Pop a value from the stack and return it
procedure pop_ll(reference to stack top) returns char:
if top is not NULL:
char temp = top.value
node pointer p = top
top = top.next
free p
return temp
end if
5] Push a value onto the stack
procedure push_ll(reference to stack top, char a):
node pointer f = allocate memory for node
f.value = a
f.next = top
top = f
6]Main procedure
procedure main:
stack s1
char array a = "hello"
int len = length of array a - 1
call newstack(s1)
for int i = 0 to len - 1:
call push_ll(s1, a[i])
end for
while s1 is not NULL:
char c = call pop_ll(s1)
print c
end while
return 0
CODE /OUTPUT:
#include <stdio.h>
#include <stdlib.h>
struct node {
char value;
struct node *next;
};
typedef struct node stack;
void newstack(stack **top) {
*top = NULL;
}
char pop_ll(stack **top) {
char temp;
stack *p;
temp = (*top)->value;
p = *top;
*top = (*top)->next;
free(p);
return temp;
}
void push_ll(stack **top, char a) {
stack *f = (stack *)malloc(sizeof(stack));
f->value = a;
f->next = *top;
*top = f;
}
int main() {
stack *s1;
char a[] = "hello";
int len = sizeof(a) / sizeof(a[0]) - 1;
newstack(&s1);
for (int i = 0; i < len; i++) {
push_ll(&s1, a[i]);
}
while (s1 != NULL) {
printf("%c\n", pop_ll(&s1));
}
return 0;
}
Question 2:
AIM:
To implement a data structure to keep student’s details
in the order of their total mark. If two students have
same mark then keep their details in the order of entry
time. The student’s details include students name, reg.
number, and total mark.
ALGORITHM/PSEUDO CODE:
1]Define a student structure with name, roll number, total marks,
and next pointer
structure student:
char name[50]
int rnum
int tmark
student pointer next
2]Create a new student node with the given name, roll number, and
total marks
procedure creat(char name[], int rnum, int tmark) returns student
pointer:
allocate memory for new student node as newstd
if memory allocation fails:
print "Memory allocation failed"
exit program
copy name to newstd->name
set newstd->rnum to rnum
set newstd->tmark to tmark
set newstd->next to NULL
return newstd
3]Insert a new student node into the linked list in descending order
of total marks
procedure insertstd(reference to student pointer head, char name[],
int rnum, int tmark):
newstd = call creat(name, rnum, tmark)
if head is NULL or head->tmark < tmark:
set newstd->next to head
set head to newstd
else:
set current to head
while current->next is not NULL and current->next->tmark >=
tmark:
set current to current->next
set newstd->next to current->next
set current->next to newstd
4]Remove the first student node from the linked list
procedure removestd(reference to student pointer head):
if head is NULL:
print "List is empty"
return
temp = head
set head to head->next
print "Removed: " + temp->name + " " + temp->rnum + " " +
temp->tmark
free temp
5]Main procedure
procedure main:
student pointer head = NULL
call insertstd(head, "Vish", 100, 500)
call insertstd(head, "Vans", 101, 550)
call insertstd(head, "Bins", 121, 600)
call insertstd(head, "Rom", 122, 500)
call removestd(head)
call removestd(head)
call removestd(head)
call removestd(head)
call removestd(head)
return 0
CODE /OUTPUT:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct student {
char name[50];
int rnum;
int tmark;
struct student *next;
} student;
student* creat(char name[], int rnum, int tmark) {
student *newstd = (student *)malloc(sizeof(student));
if (newstd == NULL) {
printf("Memory allocation failed\n");
exit(-1);
}
strcpy(newstd->name, name);
newstd->rnum = rnum;
newstd->tmark = tmark;
newstd->next = NULL;
return newstd;
}
void insertstd(student **head, char name[], int rnum, int tmark) {
student *newstd = creat(name, rnum, tmark);
if (*head == NULL || (*head)->tmark < tmark) {
newstd->next = *head;
*head = newstd;
} else {
student *current = *head;
while (current->next != NULL && current->next->tmark >= tmark)
{
current = current->next;
}
newstd->next = current->next;
current->next = newstd;
}
}
void removestd(student **head) {
if (*head == NULL) {
printf("List is empty\n");
return;
}
student *temp = *head;
*head = (*head)->next;
printf("Removed: %s %d %d\n", temp->name, temp->rnum, temp-
>tmark);
free(temp);
}
int main() {
student *head = NULL;
insertstd(&head, "Vish", 100, 500);
insertstd(&head, "Vans", 101, 550);
insertstd(&head, "Bins", 121, 600);
insertstd(&head, "Rom", 122, 500);
removestd(&head);
removestd(&head);
removestd(&head);
removestd(&head);
removestd(&head);
return 0;
}
