跪求C语言 数剧结构 编程
答案:2 悬赏:0 手机版
解决时间 2021-06-05 10:34
- 提问者网友:原来太熟悉了会陌生
- 2021-06-05 07:46
已知指针ha和hb分别指向两个单链表的头结点,且头结点的数据域中存放链表的长度,试写一算法将这两个链表连接在一起(即令其中一个表的首无结点连在另一个表的最后一个结点之后),hc指向连接后的链表的头结点,并要求算法以尽可能短的时间完成连接运算.请分析你的算法的时间复杂度
最佳答案
- 五星知识达人网友:痴妹与他
- 2021-06-05 08:03
#include <stdio.h>
#include <stdlib.h>
typedef struct _list {
int val;
struct _list* next;
} *node, list;
node Insert( node head, node pos, int val )
{
node tmp;
tmp = ( node )malloc( sizeof( list ) );
tmp->val = val;
tmp->next = pos ? pos->next : head->next;
if ( pos ) {
pos->next = tmp;
} else {
head->next = tmp;
}
return tmp;
}
void Create( node head, int* beg, int* end )
{
node t;
head->next = t = NULL;
head->val = end - beg;
while ( beg != end ) {
t = Insert( head, t, *beg++ );
}
}
void Tie( node ha, node hb, node hc )
{
int i;
node tmp = ha;
for ( i = 0; i < ha->val; ++i ) {
tmp = tmp->next;
}
tmp->next = hb->next;
hc->val = ha->val + hb->val;
hc->next = ha->next;
ha->val = hb->val = 0;
ha->next = hb->next = NULL;
}
void Print( char* msg, node head )
{
printf( msg );
head = head->next;
while ( head ) {
printf( "%d ", head->val );
head = head->next;
}
putchar( '\n' );
}
int main()
{
int a[] = { 1,3,5,7,9 };
int b[] = { 2,4,6,8,10 };
list ha, hb, hc;
Create( &ha, a, a + 5 );
Create( &hb, b, b + 5 );
Print( "ha:", &ha );
Print( "hb:", &hb );
Tie( &ha, &hb, &hc );
Print( "hc:", &hc );
getchar();
return 0;
}
#include <stdlib.h>
typedef struct _list {
int val;
struct _list* next;
} *node, list;
node Insert( node head, node pos, int val )
{
node tmp;
tmp = ( node )malloc( sizeof( list ) );
tmp->val = val;
tmp->next = pos ? pos->next : head->next;
if ( pos ) {
pos->next = tmp;
} else {
head->next = tmp;
}
return tmp;
}
void Create( node head, int* beg, int* end )
{
node t;
head->next = t = NULL;
head->val = end - beg;
while ( beg != end ) {
t = Insert( head, t, *beg++ );
}
}
void Tie( node ha, node hb, node hc )
{
int i;
node tmp = ha;
for ( i = 0; i < ha->val; ++i ) {
tmp = tmp->next;
}
tmp->next = hb->next;
hc->val = ha->val + hb->val;
hc->next = ha->next;
ha->val = hb->val = 0;
ha->next = hb->next = NULL;
}
void Print( char* msg, node head )
{
printf( msg );
head = head->next;
while ( head ) {
printf( "%d ", head->val );
head = head->next;
}
putchar( '\n' );
}
int main()
{
int a[] = { 1,3,5,7,9 };
int b[] = { 2,4,6,8,10 };
list ha, hb, hc;
Create( &ha, a, a + 5 );
Create( &hb, b, b + 5 );
Print( "ha:", &ha );
Print( "hb:", &hb );
Tie( &ha, &hb, &hc );
Print( "hc:", &hc );
getchar();
return 0;
}
全部回答
- 1楼网友:鸽屿
- 2021-06-05 08:40
void f(NODE *ha,NODE *hb,NODE *hc)
{
NODE *p;
long i=0;
char flag=0;
p=ha;
if (ha->data>hb->data)
{ p=hb; flag=1;}
i=p->data;
while (i>0){i--;p=p->next;}
hc=(NODE *)malloc(sizeof(NODE));
if (flag){p->next=ha->next;hc->next=hb->next;hc->data=hb->data+ha->data;}else{p->next=hb->next;hc->next=ha->next;hc->data=ha->data+hb->data;}
return ;
}
时间复杂度为MIN(N,M) 线性。
其中N和M分别是ha和hb的长度
我要举报
如以上问答信息为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯