Linear table is the linear structure of the data structure, about the linear structure of the relevant knowledge can see the article -01- data structure and algorithm basic knowledge

The preparatory work

The IDE used here is XCode and the language used is C, although you can use other ides and other computer languages.

  • 1. Create one in XcodeMacOStheCommand line engineering;
  • In 2.main.cSome data types and states are defined in the file;
#define MAXSIZE 100 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 // * The value of ElemType depends on the actual situation. Here, int */ typedef int ElemType is assumed. // typedefs int Status; // typedefs int Status; // typedefs int Status; // Data type redefinitionCopy the code

First, the design of linear table

Features of linear tables:

  • There are onlyThe first oneElements andThe last oneElements;
  • All elements except the first and last have oneprecursorAnd asubsequent;
  • The first element has no precursor, only follow-up, and the last element has precursor, no follow-up.

Combined with this feature we can design linear tables into sequential storage, can also be designed into chain storage, here to achieve the sequential storage of linear tables.

We use structs to design a linear table:

typedef struct { ElemType *data; // Store data int length; }Sqlist;Copy the code

Data is a pointer that can be used to store data; Length is an integer. It is used to record the amount of data currently stored. It is convenient for clearing, controlling the amount of data in a linear table, and obtaining the length of a linear table.

Two, linear table initialization

Status InitList(Sqlist *L){// Allocate an array space of MAXSIZE to a linear table L->data = malloc(sizeof(ElemType) * MAXSIZE); // Storage allocation failed exit if(! L->data) exit(ERROR); L->length = 0; return OK; }Copy the code

Allocate a block of memory using malloc, the length of which is determined by the data type and the length of the linear table. The linear table has no data when initialized, so length is 0.

Three, linear table insertion

The Status ListInsert (Sqlist * L, int I ElemType e) {/ / I value is not a legal judgment if (I < 1) | | (I > L - > length + 1)) return the ERROR; If (L->length == MAXSIZE) return ERROR; If (I <= L->length){for(int j = L->length-1; j>=i-1; J -) {/ / after insert location and the location of the backward one L - > data [j + 1) = L - > data [j]; } // Put the new element e in the ith position L->data[i-1] = e; / / length + 1; ++L->length; return OK; }Copy the code
  • I is the insertion position, should be atThe location of the dataandfooterIt is illegal to insert data from positions other than the end of a table, because it does not conform to the characteristics of a linear table.
  • When the length of a linear table is equal toMaximum data lengthWhen,Table is full, you can no longer insert data;
  • ifnotInserted into thefooter, the insertion position needs to be left empty, so the data after the insertion position should be putMove back;
  • The subscript of a linear table is theta0It starts, but the human mind starts1So the actual location of the data insertion should bei-1The location of the;
  • Insert data after the linear tableThe length of theAlso want to+ 1.

Delete the linear table

Status ListDelete(Sqlist *L,int I){if(L->length == 0) return ERROR; / / I value is not a legal judgment if (I < 1) | | (I > L - > length)) return the ERROR; for(int j = i; j < L->length; J++) {/ / deleted element to the element after the move forward L - > data [1] = L - > data [j]; } // Table length -1; L->length --; return OK; }Copy the code
  • Check whether it isempty, delete is meaningless if it is empty;
  • Delete the location within the legal range:0 to length - 1;
  • After deleting data in one location, you need to delete the data in the following locationforwardMove one bit to satisfy the properties of linear tables;
  • After successful deletion, the length is also required- 1.

Value of linear table

Status GetElem (int I Sqlist L, ElemType * e) {/ / whether I value is reasonable, if not reasonable, return the ERROR if (I < 1 | | I > L.l ength) return the ERROR; *e = l.data [i-1]; *e = l.data [i-1]; return OK; }Copy the code
  • It is also necessary to determine whether there is data at the selected position, and then causeAn array, causing a crash;
  • The valid values are as follows:0 to length - 1;
  • *e is the address passed in when the function is called. The assignment of this address and the external access of the function areThe same memoryAddress.

Six, linear table change value

Status setListIndex(Sqlist L,int i,ElemType e){

    if (i < 1 || i > L.length) {
        return ERROR;
    }
    L.data[i-1] = e;
    return OK;
}
Copy the code

The valid value ranges from 0 to length-1. Therefore, only the data in this range can be modified

Clear the linear table

Status ClearList(Sqlist *L)

{
    L->length=0;
    return OK;
}
Copy the code
  • The linear tableAdd, delete, change, searchAre based onlength, the number of data in the current linear table is determined by length, so when the linear table is emptied, the value oflengthSet to0You don’t have access to the data, that is, the linear table isempty.

Get the length of the linear table

int ListLength(Sqlist L)

{
    return L.length;
}
Copy the code

Length is the length of a linear table

Nine, the nullity of the linear table

Status ListEmpty(Sqlist L)

{
    if(L.length==0)
       return TRUE;
    else
       return FALSE;
}
Copy the code

Length is the length of a linear table. If length is greater than 0, the linear table is not empty; otherwise, the linear table is empty.

Print linear tables

Status TraverseList(Sqlist L) { int i; for(i=0; i<L.length; i++) printf("%d\n",L.data[i]); printf("\n"); return OK; }Copy the code

Walk through a linear table in order

Xi. Conclusion

As can be seen from the design of the linear table above:

  • The linear tableSequential storageUnder theCheck and changeIt’s convenient, butAdd, deleteIn order to ensure the continuity of sequential memory after addition and deletion, it is necessarymobileA lot of data;
  • Sequential storage timeMemory is continuousYes, we can also passpointerThe way totraverseIt.