資料結構線性表操作與例題總結

2. 所有鏈表操作前先判斷是否為空if (first->next == NULL)return;

1. 設有一個整數順序表，撰寫函式將其調整為奇數在前，偶數在后，

思路為left從表頭出發找到第一個偶數，right從表尾出發，找到第一個奇數，若此時left<right則交換兩個元素
簡化了答案的操作，方便理解與記憶，

void revise(int a[], int n)
{
	int left = 0;
	int right = n - 1;
	int tmp = 0;
	while (left < right)
	{
		while (a[right] % 2 == 0) right--;//右側掃描
		while (a[left] % 2 != 0) left++;//左側掃描

		if (left < right)
		{
			tmp = a[left];
			a[left] = a[right];
			a[right] = tmp;
		}
	}
}

要注意while回圈掃描的判斷條件是滿足條件“指標”移動

2)調整為負數在前，正數在后，

只需將取余為零的判斷條件，修改為大于0或小于0

void revise(int a[], int n)
{
	int left = 0;
	int right = n - 1;
	int tmp = 0;
	while (left < right)
	{
		while (a[right] >= 0) right--;//右側掃描
		while (a[left] <= 0) left++;//左側掃描

		if (left < right)
		{
			tmp = a[left];
			a[left] = a[right];
			a[right] = tmp;
		}
	}
}

3)在單鏈表中實作，

1.交換資料版

void LinkList::revise()
{
  if (first->next == NULL)return;
	Node* p = first->next;
	Node* q = p->next;
	int temp = 0;
	while (q != NULL && p != NULL)
	{
		while (q&&q->data % 2 == 0)q = q->next;
		while (p&&p->data % 2 != 0)p = p->next;

		if (q != NULL && p != NULL)
		{
			temp = q->data;
			q->data = p->data;
			p->data = temp;
		}
	}
}

2. 交換節點版

思路為：
將鏈表打散，用兩個指標分別存盤新的兩個鏈表

例如：當第一個節點為奇數則將其鏈接道odd后面

第三個節點為偶數：將其鏈接道even后面

void LinkList::revise() {
if (first->next == NULL)return;
	Node* work = first->next;//帶頭結點的形式（這里指向第一個節點）
	Node* odd_first = new Node;//生成頭節點
	Node* even_first =new Node;
	Node* odd = odd_first;
	Node* even= even_first;

	
	while (work!=NULL)
	{
	//若為奇數，添加到奇數指標后
		if (work->data % 2 != 0) {
			odd->next = work;
			odd = odd->next;
		}
		else
		{
			even->next = work;
			even = even->next;
		}
		work = work->next;
	}
	even->next = NULL;//最后一個節點置空
	odd->next = even_first->next;
	delete even_first;
	first = odd_first;//注意這里有頭節點
}

2.撰寫函式oddevenList把不帶頭結點的單鏈表中所有奇數編號的結點調整到所有偶數編號的結點前面，

思路同上面的題，代碼只是判斷條件改變

void LinkList::revise() {

   if (first->next == NULL)return;
	Node* work = first->next;//帶頭結點的形式（這里指向第一個節點）
	Node* odd_first = new Node;//生成頭節點
	Node* even_first =new Node;
	Node* odd = odd_first;
	Node* even= even_first;
	int i = 1;
	
	while (work!=NULL)
	{
		if (i % 2 != 0) {
			odd->next = work;
			odd = odd->next;
		}
		else
		{
			even->next = work;
			even = even->next;
		}
		work = work->next;
		i++;
	}
	even->next = NULL;
	odd->next = even_first->next;
	delete even_first;
	first = odd_first;

}

3.設計一個在帶頭結點的單鏈表中洗掉一個最小值結點的高效演算法，

思路:
設立一個作業指標q，負責遍歷鏈表（在訪問元素的前一個節點，方便后續洗掉節點）；另外一個p用于指向最小節點前面一個節點

void LinkList::delmin() {
	Node* p, * q;
	if (first->next == NULL)   return;
	p = first;//p存放最小節點的前一個
	q = first->next;

	while (q->next != NULL)
	{
	    //若該節點比最小值節點要小，則更換
		if (q->next->data <p->next->data)
		{
			p = q;
		}
		q = q->next;
	}
     //現在p指向的為最小節點的前一個節點
    Node* temp = p->next;
	p->next = temp->next;
	delete temp;
	//若不需要洗掉該節點只需：
	//p->next = p->next->next;
}

4.設計一個演算法，在帶頭結點的單鏈表中洗掉值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個引數，其值可以和表中的元素相同，也可以不同），

思路：
兩個指標同步移動，p在前q在后，q來識別是否滿足洗掉條件，若滿足，p將q架空，并洗掉q所指節點，洗掉后將q歸位至p節點的后面；若不滿足條件，兩個指標同步后移，

void LinkList::del(int mink, int maxk)
{
	Node* p = first;
	Node* q = first->next;
	while (q!=NULL)
	{
		if (q->data > mink&& q->data < maxk)
		{
			p->next = q->next;//把q架空
			delete q;
			q = p->next;
		}
		else {
			//整體后移
			q = q->next;
			p = p->next;	
		}

	}
}

5. 撰寫函式查找帶頭結點的單鏈表中倒數第4個元素，

思路：
設定兩個指標，相差3個節點，同步移動，當p2成為NULL后p1的位置即為倒數第四個節點

要注意的是p1向前移動的判斷條件為p1->next != NULL，否則若正好三個節點，p1將指向NULL，沒有指向第四個節點，但此時只有三個節點，不滿足條件

int LinkList::findLast4th()
{
	Node* p1 = first;
	Node* p2 = first;
	//p1先走4步，
	for (int i = 0; i < 4; i++)
	{
		if (p1->next != NULL)
		{
			p1 = p1->next;
		}
		else
		{
			cout << "鏈表長度不夠" << endl;
			return false;//鏈表長度不夠
		}
	}
	//同步移動
	while (p1 != NULL)
	{
		p1 = p1->next;
		p2 = p2->next;
	}
	return p2->data;

}

6. 設采用兩個遞增有序的單鏈表分別表示A和B，撰寫函式生成新的單鏈表C，其中C=A∩B，

思路:
1.初始化

2. pa、pb向后移動的程序中，判斷pa和pb所指向的值是否相等
3. 若值相等，pCEnd后增加節點，將pa、pb同時向后移動一位，
4. 若pa->data< pb->data則,pa向后移動一位，
5. 若pa->data> pb->data則,pb向后移動一位，
6. 最后將pCEnd->next=NULL;完成鏈表構造

Node* intersection(Node* pA, Node* pB)
{
	Node* pa = pA->next;
	Node* pb = pB->next;
	Node* pCHead = new Node;  //A與B交集頭指標
	Node* pCEnd = pCHead;  //A與B交集尾指標
	
	while (pa!=NULL&&pb!=NULL)
	{
		if (pa->data<pb->data)
		{
			pa = pa->next;
		}
		//相等則鏈表向后拓展一位
		else if (pa->data == pb->data)
		{
			Node* s = new Node;
			s->data = pa->data;
			pCEnd->next = s;
			pCEnd = s;
			//遇到相同的元素后都向后移動一個位置
			pa = pa->next;
			pb = pb->next;
		}
		//pa->data<pb->data的情況
		else {
			pb = pb->next;
		}
	}
	pCEnd->next = NULL;
	return pCHead;

}