星星之火，可以燎原

线性表

顺序表：线性表的顺序存储，其特点是 逻辑顺序与其物理顺序相同。

插入操作的平均时间复杂度为$O(n)$

存取方式是指读写方式，随机存取是指根据起始地址加上元素序号可以很方便的访问任意一个元素

#define MaxSize 50
//静态分配
typedef struct {
	ElemType data[MaxSize];
	int length;
}SqList;

//动态分配
typedef struct {
	ElemType* data;
	int InitSize, length;
}SqList1;

//初始动态分配语句为
L.data = (ElemType*)malloc(sizeof(Elemtype) * InitSize);

//顺序表的插入、删除和按值查找的实现
bool ListInsert(SqList& L, int i, ElemType e) {
	if (i<1 || i>L.length+1) {
		return -1;
	}
	if (L.length >= MaxSize) {
		return -1;
	}
	for (int j = L.length; j >= i; j--) {
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1] = e;
	L.length++;
	return 1;
}

//将顺序表L的所有元素逆置 要求空间复杂度为O(1)
bool Delete_ST(SqList& L, ElemType s, ElemType t) {
	int start=0, end=0;
	if (t<L.data[0] || s>L.data[L.length]||L.length==0)
		return false;
	//for (int i = 0; i < L.length; i++)
	while(i<L.length){
		if (L.data[i] < s)
			i++;
		start = i;
	}
	for (int j = start; j < L.length; j++) {
		if (L.data[j] > t)
			end = j;
		break;
	}
	for (; j < L.length; j++, i++) {
		L.data[i] = L.data[j];
		L.length = i;
		return true;
	}
}

//将两个有序顺序表合并为一个新的有序顺序表
1.算法思想：按顺序将两个顺序表表头较小的元素取下来存入新的顺序表中，最后将剩下的部分直接加入到新的顺序表之后即可

bool Merge(SqList& L1, SqList& L2, SqList L) {
	int i = 0, j = 0, k = 0;
	while (i < L1.length && j < L2.length) {
		if (L1.data[i] < L2.data[j])
			L.data[k++] = L1.data[i++];
		else
			L.data[k++] = L2.data[j++];
	}

	while (i < L1.length)
		L.data[k++] = L1.data[i++];
	while (j < L2.length)
		L.data[k++] = L2.data[j++];

	L.length = k;
	return true;
}

//将一维数组中存放的两个线性表的位置交换
1.算法思想：先将数组中的全部元素原地逆置，再对前n个和后m个元素分别使用逆置算法，即可实现顺序表的位置交换。
typedef int DataType;
void Reverse(DataType A[], int left, int right, int arraySize) {
	if (left >= right || right >= arraySize)
		return;
	int mid = (left + right) / 2;
	for (int i = 0; i <= mid - left; i++) {
		DataType temp = A[left + i];
		A[left + i] = A[right - i];
		A[right - i] = temp;
	}
}


void Exchange(DataType a[], int m, int n, int arraySize) {
	Reverse(A, 0, m + n - 1, arraySize);
	Reverse(A, 0, n - 1, arraySize);
	Reverse(A, n, m + n - 1, arraySize);
}

//考虑采用二分查找，时间复杂度为O(nlog2n),找到后与其后继元素交换需要额外申请一个sizeof(ElemType)空间，若找不到，先将比该元素大的元素后移一位，然后将该元素填入空出来的位置

void BinSearch(SqList& L, ElemType e) {
	bool flag = true;
	int low = 0, high = L.length, mid,pos;
	ElemType temp;
	while(low<=high) {
		mid = (low + high) / 2;
		if (L.data[mid] == e) {
			temp = L.data[mid];
			L.data[mid] = L.data[mid + 1];
			L.data[mid + 1] = temp;
		}
		else if (L.data[mid] < e) {
			low = mid + 1;
		}
		else
			high = mid - 1;
	}
	if (low > high) {
		for (int i = L.length - 1; i > high; i--) {
			A[i + 1] = A[i];
			A[i + 1] = e;
		}
	}
}

//序列的循环左移
1.算法的基本设计思想
答：这类似于将一维线性表中的两个数组交换位置，

typedef int DataType;
void Reverse(DataType A[], int left, int right) {
	
	int mid = (left + right) / 2;
	for (int i = 0; i <= mid - left; i++) {
		DataType temp = A[left + i];
		A[left + i] = A[right - i];
		A[right - i] = temp;
	}
}


void Exchange(DataType a[], int m, int n) {
	Reverse(A, 0, p - 1);
	Reverse(A, p, n - 1);
	Reverse(A, 0, n - 1);
}

//求两个等长有序序列的中位数
一.算法的设计思想
分别求俩个序列的中位数，设为a，b，求序列A,B的中位数的过程如下
1.若 a=b ,则 a 或 b为所求的中位数，算法结束；
2.若 a<b ,舍弃A中小于 a 的部分，同时舍弃B中大于 b 的部分，要求两次舍弃的长度相等；
3.若 a>b ,舍弃A中大于 a 的部分，同时舍弃B中小于 b 的部分，要求两次舍弃的长度相等；
再保留的两个升序序列中，重复1,2,3过程，直到两个序列中均只含一个元素时为止，较小者即为所求的中位数。



int M_Search(int A[], int B[], int n) {
	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(log_2n)
//算法的空间复杂度为O(1)

//找处数组的主元素
一、算法的设计思想
从后向前扫描数组元素，标记出一个可能成为主元素的的元素num，确认元素num是否是主元素。
1.选取候选的主元素。依次扫描所给数组的每个元素，将第一个遇到的元素保存到c中，记录num出现的次数为1，若遇到的下一个元素还是num,则计数加一，否则计数减一，当计数减到0时，将遇到的下一个整数保存到c中，计数重新记为1，开始新一轮计数，从当前位置开始重复上述过程，直到扫描完全部数组元素。
2.判断c中元素是否是真正的主元素，再次扫描数组，统计c中元素出现的次数，判断是否是主元素。


int Majority(int A[], int n) {
	int i, c, count = 1;
	c = A[0];
	for (i = 1; i < n; i++) {
		if (A[i] == c)
			count++;
		else {
			if (count > 0)
				count--;
			else {
				c = A[i];
				count = 1;
			}
		}
	}
	if (count > 0)
		for (i = count = 0; i < n; i++)
			if (A[i] == c)
				count++;
	if (count > n / 2) return c;
	else return -1;
}

//找出数组中未出现的最小正整数
一、算法设计思想
  A. 快速排序后从头遍历
  B. 用空间换时间。
     分配一个用于标记数组中出现了1~n中哪些数的数组，初始时全部标记为0，若出现，则标记为1
     
 int FindMissMin(int A[], int n) {
	int i, * B;
	B = (int*)malloc(sizeof(int) * n);
	memset(B, 0, sizeof(int) * n);
	for (i = 0; i < n; i++) {
		if (A[i] > 0 && A[i] <= n) {
			B[A[i] - 1] = 1;
		}
	}
	for (i = 0; i < n; i++)
		if (B[i] == 0)break;
	return i + 1;
}

//时间复杂度O(n)
//空间复杂度O(n)

//求三元组最小距离
#define INT_MAX 0x7fffffff
int abs_(int a) {
	if (a < 0) return -a;
	else return a;
}

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

int FindMinofTrip(int A[], int n, int B[], int m, int C[], int p) {
	int i = 0, j = 0, k = 0, D_min = INT_MAX, D;
	while (i < n && j < m && k < p && D_min>0) {
		D = abs_(A[i] - B[j]) + abs_(B[j] - C[k]) + abs_(C[k] - A[i]);
		if (D < D_min) D_min = D;
		if (xls_min(A[i], B[j], C[k])) i++;
		else if (xls_min(B[j], C[k], A[i]))  j++;
		else k++;
	}
	return D_min;
}

2009统考真题：在不改变链表的前提下，设计一个尽可能高效的算法，查找链表中倒数第K个位置上的节点

算法思想：设计两个指针p,q,初始时均指向头节点的下一个节点，p指针沿链表移动，当p指针移动到第k个位置时，q指针开始与p指针同步移动，当p指针移动到最后一个节点时，q指针所指节点为倒数第k个节点

typedef int ElemType;
typedef struct LNode {
	ElemType data;
	struct LNode* next;
}LNode, *LinkList;

int Search_k(LinkList L, int k) {
	LNode* p = L->next, * q = L->next;
	int count = 0;

	while (p != NULL) {
		if (count < k) count++;
		else q = q->next;
		p = p->next;
	}
	if (count < k)
		return 0;
	else {
		printf("%d", q->data);
		return 1;
	}
}

找出两个单链表共同后缀的起始位置
typedef struct Node {
	char data;
	struct Node* next;
}SNode;

int listlen(SNode* head) {
	int len = 0;
	while (head->next != NULL) {
		len++;
		head = head->next;
	}
	return len;
}

SNode* find_addr(SNode* str1, SNode* str2) {
	int m, n;
	SNode* p, * q;
	m = listlen(str1);
	n = listlen(str2);
	for (p = str1; m > n; m--)
		p = p->next;
	for (q = str2; m < n; n--)
		q = q->next;
	while (p->next != NULL && p->next != q->next) {
		p = p->next;
		q = q->next;
	}
	return p->next;
}

对于链表中data绝对值相等的节点，仅保留第一次出现的节点而删除其余出现的节点


//用空间换时间：设置一个大小为n+1的辅助数组
//依次扫描链表中各节点，同时检查对应数组的值

//时间复杂度 O(m)  空间复杂度 O(n)

typedef struct node {
	int data;
	struct node *next
}Node,*PNode;

void func(PNode L, int n) {
	PNode p = L, r;
	int* q, m;
	q = (int*)malloc(sizeof(int) * (n + 1));
	for (int i = 0; i < n + 1; i++)
		*(q + 1) = 0;
	while (p->next != NULL) {
		m = p->next->data > 0 ? p->next->data : -p->next->data;

		if (*(q + m) == 0) {
			*(q + m) = 1;
			p = p->next;
		}
		else {
			r = p->next;
			p->next = r->next;
			free(r);
		}
	}
	free(q);
}

//判断一个链表是否有环，如果有，找出环的入口点并返回，否则返回NULL

//快慢指针
struct Node{
    int val;
    Node *next;
};
 
//判断链表是否有环
bool hasCircle(Node *node) {
    
    //定义快慢指针
    Node *fast=node;
    Node *slow=node;
    
    //因为快指针要走两个节点，所以要多判断一步，遇到空指针说明没有环
    while (fast != NULL && fast->next != NULL) {
        
        fast = fast->next->next;
        slow = slow->next;
        
        //当快指针等于慢指针时，说明快指针绕环行进赶上慢指针了，证明有环
        if (fast == slow) {
            return true;
        }
    }
    
    return false;
}

Node *getCircleHead(Node *node){
    //先判读是否有环
    if (hasCircle(node)) {
        
        Node *fast=node;
        Node *slow=node;
        
        //找到交点m
        do{
            fast=fast->next->next;
            slow=slow->next;
        }while (fast!=slow);
        
        //找环入口
        fast=node;
        while (fast!=slow) {
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
    return NULL;
}

void change_order(Node* L) {
	Node* p, * q, * r, * s;
	p = q = h;
	while (q->next != NULL) {
		p = p->next;
		q = q->next;
		if (q->next != NULL)  q = q->next;   //q走两步
	}

	q = p->next;
	p->next = NULL;
	while (q != NULL) {
		r = q->next;
		q->next = p->next;
		p->next = q;
		q = r;

	}
	s = h->next;
	q = p->next;
	p->next = NULL;

	while (q != NULL) {
		r = q->next;
		q->next = s->next;
		s->next = q;
		s = q->next;
		q - r;
	}
}

星星之火，可以燎原

数据结构之线性表

线性表

数值积分

一维热传导方程的求解

1.求解原理描述

20210707

第三篇文章

第二篇文章