C语言编程练习day19
题目：将线性表L的所有元素逆置方法1：通过链表逆置。输入：5 4 3 2 1输出：1 2 3 4 5优化目标：无创建LinkList.h文件，声明相关API/**将线性表list的所有元素逆置*方法1：链表实现*HuangLiang*2022/03/18*/#ifndef LINKLIST_H#define LINKLIST_H#include <stdio.h>#include &l
·
题目：将线性表L的所有元素逆置
方法1：通过链表逆置。
输入：5 4 3 2 1
输出：1 2 3 4 5
优化目标：无
创建LinkList.h文件，声明相关API
/*
*将线性表list的所有元素逆置
*方法1：链表实现
*HuangLiang
*2022/03/18
*/
#ifndef LINKLIST_H
#define LINKLIST_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//链表结点结构体
typedef struct LINKNODE{
struct LINKNODE* next;
}LinkNode;
//打印的函数，打印结点
typedef void(*PRINTNODE)(LinkNode*);
//链表结构体
typedef struct LINKLIST{
LinkNode head;
int size;
}LinkList;
//初始化链表
LinkList* Init_LinkList();
//插入结点
void Insert_LinkList(LinkList* list, int pos, LinkNode* data);
//逆置链表
void Reverse_LinkList(LinkList* list);
//打印结点
void Print_LinkList(LinkList* list, PRINTNODE print);
//返回链表容量
int Size_LinkList(LinkList* list);
//释放链表
void FreeSpace_LinkList(LinkList* list);
#endif
创建LinkList.c文件，定义相关API
/*
*将线性表list的所有元素逆置
*方法1：链表实现
*HuangLiang
*2022/03/18
*/
#include "LinkList.h"
//初始化链表
LinkList* Init_LinkList(){
//给链表分配内存
LinkList* list = (LinkList*)malloc(sizeof(LinkList));
list->head.next = NULL;
list->size = 0;
return list;
}
/*
*插入结点
*@list:链表指针
*@pos:插入的位置
*@data:插入的结点
*/
void Insert_LinkList(LinkList* list, int pos, LinkNode* data){
//判断参数的合法性
if(list == NULL || data == NULL){
return;
}
//插入位置不合理,默认插入链尾
if(pos < 0 || pos > list->size){
pos = list->size;
}
//辅助指针，找到插入位置
LinkNode* pCurrent = &(list->head);
for(int i=0; i<pos; i++){
pCurrent = pCurrent->next;
}
//插入结点
data->next = pCurrent->next;
pCurrent->next = data;
list->size++;
}
/*
*逆置链表
*@list:链表指针
*/
void Reverse_LinkList(LinkList* list){
//判断参数的合法性
if(list == NULL){
return;
}
//一直指向头节点
LinkNode* pre = &(list->head);
//移动的辅助指针p,q。初始时p指向第一个数据结点
LinkNode* p = list->head.next;
LinkNode* q ;
pre->next = NULL;
//采用头插法进行逆置
while(p != NULL){
//q指向p的下一个结点
q = p->next;
//将p后面的断开
p->next = NULL;
//头插
p->next = pre->next;
pre->next = p;
//p往后移，q中保留了p的下一个结点
p = q;
}
}
/*
*打印函数
*@list:链表指针
*@print:用户 传入的打印函数
*/
void Print_LinkList(LinkList* list, PRINTNODE print){
//判断参数的合法性
if(list == NULL){
return;
}
//辅助指针,指向第一个数据结点
LinkNode* pCurrent = list->head.next;
while(pCurrent != NULL){
print(pCurrent);
pCurrent = pCurrent->next;
}
}
/*
*返回链表容量
*@list:链表指针
*/
int Size_LinkList(LinkList* list){
//判断参数的合法性
if(list == NULL){
return -1;
}
return list->size;
}
/*
*释放链表
*@list:链表指针
*/
void FreeSpace_LinkList(LinkList* list){
//判断参数的合法性
if(list == NULL){
return;
}
free(list);
}
创建main.c文件，测试功能
/*
*将线性表list的所有元素逆置
*方法1：链表实现
*HuangLiang
*2022/03/18
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "LinkList.h"
//自定义数据
typedef struct MYDATA{
LinkNode node;
int val;
}MyData;
//打印函数
void MyPrint(LinkNode* node){
MyData* data = (MyData*) node;
printf("%d ", data->val);
}
int main(){
//初始化链表
LinkList* list = Init_LinkList();
//初始化数据
MyData d1 = {NULL, 1};
MyData d2 = {NULL, 2};
MyData d3 = {NULL, 3};
MyData d4 = {NULL, 4};
MyData d5 = {NULL, 5};
//插入数据,采用头插法
Insert_LinkList(list, 0, (LinkNode*)&d1);
Insert_LinkList(list, 0, (LinkNode*)&d2);
Insert_LinkList(list, 0, (LinkNode*)&d3);
Insert_LinkList(list, 0, (LinkNode*)&d4);
Insert_LinkList(list, 0, (LinkNode*)&d5);
//逆置前，打印结点
Print_LinkList(list, MyPrint);
//逆置后，打印结点
printf("\n");
printf("---------Afte reverse------------\n");
//逆置线性表
Reverse_LinkList(list);
//逆置后，打印结点
Print_LinkList(list, MyPrint);
//释放雷车
FreeSpace_LinkList(list);
return 0;
}
注意事项：这里记录一种我自己写的"逆置方法“。因为刚开始的时候没有想用课本上的方法。
思路：每一次把最后一个结点放到上一次移动结点的后面，第一次则放到头节点后面。需注意的是，当尾结点移动到前面去时，我们又需要找到新的尾结点(也就是移动前尾结点的前一个结点)，并且新的尾结点的next指针还指向移动了的那一个结点，这里需要断开，不然会成为一个环。
思路图：
LinkList.c里面的Reverse_LinkList()函数的另一种写法
/*
*逆置链表
*@list:链表指针
*/
void Reverse_LinkList(LinkList* list){
//判断参数的合法性
if(list == NULL){
return;
}
//定义辅助指针
LinkNode* pCurrent = &(list->head);//指向链尾结点
LinkNode* pNext = &(list->head);//指向头节点
LinkNode* pRear;//用来找到新的链尾结点
for(int i=0; i<list->size; i++){
pCurrent = pCurrent->next;
}
while(pNext->next != pCurrent){
pRear = &(list->head);
//将链尾结点移动到前面的合适位置
pCurrent->next = pNext->next;
pNext->next = pCurrent;
//找到新的链尾，赋给pCurrent,并且next置为空
for(int i=0; i<list->size; i++){
pRear = pRear->next;
}
pCurrent = pRear;
pCurrent->next = NULL;
//pNext后移，pNext->next就是新的链尾要移动的新的位置
pNext = pNext->next;
}
}
方法2：通过顺序表逆置
输入：0 1 2 3 4 5 6 7 8 9
输出：9 8 7 6 5 4 3 2 1 0
优化目标：无
创建SeqTable.h文件，声明相关API
#ifndef SEQTABLE_H
#define SEQTABLE_H
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#define MAX_SIZE 64
typedef struct SQEARRAY{
int size;//元素的个数
int* pAddr;//存放数据的首地址
}SqeArray;
//初始化
SqeArray* Init_SeqArray();
//数据插入
void Insert_SeqArray(SqeArray* arr, int data);
//逆置
void Reverse_SeqArray(SqeArray* arr);
//打印
void Print_SeqArray(SqeArray* arr);
//释放内存
void FreeSpace_SeqArray(SqeArray* arr);
#endif
创建SeqTable.c文件，定义相关API
#include "SeqTable.h"
//初始化
SqeArray* Init_SeqArray(){
SqeArray* arr = (SqeArray*)malloc(sizeof(SqeArray));
arr->size = 0;
arr->pAddr = (int*)malloc(sizeof(int)*MAX_SIZE);
return arr;
}
/*
*数据插入
*@arr:数组指针
*@data:待插入数据
*/
void Insert_SeqArray(SqeArray* arr, int data){
//判断参数的合法性
if(arr == NULL){
return;
}
//插入数据
arr->pAddr[arr->size] = data;
arr->size++;
}
/*
*逆置
*@arr:数组指针
*/
void Reverse_SeqArray(SqeArray* arr){
//判断参数的合法性
if(arr == NULL){
return;
}
//逆置
for(int i=0; i<arr->size/2; i++){
int temp = arr->pAddr[arr->size - i - 1];
arr->pAddr[arr->size - i -1] = arr->pAddr[i];
arr->pAddr[i] = temp;
}
}
/*
*打印
*@arr:数组指针
*/
void Print_SeqArray(SqeArray* arr){
//判断参数的合法性
if(arr == NULL){
return;
}
for(int i=0; i<arr->size; i++){
printf("%d ", arr->pAddr[i]);
}
}
//
/*
*释放内存
*@arr:数组指针
*/
void FreeSpace_SeqArray(SqeArray* arr){
//判断参数的合法性
if(arr == NULL){
return;
}
if(arr->pAddr != NULL){
free(arr->pAddr);
}
free(arr);
}
创建main.c文件，测试功能
#include <stdio.h>
#include <stdlib.h>
#include "SeqTable.h"
int main() {
//初始化
SqeArray* array = Init_SeqArray();
//插入元素
for (int i = 0; i < 10; i++) {
Insert_SeqArray(array, i);
}
//打印,逆置前
Print_SeqArray(array);
//逆置
Reverse_SeqArray(array);
//打印,逆置后
printf("\n");
Print_SeqArray(array);
//释放内存
FreeSpace_SeqArray(array);
return 0;
}
总结：今天用线性表的链式存储和顺序存储对一个线性表进行了逆置。其中链表的逆置想了一种自己的方法，写的时候也是出现了不少问题，但通过调试代码，都一一解决了。数据结构的大部分内容都学写完了，后面就是复写以及对一些题的应用了。
CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！
更多推荐
0
0- 0
已为社区贡献2条内容
所有评论(0)