《数据结构算法分析C描述》引论：选择问题，字谜游戏问题
2024-08-27 08:53:09
#include <stdio.h>
#include <stdlib.h>
// 第一题
// 找出N个数的第k个最大者
// 方法1：排序(冒泡)，降序找出第k个值
// 方法2：选前k个点进行降序排序，后面的数进行比较，
// 如果数比第k个数小则忽略, 复杂度低于方法1
#define TYPE int
#define TESTBUBLESORT 1
#define TESTBLOCKCOMPARE 1
#define TESTWORDPUZZLE 1
int findk_bublesort(TYPE *pData, int N, int k);
int findk_blockcompare(TYPE *pData, int N, int k); // 缺点修改了原数据
// 第二题
// wordpuzzle猜字谜游戏，在三个方向上找单词
// dirction = 0 水平方向 从左至右
// dirction = 1............右..左
// ...........2............上..下
// ...........3............下..上
// ...........4............正对角线->
// ...........5....................<-
// ...........6............负对角线<-
// ...........7....................->
// pData字谜
// pattern：欲猜的单词
int wordpuzzle(char *pData, char *pattern, int row, int col, int driction);
int my_strlen(char *s); // 获取字符串的长度
void my_strcat(char *s, char *t); // 连接字符串
void my_strcpy(char *s, char *t); // 复制字符串 // Test Model
int main()
{
printf("Hello world!\n"); int N = ;
int k = N / ;
TYPE *pTestData = (TYPE *)malloc(sizeof(TYPE) * N);
int i;
for (i = ; i < N; ++i)
pTestData[i] = i;
#ifdef TESTBUBLESORT
// printf("the k = %d in N is %d\n", k, findk_bublesort(pTestData, N, k));
#endif
#ifdef TESTBLOCKCOMPARE
printf("the k = %d in N is %d\n", k, findk_blockcompare(pTestData, N, k));
#endif
// for (i = 0; i < N; ++i)
// printf("%d ", pTestData[i]);
// printf("\n");
free(pTestData); #ifdef TESTWORDPUZZLE
int row = ;
int col = ;
char *WorldModle = (char *)malloc(sizeof(char) * row * col);
char *a1 = "this";
char *a2 = "wats";
char *a3 = "oahg";
char *a4 = "fght";
my_strcpy(WorldModle, a1);
my_strcat(WorldModle, a2);
my_strcat(WorldModle, a3);
my_strcat(WorldModle, a4);
char *pattern = "that";
int np = my_strlen(pattern); if (np > row || np > col)
{
fputs("the pattern size is bigger!", stderr);
return -;
}
for (i = ; i < ; ++i)
{
if (wordpuzzle(WorldModle, pattern, row, col, i))
{
printf("find word:[%s] at dirction [%d] of wordwidget\n", pattern, i);
break;
}
}
#endif
return ;
} void my_strcpy(char *s, char *t)
{
while (*s++ = *t++)
;
}
void my_strcat(char *s, char *t)
{
while(*s)
{
++s;
}
my_strcpy(s, t);
} int findk_bublesort(TYPE *pData, int N, int k)
{
// 对数据进行冒泡排序 降序
int i, j;
for (i = ; i < N; ++i)
{
for (j = i + ; j < N; ++j)
{
if (pData[i] < pData[j])
{
TYPE temp;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
}
}
return pData[k - ];
} int findk_blockcompare(TYPE *pData, int N, int k)
{
// 先读入前k个数进行降序排列，然后与后面的数比较
// 前k个数进行降序排列
int i, j, z;
for (i = ; i < k; ++i)
{
for (j = i + ; j < k; ++j)
{
if (pData[i] < pData[j])
{
TYPE temp;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
}
}
// 与后面的数与前k个数进行比较
for (i = k; i < N; ++i)
{
for (j = ; j < k; ++j)
{
if (pData[j] <= pData[i])
{
// 大于k个数中的一个 插入新元素
for (z = k - ; z >= j; --z)
pData[z + ] = pData[z]; // 右移元素
pData[j] = pData[i]; // 插入新元素
break;
}
}
}
return pData[k - ];
} int wordpuzzle(char *pData, char *pattern, int row, int col, int driction)
{
int result = ;
int i, j; int np; int k = ;
switch (driction)
{
case : // 从水平方向从左至右找
for (i = ; i < row; ++i)
{
for (j = ; j < col; ++j)
{
if (pData[i * col + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
k = ;
} break; case : // 从水平方向上从右至左找
for (i = ; i < row; ++i)
{
for (j = col - ; j >= ; --j, --np)
{
if (pData[i * col + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
k = ;
}
break; case : // 按列从上往下找
for (i = ; i < col; ++i)
{
for (j = ; j < row; ++j)
{
if (pData[j * row + i] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
k = ;
}
break; case : // 按列从下往上找
for (i = ; i < col; ++i)
{
for (j = row - ; j >= ; --j)
{
if (pData[j * row + i] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
k = ;
}
break; case : // 按正对角线从左到右
for (i = ; i < row; ++i)
{
for (j = ; j < col; ++j)
{
if (i == j)
{
if (pData[i * row + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
}
}
k = ;
break; case : // 按正对角线从右到左
for (i = row - ; i >= ; --i)
{
for (j = col - ; j >= ; --j)
{
if (i == j)
{
if (pData[i * row + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
}
}
k = ;
break; case : // 按负对角线从右到左
for (i = col - ; i >= ; --i)
{
for (j = ; j < row ; --j)
{
if (i + j == col - )
{
if (pData[i * row + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
}
}
k = ;
break; case : // 从负对角线从左到右
for (i = row - ; i >= ; --i)
{
for (j = ; j < col; ++j)
{
if (i + j == row - )
{
if (pData[i * row + j] == pattern[k])
{
k++;
}
if (pattern[k] == '\0')
result = ;
}
}
}
k = ;
break;
default:
break;
}
return result;
} int my_strlen(char *s)
{
int n = ;
while (*s++)
++n;
return n;
}
最新文章
- [LeetCode] Second Highest Salary 第二高薪水
- Javascript随记
- iOS启动页设置
- MCMC and Bayesian Data Analysis(PPT在文件模块)
- java获取Json和http状态码
- 大数据下的java client连接JDBC
- DOM-判断元素节点类型
- 找出图像I的代数中心
- 流式计算-Jstorm提交Topology过程(上)
- js 的四种设计模式的优缺点
- H5复制粘贴
- for语句输出图形
- android FragmentTabhost导航分页
- 学习 Spring (十一) 注解之 Spring 对 JSR 支持
- 步步为营-104-SQL语句(截取字符串)
- git使用，提交代码简记
- .NETCore_初探
- spring自动注解Autowired配置
- 【Mybatis】XML配置实现增删改查
- Android DatePickerDialog和TimePickerDialog显示样式
热门文章
- ifconfig命令无法找到，提示bash: ifconfig: command not found
- iis配置asp.net常见问题解决方案
- Android：Gradle sync failed: Another 'refresh project' task is currently running for the project
- 传递命令行参数示例代码 (C 和 Python)
- [翻译] UIImageView-Letters
- Windows平台使用Gitblit搭建Git服务器教程
- 多路I/O复用（select、poll、epoll）的比较学习：
- delete obj$
- 汉字转拼音工具类java
- jQuery实现简易轮播图的效果