# Data structure week 3 [item 1 - basic operation of sequence table]

Question and code:

```/*
*(1)The purpose is to test the "create linear table" algorithm, CreateList. In order to view the results of table building, it is necessary to implement the "output linear table" algorithm, DispList. It is found in the study DispList that in order to output linear table, it is necessary to determine whether the table is empty. In this way, it is necessary to implement the algorithm ListEmpty to determine whether the linear table is empty. In this way, plus the main function, the program consists of four functions. The main function is used to write test related code.
* (2)On the basis of the created linear table, the algorithm of finding the length of the linear table ListLength, a data element GetElem in the specified position in the linear table L and the element LocateElem can be realized. On the basis of the original procedure, add:
*    Increase the function to find the length of the linear table ListLength and test it;
*  Add the function to find the GetElem of a data element at the specified position in the linear table L and test it;
* 　 Add the function to find the element LocateElem and test;
*(3)The other four basic operations: insert data element ListInsert, delete data element ListDelete, initialize linear table InitList and destroy linear table DestroyList can be completed in the same way. Please arrange your own practice route.
*
*/
#include<stdio.h>
#include<malloc.h>
#define Maxsize 50
typedef int Elemtype;
typedef struct
{
Elemtype date[Maxsize];
int length;
}Sqlist;
//Establish sequence table
void CreateList(Sqlist *&L, Elemtype a[ ], int n)
{
int i;
L = (Sqlist *)malloc(sizeof(Sqlist));
for (i = 0; i < n; i++)
L->date[i] = a[i];
L->length = n;
}
//Initialization sequence table
void InitList(Sqlist *&L)
{
L = (Sqlist*)malloc(sizeof(Sqlist));
L->length = 0;
}
//Destroy linear table
void DestoryList(Sqlist *&L)
{
free(L);
}
//Judge whether the linear table is empty
bool ListEmpty(Sqlist *L)
{
return(L->length == 0);
}
//Find the length of linear table
int ListLength(Sqlist *L)
{
return (L->length);
}
//Output linear table
void DispList(Sqlist *L)
{
int i;
for (i = 0; i < L->length; i++)
printf("%4d", L->date[i]);
printf("\n");
}
//Find an element in a linear table
bool GetElem(Sqlist *L, int i, Elemtype &e)
{
if (i<1 || i>L->length)
return false;
e = L->date[i - 1];
return true;
}
//Find the position of the first same element in the table by element (logical sequence number starts from 1)), and return 0 if such element does not exist
int LocateElem(Sqlist *L, Elemtype e)
{
int i = 0;
while (i < L->length&&L->date[i] != e)
i++;
if (i >= L->length)
return 0;
else
return i + 1;
}
//Insert data element
bool ListInsert(Sqlist *&L, int i, Elemtype e)
{
int j;
if (i<1 || i>L->length + 1)
return false;
i--;
for (j = L->length; j > i; j--)
L->date[j] = L->date[j-1];
L->date[i] = e;
L->length++;
return true;
}
//Delete data element
bool ListDelete(Sqlist *&L, int i, Elemtype &e)
{
int j;
if (i<1 || i>L->length)
return false;
i--;    //Convert logical sequence number to physical sequence number!!!!!!!
e = L->date[i];
for (j = i; j < L->length-1; j++)
L->date[j] = L->date[j + 1];
L->length--;
return true;
}
void CreateList(Sqlist *&L, Elemtype a[], int n);
void InitList(Sqlist *&L);
void DestoryList(Sqlist *&L);
bool ListEmpty(Sqlist *L);
int ListLength(Sqlist *L);
void DispList(Sqlist *L);
bool GetElem(Sqlist *L, int i, Elemtype &e);
int LocateElem(Sqlist *L, Elemtype e);
bool ListInsert(Sqlist *&L, int i, Elemtype e);
bool ListDelete(Sqlist *&L, int i, Elemtype &e);
int main()
{
Sqlist *sq;
Elemtype x = { 5,8,7,2,4,9 };
Elemtype a;
int t;
CreateList(sq, x, 6);
DispList(sq);
printf("The length of the table is:%d\n", ListLength(sq));
if (GetElem(sq, 4, a))
printf("The third element value found is%d\n", a);
else
printf("3rd element out of range!\n");
if (GetElem(sq, 7, a))
printf("The seventh element value found is%d\n", a);
else
printf("Element 7 out of range!\n");
if (t =LocateElem(sq,8)> 0)
printf("Find the first number that is the same as 8%d Elements\n", t);
else
if (t = LocateElem(sq, 12)> 0)
printf("Find the first value of 12 is the number of%d Elements\n", t);
else
ListInsert(sq,3, 6);
DispList(sq);
return 0;
}```

Operation result: Summary of knowledge points:

1. Definition of linear table: a linear table is a finite sequence of data elements with the same characteristics.

2. Sequential storage of linear table: store all elements of linear table in logical order in a continuous storage space at the beginning of the storage location specified by the computer.

Features: (1) there is only its own data and no pointer field in the node. High storage density and utilization of storage space.

(2) any data element can be accessed directly through the serial number, that is, it can be stored randomly.

(3) insert and delete operations will cause a large number of data elements to move.

Added by toibs on Fri, 20 Dec 2019 20:41:22 +0200