1. Purpose
The purpose of this exercise is to make the students familiar with:
(1) the implementation of basic operations of singly linked list;
(2) the basic application of singly linked list;
2. Grading Policy
（1） The full mark is 100, which is equivalent to 5 points in the final score of this course.
（2） The assessment is based on the correctness and quality of the code, the ability demonstrated in debugging and answering related questions raised by the lecturer and teaching assistants.
（3） The exercises should be completed individually and independently.
（4） Some reference codes are provided at the end of this document, only for the purpose of helping those students who really have difficulties in programing. It is allowed to use the reference codes. However, straight copy from the reference codes or with minor modification can only guarantee you to get a pass score. Therefore, the students are encouraged to write their own codes to get a higher score.
3. Contents of Exercises
3.1 Implementation of basic operations of singly linked list
Exercise 3.1 (60 points)
Create a singly linked list with some data elements, and finish such operations as initialization, insertion, deletion etc.
All operations should be implemented as independent functions, which can be called by the main function.
(1) Create a singly linked list with data elements of 21, 18, 30, 75, 42, 56, and output all the elements
(2) Get the length of the list, and output the value;
(3) Get the 3rd element of the list, and output the value;
(4) Insert 67 into the list at positon 3, and then output all the elements in the list;
(5) Delete the 2nd element from the list, and then output all the elements in the list;
(6) Search for 30 in the list. If found, report the position of the element;
3.2 Application of singly linked list
Exercise 3.2(20 points)
Based on the singly linked list created in step(1) of Exercise 3.1, complete following tasks:
(1) Get the maximum data element in the list, and print the maximum data;
(2) Test whether the list is in ascending order;
Exercise 3.3 (20 points)
Create a singly linked list with head node and with date elements as 10, 21,32,43,54, 65, 76, and complete following tasks:
(1) Insert 35 into the list, and keep the list in ascending order;
(2) Delete all the elements whose data value are between 22 and 57
4. Reference Code
Exercise 3.1
#include
#include
#include
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;
// definition of node structure of singly linked list
typedef struct L_node
{
ElemType data; // data field
struct L_node *next; // pointer field
}LNode, *LinkedList;
//==========================================
// initialization of singly linked list L with head node
//===========================================
Status InitList_L(LinkList &L)
{
L=(LinkList) malloc(sizeof(LNode)); //make a node
if(!L) return ERROR;
L->next=NULL; //empty list
return OK;
}
//===========================================
// Create a singly linked list L with head node, and with n elements
//===========================================
Status CreateList_L(LinkList &L, int n)
{
LinkList p, q;
int i ;
L=(LinkList) malloc(sizeof(LNode)); //create an empty list
if(!L) return ERROR;
L->next=NULL;
q=L;
for(i=0; idata); //enter element data from keyboard
add some codes here
}
p->next=NULL;
return OK;
}
//=========================================
// Get the length of a singly linked list with head node
//=========================================
int ListLength_L(LinkList L){
int i;
LinkList p;
p=L->next; //let p point to the first node
i=0; // i is a counter
while(p){ //traverse the list to count the nodes
add some codes here
}
return i;
}
//========================================
// Get the ith element of a singly linked list
//========================================
Status GetElem_L (LinkList L, int i, ElemType &e){
int j;
LinkList p;
p=L->next; //let p point to the first node
j=1; // j is a counter
while(p && (ji) return ERROR; // the ith element doesn’t exist
e=p->data; // get the data of the ith element
return OK;
}
//===============================================
// search for an element in a singly linked list and return its position
//==============================================
int LocateElem_L (LinkList L, ElemType e)
{
int j;
LinkList p;
p=L->next; // p points to the first node
j=1; // j is a counter
while(p && ! (p->data!=e)){ // move p
p=p->next; ++j; // until p points to the ith element
}
add some codes here
}
//=====================================
// Insert element e at the ith position of a singly linked list
//====================================
Status ListInsert_L(LinkList &L, int i, ElemType e)
{
int j;
LinkList p, s;
p=L;
j=0;
while(p && jnext;++j;} //locate the (i-1)th node
if(!p||j>i-1) return ERROR; //ilist length
s=(LinkList)malloc(sizeof(LNode)); //make a new node
add some codes here
return OK;
}
//===================================================
// Delete the ith elment from
//====================================================
Status ListDelete_L(LinkList &L,int i,ElemType &e)
{
int j;
LinkList p;
p=L;
j=0;
while(p->next && jnext; ++j;
}
if(!(p->next && jnext;
printf(“\nThe elements of linked list is:”);
while(p){
printf(“%d, ”, p->data) ;
p=p->next;
}
printf(“\n”);
}
int main()
{
int e;
ElemType e;
LinkedList LA;
int len;
int tmpPos;
// Create a singly linked list with elements of 21, 18, 30, 75, 42, 56
CreateLinkedList(LA, 6);
LinkedListPrint(LA);
// get the length
len=ListLength_L(LA);
printf(“the length of the list is %d\n”, len);
//get the 3rd element
GetElem_L(LA, 3 ,e);
printf(“the 3rd element is %d\n”, e);
// insert 67 into the list at position 3
ListInsert_L(LA, 3, 67);
LinkedListPrint(LA);
//delete the 2nd element
ListDelete_L(LA, 2);
LinkedListPrint(LA);
// Search for 30 in the list
e=30;
tmpPos = LocateElem_L(LA, e);
printf(“the position of element %d is %d”, e, tmpPos);
return OK;
}
Exercise 3.2
Note: reusable codes in Exercise 3.1 are not repeated here.
//=======================================
// test whether a singly linked list is in ascending order
//=======================================
int IsAscendingOrder_L(LinkList L)
{
LinkList p;
p=L->next;
while(p->next){
add some codes here.
}
} return TRUE;
//=================================
// Get the maximum element in a singly linked list
//================================
Status GetMaximum_L(LinkList L, ElemType &e)
{
LinkList p;
int tempMax;
p=L->next;
if(!p) return ERROR;
tempMax=p->data;
while(p){
add some codes here
}
e=tempMax;
return OK;
}
int main()
{ int e1;
ElemType e;
LinkedList LA;
int len;
int retVal;
// Create a singly linked list with elements of 21, 18, 30, 75, 42, 56
CreateLinkedList(LA, 6);
LinkedListPrint(LA);
//Get the maximum data of the list, and print the data;
GetMaximum_L(LA, e);
printf(“the maximum data is %d\n”, e);
//test whether list is in ascending order
retVal=IsAscendingOrder_L(LA);
if(retVal )
printf(“the list is in ascending order”);
else
printf(“the list is not in ascending order”);
return OK;
}
Exercise 3.3
Note: reusable codes in Exercise 3.1 are not repeated here.
//========================================
// Insert element into an ascendingly ordered list L, and keep L in ascending order
//========================================
Status OrderedListInsert(LinkList L, ElemTpye e)
{
LinkList p;
p=L->next;
while(p){
add some codes here //find the proper position where element e is inserted
}
s=(LinkList)malloc(LNode); //make a new node
if(!s) return ERROR;
s->data=e;
add some codes here //insert the new node into the linked list
return OK;
}
//============================================================
// From an ascendingly ordered linked list, delete all the elements ranged between a and b,
// where anext;
while(p && (p->data < a)){ p=p->next;
}
while((p->next) && (p->next->data < b){ add some codes here } return OK; } int main() { LinkedList LA; // Create a singly linked list with by date elements as 21, 18, 30, 75, 42, 56 CreateLinkedList(LA, 6); LinkedListPrint(LA); //insert 35 into the list; OrderedListInsert(LA, 35); LinkedListPrint(LA); //delete all the elements ranged between 22 and 57 OrderedListDelete(LA, 22, 57); LinkedListPrint(LA); }
