Internet of Things knowledge recommendation search
The data structure
algorithm
The C language
C++
YanWeiMin
Define variables
#include<stdio.h> // input/output header file #include<stdlib.h> //malloc and free are in this header file #define LIST_INIT_SIZE 100// initial allocation of linear table storage space #define LISTINCREMENT 10// Linear table storage space allocation increment #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; // The function type, whose value is the result of the function state code typedef int ElemType; #define maxList 10 ElemType* q; ElemType* p; ElemType* pa; ElemType* pb; ElemType* pc; ElemType* pa_last; ElemType* pb_last; int i; / * * * * * * * * * * * * * * * * * * element type * * * * * * * * * * * * * * * * * * * / typedef struct {ElemType * elem; // Storage space base address, l.lem [5] is the sixth bit of the address int length; // Current length int listSize; // The current allocated storage capacity (sizeof (ElemType))}SqList;Copy the code
Initialize a linear table
Create an empty table and set length to zero to initialize the storage capacity
Status list_SQ (SqList& L) {// Build an empty linear table l.ellem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); If (! L.elem)exit(OVERFLOW); OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; // initializing length 0 l.listsize = LIST_INIT_SIZE; // Initial storage capacity return OK; // return 1}Copy the code
Initialize a linear table
Create an empty table and set length to zero to initialize the storage capacity
Status list_SQ (SqList& L) {// Build an empty linear table l.ellem = (ElemType*)malloc(LIST_INIT_SIZE * sizeof(ElemType)); If (! L.elem)exit(OVERFLOW); OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; OVERFLOW (-2) l.length = 0; // initializing length 0 l.listsize = LIST_INIT_SIZE; // Initial storage capacity return OK; // return 1}Copy the code
Insert elements
A sequential list insert is an element inserted at position I, moving all elements after position I one bit back. It is obvious that the time complexity is linear.
/ * * * * * * * * * * * insert * * * * * * * * * * * * * * / Status ListInsert_Sq (int I SqList & L, ElemType e) {ElemType * newbase; Table L / / in order to insert the first before I place the legitimacy of the e / / I insert a new element 0 < I < ListLength. Sq (L) + 1 / / ListLength Sq (table) if (I < 1 | | I > L.l ength + 1) return the ERROR; // I is invalid /* The current storage space is full, */ if (l.length >= L.listSize) {newBase = (ElemType*)realloc(l.ellem, (L.listsize + LISTINCREMENT) * sizeof(ElemType)); /* release the original memory region indicated by l.ellem and re-allocate the size to (l.listsize +LISTINCREMENT)*sizeof(ElemType). Copy the original data to the newly allocated memory region from beginning to end and return the first address of the memory region. */ if (! newbase)exit(OVERFLOW); OVERFLOW (-2) l.ellem = newbase; OVERFLOW (-2) l.ellem = newbase; // new base address l.listSize += LISTINCREMENT; // Increase the storage capacity} {{llem [i-1]); // for (p = &(l.lem [l.length-1]); p >= q; --p) *(p + 1) = *p; // Insert position and backward element right *q = e; // Insert e ++ l.length; // table length +1 return OK; }Copy the code
Deletes elements from a linear table
In a sequential table, deleting an element is very similar to inserting an element. To delete an element is to move all elements after position I one bit forward. In the sequential storage structure, an element is inserted or deleted, and half of the elements in the linear list are moved in order (n) time.
/ * * * * * * * * * * * * * * * * * * * * * * * * * * to delete the element I * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * / Status ListDelete_Sq (int I SqList & L, ElemType & e) {/ / in order to delete the element I in the table, and returns its value/e/I the legitimacy of 0 < I < L.L istLength. Sq (L) if (I < 1) | | (I > L.L ength)) return the ERROR; p = &(L.elem[i - 1]); E = *p; // Assign the value of the deleted element to e q = l.lem + L.length-1; For (++p; p <= q; ++p) // The element after the deleted element moves to the left *(p-1) = *p; --L.length; // table length -1 return OK; }Copy the code
The query
To query whether a value exists in the order table, and if it does, what is its position, is to compare the value starting with the first element in the order table. Compare length at most, compare length at least once. (table is not empty)
/ * * * * * * * * * * * * * * * * * * * * * * * * * in order query whether there is in the table and the same element * * * * * e * * * * * * * * * * * * * * * * * / int locateElem_Sq (SqList L, ElemType e) {/ / if found, Returns its bit order in L, otherwise returns 0 I = 1; // the initial value of I is the sequence of the first element p = l.lem; While (I <= l.length && *p++! =e) i++; if (i <= L.length) return i; else return 0; }Copy the code
Output linear list
Void PrintList_sq(SqList L) {int I; for (i = 0; i <L.length; i++) printf("%d ",L.elem[i]); printf("\n"); }Copy the code
Merge two tables
To merge two tables, first create space that can store the space needed to merge two tables. Then compare the size of the elements in the two tables, store the smaller ones first, and then continue to compare until all the elements in one table are stored, and put the remaining elements in the other table in turn into Table 3.
Void MergeList_Sq(SqList La, SqList Lb, SqList& Lc) { The elements of Lc are also arranged in non-decreasing order of value. pb = Lb.elem; Lc.listsize = Lc.length = La.length + Lb.length; // The table length of Lc is La+Lb PC = lc. elem = (ElemType*)malloc(lc. listSize * sizeof(ElemType)); // Allocate space to the PC if (! Lc.elem) exit(OVERFLOW); Pa_last = la.elem + la.length -1; pa_last = la.elem + la.length -1; Pb_last = lb.elem + lb.length-1; While (pa <= pa_last &&pb <= pb_last) {// if (pa <=pb)// if (pa <=pb)// if (pa <=pb)// if (pa <=pb), PC assigns pa and both Pointers +1 * PC ++ = * PA ++; else *pc++ = *pb++; While (pa <= pa_last) *pc++ = *pa++; While (pb <= pb_last) *pc++ = *pb++; // Insert the rest of Lb}Copy the code
Logical run (main)
int main() { int options; SqList p; SqList q; int n; int e; int a[maxList]; InitList_Sq(p); // Initialize the sequence table printf(" Please enter the number of elements you want to create: \n"); scanf("%d", &n); MaxList for (int I = 1; i <= n; I ++) {printf(" please enter the %d element value \n", I); scanf("%d", &a[i]); ListInsert_Sq(p, i, a[i]); } PrintList_sq(p); int status1 = 1; While (status1) {printf(" Please enter what you want to do: 1, insert; 2. Delete; 3, query; 4, quit \n"); scanf("%d", &options); Switch (options) {case 1: //{printf(" please enter your desired location \n"); scanf("%d", &i); Printf (" Please enter the value of the element you want to insert \n"); scanf("%d", &e); ListInsert_Sq(p, i, e); PrintList_sq(p); //} break; Case 2: printf(" Please enter the location \n"); scanf("%d", &i); ListDelete_Sq(p, i, e); Printf (" delete %d successfully \n", e); PrintList_sq(p); break; Case 3: printf(" Please enter the value you want to query \n"); scanf("%d", &e); i = locateElem_Sq(p, e); if (i ! = 0) printf(" %d\n", I); Else printf(" no value \n"); PrintList_sq(p); break; case 4: exit(0); Default: printf (" \ n \ t error "); exit(0); PrintList_sq(p); break; } } printf("%d\n",p.length); return 0; }Copy the code
running
Scan the QR code to obtain
More wonderful
Internet of Things knowledge
This article uses the article synchronization assistant to synchronize