Data structure and algorithm (1) linear table implementation

Data structure and algorithm (2) unidirectional circular linked list creation insert delete implementation

Data structure and algorithm (3) Implementation of bidirectional linked list and bidirectional cyclic linked list

Data structures and algorithms (4) Linked list related interview questions

Data structures and algorithms (5) Stack and queue operation and implementation

Data structures and algorithms (6) The operation and implementation of queues

@TOC

1. Introduction to data structure

1.1 Abstract data types

1.1.1 Data Types

Data type: A generic term for an activation of a set of values of the same nature and for the operations defined within that activation.

In C language, data types can be divided into two types according to different values:

Atomic types: basic data types that cannot be decomposed, including integers, floats, characters, etc.
Structural type: a combination of types that can be refactored. for example, an integer array is made up of integer data.

1.1.2 Abstract data types

Abstraction: to extract the universal essence of things. It is a generalization of concrete things by extracting the feature two of the problem and ignoring non-essential details. Abstraction is a way of thinking about a problem that hides complex details and preserves only the information necessary to achieve a goal.

Abstract data type: refers to a mathematical model and the set of operations defined on that model; For example, we often use coordinates when writing computer graphics software systems. In other words, you’re always going to use x and y to describe the vertical and horizontal coordinates. In a 3D system, z-depth occurs. Since these three integer numbers always appear together, they can be defined as an abstract data type of Point. It has x,y, and z integer variables. This makes it very easy for developers to manipulate Point data variables.

Abstract data types can be understood as structures and classes that are often used in real development; Define appropriate data types and actions based on business requirements.

What are some examples of linear tables in our lives?

For example: 26 alphabets; For example, the student basic information table. Each student is a data element, including student number, name, major and other data items. If the data elements are different, but the elements in the same linear table must have the same characteristics, that is, belong to the same data object, and there is such a sequence relationship between adjacent data elements, the injection of such finite sequence consisting of (N >= 0) elements with the same data characteristics is called “linear table”.

/* Data: the operation object of a program, used to describe objective things. Data item: A data element composed of a number of data items Data element: Basic unit of the object composing data Data object: collection of data elements (similar to array) with the same properties structure: Data elements are not independent but have specific relationships. These relations are structures; Data structure: Refers to the relationship between data elements in the data object */
#include <stdio.h>

// Declare a structure type
struct Teacher{     // A data structure
    char *name;     // Data item -- name
    char *title;    // Data item -- title
    int  age;       // Data item -- age
};


int main(int argc, const char * argv[]) {
   
    struct Teacher t1; // Data element;struct Teacher tArray[10]. // Data object;t1.age= 18; / / data itemst1.name="CC"; / / data itemst1.title= "lecturer "; / / data itemsprintf(" Name of teacher :%s\n",t1.name);
    printf(" Teacher age :%d\n",t1.age);
    printf(" Teacher title :%s\n",t1.title);
    
    return 0;
}
Copy the code

The number of elements in a linear table, n, is defined as the length of the linear table, and is called empty if n=0

Corresponding to non-empty linear tables and linear structures, which have the following characteristics:

There is a unique data element called “first”
There is a single data element called “the last”.
Every data element in the structure except the first has a precursor.
Every data element in the structure has a successor except the last one.

1.2 Basic terms of data structures

1.2.1 Basic terms of data structures

Composition of data: Basic units of data

Logical structure of data structure: according to logic, it is divided into: set structure, linear structure, tree structure, graphic mechanism and so on.

Set structure: Data elements in a set structure have no other relations except that they all belong to the same set. The only similarity between them is “all belong to the same set”.

Linear structure: The relationship between data elements in a linear structure is one-to-one. Common linear structures are: linear tables, stacks, queues, double queues, arrays, strings.

Tree structure: Data elements in a tree structure are hierarchically one-to-many. Common tree structure: binary tree, B tree, Huffman tree, red black tree and so on.

Graph structure: The relationship between data elements in a graph structure is many-to-many. Common graphic structures: adjacency matrix, adjacency list.

Data structure is divided into sequential storage structure and chain storage structure according to object mechanism.

Sequential storage structure: Data elements are stored in storage units with contiguous addresses. The logical and physical relationships between the data are consistent. For example, in an array, its elements are one after another, and the address in memory space is also continuous. We can access each element by the index of the array, or we can use the address increment method to access

// Sequence table structure
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;
Copy the code

Chain storage: Data elements are placed in arbitrary storage units, which can be contiguous or discontiguous. The storage relationship of data elements does not reflect the logical relationship, so a pointer is needed to store the address of the data element, so that the location of the associated data elements can be found through the address.

1.2.2 Relationship between data structure and algorithm

What’s the algorithm?

An algorithm is a description of the steps required to solve a particular problem, and is represented in a computer as a finite sequence of instructions, each of which represents one or more operations.

The algorithm has the following characteristics:

Input/output: An algorithm has zero or more inputs and at least one or more outputs.
Fineness: Fineness means that an algorithm automatically terminates without an infinite loop after executing a finite number of steps, and each step is completed in an acceptable amount of time.
Deterministic: Deterministic means that each step of the algorithm has a definite meaning and ambiguity cannot occur. Algorithm under certain conditions, there is only one execution path, the same input can only have a unique output result.
Feasibility: Each step of the algorithm must be feasible, that is, each step can be performed a finite number of times

Algorithm design requirements:

Correctness: The correctness of the algorithm means that the algorithm should at least have input, output and processing unambiguous, can correctly reflect the needs of the problem, can get the correct answer to the problem. Correctness is divided into four levels: – Algorithmic programs have no syntax errors; – The algorithm program can produce output results that meet the requirements for legitimate input data; – Algorithm program for illegal input data can get results that meet specifications; – Algorithm program for carefully selected, even tricky test data have to meet the requirements of the output results;
Readability: : Algorithms are also designed to be easy to read, understand, and communicate. High readability helps people understand algorithms, and obscure algorithms often contain errors that are difficult to find, debug, and modify.
Robustness: A good algorithm should also be able to handle input data in cases where it is illegal, which is often the case when writing code. When the input data is invalid, the algorithm can also make relevant processing, rather than producing abnormal and inexplicable results.
High time efficiency and low storage: with the least storage space and the least time, to do the same thing, is a good algorithm

1.2.3 Time complexity and Space Complexity

1.2.3.1 Time Complexity:

The time that a program written in a high-level programming language takes to run on a computer depends on the following factors:

The strategy and method adopted by the algorithm
The quality of code produced by compilation
The input size of the problem
The speed at which a machine executes instructions

The time complexity of the algorithm is defined as follows: In the analysis of the algorithm, the total execution times of the statement T(n) is a function of the problem size n, and then the change of T(n) with n is analyzed and the order of magnitude of T(n) is determined. The time complexity of the algorithm, or the time measure of the algorithm, is T(n) = O(f(n)). It means that with the increase of problem size N, the growth rate of algorithm execution time is the same as that of F (n), which is called the asymptotic time complexity of the algorithm, or time complexity for short. Where f(n) is some function of the size n of the problem. Capital O() to reflect the algorithm time complexity notation, we call it big O notation. The method of deriving large O order:

Replace all addition constants in running time with constant 1
In the modified run times function, only the highest order terms are retained
If the highest order term exists and is not 1, then the constant multiplied by the term is removed
Constant of the order

int sum = 0, n = 100;
sum = (1 + n) * n / 2;
printf("%d", sum);
Copy the code

Each line of code of this algorithm is executed once, and the function of the number of runs is F (n) = 3. According to the method of deducing large order O, the first step is to replace the constant with 1. Since there is no highest order term, the time complexity of this algorithm is O(1). It should be noted that no matter what the constant is, the algorithm of constant order is denoted as O(1) and has no complexity such as O(2) and O(3).

Linear order

for (int i = 0; i < n; i++) {
    // Time complexity O(1) operation
}
Copy the code

To analyze the complexity of the algorithm is to analyze the operation of the loop structure. The time complexity of the above code is O(n) because the code in the body of the loop executes n times.

The logarithmic order

int i = 1;
while (i < n) {
    i = i * 2;
}
Copy the code

In the circulator, I is multiplied by 2 every time, which is 2 to the x is equal to n, and you get the degree x is log base 2 of n x is equal to log base 2 of n. According to the method of deriving large order, the constant of the highest order term is removed, which is O(logn).

Square order

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        // Time complexity O(1) operation}}Copy the code

Loop nesting n*n, time complexity is O(n^2).

For example, the number of times the following function is executed:

The corresponding times of function execution in the above table are as follows:

Time complexity is actually the number of times the algorithm is executed:

Time complexity calculation exercises

#include <stdio.h>
/* big O notation 1. Replace all constants 3->1 O(1) 2. N ^3+2n^2+5 -> O(n^3) 3. If it exists in the highest order and is not equal to 1, then the constant of the multiplication of the items is removed: 2n^3 -> n^3 */

/* Time complexity terms: 1. Constant order 2. Linear order 3. Logarithmic order 5. Cubic order 6. Nlog order 7. Exponential order (regardless) O(2^n) or O(n!) Unless it's a very small n, it's a nightmare time drain. This is an unrealistic time complexity of algorithms. Generally not considered! * /

/* 1. Constant order time complexity calculation O(1) */
//1+1+1 = 3 O(1)
void testSum1(int n){
    int sum = 0;                // Execute once
    sum = (1+n)*n/2;            // Execute once
    printf("testSum1:%d\n",sum);// Execute once
}

//1+1+1+1+1+1+1 = 7 O(1)
void testSum2(int n){
    int sum = 0;                // Execute once
    sum = (1+n)*n/2;            // Execute once
    sum = (1+n)*n/2;            // Execute once
    sum = (1+n)*n/2;            // Execute once
    sum = (1+n)*n/2;            // Execute once
    sum = (1+n)*n/2;            // Execute once
    printf("testSum2:%d\n",sum);// Execute once
    
}
//x=x+1; Perform one
void add(int x){
    x = x+1;
}


/*2. Linear order time complexity */
//x=x+1; N times O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1; }}//1+(n+1)+n+1 = 3+2n -> O(n)
void testSum3(int n){
    int i,sum = 0;               // Execute once
    for (i = 1; i <= n; i++) {   // Execute n+1 times
        sum += i;                // Execute n times
    }
    printf("testSum3:%d\n",sum);  // Execute once
}

/*3. Logarithmic */
PI over 2 to the x is equal to n x is equal to log base 2 of n minus log base n times omega
void testA(int n){
    int count = 1;         // Execute once
    //n = 10
    while (count < n) {
        count = count * 2; }}/*4. */
//x=x+1; Run n*n times ->O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1; }}}//n+(n-1)+(n-2)+... +1 = n(n-1)/2 = n^2/2 + n/2 = O(n^2)
//sn = n(a1+an)/2
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n; i++)for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
    
}

//1+(n+1)+n(n+1)+n^2+n^2 = 2+3n^2+2n -> O(n^2)
void testSum5(int n){
    int i,j,x=0,sum = 0;           // Execute once
    for (i = 1; i <= n; i++) {     // Execute n+1 times
        for (j = 1; j <= n; j++) { / / execution n (n + 1)
            x++;                   // Execute n*n times
            sum = sum + x;         // Execute n*n times
        }
    }
    printf("testSum5:%d\n",sum);
}


/*5. */
void testB(int n){
    int sum = 1;                         // Execute once
    for (int i = 0; i < n; i++) {        // Execute n times
        for (int j = 0 ; j < n; j++) {   // Execute n*n times
            for (int k = 0; k < n; k++) {// Execute n*n*n times
                sum = sum * 2;          // Execute n*n*n times
            }
        }
    }
}

int main(int argc, const char * argv[]) {
    
    testSum1(100);
    testSum2(100);
    testSum3(100);
    
    return 0;
}
Copy the code

1.2.3.2 Space Complexity:

Spatial complexity of the algorithm:

The spatial complexity of the algorithm is realized by calculating the storage space required by the algorithm. The calculation formula of the spatial complexity of the algorithm is written as S(n) = N (f(n)), where N is the size of the problem and f(n) is the function of the statement regarding the memory space occupied by n.

Spatial complexity exercises

/* Program space calculation factor: 1. Store the instruction itself 2. Constant 3. Variable 4. Input 5. Auxiliary space for data operation When considering the spatial complexity of an algorithm, the auxiliary space required for algorithm execution is mainly considered. Calculation of space complexity: Problem: array reverse order, store n numbers in one-dimensional array A in reverse order in the original array. */

#include <stdio.h>

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
   
    int n = 5;
    int a[10] = {1.2.3.4.5.6.7.8.9.10};
    
    // Algorithm implementation (1)
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

    for(int i = 0; i <10; i++) { printf("%d\n",a[i]);

    }
    
    // Algorithm implementation (2)
    int b[10] = {0};
    for(int i = 0; i < n; i++){ b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }
    for(int i = 0; i <10; i++) { printf("%d\n",a[i]);
        
    }
    
    return 0;
}
Copy the code

1.3 linear table

1.3.1 Sequence of linear tables

ADT list{Data: The set of Data objects for a linear table is {a1, A2,a,…… An}, each element is DataType, where, except for the first element A1, each element has and only one direct precursor element, and except for the last element an, each element has and only one direct subsequent element, and the relationship between data elements is one-to-one. OPeration (OPeration) InitList(&L) Initializes the table OPeration result: Initialize the table and create an empty linear table. ListEmpty(L) = ListEmpty(L) = ListEmpty(L) = ListEmpty(L) Return true if Lis an empty table, false otherwise ListLength(L) The length of the table (number of elements) Initial condition: a linear table L already exists Operation Result: Return the number of data elements in L…… GetElem(L, I,&e); GetElem(L, I,&e); GetElem(L, I,&e); GetElem(L, I,&e); LocateElem(L,e) Initial condition: linear table L already exists Result: Return the position of the first element in L that has the same value as e in L. Returns 0 if the data does not exist; PriorElem(L, cur_e,&pre_e); Initial condition: linear table L already exists Result: If cur_e is the data element of L and is not the first, pre_e is used to return its precursor, otherwise the operation fails. NextElem(L, cur_e,&next_e); Operation result: If cur_e is the data element of L and not the last one, use next_e to return the next; otherwise, the operation fails……. ListInsert(L,i,e); ListDelete(L, I); ListDelete(L, I); ListDelete(L, I); ListDelete(L, I) 1<= I <=listLength(L); 1<= I <=listLength(L); Initial condition: linear table L already exists Operation result: row through linear table L, each node of Lis accessed once during the traversal.}ADT List

1.3.1.1 Basic operation of sequence table

Order table complete implementation code click here to download: order table basic operation implementation

1.3.1.1.1 Sequence table Structure definition

// Sequence table structure
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;
Copy the code

1.3.1.1.2 Initializing the Sequence table

// 1 sequence table initialization
KStatus initSequenceList(KSList *L) {
    
    // Allocate an array space of MAXSIZE for the sequential table
    L->data = malloc(sizeof(KElementType) * MAXSIZE);
    // The storage fails to be allocated
    if(!L->data) return ERROR;
    // The length of the empty table is 0
    L->length = 0;
    
    return OK;
}
Copy the code

1.3.1.1.3 Insertion of sequence tables

// 2 Insert the sequence table
1≤ I ≤ListLength(L);
Insert a new data element e before the ith position in L, and increase the length of L by 1
KStatus insertElement(KSList *L, int i, KElementType e) {
    
    // Boundary condition judgment
    //1.1 The validity of index I cannot exceed the total length of the linked list
    if((i < 1) || (i > L->length+1)) return ERROR;
    1.2 Check whether the storage space is used up
    if(L->length == MAXSIZE) return ERROR;
    
    If the table is not at the end, move it back to make room for the element to be inserted
    if(i <= L->length) {
        for(int j = L->length-1; j >= i-1; j--) {
            // Move the element after the insertion position by 1, giving way to the ith position
            L->data[i+1] = L->data[i]; }}//1.4 Assign the new element to the vacant position to complete the insert
    L->data[i-1] = e;
    
    //1.5 List length increased by 1
    ++L->length;
    
    return OK;
}
Copy the code

1.3.1.1.4 Sequence table values

// 3. Order table values
KStatus getElement(KSList L, int i, KElementType *e) {
    
    // The boundary condition determines that I cannot exceed the total length
    if(i < 1 || i > L.length) return ERROR;
    
    // Select the value of the ith element with the index I -1 (the index starts at 0 by default)
    *e = L.data[i-1];
    
    return OK;
}
Copy the code

1.3.1.1.5 Order table deletion

// 4. Delete the sequence table
1≤ I ≤ListLength(L)
// Delete the ith element of L, and the length of L is reduced by 1
KStatus deleteElement(KSList *L, int i) {
    
    // Boundary condition judgment
    // Whether the linear table is empty
    if(L->length == 0) return ERROR;
    // Check the validity of the I value
    if((i < 1) || (i > L->length+1)) return ERROR;
    
    for (int j = i; j < L->length; j++) {
        // All elements after the deleted element move forward one position
        L->data[j-1] = L->data[j];
    }
    
    // The table length is reduced by 1
    L->length--;
    
    return OK;
}
Copy the code

1.3.1.1.6 Clearing the order table

// 5. Clear the order table
// Initial condition: sequential linear table L already exists. Result: Reset L to an empty table
KStatus clearList(KSList *L) {
    L->length = 0;
    return OK;
}
Copy the code

1.3.1.1.7 The Judgment sequence table is cleared

// 6. The judgment order table is cleared
// Initial condition: sequential linear table L already exists. Result: TRUE if L is an empty table, FALSE otherwise
KStatus isListEmpty(KSList L) {
    return L.length == 0 ;
}
Copy the code

1.3.1.1.8 Obtaining the Sequence Table Length

// get the length of the sequence table
int getListLength(KSList L) {
    return L.length;
}

Copy the code

1.3.1.1.9 Traverse the order table

// 8. Iterate through the order table
// Initial condition: sequential linear table L already exists
// Result of operation: output each data element of L in turn
KStatus traverseList(KSList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d.\n".L.data[i]);
    }
    printf("\n");
    return OK;
}
Copy the code

1.3.1.1.10 Finding subscripts of order table elements

// 9. Find the order table element subscript
// Initial condition: sequential linear table L already exists
// Return the bit order of the first data element in L that satisfies e.
// If such a data element does not exist, the return value is 0
int getElementIndex(KSList L.KElementType e) {
    // Boundary condition judgment
    if (L.length == 0 ) return 0;
    
    // sequential search
    int i = 0;
    for(i = 0; i < L.length; i++) {
        if (L.data[i] == e) {break;}
    }
    
    if (i >= L.length) return 0;
    
    return i;
}
Copy the code

1.3.1.1.11 Unit Tests

// unit tests
void test() {
    KSList L1;
    //KSList L2;
    KElementType e;
    KStatus iStatus;
    
    //1.1 Sequence table initialization
    iStatus = initSequenceList(&L1);
    printf("After initializing L1: l string = %d\n".L1.length);
    
    //1.2 Sequential table data insertion
    for(int j=1; j <= 5; j++){ iStatus = insertElement(&L1.1, j);
    }
    printf("Insert data L1 length: %d\n".L1.length);
    
    //1.3 Sequence table values
    getElement(L1.5, &e);
    printf("The 5th element of L1 is :%d\n",e);
    
    // remove the second element from the sequence table
    deleteElement(&L1.2);
    printf("Order table L1 deletes element %d with length %d\n".2.L1.length);
    
    //1.5 Clear the order table
    iStatus = clearList(&L1);
    printf("After clearing L1, l string = %d\n".L1.length);
    
    //1.6 Check whether the List is empty
    iStatus = isListEmpty(L1);
    printf("L1 empty: I =%d(1: yes 0: no)\n",iStatus);
    
    //1.8 Iterate over the print order table
    for(int j=1; j <= 5; j++){ iStatus = insertElement(&L1.1, j);
    }
    traverseList(L1);
}
Copy the code

Output structure is as follows:

Hello, World! LTH = 0 after initialization: LTH = 0 Select * from L1; select * from L1; select * from L1; select * from L1; I =1(1: yes 0: no) 5. 0. 444.6Copy the code

1.3.1.2 Linear sequence table complete operation code

//
// main.c
// 001_LinearList
//
// Created by bog on 2020/4/5
// Copyright © 2020 Apple. All rights reserved
//

#include <stdio.h>
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define MAXSIZE 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

//KElementType the KElementType type depends on the actual situation; int is assumed here
typedef int KElementType;
//KStatus is the type of the function whose value is the status code of the function result, such as OK, etc
typedef int KStatus;


// Sequence table structure
typedef struct KSequenceList {
    KElementType *data;
    int length;
}KSList;

// 1 sequence table initialization
KStatus initSequenceList(KSList *L) {
    
    // Allocate an array space of MAXSIZE for the sequential table
    L->data = malloc(sizeof(KElementType) * MAXSIZE);
    // The storage fails to be allocated
    if(!L->data) return ERROR;
    // The length of the empty table is 0
    L->length = 0;
    
    return OK;
}

// 2 Insert the sequence table
1≤ I ≤ListLength(L);
Insert a new data element e before the ith position in L, and increase the length of L by 1
KStatus insertElement(KSList *L, int i, KElementType e) {
    
    // Boundary condition judgment
    //1.1 The validity of index I cannot exceed the total length of the linked list
    if((i < 1) || (i > L->length+1)) return ERROR;
    1.2 Check whether the storage space is used up
    if(L->length == MAXSIZE) return ERROR;
    
    If the table is not at the end, move it back to make room for the element to be inserted
    if(i <= L->length) {
        for(int j = L->length-1; j >= i-1; j--) {
            // Move the element after the insertion position by 1, giving way to the ith position
            L->data[i+1] = L->data[i]; }}//1.4 Assign the new element to the vacant position to complete the insert
    L->data[i-1] = e;
    
    //1.5 List length increased by 1
    ++L->length;
    
    return OK;
}


// 3. Order table values
KStatus getElement(KSList L, int i, KElementType *e) {
    
    // The boundary condition determines that I cannot exceed the total length
    if(i < 1 || i > L.length) return ERROR;
    
    // Select the value of the ith element with the index I -1 (the index starts at 0 by default)
    *e = L.data[i-1];
    
    return OK;
}

// 4. Delete the sequence table
1≤ I ≤ListLength(L)
// Delete the ith element of L, and the length of L is reduced by 1
KStatus deleteElement(KSList *L, int i) {
    
    // Boundary condition judgment
    // Whether the linear table is empty
    if(L->length == 0) return ERROR;
    // Check the validity of the I value
    if((i < 1) || (i > L->length+1)) return ERROR;
    
    for (int j = i; j < L->length; j++) {
        // All elements after the deleted element move forward one position
        L->data[j-1] = L->data[j];
    }
    
    // The table length is reduced by 1
    L->length--;
    
    return OK;
}

// 5. Clear the order table
// Initial condition: sequential linear table L already exists. Result: Reset L to an empty table
KStatus clearList(KSList *L) {
    L->length = 0;
    return OK;
}

// 6. The judgment order table is cleared
// Initial condition: sequential linear table L already exists. Result: TRUE if L is an empty table, FALSE otherwise
KStatus isListEmpty(KSList L) {
    return L.length == 0 ;
}

// get the length of the sequence table
int getListLength(KSList L) {
    return L.length;
}

// 8. Iterate through the order table
// Initial condition: sequential linear table L already exists
// Result of operation: output each data element of L in turn
KStatus traverseList(KSList L) {
    for(int i = 0; i < L.length; i++) {
        printf("%d.\n".L.data[i]);
    }
    printf("\n");
    return OK;
}

// 9. Find the order table element subscript
// Initial condition: sequential linear table L already exists
// Return the bit order of the first data element in L that satisfies e.
// If such a data element does not exist, the return value is 0
int getElementIndex(KSList L.KElementType e) {
    // Boundary condition judgment
    if (L.length == 0 ) return 0;
    
    // sequential search
    int i = 0;
    for(i = 0; i < L.length; i++) {
        if (L.data[i] == e) {break;}
    }
    
    if (i >= L.length) return 0;
    
    return i;
}

// unit tests
void test() {
    KSList L1;
    //KSList L2;
    KElementType e;
    KStatus iStatus;
    
    //1.1 Sequence table initialization
    iStatus = initSequenceList(&L1);
    printf("After initializing L1: l string = %d\n".L1.length);
    
    //1.2 Sequential table data insertion
    for(int j=1; j <= 5; j++){ iStatus = insertElement(&L1.1, j);
    }
    printf("Insert data L1 length: %d\n".L1.length);
    
    //1.3 Sequence table values
    getElement(L1.5, &e);
    printf("The 5th element of L1 is :%d\n",e);
    
    // remove the second element from the sequence table
    deleteElement(&L1.2);
    printf("Order table L1 deletes element %d with length %d\n".2.L1.length);
    
    //1.5 Clear the order table
    iStatus = clearList(&L1);
    printf("After clearing L1, l string = %d\n".L1.length);
    
    //1.6 Check whether the List is empty
    iStatus = isListEmpty(L1);
    printf("L1 empty: I =%d(1: yes 0: no)\n",iStatus);
    
    //1.8 Iterate over the print order table
    for(int j=1; j <= 5; j++){ iStatus = insertElement(&L1.1, j);
    }
    traverseList(L1);
}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    test();
    return 0;
}

Copy the code

1.3.2 Single linked list of linear lists

Single linked list Demo Click here to download: Single linked list Operations

Single linked list node

// Define the node
typedef struct KNodeInfo{
    KElementType data;
    struct KNodeInfo *next;
}Node;
Copy the code

Single linked list logical state
Adds the single-linked list logical state of the header
Why do single-linked lists add headers

1.3.2.1 Single-linked List Initialization

//1. Initialize the single linked list
KStatus initList(KLinkList *L) {
    
    // Generate a header and point to it with L
    *L = (KLinkList)malloc(sizeof(Node));
    // If space allocation fails, exit
    if(*L= =NULL) return ERROR;
    // Set the pointer field of the header to null
    (*L)->next = NULL;
    
    return OK;
}
Copy the code

1.3.2.2 Single linked list insertion node

Single linked list insertion

Implementation code:

//2. Single linked list insertion
1≤ I ≤ListLength(L);
// Insert a new data element e after the ith position in L, and increase the length of L by 1;
KStatus insertElement(KLinkList *L, int i, KElementType e) {
    
    int j = 1;
    KLinkList p, s;
    p = *L;
    
    // find the i-1 node
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    // Check whether the ith element exists
    if(! p || j > i)return ERROR;
    
    // create a new node s
    s = (KLinkList)malloc(sizeof(Node));
    // Assign e to the range of s
    s->data = e;
    // Assign the successor of p to the successor of s
    s->next = p->next;
    // Assign s to the successor of p
    p->next = s;
    
    return OK;
}
Copy the code

1.3.2.3 Deleting nodes from single-linked lists

Single linked list deleted

Implementation code:

//4. Single-linked list deletes elements
1≤ I ≤ListLength(L)
// Delete the ith element of L and return it with e, the length of L minus 1
KStatus deleteElement(KLinkList *L, int i, KElementType *e) {
    
    int j = 1;
    KLinkList p,q;
    p = (*L)->next;
    
    // find the i-1 node where p points to
    while (p->next && j < (i-1)) {
        p = p->next;
        ++j;
    }
    
    // If I >n or I < I, the delete position is incorrect
    if(! (p->next) || (j>i-1)) return ERROR;
    
    //q points to the node to be deleted
    q = p->next;
    // Assign the successor of q to the successor of p
    p->next = q->next;
    // Assign data from q to e
    *e = q->data;
    // Free memory
    free(q);
    
    return OK;
}
Copy the code

1.3.2.4 Single-linked list Values

//3. Single-linked list values
1≤ I ≤ListLength(L);
// Return the ith element in L with e
KStatus getElement(KLinkList L, int i, KElementType *e) {
    int j = 1;
    // point node P to the first node in list L
    KLinkList p = L->next;
    
    P is not null, and j is not equal to I, then the loop continues
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    // If p is empty or j> I, error is returned
    if(! p || j > i)return ERROR;
    
    *e = p->data;
    
    return OK;
}
Copy the code

1.3.2.5 Table – head insertion method for single-linked lists

Single linked list forward interpolation

Implementation code:

// create a singly linked list
// Create a single linear list with a table head.
void createListByHeadInsert(KLinkList *L, int n) {
    KLinkList p;
    // create a singly linked list of leading nodes
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    // Insert random data before loop
    for (int i = 0; i < n; i++) {
        // Create a new node
        p = (KLinkList)malloc(sizeof(Node));
        // assign I to the new node
        p->data = i;
        
        // insert node p after the header
        p->next = (*L)->next;
        (*L)->next = p; }}Copy the code

1.3.2.6 Table – head insertion method for single-linked lists

Single linked list after interpolation

Implementation code:

//8. Create a singly linked list: tail insertion method
// Create a single linear list with a table head.
void createListByTailInsert(KLinkList *L, int n) {
    
    KLinkList p, r;
    
    // create a singly linked list of leading nodes
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    // let the r pointer point to the tail node
    r = *L;
    
    // loop to create the linked list node, insert the tail
    for (int i = 0; i < n; i++) {
        // Create a new node
        p = (Node *) malloc(sizeof(Node));
        // Assign a random number I
        p->data = i;
        
        // insert a new node at the end
        // add a pointer to the end node of the table
        r->next = p;
        // Define the current new node as the table end node
        r = p;
    }
    
    // Next =NULL
    r->next = NULL;
    
}

Copy the code

1.3.2.7 Traversing a single linked list

//5. Iterate through the single linked list
// Initial condition: sequential linear table L already exists
// Result of operation: output each data element of L in turn
KStatus traverseList(KLinkList L) {
    KLinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}
Copy the code

1.3.2.8 Clearing the single-linked list

//6. Clear the singly linked list
// Initial condition: sequential linear table L already exists. Result: Reset L to an empty table
KStatus clearList(KLinkList *L) {
    
    KLinkList p, q;
    // point to the first node
    p = (*L)->next;
    while (p) {
        // Traversal deletes each node and frees memory
        q = p->next;
        free(p);
        p = q;
    }
    // The header pointer field is set to null
    (*L)->next = NULL;
    
    return OK;
}
Copy the code

1.3.2.9 Complete code for single linked list operation

//
// main.c
// 003_LInkedStorage
//
// Created by bog on 2020/4/5
// Copyright © 2020 Apple. All rights reserved
//

#include <stdio.h>
#include "string.h"
#include "ctype.h"
#include "stdlib.h"
#include "math.h"
#include "time.h"

#define ERROR 0
#define TRUE 0
#define FALSE 0
#define OK 1

#define MAXSIZE 20

typedef int KStatus;
typedef int KElementType;

// Define the node
typedef struct KNodeInfo{
    KElementType data;
    struct KNodeInfo *next;
}Node;

typedef struct KNodeInfo *KLinkList; //1. Initialize the single linked listKStatus initList(KLinkList *L) {
    
    // Generate a header and point to it with L
    *L = (KLinkList)malloc(sizeof(Node));
    // If space allocation fails, exit
    if(*L= =NULL) return ERROR;
    // Set the pointer field of the header to null
    (*L)->next = NULL;
    
    return OK;
}

//2. Single linked list insertion
1≤ I ≤ListLength(L);
// Insert a new data element e after the ith position in L, and increase the length of L by 1;
KStatus insertElement(KLinkList *L, int i, KElementType e) {
    
    int j = 1;
    KLinkList p, s;
    p = *L;
    
    // find the i-1 node
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    // Check whether the ith element exists
    if(! p || j > i)return ERROR;
    
    // create a new node s
    s = (KLinkList)malloc(sizeof(Node));
    // Assign e to the range of s
    s->data = e;
    // Assign the successor of p to the successor of s
    s->next = p->next;
    // Assign s to the successor of p
    p->next = s;
    
    return OK;
}

//3. Single-linked list values
1≤ I ≤ListLength(L);
// Return the ith element in L with e
KStatus getElement(KLinkList L, int i, KElementType *e) {
    int j = 1;
    // point node P to the first node in list L
    KLinkList p = L->next;
    
    P is not null, and j is not equal to I, then the loop continues
    while (p && j < i) {
        p = p->next;
        ++j;
    }
    // If p is empty or j> I, error is returned
    if(! p || j > i)return ERROR;
    
    *e = p->data;
    
    return OK;
}

//4. Single-linked list deletes elements
1≤ I ≤ListLength(L)
// Delete the ith element of L and return it with e, the length of L minus 1
KStatus deleteElement(KLinkList *L, int i, KElementType *e) {
    
    int j = 1;
    KLinkList p,q;
    p = (*L)->next;
    
    // find the i-1 node where p points to
    while (p->next && j < (i-1)) {
        p = p->next;
        ++j;
    }
    
    // If I >n or I < I, the delete position is incorrect
    if(! (p->next) || (j>i-1)) return ERROR;
    
    //q points to the node to be deleted
    q = p->next;
    // Assign the successor of q to the successor of p
    p->next = q->next;
    // Assign data from q to e
    *e = q->data;
    // Free memory
    free(q);
    
    return OK;
}

//5. Iterate through the single linked list
// Initial condition: sequential linear table L already exists
// Result of operation: output each data element of L in turn
KStatus traverseList(KLinkList L) {
    KLinkList p = L->next;
    while (p) {
        printf("%d\n",p->data);
        p = p->next;
    }
    printf("\n");
    return OK;
}

//6. Clear the singly linked list
// Initial condition: sequential linear table L already exists. Result: Reset L to an empty table
KStatus clearList(KLinkList *L) {
    
    KLinkList p, q;
    // point to the first node
    p = (*L)->next;
    while (p) {
        // Traversal deletes each node and frees memory
        q = p->next;
        free(p);
        p = q;
    }
    // The header pointer field is set to null
    (*L)->next = NULL;
    
    return OK;
}

// create a singly linked list
// Create a single linear list with a table head.
void createListByHeadInsert(KLinkList *L, int n) {
    KLinkList p;
    // create a singly linked list of leading nodes
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    // Insert random data before loop
    for (int i = 0; i < n; i++) {
        // Create a new node
        p = (KLinkList)malloc(sizeof(Node));
        // assign I to the new node
        p->data = i;
        
        // insert node p after the header
        p->next = (*L)->next;
        (*L)->next = p; }}//8. Create a singly linked list: tail insertion method
// Create a single linear list with a table head.
void createListByTailInsert(KLinkList *L, int n) {
    
    KLinkList p, r;
    
    // create a singly linked list of leading nodes
    *L = (KLinkList)malloc(sizeof(Node));
    (*L)->next = NULL;
    
    // let the r pointer point to the tail node
    r = *L;
    
    // loop to create the linked list node, insert the tail
    for (int i = 0; i < n; i++) {
        // Create a new node
        p = (Node *) malloc(sizeof(Node));
        // Assign a random number I
        p->data = i;
        
        // insert a new node at the end
        // add a pointer to the end node of the table
        r->next = p;
        // Define the current new node as the table end node
        r = p;
    }
    
    // Next =NULL
    r->next = NULL;
    
}

// unit tests
void test() {
        KStatus iStatus;
        KLinkList L;
        KElementType e;
        
        //2.1 Single-linked list initialization
        iStatus = initList(&L);
        printf("L successfully initialized? (0: failed,1: succeeded) %d\n",iStatus);
        
        //2.2 Single linked list inserts data
        for(int j = 1; j<=10; j++) { iStatus = insertElement(&L.1, j);
        }
        printf("L after insertion \n");
        traverseList(L);
        
        //2.3 Single-linked lists get elements
        getElement(L.5,&e);
        printf("The value of the 5th element is: %d\n",e);
        
        //2.4 Delete element 5
        iStatus = deleteElement(&L.5, &e);
        printf("Delete 5th element with value :%d\n",e);
        traverseList(L);
        
        // create linked list L
        iStatus = clearList(&L);
        createListByHeadInsert(&L.20);
        printf("Collate elements that create L (pre-interpolation):\n");
        traverseList(L);
        
        // create linked list L
        iStatus = clearList(&L);
        createListByTailInsert(&L.20);
        printf("Collate elements that create L (interpolation):\n");
        traverseList(L);
}


int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World! \n");
    test();
    return 0;
}

Copy the code

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

Data structure and algorithm (a) linear table implementation

1. Introduction to data structure

1.1 Abstract data types

1.1.1 Data Types

1.1.2 Abstract data types

1.2 Basic terms of data structures

1.2.1 Basic terms of data structures

1.2.2 Relationship between data structure and algorithm

1.2.3 Time complexity and Space Complexity

1.2.3.1 Time Complexity:

1.2.3.2 Space Complexity:

1.3 linear table

1.3.1 Sequence of linear tables

1.3.1.1 Basic operation of sequence table

1.3.1.1.1 Sequence table Structure definition

1.3.1.1.2 Initializing the Sequence table

1.3.1.1.3 Insertion of sequence tables

1.3.1.1.4 Sequence table values

1.3.1.1.5 Order table deletion

1.3.1.1.6 Clearing the order table

1.3.1.1.7 The Judgment sequence table is cleared

1.3.1.1.8 Obtaining the Sequence Table Length

1.3.1.1.9 Traverse the order table

1.3.1.1.10 Finding subscripts of order table elements

1.3.1.1.11 Unit Tests

1.3.1.2 Linear sequence table complete operation code

1.3.2 Single linked list of linear lists

1.3.2.1 Single-linked List Initialization

1.3.2.2 Single linked list insertion node

1.3.2.3 Deleting nodes from single-linked lists

1.3.2.4 Single-linked list Values

1.3.2.5 Table – head insertion method for single-linked lists

1.3.2.6 Table – head insertion method for single-linked lists

1.3.2.7 Traversing a single linked list

1.3.2.8 Clearing the single-linked list

1.3.2.9 Complete code for single linked list operation

Data structure and algorithm (a) linear table implementation

1. Introduction to data structure

1.1 Abstract data types

1.1.1 Data Types

1.1.2 Abstract data types

1.2 Basic terms of data structures

1.2.1 Basic terms of data structures

1.2.2 Relationship between data structure and algorithm

1.2.3 Time complexity and Space Complexity

1.2.3.1 Time Complexity:

1.2.3.2 Space Complexity:

1.3 linear table

1.3.1 Sequence of linear tables

1.3.1.1 Basic operation of sequence table

1.3.1.1.1 Sequence table Structure definition

1.3.1.1.2 Initializing the Sequence table

1.3.1.1.3 Insertion of sequence tables

1.3.1.1.4 Sequence table values

1.3.1.1.5 Order table deletion

1.3.1.1.6 Clearing the order table

1.3.1.1.7 The Judgment sequence table is cleared

1.3.1.1.8 Obtaining the Sequence Table Length

1.3.1.1.9 Traverse the order table

1.3.1.1.10 Finding subscripts of order table elements

1.3.1.1.11 Unit Tests

1.3.1.2 Linear sequence table complete operation code

1.3.2 Single linked list of linear lists

1.3.2.1 Single-linked List Initialization

1.3.2.2 Single linked list insertion node

1.3.2.3 Deleting nodes from single-linked lists

1.3.2.4 Single-linked list Values

1.3.2.5 Table – head insertion method for single-linked lists

1.3.2.6 Table – head insertion method for single-linked lists

1.3.2.7 Traversing a single linked list

1.3.2.8 Clearing the single-linked list

1.3.2.9 Complete code for single linked list operation

Related Posts

Fundamentals of client development – mobile network

Technology sharing | audio and more channels using the correct posture

IOS into the advanced Shell script packaging automatic release chapter