论坛 › C\C++交流 › 指针逆序

h-b-z-d-j-s-m 发表于 2022-11-23 19:33:58

指针逆序

%5Burl=https://imgse.com/i/z8I8XV%5Dhttps://s1.ax1x.com/2022/11/23/z8I8XV.png
typedef int datatype;
typedef struct node
        {
                datatype data;
                struct node *next;
}linklist;

INVERT(linklist *head)
{
        linklist *p,*q;
        p=head->next;
        if(p!=NULL)
        {
                head->next=NULL;
                do
                {
                        q=p->next;
                        p->next=head->next;
                        head->next=p;
                        p=q;
                }
                while(p!=NULL);
        }
}

这个逆序怎么实现的啊，没咋看懂

jackz007 发表于 2022-11-23 19:49:19

本帖最后由 jackz007 于 2022-11-23 19:55 编辑

void INVERT(linklist ** head)                // head 头结点指针肯定会被修改，所以，这里应该传入二级指针
{
      linklist * p , * q , * next ;
      for(p = * head , q = NULL ; p ;) {
                next = p -> next             // 保存下一个节点信息，准备改变 p -> next 指针，
                p -> next = q       ;      // 让 p -> next 指向上一个遍历的节点，如果是原来的头结点，那么，q = NULL，成为新的尾节点
                q = p               ;      // 让 p 成为前一个节点，准备进入下一个节点
                p = next            ;      // 进入下一个节点，如果是原来的尾节点，那么，p = NULL，q 就是新的头结点
      }
      * head = q                  ;      // 循环结束后，q 自然就是新的头结点，必须把新的头结点指针返回主程序
}
      完整程序请参考此帖：https://fishc.com.cn/forum.php?mod=redirect&goto=findpost&ptid=221095&pid=6058652

两手空空儿 发表于 2022-11-24 19:32:29

小甲鱼老师的课后作业答案
这是代码
struct Node *reversed(struct Node *head)
{
      struct Node *pre;
      struct Node *cur;
   
      pre = NULL;
      cur = head;
      while(cur)
      {
                struct Node *next = cur->next;
                cur->next = pre;
                pre = cur;
                cur = next;
      }
   
      return pre;
}
链接：
https://fishc.com.cn/forum.php?mod=viewthread&tid=85453&extra=page%3D2%26filter%3Dtypeid%26typeid%3D570

人造人 发表于 2022-11-24 21:04:04

最简单的方法，对链表逆序遍历，然后把每一个元素都添加到另一个新链表里面
这很简单，但是效率不高

sh-5.1$ ls
list.c        list.h        main.c
sh-5.1$ cat main.c
#include "list.h"
#include <stdio.h>
#include <stdint.h>

void output(const list_t *list) {
    for(size_t i = 0; i < list_size(list); ++i) {
      size_t temp; list_get(list, i, &temp, sizeof(temp));
      printf("%zu ", temp);
    }
    puts("");
}

list_t *list_reverse(const list_t *list, size_t elem_size) {
    list_t *result = list_init();
    for(size_t i = list_size(list) - 1; i != -1; --i) {
      uint8_t buff;
      list_get(list, i, buff, elem_size);
      list_append(result, buff, elem_size);
    }
    return result;
}

int main(void) {
    list_t *list = list_init();
    for(size_t i = 1; i <= 10; ++i) {
      list_append(list, &i, sizeof(i));
    }
    list_t *lr = list_reverse(list, sizeof(size_t));
    output(list);
    output(lr);
    list_deinit(lr);
    list_deinit(list);
    return 0;
}
sh-5.1$ cat list.h
#ifndef _LIST_H_
#define _LIST_H_

#include <stddef.h>
#include <stdbool.h>

struct list_node_tag {
    void *data; size_t size;
    struct list_node_tag *next;
};

typedef struct {
    struct list_node_tag *head;
    size_t size;
} list_t;

list_t *list_init(void);
void list_deinit(list_t *list);
bool list_clean(list_t *list);
bool list_insert(list_t *list, size_t index, const void *data, size_t size);
bool list_delete(list_t *list, size_t index);
bool list_get(const list_t *list, size_t index, void *data, size_t size);
bool list_set(list_t *list, size_t index, const void *data, size_t size);
bool list_append(list_t *list, const void *data, size_t size);
size_t list_size(const list_t *list);
bool list_empty(const list_t *list);

#endif
sh-5.1$ cat list.c
#include "list.h"
#include <stdlib.h>
#include <memory.h>

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return NULL;
    list->head = NULL;
    list->size = 0;
    return list;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clean(list);
    free(list);
}

bool list_clean(list_t *list) {
    if(!list) return false;
    while(!list_empty(list)) if(!list_delete(list, 0)) return false;
    return true;
}

bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    if(list_size(list) < index) return false;
    if(!data) return false;
    struct list_node_tag **current = &list->head;
    while(index--) current = &(*current)->next;
    struct list_node_tag *node = malloc(sizeof(*node));
    if(!node) return false;
    node->data = malloc(size);
    if(!node->data) {free(node); return false;}
    memcpy(node->data, data, size);
    node->size = size;
    node->next = *current;
    *current = node;
    ++list->size;
    return true;
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(list_size(list) <= index) return false;
    struct list_node_tag **current = &list->head;
    while(index--) current = &(*current)->next;
    struct list_node_tag *temp = *current;
    *current = temp->next;
    free(temp->data); free(temp);
    --list->size;
    return true;
}

bool list_get(const list_t *list, size_t index, void *data, size_t size) {
    if(!list) return false;
    if(list_size(list) <= index) return false;
    if(!data) return false;
    struct list_node_tag *const *current = &list->head;
    while(index--) current = &(*current)->next;
    struct list_node_tag *temp = *current;
    if(temp->size > size) return false;
    memcpy(data, temp->data, temp->size);
    return true;
}

bool list_set(list_t *list, size_t index, const void *data, size_t size) {
    bool res = list_delete(list, index);
    return res ? list_insert(list, index, data, size) : res;
}

bool list_append(list_t *list, const void *data, size_t size) {
    if(!list) return false;
    return list_insert(list, list_size(list), data, size);
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list_size(list) == 0;
}
sh-5.1$ gcc -g -Wall -o main main.c list.c
sh-5.1$ ls
list.c        list.h        mainmain.c
sh-5.1$ ./main
1 2 3 4 5 6 7 8 9 10
10 9 8 7 6 5 4 3 2 1
sh-5.1$

人造人 发表于 2022-11-25 12:07:50

这次用递归的方式逆序，效率也不高
其实我是想把逆序链表的函数写到list.c里面的，这样可以直接操作底层结构，效率更高，但是最终还是没有这样做，因为这违背了我写这个代码的初衷，我写这个代码的目的并不是为了效率
因为做了这样的尝试，所以list.c内部的逻辑也发生了有点大的变化，不过对外没有改变，外面是看不到这个变化的，这就是定义良好的接口带来的好处

sh-5.1$ ls
list.c        list.h        main.c
sh-5.1$ cat main.c
#include "list.h"
#include <stdio.h>

void output(const list_t *list, size_t index) {
    if(index >= list_size(list)) return;
    size_t temp; list_get(list, index, &temp, sizeof(temp));
    printf("%zu ", temp);
    output(list, index + 1);
}

list_t *list_reverse(const list_t *list, size_t index) {
    if(index >= list_size(list)) return list_init();
    list_t *result = list_reverse(list, index + 1);
    size_t temp; list_get(list, index, &temp, sizeof(temp));
    list_append(result, &temp, sizeof(temp));
    return result;
}

int main(void) {
    list_t *list = list_init();
    for(size_t i = 0; i < 10; ++i) {
      list_append(list, &i, sizeof(i));
    }
    list_t *lr = list_reverse(list, 0);
    output(list, 0); puts("");
    output(lr, 0); puts("");
    list_deinit(lr);
    list_deinit(list);
    return 0;
}
sh-5.1$ cat list.h
#ifndef _LIST_H_
#define _LIST_H_

#include <stddef.h>
#include <stdbool.h>

struct list_node_tag {
    void *data; size_t size;
    struct list_node_tag *next;
};

typedef struct {
    struct list_node_tag *head;
    size_t size;
} list_t;

list_t *list_init(void);
void list_deinit(list_t *list);
bool list_clean(list_t *list);
bool list_insert(list_t *list, size_t index, const void *data, size_t size);
bool list_delete(list_t *list, size_t index);
bool list_get(const list_t *list, size_t index, void *data, size_t size);
bool list_set(list_t *list, size_t index, const void *data, size_t size);
bool list_append(list_t *list, const void *data, size_t size);
size_t list_size(const list_t *list);
bool list_empty(const list_t *list);

#endif
sh-5.1$ cat list.c
#include "list.h"
#include <stdlib.h>
#include <string.h>

static struct list_node_tag *new_node(const void *data, size_t size) {
    struct list_node_tag *result = malloc(sizeof(*result));
    if(!result) return NULL;
    result->data = malloc(size);
    if(!result->data) {free(result); return NULL;}
    memcpy(result->data, data, size);
    result->size = size;
    result->next = NULL;
    return result;
}

static void free_node(struct list_node_tag *n) {
    free(n->data);
    free(n);
}

static struct list_node_tag *const *locate_node_const(const list_t *list, size_t index) {
    struct list_node_tag *const *result = &list->head;
    while(index--) result = &(*result)->next;
    return result;
}

static struct list_node_tag **locate_node(list_t *list, size_t index) {
    return (struct list_node_tag **)locate_node_const(list, index);
}

list_t *list_init(void) {
    list_t *list = malloc(sizeof(*list));
    if(!list) return NULL;
    list->head = NULL;
    list->size = 0;
    return list;
}

void list_deinit(list_t *list) {
    if(!list) return;
    list_clean(list);
    free(list);
}

bool list_clean(list_t *list) {
    if(!list) return false;
    while(!list_empty(list)) if(!list_delete(list, 0)) return false;
    return true;
}

bool list_insert(list_t *list, size_t index, const void *data, size_t size) {
    if(!list) return false;
    if(list_size(list) < index) return false;
    if(!data) return false;
    struct list_node_tag **current = locate_node(list, index);
    struct list_node_tag *node = new_node(data, size);
    if(!node) return false;
    node->next = *current;
    *current = node;
    ++list->size;
    return true;
}

bool list_delete(list_t *list, size_t index) {
    if(!list) return false;
    if(list_size(list) <= index) return false;
    struct list_node_tag **current = locate_node(list, index);
    struct list_node_tag *temp = *current;
    *current = temp->next;
    free_node(temp);
    --list->size;
    return true;
}

bool list_get(const list_t *list, size_t index, void *data, size_t size) {
    if(!list) return false;
    if(list_size(list) <= index) return false;
    if(!data) return false;
    struct list_node_tag *current = *locate_node_const(list, index);
    if(current->size > size) return false;
    memcpy(data, current->data, current->size);
    return true;
}

bool list_set(list_t *list, size_t index, const void *data, size_t size) {
    bool res = list_delete(list, index);
    return res ? list_insert(list, index, data, size) : res;
}

bool list_append(list_t *list, const void *data, size_t size) {
    if(!list) return false;
    return list_insert(list, list_size(list), data, size);
}

size_t list_size(const list_t *list) {
    if(!list) return 0;
    return list->size;
}

bool list_empty(const list_t *list) {
    if(!list) return true;
    return list_size(list) == 0;
}
sh-5.1$ gcc -g -Wall -o main main.c list.c
sh-5.1$ ./main
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0
sh-5.1$

查看完整版本: 指针逆序