Step 1. Setting up Your Environment
Remote login to data
Change to the directory ~/cs240 that you created previously.
cd
cd cs240
Now copy the initial lab6 files by typing:
cp /homes/cs240/lab6-linkedlists/lab6-src.tar .
tar -xvf lab6-src.tar
cd lab6-src
Update
There’s a missing file that’s needed by test 10. Follow these instructions to copy it into your lab6 directory. Follow these instructions only if you have started working on lab6. If you haven’t downloaded the lab6-src.tar file yet, then, you may ignore this post as the new tar file already includes this file.
cd ~/cs240/lab6-src
cp /homes/cs240/lab6-linkedlists/table1.ll .
Step 2. Pointer Operations
See the following program ptr_simple.c1
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
int a;
int *p;
int b[20];
int main() {
a=5;
p=&a;
printf("a=5\n");
printf("p=&a\n");
printf("a=%d\n",a);
printf("&a=%ld\n",(long)&a);
printf("p=%ld\n",(long)p);
printf("&p=%ld\n",(long)&p);
printf("*p=%d\n",*p);
printf("\n");
p=&b[0];
printf("&b[0]=%ld\n",(long)&b[0]);
printf("p=%ld\n\n",(long)p);
p++;
printf("p++\n");
printf("&b[1]=%ld\n",(long)&b[1]);
printf("p=%ld\n\n",(long) p);
p++;
printf("p++\n");
printf("&b[2]=%ld\n",(long) &b[2]);
printf("p=%ld\n\n",(long)p);
}
Type “make” and run the program “/ptr-simple”
make
./ptr_simple
Examine the output line by line and see if the values of p in the output after incrementing are what you expect. The instructors will make sure that you have examined the code and the output. Be prepared to answer the instructor’s questions about the code.
Step 3. Using ddd to Debug a Simple List.
You are given a simple_list.c file that implements a simple linked list.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
// Simple list of integers
struct ListNode {
int value;
struct ListNode *next;
};
typedef struct ListNode ListNode;
struct ListNode *head = NULL;
void addFront(int val) {
// Create new node
ListNode * n = (ListNode *) malloc(sizeof(ListNode));
n->value = val;
// Add at the beginning of the list
n->next = head;
head = n;
}
void printList() {
// Traverse list ad print elements
printf("---List---\n");
ListNode * n = head;
while (n!=NULL) {
printf("%d\n", n->value);
n = n->next;
}
}
int main()
{
addFront(5);
addFront(6);
addFront(8);
addFront(1);
addFront(2);
printList();
}
The struct ListNode stores an integer value and has a pointer to the next node in the list. The variable “head” points to the first node in the list. addFront(int val) adds a new node to the front of the Linked List. The function printList traverses the list to print all the elements in the linked list.
Compile simple_list using “make” and run “ddd”.
make
ddd simple_list
Follow the video “Debugging Linked Lists in DDD”. This video is hosted in the blackboard website so you will need to type your Purdue user and password. If you have problems with this link login to blackboard directly and go to the class blackboard’s webpage. The video is also available there.
Set a breakpoint by selecting double click at the beginning of the list.
Step through each line in the code and double click in “head”. This will show the value of the head. Now point in the “next” address to show the next node in the list.
It is important that you do this tutorial and watch the video to be able to debug the linked lists operations you will implement later.
To show the line number in DDD press Edit->Preferences->Source and mark the checkbox “Display Source Line Numbers”.
Step 4. Implementing a Linked List of ints
The files LinkedList.h and LinkedList.c implement a linked list of ints. Complete the implementation of the functions indicated in LinkedList.c. Run testall to verify that your implementation is correct.
LinkedList.h1
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// Data structs for a list of ints
struct ListNode {
int value;
struct ListNode * next;
};
typedef struct ListNode ListNode;
struct LinkedList {
ListNode * head;
};
typedef struct LinkedList LinkedList;
void llist_init(LinkedList * list);
void llist_print(LinkedList * list);
void llist_add(LinkedList * list, int value);
int llist_exists(LinkedList * list, int value);
int llist_remove(LinkedList * list, int value);
int llist_get_ith(LinkedList * list, int ith, int *value);
int llist_remove_ith(LinkedList * list, int ith);
int llist_number_elements(LinkedList * list);
int llist_save(LinkedList * list, char * file_name);
int llist_read(LinkedList * list, char * file_name);
void llist_sort(LinkedList * list, int ascending);
void llist_clear(LinkedList *list);
int llist_remove_first(LinkedList * list, int * value);
int llist_remove_last(LinkedList * list, int * value);
void llist_insert_first(LinkedList * list, int value);
void llist_insert_last(LinkedList * list, int value);
LinkedList.c1
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
//
// Initialize a linked list
//
void llist_init(LinkedList * list)
{
list->head = NULL;
}
//
// It prints the elements in the list in the form:
// 4, 6, 2, 3, 8,7
//
void llist_print(LinkedList * list) {
ListNode * e;
if (list->head == NULL) {
printf("{EMPTY}\n");
return;
}
printf("{");
e = list->head;
while (e != NULL) {
printf("%d", e->value);
e = e->next;
if (e!=NULL) {
printf(", ");
}
}
printf("}\n");
}
//
// Appends a new node with this value at the beginning of the list
//
void llist_add(LinkedList * list, int value) {
// Create new node
ListNode * n = (ListNode *) malloc(sizeof(ListNode));
n->value = value;
// Add at the beginning of the list
n->next = list->head;
list->head = n;
}
//
// Returns true if the value exists in the list.
//
int llist_exists(LinkedList * list, int value) {
return 0;
}
//
// It removes the entry with that value in the list.
//
int llist_remove(LinkedList * list, int value) {
return 1;
}
Step 5. Turning In your Project
Follow these instructions to turn in lab6:
cd cs240
turnin -c cs240 -v -p lab6 lab6-src