王道代码题汇总（持续更新）

课后题：

都是经过测试通过的，测试函数最好自己写一个吧

//第一题
//第一题的函数
void DelMin(int* arr, int len) {
	if (!len) {
		printf("数组为空");
		return;
	}
	//遍历一遍找到最小值
	int min = arr[0], minpos = 0;
	for (int i = 0; i < len; ++i) {
		if (arr[i] < min) {
			//把最小值赋值给他
			minpos = i;//记录下标
			min = arr[i];
		}
	}
	//找到最小值的元素之后把最后一个元素挪到删除元素的位置
	//返回最小值
	arr[minpos] = arr[len - 1];
	arr[len - 1] = NULL;
	return min;
}

//第二题：设计一个高效算法。。。
void Reserve(int* arr, int len) {
	for (int i = 0; i < len / 2; ++i) {
		//只用遍历一半保证其不会被换回来
		int tmp = arr[i];
		arr[i] = arr[len - i - 1];//画图理解
		arr[len - i - 1] = tmp;
	}
	return;
}

第三题设计的很巧妙，建议都写一下

//第三题
int DelX(int* arr, int len, int x) {
	int count = 0;
	int i = 0;
	while (i < len) {
		//找出相应的元素
		if (arr[i] == x) {
			count++;
		}
		else {
			arr[i - count] = arr[i];
		}
		i++;
	}
 //处理后续元素
	for (int j = len-count; j < len ; j++) {
		arr[j] = NULL;
	}
	return count;//返回删除元素的总数
}

//第四题函数
void DletePoint(int* arr, int s, int t, int len) {
	int right = 0, left = 0;//找到第一个大于等于s的和第一个大于t的
	for (left = 0; left < len && arr[right] < s; right++);
	if (right >= len)return;
	for (left = 0; left <= len && arr[left] <= t; left++);
	//都找到了直接换
	for (; left < len; left++, right++) {
		arr[left] = arr[right];
	}
	for (int j = 0; j < left; j++) {
		printf("%d ", arr[j]);
	}
}
//测试函数
//第四题测试函数
int main() {
	int arr[] = { 1,4,5,7,8,1,2 };
	int s, t;//用于限定区间范围
	int len = sizeof(arr) / sizeof(int);
	printf("请输入区间范围");
	do {
		printf("s=");
		scanf("%d", &s);
		printf("t=");
		scanf("%d", &t);
	} while (s > t);
	DletePoint(arr, s, t, len);
	return 0;
}

//第六题
int Delerep(int* arr, int len) {
	int pos = 0;//记录当前数组下标
	for (int i = 0; i < len; i++) {
		if (arr[i] - arr[i + 1]) {
			//如果不一样保持原来的的值
			arr[pos] = arr[i];
			pos++;
		}
	}
		if (arr[len-2] == arr[len-1]) {
			//如果最后两个元素一样
			arr[len - 1] = NULL;
			pos++;
		}
		return pos;
}

合并数组重中之重

//第七题
int* mergeList(int* l1, int* l2, int len1, int len2) {
	int* newList = (int*)malloc(len1 + len2);
	int k = 0, i = 0, j = 0;
	for (; i < len1 && j < len2;) {
		l1[i]
		//把后续元素补上
		newList[k++] = l1[i++];
	}
	while (j< len2) {
		//把后续元素补上
		newList[k++] = l2[j++];
	}
	return newList;
}

第八题

//第八题逆置顺序表中指定范围的元素
void reserve(int* arr, int from, int end) {
	if (from > end) {
		return;
	}
	int tmp;
	for (int i = from; i < (from + end) / 2; ++i) {
		tmp = arr[i];
		arr[i] = arr[end+from-i];//随着i的增加end指针向前移动
		 arr[end+from-i] = tmp;
	}
}
int main() {
	int arr[] = {1,2,2,3,4};
	reserve(arr, 0, 4);
	reserve(arr, 0, 2);
	reserve(arr, 3, 4);
	for (int i = 0; i < 5; ++i) {
		printf("%d", arr[i]);
	}
	return 0;

}

第九题

//第九题时间复杂度尽量少找到指定元素，时间复杂度尽可能第是所以用二分查找
int Findx(int* arr, int len, int x) {
	int low = 0, high = len - 1, mid;
	while (low <= high && (mid = (low + high) / 2)) {
		if (x == arr[mid])  break;//找到了
		if (x < arr[mid]) {
			//说明要在左边找
			high = mid - 1;
		}
		else
		{
			low = mid + 1;
		}
	}
	if (low > high) {
		//说明没有找到
		//插入即可，把后续元素往后挪
		int i;
		for (i = len - 1; i > high; --i) {
			arr[i + 1] = arr[i];//腾出位置放入元素
		}
		arr[i] = x;
		return len + 1;//数组长度
	}
	else {
		//找到了，进行对调
		int tmp=arr[mid];
		arr[mid + 1] = arr[mid];
		arr[mid] = tmp;
		return len;
	}
}

后面都是真题等我过完一遍再来做

接下里到单链表的课后题啦

//递归删除指定元素
//单链表第一题
void DeletX(Link* (&k), int delnum) {
	//第一个函数必须为引用值防止断链，就相当于传入的是k-》next
	struct Link* tmp;
	if (k == NULL) return;//边界条件
	if (k->next == delnum) {
		//删除其元素并且继续向里递归
		tmp = k;
		k = k->next;
		free(tmp);
		DeletX(k, delnum);
	}
	else {
		//不等于
		//也是向内递归
		DeletX(k->next, DeletX);
	}

第二题
//带头结点的链表删除指定值
void DelX(Link* p, int delnum) {
	struct Link* tmp=p;
	struct Link* fir = p->next;
	struct Link* tmp2;
	while (fir)
	{
		if (fir->value==delnum) {
			tmp2 = fir;//保存删除结点的地址
			fir = fir->next;//指向下一个结点
			tmp->next = fir;//删除节点的前一个结点指向新的结点
			free(tmp2);
		}
		else {
			//若不相等则继续遍历
			tmp = fir;
			fir = fir->next;//保持tmp一直指向fir前一个结点即可
		}
	}
	}

//第三题
//反向输出链表所有元素
//实际上就是把所有元素放入栈中最后在一起取出来即可
void ReserveOutPut(Link* p) {
	if (p == NULL) return;//边界条件：直到没有链表指针后依次出栈
	ReserveOutPut(p->next);
	printf("%d", p->next);
}

//第四题
//第四题函数
//带头结点所以第一步就是保存头节点以及保留下下个结点
//头->带数据结点->下一个结点->下下个结点
//删除下一个结点所以要保留下下个结点
void DeletMin(Link* p) {
	struct Link* fir = p;//记录头结点
	struct Link* minPin = p->next;
	struct Link* prePin = p->next;
	struct Link* next = p->next->next;//记录下下个结点
	while (next) {
		if (next->value < minPin->value) {
			//如果比当前值要小
			minPin = next;//记录当前最小值节点
			fir = prePin;//前驱也要更换
		}
		//否则继续前进
		//要一直记录前驱
		prePin = next;
		next = next->next;
	}
	//这时候已经找到最小值啦
	struct Link* f = minPin;
	fir->next = minPin->next;
	free(f);

}

第五题单链表经典题目

相似题目（有道原题）

(17条消息) 六月集训第十二日-链表_达芬奇的奇妙之旅的博客-CSDN博客

//就地逆置单链表（带头结点）
//其实很简单的方式就是让指针指向的方向逆置
void Reverse(Link* p) {
	struct Link* pre = p;//记录头节点
	struct Link* rec = p->next;//记录
	struct Link* q = p->next;
	struct Link* tmp;
	while (rec) {
		tmp = rec->next;//记录下一个结点
		rec->next = pre;//指向数据结点前一个结点也就是换方向
		pre = rec;//前一个结点往下移一位
		rec = tmp;//当前结点也往下移动
	}
	//还完之后在处理第一个结点和最后一个结点
	p->next = pre;//为什么是pre因为他保存是rec的上一个结点rec寄了自然是pre
	//还记得第一个数据结点码，处理它
	q->next = NULL;
}

第六题涉及到排序算法打算等到最后一章回来再写

//待更新。。。

第七题：带头结点无序单链表中删除表中所有介于给定的两个值之间的元素的元素（easy~）

void DelNum(Link* L, int min, int max) {
	struct Link* pre = L;
	struct Link* p = pre->next;
	struct Link* tmp;
	while (p) {
		//依次判断是否在其范围之内
		if (p->value > min && p->value < max) {
			//如果满足删除
			tmp = p->next;//记录当前结点的下一个结点
			pre->next = p->next;
			free(p);//删除当前结点
			p = tmp;
		}
		//若不在继续往下走
		pre = p;
		p = p->next;
	}
}

第八题太简单懒得写了hh

第九题按递增次序输出单链表中各节点的数据元素，并且释放结点所占的存储空间

void PrintandDel(Link* L) {
	//我就懒得改我设定的adt了num=value
	struct Link* pre = L;
	struct Link* p = L->next;
	struct Link* tmp;//上面三个常用管他要不要不要再删
	struct Link* min = L->next;//用于记录最小值结点
	struct Link* minPre = L;//记录最小值前一个结点
	int count = 0;
	while (p) {
		count++;
		p = p->next;
	}
	p = L->next;
	for (int i = 0; i < count; i++) {
		//依次找出最小的然后删除
		//有点暴力但是简单
		while (p) {
			if (p->value < min->value) {
				//如果小换
				minPre = pre;
				min = p;
			}
			pre = p;
			p = p->next;
		}
		//这时候最小的已经出现了输出删除即可
		printf("%d", min->value);
		tmp = min;
		minPre->next = min->next;
		free(tmp);
		//重置
		pre = minPre=L;
		p = min = L->next;
	}
	printf("n");
	return;
}

第十题：讲带一个头结点的单链表A分解为两个带头结点的单链表A和B，使得a表中含有原表中序号为奇数的元素，b表中含有原表中序号为偶素的元素，且保持相对顺序不变

void Divide(Link* la, Link* lb) {
	int flag = 0;//用于奇偶校验
	struct Link* l = la;
	struct Link* p = la->next;
	struct Link* a = la;
	struct Link* b = lb;
	l->next = NULL;//原链表的头节点设为空
	while (p) {
		//使其顺序不变采取尾插法
		if (!flag) {
			//0时为奇数
			a->next = p;
			a = p;
			flag = 1;
		}
		if (flag) {
			//为偶
			b->next = p;
			b = p;
			flag = 0;
		}
		p = p->next;
	}
	//边界处理
	a->next = NULL;
	b->next = NULL;
}

第十一题和第十题差不多哦也是拆分成两个顺序表

唯一个要注意的时b表采取尾插法因为是逆序的

//如果是奇数不动偶数提出来
//b中采取头插法

void DivideList(Link* L) {
	struct Link* l2 = (Link*)malloc(sizeof(Link));
	l2->next = NULL;
	Link* p = L->next, * q, * r = L;
	while (p)
	{
		r->next = p;
		r = p;
		p = p->next;
		if (p) q = p->next;
		p->next = l2->next;
		l2->next = p;
		p = q;
	}
	r->next = NULL;
}

第十二题：在一个递增有序的线性表中，有数值相同的元素存在，若存储方式为单链表，设计算法去掉数值相同的元素，是表中不再有重复的元素。。

双指针，两个向前进，然后相同去掉

//12
void deleteRep(Link* L) {
	struct Link* pre = L, * p = L->next, * r;//删除无脑写(主要是防止断链)
	while (p->next) {
		if (p->value == p->next->value) {
			r = p->next;
			pre->next = p->next;
			free(p);
			p = r;
		}
		else
		{
			//不相等
			pre = p;
			p = p->next;
		}
	}
}

第十三题：假设有两个按元素值递增有序的线性表，均已单链表的形式春促，请编写算法使得这两个的那链表归并成为一个按元素之递减次序排序的单链表，并且要求利用原来两个单链表的结点存放归并后的单链表

因为是要递减顺序所以这里采取头插法将小的值依次放入

void MergeList(Link* la, Link* lb) {
	struct Link* l = (Link*)malloc(sizeof(Link)), * pa = la->next, * pb = lb->next, * ra, * rb;
	l->next = NULL;
	//采取头插法的方式
	while (pa && pb) {
		if (pa->value < pb->value) {
			//也就是要头插法插入pa
			ra = pa->next;//保留下一个结点
			pa->next = l->next;
			l->next = pa;
			pa = ra;
		}
		else {
			rb = pb->next;
			pb->next = l->next;
			l->next = pb;
			pb = rb;
		}
	}
	while (pa) {
		ra = pa->next;
		pa->next = l->next;
		l->next = pa;
		pa = ra;
	}
	while (pb) {
		rb = pb->next;
		pb->next = l->next;
		l->next = pb;
		pb = rb;
	}
}

第十四题：设A和B是两个单链表（带头结点），其中元素递增有序。设计一个算法从A和B中的公共元素残生单链表c，要求不破坏A。B结点

//14
void LinkCom(Link* a, Link* b, Link* c) {
	struct Link* lc = c, * pa = a->next, * pb = b->next,*rc=lc;
	while (pa) {
		//没遍历一个la就遍历依次lb找到相同放入c
		while(pb){
			if (pa->value == pb->value) {
				struct Link* q = (struct Link*)malloc(sizeof(struct Link));
				q->value = pa->value;
				rc->next = q;
				rc = q;
				break;
			}
			pb = pb->next;
		}
		pa = pa->next;
		pb = b->next;
	}
	rc->next = NULL;
}