头歌实践平台答案educoder

数据结构-链表及其应用

第1关：链表的实现之查找功能

/*************************************************************
    链表的实现之查找功能  实现文件
    更新于2020年4月21日
**************************************************************/
void LL_GetAt(LinkList L, int i, ElemType &e)
// 在带头结点的单链表L中获取第i个元素的值赋给e，i的取值范围[1,n]
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/
	int j=0;
	LinkList pTail = L;
	while(j<i){
		pTail = pTail->next;
			j++;
	}
	e = pTail->data;
	/********** End **********/
}

LNode *LL_FindValue(LinkList L, ElemType e,int &i)
//在带头结点的单链表L中查找第一个值为e的元素，
//找到则将该元素在链表中的位置赋给i，并返回该结点指针，否则i赋值为0并返回空指针
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/
	
	//1-1 调用LL_GetAt();函数
		int temp ;
		LinkList pTail = L->next;
		for(int j=1;pTail!=NULL;j++)
		{
			
			LL_GetAt(L,j,temp);
				if(temp==e)
				{
					i = j;
					return pTail;
					break;
				}
			pTail = pTail->next;
			
		}

	if(pTail == NULL){
		i = 0;
		return NULL;
	}

        /* 方法二：不调用函数
        LinkList p = L->next;
        i++;
        while(p&&p->data!=e){
            p = p->next;
            i++;
        }

        if(!p)
        {
            i=0;
            return p;
        }
        return p;
        */
	/********** End **********/
}

第2关：链表的实现之增删功能

/*************************************************************
    链表的实现之增删功能  实现文件
    更新于2020年4月21日   
**************************************************************/

void LL_InsAt(LinkList L,int i,ElemType e)
// 在带头结点的单链表L中第i个位置插入值为e的新元素，i的取值范围[1,n+1]
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/
	int flag = 1;
	LinkList pTail = L,pNew;

	while(flag<i)
		{
			pTail = pTail->next;
			flag++;
		}

	pNew = (LinkList)malloc(sizeof(LNode));
	pNew->data = e;
	pNew->next = pTail->next;
	pTail->next = pNew;

	/********** End **********/
}

void LL_DelAt(LinkList L,int i)
// 在带头结点的单链表L中，删除第i个元素，i的取值范围[1,n]
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/
	int flag = 1;
	LinkList pTail = L,pDelete;

	while(flag<i)
		{
			pTail = pTail->next;
			flag++;
		}
	pDelete = pTail->next;
	pTail->next = pTail->next->next;
	free(pDelete);

	/********** End **********/
}

void LL_DelValue(LinkList L, ElemType e)
// 删除第一个值为e的数据元素
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/

	LinkList pTail = L,pDelete;
	while(pTail->next->data!=e&&pTail->next->next!=NULL)//此处的！=NULL可以删除
		pTail = pTail->next;
	if(pTail->next->data==e&&pTail->next!=NULL)//同上，此处的！=NULL可以删除
		{
			pDelete = pTail->next;
			pTail->next = pTail->next->next;
			free(pDelete);
		}
	
        /*
            LinkList p;
            p = L->next;
            int pos = 1;

            while(p){
                if(p->data==e)
                {
                    LL_DelAt(L,pos);
                    break;
                }
                p = p->next;
                pos++;
            }
        */
	/********** End **********/
}

第3关：链表的合并

/*************************************************************
    链表的合并  实现文件
    更新于2020年4月21日    
**************************************************************/
void MergeList_L(LinkList LA,LinkList LB,LinkList &LC)
//已知单链表LA和LB的元素按值非递减排列
//归并LA和LB得到新的单链表LC，LC的元素也按值非递减排列。
{
	// 请在这里补充代码，完成本关任务
    /********** Begin *********/
		
	LL_Initiate(LC);
	LNode*p=LA,*q=LB,*r=LC,*sc;
	p = p->next;
	q = q->next;
	
	while(p!=NULL&&q!=NULL)
	{
		sc = (LinkList)malloc(sizeof(LNode));
		r->next = sc;
		sc->next= NULL;
		if(q->data <= p->data)
		{
			sc->data = q ->data;
			q = q->next;
		}
		else
		{
			sc->data = p->data;
			p = p->next;
		}
		r = r->next;
		
	}
	
	if(q==NULL)
	{
		while(p!=NULL)
		{
			sc = (LinkList)malloc(sizeof(LNode));
			r->next = sc;
			sc->next= NULL;
			sc->data = p->data;
			p=p->next;
			r = r->next;
		}
		
	}
	else
	{
		while(q!=NULL)
		{
			sc = (LinkList)malloc(sizeof(LNode));
			r->next = sc;
			sc->next= NULL;
			sc->data = q->data;
			q=q->next;
			r = r->next;
		}
	}

	/********** End **********/
}  

																											"答案仅供参考"
																											"直接抄袭毫无意义"