Array structure of data structure and algorithm

Data structure and algorithm (1) array structure

I Basic use of arrays

Create and initialize arrays

It is easy to declare, create, and initialize arrays in JavaScript, as follows:

//Create and initialize arrays
let daysOfWeek = new Array();
let daysOfWeek = new Array(7);
let daysOfWeek = new Array('Sunday','Moday','Tuesday','Wednesday','Thursday','Friday','Saturday');

Code parsing:
- Using the new keyword, you can simply declare and initialize an array
- In this way, you can also create an array of a specified length
- In addition, you can directly pass array elements as parameters to its constructor
- Creating arrays with new is not the best way. If you want to create an array in JavaScript, just use the form of brackets ([])

Create an array using brackets ([]):

let daysOfWeek = new Array('Sunday','Moday','Tuesday','Wednesday','Thursday','Friday','Saturday');

Array length and traversal array

If we want to get the length of the array, we have a length attribute
```
//Gets the length of the array
alert(daysOfWeek.length)
```

You can also traverse the array by subscript value:

//The normal for method traverses the array
for(let i = 0;i<daysOfWeek.length;i++){
	alert(daysOfWeek[i])
}

//Traversing arrays through foreach
daysOfWeek.forEach(function (value){
    alert(value)
})

Let's do an exercise:
- Find the first 20 numbers of Fibonacci sequence and put them in the array.
- Fibonacci sequence the first number of the sequence is 1, the second number is also 1, and the third term is the sum of the first two terms
```
//Find the first 28 digits of Fibonacci sequence
let fibonac = [];
fibonac[0] = 1;
fibonac[1] = 1;

for(let i = 2;i < 20;i++){
    fibonac[i] = fibonac[i-1] + fibonac[i - 2];
}
alert(fibonac);
```

II Common operations for arrays

The common operations in an array are: adding elements, deleting elements, modifying elements, and obtaining elements

Add element

In JavaScript, the above operations are relatively simple, because the language itself has encapsulated these features.

Suppose we have an array: numbers, initialize 0 ~ 9

// Initialize an array
let numbers = [0,1,2,3,4,5,6,7,8,9];

Add an element to the last position of the array:

// Adds an element to the last position of the array
// Mode 1:
numbers[numbers.length] = 10;

// Mode 2:
numbers.push(11);
numbers.push(12,13)

alert(numbers);

Insert an element at the beginning of the array:

// Insert an element at the beginning of the array
for(let i = numbers.length;i > 0;i--){
	numbers[i] = numbers[i-1]
}
numbers[0] = -1
alert(numbers) // -1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

What is the principle of the above code implementation?
Consider the performance of the above code implementation?
- The performance is not very high
- This is also a disadvantage of array compared with linked list: the efficiency of inserting elements in the middle is lower than that of linked list

Of course, we can directly use the unshift method to insert data at the beginning of the array

// Insert data in the first place by unshift
numbers.unshift(-2);
numbers.unshift(-4,-3);
alert(numbers) // -4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

Delete element

If you want to delete the last element of the array, you can use the pop() method

// Delete last element
numbers.pop()
alert(numbers) //-4,-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12

If we want to remove the first element of:

// Delete the first element
for(let i = 0;i < numbers.length;i++){
	numbers[i] = numbers[i+1]
}
numbers.pop();
alert(numbers); //-3,-2,-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13

Of course, we can directly use the shift method to achieve:
```
numbers.shift()
alert(numbers)
```

Any position

Anywhere?
- What we learned earlier is to add and delete data at the beginning and end of the array
- What if we want to do something in the middle of the array?
On the one hand, we can encapsulate such functions ourselves, but JS has provided us with a splice method

Delete data through splice

// Delete several elements at the specified location
numbers.splice(5,3);
alert(numbers); // -4,-3,-2,-1,0,4,5,6,7,8,9,10,11,12,13

Code parsing:
- The above code will delete the elements with indexes 5, 6 and 7.
- The first parameter indicates that the starting position of the index is 5 (actually the sixth element, because the index starts from 0), and 3 elements are deleted.

What if we want to use splice to insert data?

// Inserts the element at the specified location
numbers.splice(5,3,3,2,1);
alert(numbers); //-4,-3,-2,-1,0,3,2,1,4,5,6,7,8,9,10,11,12,13

Code parsing:
- The above code will modify the data from the position of index 5. How many? The second parameter.
- The first parameter is still the index at position 5 (the sixth position)
- The second parameter is the number of elements in the array to be replaced. Here are three (you can also use three elements to replace two. You can try it yourself)
- Followed by the element to be replaced.

III Other operations on arrays

JavaScript has added many methods to facilitate data manipulation

Common methods

Let's take a brief look at the common methods

Method name	Method description
concat	Connect 2 or more arrays and return results
every	Run the given function for each item in the array. If the row returns true for each item, it returns true. Otherwise, it returns false
filter	Run the given function on each item in the array, and returning the function will return an array of true items
forEach	Runs the given function on each item in the array. This method has no return value
join	Concatenate all array elements into a string
indexOf	Returns the index of the first array element equal to the given parameter, or - 1 if not found
lastIndexOf	Returns the largest value in the index of the element found in the array equal to the given parameter
map	Run the given function on each item in the array and return an array composed of the results of each function call
reverse	Reverse the order of the elements in the array. The original first element is now the last, and the original last element is now the first
slice	Pass in the index value and return the elements within the corresponding index range in the array as new elements
some	Run the given function for each item in the array. If any item returns true, the result is true and the iteration ends
sort	Sorting by comparison with alphabetic order group supports the function of specifying sorting method as parameter
toString	Returns an array as a string
valueOf	Similar to toString, an array is returned as a string

Array merge

The merging of arrays is very simple. You can use concat (or directly + to merge)

// Merging of arrays
let nums1 = [1,2,3]
let nums2 = [100,200,300]
let newNums = nums1.concat(nums2)
alert(newNums) // 1,2,3,100,200,300

newNums = nums1 + nums2
alert(newNums) // 1,2,3,100,200,300

Iterative method

To facilitate array manipulation, JS provides many iterator methods:
every() method
- The every() method passes each element in the array into a function that returns true/false
- If each element in the function returns true and one is false, the result is false
- Exercise: determine whether a set of elements contains a character
```
// Define array
let names = ["abc","cb","mba","dna"]

// Determine whether the elements of the array contain the a character
let flag = names.every(function(t){
	return t.indexOf('a') != -1
})
alert(flag)
```

some() method

The some() method passes each element in the array into a function that returns true/false
But unlike every, once a function returns true, the iteration ends and the result is true
practice:

// Define array
let names = ["abc","cb","mba","dna"]

// Determine whether the array contains a character
let flag = names.some(function(t){
  alert(t);
  return t.indexOf("a") != -1;
})
alert(flag)

forEach() method
- The forEach() method is just a quick way to iterate over arrays
- This method does not need to return a value
- use
```
// Define array
let names = ["abc","cb","mba","dna"];

// Use of forEach
names.forEach(function(t){
		alert(t)
})
```
filter() method
- The filter() method is a filter function
- First, each element in the array will be traversed and passed into the function
- If the result of the function returns true, the element will be added to the latest array. If it returns false, the element will be ignored.
- Finally, a new array will be formed, which is the return value of the filter() method
- practice:
```
  // Define array
  let names = ["abc","cb","mba","dna"]
  
  // Gets all elements in names that contain the 'a' character
  let newNames = names.filter(function (t){
    return t.indexOf("a") !=-1
  })
  alert(newNames)
```
map() method
- The map() method provides a mapping function
- First, each element in the array will be traversed and passed into the function
- The element will undergo various transformations through the instructions in the function to generate a new element, and the new element and the new element will be returned
- Finally, all the returned elements will form a new array, which is the return value of the map() method
- practice:
```
  // Define array
  let names = ["abc","cb","mba","dna"]
  
  // Splice - abc after all elements in names
  let newNames = names.map(function(t){
  	return t + "-abc"
  })
  alert(newNames)
```

reduce method

We take out the reduce method alone, because this method is relatively difficult to understand
First, let's look at the parameters required for this method:
```
arr.reduce(callback[,initialValue])
```
parameter
- Callback (a function that calls a callback on each item in the array and accepts four functions:)
  - previousValue (return value or initial value when the callback function was last called)
  - currentValue (array element currently being processed)
  - currentIndex (index of array element currently being processed)
  - Array (array calling the reduce() method)
- initialValue (optional initial value. As the value passed to previousValue when the callback function is called for the first time)
Some are obscure. Let's look at the examples directly
- Find the cumulative sum of a number
- Use for to implement:
```
// Define array
let numbers = [1,2,3,4]

// for realize accumulation
let total = 0
for(let i = 0;i<numbers.length;i++){
	total += numbers[i]
}
alert(total) // 10
```
- Simplify the for loop with forEach
  - Compared with the for loop, forEach is more in line with our thinking (traversing the elements in the array)
```
// Using forEach
let total = 0
numbers.forEach(function(t){
	total += t
})
alert(total)
```
- Using the reduce method
```
// Using the reduce method
let total = numbers.reduce(function(pre,cur){
	return pre + cur
})
alert(total)
```
  Code parsing:
  - The parameters passed in each time in pre are not fixed, but the results of the last function execution are saved in pre
  - For the first execution, pre is 0 and cur is 1
  - In the second execution, pre is 1 (0 + 1, the result of the last function execution), and cur is 2
  - In the third execution, pre is 3 (1 + 2, the result of the last function execution), and cur is 3
  - In the fourth execution, pre is 6 (3 + 3, the result of the last function execution), and cur is 4
  - When cur is 4, after traversing the elements in the array, the fourth result is directly returned as the return value of the reduce function.
- Doesn't seem to have much advantage over forEach?
  - Through this code, you will find that you do not need to define a variable before calling the function, but only need a variable to accept the method.
  - But is that the advantage? No, the advantage is that the reduce method has a return value, but forEach does not.
  - Is that an advantage? If the reduce method has a return value, the reduce method itself can be directly passed as a parameter to another function that needs the return value of reduce as a parameter. In forEach, you can only save the result of each function in a variable, and then pass the variable into the parameter.
  - Yes, this is the very popular functional programming recently. It is also the reason that almost every language that can use functional programming has the method of reduce.
  - Functional programming is not discussed in this course. I just saw this function and extended it to you.
- Do you need to talk about initialValue?
  - In fact, it is the value of pre when the function in reduce is executed for the first time.
  - Because the default pre is 0.0 when it is first executed

Keywords: Javascript Algorithm data structure

Added by stvs on Tue, 18 Jan 2022 15:43:15 +0200

Programming VIP

Array structure of data structure and algorithm

Data structure and algorithm (1) array structure

I Basic use of arrays

Create and initialize arrays

Array length and traversal array

II Common operations for arrays

Add element

Delete element

Any position

III Other operations on arrays

Common methods

Array merge

Iterative method

every() method

Exercise: determine whether a set of elements contains a character

some() method

practice:

forEach() method

use

filter() method

practice:

map() method

practice:

reduce method

Popular Keywords