文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

上个学期C语言程序实践课的作业题，发出来给有需要的人参考吧。代码是纯C写的，已加注释。下面是作业要求:

* 设计一个学生成绩管理系统（学号、姓名、总分、物理、化学、计算机、英语、数学、体育）
* 采用单链表的方式设计
* 使用菜单方式进行操作，并具有操作出错提示
* 可以对记录进行增加、显示、保存到文件、读取文件、删除、查询等操作

具体的菜单如下：

" 0. init list", /*初始化*/
" 1. Enter list",/*输入记录*/
" 2. Delete a record from list",  /*从表中删除记录，可以依照学号或姓名进行查找删除。如果删除后没有保存到文件，直接退出系统时，需要提醒保存文件*/
" 3. print list ", /*显示所有记录到屏幕*/
" 4. Search record on name",/*按照姓名查找记录*/
" 5. Save the file", /*将单链表中记录保存到文件中*/
" 6. Load the file",  /*从文件中读入记录*/
" 7. compute the score", /*计算所有学生的总分和均分*/
" 8. insert record to list ",/*插入记录到表中，插入记录后，直接退出时，需要提醒保存文件*/
" 9. copy the file to new file",/*复制文件到新的文件中*/
" 10. sort to make new file",/*排序,将学生按照分数（总分）由高到低排名*/
" 11. append  record to file",/*追加记录到文件中，追加记录后，直接退出时，需要提醒保存文件*/
" 12. index on number", /*索引，按照学号进行排序*/
" 13. total on number",/*分类合计，依据不同学科进行分类统计（平均分）和排名*/
" 14. Quit" /*退出系统*/

只完成这些要求不复杂，我大概花了2个小时，但是考虑下面一些细节的话，就要耗费一番功夫了...

1.命令的操作顺序需要正确。例如所有的操作前必须初始化，按总分排序前必须计算总分等。
2.输入的学号和姓名必须检查合法性，这里限定学号为纯数字串，
姓名为纯大小写字母串，且长度有限。
3.输入信息时要判断是否存在学号相同的学生。
4.因为存在按姓名查找功能，则假定按姓名删除时姓名唯一，否则应按学号查找删除。
因此按姓名查找应能打印多个姓名相同的情况，而按姓名删除不需要删除多个姓名相同的学生信息。
5.复制文件时应排除源文件名与目标文件名相同的情况，否则会得到空白文件。
6.追加记录到文件时，链表中始终不应出现追加的信息，文件中在未保存前也不应出现追加的信息。
追加的信息应位于文件末尾。
7.菜单应能处理用户输入的错误命令，例如输入大数字、字符、字符串等。
8.退出时应释放链表。

下面给出完整的代码，比较长，建议拷贝下来放到IDE里面看...

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

09-12-05网络赛的一道题，概率公式的推导及化简。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

09-12-05网络赛的一道题，用到了异或运算的几个性质。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

实验课内容的代码，无聊发出来。

功能包括从文件中读取文章，将文章转换为哈夫曼编码，将哈夫曼编码还原，就是那几个基本算法的实现啦。

为了方便查看，这里输出的哈夫曼编码是1byte的，其实真正应该将其变为1bit存储，这样才能达到压缩的目的。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

刚才用O(n^2)的DP算法做了最长上升子序列，具体见POJ2533解题报告。后来在网上看到说LIS问题有O(nlogn)的算法，于是拿来小研究了一下。

这个算法其实已经不是DP了，有点像贪心。至于复杂度降低其实是因为这个算法里面用到了二分搜索。本来有N个数要处理是O(n)，每次计算要查找N次还是O(n)，一共就是O(n^2)；现在搜索换成了O(logn)的二分搜索，总的复杂度就变为O(nlogn)了。

这个算法的具体操作如下(by RyanWang):

开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。

这也是很好理解的，对于x和y，如果x < y且Stack[y] < Stack[x],用Stack[x]替换Stack[y]，此时的最长序列长度没有改变但序列Q的''潜力''增大了。

举例：原序列为1，5，8，3，6，7

栈为1，5，8，此时读到3，用3替换5，得到1，3，8； 再读6，用6替换8，得到1，3，6；再读7，得到最终栈为1，3，6，7。最长递增子序列为长度4。

用该算法完成POJ2533的具体代码如下:

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

24点游戏是一种使用扑克牌来进行的益智类游戏，游戏内容是：从一副扑克牌中抽去大小王剩下52张，任意抽取4张牌，把牌面上的数(A代表1)运用加、减、乘、除和括号等进行运算得出24。每张牌都必须使用一次，但不能重复使用。

简单说就是给你4个数(1-13)，数字可以重复，然后让你运用加、减、乘、除和括号运算得出24，每个数字必须使用一次，但不能重复使用。当然，运算中出现的分数是允许的，如1 5 5 5和3 3 8 8这两组数字得到的24点表达式为((5-(1/5))*5) 和 (8/(3-(8/3)))，是不是很变态？

因为表达式是字符串，所以这次我没有用C语言实现，而是选择了具有string类型的C++语言，这样可以更好地处理字符串。在代码中我还使用了STL的Vector来过滤掉重复的解，感叹STL的方便之余对迭代器的使用也有了更深的认识。

至于24点求解的算法，仔细研究一下24点解集，可以发现解的形式无非就是2种。一种是(((A,B),C),D)，另一种是((A,B),(C,D))。有了这个发现，就可以在很大程度上避免对于括号的处理，接下来的工作就是...枚举，哈哈。

花了3个多小时敲代码，注释我写得很清晰了，测试了很多组数据，目前没有发现bug，下面是代码。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

今天翻手机里的游戏时，找到了以前经常玩的九宫格，也就是数独。拼出一个20个已知数字的数独后，我又想写代码解数独了...

思路比较清晰，依旧是DFS，感觉应该不难写。花了2个小时搞定代码，用手机里的数独游戏测试了几次，全部通过...

意外发现PKU 2676就是数独求解，用我写的代码交了2次全是TLE...看了Discuss以后得知要AC必须从后面开始搜...囧，数据问题，数据问题...

恩，代码的注释我写的异常清楚，就不再写废话了。

阅读全文...

文章作者：Slyar 文章来源：Slyar Home (www.slyar.com) 转载请注明，谢谢合作。

周四的外教课，我们那个澳大利亚籍外教给了一个小朋友玩的游戏 -- Crossword Puzzles。规则就是先给你一个由字母组成的矩阵，里面隐藏了很多单词，之后再给你一排单词，让你把这些单词在矩阵里画出来...

11 11
r e h t o r b b r y g
y r e h t o m e a r z
l e l n n o h t a w r
i t c b i t z n w e g
m s n y a s d a u n t
a i u f n p u w e f e
f s w n a m t o r o w
u i c r t p r l c x p
t g e n d c e b s x u
u n c l r m z f e m a
t w q r v t o h c y t

9
aunt
brother
cousin
family
father
grandparent
mother
sister
uncle

恩，大概就是这么个意思。不过我最近比较烦啊，哪里有心情去一个一个找，还不说这些单词可以正向，可以反向，可以斜着...大爷没空

烦躁的时候就想写代码，顺手就把这个小游戏敲完了，懒得写printf和scanf，就用C++的cin和cout，不过没有什么高深算法，就是一个简单的深搜，上面的那堆就是测试数据，效果自己编译运行看去...

我发这个代码纯属凑文章数...

阅读全文...