6-6 删除单链表偶数节点
本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中偶数值的结点删除。链表结点定义如下：
struct ListNode { int data; struct ListNode *next; };
函数接口定义：
struct ListNode *createlist(); struct ListNode *deleteeven( struct ListNode *head );
函数createlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到−1时表示输入结束，函数应返回指向单链表头结点的指针。
函数deleteeven将单链表head中偶数值的结点删除，返回结果链表的头指针。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> struct ListNode { int data; struct ListNode *next; }; struct ListNode *createlist(); struct ListNode *deleteeven( struct ListNode *head ); void printlist( struct ListNode *head ) { struct ListNode *p = head; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } int main() { struct ListNode *head; head = createlist(); head = deleteeven(head); printlist(head); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
1 2 2 3 4 5 6 7 -1
输出样例：
1 3 5 7
解析
struct ListNode *createlist() { int m; struct ListNode *p, *s, *l; p = (struct ListNode *) malloc(sizeof(struct ListNode)); scanf("%d", &m); if (m == -1) return NULL; p->data = m; p->next = NULL; s = p; while (1) { scanf("%d", &m); if (m == -1) break; l = (struct ListNode *) malloc(sizeof(struct ListNode)); l->data = m; l->next = NULL; s->next = l; s = l; } return p; } struct ListNode *deleteeven(struct ListNode *head) { struct ListNode *p = NULL, *s = NULL; while (head && head->data % 2 == 0) { p = head; head = head->next; free(p); } if (head == NULL) return NULL; s = head; while (s->next) { if (s->next->data % 2 == 0) s->next = s->next->next; else s = s->next; } return head; }
6-7 逆序数据建立链表
本题要求实现一个函数，按输入数据的逆序建立一个链表。
函数接口定义：
struct ListNode *createlist();
函数createlist利用scanf从输入中获取一系列正整数，当读到−1时表示输入结束。按输入数据的逆序建立一个链表，并返回链表头指针。链表节点结构定义如下：
struct ListNode { int data; struct ListNode *next; };
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> struct ListNode { int data; struct ListNode *next; }; struct ListNode *createlist(); int main() { struct ListNode *p, *head = NULL; head = createlist(); for ( p = head; p != NULL; p = p->next ) printf("%d ", p->data); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
1 2 3 4 5 6 7 -1
输出样例：
7 6 5 4 3 2 1
解析：
struct ListNode *createlist() { int m; struct ListNode *head, *p; head = (struct ListNode *) malloc(sizeof(struct ListNode)); head->next = NULL; while (1) { scanf("%d", &m); if (m == -1) break; p = (struct ListNode *) malloc(sizeof(struct ListNode)); p->next = head->next; p->data = m; head->next = p; } return head->next; }
6-8 求链表的倒数第m个元素
请设计时间和空间上都尽可能高效的算法，在不改变链表的前提下，求链式存储的线性表的倒数第m（>0）个元素。
函数接口定义：
ElementType Find( List L, int m );
其中List结构定义如下：
typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */
L是给定的带头结点的单链表；函数Find要将L的倒数第m个元素返回，并不改变原链表。如果这样的元素不存在，则返回一个错误标志ERROR。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> #define ERROR -1 typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表 */ ElementType Find( List L, int m ); int main() { List L; int m; L = Read(); scanf("%d", &m); printf("%d\n", Find(L,m)); Print(L); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
5 1 2 4 5 6 3
输出样例：
4 1 2 4 5 6
解析
ElementType Find(List L, int m) { int i; PtrToNode p, s; p = s = L; for (i = 0; i < m; i++) { p = p->Next; if (!p) return ERROR; } while (p) { s = s->Next; p = p->Next; } return s->Data; }
6-9 两个有序链表序列的合并
本题要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。
函数接口定义：
List Merge( List L1, List L2 );
其中List结构定义如下：
typedef struct Node *PtrToNode; struct Node { ElementType Data; /* 存储结点数据 */ PtrToNode Next; /* 指向下一个结点的指针 */ }; typedef PtrToNode List; /* 定义单链表类型 */
L1和L2是给定的带头结点的单链表，其结点存储的数据是递增有序的；函数Merge要将L1和L2合并为一个非递减的整数序列。应直接使用原序列中的结点，返回归并后的带头结点的链表头指针。
裁判测试程序样例：
#include <stdio.h> #include <stdlib.h> typedef int ElementType; typedef struct Node *PtrToNode; struct Node { ElementType Data; PtrToNode Next; }; typedef PtrToNode List; List Read(); /* 细节在此不表 */ void Print( List L ); /* 细节在此不表；空链表将输出NULL */ List Merge( List L1, List L2 ); int main() { List L1, L2, L; L1 = Read(); L2 = Read(); L = Merge(L1, L2); Print(L); Print(L1); Print(L2); return 0; } /* 你的代码将被嵌在这里 */
输入样例：
3 1 3 5 5 2 4 6 8 10
输出样例：
1 2 3 4 5 6 8 10 NULL NULL
解析
List Merge( List L1, List L2 ) { List pa,pb,pc; pa=L1->Next; pb=L2->Next; List L=(List)malloc(sizeof(List)); pc=L; while(pa&&pb) { if(pa->Data>pb->Data) { pc->Next=pb; pb=pb->Next; } else{ pc->Next=pa; pa=pa->Next; } pc=pc->Next; } if(pa) pc->Next = pa; if(pb) pc->Next = pb; L1->Next=NULL; L2->Next=NULL; return L; }
6-10 二叉树的遍历
本题要求给定二叉树的4种遍历。
函数接口定义：
void InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); void LevelorderTraversal( BinTree BT );
其中BinTree结构定义如下：
typedef struct TNode *Position; typedef Position BinTree; struct TNode{ ElementType Data; BinTree Left; BinTree Right; };
要求4个函数分别按照访问顺序打印出结点的内容，格式为一个空格跟着一个字符。
裁判测试程序样例：
#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 InorderTraversal( BinTree BT ); void PreorderTraversal( BinTree BT ); void PostorderTraversal( BinTree BT ); void LevelorderTraversal( BinTree BT ); int main() { BinTree BT = CreatBinTree(); printf("Inorder:"); InorderTraversal(BT); printf("\n"); printf("Preorder:"); PreorderTraversal(BT); printf("\n"); printf("Postorder:"); PostorderTraversal(BT); printf("\n"); printf("Levelorder:"); LevelorderTraversal(BT); printf("\n"); return 0; } /* 你的代码将被嵌在这里 */
输出样例（对于图中给出的树）：
Inorder: D B E F A G H C I Preorder: A B D F E C G H I Postorder: D E F B H G I C A Levelorder: A B C D F G I E H
解析
void InorderTraversal(BinTree BT) {//中序遍历 if (BT) { InorderTraversal(BT->Left); printf(" %c", BT->Data); InorderTraversal(BT->Right); } } void PreorderTraversal(BinTree BT) {//先序遍历 if (BT) { printf(" %c", BT->Data); PreorderTraversal(BT->Left); PreorderTraversal(BT->Right); } } void PostorderTraversal(BinTree BT) {//后序遍历 if (BT) { PostorderTraversal(BT->Left); PostorderTraversal(BT->Right); printf(" %c", BT->Data); } } void LevelorderTraversal(BinTree BT) { BinTree B[100];//结构体数组 BinTree T; int i = 0, j = 0; if (!BT)return;//树为空，返回 if (BT)//不为空 { B[i++] = BT;//根节点入队 while (i != j)//队列不空 { T = B[j++];//出队 printf(" %c", T->Data); if (T->Left) B[i++] = T->Left; if (T->Right) B[i++] = T->Right; } } }
