博文
我所理解的链表02(2005-12-07 08:46:00)
摘要：/----------线性表的单链表基本操作的算法实现------------
//我给链表设置了一个头结点,虽然它的数据域毫无意义,但它作为一个指针却意义非凡!
//它的作用我们在下面的例程中可以领教
LinkList InitList(void) //构造一个空的线性表
{
LNode Head;
Head = (LNode)malloc(sizeof(struct Node)); //为链表的头结点分配空间
if(!Head)
{
printf("Out of space!");
return NULL;
}
Head->next = NULL;
return Head;//返回头结点
}
void DestroyList(LinkList *L)//初始条件：线性表L已存在。 操作结果：销毁线性表L。
{
LNode Head, P;
if(*L)//若线性表L已存在
{
Head = *L;
P = Head->next;
while(!P) //把链表中除头结点外的所有结点释放
......
我所理解的链表 01(2005-12-07 08:43:00)
摘要：我所理解的链表
虽然使用数组可以很方便的查找每一个元素，但如果要插入或删除元素时，因为要移动大量的元素，所以需要一定的运行时间，而且代码也变的复杂。为了能够方便的删除和插入元素，我们一般不采用顺序存取结构，而采用链表存取。根据链表中结点的性质，我把它分为两种，一种是使用指针来指向它的后继（为简单起见，我暂时只讲一下单向链表，至于双向链表和循环链表，大家可以在单向链表的基础上做一定扩展即可），每一个结点的空间由系统动态分配，我们称之为动态链表；另一种是用游标（相当于指针）来指向它的后继，每一个结点的空间由程序建立的“模拟空间分配站”来分配，这个“模拟空间分配站”实际上是一个事先给定足够空间的结构数组，它为链表的结点分配空间，链表上释放的结点空间再返回给“模拟空间分配，
站”，由于这个“模拟空间分配站”的空间是由系统事先静态分配好空间的，所以称这种链表为静态链表。静态链表满足了那些不支持指针的高级语言（如BASIC和FORTRAN）需要链表的要求，它的使用方法和动态链表极为相似。
首先我们来了解动态链表。它的类型声明和基本操作如下表所示：
//-----------线性表的单链表存储结构-------------
typedef struct Node{
ElemType data;
struct Node *next;
} *LNode, *LinkList;
//----------线性表的单链表基本操作------------
LinkList InitList(void); //构造一个空的线性表
void DestroyList(LinkList *L);//初始条件：线性表L已存在。 操作结果：销毁线性表L。
LinkList MakeEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：将线性表L重置为空表。
int IsEmpty(LinkList L);//初始条件：线性表L已存在。 操作结果：判断线性表是否为空表。
int ListLength(LinkList L);//初始条件：线性表L已存在。 操作结果：返回线性表L结点的个数。
......
一个实用的小程序－－魔术师翻牌(2005-12-05 17:29:00)
摘要：/*魔术师翻牌，魔术师将扑克中的13张黑桃预先排好，牌面朝下，放在手中，
第一次数一张牌翻过来刚刚好是A，放在桌面上;第二次数MAX>1张牌，把记数分别为1，2，。。。，
(MAX-1)的那些牌，依次 放在手中牌的下面，数MAX的牌，翻过来刚刚好是2，放在桌面上；
第三次也数MAX>1张牌，把记数分别为1，2，。。。，(MAX-1)的那些牌，依次 放在手中牌的下面，
数MAX的牌，翻过来刚刚好是3，放在桌面上；这样做下去，直到13张牌翻完为止，
此时桌面上的牌顺序刚刚好是A，2，3，4，5，6，7，8，9，10，J，Q，K。
请编程找出魔术师手中的13张牌的原始顺序... */
#include <stdio.h>
#include <stdlib.h>
#define MAX 2
void Solve(int *Puke, int len); //此函数用来找出魔术师手中的13张牌的原始顺序
void show(int Puke[], int len); //此函数用来演示魔术师的翻牌顺序
int main(void)
{
int side, Puke[13]={0}, *P_Puke=Puke;//用来存储13张牌
Solve(P_Puke, 13);//此函数用来找出魔术师手中的13张牌的原始顺序
printf("原始顺序 : ");
for(side=0; side<13; side++)//输出13张牌的原始顺序
printf("%d ",Puke[side]);
printf("\n翻牌顺序 : ");
show(Puke, 13);//此函数用来演示魔术师的翻牌顺序
system("pause");
return 0;
}
void Solve(int *Puke, int len)//此函数用来找出魔术师手中的13张牌的原始顺序
{
int cou......
菜鸟在成长------我的参赛心得(2005-12-04 19:51:00)
摘要：菜鸟在成长
------我的参赛心得
今天中午12点，“编程爱好者论坛第六次编程比赛”正式落下帷幕，冠军得主是 iAkiak。又是iAkiak，是正是这个iAkiak，在第三次编程比赛中，他和LO几又VE不相上下，后来因为LO几又VE离开了论坛，他也就理所当然的成为了第三次编程比赛的冠军。他的编程风格特异，有时令人难以理解，但是他的算法非常漂亮，效率极高，令我等菜鸟叹为观止。这次他能拿到冠军，也是理所当然的。但我现在想说的，并不是评论iAkiak的程序有多么的好，本人水平有限，判断不出代码优劣，也就不敢妄加评论高手们的代码了。但是我连续参加了三届编程比赛，而且收获颇丰，就把自己这几次参加比赛的心路历程总结一下－－有点自作多情，大家不要拿板砖砸我啊！
作为一名编程爱好者，虽然明知自己水平很低，是个“臭棋篓子”，但处于对编程的热爱，对挑战自我的冲动，我还是义无返顾的参加了比赛，把自己算法质朴，效率低下的代码贴了上去。这些代码在高手眼离也许是一堆垃圾，但在我看来，却是一群宝贝，因为它们都是我一个字一个字抠出来的，虽说不上废寝忘食，日以继夜，苦思冥想，但也是花了一番心血的。
前三届比赛我没有参加，是因为那时侯对比赛还不了解，那段时间也没怎么上论坛，没注意到有比赛。但后来看了这几次比赛的帖子，发现参赛者热情都很高，也体现了一定的水平，就有点后悔，并兴冲冲地参加了第四届比赛。第四次比赛是iAkiak 出的题目，看起来是很简单的一个数学问题，我很快的就想到解题思路了，程序出来在自己的机子上运行也通过了，但就是过不了poj那一关。当时百思不得其解，现在想起来真好笑啊，以前对程序的时间和空间复杂度根本不在乎，也搞不懂——现在仍然不太清楚，呵呵。但是不服气归不服气，答案还是“勇敢”地交上去了。当时的“主持人” iAkiak 很仔细地分析了我的答案，并在比赛总结中对所有人的代码做了中肯的评析，让我受益匪浅，在这里我想一说声：谢谢你，iAkiak ，是你让我进一步认识到了自己的不足，并有了学习的目标。
有了第四届比赛的经历，看到自己的帖子和高手们的帖子排在一起，我的兴趣更大了，以更高的热情参加了第五次编程比赛。这次比赛的题目是由第四届的冠军nopeak出的，是一道关于考试排名的题目，实用性很强，数据结构有些复杂-----对......
排序算法小结 (2005-11-28 15:42:00)
摘要：
此为转帖:
排序算法小结
排序小结
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法对算法本身的速度要求很高。
而一般我们所谓的算法的性能主要是指算法的复杂度，一般用O方法来表示。在后面我将给出详细的说明。
对于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。
我将按照算法的复杂度，从简单到难来分析算法。
第一部分是简单排序算法，后面你将看到他们的共同点是算法复杂度为O(N*N)（因为没有使用word,所以无法打出上标和下标）。
第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为涉及树与堆的概念，所以这里不于讨论。
第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可以让我们从另外的角度来认识这个问题。
第四部分是我送给大家的一个餐后的甜点——一个基于模板的通用快速排序。由于是模板函数可以对任何数据类型排序（抱歉，里面使用了一些论坛专家的呢称）。
现在，让我们开始吧：
一、简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
1.冒泡法：
这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：
#include
void BubbleSort(int* pData,int Count)
{
&nbs......
用数组解决约瑟夫环的几个算法(2005-11-15 10:59:00)
摘要：算法1:
/*求围圈问题的详细算法和程序*/
/*17人围成一圈，编号为1，2，3，……，17，从1开始报数，报到3的倍数的人离开，
一直下去，直到最后剩下1人，求此人的编号 */
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int a[17]={0};
int i, count, s;
for (i = 0;i < 17;i++)
{
a[i] = i + 1; /* 填空数组，编号是下标加一，注意C语言中的数组下标从0开始 */
}
i=0;
s=17; //用来记录退出圈外的人的数目
count=0; //计数器
while(s > 1)
{
for(i=0; i<17; i++)
if(a[i] != 0)
{
count++; //报一次数
if(count == 3) //每报到一次3，该人退出
{
printf("%d\n",a[i]);&nbs......
"S、P先生数学谜题"算法分析及源代码(3)(2005-11-13 13:55:00)
摘要：附录2：
根据算法（二）写出的程序代码：
/* S、P先生数学谜题*/
/*梁见斌 2005-11-14*/
#include <stdio.h>
#include <stdlib.h>
#define M 2
#define N 99
//初步列出所有可能的p的值（M*M〈= p〈= N*N），并把每一个p的xy组合的个数作为p[i]的值
void possible1_p(int *p);
//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合 ，即设该元素值为s[x+y] = 1;
void possible_us(int *s, int p[]);
//根据s的不可能的值的集合，推出s的可能的值的集合
int possible2_s(int *s);
//根据p的不可能的值的集合，推出p的可能的值的集合
int possible2_p(int *p);
//根据P的话判断出p[]的可能的值的集合
int possible3_p(int *p, int s[], int len_p, int len_s);
//根据S的话判断出s[]的可能的值的集合
int possible3_s(int *s, int p[], int len_s, int len_p);
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(int p[], int s[], int len_s, int len_p, int *px, int *py);
//输出最后的结果
void print(int x[], int y[], int len);
int main( void )
{
int len_s=0, len_p=0, len_xy;
int s[N+N+1]={0}, p[N*N+1]={0}, *ps, *pp;
&n......
"S、P先生数学谜题"算法分析及源代码(2)(2005-11-13 13:54:00)
摘要：附录1：
根据算法（一）写出的程序代码：
/* S、P先生数学谜题*/
/*梁见斌 2005-11-14*/
#include <stdio.h>
#include <stdlib.h>
#define M 2
#define N 200
typedef struct{ //存放两个数之和或积的集合
int x;
int y;
int data;
} SP1;
int possible_up(SP1 *up); // 寻找p的不可能的值的集合
//根据p的不可能的值的集合 进一步确定 s的不可能的值的集合
int put_us(SP1 *us, SP1 up[], int len_us, int len_up);
int out_s(SP1 us[], SP1 *s, int len);//根据s的不可能的值的集合，推出s的可能的值的集合
int out_p(SP1 up[], SP1 *p, int len); //根据p的不可能的值的集合，推出p的可能的值的集合
int judge1(SP1 *p, SP1 s[], int len_p, int len_s);//根据P的话判断出P的可能的值的集合
int judge_s(int x, int y, SP1 s[], int len);//判断P分解的两个数之和是否属于集合S
int judge2(SP1 *s, SP1 p[], int len_s, int len_p);//根据S的话判断出S的可能的值的集合
int judge_p(int x, int y, SP1 p[], int len); //判断S分解的两个数之积是否属于集合P
//根据P和S的可能的值的集合，判断出X，Y的可能的值的集合
int possible_xy(SP1 p[], SP1 s[], int len_s, int len_p, int *px, int *py);
void print(int x[], int y[], int len);//输出最后的......
"S、P先生数学谜题"算法分析及源代码(2005-11-13 13:53:00)
摘要：S、P先生数学谜题：
设有两个自然数X、Y，2<=X<=Y<=99,S先生知道这两个数的和S，P先生知道这两个数的积 P ，他们二人进行了如下对话：
S：我确信你不知道这两个数是什么，但我也不知道。
P: 一听你说这句话，我就知道这两个数是什么了。
S: 我也是，现在我也知道了。
现在你能通过他们的会话推断出这两个数是什么吗？（当然，S和P先生都是非常聪明的）
S、P先生数学谜题的思路：
首先已声明2<=x<=y<=99，且x，y都是自然数。
1、S先生说：“我不知道这两个数。”，这就可知S决不是：
4(=2+2)；5(=2+3)；197(=98+99)；198(=99+99)。
把这些S的不可能的值及其对应的X，Y的组合存储到数组US[]中。
2、S先生说：“我确定你也不知道这两个数。”，这就可知P决不是：
（1） 两端的数之积，如4(=2*2)；6(=2*3)；8=(2*4)；10(=2*5)；。。。
9801（=99*99）；9702（=98*99）；9604（=98*98）。
（2） 素数或者素数之积，如5，7，11，。。。25（=5*5），35（=5*7）。
把这些P的不可能的值及其对应的X，Y的组合存储到数组UP[]中。
UP共有2981个元素，它们是：
UP={4 5 6 7。。。4316 4327 4331 。。。9781 9787 9791 9801}
那么可以根据这些X，Y的组合求出对应的S（=X+Y）来，把它们加入到数组US[]中。这样一来，S的数又可以排除一些了。
比如6(=2+4)；7(=2+5)；...10(=5+5);...。
如此一来，就可以初步总结出S可能的数的集合：
......
迷宫的算法(2005-04-24 22:17:00)
摘要：深度搜索：
/*迷宫的算法*/
/* 先建立迷宫（外围建筑围墙），设置入口和出口。建立链表，把第一个点（入口）入舰，同时做好
标记，以免重复入舰。a：判断舰顶元素的东面是否可通，若可通则将其入舰 ，同时做好标记，
以免重复入舰；若不通则判断舰顶元素的南面是否可通，依此操作至北面元素。
判断新的舰顶元素是否为出口 ，若是，则报告结束，并打印出路径；否则递归操作a：。
若舰顶元素其余三面皆不通 ，则将舰顶元素其重新设定为不通，以免以后再走弯路。然后退舰。
重复a；操作。
若退回到入口，则表示迷宫走不通，报告不通。*/
/*2005-4-22 梁见斌*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define NO 0
#define OVERFLOW 1
#define M 5
#define N 5
typedef struct poi{/*建立链表结构，存储每个路径点的有关数据；横坐标，纵坐标，所指方向和向下的指针*/
int x;
int y;
char *p;
struct poi *next;
} Point;
Point *head;
char a[100][200];
char FX[14]={'E','S','W','N','E','S','W', 'E','N','W','S','E','N','W',};/*存储方向*/
int MG_S[M+2][N+2], MG[M+2][N+2], In[2],......