题目1

题目

设顺序表a中的数据元素递增有序，编写一个算法，将数据元素x插入到顺序表a的适当位置上，以保持该顺序表的有序性。

解答

void SLFindInsert(SL* ps, SLDataType x)
{
	assert(ps);
	int pos = SLFind(ps, x);
	if (pos >= 0)
	{
		//如果存在数值相同的元素
		printf("存在数值相同的元素");
		SLInsert(ps, pos, x);
	}
	else
	{
		pos = 0;
		while (pos < ps->size && ps->arr[pos] < x)
		{
			pos++;
		}
		SLInsert(ps, pos, x);
	}
}

题目2

题目

设线性表中的数据元素以值递增排列，并以单链表作为存储结构。设计一个高效算法，删除表中所有值大于min且小于max的元素，同时释放被删除节点的空间，并分析算法的时间复杂度

解答

void SLEraseRange(SLTNode** pphead, int min, int max)
{
	assert(pphead && *pphead);
	//当要删除的节点是头结点时
	while ((*pphead)->data > min && (*pphead)->data < max)
	{
		SLTPopFront(pphead);
	}

	//当要删除的节点是非头结点时
	SLTNode* pcur = *pphead;
	while (pcur && pcur->next)
	{
		if (pcur->next->data > min && pcur->next->data < max) {
			SLTEraseAfter(pcur);  // 删除当前节点之后的节点
		}
		else {
			pcur = pcur->next;  // 继续检查下一个节点
		}
	}
}

题目三

题目

假设有两个按元素递增有序排列的线性表A和B，均以单链表作为其存储结构，试设计一个算法将A和B归并成一个按元素递减有序排列的线性表C，并要求利用原表（即表A和表B）的节点空间构造表C。

思考

解法1

因要求用原表的节点空间构造表c，则先用head指针指向B链表的第一个节点，temp2指向当前节点，prev2指向当前节点的前一个节点。 将B的第一个节点大小循环与A中数据大小比较，用SLTFind函数（修改版，增加没有这个数时找到小于它的最大数），返回下标，修改该节点temp1的下一个节点，并把插入的节点连接到下一个节点上。

###解法2（解答）

解答

SLTNode* MergeDescending(SLTNode* A, SLTNode* B) {
	SLTNode* C = NULL; // 头指针，最终指向降序链表
	SLTNode* temp;

	while (A && B) {
		if (A->data >= B->data) {
			temp = A;  // 取A的节点
			A = A->next; // A指向下一个
		}
		else {
			temp = B;  // 取B的节点
			B = B->next; // B指向下一个
		}
		// 头插法插入C
		temp->next = C;
		C = temp;
	}

	// 处理剩余的A或B
	while (A) {
		temp = A;
		A = A->next;
		temp->next = C;
		C = temp;
	}

	while (B) {
		temp = B;
		B = B->next;
		temp->next = C;
		C = temp;
	}

	return C;
}

题目四

题目

试设计一个算法，删除一个顺序表中从第i个元素开始的k个元素。

解答

void SLDeleteK(SL* ps, int i, int k)
{
	assert(ps);
	// 参数检查
	if (i < 0 || i >= ps->size || k <= 0) {
		printf("Invalid i or k!\n");
		return;
	}

	// 计算实际能删除的元素数量，防止越界
	if (i + k > ps->size) {
		k = ps->size - i;
	}

	// 移动数据：从 i+k 开始的元素往前移动 k 个位置
	for (int j = i; j + k < ps->size; j++) {
		ps->arr[j] = ps->arr[j + k];
	}

	// 更新顺序表大小
	ps->size -= k;
}

题目五

题目

已知两个元素按值递增有序排列的线性表A和B，且同一表中的元素值各不相同。试构造一个线性表C，其元素为A和B中元素的交集，且表C中的元素也按值递增有序排列。设计对A、B、C都是顺序表时的算法

解答

void SLIntersection(SL* A, SL* B, SL* C) {
    assert(A && B && C);
    SeqListInit(C);  // 初始化 C

    int i = 0, j = 0;
    while (i < A->size && j < B->size) {
        if (A->arr[i] == B->arr[j]) {
            SLPushBack(C, A->arr[i]);  // 插入交集元素
            i++;
            j++;
        } else if (A->arr[i] < B->arr[j]) {
            i++;  // 跳过 A[i]
        } else {
            j++;  // 跳过 B[j]
        }
    }
}

题目六

题目

给定一个单向链表，试设计一个既节省时间又节省空间的算法来找出该链表的倒数第m个元素。实现这个算法，并对可能出现的特殊情况做相应处理。自行设计链表的数据结构。（“倒数第m个元素”的含义：当m=0试，链表的最后一个元素将被返回）

解答

ListNode* FindMthFromEnd(ListNode* head, int m) {
    if (!head || m < 0) return NULL;  // 处理无效输入

    ListNode* fast = head;
    ListNode* slow = head;

    // 让 fast 先走 m+1 步
    for (int i = 0; i <= m; i++) {
        if (fast == NULL) return NULL;  // m 超出链表长度
        fast = fast->next;
    }

    // fast 和 slow 一起向前走
    while (fast) {
        fast = fast->next;
        slow = slow->next;
    }

    return slow;  // slow 现在是倒数第 m 个节点
}