数据结构与算法参考答案（第三周）

一、已知线性表中元素以值递增有序排列，并以单链表作存储结构。试写一高效的算法，删除表中所有值大于mink且小于maxk的元素（若表中存在这样的元素）同时释放被删结点空间，并分析你的算法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值可以和表中的元素相同，也可以不同）。

答：

本题对于算法的优化的突破点在于线性表中的元素是以值递增有序排列。从头节点开始遍历链表，当遍历到第一个大于mink的元素时，记录下来其前驱的指针。然后继续判断后面的元素。如果后面的元素小于maxk继续遍历，同时释放该结点。当判断出来的元素大于等于maxk时，需要将原先记录的结点的指针的next指向这个元素的后继指针，同时将这个结点空间释放，然后结束循环，返回链表头节点。本题在输入的时候需要判断这个线性表是否为空表。

本算法实现的伪代码如下：

/*
	函数名称：有序链表删除算法
	传入参数：需要插入的单链表L， 操作区间mink, maxk
	返回值：返回OK代表删除成功，返回NO代表传入为空表或者删除后为空表
*/
Status DeleteLNode(LNode &L, mink, maxk) {
	if(L->next == NULL) {
	//说明传入的是空表
		return NO;
	}
	else {
		p1 = L->next;	//p1指向第一个结点
		p2 = L->next	//p2指向第一个结点
		//查找第一个大于mink结点所处在的位置
		while(p1 && p1->val <= mink) {
			p2 = p1;
			p1 = p1->next;
		}
		while(p1 && p1->val <= maxk) {
			temp = p1;
			p1 = p1->next;
			free(temp);		//释放空间
		}
/*此时p1为第一个大于maxn的结点或者空结点因为可能不存在大于等于maxk的元素*/
		p2->next = p1
		if(L->next != NULL)
			return OK;
		else
			return NO;
	}
}

二、试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表(a₁, a₂, ...,a_n)逆置为（a_n, a_n-1,...,a₁)

答：

由于我们可以通过标号来访问顺序表，所以解决本问题我们只需要遍历数组一半的元素将第i个元素和第L.length-i-1个元素交换即可。

本算法实现的伪代码如下：

/*
	函数名称：顺序表逆置算法
	传入参数：顺序表
	返回值：返回OK代表操作成功
*/
Status ListOppose(SqList &L)
{   //颠倒顺序表中的数据元素
    int i;
    ElemType x;
    for(i = 0; i< L.length / 2; i++)
    {
        /*实现数据元素交换*/
        x = L.elem[i];
        L.elem[i] = L.elem[L.length-i-1]; 
        L.elem[L.length-i-1] = x;
    }
    return OK;
}

三、试写一算法，实现对单链表就地置换。

答：

首先我们需要将链表的头节点取出，构成一个空表。然后将剩下的元素依次取出作为前一个链表的第一个元素节点。最后将头节点的指针指向第一个元素结点。

本算法实现的伪代码如下：

/*
	函数名称：单链表表逆置算法
	传入参数：单链表
	返回值：返回OK代表操作成功
*/
Status LNodeOppose(LNode &L)
{   // 颠倒单链表中的数据元素
    temp1 = L->next;
    temp1->next = NULL;
    while(temp1) {
        temp2 = temp1->next;    //得到后继
        temp1->next = L->next;
        L->next = temp1;    //插入在都节点之后
        temp1 = temp2;  //向后移动
    }
    return OK;
}

四、假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序，允许表中含有值相同的元素）排列的线性表C，并要求利用原表（即A表和B表）的结点空间构造C表。

答：

解决这个问题，我们需要使用两个指针指向A和B两个链表，将A和B中第一个元素较小的结点取出构成第三个链表最后的结点。然后在遍历的过程中使用头插法一次插入。

本算法实现的伪代码如下：

/*
    函数名称：链表合并算法
    传入参数：两链表A和B
    返回值：返回OK代表操作成功
*/
Status Merge(LNode &A, LNode &B)
{   
    tempA = A->next;
    tempB = B->next;
    C = NULL;
    //实现对齐长度的插入
    while(A->next != NULL && B->next != NULL) {
        tempA = A->next;
        tempB = B->next;
        if(tempA->val <= tempB->val) {
            //将小的插入C中
            A->next = tempA->next;
            tempA->next = NULL;
            tempA->next = C->next;
            C->next = tempA;
        }
        else {
            B->next = tempB->next;
            tempB->next = NULL;
            tempB->next = C->next
        }
    }
    //如果A表更长
    if(A->next == NULL) {
        while(B->next != NULL) {
            tempB = B->next;
            B->next = tempB->next;
            tempB->next = C->next;
            C->next = tempB;
        }
    }
    //如果B表更长
    else {
        while(A->next != NULL) {
            tempA = A->next;
            A->next = tempA->next;
            tempA->next = C->next;
            C->next = tempA;
        }        
    }
    return OK;
}

Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C){

     LinkList pa,pb,qa,qb;

     pa=A;

     pb=B;

     qa=pa;   // 保存pa的前驱指针

     qb=pb;   // 保存pb的前驱指针

     pa=pa->next;

     pb=pb->next;

     A->next=NULL;

     C=A;

     while(pa&&pb){

          if(pa->data<pb->data){

               qa=pa;

               pa=pa->next;

               qa->next=A->next; 

               A->next=qa;

          } else{

               qb=pb;

               pb=pb->next;

                qb->next=A->next;            //将当前最小结点插入A表表头

               A->next=qb;

          }

     }

     while(pa){

          qa=pa;

          pa=pa->next;

          qa->next=A->next;

          A->next=qa;

     }

     while(pb){

          qb=pb;

          pb=pb->next;

          qb->next=A->next;

          A->next=qb;

     }

     pb=B;

     free(pb);

     return OK;

}

五、已知由一个线性链表表示的线性表中含有三类字符的数据元素（如：字母字符、数字字符和其它字符），试编写算法将该线性链表分割为三个循环链表，其中每个循环链表示的线性表中均只含一类字符。

答：

由分析可知，我们需要通过遍历判断这个字符属于哪一类。然后通过将其插入相应的位置构成链表。最后将其转换为循环链表。

本算法实现的伪代码如下：

/*
    函数名称：分割链表
    传入参数：需分割链表L 三结果链表A和B和C
    返回值：返回OK代表操作成功
*/
Status Classify(LNode &L, LNode &A, LNode &B, LNode &C)
{   
    temp = L->Node;
    //使A，B，C成为循环链表
    A->next = A;
    B->next = B;
    C->next = C;
    while(temp) {
        //通过ASCILL判断
        if(temp->data是字母字符) {
            //将该字符插入链表A中
           temp->next = A->next;
           A->next = temp;
           A = temp;
        }
        else if(temp->data是数字) {
            //将该字符插入链表A中
           temp->next = B->next;
           B->next = temp;
           B = temp;
        }
        else{
            //将该字符插入链表A中
           temp->next = C->next;
           C->next = temp;
           C = temp;
        }
        temp = temp->next;
    }
    return OK;
}