# include <bits/stdc++.h>
using namespace std;
#include<malloc.h>
typedef struct Node
{
int data;
struct Node *pNext;
}Node, *pNode;
void malloc_fail(pNode p)
{
if (p == NULL)
{
puts("Memroy allocate fail!\n");
exit(-1);
}
}
pNode h_create_list() //头插法
{
int num;
printf("Nodes: ");
scanf("%d", &num);
pNode pHead = NULL;
for (int i=1; i<=num; i++)
{
printf("node %d: ", i);
pNode pNew = (pNode)malloc( sizeof(Node) );
malloc_fail(pNew);
scanf("%d", &pNew->data);
pNew->pNext = pHead;
pHead = pNew;
}return pHead;
}
pNode t_create_list()//尾插法
{
pNode pHead = (pNode)malloc( sizeof(Node) );
malloc_fail(pHead);
pNode pTail = pHead;
pTail->pNext = NULL;
int num;
printf("Nodes: ");
scanf("%d", &num);
for (int i=1; i<=num; i++)
{
printf("node %d: ", i);
pNode pNew = (pNode)malloc( sizeof(Node) );
malloc_fail(pNew);
scanf("%d", &pNew->data);
pTail->pNext = pNew;
pNew->pNext = NULL;
pTail = pNew;
}
return pHead;
}
void traverse_list1(pNode pHead)
{
pNode p = pHead;
while (p)
{
printf("%d ", p->data);
p = p->pNext;
}puts("");
}
void traverse_list2(pNode pHead)
{
pNode p = pHead->pNext;
while (p)
{
printf("%d ", p->data);
p = p->pNext;
}puts("");
}
int insert_list(pNode pHead, int pos, int val)//插入
{
int i=1;
pNode p = pHead;
while (NULL!=p && i<pos)
{
p = p->pNext;
++i;
}
if (NULL==p || i>pos) return 0;
pNode pNew = (pNode)malloc( sizeof(Node) );
pNew->data = val;
pNew->pNext = p->pNext;
p->pNext = pNew;
return 1;
}
int delete_list(pNode pHead, int pos, int *val)//删除
{
int i=1;
pNode p = pHead;
while (NULL!=p->pNext && i<pos)
{
p = p->pNext;
i++;
}
if (NULL==p->pNext || i>pos) return 0;
pNode q = p->pNext;
*val = q->data;
p->pNext = q->pNext;
free(q);
q = NULL;
return 1;
}
int getElem_list(pNode pHead, int pos, int*val) //查找元素
{
int i=1;
pNode p = pHead;
while (NULL!=p->pNext && i<pos)
{
p = p->pNext;
i++;
}
if (NULL==p->pNext || i>pos) return 0;
*val = p->pNext->data;
return 1;
}
int getIndex_list(pNode pHead, int val, int*index) //返回位置
{
int i = 1;
pNode p = pHead->pNext;
while (p != NULL)
{
if (val == p->data)
{
*index = i;
return 1;
}
i++;
p = p->pNext;
} return 0;
}
int destroy_list(pNode pHead)//销毁
{
if (pHead == NULL) return 0;
pNode p = pHead->pNext;
pNode q;
while (p)
{
q = p->pNext;
free(p);
p = q;
}
pHead->pNext = NULL;
return 1;
}
int sort_list1(pNode pHead) //头插排序
{
pNode p,pTail;
int temp;
pTail = NULL;
if (pHead->pNext == NULL) return 0;
while (pHead->pNext != pTail)
{
p = pHead->pNext;
while (p->pNext != pTail)
{
if (p->data > p->pNext->data)
{
printf("%f\n", p->data);
temp = p->pNext->data;
p->pNext->data = p->data;
p->data = temp;
} p = p->pNext;
} pTail = p;
} return 1;
}
int sort_list2(pNode pHead)//尾插排序
{
pNode pTemp, p, pPre, pTail;
pTail = NULL;
if (pHead->pNext == NULL) return 0;
while (pHead->pNext != pTail)
{
pPre = pHead;
p = pHead->pNext;
while (p->pNext != pTail)
{
if (p->data > p->pNext->data)
{
pTemp = p->pNext;
pPre->pNext = p->pNext;
p->pNext = p->pNext->pNext;
pPre->pNext->pNext = p;
p = pTemp;
}
p = p->pNext;
pPre = pPre->pNext;
} pTail = p;
} return 1;
}
pNode reverse_list(pNode pHead) //逆序
{
pNode current, p;
if (pHead == NULL) return NULL;
current = pHead->pNext;
while (current->pNext != NULL)
{
p = current->pNext;
current->pNext = p->pNext;
p->pNext = pHead->pNext;
pHead->pNext = p;
} return pHead;
}
pNode merge_list(pNode La, pNode Lb) //合并
{
pNode Lc, HeadC;
HeadC = La;
Lc = HeadC;
La = La->pNext;
Lb = Lb->pNext;
while (La && Lb)
{
if (La->data > Lb->data)
{
Lc->pNext = Lb;
Lb = Lb->pNext;
}
else
{
Lc->pNext = La;
La = La->pNext;
}
Lc = Lc->pNext;
}
Lc->pNext = La ? La : Lb;
return HeadC;
}
int main(void)
{
pNode linkList1 = NULL;
pNode linkList2 = NULL;
linkList2 = t_create_list();
linkList1 = t_create_list();
/*test*/
/*
traverse_list1(linkList1);
traverse_list2(linkList2);
insert_list(linkList1, 3, 0);
insert_list(linkList2, 4, 0);
int val;
if (delete_list(linkList2, 1, &val))
printf("Element deleted:%f\n", val);
if (getElem_list(linkList2, 4, &val))
printf("The ele is%f\n", val);
int i;
if(getIndex_list(linkList2, 2, &i))
printf("The index is %d\n", i);
destroy_list(linkList2);
traverse_list2(linkList2);
traverse_list1(linkList1);
traverse_list2(linkList2);
traverse_list2(linkList2);
sort_list2(linkList2);
traverse_list2(linkList2);
pNode linkList3 = NULL;
linkList3 = reverse_list(linkList2);
traverse_list2(linkList3);
*/
pNode linkList3 = merge_list(linkList1, linkList2);
traverse_list2(linkList3);
return 0;
}
