Array list: remove - Revision history

Luedecke at 23:11, 19 June 2015

2015-06-19T23:11:06Z

← Older revision		Revision as of 23:11, 19 June 2015
Line 1:		Line 1:
			[[Category:Videos]]
			{{#ev:youtube\|https://www.youtube.com/watch?v=uYTck0kDvl4\|500\|right\|\|frame}}
	'''Algorithmic problem:''' [[Ordered sequence#Remove\|Ordered sequence: remove]]		'''Algorithmic problem:''' [[Ordered sequence#Remove\|Ordered sequence: remove]]

Weihe: /* Induction step */

2015-05-17T09:13:27Z

Induction step

← Older revision		Revision as of 09:13, 17 May 2015
Line 53:		Line 53:
	# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.		# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.

	'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.		'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>.next.n]<math>\}</math>.
	If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, <math>K</math> is overwritten and the array is rearranged accordingly in Step 2.2.		If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, <math>K</math> is overwritten and the array is rearranged accordingly in Step 2.2.

Weihe: /* Induction step */

2015-05-17T09:03:21Z

Induction step

← Older revision		Revision as of 09:03, 17 May 2015
Line 54:		Line 54:

	'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.		'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.
	If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, it is ~~removed~~ and the array is rearranged accordingly in Step 2.2.		If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, <math>K</math> is overwritten and the array is rearranged accordingly in Step 2.2.

	== Complexity ==		== Complexity ==

Weihe: /* Induction step */

2015-05-17T09:01:04Z

Induction step

← Older revision		Revision as of 09:01, 17 May 2015
Line 42:		Line 42:

	'''Implementation:'''		'''Implementation:'''
	# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .		# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return '''false'''.
	# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,<math>p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:		# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,<math>p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
	## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.		## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.
Line 50:		Line 50:
	### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.		### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.
	### Set <math>p</math>.next.n<math>:=p</math>.next.n <math>-1</math>.		### Set <math>p</math>.next.n<math>:=p</math>.next.n <math>-1</math>.
	## Terminate the algorithm and return ~~<math>~~true~~</math>~~.		## Terminate the algorithm and return '''true'''.
	# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.		# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.

Weihe: /* Induction step */

2015-05-17T09:00:17Z

Induction step

← Older revision		Revision as of 09:00, 17 May 2015
Line 49:		Line 49:
	### For <math>h=j,..,p</math>.next.n<math>-1</math> (in this order): Set <math>p</math>.next.A<math>[h]:=p</math>.next.A<math>[h+1]</math>.		### For <math>h=j,..,p</math>.next.n<math>-1</math> (in this order): Set <math>p</math>.next.A<math>[h]:=p</math>.next.A<math>[h+1]</math>.
	### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.		### Set <math>p</math>.next.A<math>[p</math>.next.n<math>]:=</math>void.
	### Set <math>p</math>.next.n<math>:=p</math>.next.n<math>-1</math>.		### Set <math>p</math>.next.n<math>:=p</math>.next.n <math>-1</math>.
	## Terminate the algorithm and return <math>true</math>.		## Terminate the algorithm and return <math>true</math>.
	# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.		# Otherwise (that is, <math>p</math>.next<math>\ne</math>void and <math>K\notin\{p</math>.next.A<math>[1],...,</math>.next.A[p.next.n]<math>\}</math>), set <math>p:=p</math>.next.

Weihe: /* Induction step */

2015-05-17T08:59:18Z

Induction step

← Older revision		Revision as of 08:59, 17 May 2015
Line 43:		Line 43:
	'''Implementation:'''		'''Implementation:'''
	# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .		# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .
	# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:		# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,<math>p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
	## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.		## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.
	## Otherwise:		## Otherwise:

Weihe: /* Induction step */

2015-05-17T08:58:35Z

Induction step

← Older revision		Revision as of 08:58, 17 May 2015
Line 43:		Line 43:
	'''Implementation:'''		'''Implementation:'''
	# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .		# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .
	# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:		# Otherwise, if <math>K \in \{p</math>.next.A[<math>1</math>],...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
	## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.		## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.
	## Otherwise:		## Otherwise:

Weihe: /* Induction step */

2015-05-17T08:55:55Z

Induction step

← Older revision		Revision as of 08:55, 17 May 2015
Line 54:		Line 54:

	'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.		'''Correctness:''' If <math>p</math>.next<math>=</math>void or <math>K\notin\{p</math>.next.A<math>[1],...,p</math>.next.A[first.n]<math>\}</math>, correctness is obvious. So consider the case that <math>p</math>.next<math>=</math>void and <math>K\in\{p</math>.next.A<math>[1],...,p</math>.next.A[<math>p</math>next.n]<math>\}</math>.
	If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so this list item ~~is decoupled~~ from the list ~~in Step 2.1~~. Otherwise, it is removed and the array is rearranged accordingly in Step 2.2.		If <math>p</math>.next.n<math>=1</math>, the array would be empty after removing <math>K</math>, so Step 2.1 is right to decouple this list item from the list. Otherwise, it is removed and the array is rearranged accordingly in Step 2.2.

	== Complexity ==		== Complexity ==

Weihe: /* Induction step */

2015-05-17T08:55:02Z

Induction step

← Older revision		Revision as of 08:55, 17 May 2015
Line 44:		Line 44:
	# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .		# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .
	# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:		# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
	## If <math>p</math>.next.n<math>=1</math>, set .<math>p</math>next<math>:=</math>.next.next.		## If <math>p</math>.next.n<math>=1</math>, set <math>p</math>.next<math>:=</math>.next.next.
	## Otherwise:		## Otherwise:
	### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.		### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.

Weihe: /* Induction step */

2015-05-17T08:54:43Z

Induction step

← Older revision		Revision as of 08:54, 17 May 2015
Line 44:		Line 44:
	# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .		# If <math>p</math>.next<math>=</math>void, terminate the algorithm and return .
	# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:		# Otherwise, if <math>K \in \{p</math>.next<math>,...,p</math>.A.next.A[<math>p</math>.next.n]<math>\}</math>:
	## If <math>p</math>.next.n<math>=1</math>, set .<math>p</math>next<math>p:=</math>.next.next.		## If <math>p</math>.next.n<math>=1</math>, set .<math>p</math>next<math>:=</math>.next.next.
	## Otherwise:		## Otherwise:
	### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.		### Let <math>j \in \{1,...,p</math>.next.n<math>\}</math> such that <math>p</math>.next.A.<math>[j]=K</math>.