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; i

p=(LinkList) malloc(sizeof(LNode)); //make a new node

if(!p) return ERROR;

scanf(&p->data); //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 && (j

add some codes here //or p becomes NULL

}

if(!p||j>i) return ERROR; // the ith element doesnt 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; //i <1 or i> list 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 && j

//and p points to its precursor

p=p->next; ++j;

}

if(!(p->next && j

?

add some codes here

return OK;

}

//======================================

// Print the elements in a list

//=======================================

void LinkedListPrint(LinkedList L)

{

?LinkList p;

p=L->next;

printf( The elements of linked list is:);

while(p){

?printf(%d, , p->data) ;

??p=p->next;

?}

?printf( );

}

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 , len);

//get the 3rd element

GetElem_L(LA, 3 ,e);

printf(the 3rd element is %d , 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 , 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 a

//============================================================

Status OrderedListDelete(LinkList &L, int a, int b)

{

?LinkList p;

?p=L->next;

?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);

}