Programming Exercise 2
Sequential 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 sequential list;
(2) the basic application of sequential 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 done 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 sequential list
Exercise 2.1 (60 points)
Create a sequential 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 sequential list with data elements of 21, 18, 30, 75, 42, 56, and output all the elements
(2) Get the 3rd element of the list, and output the value;
(3) Insert 67 into the list at positon 3, and then output all the elements in the list;
(4) Delete the 6th elements from the list, and then output all the elements in the list;
(5) Search for 75 in the list. If found, report the position of the element;
(6) Get the maximum data element in the list, and print the maximum data;
3.2 Application of sequential list
Exercise 2.2 (20 points)
Based on the sequential list created in step(1) of exercise 2.1, finish following operations:
(1) Sort the list into ascending order, by using bubble sort or other sort method, and output all the elements in the list;
(2) Insert 35 into the list, and keep the list in ascending order;
Exercise 2.3 (20 points)
Based on the sequential list created in step(1) of Exercise 2.1, finish following tasks:
(1) Delete a total of 3 elements starting from the 2nd element.
(2) Inverse the list, namely from A=(a1,a2,…an) to A=(an,an-1,…a1).
4. Reference Code
Exercise 2.1
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
// Create an empty list
Status CreateList_Sq(SqList &L)
{
L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
if (!L.elem) return ERROR;
L.length=0; // length is 0
L.listsize=INIT_SIZE; // initial size of the list
return OK;
}
//
// insert element e at position i
//
Status InsertList_Sq(SqList &L, int i, ElemType e)
{ int * newbase,*q,*p;
if ((i<1)||(i>L.length+1)) {
printf("illegal value of i!\n");
return ERROR;
}
if (L.length>=L.listsize) //the list is full, increase the size of storage space
{
newbase=(ElemType
*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));
if (!newbase) return ERROR;
L.elem=newbase;
L.listsize= L.listsize+LISTINCREMENT;
}
Add some codes here
}
//
// Delete the ith elements of sequential list L
//
Status DeleteList_Sq(SqList &L, int i)
{
int *q,*p;
if ((i<1)||(i>L->length)) {
printf("illegal value of i!\n");
return ERROR;
}
Add some codes here
}
//print out all elements
void PrintList_Sq(SqList L)
{ int i;
for(i=0;i<L.length;i++)
{
printf("%3d ",L.elem[i]);
}
}
//
//compare two elements
//
int equal(ElemType e1,ElemType e2)
{
if (e1==e2) return 1;
else return 0;
}
//
// search for an element in a list
int LocateElem_Sq(SqList L,ElemType e, int (* compare)(ElemType e1,ElemType e2))
{ int i;
i=1;
add some codes here
}
//
// get the ith elements of the list
//
Status GetElem_Sq(SqList L,int i, ElemType &e)
{
Add some codes here;
}
//
// Get the maximum element of the list
//
int GetMax_Sq(SqList L)
{
int Maxval;
add some codes here
return MaxVal;
}
int main()
{
int i;
SqList Lq;
int retval;
int tmpval;
retval=CreateList_Sq(Lq);
if(retval==ERROR)
exit(0);
InsertList_Sq(&Lq,1,21);
InsertList_Sq(&Lq,2,18);
InsertList_Sq(&Lq,3,30);
InsertList_Sq(&Lq,4,75);
InsertList_Sq(&Lq,5,42);
InsertList_Sq(&Lq,6,56);
printf("The initial list is \n");
Print_Sq(Lq) ;
retval=GetElem_Sq(Lq, 3, tmpval);
if(retval==OK) printf(“the 3rd element is\n ”, tmpval);
InsertList_Sq(&Lq,3,67);
printf("\n After inserting 67, the list is \n");
Print_Sq(Lq) ;
DeleteList_Sq(&Lq, 6);
printf("\n After deleting the 6th element, the list is \n");
Print_Sq(Lq);
if ((i=LocateElem_Sq(Lq,75,equal)))
printf("\n75 exists in the list, and its position is %d\n",i);
else
printf("\n 75 doesn’t exist in the list\n");
tmpval=GetMax_Sq(Lq)
printf(“\n the maximum data is \n”, tmpval);
free(L.elem);
return 1;
}
Exercise 2.2
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//
//sort array a[] into ascending order
//
void bubble_sort(int a[],int n){
int i,j;
Boolean change;
for(i=n-1,change=TRUE; i>1 && change; --i){
change=FALSE;
for(j=0;j<i;++j)
if(a[j]>a[j+1])
{
add some codes here
}
}
}
//
// Insert an element into an ordered sequential list, and keep the list in ascending order
//.
void OrderedListInsert(SqList &L, ElemType x)
{
add some codes here
}
int main()
{
int i;
SqList Lq;
int retval;
int tmpval;
retval=CreateList_Sq(Lq);
if(retval==ERROR)
exit(0);
InsertList_Sq(&Lq,1,21);
InsertList_Sq(&Lq,2,18);
InsertList_Sq(&Lq,3,30);
InsertList_Sq(&Lq,4,75);
InsertList_Sq(&Lq,5,42);
InsertList_Sq(&Lq,6,56);
printf("The initial list is \n");
Print_Sq(Lq) ;
// sort the list into ascending order with bubble sort
bubblesort(Lq.elem, Lq.length);
Print_Sq(Lq) ;
//insert 35
retval = OrderedListInsert (Lq, 35);
if(retval == OK)
printf(“\n after inserting 35, the list is\n”);
Print_Sq(Lq);
}
else
printf(“\n List insert error\n”);
return OK;
}
Exercise 2.3
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
//
//delete k elements from a sequential list, starting from position i
//
Status ListDeleteK_Sq(SqList &L, int i, int k)
{
add some codes here
}
//
// inverse a sequential list
//
void InverseList_Sq(SqList &L)
{
add some codes here
}
int main(void)
{
retval=CreateList_Sq(Lq);
if(retval==ERROR)
exit(0);
InsertList_Sq(&Lq,1,21);
InsertList_Sq(&Lq,2,18);
InsertList_Sq(&Lq,3,30);
InsertList_Sq(&Lq,4,75);
InsertList_Sq(&Lq,5,42);
InsertList_Sq(&Lq,6,56);
printf("The initial list is \n");
Print_Sq(Lq) ;
ListDeleteK_Sq(Lq, 2, 3);
Print_Sq(Lq);
InverseList_Sq(Lq);
Print_Sq(Lq);
}
代写CS&Finance|建模|代码|系统|报告|考试
编程类：C++,JAVA ,数据库,WEB,Linux,Nodejs,JSP,Html,Prolog,Python,Haskell,hadoop算法,系统 机器学习
金融类：统计，计量，风险投资，金融工程，R语言，Python语言，Matlab，建立模型，数据分析，数据处理
服务类：Lab/Assignment/Project/Course/Qzui/Midterm/Final/Exam/Test帮助代写代考辅导
天才写手,代写CS,代写finance,代写statistics,考试助攻
E-mail:850190831@qq.com 微信：BadGeniuscs 工作时间：无休息工作日-早上8点到凌晨3点
如果您用的手机请先保存二维码到手机里面，识别图中二维码。如果用电脑，直接掏出手机果断扫描。
