2 pinkfavorite pinkfavorite 于 2016.04.12 08:03 提问

用c语言编程,关于链表的

请教各位大神:实现创建链表,输出链表两个函数怎么编程序。。。
输入两个非降序列,转换成两个非升序列,合并成一个非升序列,用链表实现

5个回答

CSDNXIAON
CSDNXIAON   2016.04.12 08:12

C语言编程入门——链表
----------------------同志你好,我是CSDN问答机器人小N,奉组织之命为你提供参考答案,编程尚未成功,同志仍需努力!

beifengche
beifengche   2016.04.12 10:45

您这问题也太多了吧。创建链表都要问,创建链表书上都有。第一行的问题自己想办法。
第二行问题我回答下,可以想象一下当一个链表从非降序转化成非升序时,其实就是将链表逆序。可以新建一个链表,然后遍历要逆序的链表,每次将每个元
素插入到新链表的第一个位置。这样遍历结束后新链表就是非升序的。
两个非降序列,转换成两个非升序列,合并成一个非升序列。其实道理是一样的,多了比较而已,
第一步 新建一个新的链表
第二步 定义三个指着分别指向非降序链表(p1,p2),和新生成的链表(p3)
第三歩 比较比较p1和p2所指的元素大小,哪个元素大就讲哪个元素插入到新链表中的第一的位置上,并将该指着移动到下一个位置上。
重复做第三步,知道摸一个非降序链表遍历结束,将另一个还剩下的元素遍历每个元素还是直接插入到新链表的首部。

qq423399099
qq423399099   Ds   Rxr 2016.04.12 11:40

参考:http://blog.csdn.net/pf4919501/article/details/38818335
建议楼主先自己试着写一下,有问题的话可以再发上来

qq_31597573
qq_31597573   2016.04.12 11:41

链表的创建。。。。。。。。。还是看书吧。先把链表的定义搞清楚.楼上回答的已经很清楚了。这里我补充一下代码,哈哈。
两个非降序列,转换成两个非升序列:就是先分别反转链表。反转链表代码如下
ListNode* reverseList(ListNode* head) {
if(NULL==head)
{
return head;
}
ListNode* prev=head;
ListNode* cur=head->next;
ListNode* tmp=NULL;
prev->next=NULL;
while(cur!=NULL)
{
tmp=cur->next;
cur->next=prev;
prev=cur;
cur=tmp;
}
return prev;
}
大意就是设两个指针,两个指针指向相邻的结点。然后反转相邻的两个结点,然后指针向前走,再反转指向的两个结点。不断重复,一直到链表结尾。就可以了。
除了这种方法以外,还可以用递归。代码如下:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
{
return head;
}
ListNode* tmp;
tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
反转完链表以后。接下来就是将两个链表merge成一下单链表。楼上说的很清楚,但是需要额外申请空间。这里有一个方法不用申请内存。如下:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
{
return head;
}
ListNode* tmp;
tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
依然是递归。如果不懂递归。。。。。。。。看书去。

qq_31597573
qq_31597573   2016.04.12 11:56

上面的merge链表函数写错了。更正如下(并补充非递归的写法)
递归:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
if(l2==NULL) return l1;
ListNode* Head=NULL;
if(l1->valval)
{
Head=l1;
Head->next=mergeTwoLists(l1->next,l2);
}
else
{
Head=l2;
Head->next=mergeTwoLists(l1,l2->next);
}
return Head;
}
非递归:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL&&l2==NULL) return NULL;
vector NodeVec;
while(l1!=NULL&&l2!=NULL)
{
if(l1->val>l2->val)
{
NodeVec.push_back(l2);
l2=l2->next;
}
else
{
NodeVec.push_back(l1);
l1=l1->next;
}
}
while(l1!=NULL)
{
NodeVec.push_back(l1);
l1=l1->next;
}
while(l2!=NULL)
{
NodeVec.push_back(l2);
l2=l2->next;
}
int i=0;
for(;i {
NodeVec[i]->next=NodeVec[i+1];
}
NodeVec[i]->next=NULL;
return NodeVec[0];
}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!