匿名网友
第一题：
/****************************************************************************
* @file 01_最大二叉树差的绝对.c
* @brief 写一个函数，输入一个二叉树，树中每个节点存放了一个整数值，函数
返回这棵二叉树中相差最大的两个节点间的差值绝对值。
* @version V1.00
* @date 2014.8.29
* @note
****************************************************************************/
#include “stdio.h”
#include “malloc.h”
/** 节点数据类型
*
* 定义节点数据类型。
*/
typedef char ElementType;
/** 树节点结构体定义
*
* 定义树节点所包含的成员变量。
*/
typedef struct treenode
{
int data; /**< 节点数据 */
struct treenode* leftchild; /**< 左孩子节点指针 */
struct treenode* rightchild; /**< 右孩子节点指针 */ } TreeNode, *TreeNode_ptr; /** * @brief 使用先序遍历创建二叉树。 * @param None * @retval TreeNode* 创建的树节点。 * @see TreeNode; * @note scanf函数的问题：scanf会读入回车符，当需要一个一个的输入字符时， 可以在%c前面加个空格 */ TreeNode* Create_Binarytree() { ElementType ch; TreeNode* T; scanf(“%c”,&ch); //这样调用scanf时，树的结点一次全部输入，如果要一次一个的输入，在%c前加个空格 if(ch != ‘#’) { if(NULL == (T = (TreeNode*)malloc(sizeof(TreeNode)))) { perror(“error…”); exit(1); } T->data = ch;
T->leftchild = Create_Binarytree();
T->rightchild = Create_Binarytree();
}
else
{
T = NULL;
}
return T;
}
/**
* @brief 返回这棵二叉树中相差最大的两个节点间的差值绝对值。
* @param head 当前节点的指针
* @param max 当前最大节点值
* @param min 当前最小节点值
* @retval None
* @see TreeNode;
* @note 递归调用。
*/
void MaxLength(TreeNode_ptr head, int *max, int *min)
{
if(NULL == head)
{
//到达叶子节点，直接返回
return;
}
if(head->data > *max)
{
*max = head->data;
}
else if(head->data < *min) { *min = head->data;
}
MaxLength(head->leftchild, max, min);
MaxLength(head->rightchild, max, min);
}
int main()
{
TreeNode_ptr head_ptr = Create_Binarytree();
ElementType max = head_ptr->data, min = head_ptr->data;
MaxLength(head_ptr, &max, &min);
printf(“%d”,max-min);
}
第二题：求text在query中的最长子串
/****************************************************************************
* @file 02_求text在query中的最长子串.c
* @brief 给定一个query和一个text，均由小写字母组成。要求在text中找出以同
样的顺序连续出现在query中的最长连续字母序列的长度。例如， query为“acbac”，text为“acaccbabb”，那么text中的“cba”为最长的连续
出现在query中的字母序列，因此，返回结果应该为其长度3。
* @version V1.00
* @date 2014.8.29
* @note
****************************************************************************/
#include
#define MAXNUM 200
/**
* @brief 求text和query两个字符串的最长公共子串。
* @param query query的首指针
* @param query_len query的长度
* @param text text的首指针
* @param text_len text的长度
* @retval 错误码 0：成功 -1：输入参数有误 -2：申请空间失败。
* @see None;
* @note
*/
int MaxCommonSubString(char* query, int query_len, char* text, int text_len)
{
if(NULL == query || NULL == text || 0 == query_len || 0 == text_len)
{
printf(“输入参数有误\r\n”);
return -1;
}
int *p, max = 0, postion = 0;
int i,j;
if(NULL == (p = (int*)malloc(sizeof(int)*(text_len + 1))))
{
printf(“申请空间失败!\r\n”);
return -2;
}
memset(p, 0, sizeof(int)*(text_len + 1));
for(i = 0; i < query_len; i++) { for(j = text_len – 1; j >= 0; j–)
{
//从后向前遍历query，若从前向后遍历，需要额外的一个数组存放数组p上一次的值
if(text[j] == query[i])
{
p[j+1] = p[j] + 1;
if(p[j+1] > max)
{
max = p[j+1]; //替换当前最大子串长度
postion = j – max + 1;//子串初始位置
}
}
else
{
p[j+1] = 0;
}
}
}
//申请并复制最长公共子串到substring
char *substring;
if(NULL == (substring = (char*)malloc(sizeof(char)*(max + 1))))
{
printf(“申请空间失败!\r\n”);
return -1;
}
memcpy(substring, text + postion, max);
substring[max] = ‘\0’;
printf(“最长公共子串为：%s，长度：%d\r\n”, substring, max);
free(p);
free(substring);
return 0;
}
int main()
{
char *query = (char*)malloc(sizeof(char)*MAXNUM);
char *text = (char*)malloc(sizeof(char)*MAXNUM);
printf(“请输入query：”);
gets(query);
printf(“请输入text：”);
gets(text);
int i = 0, j = 0;
while(query[i] != ‘\0’){i++;};
while(text[j] != ‘\0’){j++;};
MaxCommonSubString(query, i, text, j);
free(query);
free(text);
}
