/*

This program demonstrates how a very simple linked list would work.

First, we will have the user input the initial list, which we will

sort. After sorting, we will initialize the links, which means

simply that we will store information in each record about where

the next record is. Finally, we will demonstrate how you would

update the list, adding new records at the end, but effectively

inserting them into the list at the right point just by changing

the links of the old records.

*/

#include<stdio.h>

#include<stdlib.h>

#define MAXSTUDENTS 50

void id_swap(long int *k, long int *l)

{

long int temp;

temp = *k;

*k = *l;

*l = temp;

}

void grade_swap(int *grade1, int *grade2)

{

int temp;

temp = *grade1;

*grade1 = *grade2;

*grade2 = temp;

}

void bsort2( long int id[], int grade[], int n)

{

int last, k, i, kk;

printf("Sorting\n");

last = n - 1;

do {

k = 0;

for (i = 1; i <= last; i++) {

if (id[i - 1] > id[i]) {

id_swap(&id[i - 1], &id[i]);

grade_swap(&grade[i - 1], &grade[i]);

k = i;

}

}

last = k;

} while (k != 0);

}

long int linear(long int list[], long int key, int n){

/* This is just the linear search function with no alterations */

int i, flag;

flag = -2;

for( i=0; i<n; i++){

if( list[i] == key ){

flag = i;

break;

}

}

return(flag);

}

void print_list(long int id[], int grade[], long int next[], int first)

{

int i, new;

printf("first =%d\n",first);

i = 1;

printf("\nElement# %d ID# %ld Grade- %d\n", i, id[first], grade[first]);

new = first;

while(next[new] >= 0){

i++;

new = next[new];

printf("Element# %d ID# %ld Grade- %d\n", i, id[new], grade[new]);

}

}

main(){

long int id[MAXSTUDENTS], key, temp_id, next[MAXSTUDENTS], first, last,

lastrecord;

int i, n, flag, reply, grade[MAXSTUDENTS], temp_grade;

do{

printf("How many students? ( <%4d) \n",MAXSTUDENTS);

scanf("%d",&n);

}while( n>MAXSTUDENTS );

printf("Enter students' names and ID #'s\n");

printf("in this format ->ID:9421234[ENTER] (no spaces)\n");

printf(" ->Grade:49[ENTER]\n");

for( i=0; i<n; i++){

printf("Student #%d:\n",i+1);

printf("ID #:");

scanf("%ld",&id[i]);

printf("Grade:");

scanf("%d",&grade[i]);

}

/* We will sort the initial list using the improved bubble sort */

bsort2( id, grade, n );

/* Now, we will initialize the links */

/* The last record has a null link (-1) */

for(i=0; i < (n-1); i++)

next[i] = i+1;

next[n-1] = -1;

first = 0;

print_list( id, grade, next, first );

printf("Ready to add new records to the list.\n\n");

do{

printf("Enter 0 for front of list, 1 for back of list : ");

scanf("%d",&reply);

last = linear( next, -1, MAXSTUDENTS );

lastrecord = last;

if(last == -2){

printf("ERROR- could not find end of list\n\n\n");

break;

}

printf("\nlast = %d\n\n",last);

printf("Enter student's name and ID #\n");

printf("in this format ->ID:9421234[ENTER] (no spaces)\n");

printf(" ->Grade:49[ENTER]\n");

printf("ID #:");

scanf("%ld",&id[last+1]);

printf("Grade:");

scanf("%d",&grade[last+1]);

printf("Reply = %d", reply);

if(reply == 0){

printf("Adding record to the front of the list\n");

lastrecord = lastrecord + 1;

next[lastrecord] = first;

first = lastrecord;

print_list( id, grade, next, first );

}

if(reply == 1){

printf("Adding record to the back of the list\n");

lastrecord = lastrecord + 1;

next[lastrecord] = -1;

next[last] = lastrecord;

last = lastrecord;

print_list( id, grade, next, first );

printf("This is back end! first= %ld",first);

}

printf("Add another (0 for no, 1 for yes)?\n");

scanf("%d",&reply);

}while( reply == 1 );

}

/* End of main program linked.c */

/*

Input :

8

9611684 67

9613986 65

9412978 72

9613693 73

9515010 82

9510633 71

9513221 69

0000000 00

1

0 0

0

Output :

How many students? ( < 50)

Enter students' names and ID #'s

in this format ->ID:9421234[ENTER] (no spaces)

->Grade:49[ENTER]

Student #1:

ID #:9611684

Grade:67

Student #2:

ID #:9613986

Grade:65

Student #3:

ID #:9412978

Grade:72

Student #4:

ID #:9613693

Grade:73

Student #5:

ID #:9515010

Grade:82

Student #6:

ID #:9510633

Grade:71

Student #7:

ID #:9513221

Grade:69

Student #8:

ID #:0000000

Grade:00

Sorting

first =0

Element# 1 ID# 0 Grade- 0

Element# 2 ID# 9412978 Grade- 72

Element# 3 ID# 9510633 Grade- 71

Element# 4 ID# 9513221 Grade- 69

Element# 5 ID# 9515010 Grade- 82

Element# 6 ID# 9611684 Grade- 67

Element# 7 ID# 9613693 Grade- 73

Element# 8 ID# 9613986 Grade- 65

Ready to add new records to the list.

Enter 0 for front of list, 1 for back of list : 1

last = 7

Enter student's name and ID #

in this format ->ID:9421234[ENTER] (no spaces)

->Grade:49[ENTER]

ID #:0

Grade:0

Reply = 1

Adding record to the back of the list

first =0

Element# 1 ID# 0 Grade- 0

Element# 2 ID# 9412978 Grade- 72

Element# 3 ID# 9510633 Grade- 71

Element# 4 ID# 9513221 Grade- 69

Element# 5 ID# 9515010 Grade- 82

Element# 6 ID# 9611684 Grade- 67

Element# 7 ID# 9613693 Grade- 73

Element# 8 ID# 9613986 Grade- 65

Element# 9 ID# 0 Grade- 0

This is back end! first= 0

Add another (0 for no, 1 for yes)?0

*/