(数据结构C语言版)顺序表和单链表的逆置

ｃ语⾔链表逆序的问题去⾯试被问到⼀个问题，怎么把⼀个链表反转(⽤原链表)，⾃⼰在⽹上找了到了⼀篇⽂章，/sicofield/article/details/8850269，原作者给出了三种⽅法，⽅法⼀：将链表数据全部读到数组中，然后在倒序输出。

⽅法⼆：就是我下⾯要讲的。

⽅法三：从第⼆个结点开始，把之后的每个结点都插⼊到第⼀个结点之后，最后在把第⼀个结点挪到表尾。

第⼆种⽅法的思路是：从第⼆个结点开始，记录它的下个结点，把它挪到第⼀个结点之前，成为新表头，然后下个结点继续这个过程。

1struct stu *reserve(struct stu *head)2 {3struct stu *p1,*p2,*p3; 4 p1=head;5 p2=p1->next; //　这个结点为要移动的结点6while(p2)7 {8 p3=p2->next; //记录的为要移动的结点的下⼀个结点9 p2->next=p1; //移动结点到最前10 p1=p2; //移动的结点变为新表头11 p2=p3; //下个结点变为要移动的结点12 }13 head->next=NULL; //移动完毕后head变为表尾，让它指向为空14 head=p1; 15return head;16 }⽅法三的贴下原作者的代码加上⾃⼰的思路：1struct stu *reserve(struct stu *head)2 {3struct stu *p,*q;4 p=head->next; //记录第⼆个结点5while(p->next!=NULL)6 {7 q=p->next; //记录要移动的结点8 p->next=q->next; //把该结点从原链表中移除9 q->next=head->next; //把该结点连接到head之后10 head->next=q;11 }12 p->next=head; //把head移动到新表尾，此时链表成环13 head=p->next->next; //找到移动完之后的新head14 p->next->next=NULL; //断开环15return head;1617 }。

C语⾔单链表逆置的代码实现（简单易懂版） 嗯，，这是⾃⼰写的第⼀篇博客哈，写的不好⼤家不要见怪，主要是想把⾃⼰的⼀些思想分享给⼤家。

也欢迎⼤家指出错误，⼀同进步。

话不多说，直接先说想法。

要把⼀个单链表逆置，可以⼤致分为下列⼏步。

先创建⼀个链表。

然后要考虑到链表的逆置实现。

最后是链表的输出。

有了这样过⼏步⼤概的想法之后，我们便要来⼀步步的实现啦。

嗯，，创建链表就不说了，⼤家都会。

然后呢就是链表的逆置，这⾥我是采⽤的就地逆置法，，嗯，反正我是这么叫的，⼤家可以参考⼀下。

当然啦，你得考虑到函数的形参和返回值以及指针的交接，这⾥如果出了问题，编译器是不会报错的，所以⼤家务必多加注意。

其余的⼩问题还是看代码吧。

额，，之前画的草图不见了，，现在也没有办法给⼤家画个草图演⽰⼀下，很抱歉啊。

如果⼤家看不懂链表逆置可以画个草图⾃⼰看看，应该就差不多了1 #include <stdio.h>2 #include <stdlib.h>34struct student5 {6int data;7struct student *next;8 };910int iCount; //定义全局变量保存代码长度1112struct student *Create()13 {14struct student *pHead = NULL;15struct student *pNew,*pEnd;16 iCount = 0;17 pEnd = pNew = (struct student*)malloc(sizeof(struct student));18 printf("请输⼊数据:");19 scanf("%d",&pNew->data);20while(pNew->data!=0)21 {22 iCount++;23if(iCount == 1) //从本条if语句开始就要多注意指针的交接了哦，⽐较容易错24 {25 pNew->next = NULL;26 pEnd = pNew;27 pHead = pNew;28 }29else30 {31 pNew->next = NULL;32 pEnd->next = pNew;33 pEnd = pNew;34 }35 pNew = (struct student*)malloc(sizeof(struct student));36 printf("请输⼊数据:");37 scanf("%d",&pNew->data);38 }39free(pNew);40return pHead;41 }4243struct student *reverse(struct student *pHead) //链表逆置函数44 {45struct student *p,*q,*t; //p为前置指针，q为后置指针，t为交换指针46 q = pHead;47 p = (q->next);48 q->next = NULL;49while(t!=NULL)50 {51 t = p->next;52 p->next = q;53 q = p;54if(t!=NULL) p = t;55else;56 }57return (p);58 }5960void showlist(struct student *pHead) //指针输出函数61 {62struct student *temp;63 temp = pHead;6465while(temp)66 {67 printf(" %d ",temp->data);68 temp = temp->next;69 }70 printf("\n");71 }7273int main()74 {75struct student *first;7677 first = Create();78 printf("链表逆置前的数据:");79 showlist(first);8081 first = reverse(first);8283 printf("链表逆置后的数据:");84 showlist(first);8586return0;87 }。

数据结构(c语言版)课后习题答案完整版数据结构(C语言版)课后习题答案完整版一、数据结构概述数据结构是计算机科学中一个重要的概念，用来组织和存储数据，使之可以高效地访问和操作。

在C语言中，我们可以使用不同的数据结构来解决各种问题。

本文将提供完整版本的C语言数据结构的课后习题答案。

二、顺序表1. 顺序表的定义和基本操作顺序表是一种线性表，其中的元素在物理内存中连续地存储。

在C 语言中，我们可以通过定义结构体和使用指针来实现顺序表。

以下是顺序表的一些基本操作的答案：（1）初始化顺序表```ctypedef struct{int data[MAX_SIZE];int length;} SeqList;void InitList(SeqList *L){L->length = 0;}```（2）插入元素到顺序表中```cbool Insert(SeqList *L, int pos, int elem){if(L->length == MAX_SIZE){return false; // 顺序表已满}if(pos < 1 || pos > L->length + 1){return false; // 位置不合法}for(int i = L->length; i >= pos; i--){L->data[i] = L->data[i-1]; // 向后移动元素 }L->data[pos-1] = elem;L->length++;return true;}```（3）删除顺序表中的元素```cbool Delete(SeqList *L, int pos){if(pos < 1 || pos > L->length){return false; // 位置不合法}for(int i = pos; i < L->length; i++){L->data[i-1] = L->data[i]; // 向前移动元素 }L->length--;return true;}```（4）查找顺序表中的元素```cint Search(SeqList L, int elem){for(int i = 0; i < L.length; i++){if(L.data[i] == elem){return i + 1; // 找到元素，返回位置 }}return -1; // 未找到元素}```2. 顺序表习题解答（1）逆置顺序表```cvoid Reverse(SeqList *L){for(int i = 0; i < L->length / 2; i++){int temp = L->data[i];L->data[i] = L->data[L->length - 1 - i]; L->data[L->length - 1 - i] = temp;}}```（2）顺序表元素去重```cvoid RemoveDuplicates(SeqList *L){for(int i = 0; i < L->length; i++){for(int j = i + 1; j < L->length; j++){if(L->data[i] == L->data[j]){Delete(L, j + 1);j--;}}}}```三、链表1. 单链表单链表是一种常见的链式存储结构，每个节点包含数据和指向下一个节点的指针。

数据结构之顺序表和链表的就地逆置源代码//顺序表和链表的就地逆置#include<stdio.h>#include<mlloc.h>#deine mxsize 100struct dt //为链表的处理做结构体定义{int m;dt *next;}; //子函数，每种数据结构两个函数，前者是顺序表，后者是链表void disply1(int [],int num);void inverse1(int [],int num);void disply2(dt *b,int num);void inverse2(dt *b,int num);void min(){int i,num1,num2;int [mxsize];dt *b,*p,*q;//顺序表的就地逆置print("请输入需要创建的顺序表的长度:\n");scn("%d",&num1);print("请输入顺序表的关键字:\n");or(i=0;i<num1;i++){lush(stdin); //清除输入缓存scn("%d",&[i]);}print("创建的顺序表为:\n");disply1(,num1);inverse1(,num1); //地址传递print("\n就地逆置后的顺序表:\n");disply1(,num1);//链表的就地逆置print(" \n请输入需要创建的链表的长度:\n");scn("%d",&num2);print("请输入链表的关键字:\n");b=(dt*)mlloc(sizeo(dt)); //申请内存空间b->next=NULL; //链表含有头结点q=b;or(i=0;i<num2;i++){p=(dt*)mlloc(sizeo(dt));lush(stdin);scn("%d",&p->m);p->next=q->next;q->next=p;q=q->next;}print("创建的链表为:\n");disply2(b,num2);inverse2(b,num2); //地址传递print("\n就地逆置后的链表:\n");disply2(b,num2);}void disply1(int [],int num){int i;or(i=0;i<num;i++){print("-%d-",[i]);}}void inverse1(int [],int num){int *p,*q,t;p=&[0]; //指向第一个数q=&[num-1]; //指向最后一个数while(p<q) //算法是：前后指针所指的数值交换，然后向中间靠拢，直到p<q停止{t=*p;*p=*q;*q=t;p++;q--;}}void disply2(dt *b,int num){dt *t;t=b->next;while(t!=NULL){print("-%d-",t->m);t=t->next;}}void inverse2(dt *b,int num){dt *p,*q;int i,j,t;or(i=1;i<=num-1;i++) //算法类似于冒泡排序{p=b->next;q=p->next;or(j=num-i;j>0;j--){t=p->m;p->m=q->m;q->m=t;p=p->next;q=q->next;}}}。

标题：C语言编程ACM：链表的逆置一、概述ACM（Advanced Computing Machinery）竞赛是计算机科学领域最负盛名的竞赛之一，要在ACM竞赛中获得优异的成绩，熟练掌握C 语言编程技术是必不可少的。

本文将讨论C语言编程中常见的ACM题目之一：链表的逆置。

二、链表的基本概念1.链表的定义链表是一种线性表的物理存储单位，由一个个节点组成，每个节点包含数据元素和下一个节点的指针。

链表中的数据元素可以是任意类型。

2.链表的基本操作在C语言中，链表的基本操作包括插入节点、删除节点、查找节点等。

而链表的逆置就是将链表中的节点顺序颠倒。

三、链表的逆置方法在C语言中，链表的逆置可以采用多种方法实现。

1.迭代法迭代法是最直接的方法，具体步骤如下：（1）初始化三个指针，分别指向当前节点、前一节点、后一节点。

（2）遍历链表，将当前节点的指针指向前一节点。

（3）更新前一节点和当前节点的位置。

（4）遍历结束后，前一节点指向NULL，表示逆置完成。

2.递归法递归法是一种更为巧妙的方法，具体步骤如下：（1）递归遍历链表，直至到达链表尾部。

（2）从链表尾部开始，逐一修改每个节点的指针指向。

（3）递归结束后，链表即被逆置。

四、链表逆置的C语言实现以下是链表逆置的C语言实现代码，以迭代法为例：```ctypedef struct Node {int data;struct Node* next;} Node;Node* reverseList(Node* head) {Node *prev = NULL, *curr = head, *next = NULL; while (curr) {next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```五、实例分析假设有一个链表的头指针为head，包含数据元素1、2、3、4、5。

c语言实现顺序表的增删查改逆置简单代码1. 顺序表的定义顺序表是一种线性表，其元素在内存中按顺序存储，每个元素占用连续的存储单元。

顺序表的特点是存取速度快，但插入和删除元素时需要移动大量的元素。

顺序表可以用结构体来表示，其定义如下：typedef struct_SeqList {int*data; // 指向数据元素的指针int size; // 顺序表的长度int capacity; // 顺序表的容量} SeqList;2. 顺序表的初始化顺序表的初始化需要分配内存空间来存放数据元素。

可以使用以下代码来初始化顺序表：SeqList*init_seq_list(int capacity) {SeqList*list= (SeqList*)malloc(sizeof(SeqList));if (list==NULL) {return NULL;}list->data= (int*)malloc(sizeof(int) *capacity);if (list->data==NULL) {free(list);return NULL;}list->size=0;list->capacity=capacity;return list;}3. 顺序表的插入在顺序表中插入元素需要移动后面的元素，以保证元素的顺序性。

可以使用以下代码在顺序表中插入元素：int insert_seq_list(SeqList*list, int index, int value) {if (index<0||index>list->size) {return-1;}if (list->size==list->capacity) {// 扩容顺序表int*new_data= (int*)realloc(list->data, sizeof(int) *list->capacity*2);if (new_data==NULL) {return-1;}list->data=new_data;list->capacity*=2;}// 移动后面的元素for (int i=list->size; i>index; i--) {list->data[i] =list->data[i-1];}// 插入元素list->data[index] =value;list->size++;return0;}4. 顺序表的删除从顺序表中删除元素需要移动后面的元素，以保证元素的顺序性。

C语⾔实现单链表逆序与逆序输出实例单链表的逆序输出分为两种情况，⼀种是只逆序输出，实际上不逆序；另⼀种是把链表逆序。

本⽂就分别实例讲述⼀下两种⽅法。

具体如下：1.逆序输出实例代码如下：#include<iostream>#include<stack>#include<assert.h>using namespace std;typedef struct node{int data;node * next;}node;//尾部添加node * add(int n, node * head){node * t = new node;t->data = n;t->next = NULL;if (head == NULL){head = t;}else if (head->next == NULL){head->next = t;}else{node * p = head->next;while (p->next != NULL){p = p->next;}p->next = t;}return head;}//顺序输出void print(node * head){node * p = head;while (p != NULL){cout << p->data << " ";p = p->next;}cout << endl;}//递归void reversePrint(node * p){if (p != NULL){reversePrint(p->next);cout << p->data << " ";}}//栈void reversePrint2(node * head){stack<int> s;while (head != NULL){s.push(head->data);head = head->next;}while (!s.empty()){cout << s.top() << " ";s.pop();}}int main(){node * head = NULL;for (int i = 1; i <= 5; i++){head = add(i, head);}print(head);reversePrint(head);reversePrint2(head);system("pause");return 0;}逆序输出可以⽤三种⽅法: 递归，栈，逆序后输出。

以下是使用C语言实现单链表逆置的示例代码：c复制代码#include<stdio.h>#include<stdlib.h>// 定义链表节点结构体struct ListNode {int val;struct ListNode *next;};// 定义函数用于链表逆置struct ListNode* reverseList(struct ListNode* head) {struct ListNode *prev =NULL;struct ListNode *curr = head;while (curr != NULL) {struct ListNode *next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}// 创建链表并逆置int main() {struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));head->val = 1;head->next = NULL;struct ListNode *node2 = (struct ListNode*)malloc(sizeof(struct ListNode));node2->val = 2;node2->next = NULL;struct ListNode *node3 = (struct ListNode*)malloc(sizeof(struct ListNode));node3->val = 3;node3->next = NULL;head->next = node2;node2->next = node3;struct ListNode *newHead = reverseList(head);while (newHead != NULL) {printf("%d ", newHead->val);newHead = newHead->next;}return0;}在上面的代码中，我们首先定义了链表节点结构体，其中包含一个整数值和一个指向下一个节点的指针。

什么单链表的逆置问题描述设计一个程序，实现单链表的逆置。

一、需求分析⑴按程序提示输入并创建一个单链表，带有头结点⑵可自定义链表的长度，可自定义链表储存的数据类型，注意更改相应的输入输出方式⑶实现单链表的逆置，直观地输出结果二、概要设计为实现上述程序功能，需创建以下抽象数据类型：ADT LinkList {数据对象：D={ai|ai∈（0，1，…，9），i=0,1，2，…，n，n≥0}数据关系：R={<ai-1,ai>|ai-1,ai∈D,i=1,2，…，n}基本操作：InitList（&L）操作结果：初始化一个链表L。

CreatList（L，L_Length）初始条件：链表L已存在。

操作结果：创建一个长度为L_Length的单链表。

InverseList（L）初始条件：链表L已存在。

操作结果：将单链表逆置。

DisplayList（L）初始条件：链表L已存在。

操作结果：销毁链表L。

} ADT LinkList本程序包含四个模块，即1）主程序模块，接受命令2）初始化及链表创建模块，按要求创建链表3）单链表逆置模块，实现单链表的逆置4）显示模块，输出结果三、详细设计（C语句，而非伪码）1.元素类型、节点类型和指针类型的定义typedef int Status;//函数状态类型typedef int ElemType;//元素类型typedef struct node{ElemType data;struct node *next;}Node,*LinkList;//节点类型、2.基本操作和所需调用的函数//初始化一个链表Status InitList(LinkList *L){*L=(LinkList)malloc(sizeof(node));if(!(*L)) exit(-2);//内存分配失败(*L)->next=NULL;return 1;}//在初始化的基础上按顺序创建一个链表Status CreatList(LinkList L,int n){LinkList p=L;int i;for(i=0;i<n;i++){(p->next)=(LinkList)malloc(sizeof(node));if (!(p->next)) exit(-2);//内存分配失败scanf("%d",&p->next->data);p=p->next;}p->next=NULL;return 1;}//依次输出单链表中的各个元素Status DisplayList(LinkList L){LinkList p;p=L->next;while(p){printf("%5d",p->data);p=p->next;}printf("\n");return 1;}//逆置1(递归方法)LinkList Ieverse(LinkList pre, LinkList cur) {LinkList head;if(!cur)return pre;head =Ieverse(cur, cur->next);cur->next = pre;return head;}//逆置2（就地逆置）Status Ieverse(LinkList L) {LinkList last = L->next;LinkList first ;while(last->next){first = L->next;L->next=last->next;last->next=L->next->next;L->next->next=first;}return 1;}3.主函数及功能的实现void main(){LinkList L;int L_Length;InitList(&L);//初始化链表printf("请输入单链表的长度：\n");scanf("%d",&L_Length);if(L_Length < 1) exit(-1);//长度不符合要求printf("请依次输入各个元素的值：\n");CreatList(L,L_Length);//按输入数据创建链表DisplayList(L);//显示原单链表//L->next=Ieverse(NULL,L->next);此语句可调用递归方法实现链表的逆置//Ieverse(L);//实现单链表的就地逆置printf("After reversing!\n");DisplayList(L);//显示逆置后的链表}四、调试分析本程序的基本框架比较简单，整个运行过程主要分为五个部分:主程序模块（接受链表的信息）->创建链表模块（初始化链表，即创建一个仅含头结点的空链表；按主程序模块接受的元素信息创建链表）->输出单链表模块（按一定格式输出原始链表） ->单链表逆置模块（可通过两种方式实现）->输出链表模块（按一定格式输出逆置后的链表）。