JZTXT

数据结构之刷题记录

发布时间 2023-06-29 22:16:59作者: 满城衣冠

删除链表中的某个x数据

void Del_x(LinkList& L, ElementType x) {
	LNode* pre = L, * p = L->next, * q;
	while (p != null) {
		if (p->data == x) {
			q = p;
			p = p->next;
			pre->next = p;
			free(q);
		}
		else {
			pre = p;
			p=p->next
		}
	}
}

将两个有序表合成一个有序表，返回有序表

 

bool Merge(Sqlist a, Sqlist b, Sqlist& c) {
	int i = 0, j = 0, k = 0;
	if (a.length + b.length < c.maxSize)//c辅助表无法容纳两个表元素
		return false;
	while (i < a.length && j < b.length) {//从两个表中各取一个，谁小存入c表
		if (a.data[i] = b.data[j]) {
			c.data[k++] = a.data[i++];
		}
		else {
			c.data[k++] = b.data[j++];
		}
	}
	while (i < a.length) {//a表有剩余，全放入c
		c.data[k++] = a.data[i++];
	}
	while (j < b.length) {//b表有剩余，全放入c
		c.data[k++] = b.data[j++];
	}
	c.length = k;
	return true;
}

将顺序表倒置，空间复杂度为O（1）

两者交换关系：i   n-i    不过n=L.length-1;

void Reverse(SqList& L) {
	ElemType temp;
	for (int i = 0; i < L.length / 2; i++) {
		temp = L.data[i];
		L.data[i] = L.data[L.length - 1 - i];
		L.data[L.length - 1 - i] = temp;
	}
}

使用递归方法

void Reverse(int* a, int low, int high) {
	if (low < high) {
		swap(a[low], a[high]);
		Reverse(a, low + 1, high - 1);
	}
}