Algo lab/linked lists - ประวัติรุ่นแก้ไข

Jittat: /* Array implementation */

2018-09-09T22:32:21Z

Array implementation

2018-09-09T22:31:50Z

A list of colored balls

2018-09-09T22:31:35Z

Linked lists

2018-09-09T22:31:11Z

Implementations

2018-09-09T22:29:17Z

Array implementation

2018-09-09T22:27:03Z

Array implementation

2018-09-09T22:26:16Z

Array implementation

2018-09-09T22:22:34Z

Array implementation

2018-09-09T22:07:15Z

Array implementation

2018-09-09T22:00:55Z

A list of colored balls

@@ แถว 80: / แถว 80: @@
 === Array implementation ===
-The easiest way to implement lists is to use ''arrays'''.  For this Zooma1 problem, we have to maintain a list of ball numbers.  We can do so by having a large enough array and a size counter.
+The easiest way to implement lists is to use ''arrays''  For this [[Algo lab/zooma 1|Zooma1]] problem, we have to maintain a list of ball numbers.  We can do so by having a large enough array and a size counter.
 <syntaxhighlight lang="cpp">

@@ แถว 74: / แถว 74: @@
 We will look at the simpler version of the game, where we can shoot the balls, but the balls remain in the list. In this tasks, there are '''n''' enemy colored balls and you want to shoot m colored balls. To be precise, the enemy balls are referred to as ball '''1''' to ball '''n''', and the balls you will shoot are referred to as ball '''n+1''' to ball '''n+m'''. For each of your '''i'''-th ball, for '''1≤i≤m''' you shoot into the list, it will land right after ball '''p[i]'''. (Note that '''i''' here is not referring to the ball numbers, as your '''i'''-th ball is numbered '''n+i'''.) You want to know the final list of balls.
-Related task: [[Algo lab/zooma 1|Zooma 1]]
+: '''Related task: [[Algo lab/zooma 1|Zooma 1]]'''
 One can deal with this task by just simulating the system and output the final result. Starting with a list of '''n''' numbers from '''1''' to '''n'''. We iterate the array '''p[i]''' and insert ball number '''n+1''' into the sequence right after '''p[i]'''. To do so, we need to look up where '''p[i]''' is in the sequence and insert '''i+n''' right after it.

@@ แถว 129: / แถว 129: @@
 == Implementations: array-based lists ==
-== Linked lists ==
+== Implementations: linked lists ==
 === typedef ===

@@ แถว 127: / แถว 127: @@
 We will learn a new data structure that can speed up the solution to run in time '''O(n+m)'''.
-== Implementations ==
+== Implementations: array-based lists ==
-=== Array-based lists ===
+== Linked lists ==
-=== List nodes ===
+=== typedef ===
 In C++, you can simply declare a new type based on known types using <tt>typedef</tt>.
@@ แถว 143: / แถว 141: @@
 We will declare new <tt>valueType</tt> so that our linked list code works fairly well with any types.  We will eventually use '''template''' to make generic linked list.
-==== struct ====
+=== struct ===
 <source lang="cpp">
 struct ListNode

@@ แถว 121: / แถว 121: @@
 </syntaxhighlight>
-We will learn a new data structure that can speed up the solution to run in time '''O(n)'''.
+=== Running time ===
 == Implementations ==

@@ แถว 91: / แถว 91: @@
 To solve zooma1, we need the following list operations:
-* <tt>insert_end</tt> - add an integer to the end of the list
+* <tt>insert_end(int lst[], int& s, int val)</tt> - add an integer to the end of the list
-* <tt>find</tt> - find a target location in the list
+* <tt>find(int lst[], int s, int target)</tt> - find a target location in the list
-* <tt>insert</tt> - add an integer to a particular location on the list
+* <tt>insert(int lst[], int& s, int val, int loc)</tt> - add an integer to a particular location on the list
 With these functions, we can implement the main function for solving zooma1 as follows.

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 22:26, 9 กันยายน 2561
แถว 79:		แถว 79:

	=== Array implementation ===		=== Array implementation ===
		+
		+	The easiest way to implement lists is to use ''arrays'''. For this Zooma1 problem, we have to maintain a list of ball numbers. We can do so by having a large enough array and a size counter.
		+
		+	<syntaxhighlight lang="cpp">
		+	const int MAX_N = 2000100;
		+
		+	int balls[MAX_N];
		+	int ball_count = 0;
		+	</syntaxhighlight>
		+
		+	To solve zooma1, we need the following list operations:
		+
		+	* <tt>insert_end</tt> - add an integer to the end of the list
		+	* <tt>find</tt> - find a target location in the list
		+	* <tt>insert</tt> - add an integer to a particular location on the list
		+
		+	With these functions, we can implement the main function for solving zooma1 as follows.

	<syntaxhighlight lang="cpp">		<syntaxhighlight lang="cpp">