c - 交换链表项问题 C

Question

我正在尝试反转列表中的“信息”字段，如下所示

struct nodo {
    int info;
    struct nodo *next;
    struct nodo *prev;
    } ;
typedef struct nodo nodo;

这里是主要部分，两个输出应该是 n 个成员的原始列表和倒排列表(第一个值 go n ，第二个值 n-1 等等)

int main(int argc, const char * argv[]) {
    struct nodo *p;

    p = CreateList();
    PrintList(p);
    IvertList(p);
    Printlist(p);


    return 0;
    }

这里是 InvertList():(Count() 函数仅返回列表的维度，我知道这是一种困惑的方式，但我现在专注于结果)

void InvertList (struct nodo *p) {

int tmp = 0, num = 0, i = 0;

    num = (Count(p));
    tmp = num;

    for (i=1; i!=tmp; i++) {
        Swap(p,num);
        num--;
        }
   } 

这里是 Swap()，它应该将一个值(int info)带到列表的第一个位置，最后与每个位置交换:

void Swap (struct nodo *p, int n) {

    int *tmp1 = NULL, *tmp2 = NULL;
    int i;
    for ( i = 1;  i != n && p != NULL; i++) {
        tmp1 = &p->info;
        p = p->succ;
        tmp2 = &p->info;
        p->info = *tmp1;
        p->prec->info = *tmp2;

       }
    }

现在我打印的输出是:

Value: 1
Value: 2
Value: 3
Value: 4
Value: 5
Value: 1
Value: 1
Value: 1
Value: 1
Value: 1

其中最后 5 个值应为 5-4-3-2-1。

Answer 1

尽管代码中存在错误，但您根本没有反转物理列表，我可以保证这是练习的首要目的。

链表的反转意味着所有指针交换方向，旧的尾部变成新的头。您似乎在避免这种情况并尝试交换节点信息值。

要使用简单的指针交换来反转列表:

// note head pointer passed by address
void InvertList(node **pp)
{
    node *cur = *pp;
    while (cur)
    {
        node *tmp = cur->prev;
        cur->prev = cur->next;
        cur->next = tmp;
        *pp = cur;
        cur = cur->prev;
    }
}

并从 main() 调用为:

InvertList(&p);

请注意，不需要交换、复制等信息值。节点指针只需切换方向，它们的枚举将从另一端开始。完整的工作示例如下:

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int info;
    struct node *next;
    struct node *prev;
};
typedef struct node node;

static void PrintList(const node *head)
{
    while (head)
    {
        printf("%d: this=%p, prev=%p, next=%p\n",
               head->info, head, head->prev, head->next);
        head = head->next;
    }
}


static void InvertList(node **pp)
{
    node *cur = *pp;
    while (cur)
    {
        node *tmp = cur->prev;
        cur->prev = cur->next;
        cur->next = tmp;
        *pp = cur;
        cur = cur->prev;
    }
}

int main()
{
    node *prev = NULL, *head = NULL, **pp = &head;

    for (int i=1; i<=5; ++i)
    {
        *pp = malloc(sizeof **pp);
        (*pp)->info = i;
        (*pp)->prev = prev;
        prev = *pp;
        pp = &(*pp)->next;
    }
    *pp = NULL;

    PrintList(head); // prints 1,2,3,4,5
    InvertList(&head);
    PrintList(head); // prints 5,4,3,2,1
}

输出(地址显然不同)

1: this=0x1001054b0, prev=0x0, next=0x1001054d0
2: this=0x1001054d0, prev=0x1001054b0, next=0x1001054f0
3: this=0x1001054f0, prev=0x1001054d0, next=0x100105510
4: this=0x100105510, prev=0x1001054f0, next=0x100105530
5: this=0x100105530, prev=0x100105510, next=0x0
5: this=0x100105530, prev=0x0, next=0x100105510
4: this=0x100105510, prev=0x100105530, next=0x1001054f0
3: this=0x1001054f0, prev=0x100105510, next=0x1001054d0
2: this=0x1001054d0, prev=0x1001054f0, next=0x1001054b0
1: this=0x1001054b0, prev=0x1001054d0, next=0x0