代写Singly Linked List C 程序、代写C列表、代做国外C程序

日期：2018-06-01 07:00

Programming Exercise 3

Singly Linked List Implementation and Application

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 <stdio.h>  

#include <stdlib.h>  

#include <malloc.h>

#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<n; 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<i)){            // move p until p points to the ith element

     add some codes here       //or p becomes NULL

   }

   if(!p||j>i) 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 && j<i-1){p=p->next;++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<i-1){  //locate the ith node,

                         //and p points to its precursor

     p=p->next; ++j;

  }

  if(!(p->next && j<i-1) return ERROR; //error for the position for deletion

add some codes here

return OK;

}

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

// Print the elements in a list

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

void LinkedListPrint(LinkedList L)

{

LinkList p;

p=L->next;

printf(“\nThe elements of linked list is:”);

   while(p){

   printf(“%d,  ”, p->data) ;

p=p->next;

}

printf(“\n”);

}

int main()  

{  

int e1;

   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 a<b

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

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()  

{  

int e1;

   ElemType e;

LinkedList LA;  

int len;

int a, b;

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

}