当前位置: 代码迷 >> 综合 >> PTA 6-1 带头结点的单链表就地逆置
  详细解决方案

PTA 6-1 带头结点的单链表就地逆置

热度:60   发布时间:2024-01-18 18:25:44.0
6-1 带头结点的单链表就地逆置(10 分)

本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。L是一个带头结点的单链表,函数ListReverse_L(LinkList &L)要求在不新开辟节点的前提下将单链表中的元素进行逆置,如原单链表元素依次为1,2,3,4,则逆置后为4,3,2,1。

函数接口定义:

void ListReverse_L(LinkList &L);

其中 L 是一个带头结点的单链表。

裁判测试程序样例:

//库函数头文件包含
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>//函数状态码定义
#define TRUE        1
#define FALSE       0
#define OK          1
#define ERROR       0
#define INFEASIBLE -1
#define OVERFLOW   -2typedef int  Status;
typedef int  ElemType; //假设线性表中的元素均为整型typedef struct LNode
{ElemType data;struct LNode *next;
}LNode,*LinkList;Status ListCreate_L(LinkList &L,int n)
{LNode *rearPtr,*curPtr;   //一个尾指针,一个指向新节点的指针L=(LNode*)malloc(sizeof (LNode));if(!L)exit(OVERFLOW);L->next=NULL;               //先建立一个带头结点的单链表rearPtr=L;  //初始时头结点为尾节点,rearPtr指向尾巴节点for (int i=1;i<=n;i++){  //每次循环都开辟一个新节点,并把新节点拼到尾节点后curPtr=(LNode*)malloc(sizeof(LNode));//生成新结点if(!curPtr)exit(OVERFLOW);scanf("%d",&curPtr->data);//输入元素值curPtr->next=NULL;  //最后一个节点的next赋空rearPtr->next=curPtr;rearPtr=curPtr;}return OK;
}
void ListReverse_L(LinkList &L);
void ListPrint_L(LinkList &L){
//输出单链表LNode *p=L->next;  //p指向第一个元素结点while(p!=NULL){if(p->next!=NULL)printf("%d ",p->data);elseprintf("%d",p->data);p=p->next;}
}
int main()
{LinkList L;int n;scanf("%d",&n);if(ListCreate_L(L,n)!= OK) {printf("表创建失败!!!\n");return -1;}ListReverse_L(L);ListPrint_L(L);return 0;
}
/* 请在这里填写答案 */

输入格式:

第一行输入一个整数n,表示单链表中元素个数,接下来一行共n个整数,中间用空格隔开。

输出格式:

输出逆置后顺序表的各个元素,两个元素之间用空格隔开,最后一个元素后面没有空格。

输入样例:

4
1 2 3 4

输出样例:

4 3 2 1
void ListReverse_L(LinkList &L)
{LNode *p=L->next,*q;L->next=NULL;while(p!=NULL){q=p->next;p->next=L->next;L->next=p;p=q;}
}
/*思路:①将原来的头结点拆下来,作为新的逆置链表的头结点②将原来链表的各个节点,依次拆卸下来,然后按照头插法,插入到逆置链表当中③循环,直到原来的链表为空即可。*/




  相关解决方案