第二章 线性表-单链表的顺序合并操作2019-01-31

代码块
//错误点1：在输出链表信息的时候没有加 p =p->pNext;这句话，导致运行出现问题
//问题2：结构体取名确实叫LNode比较好，自己取名SList有点说不过去
//下面还有一些自己看并没有动手实验的时候，没有认真想的地方，然后自己试验过程中需要花费一点时间，考虑其中的关系，在这个地方，真心不应该的
typedef struct LNode
{
int nData;
struct LNode* pNext;
}LNode;

void InitListData(LNode *&p)
{
p = (LNode *)malloc(sizeof(LNode));
p->pNext = NULL;
}

void CreateSingleList(LNode &pList,int nNum[],int n)
{
LNode p = pList;
LNode* q;
for (int i=0; i<n; i++)
{
InitListData(q);
q->nData = nNum[i];
p->pNext = q;
p = p->pNext;
}
}

void ShowList(LNode* p)
{
cout<<"输出链表："<<endl;
while (NULL!=p->pNext)
{
cout<<p->pNext->nData<<endl;
p =p->pNext;
}
cout<<"链表输出结束"<<endl;
}

//头插法，从大到小排序
void MergeListFromBToL(LNode* &pHead1,LNode* &pHead2,LNode* &pMergeHead)
{
LNode* p1 = pHead1->pNext;
LNode* p2 = pHead2->pNext;
pMergeHead = pHead1;
pMergeHead->pNext = NULL;
LNode* p;
free(pHead2);
while (p1!=NULL && p2!=NULL)
{
if (p1->nData<p2->nData)
{
p = p1->pNext;//这个地方想了一分钟才捋顺关系，不应该的
p1->pNext=pMergeHead->pNext;
pMergeHead->pNext = p1;
p1 = p;
}
else
{
p = p2->pNext;
p2->pNext = pMergeHead->pNext;
pMergeHead->pNext = p2;
p2 = p;
}
}
while(p1!=NULL)
{
p = p1->pNext;
p1->pNext=pMergeHead->pNext;
pMergeHead->pNext = p1;
p1 = p;
}
while(p2!=NULL)
{
p = p2->pNext;
p2->pNext = pMergeHead->pNext;
pMergeHead->pNext = p2;
p2 = p;
}
}

//尾插法，从小到大排序
void MergeList(LNode* &pHead1,LNode* &pHead2,LNode* &pMergeHead)
{
LNode* p1 = pHead1->pNext;
LNode* p2 = pHead2->pNext;
LNode* p = pMergeHead;
pMergeHead = pHead1;//这个地方写的时候出现了错误，写的是=p1；
free(pHead2);//以前这个地方没有特别注意，确实合并之后，这个头结点已经不需要，需要及时的释放掉
while (p1!=NULL && p2!=NULL)
{
if (p1->nData<p2->nData)
{
p->pNext = p1;
p = p->pNext;
p1 = p1->pNext;

    }
    else
    {
        p->pNext = p2;
        p = p->pNext;
        p2 = p2->pNext;
    }
}
if (p1 != NULL)
{
    p->pNext = p1;
}
else
{
    p->pNext = p2;
}

}

void FindAndDelete(LNode& pHead,int nData)
{
LNode p = pHead->pNext;
LNode* q = pHead;
while (q!=NULL && p!=NULL)
{
if (p->nData == nData)
{
q->pNext = p->pNext;
free(p);
break;
}
p = p->pNext;
q = q->pNext;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int nListNum[5] = {0,1,2,3,4};
int listNum[5] = {1,3,4,5,6};
LNode* pHeadList1;
LNode* pHeadList2;
LNode* pMergeHead;
InitListData(pHeadList1);
InitListData(pHeadList2);
InitListData(pMergeHead);
CreateSingleList(pHeadList1,nListNum,5);
CreateSingleList(pHeadList2,listNum,5);
// ShowList(pHeadList1);
// ShowList(pHeadList2);
MergeListFromBToL(pHeadList1,pHeadList2,pMergeHead);
ShowList(pMergeHead);
return 0;
}