2 C Problems involving linked lists(executed and tested in Linux)
Microsoft Word - Linked list (needs more problems).docx INSTRUCTIONS: For each problem, submit: 1) Your program, and 2) one or two screenshots in jpg format showing that your program really works (only include the executions, no need to include the gcc compilation in the screenshots). You must submit C programs (not C++, java, etc), which can be compiled using gcc on the virtual machine used in the course. Also, test your program on the virtual machine. The grader will not give credits if your program cannot be compiled or run on the virtual machine. 2) Name your programs using the pattern Problem#.c , and name your screenshots using the pattern Problem#_Index.jpg. Problem# is the problem number (e.g., 1, 2, 3, 4, etc). Index is the index number showing the order of the screenshots (e.g., 1 or 2). The following problems create and use singly linked lists. You can use the following structure definition for nodes. struct node { int value; struct node *next; }; Use linked list. Using arrays will not receive any points. Problem 1 Write a program in C to create a singly linked list of n nodes and display the nodes in original and reversed orders. Your program should first ask user for integers. In a loop, it reads in integers (scanf), creates structure nodes (malloc), saves the integers into the nodes, and links the nodes onto a linked list. To finish inputting integers, the user presses ctrl-d, and scanf() will return EOF (e.g., if(scanf("%d", ...) == EOF) break; ) Your program prints the integers from the beginning of the list to the end, and then it prints the integers in reverse order (i.e., from the end to the beginning). Hint: To print the integers in reverse order, you can create a new linked list: remove the nodes on the original list from beginning to end, and add then to the front of the new list. In this way, the last node in the original list will become the first node in the new list, the second last becomes the second, … Your program can display the nodes on the new list. Do not use an array to save the data in the original list, and then display the data in the array in reversed order. Test Data : Input data for node 1 : 5 Input data for node 2 : 6 Input data for node 3 : 7 Expected Output: Data entered in the list are: Data = 5 Data = 6 Data = 7 The list in reverse are : Data = 7 Data = 6 Data = 5 Problem 2 Write a C program that use bubble sort to sort the integer values provided through user inputs (not from the command line). Your program should first ask user for integers. In a loop, it reads in integers (scanf), creates structure nodes (malloc), saves the integers into the nodes, and links the nodes onto a linked list. To finish inputting integers, the user presses ctrl-d, and scanf() will return EOF. Then, your program sorts the nodes on the list by moving the nodes on the list. The nodes saving smaller values are moved to the front and the nodes saving larger values are moved to the rear. Use bubble sort. Do not use radix sort or other sort algorithms. Sort the nodes on the linked list directly. Do not use an array to save and sort the values. I know you can swap the values in the nodes to keep them in ascending order. But this problem is for you to practice. Thus, your program is not allowed to change the value in a node after the value is initialized. To sort the values, your program can only change the positions of the nodes on the list (i.e., unlink a node from the list and relink it to somewhere else). When sorting is finished, your program prints out the integers saved in the nodes from the first node to the last node on the list, one number on each line. Test your program manually first. Manually type in inputs, press ctrl-d, and check output. To fully test your program with more numbers, modify and use the following scripts. $1 of the script is the count of the integer values. Take screenshots when you test your program manually, such that we can see the numbers provided to the program and the output of the program. #!/bin/bash count=$1 rm input rm your_output rm standard_output echo "================== input ======================" for (( i=0; i<${count}; i++="" ));="" do="" echo="" $random="" done="" |="" tee="" -a="" input="" echo="" "="============" execution="" result="==============="" cat="" input="" |="" path_name_of_your_program="" |="" tee="" your_output="" sort="" -n="" input=""> standard_output echo "====== differences from correct result =======" diffyour_outputstandard_output CS 288 Intensive Programming Structures and pointers 6/25/2021 1 Structures can organize data in different types Declared using struct with member types and names included in braces. struct variables can be declared with the struct. 6/25/2021 Lect 23P. 2 struct transaction { int id; float amount; char name[20]; char addr[30]; }; struct transaction t, *pt; struct transaction { int id; float amount; char name[20]; char addr[30]; } t, *pt; typedef struct { int id; float amount; char name[20]; char addr[30]; } transaction; transaction t,*pt; Prof. Ding, Xiaoning. Spring 2021. Protected content. 6/25/2021 Prof. Ding, Xiaoning. Spring 2021. Protected content. 2 Instructor: Often multiple variables must be passed from one function to another, and often these variables have different data types. Thus it is useful to have a container to store various types of variables in. Structs allow the programmer to do just that. Accessing struct members using . or -> A member in a struct variable can be access using . A member in a struct pointed by a pointer can be access using -> or by dereferencing the pointer first and then using . 6/25/2021 3 pt=&t; printf("id: %d, name: %s, addr: %s", t.id, pt->name, (*pt).addr); Pointer members in a struct Some members need to have their memory dynamically allocated or location dynamically determined. 6/25/2021 4 Extra pointers can be added to structs to support data structures, e.g., linked list, stack, queue, tree, graph, … struct transaction{ int id; float amount; char name[20]; char *addr; } t1, t2; t1.addr=(char *)malloc(30); t2.addr=another_str; struct transaction{ int id; float amount; char name[20]; char *addr; struct transaction *next; } t1, t2; t1.next = &t2; Linked Lists A linked list is a sequence of connected nodes. Each node contains at least Some data A pointer to the next node in the list The head pointer points to the first node The last node points to NULL The tail pointer (optional) points to the last node. 6/25/2021 5 '\0' node * a; a->next = b; z->next = NULL; b->next = c; node * head; node * tail; … Why linked list? Often the maximum size of the list cannot be estimated. Static arrays have fixed sizes. Extending dynamic arrays (malloc-ed mem space) may need to copy data from the old and smaller space to a larger new space. Usually there are updates in the middle of the list, e.g., insertion, deletion, re-arranging, etc. Overhead is high with arrays. Inserting a new element in the front or deleting the first element requires shifting all the elements in the array On average, half of the lists needs to be moved for insertion/deletion. Compared to an array, linked list uses only as much space as is needed (requires extra-space for pointers) 6/25/2021 6 Declare node type --- self-referential struct Create nodes --- allocate memory on-demand, initialize members Link nodes to the list --- find a location on the list (the previous and/or the next node) and update pointers in these nodes and the new node. Keep the head pointer updated --- If the address is lost, the whole list may be lost. Ensure the next pointer of the last node to NULL. If there is a tail pointer, keep it updated Building a linked list 7 6/25/2021 '\0' … node * a; node * b; a->next = b; z->next = NULL; b->next = c; node * head; node * tail; 6/25/2021 8 #include
#include struct node{ int id; char name[20]; struct node *next; }; int main(){ struct node *head=NULL, *tail=NULL, *pnode; while(1){ pnode=(struct node *)malloc(sizeof(struct node)); printf("id:"); scanf("%d", &(pnode->id)); if(pnode->id<0) break;="" printf("name:");="" scanf("%s",="" pnode-="">name); pnode->next=NULL; /*ensure next pointer of last node is NULL */ if(head==NULL) head=pnode; if(tail!=NULL) tail->next=pnode; tail=pnode; } Declare node type self_referential struct Create and initialize a new node Link the new node to the end head/tail pointers always point to the first/last node. Traverse a linked list Start from the head pointer. Proceed following the next pointers of nodes. Stop when the last node is reached. Last node: next pointer is NULL, or pointed by the tail pointer. 6/25/2021 9 pnode=head; while(pnode!=NULL) { printf("id: %d\t name:%s\n", pnode->id, pnode->name); pnode=pnode->next; } } Adding a node to a list 6/25/2021 10 node * head; node * b; b->next = head; head = b; Order of the operations is important head = b; b->next = ? '\0' ? adding to the front Adding a node to a list adding to the front 6/25/2021 11 node * head; node * b; b->next = head; head = b; Order of the operations is important head = b; b->next = ? '\0' ? Inserting into the middle node * a; node * b; '\0' b->next = a->next; a->next = b; Consider a->next as a "head pointer" to the rest of the list. Deleting a node 12 6/25/2021 node * a; a->next; a->next->next; p = a->next; a->next = a->next->next; … free(p); p Deleting the first node 13 6/25/2021 node * a; a->next; a->next->next; p = a->next; a->next = a->next->next; … free(p); p p = head; head = head->next; … free(p); Deleting the last node ? Inserting/deleting a node: what to notice? Check whether the node is to be added to (deleted from) the front, the middle, or the end of the list. Different operations for different locations. Avoid losing the pointer pointing to a node It becomes ``inaccessible'' if there are no pointers points to