当前位置：首页 > news >正文

数据结构1_C---单链表的逆转

news 来源：原创 2024/5/19 11:48:23

通过C语言函数实现单链表的逆转操作

例：

输入数据1，2,3,4

输出数据4，3,2,1

一共三个文件：

头文件stulist,h :链表结点的定义，结点指针的定义

源文件stulist.c：具体的实现函数，主要包括三个，打印链表，创建链表和反转链表

测试文件test.c：调用实现功能；

stulist.c文件内容

 1 include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 #include"stulist.h"
 5 
 6 List Reverse(List L) {
 7     List head, p, q, r;
 8     head = L;
 9     p = L;
10     int n=0;
11     while (p->Next) {             //统计链表长度，使p指针指向最后一个结点
12         n++;
13         p = p->Next;
14     }
15     n++;
16     if (n == 1) {                //如果链表只有一个结点，直接返回
17         return head;
18     }else if (n == 2) {          //如果链表有两个结点，单独操作，实现反转
19         p = head;
20         q = p->Next;
21         head->Next = NULL;
22         q->Next = p;
23         head = q;
24         return head;
25     }
26     else {                       //如果链表有三个或三个以上结点，则通过三个指针交互操作，实现链表反转，此处遍历到最后一结点后单独操作，并将头结点指向该节点。
27         p = head;                 //p指向第一个结点，q指向第二个结点，r指向第三个结点
28         q = p->Next;
29         r = q->Next;
30         head->Next = NULL;
31         for (int i = 0; i < n - 2; i++) {
32             q->Next = p;
33             p = q;
34             q = r;
35             r = r->Next;
36         }
37         head = q;
38         head->Next = p;
39     }
40     return head;                    //返回头结点
41 }
42 List Read() /* 细节在此不表 */
43 {
44     //创建一个链表
45     List head, p,q;
46     int data;
47     head = NULL;
48     q = head;
49     while (1) {
50         printf("请输入学生记录：\n");
51         scanf("%d", &data);
52         if (data < 0) {
53             break;
54         }
55         p = (PtrToNode)malloc(sizeof(List));
56         p->Data = data;
57         if (head == NULL) {
58             head = p;
59         }
60         else {
61             q->Next = p;
62         }
63         q = p;
64         if (head != NULL) {
65             q->Next = NULL;
66         }
67     }
68     return head;
69 }
70 void Print(List L) /* 细节在此不表 */
71 {
72     List p;
73     p = L;
74     printf("记录\n");
75     int i = 1;
76     while (p) {
77         printf("%d\t%d\n",i, p->Data);
78         p = p->Next;
79         i++;
80     }
81 }

stulist,h文件

#include<stdio.h>
#include<stdlib.h>
#define LEN sizeof (struct stu_node)
typedef struct Node *PtrToNode;
struct Node {
    int Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */
typedef int ElementType;

test.c文件

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stulist.h"

int main()
{
    List L1, L2;
    L1 = Read();
    Print(L1);
    L2 = Reverse(L1);
    Print(L2);

    char mmmmm[10];
    gets_s(mmmmm);
    getchar();
    return 0;
}