将链表拆分为c中的另外两个链表的问题
Problem splitting a linked list into two other linked lists in c
我的代码应该在一个链表中存储 10 个 int 数字，将这 10 个数字平均分配到另外两个链表中。但是我的两个列表返回空
我的结构：
typedef struct no
{
int value;
struct no *next;
} no;
变量大小来自一个循环遍历我的主列表的函数和 returns 它的大小。
然后创建了两个“几乎相等”的函数来从主列表中获取值并将其存储在 ListB 和 ListC 中。
我的职能：
no* copylist(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
insert(receive, aux->value);
aux=aux->next;
}
count = size/2;
return receive;
}
no* copylist1(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
aux=aux->next;
count++;
}
count = size/2;
aux=aux->next;
while(aux!=NULL&&count<size)
{
insert(receive, aux->value);
aux=aux->next;
}
return receive;
}
Obs：对我来说链表是一个很混乱的内容
如果我们使用 两个 指针，拆分可以在 单次 传递中完成。一个通过 cur1 = cur1->next 遍历，另一个通过两倍的速度遍历（例如 cur2 = cur2->next->next）；
当cur2到达终点时，cur1会在中点。
当我们将作为列表开始的“单星”指针传递给必须调整的函数并且return列表的头部时，调整将不会 被反射回 调用者 。
与其传递此列表的“双星”指针，不如 easier/better 使用单独的列表 struct 除了节点 struct。
请注意，我们可以 co-opt/reuse一个[虚拟]节点作为列表指针，但如果我们使用单独的结构会更清楚。
下面是一些带注释的代码。不幸的是，我不得不对其进行大量重构才能使其正常工作。
这是一个[取决于程序参数]的版本：
- 一个简单的两个通过版本。一个是计算计数，第二个是根据该计数进行拆分
- 一个改进的版本，使用上面提到的“双指针”技术
在单次传递中进行拆分
#include <stdio.h>
#include <stdlib.h>
int passno;
// node
typedef struct no {
int value;
struct no *next;
} no;
// list
typedef struct li {
no *head;
} li;
// show -- show a list
void
show(li *lst,const char *sym)
{
printf("%s:",sym);
for (no *cur = lst->head; cur != NULL; cur = cur->next)
printf(" %2d",cur->value);
printf("\n");
}
// newlist -- create a new list with N elements
li *
newlist(int count)
{
li *lst = malloc(sizeof(*lst));
no *cur;
no *prev;
lst->head = NULL;
prev = NULL;
for (int idx = 0; idx < count; ++idx) {
cur = malloc(sizeof(*cur));
cur->next = NULL;
cur->value = idx + 1;
if (prev != NULL)
prev->next = cur;
else
lst->head = cur;
prev = cur;
}
return lst;
}
// lstcount -- count number of elements in the list
int
lstcount(li *lst)
{
no *cur;
int count = 0;
for (cur = lst->head; cur != NULL; cur = cur->next)
++count;
return count;
}
// splitA -- split a list into two halves (single pointer, two pass version)
void
splitA(li *lstleft,li *lstright,li *lstfrom)
{
int count;
int idx;
no *cur;
no *left;
count = lstcount(lstfrom);
count = (count + 1) / 2;
left = NULL;
lstleft->head = NULL;
idx = 0;
for (cur = lstfrom->head; cur != NULL; cur = cur->next) {
if (++idx > count)
break;
// append to left list
if (left == NULL)
lstleft->head = cur;
left = cur;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur;
// zap the original list
lstfrom->head = NULL;
}
// splitB -- split a list into two halves (two pointer, one pass version)
void
splitB(li *lstleft,li *lstright,li *lstfrom)
{
no *cur1;
no *cur2;
no *left;
left = NULL;
lstleft->head = NULL;
cur2 = lstfrom->head;
for (cur1 = lstfrom->head; cur1 != NULL; cur1 = cur1->next) {
// wait for double speed pointer to end
if (cur2 == NULL)
break;
cur2 = cur2->next;
// append to left list
if (left == NULL)
lstleft->head = cur1;
left = cur1;
// advance at twice the rate
if (cur2 != NULL)
cur2 = cur2->next;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur1;
// zap the original list
lstfrom->head = NULL;
}
// clean -- free up list elements and list descriptor
void
clean(li *lst)
{
no *cur;
no *next;
for (cur = lst->head; cur != NULL; cur = next) {
next = cur->next;
free(cur);
}
free(lst);
}
// dotest -- test the split for a given number of nodes
void
dotest(int count)
{
li *big;
li *left;
li *right;
printf("\n");
printf("dotest: count=%d\n",count);
big = newlist(count);
show(big,"big");
left = newlist(0);
right = newlist(0);
switch (passno) {
case 1:
splitA(left,right,big);
break;
case 2:
splitB(left,right,big);
break;
}
show(left,"lhs");
show(right,"rhs");
clean(left);
clean(right);
clean(big);
}
int
main(int argc,char **argv)
{
--argc;
++argv;
if (argc > 0)
passno = atoi(*argv);
if (passno <= 0)
passno = 1;
if (passno > 2)
passno = 2;
printf("passno=%d\n",passno);
for (int count = 0; count <= 12; ++count)
dotest(count);
}
程序输出如下：
passno=1
dotest: count=0
big:
lhs:
rhs:
dotest: count=1
big: 1
lhs: 1
rhs:
dotest: count=2
big: 1 2
lhs: 1
rhs: 2
dotest: count=3
big: 1 2 3
lhs: 1 2
rhs: 3
dotest: count=4
big: 1 2 3 4
lhs: 1 2
rhs: 3 4
dotest: count=5
big: 1 2 3 4 5
lhs: 1 2 3
rhs: 4 5
dotest: count=6
big: 1 2 3 4 5 6
lhs: 1 2 3
rhs: 4 5 6
dotest: count=7
big: 1 2 3 4 5 6 7
lhs: 1 2 3 4
rhs: 5 6 7
dotest: count=8
big: 1 2 3 4 5 6 7 8
lhs: 1 2 3 4
rhs: 5 6 7 8
dotest: count=9
big: 1 2 3 4 5 6 7 8 9
lhs: 1 2 3 4 5
rhs: 6 7 8 9
dotest: count=10
big: 1 2 3 4 5 6 7 8 9 10
lhs: 1 2 3 4 5
rhs: 6 7 8 9 10
dotest: count=11
big: 1 2 3 4 5 6 7 8 9 10 11
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11
dotest: count=12
big: 1 2 3 4 5 6 7 8 9 10 11 12
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11 12
我的代码应该在一个链表中存储 10 个 int 数字，将这 10 个数字平均分配到另外两个链表中。但是我的两个列表返回空
我的结构：
typedef struct no
{
int value;
struct no *next;
} no;
变量大小来自一个循环遍历我的主列表的函数和 returns 它的大小。 然后创建了两个“几乎相等”的函数来从主列表中获取值并将其存储在 ListB 和 ListC 中。
我的职能：
no* copylist(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
insert(receive, aux->value);
aux=aux->next;
}
count = size/2;
return receive;
}
no* copylist1(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
aux=aux->next;
count++;
}
count = size/2;
aux=aux->next;
while(aux!=NULL&&count<size)
{
insert(receive, aux->value);
aux=aux->next;
}
return receive;
}
Obs：对我来说链表是一个很混乱的内容
如果我们使用 两个 指针，拆分可以在 单次 传递中完成。一个通过 cur1 = cur1->next 遍历，另一个通过两倍的速度遍历（例如 cur2 = cur2->next->next）；
当cur2到达终点时，cur1会在中点。
当我们将作为列表开始的“单星”指针传递给必须调整的函数并且return列表的头部时，调整将不会 被反射回 调用者 。
与其传递此列表的“双星”指针，不如 easier/better 使用单独的列表 struct 除了节点 struct。
请注意，我们可以 co-opt/reuse一个[虚拟]节点作为列表指针，但如果我们使用单独的结构会更清楚。
下面是一些带注释的代码。不幸的是，我不得不对其进行大量重构才能使其正常工作。
这是一个[取决于程序参数]的版本：
- 一个简单的两个通过版本。一个是计算计数，第二个是根据该计数进行拆分
- 一个改进的版本，使用上面提到的“双指针”技术 在单次传递中进行拆分
#include <stdio.h>
#include <stdlib.h>
int passno;
// node
typedef struct no {
int value;
struct no *next;
} no;
// list
typedef struct li {
no *head;
} li;
// show -- show a list
void
show(li *lst,const char *sym)
{
printf("%s:",sym);
for (no *cur = lst->head; cur != NULL; cur = cur->next)
printf(" %2d",cur->value);
printf("\n");
}
// newlist -- create a new list with N elements
li *
newlist(int count)
{
li *lst = malloc(sizeof(*lst));
no *cur;
no *prev;
lst->head = NULL;
prev = NULL;
for (int idx = 0; idx < count; ++idx) {
cur = malloc(sizeof(*cur));
cur->next = NULL;
cur->value = idx + 1;
if (prev != NULL)
prev->next = cur;
else
lst->head = cur;
prev = cur;
}
return lst;
}
// lstcount -- count number of elements in the list
int
lstcount(li *lst)
{
no *cur;
int count = 0;
for (cur = lst->head; cur != NULL; cur = cur->next)
++count;
return count;
}
// splitA -- split a list into two halves (single pointer, two pass version)
void
splitA(li *lstleft,li *lstright,li *lstfrom)
{
int count;
int idx;
no *cur;
no *left;
count = lstcount(lstfrom);
count = (count + 1) / 2;
left = NULL;
lstleft->head = NULL;
idx = 0;
for (cur = lstfrom->head; cur != NULL; cur = cur->next) {
if (++idx > count)
break;
// append to left list
if (left == NULL)
lstleft->head = cur;
left = cur;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur;
// zap the original list
lstfrom->head = NULL;
}
// splitB -- split a list into two halves (two pointer, one pass version)
void
splitB(li *lstleft,li *lstright,li *lstfrom)
{
no *cur1;
no *cur2;
no *left;
left = NULL;
lstleft->head = NULL;
cur2 = lstfrom->head;
for (cur1 = lstfrom->head; cur1 != NULL; cur1 = cur1->next) {
// wait for double speed pointer to end
if (cur2 == NULL)
break;
cur2 = cur2->next;
// append to left list
if (left == NULL)
lstleft->head = cur1;
left = cur1;
// advance at twice the rate
if (cur2 != NULL)
cur2 = cur2->next;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur1;
// zap the original list
lstfrom->head = NULL;
}
// clean -- free up list elements and list descriptor
void
clean(li *lst)
{
no *cur;
no *next;
for (cur = lst->head; cur != NULL; cur = next) {
next = cur->next;
free(cur);
}
free(lst);
}
// dotest -- test the split for a given number of nodes
void
dotest(int count)
{
li *big;
li *left;
li *right;
printf("\n");
printf("dotest: count=%d\n",count);
big = newlist(count);
show(big,"big");
left = newlist(0);
right = newlist(0);
switch (passno) {
case 1:
splitA(left,right,big);
break;
case 2:
splitB(left,right,big);
break;
}
show(left,"lhs");
show(right,"rhs");
clean(left);
clean(right);
clean(big);
}
int
main(int argc,char **argv)
{
--argc;
++argv;
if (argc > 0)
passno = atoi(*argv);
if (passno <= 0)
passno = 1;
if (passno > 2)
passno = 2;
printf("passno=%d\n",passno);
for (int count = 0; count <= 12; ++count)
dotest(count);
}
程序输出如下：
passno=1
dotest: count=0
big:
lhs:
rhs:
dotest: count=1
big: 1
lhs: 1
rhs:
dotest: count=2
big: 1 2
lhs: 1
rhs: 2
dotest: count=3
big: 1 2 3
lhs: 1 2
rhs: 3
dotest: count=4
big: 1 2 3 4
lhs: 1 2
rhs: 3 4
dotest: count=5
big: 1 2 3 4 5
lhs: 1 2 3
rhs: 4 5
dotest: count=6
big: 1 2 3 4 5 6
lhs: 1 2 3
rhs: 4 5 6
dotest: count=7
big: 1 2 3 4 5 6 7
lhs: 1 2 3 4
rhs: 5 6 7
dotest: count=8
big: 1 2 3 4 5 6 7 8
lhs: 1 2 3 4
rhs: 5 6 7 8
dotest: count=9
big: 1 2 3 4 5 6 7 8 9
lhs: 1 2 3 4 5
rhs: 6 7 8 9
dotest: count=10
big: 1 2 3 4 5 6 7 8 9 10
lhs: 1 2 3 4 5
rhs: 6 7 8 9 10
dotest: count=11
big: 1 2 3 4 5 6 7 8 9 10 11
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11
dotest: count=12
big: 1 2 3 4 5 6 7 8 9 10 11 12
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11 12