问题：

C与双链表交换

侯博易

2023-03-14

我试图交换链表中节点的位置，然后使用排序函数进行排序。这两个函数中的任何一个都有逻辑错误。当我运行这个程序时，它会无限循环。

更新代码

int adjuctNodes(struct student_record_node** n1, struct student_record_node** n2)

{
      struct student_record_node* prev_;
      struct student_record_node* next_;  
      return((*n1)->next_==(*n2) && (*n2)->prev_ == (*n1))||
      ( (*n1)->prev_ ==(*n2) && (*n2)->next_ == (*n1) );
}

void updateOuterPointer(struct student_record_node** n)

{
     struct student_record_node* next_;
     struct student_record_node* prev_;
     if((*n)->next_!=NULL)
             (*n)->prev_->next_=(*n);
     if((*n)->next_ !=NULL)
             (*n)->next_->prev_=(*n);
}


/*Swaping */

void swap(struct student_record_node** node1, struct student_record_node** node2)

{


          struct student_recod_node* prev_;
          struct student_recod_node* next_;
          struct student_record_node* ptr=(*node1)->next_;

             if(adjucntNodes((node1),(node2)))
     {
             (node1)->prev_=pnode2;
             (node2)->prev_=pnode0;
             (node1)->next_=pnode3;
             (node2)->next_=pnode1;

     }else{

             (node1)->prev_=pnode1;
             (node2)->prev_=pnode0;
             (node1)->next_=pnode3;
             (node2)->next_=pnode2;
     }

     updateOuterPointer((node1));
     updateOuterPointer((node2));

} 
 /*Sorting linked list*/


void sort(struct student_record_node**recordsHead,int(*compare_fcn)(struct  
student_record_node*,struct student_record_node*))

 {

         int swapped;
         struct student_record_node *ptr1=*recordsHead;
         struct student_record_node *lptr = NULL;

         if (ptr1 == NULL)
                 return;

         do
         {
                 swapped = 0;
                 ptr1 = *recordsHead;


                 while (ptr1->next_ != lptr)
                 {
                              if (compare_fcn(ptr1,ptr1->next_))
                         {
                                 printf("swapping\n");
                                swap(&ptr1,&ptr1->next_);
                                if(ptr1==*recordsHead)
                                 {
                                    (*recordsHead)=ptr1->next_;
                                 }
                                 swapped=1;

                         }

                         else ptr1 = ptr1->next_;
                 }
                    lptr = ptr1;
                         ;
         }
         while (swapped);


}

共有2个答案

闾丘玮

2023-03-14

为了处理节点相邻或不相邻的情况，首先交换两个节点的（外部）指针，然后交换两个节点的（内部）指针。如果节点相邻，这将根据需要旋转指针，如果节点不相邻，交换指针对。注意，如果节点相邻，其中一个“外部”指针将是“其他”节点的内部指针之一，反之亦然，但它仍然有效：首先交换“外部”指针，然后交换“内部”指针。

在进行交换时，请确保根据需要使用临时指针（从技术上讲是指向节点指针的指针），否则会在交换操作的一段时间内覆盖节点指针。如果卡住了，我可以稍后用一个例子进行更新。

更新-图表类型示例，以显示发生了什么为例，使用带有下一个指针的单链表作为示例。假设从5个节点开始，从0到4：

0->1->2->3->4

交换1和3，0-

0->3
2->1

然后交换1-

1->4
3->2

导致了

0->3->2->1->4

从0-开始

0->2
1->1

然后交换1-

1->3
2->1

导致了

0->2->1->3->4

示例交换代码。该代码假设有头指针指向第一个节点，尾指针指向最后一个节点（或NULL）。

struct student_record_node *Head = &firstnode;  /* head */
struct student_record_node *Tail = &lastnode;   /* tail (NULL is ok) */

/* swap function */

void swap(struct student_record_node **Head,
          struct student_record_node **Tail,
          struct student_record_node *node1,
          struct student_record_node *node2)
{
struct student_record_node **en1 /* & external next ptr to 1 */
struct student_record_node **en2 /* & external next ptr to 2 */
struct student_record_node **ep1 /* & external prev ptr to 1 */
struct student_record_node **ep2 /* & external prev ptr to 2 */
struct student_record_node  *tmp /* temp node ptr */
    en1 = (node1->prev_ != NULL) ? &(node1->prev_->next_) : Head;
    en2 = (node2->prev_ != NULL) ? &(node2->prev_->next_) : Head;
    ep1 = (node1->next_ != NULL) ? &(node1->next_->prev_) : Tail;
    ep2 = (node2->next_ != NULL) ? &(node2->next_->prev_) : Tail;
    /* swap en1, en2 */
    tmp = *en1;
    *en1 = *en2;
    *en2 = tmp;
    /* swap ep1, ep2 */
    tmp = *ep1;
    *ep1 = *ep2;
    *ep2 = tmp;
    /* swap n1, n2 next_ */
    tmp = node1->next_;
    node1->next_ = node2->next_;
    node2->next_ = tmp;
    /* swap n1, n2 prev_ */
    tmp = node1->prev_;
    node1->prev_ = node2->prev_;
    node2->prev_ = tmp;
}

    /* call to swap function */
    swap(&Head, &Tail, node1, node2);

梁俊智

2023-03-14

原始代码中有两个主要问题，可能还有第三个问题：

当被交换的节点相邻时，交换函数不起作用，但是排序函数只交换相邻的节点！
交换两个节点后ptr1和ptr1-

此外，交换函数的接口可以简化，因为不需要将指针传递给指向节点的指针。

以下示例程序修复了上述问题：

#include <stdio.h>
#include <string.h>

struct student_record_node {
    struct student_record_node *next_;
    struct student_record_node *prev_;
    const char *name;
    unsigned int age;
};

void swap(struct student_record_node *node1, struct student_record_node *node2)
{
    struct student_record_node *ptr1, *ptr2;

    /* Swap the 'next_' pointers, taking adjacency into account. */
    ptr1 = node1 == node2->next_ ? node2 : node2->next_;
    ptr2 = node2 == node1->next_ ? node1 : node1->next_;
    node1->next_ = ptr1;
    node2->next_ = ptr2;
    /* Swap the 'prev_' pointers, taking adjacency into account. */
    ptr1 = node1 == node2->prev_ ? node2 : node2->prev_;
    ptr2 = node2 == node1->prev_ ? node1 : node1->prev_;
    node1->prev_ = ptr1;
    node2->prev_ = ptr2;
    /* Fix the links from other nodes. */
    if (node1->next_) node1->next_->prev_ = node1;
    if (node1->prev_) node1->prev_->next_ = node1;
    if (node2->next_) node2->next_->prev_ = node2;
    if (node2->prev_) node2->prev_->next_ = node2;
}

int compare_ages(const struct student_record_node *a,
        const struct student_record_node *b)
{
    return a->age < b->age ? -1 : a->age > b->age ? 1 : 0;
}

int compare_names(const struct student_record_node *a,
        const struct student_record_node *b)
{
    return strcmp(a->name, b->name);
}

void sort(struct student_record_node **recordsHead,
        int(*compare_fcn)(const struct student_record_node *,
                const struct student_record_node *))
{
    int swapped;
    struct student_record_node *ptr1;
    struct student_record_node *lptr = NULL;

    if (*recordsHead == NULL)
        return;

    do
    {
        swapped = 0;
        ptr1 = *recordsHead;

        while (ptr1->next_ != lptr)
        {
            if (compare_fcn(ptr1, ptr1->next_) > 0)
            {
                printf("swapping (%s:%u <=> %s:%u)\n", ptr1->name, ptr1->age,
                        ptr1->next_->name, ptr1->next_->age);
                swap(ptr1, ptr1->next_);
                if (ptr1 == *recordsHead)
                {
                    /* ptr1 is now the second node. */
                    (*recordsHead) = ptr1->prev_;
                }
                swapped = 1;
            }
            else
            {
                ptr1 = ptr1->next_;
            }
        }
        lptr = ptr1;
    }
    while (swapped);
}

void dump(const struct student_record_node *students)
{
    const struct student_record_node *prev_ = NULL;
    unsigned int pos = 0;

    while (students)
    {
        if (students->prev_ != prev_)
        {
            printf("[%u] ** Bad prev_ link!\n", pos);
        }
        printf("[%u] %s:%u\n", pos, students->name, students->age);
        pos++;
        prev_ = students;
        students = students->next_;
    }
}

int main(void)
{
    static struct student_record_node testdata[] =
    {
        { testdata + 1, NULL, "susan", 20 },
        { testdata + 2, testdata + 0, "bill", 21 },
        { testdata + 3, testdata + 1, "joe", 18 },
        { testdata + 4, testdata + 2, "tom", 19 },
        { NULL, testdata + 3, "karen", 21 },
    };
    struct student_record_node *students = testdata;

    puts("Original order:");
    dump(students);
    puts("By name:");
    sort(&students, compare_names);
    dump(students);
    puts("By age:");
    sort(&students, compare_ages);
    dump(students);
    return 0;
}

输出：

Original order:
[0] susan:20
[1] bill:21
[2] joe:18
[3] tom:19
[4] karen:21
By name:
swapping (susan:20 <=> bill:21)
swapping (susan:20 <=> joe:18)
swapping (tom:19 <=> karen:21)
swapping (susan:20 <=> karen:21)
[0] bill:21
[1] joe:18
[2] karen:21
[3] susan:20
[4] tom:19
By age:
swapping (bill:21 <=> joe:18)
swapping (karen:21 <=> susan:20)
swapping (karen:21 <=> tom:19)
swapping (bill:21 <=> susan:20)
swapping (bill:21 <=> tom:19)
swapping (susan:20 <=> tom:19)
[0] joe:18
[1] tom:19
[2] susan:20
[3] bill:21
[4] karen:21

类似资料：

双向链表交换

我正在尝试交换双链接列表中的两个节点。下面是具有交换功能的程序部分。当我运行这个程序时，在第一个和第二个节点的情况下，它崩溃了。而在任何其他节点的情况下，它提供无限循环输出。（例如：-2- 我知道还有一些关于节点交换的问题，但是我没有找到任何与我的问题相似的问题。请帮帮我...！！提前谢谢。
Java双链表，交换节点

我在Java中实现一个双链接列表时遇到了一个问题。特别是要交换2个以下节点（在我的例子中，一个节点包含一个政治候选人）。假设下面的DLL： head- 作为输出，我没有从头到尾的正确DLL，但从头到尾都很好：我已经写了几个版本的这个方法reverseTwoNode。我甚至尝试在节点内部交换数据，而不是交换节点，我也有同样的问题。你能帮我真是太好了，我花了这么多时间在这个简单的功能上，我看不出有
C-双链表总是空的

我正在用以下数据结构编写双向链表程序：在下面的函数中，我将文本文件中的数据读取到链表中，文件内容如下所示：这是创建列表的功能，问题可能在这里：它没有向列表中添加新节点，只是用新节点替换了第一个节点。最后，链接列表只有1条记录，这是文本文件中的最后一条。我该如何修复代码？谢谢！这是检查输入的功能：
列出双向链表C项

我是C语言的新手。我正在尝试创建一个双链接列表，其中数据字段是一个结构。但是当我输出元素时，只有结构的第一个字段正确显示。所以，我有几个问题。我是否正确声明了节点值字段？我是否正确地插入了列表末尾的节点？双向链表项的输出正确吗？我的错误在哪里，如何纠正？
双链表

我写了一个程序，通过双链表管理银行账户，但我发现取消程序有问题。我仍然有同样的问题，即使我尝试了这个方法：-（pnt）-
插入C中的双向链表

我的程序不断崩溃。我觉得我的逻辑有问题。请帮忙！谢谢

C与双链表交换

共有2个答案

相关问答

相关文章

相关阅读

相关工具

相关文档