先序输出叶子结点
本题要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义：
void PreorderPrintLeaves( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
函数PreorderPrintLeaves应按照先序遍历的顺序输出给定二叉树BT的叶结点，格式为一个空格跟着一个字符。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef char ElementType; typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; }; BinTree CreatBinTree(); /* 实现细节忽略 */ void PreorderPrintLeaves( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("Leaf nodes are:"); PreorderPrintLeaves(BT); printf(" "); return 0; } /* 你的代码将被嵌在这里 */
输出样例：
Leaf nodes are: D E H I
void PreorderPrintLeaves( BinTree BT ) { if(BT) { if(BT->Left==MULL&&BT->Right==NULL) printf("%c ",BT->Data); else { if(BT->Left) { PreorderPrintLeaves(BT->Data); } if(BT->Right) { PreorderPrintLeaves(BT->Data); } } } }
void PreorderPrintLeaves( BinTree BT ) { if(BT) { if(!BT->Left&&!BT->Right) printf(" %c",BT->Data); PreorderPrintLeaves(BT->Left); PreorderPrintLeaves(BT->Right); } return; }
带头结点的单链表就地逆置
本题要求编写函数实现带头结点的单链线性表的就地逆置操作函数。
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 -2 typedef 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); else printf("%d",p->data); p=p->next; } } int main() { LinkList L; int n; scanf("%d",&n); if(ListCreate_L(L,n)!= OK) { printf("表创建失败！！！ "); return -1; } ListReverse_L(L); ListPrint_L(L); return 0; } /* 请在这里填写答案 */
输入格式：
第一行输入一个整数n，表示单链表中元素个数，接下来一行共n个整数，中间用空格隔开。
输出格式：
输出逆置后顺序表的各个元素，两个元素之间用空格隔开，最后一个元素后面没有空格。
输入样例：
4
1 2 3 4
输出样例：
4 3 2 1
注意两点，一个是题面中所说的”要求在不新开辟节点的前提下“，一个是要将L本身逆置，不是逆置入新链表
void ListReverse_L(LinkList &L)//L为头结点 { LinkList p,q; p = L->next; L->next = NULL; while(p) { //向后挪 q = p;// p = p->next; //头插 q->next = L->next;//非常重要，相当于p和q之间没有了指针连接 //q->next=NULL; L->next = q;//把q接到头的后面 } }
void ListReverse_L(LinkList &L)//L为头结点 { LinkList p,q; p = L->next; L->next = NULL; while(p) {
q=p; q->next=L->next; L->next=q; p=p->next; } }