数据结构考研复习 | 2021王道第2章·线性表的顺序表示之综合应用题(C语言实现)

朴灿烈づ我的快乐病毒、 2023-07-17 14:12 16阅读 0赞

#include "stdafx.h"
    #include <iostream>
    #define MAXSIZE 100
    typedef int ElemType;
    typedef int DataType;
    
    typedef struct
    {
    	ElemType data[MAXSIZE];
    	int length;
    } SqList;
    
    bool InitList(SqList *L)
    {
    	L->length = 0;
    	return true;
    }
    
    bool ListInsert(SqList *L, int i, ElemType e)
    {
    	if (i < 1 || i > L->length + 1)
    		return false;
    	if (L->length == MAXSIZE)
    		return false;
    	for (int k = L->length; k >= i - 1; k--)
    	{
    		L->data[k + 1] = L->data[k];
    	}
    	L->data[i - 1] = e;
    	L->length++;
    	return true;
    }
    
    bool ListDelete(SqList *L, int i, ElemType *e)
    {
    	if (i > L->length || i <= 0)
    		return false;
    	if (L->length == 0)
    		return false;
    	*e = L->data[i - 1];
    	for (i = i - 1; i < L->length - 1; i++)
    	{
    		L->data[i] = L->data[i + 1];
    	}
    	L->length--;
    	return true;
    }
    
    bool LocateElem(SqList L, ElemType e)
    {
    	int i;
    	for (i = 0; i < L.length; i++)
    	{
    		if (L.data[i] == e)
    			return i + 1;
    	}
    	return false;
    }
    
    bool ListEmpty(SqList L)
    {
    	/*判断线性表是否为空*/
    	if (L.length == 0)
    		return true;
    	else
    		return false;
    }
    
    bool ClearList(SqList *L)
    {
    	L->length = 0;
    	return true;
    }
    
    bool ListLength(SqList L)
    {
    	return L.length;
    }
    
    bool GetElem(SqList L, int i, ElemType *e)
    {
    	if (L.length == 0 || i < 1 || i > L.length)
    		return false;
    	*e = L.data[i - 1];
    	return true;
    }
    
    void Union(SqList *La, SqList Lb)
    {
    	int La_len = La->length;
    	int Lb_len = ListLength(Lb);
    	ElemType e;
    	int i = 1;
    	for (i = 1; i < Lb_len; i++)
    	{
    		GetElem(Lb, i, &e);
    		if (!LocateElem(*La, e))
    			ListInsert(La, ++La_len, e);
    	}
    }
    
    int printList(SqList L)
    {
    	if (L.length == 0)
    	{
    		printf("链表为空\n");
    		return 0;
    	}
    	for (int i = 0; i < L.length; i++)
    	{
    		printf("%d ", L.data[i]);
    	}
    	printf("\n");
    	return 1;
    }
    
    bool delMin(SqList *L,ElemType *e)//2.2-1
    {
    	if (L->length == 0)
    		return false;
    	*e = L->data[0];
    	int pos = 0;
    	for (int j = 0; j < L->length; j++) {
    		if (*e > L->data[j]) {
    			*e = L->data[j];
    			pos = j;
    		}
    	}
    	printf("min:%d,pos:%d\n", *e, pos);
    	L->data[pos] = L->data[L->length - 1];
    	return true;
    }
    
    bool reverse(SqList *L) {//2.2-2
    	if (L->length == 0)
    		return false;
    	ElemType temp;
    	for (int i = 0; i < L->length/2; i++) {
    		temp = L->data[i];
    		L->data[i] = L->data[L->length - i - 1];
    		L->data[L->length - i - 1] = temp;
    	}
    	return true;
    }
    
    void del_x_1(SqList *L, ElemType x) {//2.2-3 时间复杂度为O(n^2)
    	for (int i = 0; i < L->length; i++) {
    		if (L->data[i] == x) {
    			for (int j = i; j < L->length; j++) {
    				L->data[j] = L->data[j + 1];
    			}
    			L->length = L->length -1;
    		}
    	}
    }
    
    void del_x_2(SqList *L, ElemType x) {//2.2-3 时间复杂度为O(n)
    	int k = 0;
    	for (int i = 0; i < L->length; i++) {
    		if (L->data[i] != x) {
    			L->data[k] = L->data[i];
    			k++;
    		}
    	}
    	L->length = k;
    }
    
    void del_x_3(SqList *L, ElemType x) {//2.2-3 时间复杂度为O(n)
    	int k = 0;
    	for (int i = 0; i < L->length; i++) {
    		if (L->data[i] == x)
    			k++;
    		else
    			L->data[i - k] = L->data[i];
    	}
    	L->length -= k;
    }
    
    bool del_s_t_1(SqList *L, ElemType s, ElemType t) {//2.2-4 删除s-t元素
    	if (L->length == 0 || s >= t) {
    		printf("error");
    		return false;
    	}
    	int count = 0;
    	int pos = 0;
    	for (int i = 0; i < L->length; i++) {
    		if (L->data[i] > s && L->data[i] < t) {
    			//printf("%d\n", L->data[i]);
    			count++;
    			pos = i;
    		}
    	}
    	for (int j = pos-count+1; j < L->length; j++) {
    		L->data[j] = L->data[j + count];
    	}
    	L->length-=count;
    }
    
    bool del_s_t_2(SqList *L,ElemType s,ElemType t) {//2.2-5 删除s-t元素
    	if (L->length == 0 || s >= t) {
    		printf("error");
    		return false;
    	}
    	for (int i = 0; i < L->length; i++) {
    		if (L->data[i] >= s && L->data[i] <= t) {
    			//printf("%d\n", L->data[i]);
    			for (int j = i; j < L->length; j++) {
    				L->data[j] = L->data[j + 1];
    			}
    			L->length--;
    			i--;
    		}
    	}
    }
    
    void del_repeated(SqList *L) {//2.2-6 删除重复元素
    	//int count = 0;
    	//bool found = false;
    	//for (int i = 0; i < L->length; i++) {
    	//	if (L->data[i] == L->data[i + 1]) {
    	//		found = true;
    	//		count++;
    	//	}
    	//	else if (found == true) {
    	//		for (int j = i - 1; j < L->length; j++) {
    	//			L->data[j] = L->data[j + count];
    	//		}
    	//		L->length -= count;
    	//		found = false;
    	//	}
    	//}
    	int i = 0;
    	for (int j = 1; j < L->length; j++) {
    		if (L->data[i] != L->data[j])
    			L->data[++i] = L->data[j];
    	}
    }
    bool list_merge(SqList L1,SqList L2,SqList &L3) {//2.2-7 有序表合并
    	//if (L1.length + L2.length > L3.length)
    	//	return false;
    	int i = 0,j = 0, k = 0;
    	
    	while (i < L1.length && j < L2.length) {
    		if (L1.data[i] <= L2.data[j])
    			L3.data[k++] = L1.data[i++];
    		else
    			L3.data[k++] = L2.data[j++];
    	}
    	while (i < L1.length)
    		L3.data[k++] = L1.data[i++];
    	while (j < L2.length)
    		L3.data[k++] = L2.data[j++];
    	L3.length = k;
    	return true;
     }
    
    void reverse(DataType *a,int m,int n) {//2.2-8 顺序表位置互换
    	DataType b[MAXSIZE];
    	memset(b, 0, m * sizeof(DataType));
    	memcpy(b, a, m * sizeof(DataType));
    	for (int i = 0; i < n; i++)
    		b[i] = a[m + i];
    	for (int i = n; i < m + n; i++)
    		b[i] = a[i - n];
    	for (int i = 0; i < m + n; i++) {
    		a[i] = b[i];
    	}
    }
    
    void search_x(SqList *L, DataType x) {//2.2-9 查找x
    	int i = 0, j = L->length - 1;
    	while (i <= j) {
    		int m = (i + j) / 2;
    		if (L->data[m] < x && L->data[m + 1] > x) {
    			//printf("not found\n");
    			L->length++;
    			for (int ii = L->length - 1; ii > m; ii--)
    				L->data[ii] = L->data[ii-1];
    			L->data[m + 1] = x;
    			return;
    		}
    		else if (L->data[m] > x) {
    			j = m;
    		}
    		else if (L->data[m] < x) {
    			i = m;
    		}
    		else {
    			//printf("found\n");
    			DataType temp = L->data[m];
    			L->data[m] = L->data[m+1];
    			L->data[m + 1] = temp;
    			return;
    		}
    	}
    }
    
    void moving(DataType *r,int p,int n) {//2.2-10 循环左移P个位置
    	DataType b[MAXSIZE];
    	memset(b, 0, n * sizeof(DataType));
    	memcpy(b, r, n * sizeof(DataType));
    	for (int i = 0; i < p; i++)
    		b[n-p+i] = r[i];
    	for (int i = 0; i < n-p; i++)
    		b[i] = r[p+i];
    	for (int i = 0; i < n; i++) {
    		r[i] = b[i];
    	}
    }//时间复杂度为O(n)，空间复杂度为O(n)，空间复杂度可以优化为O(p)
    
    int get_median(int *a,int *b,int n) {//2.2-11 寻找中位数
    	int i = 0, j = 0;
    	int k;
    	while (i + j != n-2) {
    		if (a[i] <= b[j]) {
    			i++;
    			k = a[i];
    		}
    		else if (a[i] > b[j]) {
    			j++;
    			k = b[j];
    		}
    	}
    	return k;
    }//时间复杂度为O(n)，空间复杂度为O(1)
    
    int get_median_2(int *a, int *b, int n) {//2.2-11 寻找中位数(优解)
    	int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    	//分别表示序列A和B的首位数、末位数、中位数
    	while (s1 != d1 || s2 != d2) {
    		m1 = (s1 + d1) / 2;
    		m2 = (s2 + d2) / 2;
    		if (a[m1] == b[m2])
    			return a[m1];
    		if (a[m1] < b[m2]) {
    			if ((s1 + d1) % 2 == 0) {
    				s1 = m1; 
    				d2 = m2;
    			}
    			else {
    				s1 = m1 + 1;
    				d2 = m2;
    			}
    		}
    		else {
    			if ((s2+ d2) % 2 == 0) {
    				d1 = m1;
    				s2 = m2;
    			}
    			else {
    				d1 = m1;
    				s2 = m2+1;
    			}
    		}
    	}
    	return a[s1] < b[s2] ? a[s1]:b[s2];
    }//时间复杂度为O(log2n)，空间复杂度为O(1)
    
    int get_main_element(int *a,int n) {//2.2-12 寻找主元素
    	int c;//候选主元素
    	for (int i = 0; i < n; i++) {
    		if (a[i] == a[i + 1]) {
    			c = a[i];
    			break;
    		}
    	}
    	for (int i = n / 2; i < n; i++) {
    		if (a[i] == c && a[i]==a[i+1])
    			return c;
    	}
    	return -1;
    }
    
    void quick_sort(int s[], int l, int r)
    {
    	if (l < r)
    	{
    		//Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
    		int i = l, j = r, x = s[l];
    		while (i < j)
    		{
    			while (i < j && s[j] >= x) // 从右向左找第一个小于x的数
    				j--;
    			if (i < j)
    				s[i++] = s[j];
    
    			while (i < j && s[i] < x) // 从左向右找第一个大于等于x的数
    				i++;
    			if (i < j)
    				s[j--] = s[i];
    		}
    		s[i] = x;
    		quick_sort(s, l, i - 1); // 递归调用 
    		quick_sort(s, i + 1, r);
    	}
    }
    
    int get_min_int(int *a, int n) {//2.12-13 寻找最小正整数
    	quick_sort(a,0, n-1);
    	bool have1 = true;
    	for (int i = 0; i < n; i++) {
    		if (a[i] <= 0)
    			continue;
    		else if (have1 == true && a[i] > 1)
    			return 1;//只限首个大于0的数大于1时，返回1
    		else if (a[i] + 1 != a[i + 1] && a[i] != a[i+1])
    			return a[i] + 1;
    		else
    			have1 = false;
    	}
    	return -1;
    }//时间复杂度为0(nlogn)，空间复杂度为O(1)
    
    int get_min_int_2(int *a, int n) {//2.12-13 寻找最小正整数，空间换时间
    	int i, *b;
    	b = (int *)malloc(sizeof(int)*n);
    	memset(b, 0, sizeof(int)*n);
    	for (int i = 0; i < n; i++) {
    		if (a[i] > 0)b[a[i] - 1] = 1;
    	}
    	for (i = 0; i < n; i++)
    		if (b[i] == 0)
    			break;
    	return i + 1;
    }//时间复杂度为0(n)，空间复杂度为O(n)
    
    int main()
    {
    	SqList L;
    	InitList(&L);//初始化
    	SqList L2;
    	InitList(&L2);
    	for (int i = 0; i < 10; i++) //向线性表插入10个元素
    	{
    		//ListInsert(&L, i + 1, i*i-8*i);
    		//ListInsert(&L, i + 1, i*i - 4 * i + 4);
    		//ListInsert(&L, i + 1, 2+i);
    		ListInsert(&L, i + 1, i*i+1);
    		//ListInsert(&L2, i + 1, i-2);
    	}
    	//printList(L);
    	//printList(L2);
    
    	//2.2-1 删除最小元素
    	//int num;
    	//if (delMin(&L, &num)) {
    	//	printf("return:%d\n", num);
    	//	printList(L);
    	//}
    	//else
    	//	printf("linear list is empty");
    
    	//2.2-2 线性表倒置
    	//reverse(&L);
    
    	//2.2-3 删除所有x
    	//del_x_3(&L,1);
    
    	//2.2-4 删除s-t元素
    	//del_s_t_1(&L, 3, 5);
    
    	//2.2-5 删除s-t元素
    	//del_s_t_2(&L, 0, 20);
    
    	//2.2-6 删除重复元素
    	//del_repeated(&L);
    
    	//2.2-7 有序表合并
    	//SqList L3;
    	//InitList(&L3);
    	//list_merge(L, L2, L3);
    	//printList(L3);
    
    	//2.2-8 顺序表位置互换
    	//DataType a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	//reverse(a, 4, 6);
    	//for (int i = 0; i < 10; i++) {
    	//	printf("%d ", a[i]);
    	//}
    
    	//2.2-9 查找x
    	//search_x(&L, 26);
    
    	//2.2-10 循环左移P个位置
    	//DataType a[10] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    	//moving(a, 6, 10);
    	//for (int i = 0; i < 10; i++) {
    	//	printf("%d ", a[i]);
    	//}
    
    	//2.2-11 寻找中位数
    	//DataType a[9] = { 1, 3, 5, 7, 9, 11, 13, 15, 17 };
    	//DataType b[9] = { 2, 4, 6,8, 10, 12, 14, 16, 18 };
    	//printf("%d\n",get_median(a,b,9));
    	//printf("%d", get_median_2(a, b, 9));
    
    	//2.2-12 寻找主元素
    	//int a[9] = { 1, 3, 3, 7, 9, 11, 3, 3, 17 };
    	//int b[9] = { 1, 3, 3, 7, 9, 11, 3, 15, 17 };
    	//printf("%d\n",get_main_element(a,9));
    	//printf("%d\n", get_main_element(b, 9));
    
    	//2.12-13 寻找最小正整数
    	int a[9] = { 9, 3, 3, 4, 1, 2, 5, 6, 7 };
    	int b[9] = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    	printf("%d\n",get_min_int_2(a, 9));
    	printf("%d\n", get_min_int_2(b, 9));
    	//for (int i = 0; i < 9; i++) {
    	//	printf("%d ", a[i]);
    	//}
    
    	//printf("%d\n", get_main_element(a, 9));
    	//printf("%d\n", get_main_element(b, 9));
    
    	//printList(L);
    	printf("\n");
    	system("pause");
    	return 0;
    }