312 Intermediate C Programming
{112
Node * arr2 = NULL ;113
while ( arr != NULL )114
{115
arr2 = List_i nsert ( arr2 , arr -> index , arr -> value );116
arr = arr -> next ;117
}118
return arr2 ;119
}120
Below is a sample main function that we can use to test our implementation.
// main . c1
#in clude < stdio .h >2
#in clude < stdlib .h >3
#in clude " sparse .h "4
int main ( i n t argc , char ** argv )5
{6
i f ( argc != 4)7
{8
return EXIT _FAILUR E ;9
}10
Node * arr1 = List_rea d ( argv [1]) ;11
i f ( arr1 == NULL )12
{13
return EXIT _FAILUR E ;14
}15
Node * arr2 = List_rea d ( argv [2]) ;16
i f ( arr2 == NULL )17
{18
List_ destroy ( arr2 );19
return EXIT _FAILUR E ;20
}21
Node * arr3 = List_ m erge ( arr1 , arr2 );22
int ret = List_save ( argv [3] , arr3 );23
List_ destroy ( arr1 );24
List_ destroy ( arr2 );25
List_ destroy ( arr3 );26
i f ( ret == 0)27
{28
return EXIT _FAILUR E ;29
}30
return EXIT _SUCCES S ;31
}32
Here is a Makefile that combines the compiling and testing.
GCC = gcc1
CFLAGS = -g - Wall - Wshadow2
LIBS =3
SOURCES = sparse . c main . c4
TARGET = main5
VALGRIND = valgrind -- tool = memc h eck -- verbose --log - file6
Programming Problems Using Linked List 313
TEST0 = inputs / input0A inputs / i n p u t 0 B outputs / output07
TEST1 = inputs / input1A inputs / i n p u t 1 B outputs / output18
9
main : $ ( SOURCES )10
$( GCC ) $ ( CFLAGS ) $( SOURCES ) -o $@11
./ main $( TEST0 )12
diff -w outputs / output0 expected / expecte d 013
./ main $( TEST1 )14
diff -w outputs / output1 expected / expecte d 115
$( VALGRIND )= outputs / valg rindlog 0 ./ main $( TEST0 )16
$( VALGRIND )= outputs / valg rindlog 1 ./ main $( TEST1 )17
18
clean :19
/ bin / rm -f main outputs /*20
Let’s assume that we have inputs input0A and input0B as shown below. The expected0
column shows the result of merging the two arrays.
input0A:
76 16151
115 -19702
164 2813
495 8834
912 1165
1124 4586
1396 707
1468 -11008
1777 17729
2064 209310
2333 -116311
2418 -168312
2943 -207813
3545 -53814
3678 -226015
3700 -13116
3708 -159617
3933 205018
4031 -40819
4287 -72820
4363 224421
4857 -229322
4951 -173723
input0B:
1502 17941
2545 -13872
2872 20353
3133 23394
3164 -13735
4218 7136
4934 -15397
expected0:
76 16151
115 -19702
164 2813
495 8834
912 1165
1124 4586
1396 707
1468 -11008
1502 17949
1777 177210
2064 209311
2333 -116312
2418 -168313
2545 -138714
2872 203515
2943 -207816
3133 233917
3164 -137318
3545 -53819
3678 -226020
3700 -13121
3708 -159622
3933 205023
4031 -40824
4218 71325
4287 -72826
4363 224427
4857 -229328
4934 -153929
4951 -173730
314 Intermediate C Programming
Below is a second set of sample inputs and outputs. Some elements (indexes = 54 and
4019) are eliminated in the output because the values add to zero.
input1A:
1769 -11211
1859 21702
4879 -24403
1994 9114
3123 21695
4441 7846
54 -11857
4735 23508
4931 14549
3811 208810
4019 122711
input1B:
54 11851
2328 -24732
2379 22073
886 -6424
1765 -16945
2226 -15426
3103 -7007
2304 23248
2308 -3699
4019 -122710
expected1:
886 -6421
1765 -16942
1769 -11213
1859 21704
1994 9115
2226 -15426
2304 23247
2308 -3698
2328 -24739
2379 220710
3103 -70011
3123 216912
3811 208813
4441 78414
4735 235015
4879 -244016
4931 145417
19.4 Reversing a Linked List
This program asks you to write a function that reverses a linked list by reversing the
individual links between the nodes. The function’s input argument is the head of the linked
list and returns the head of the reversed linked list. This function should not call malloc
directly or indirectly (i.e., calling another function that calls malloc), because it is unnec-
essary and slow.
Node * List_ reverse ( Node * head );1
Fig. 19.1 shows an example list and its reversed form.
(a)
(b)
FIGURE 19.1: (a) The original linked list. The list’s head points to A. (b) The reversed
linked list. The list’s head points to E.
Programming Problems Using Linked List 315
Fig. 19.2 shows how to reverse a linked list. Suppose the first two nodes have already
been reversed: revhead points to the head of the partially reversed list; orighead points to
the head of the remaining original list; origsec points to the second node of the remaining
list.
(a)
(b)
(c)
(d)
(e)
FIGURE 19.2: (a) Three pointers are used. (b) Change orighead -> next and make it
point to revhead. (c) Update revhead to the new head of the reversed list. (d) Update
orighead to the new head of the remaining list. (e) Update origsec to the second node of
the remaining list.
Below is a sample implementation that reverses a linked list as desired. It essentially
implements the four steps depicted in the figure.
Node * List_ reverse ( Node * head )1
{2
i f ( head == NULL )3
{4
// empty list , nothing to do5
return NULL ;6
}7
Node * orighead = head ;8
Node * revhead = NULL ; // must initia l ize to NULL9
Node * origsec ; // will be assigned before using10
while ( orighead != NULL )11
316 Intermediate C Programming
{12
origsec = o r ig head -> next ;13
orighead -> next = revhead ;14
revhead = o r ig head ;15
orighead = origsec ;16
}17
return revhead ;18
}19
The order of the four steps inside while is important. It would be wrong if the order
were different. For example, reversing lines 13 and 14 would lose the remaining list because
orighead -> head has already been changed and origsec is the same as revhead. Re-
member to initialize revhead to NULL because it will be the end of the reversed list. It is
unnecessary to initialize origsec because it is orighead -> next before it is used.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.