XIAOSUO 记录个人学习的足迹

这篇文章是一些与线性表相关的算法

1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。

2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。

3.编写一个单链表逆置算法。

4.找出单链表的中间元素。

1.如果顺序表中每个元素都是整数，设计用最少时间把所有值为负数的元素放在全部正数值元素的前面。

分析：从左向右找到正数，从右到左找到负，将两者交换。循环直到 i 大于 j 为止。

public void Move(int[] list)
{
	int i = 0, j = list.Length;
	int temp;
	while (i <= j)
	{
		while (list[i] <= 0) i++;
		while (list[j] >= 0) j--;
		if (i < j)
		{
			temp = list[i];
			list[i] = list[j];
			list[j] = temp;
		}
	}
}

注意：①“用最少的时间”一词，②只要求将负数的元素移动到全部正数的前面。

2.如果顺序表为非递减有序排列，试删除顺序表中多余的值相同的元素。

分析：由于顺序表是非递减有序排序，值相同的元素必为相邻的元素，因此依次比较相邻两个元素，若值相等则删除其中一个，否则继续向后查找。

public void Delete(int[] list)
{
	int i = 0, j, len = list.Length;
	while (i < len - 1)
	{
		if (list[i] != list[i + 1])
		{
			i++;
		}
		else
		{
			for (j = i; j < len; j++)
			{
				list[j] = list[j + 1];
			}
		}
	}
}

注意：顺序表删除一个元素的实现方法。

3.编写一个单链表逆置算法。

分析：我们需要额外的两个变量来存储当前节点curr的下一个节点next、再下一个节点nextnext；

public static Link Reverse(Node<T> head)
{
	Node<T> curr = head.Next;
	Node<T> next = null;
	Node<T> nextnext = null;
	if (curr == null || curr.Next == null)
	{
		return head;
	}

	while (curr.Next != null)
	{
		next = curr.Next;       //1
		nextnext = next.Next;   //2
		next.Next = head.Next;  //3
		head.Next = next;       //4
		curr.Next = nextnext;   //5
	}
	return head;
}

注意：出于编程的严谨性，还要考虑2种极特殊的情况：没有元素的单链表，以及只有一个元素的单链表，都是不需要反转的。

4.找出单链表的中间元素。

分析： 使用两个引用first和second，只是first每次走两步，second每次走一步

public Node<T> GetMiddleOne(Node<T> head)
{
	Node<T> first = head;
	Node<T> second = head;
	while (first != null && first.Next != null)
	{
		first = first.Next.Next;
		second = second.Next;
	}
	return second;
}

这里有个地方需要注意，就是对于链表元素个数为奇数，以上算法成立。如果链表元素个数为偶数，那么在返回second的同时，还要返回second.Next也就是下一个元素，它俩都算是单链表的中间元素。下面的方法无论奇数偶数，一概通杀：

public Node<T> GetMiddleOne(Node<T> head, ref bool isOdd)
{
	Node<T> first = head;
	Node<T> second = head;
	while (first != null && first.Next != null)
	{
		first = first.Next.Next;
		second = second.Next;
	}
	if (first != null)
		isOdd = false;
	return second;
}

最后在得到该方法的返回值后，判断isOdd。如果是True，那么second为所求；如果不是second与second.Next都为所求。