! PROGRAM P106 ! ! ! CLASS LIST UPDATE PROGRAM ! USES LINKED LIST WITH THE NAME AS THE KEY ! ! DECLARATION STATEMENTS ! IMPLICIT NONE CHARACTER (LEN=25) :: NAMES(100),NAME INTEGER :: ID(100),MARKS(100,7),GRADES(7),LINK(100) INTEGER :: TOP,LAST,I,J,K,NREC,NLINES,M,KPOS INTERFACE SUBROUTINE LOOK(LIST,LINK,NAME,KPOS,TOP,LAST) IMPLICIT NONE CHARACTER (LEN=25) :: LIST(:),NAME INTEGER ,INTENT(IN OUT) :: LINK(:),KPOS,LAST END SUBROUTINE LOOK END INTERFACE ! PRINT *, 'This is Program >> P106 = Linked Lists' ! ! Tell program where data for READ* is coming from OPEN(UNIT=5, FILE='P106.DAT') ! UNIT=5 is the default input ! TOP=1 ! !=== READ CURRENT STATE OF FILE ! L1: DO J=1,100 READ 15, ID(J),NAMES(J),(MARKS(J,K),K=1,7) 15 FORMAT(I7,' ',A25,7I3) IF (ID(J) == 0) GOTO 101 Print 15, ID(J),NAMES(J),(MARKS(J,K),K=1,7) ! SETUP POINTER TO NEXT RECORD LINK(J)=J+1 END DO L1 PRINT 16 16 FORMAT(/'TOO MUCH DATA FOR DEFINED ARRAYS'/ &'INCREASE ARRAY SIZE AND RERUN'//) STOP 101 NREC=J-1 ! !==== MARK THE LAST RECORD AS END OF THE FILE ! WITH A ZERO IN THE LINK FIELD ! LINK(NREC)=0 ! PRINT 102,NREC 102 FORMAT(/'CLASS LIST UPDATE PROGRAM'/ &I5,' RECORDS ON FILE') L2: DO J=1,100 READ(5,15) KID,NAME,GRADES IF (KID == 0) THEN PRINT 202,J-1 202 FORMAT(/I5,' UPDATES PROCESSED'// &'UPDATED CLASS LIST') ! !===== PRINT OUT A LINKED LIST - IT'S EASY ! START AT THE TOP OF THE LIST AND FOLLOW THE POINTERS ! UNTIL YOU HIT A ZERO POINTER ! K=TOP NLINES=0 210 PRINT 211,ID(K),NAMES(K),(MARKS(K,L),L=1,7) 211 FORMAT(I9,' ',A25,7I5) NLINES=NLINES+1 ! !=== LEAVE A BLANK LINE EVERY FIVE LINES OF OUTPUT ! IF (MOD(NLINES,5) == 0) PRINT * IF(LINK(K) == 0) STOP K=LINK(K) GO TO 210 ELSE CALL LOOK(NAMES,LINK,NAME,KPOS,TOP,LAST) IF (KPOS <= 0) THEN ! !==== PROGRAM SECTION TO ADD A NEW MEMBER TO CLASS LIST ! INSERT RECORD AT THE END OF THE FILE ! WHERE THE FREE SPACE IS, BUT LINK IN CORRECT ORDER ! NREC=NREC+1 IF(NREC > 100) THEN PRINT 220,KID,NAME 220 FORMAT(/'ARRAYS FULL - UNABLE TO ADD',I10,2X,A25) STOP ENDIF !===== NOW ADD NEW DATA IN EMPTY SLOT AT END OF FILE ID(NREC)=KID NAMES(NREC)=NAME L3: DO M=1,7 MARKS(NREC,M)=GRADES(M) END DO L3 KPOS=-KPOS LINK(NREC)=KPOS IF(LAST == 0) THEN ! !=== HAVE AN ADDITION IN FRONT OF FIRST RECORD ! TOP=NREC ELSE LINK(LAST)=NREC END IF ! !==== STUDENT FOUND - UPDATE ANY NONZERO GRADES ! ELSE L4: DO I=1,7 IF (GRADES(I) /= 0) THEN MARKS(KPOS,I)=GRADES(I) ENDIF END DO L4 ENDIF ENDIF END DO L2 STOP END PROGRAM P106 ! SUBROUTINE LOOK(LIST,LINK,NAME,KPOS,TOP,LAST) IMPLICIT NONE CHARACTER (LEN=25) :: LIST(:),NAME INTEGER ,INTENT(IN OUT) :: LINK(:),KPOS,LAST INTEGER :: NEXT ! ! LINKED LIST LOOKUP ROUTINE ! NEXT=TOP LAST=0 1 IF(LIST(NEXT) == NAME) THEN !=== YES WE FOUND THE ONE WE WANT AND KPOS IS ITS POSITION KPOS=NEXT RETURN ELSE IF(NAME < LIST(NEXT)) THEN !=== THE ONE WE WANT IS NOT IN LIST - KPOS POINT TO NEXT ONE ! NEGATIVE KPOS SAYS WE CAN'T FIND IT KPOS=-NEXT RETURN ENDIF ENDIF ! REMEMBER PREVIOUS POINTER VALUE LAST=NEXT IF(LINK(NEXT) == 0) THEN !=== WE HAVE REACHED END OF LIST AND STILL NOT FOUND THE ONE KPOS=0 RETURN ELSE !=== HAVE NOT FOUND IT YET ! POINT TO NEXT ONE NEXT=LINK(NEXT) GO TO 1 ENDIF RETURN END SUBROUTINE LOOK
/* 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 0OUTPUT :
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 */
{$G256} {$P512} {D+} PROGRAM p106 (input, output); TYPE char_array = ARRAY[1..25] OF CHAR; cell = RECORD name : char_array; marks : ARRAY[1..7] OF INTEGER; id : REAL; next : INTEGER END; linked_list = ARRAY[1..100] OF cell; VAR top, i, j, k, m, last, lines, position, records : INTEGER; kid : REAL; list : linked_list; grades : ARRAY[1..7] OF INTEGER; alias : char_array; PROCEDURE look ( VAR list : linked_list; VAR position : INTEGER; alias : char_array ); VAR link : INTEGER; BEGIN link := top; last := 0; WHILE ( ( list[link].name < alias ) AND ( link <> 0 ) ) DO BEGIN last := link; link := list[link].next END; IF ( link = 0 ) THEN { We have reached the end of the list, and not found the one we want } position := 0 ELSE IF ( list[link].name = alias ) THEN { Yes, we have found the one we want } position := link ELSE IF ( list[link].name > alias ) THEN { The one we want is not in the list - position points to the next one, negative position says we can't find it } position := -link END; BEGIN top := 1; j := 0; REPEAT j := j + 1; WITH list[j] DO BEGIN read ( id, name ); FOR k := 1 TO 7 DO read ( marks[k] ); readln; next := j + 1 END UNTIL ( ( j >= 100 ) OR ( list[j].id = 0 ) ); IF ( ( j >= 100 ) AND ( list[j].id <> 0 ) ) THEN BEGIN writeln; writeln ( 'Too much data for defined arrays'); writeln ( 'increase array size and rerun'); writeln END ELSE BEGIN records := j - 1; { Mark the last record as the end of the file with a zero in the next field } list[records].next := 0; writeln; writeln ( ^l ); writeln ( ' Class list update program'); writeln; writeln ( records:5, ' records on file' ); writeln; REPEAT read ( kid, alias ); FOR m := 1 TO 7 DO read ( grades[m] ); readln; IF ( kid <> 0 ) THEN BEGIN look ( list, position, alias ); IF ( position <= 0 ) THEN BEGIN { Program section to add a new member to class list Insert record at the end of the file where the free space is, link in correct order } records := records + 1; IF ( records <= 100 ) THEN { Now add new data at empty slot at end of file } BEGIN WITH list[records] DO BEGIN id := kid; name := alias; FOR m := 1 TO 7 DO marks[m] := grades[m]; position := -position; next := position END; { end with } IF ( last = 0 ) THEN { Have an addition in front of first record } top := records ELSE list[last].next := records END { end if } END { end if } ELSE FOR i := 1 TO 7 DO IF ( grades[i] <> 0 ) THEN list[position].marks[i] := grades[i] END { end if } UNTIL ( ( records > 100 ) OR ( kid = 0 ) ); writeln ( ( j - 1 ):5, ' updates processed' ); writeln ( ^l ); writeln ( 'Updated class list' ); writeln; { Print out a linked list, - it's easy Start at the top of the list, and follow the pointers until you hit a zero pointer } k := top; lines := 0; WHILE ( k <> 0 ) DO WITH list[k] DO BEGIN write ( id:9:0, ' ':2, name ); FOR m := 1 TO 7 DO write ( marks[m]:5 ); writeln; lines := lines + 1; IF ( ( lines MOD 5 ) = 0 ) THEN writeln; k := next END { end with } END { end else } END.DATA :
7611864 Brande, Bernardo 14 0 16 16 15 0 67 7613986 Burke, Christina 12 13 13 14 13 31 65 7412978 Colmenro, Jimi 14 15 16 16 17 42 72 7613693 Lauzier, Guy 15 15 14 16 17 35 73 7515010 Lim, Leong 17 16 18 17 17 44 82 7510633 Nguy, Gulliver 11 13 13 14 14 45 71 7513221 Talko, Stephen 12 14 14 14 14 39 69 0000000 Dummy 0 0 0 0 0 0 0 7510633 Nguy, Gulliver 0 0 0 0 19 0 0 7415795 Smith, John 11 12 0 0 0 0 0 7611684 Brande, Bernardo 0 17 0 0 0 35 0 9999999 Zylinski, Zarro 0 0 0 0 0 0 99 1111111 Aardvark, Andrew 0 0 0 0 0 41 0 0000000 Dummy 0 0 0 0 0 0 0
Last modified: 08/07/97