Question

初学者求解一道数据结构[c语言版]的题目

已知指针HA和HB分别指向两个单链表的头结点,并且已知两个链表的长度分别为M和N.试写一算法将这两个链表连接在一起,即是其中一个表的首元结点连在另一个表的最后一个结点之后.假设指针HC指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算,试分析算法的时间复杂度.
谢谢!
还有人来吗?

Answer 1

/***
*
*题目：已知线性表中的元素以值递增有序排列，并以单链表做存储结构。试写一高效的算法，
*
删除表中所有值大于
mink
且小于
maxk
的元素（若表中存在这样的元素）,同时释放
*
被删除节点空间，并分析你的算法的时间复杂度（注意：mink
和
maxk
是给定的两个
*
参变量，它们的值可以和表中的元素相同，也可以不同）
*
****/
#include
<stdio.h>
#include
<stdlib.h>
#include
"DynaLinkList.h"
void
DelMminMax(LinkList
*L,
int
min,
int
max)
{
LinkList
p
=
(*L)->next,
q
=
(*L),
r;
while
(p
&&
p->data
<=
min)
{
q
=
p;
p
=
p->next;
}
while
(
p
&&
p->data
<
max)
{
r
=
p;
p
=
p->next;
q->next
=
p;
free(r);
}
}
//算法的时间复杂度为O(n)
int
main()
{
LinkList
L;
ElemType
e,
min,
max;
InitList(&L);
printf("输入8个元素建立线性表L(元素递增有序):\n");
for
(int
i=1;
i<=8;
i++)
{
scanf("%d",
&e);
ListInsert(&L,
i,
e);
}
printf("表L是：\n");
ListTraverse(L,
visit);
printf("请输入待删除的元素的区间是(min,max):\n");
scanf("%d%d",
&min,
&max);
DelMminMax(&L,min,max);
printf("删除(%d,%d)之间的元素后表L是：\n",min,max);
ListTraverse(L,
visit);
return
0;
}

Answer 2

/***
*
*题目：已知线性表中的元素以值递增有序排列，并以单链表做存储结构。试写一高效的算法，
*
删除表中所有值大于
mink
且小于
maxk
的元素（若表中存在这样的元素）,同时释放
*
被删除节点空间，并分析你的算法的时间复杂度（注意：mink
和
maxk
是给定的两个
*
参变量，它们的值可以和表中的元素相同，也可以不同）
*
****/
#include
<stdio.h>
#include
<stdlib.h>
#include
"DynaLinkList.h"
void
DelMminMax(LinkList
*L,
int
min,
int
max)
{
LinkList
p
=
(*L)->next,
q
=
(*L),
r;
while
(p
&&
p->data
<=
min)
{
q
=
p;
p
=
p->next;
}
while
(
p
&&
p->data
<
max)
{
r
=
p;
p
=
p->next;
q->next
=
p;
free(r);
}
}
//算法的时间复杂度为O(n)
int
main()
{
LinkList
L;
ElemType
e,
min,
max;
InitList(&L);
printf("输入8个元素建立线性表L(元素递增有序):\n");
for
(int
i=1;
i<=8;
i++)
{
scanf("%d",
&e);
ListInsert(&L,
i,
e);
}
printf("表L是：\n");
ListTraverse(L,
visit);
printf("请输入待删除的元素的区间是(min,max):\n");
scanf("%d%d",
&min,
&max);
DelMminMax(&L,min,max);
printf("删除(%d,%d)之间的元素后表L是：\n",min,max);
ListTraverse(L,
visit);
return
0;
}

Answer 3

struct LNode
{
int date;
LNode *next;
} *head;

LNode* LNodeCom(LNode* h1,int h1len, Lnode* h2,int h2len )
{
LNode* p1,p2;
if(h1len>h2len)
{
p1 = h2;
p2 = h1;
}
else
{
p1 = h1;
p2 = h2;
}
while(p1->next != NULL)
p1 = p1->next;
p1->next = p2;
return p1;
}

复杂度:
O(hlen) (hlen为短表的长度)