Linear table definitions and features

A finite sequence of data elements of the same type

The initial node has a successor and no precursor, the terminal node has a precursor and no successor, the intermediate node, the internal node has and only one direct precursor and one direct successor.

It comes down to: linearization of relation and sequential storage of nodes

Memory allocation function

To use the following functions, you need to load the header file<stdlib.h>

  1. The malloc(m) function allocates m bytes of address space and returns the first address of the space
  2. The sizeof(x) function: evaluates the length of the variable x
  3. Free (p) : Releases the storage space of the variable indicated by the pointer P, that is, deletes a variable completely

For example, L.d ata = (int *) malloc (sizeof (int) * MaxSize)

Multiply the sizeof an int by the maximum number of nodes MaxSize. Malloc allocates 4*MaxSize space.

If MaxSize=100, then we know that 400 bytes are required, but we do not know whether 400 char, 100 int, or 50 double.

Commonly used predefined variables

Sequential representation and implementation

When logic is continuous, storage is continuous. Any element can be accessed at will without having to walk through it one by one. However, insert and delete operations are not convenient, except for the end of the table element operation, other locations need to move a large number of elements.

Storage allocation functions are allocated statically in advance. Therefore, when the table length changes greatly, it is difficult to determine the appropriate storage scale, and the length cannot be defined dynamically.

Calculation of where elements are stored

Storage Type Description

Since it is not convenient to add and delete, we need to save the current table length while defining each node of a linear table.

ElemType is an alternative to “int”, “float”, “char” and other data types……

Typedef struct{ElemType elem[maxsize]; Int length; }seqlist; seqlist L; L.data=(ElemType*)malloc(sizeof(ElemType)*10)Copy the code

Where elem is an array of 100 nodes, length is the current table length, and the sequential table type name (which I call “phenotype”) is seqList, which means the table has 100 nodes.

useseqlist Lorseqlist *LCreate an order table named L of type seqList

  1. The most basic structure
typedef struct{ int data[10]; Int length; }seqlist; seqlist L;Copy the code

Since the number of nodes is declared, there is no need to allocate memory.

  1. As shown below, there are two elements in each node

Declare a type and then use it inside another structure

typedef struct{ float p; // int e; / /} poly real order; Poly typedef struct{poly *elem; /* Use the type declared above to define the sequential table head address, dynamically define the head address (also can use poly ELEm [100], static definition) */ int length; / / table} seqlist long; // No space is allocated when only variables are declared. L lem=(poly*)malloc(sizeof(ElemType)*MaxSize) // Need to allocate space to the nodeCopy the code

Find operations

Find and return the location by value

Compare them one by one and use flag to determine if they are found

Int locate(seqlist L,int find){// locate(seqlist L,int find){ int flag=0; for(i=0; i<L.length; i++){ if(L.data[i]==find){ flag=1; number=i+1; } } if(flag==1) return number; else return -1; }Copy the code

Algorithm analysis

The number of searches is related to the position of the keyword, and the average search length is similar to the expectation in mathematics:Each of them has a probability of 1 over n, which simplifies to 1 over n(n + 1) / 2

The insert

Before inserting an element into a position (push aside, occupy the original position)

Key:

  1. The element after the insertion position is moved one bit in order to make room, and then inserted.
  2. Check the insertion position: if the subscript is >0 and the subscript is < table length +1
  3. Check the table length. If the table length is ==MaxSize, the table cannot be inserted
  4. At the end of the insert, give the table length +1
Seqlist add(seqlist L,int local,int num) // Insert num {int I,j; If ((local < 1) | | (local > L.l ength + 1)) {printf (" \ n input position illegal "); } else if(l.length ==MaxSize){printf("\n insert position not enough "); } else{for(I = l.length-1; i>=local-1; I --){/*** / l.data [I +1]= l.data [I]; } L.data[local-1]=num; } l.length ++; printf("\n"); for(i=0; i<L.length; I ++){// Print check printf("%d ", l.ata [I]); }}Copy the code

This code has a variable pass problem, that is, the insertion result is not received in the function

Delete operation

Delete the element in position I

Key:

  1. Check the insertion position: if the subscript is >0 and the subscript is < table length +1

  2. Delete the location element, then move forward one bit to fill the position

  3. At the end of the insert, give the table length -1

Seqlist del(seqlist L,int local){// Delete the local element int I; If (local > L.l ength | | local < 1) printf (" \ n input position without element "); else{ for(i=local-1; i<L.length; i++){ L.data[i]=L.data[i+1]; }} l.length --; printf("\n"); for(i=0; i<L.length; I ++){// Print check printf("%d ", l.ata [I]); }}Copy the code

Algorithm analysis

The probability of each element being selected is 1/n, the sum of moves is (n-1)n/2, and the final deletion expectation is (n-1)/2

merge

In order to apply the explanation by Professor Geng Guohua of Northwest University, the structure is modified (or not modified, subscript last is represented by table length-1) :

typedef struct{
	int data[10];
	int last;
}seqlist;
Copy the code

The merge operation actually means that the smaller of the two order tables is first added to the new order table. When one table is finished, the other table is added to the new order table. (Default ascending order)

/* I,j,k point to L1, L2, L3 * / while (I < = L1. The last one & j < = L2. Last) {if (L1) data [I] < = L2. Data [j]) / / which small put which into the new linear list {L3. Data [k]. = L1 data [I]; i++; k++; } else{ L3.data[k]=L2.data[j]; j++; k++; If (I <= l1.last){if (I <= l1.last){if (I <= l1.last){ i++; k++; } while(j<=L2.last){ L3.data[k]=L2.data[j]; j++; k++; }Copy the code

From: Wang Zhuo teacher: www.bilibili.com/read/cv3285…

From: guo-hua geng teacher www.bilibili.com/video/BV1kx…