天天看點
傳回

【王道408資料結構】線性表習題Seqlist

Seqlist

  • P18開始的習題
  • 算法真美妙
  • 不保證正确，歡迎讨論，本質是僞代碼，隻是一個思路，實作還需要考慮一些細節

文章目錄

  • Seqlist
    • 1. 删除最小元素
    • 2. 順序表逆置
    • 3. 删除所有值為x的元素
    • 4. 删除範圍元素
    • 5. 删除範圍元素(與第四題相似)
    • 6. 删除重複元素
    • 7. 合并兩個有序數組
    • 8. 兩個連結清單換位
    • 9. 二分查找
    • 10. [2010統考真題]循環移動
    • 11. [2011統考真題]找兩個順序表合并的中位數
    • 12. [2013統考真題]出現超過一半的元素
    • 13. [2018統考真題] 數組未出現最小正整數
    • 14. [2020統考真題]三元數組最小距離

1. 删除最小元素

從順序表中删除具有最小值的元素( 假設唯一)并由函數傳回被删元素的值。空出的位置由最後一個元素填補，若順序表為空，則顯示出錯資訊并退出運作。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

//算法思路：周遊順序表，如果比value小，value就等于它，并且記錄該資料的下标，最後将最後一個字元與之交換
bool Del_Min(SL& ps, SLDateType& value)
{
	//如果為空，傳回錯誤
	if (ps.size == 0)
	{
		return false;
	}
	//記錄數組下标
	size_t index = 0;
	for (size_t i = 0; i < ps.size; i++)
	{
		//如果比value小指派給value
		if (value > ps.a[i])
		{
			value = ps.a[i];
			index = i;
		}
	}
	//交換
	//ps.a[index] = ps.a[ps.size - 1];
	//這裡template <class T> void swap (T& a, T& b);
	swap(ps.a[index], ps.a[ps.size - 1]);
	ps.size--;
	return true;
}

2. 順序表逆置

設計一個高效算法，将順序表L的所有元素逆置，要求算法的空間複雜度為0(1)。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

//算法思路：兩個指針指向left和right，向中間首尾交換，直到相遇
void Reverse(SL& ps)
{
	size_t left = 0;
	size_t right = ps.size - 1;

	//直到中間相等或者right比left大退出循環
	while (left < right)
	{
		//交換
		swap(ps.a[left], ps.a[right]);
		//向中間移動
		left++;
		right--;
	}
}

3. 删除所有值為x的元素

對長度為n的順序表L，編寫一個時間複雜度為0(n)、空間複雜度為0(1)的算法，該算法删除線性表中所有值為x的資料元素。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

//算法思路：周遊，一個指針遇到x停下，另一個指針尋找不是x元素的數值，将該值指派給該位置。
void Del_Value(SL& ps, SLDateType x)
{
	//記錄可以替換的位置
	int cur = 0;
	//尋找x元素
	int index = 0;

	while(index < ps.size -1)
	{
		if (ps.a[index] != x)
		{
			ps.a[cur] = ps.a[index];
			cur++;
		}
		//遇到相等的時候cur停止移動，而index繼續右移動，将數值指派給cur（覆寫掉x）
		index++;
	}

	ps.size = cur;
}

4. 删除範圍元素

從有序順序表中删除其值在給定值s與t之間(要求s<t)的所有元素，若s或t不合理或順序表為空，則顯示出錯資訊并退出運作。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*算法思路：
和第三題差不多，遇到s-t範圍内k++,
範圍外将其指派給該位置減去k，最終數組最後k個數就是s-t中數組
*/

bool Del_ValueRange(SL& ps, const SLDateType& s, const SLDateType& t)
{
	//s和t不合法，數組為空
	if (s >= t || ps.size == 0)
	{
		return false;
	}

	size_t k = 0;
	for (size_t i = 0; i < ps.size; i++)
	{
		if (ps.a[i] > s && ps.a[i] < t)
		{
			k++;
		}
		else
		{
			ps.a[i - k] = ps.a[i];
		}
	}

	ps.size -= k;

	return true;
}

5. 删除範圍元素(與第四題相似)

從順序表中删除其值在給定值s與t之間(包含s和t,要求s<t)的所有元素，若s或t不合理或順序表為空，則顯示出錯資訊并退出運作。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>

using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*算法思路：
和第三題差不多，遇到s-t範圍内k++,
範圍外将其指派給該位置減去k，最終數組最後k個數就是s-t中數組
*/

bool Del_ValueRange(SL& ps, const SLDateType& s, const SLDateType& t)
{
	//s和t不合法，數組為空
	if (s >= t || ps.size == 0)
	{
		return false;
	}

	size_t k = 0;
	for (size_t i = 0; i < ps.size; i++)
	{
		if (ps.a[i] >= s && ps.a[i] =< t)
		{
			k++;
		}
		else
		{
			ps.a[i - k] = ps.a[i];
		}
	}

	ps.size -= k;

	return true;
}

6. 删除重複元素

從有序順序表中删除所有其值重複的元素，使表中所有元素的值均不同。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*算法思路：
記錄cur和index，index記錄尋找和cur不同的數組元素下标；
如果cur等于index，index++；
如果cur不等于index，cur++,cur=index,index++；
index無論在哪種情況都需要++,是以index可以為for循環的i
*/

void Del_Dup_Ele(SL& ps)
{

	size_t cur = 0;

	for (size_t i = 0; i < ps.size - 1; i++)
	{
		if (ps.a[cur] != ps.a[i])
		{
			cur++;
			ps.a[cur] = ps.a[i];
		}
	}

	ps.size = cur;

}

7. 合并兩個有序數組

将兩個有序順序表合并為一個新的有序順序表，并由函數傳回結果順序表。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*算法思路：
ps3存放，分别周遊ps1和ps2，小的先賦給ps3
*/

bool Merge_Ordered_List(const SL& ps1, const SL& ps2, SL& ps3)
{
	if (ps1.size + ps2.size > ps3.size)
	{
		return false;//放不下
	}

	int i = 0;
	int j = 0;
	int k = 0;

	while (i < ps1.size && j < ps2.size)
	{
		if (ps1.a[i] < ps2.a[j])
		{
			ps3.a[k++] = ps1.a[i++];
		}
		else
		{
			ps3.a[k++] = ps2.a[j++];
		}
	}

	while (i < ps1.size)
	{
		ps3.a[k++] = ps1.a[i++];
	}

	while (j < ps2.size)
	{
		ps3.a[k++] = ps2.a[j++];
	}

	ps3.size = k;
	return true;
}

8. 兩個連結清單換位

已知在一維數組A[m + n]中依次存放兩個線性表(an, a2, a… am)和(b, b2, b3…… bn)。編寫一

個函數，将數組中兩個順序表的位置互換,即将(b1, b2, b3… bn,)放在(a1, a2, a3…… am)的前面。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*
算法思路：
a表逆置，b表逆置，整個連結清單逆置
*/

void Reverse_List(SLDateType* a, int sz)
{
	int begin = 0;
	int end = sz - 1;
	while (begin < end)
	{
		swap(a[begin], a[end]);
	}
}

void Dul_List_Swap_Position(SL& pl, int m, int n)
{
	Reverse_List(pl.a, m);
	Reverse_List(pl.a + m, n);
	Reverse_List(pl.a, m + n);

}

9. 二分查找

線性表(a1, a2, a3…… an)中的元素遞增有序且按順序存儲于計算機内。要求設計一個算法,完成用最少時間在表中查找數值為x的元素，若找到，則将其與後繼元素位置相交換,若找不到，則将其插入表中并使表中元素仍遞增有序。 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*
算法思路：
尋找中間數，如果比x大找右邊，比x小，找左邊
在按照這個思路繼續查找
*/


void Binary_Search(SL& pl, SLDateType x)
{
	int left = 0;
	int right = pl.size;
	int mid = (left + right) / 2;

	while (left <= right)
	{
		if (x > pl.a[mid])
		{
			left = mid + 1;
			mid = (left + right) / 2;
		}

		if (x < pl.a[mid])
		{
			right = mid - 1;
			mid = (left + right) / 2;
		}

		//找到了
		if (pl.a[mid] == x)
		{
			break;
		}
	}
	
	if (pl.a[mid] == x && mid != pl.size - 1)
	{
		swap(pl.a[mid], pl.a[pl.size - 1]);
	}
	else
	{
		for (int i = pl.size - 1; i > mid ; i--)
		{
			pl.a[i + 1] = pl.a[i];
		}
		pl.a[mid + 1] = x;
	}
}

10. [2010統考真題]循環移動

設将n (n> 1)個整數存放到一維數組R中。設計一個在時間和空間兩方面都盡可能高效的算法。将R中儲存的序列循環左移p(0<p<n)個位置，即将R中的資料由(X0, X1, Xn-1)變換為(Xp, Xp+1,……X0, X1,Xp-1)

要求:

1)給出算法的基本設計思想。

2)根據設計思想，采用C或C+或Java語言描述算法，關鍵之處給出注釋。

3)說明你所設計算法的時間複雜度和空間複雜度。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*
算法思路：
a表逆置，b表逆置，整個連結清單逆置
時間複雜度：On 空間複雜度O1
*/

void Reverse_List(SLDateType* a, int sz)
{
	int begin = 0;
	int end = sz - 1;
	while (begin < end)
	{
		swap(a[begin], a[end]);
	}
}

void Dul_List_Swap_Position(SL& pl, int m, int n)
{
	Reverse_List(pl.a, m);
	Reverse_List(pl.a + m, n);
	Reverse_List(pl.a, m + n);

}

11. [2011統考真題]找兩個順序表合并的中位數

一個長度為L (L≥1) 的升序序列s,處在第[L/2]個位置的數稱為s的中位數。例如，若序列S1=(11,13,15,17,19),則S的中位數是15, 兩個序列的中位數是含它們所有元素的升序序列的中位數。例如，若S2=(2, 4, 6, 8, 20),則S;和S2的中位數是11.現在有兩個等長升序序列A和B,試設計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數。要求:

1)給出算法的基本設計思想。

2)根據設計思想，采用C或C++或Java語言描述箕法，關鍵之處給出注釋。

3)說明你所設計算法的時間複雜度和空間複雜度

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*
算法思路：
類似兩個連結清單合并成一個連結清單

時間複雜度：On 空間複雜度O1
*/

/*

int Find_Mid(SL& p1, SL& p2)
{
	int i = 0;
	int j = 0;
	int len = (p1.size + p2.size)/2;
	int x = 0;
	while (i < p1.size && j < p2.size)
	{
		if (p1.a[i] < p2.a[j])
		{
			i++;
			x = p1.a[i];
		}
		else
		{
			j++;
			x = p1.a[i];
		}

		if (i + j == len)
		{
			break;
		}
	}
	
	return x;
}

*/


/*
算法思路：
分别查找兩個數組的中位數
a = b，則為中位數
a < b, 中位數在 a的數組右邊，b的左邊
a > b, 反之
最後分别剩1個數，較小為中位數
*/

int Find_Mid(SL& p1, SL& p2)
{
	int left1 = 0;
	int right1 = p1.size - 1;
	int mid1 = (left1 + right1) / 2;
	int left2 = 0;
	int right2 = p1.size - 1;
	int mid2 = (left2 + right2) / 2;
	

	while (left1 != right1 && left2 != right2)
	{

		if (p1.a[mid1] < p2.a[mid2])
		{
			//留下右邊
			if (left1 < right1)
			{
				left1 = mid1 + 1;
				mid1 = (left1 + right1) / 2;
			}

			//留下左邊
			if (left2 < right2)
			{
				right2 = mid2 - 1;
				mid2 = (left2 + right2) / 2;
			}
		}

		//反之
		if (p1.a[mid1] > p2.a[mid2])
		{
			//留下右邊
			if (left2 < right2)
			{
				left2 = mid2 + 1;
				mid2= (left2 + right2) / 2;
			}

			//留下左邊
			if (left1 < right1)
			{
				right1 = mid1 - 1;
				mid1 = (left1 + right1) / 2;
			}
		}

		
	}

	return p1.a[mid1] > p1.a[mid2] ? p1.a[mid1] : p2.a[mid2];
}

12. [2013統考真題]出現超過一半的元素

已知一個整數序列A = (a0, a1,an-1)，其中0<a<n(0≤i<n)。

若存在ap1=ap2= … =apm=x且m> n/2 (0≤pk<n, 1≤k≤m)，則稱x為A的主元素。例如A=(0,5,5,3,5,7,5,5)，則5為主元素;又如A=(0,5,5,3,5,1,5,7), 則A中沒有主元素，元素。假設A中的n個元素儲存在一個一維數組中，請設計一個盡可能高效的算法，找

出A的主元素。若存在主元素，則輸出該元素;否則輸出-1. 要求:

1)給出算法的基本設計思想。

2)根據設計思想，采用C或C++或Java語言描述算法，關鍵之處給出注釋.

3)說明你所設計算法的時間複雜度和空間複雜度。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;


/*
算法思路：
出現并計數，不出現--，直到0，重新計數，最終次數大于0是備選人
再進行周遊檢視出現次數
空間複雜度O1，時間複雜度On
*/

int Main_Ele(SL& pl)
{
	int x = 0;
	int count = 0;

	for (size_t i = 0; i < pl.size; i++)
	{
		if (x != pl.a[i])
		{
			if (count == 0)
			{
				x = pl.a[i];
			}
			else
			{
				count--;
			}
		}
		else
		{
			count++;
		}
	}

	if (count > 0)
	{
		int count = 0;
		for (size_t i = 0; i < pl.size; i++)
		{
			if (x == pl.a[i])
			{
				count++;
			}
		}
	}

	if (count > pl.size / 2)
	{
		return x;
	}

	return -1;
}

13. [2018統考真題] 數組未出現最小正整數

給定一個含n (n≥1)個整數的數組，請設計一個在時間上盡可能高.

效的算法，找出數組中未出現的最小正整數。例如，數組{-5,3, 2,3}中未出現的最小正

整數是1;數組{1,2,3}中未 出現的最小正整數是4.要求:

1)給出算法的基本設計思想。

2)根據設計思想，采用C或C++語言描述算法，關鍵之處給出注釋。.

3)說明你所設計算法的時間複雜度和空間複雜度。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

/*
算法思路：遇到負數忽略，尋找最小正數，
時間複雜度On，空間複雜度O1
*/

int Min_Pos_Int(SL& pl)
{
	int x = INT_MAX;
	for (size_t i = 0; i < pl.size; i++)
	{
		if (pl.a[i] > 0)
		{
			if (pl.a[i] < x)
			{
				x = pl.a[i];
			}
		}
	}

	return x;
}

14. [2020統考真題]三元數組最小距離

定義三元組(a, b,c) (a、 b、c均為正數)的距離D=|a-b| + |b-c| +|c-a|

給定3個非空整數集合S1、S2和S3按升序分别存儲在3個數組中。請設計一個盡可能高效的算法 ，計算并輸出所有可能的三元組(a,b,c) (a∈S|, b∈S2， cESj) 中的最小距離

例如Si={-1,0,9}， S2={-25,-10, 10,11}, S3= {2, 9, 17,30, 41},則最小距離為2,相應的三元組為(9, 10, 9)。要求:

1)給出算法的基本設計思想。

2)根據設計思想，采用C語言或C++語言描述算法，關鍵之處給出注釋。

3)說明你所設計算法的時間複雜度和空間複雜度。

【王道408資料結構】線性表習題Seqlist
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
using namespace std;

typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	size_t size;
	size_t capacity;
}SL;

bool Min(int a , int b, int c)
{
	if (a <= b && a <= c)
	{
		return true;
	}

	return false;
}

int ThreeArray_Min_Distance(SL& s1, SL& s2, SL& s3)
{
	//距離
	int d = INT_MAX;
	//數組下标
	int i = 0, j = 0, k = 0; 

	while (i < s1.size && j < s2.size && k < s3.size)
	{
		int ret = abs(s1.a[i] - s2.a[j]) + abs(s1.a[i] - s3.a[k]) + abs(s2.a[j] - s3.a[k]);
		if (ret < d)
		{
			d = ret;
		}

		if (Min(s1.a[i], s2.a[j], s3.a[k]))
		{
			i++;
		}
		else if (Min(s2.a[j], s1.a[i], s3.a[k]))
		{
			j++;
		}
		else
		{
			k++;
		}
	}

	return d;
}
The data structure 資料結構 c++ 順序表 王道408 考研
上一篇: mysql資料庫清系統資料庫_完全解除安裝MySQL 資料庫——清空MySql系統資料庫
下一篇: java在項目中建立目錄結構圖,Gradle建立項目目錄結構

繼續閱讀