Toby's Space

刚回家两天，还没歇停休息下，就开始马不停蹄的上车训练..........车开得越来越快，加速和飞车的感觉真的比较爽——后果是教练在旁边不停碎烦：慢一点慢一点，控制速度！。。。被教练骂了.....9号考车，还是夜考，黑不咙咚的估计可以混过去.................

 

考完车，拿到驾照，嘿嘿，那时候就开车到处玩!!!    kevin貌似对我新手开车出去心惊肉跳的........嘿嘿~~~

 

 

题目4 Hash表问题(有的书说的是 散列表，好像貌似可能就是同一个东西）；里面就改了个find的函数，其他就是代码重用，偷懒抄来的............

1． 问题描述：假设有一个100*100的稀疏矩阵，其中1%的元素为非零元素，现要求对其非零元素进行散列存储，使之能够按元素的行、列值存取元素（即元素的行、列值联合为元素的关键字），试采用除留余数法构造散列函数和线性探查法处理冲突，分别设计出建立散列表和查找散列表的算法。
2． 实现设计：
①由题意可知，整个稀疏矩阵中非零元素的个数为100个。为了散列存储这100个非零元素，需要使用一个称为散列表的一维数组，该数组中元素的类型为：
                 
 Struct DataType
                     {
                       int  row;  //存储非零元素行下标
                       int  col;   //存储非零元素列下标
                       float  val;  //存储非零元素值
                    }；
    ②假定用H[m]表示这个散列表，其中m为散列表的长度，若取装载因子为0.8左右，则令 M=127 为宜(127为质数)；
    ③按照题目要求，需根据稀疏矩阵非零元素的行下标和列下标存取散列表中的元素，所以每个元素的行下标和列下标共同组成元素的关键字。假定用x表示一个非零元素，按除留余数法构造散列函数，并考虑尽量让得到的散列地址均匀分布，可以采用如下的散列函数：
Hash(x)=(13*x.row+17*x.col) % m.

3. 附录：程序清单如下：

#include <iostream.h>
typedef char ElemType;
#include "HashTable.h"

void main(void)
{
 HashTable A(127);
 DataType *a=new DataType[];
 a[0].row=2;a[0].col=22;a[0].value='H';
 a[1].row=34;a[1].col=21;a[1].value='E';
 a[2].row=56;a[2].col=34;a[2].value='R';
 a[3].row=64;a[3].col=11;a[3].value='T';
 a[4].row=98;a[4].col=78;a[4].value='G';
 a[5].row=76;a[5].col=97;a[5].value='D';
 a[6].row=67;a[6].col=54;a[6].value='E';
 a[7].row= 4;a[7].col=87;a[7].value='A';
 a[8].row=2;a[8].col =22;a[8].value='e';

 DataType item;

 int n=9;
 for(int i=0;i<n;i++)A.Insert(a[i]);

 for(i=0;i<n;i++)
 {
  int j=A.Find(a[i]);
  if(j>0)
  {
   item=A.GetValue(j);
   cout<<"j="<<j<<" "<<"ht[]="<<item.value<<endl;
  }
 }

 DataType x;
 cout<<"请输入数据元素的row=";cin>>x.row;
 cout<<"请输入数据元素的col=";cin>>x.col;
 cout<<"请输入数据元素的value=";cin>>x.value;

 int k=A.IsIn(x);
 if(k==1)cout<<x.value<<"在哈希表中!"<<endl;
 else cout<<x.value<<"不在哈希表中!"<<endl;
}

执行测试程序，测试结果如下：
j=19 ht[]=H
j=37 ht[]=E
j=36 ht[]=R
j=3 ht[]=T
j=60 ht[]=G
j=97 ht[]=D
j=11 ht[]=E
j=7 ht[]=A
j=20 ht[]=e
请输入数据元素的row=4
请输入数据元素的col=87
请输入数据元素的value=A
A在哈希表中!

 

j=19 ht[]=H
j=37 ht[]=E
j=36 ht[]=R
j=3 ht[]=T
j=60 ht[]=G
j=97 ht[]=D
j=11 ht[]=E
j=7 ht[]=A
j=20 ht[]=e
请输入数据元素的row=4
请输入数据元素的col=65
请输入数据元素的value=J
J不在哈希表中!

 

 

 

哈希表头文件"HashTable.h"程序代码：
enum KindOfItem {Empty, Active, Deleted};
struct DataType      
{
 int row;       //行号
 int col;       //列号
 ElemType value;                     //元素值
};

struct HashItem
{
 DataType data;
 KindOfItem info;

 HashItem(KindOfItem i = Empty): info(i){}
 HashItem(const DataType &D, KindOfItem i = Empty): data(D), info(i){}
 int operator ==(HashItem &a)
  {return data.value == a.data.value;}
 int operator !=(HashItem &a)
  {return data.value != a.data.value;}
};

class HashTable
{
private:
 HashItem *ht;      //哈希表数组
 int TableSize;      //哈希表的长度（即m）
 int currentSize;     //当前的表项个数
public:
 HashTable(int m);     

 ~HashTable(void)     
  {delete []ht;}

 int Find(const DataType &x)const; 

 int Insert(const DataType &x);  
 int Delete(const DataType &x);  
 int IsIn(const DataType &x)   
  {int i = Find(x); return i >= 0 ? 1: 0;}
 DataType GetValue(int i)const  
  {return ht[i].data;}
};

//哈希表类实现
HashTable::HashTable(int m)    
{
 TableSize = m;      //置哈希表长度
 ht = new HashItem[TableSize];  //申请动态数组空间
 currentSize = 0;     //置初始的当前表项个数
}

int HashTable::Find(const DataType &x)const    
{
 int i=(13*x.row+17*x.col)%TableSize;
 int j = i;
 while(ht[j].info == Active && ht[j].data.value != x.value ) //说明存在冲突
 {
  j = (j + 1) % TableSize;  //用哈希冲突方法继续查找
  if(j == i) return -TableSize;//说明已遍历整个哈希表未找到且表已满
 }
 
 if(ht[j].info == Active)
  return j;       //找到，返回正值
 else
  return -j;       //未找到，返回负值

}

int HashTable::Insert(const DataType &x)
{
 int i = Find(x);       //调用Find(x)

 if(i > 0) return 0;      //数据元素x已经存在
 else if(i != -TableSize) //数据元素x不存在且哈希表未满
 {
  ht[-i].data = x;     //数据元素赋值
  ht[-i].info = Active;    //置活动标记
  currentSize++;      //当前表项个数加1
  return 1;       //返回插入成功状态
 }
 else return 0;       //返回插入失败状态
}

int HashTable::Delete(const DataType &x) //删除
{
 int i = Find(x);       //调用Find(x)

 if(i >= 0)
 {
  ht[i].info = Deleted;    //置删除标记
  currentSize--;      //当前表项个数减1
  return 1;       //返回删除成功状态
 }
 else return 0;       //返回删除失败状态
}

回来了回来了回来了..................

        热死了热死了热死了!!!!!!!!!!!!!!!!

 

 

 

作了一天一夜的火车(硬座);全身都是煤灰的回到家............弄好电脑上网,洗个澡,去百大买双鞋~~~~

半夜小猪说出去夜宵,真是力气没了..............

 

 

 题目：选址问题  图的应用
1. 问题描述：给定n个小区之间的交通图。若小区i与小区j之间有路可通，则将顶点i与顶点j之间用边连接，边上的权值 表示这条道路的长度。现在打算在这n个小区中选定一个小区建一所医院。试问这家医院应建在哪个小区，才能使距离医院最远的小区到医院的路程最短？请设计一个算法求解上述问题。
2. 实现设计：将n个小区的交通图视为一张带权无向图，并利用邻接矩阵来存放带权无向图。算法的思想是：
①应用Dijkstra算法（根据Dijkstra算法的思想，自己设计Dijkstra算法）计算每对顶点之间的最短路径；
②找出从每一个顶点到其它各顶点的最短路径中最长路径；
③在这n条最长路径中找出最短的一条，则它的出发点即为所求。
3．附录：测试小区交通图如下图： (试着贴了一下，贴不上去，大家自个儿yy吧)

下午又考完一门，反复看书看了一周，发现可以从一点不会到差不多都会......然后再看到想吐........还有三门轻松得多的..........现在学习，不太重要的课,平时偶尔去上上,考试前一周开始仔细研究书,看到吐了,考试还能考个马马虎虎......艾,这种学习态度,自己都惭愧....

 

昨天和老妈打电话，算算马上就要回家了，然后又是学车，到八月十二号路考；然后估计又玩不了不了几天，就要返校了........还没开始放假呢就开始发愁了~~~~~艾！

 

 

 

 

题目：背包问题------这个问题原来我还以为要把具体的解给求出来，结果发现自己没这个能力，只能满足老师的要求完成作业了......求解是否存在~~

1. 问题描述：设有一个背包可以放入的物品重量最重为s，现有n件物品，它们的重量分别为w[0]、 w[1]、w[2]、…、w[n-1]。问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s.如果存在一种符合上述要求的选择，则称此背包问题有解（或称其解为真）；否则称此背包问题无解（或称其解为假）。

 

 

#include<iostream.h>
#include<stdlib.h>

typedef int DataType;

class bag
{
private:
 int s;
 int n;
 int *w;
public:
  bag(int N,int S,int W[]){s=S;n=N;w=W;}
  ~bag(){}

 int KNAP(int s,int n)
{
 if(s==0)return 1;if (s<0||s>0&&n<1)return 0;
 if(KNAP(s,n-1)){;return 1;}
 return KNAP(s-w[n-1],n-1);
}
};

void main()
{
 int n;
 cout<<"请输入物件个数:";cin>>n;

 int *m=new int[n];
 cout<<"请输入各个物件重量:";
 for(int i=0;i<n;i++)cin>>m[i];
 int w;
 cout<<"请输入背包总容量:";cin>>w;

 bag A(w,n,m);

 int x=A.KNAP(w,n);
 if(x==1)cout<<"存在正好填满背包的组合!"<<endl;
 if(x==0)cout<<"不存在正好填满背包的组合!"<<endl;
 
}

执行测试程序，测试结果如下：
请输入物件个数:5
请输入各个物件重量:45 44 43 42 41
请输入背包总容量:171
存在正好填满背包的组合!

请输入物件个数:5
请输入各个物件重量:45 44 43 42 41
请输入背包总容量:161
不存在正好填满背包的组合!

都到放假的日子了，据说杭州已经回去了不少人！................ 荷包小猪，还有kevin都准备给我接风呢！ 可惜还有好几门考试，要道7月20才会到杭州..................后天就是门 运筹学,混得不容易啊

 

前几天终于把课程设计给搞定了............哗哗的打印了近50页,摸着还烫手的纸,hot of press,心理超级有成就感。。。。。虽然大部分模板代码都是抄来的（代码重用）,自己就设计了几个专门针对问题的函数和测试程序,但怎么说也为这些问题掉了不少头发,夜不能寐,辗转反侧了几个晚上............

 

看到bob的空间了,联个连接,发现上面的八卦信息不少,以后又有新地方去关心老同学的近况了~~~~~~~~

 

 

 

上次说要装B,贴代码出来,貌似一个半桶水的技术空间................

    下面是一道道题目的代码,哪个人家的模版我就不贴了,大家只要看清大概接口,套到这个函数里去看就是了。更新次贴一个问题...........其实这都是超级简单的小函数,太难得老头子也不好意思拿出来为难向我这样的什么都不精通的composer了

 

 

题目：求解约瑟夫（Josephus）问题
1. 问题描述：有一个旅行社要从n个旅客中选出一名旅客，为他提供免费的环球旅行服务。旅行社安排这些旅客围成一个圆圈，并从帽子中取出一张纸条，用纸条上面写的正整数m（m<n）作为报数值。游戏进行时，从第一个人开始按顺时针方向自1开始顺序报数，当报到m时停止报数，报m的人被淘汰出列。然后从他顺时针方向上的下一个人开始从1重新报数，当报到m时停止报数，报m的人被淘汰出列。如此下去，直到圆圈中剩下一个人为止。这个最后的幸存者就是游戏的胜利者，他将得到免费旅行的奖励。请编写程序，让计算机模拟此问题。

#include <iostream.h>
#include <stdlib.h>
#include "LinList.h"     //循环单链表

void main(void)
{
 LinList<int> myList;
    int s[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14}, n = 14;
 int temp=0;

    for(int i = 0; i < n; i++)  
  myList.Insert(s[i], i);

 int x; cout<<"请输入一个随机数:";cin>>x;

 josph(myList,x);
}

执行测试程序，测试结果如下：
请输入一个随机数:6
幸运者是第7号参与者

算法思想：josph()函数检验m值，取A.size的余赋给m；执行A.Delete(m-1)，然后建立一个结点指针，指向删除结点的下一个结点；此指针执行指向下一结点的循环m次，当遇到头指针时跳过头指针，删除第m个指针，继续循环，直到剩下最后一个元素时，跳出循环，返回结点的数据。

 

template<class T>
void josph(LinList<T> &A,int m)
{
 if(m>=A.size)m=m%A.size+1;
 ListNode<T> *p;
 A.Delete(m-1);
 p=A.Index(m-1);
 while(A.size>1)
 {
  ListNode<T> *s;
  for(int i=0;i<m-1;i++)
  {
   if(p->next==A.head)p=p->next;
  }
  s=p->next ;p->next =p->next ->next ;
  delete s;A.size --;
 }
 
 if(A.head ->next ->next =A.head)
cout<<"幸运者是第"<<A.head->next->data<<"号参与者"<<endl;
}

 

 

另附加一种算法及代码（未测试）：
思想：JOSPH()函数先检验m值，取A.size的余赋给m；执行A.Delete(m-1)，然后将头指针指向删除结点的下一个结点，递归调用JOSPH()；判断是否只剩下最后一个结点为递归出口，返回结点数据。

template <class T>
 void JOSPH(LinList<T> &A,int m)
{
  ListNode<T> *p;
  

  if(m>=A.size)m=m%A.size+1;
  A.Delete(m);
  p=A.Index(A.size-1);

  p->next=A.head->next;
  A.head->next=A.Index(m-1)->next;
  A.Index(m-1)->next=A.head;
  if(A.head->next->next==A.head){cout<<"lucker"<<A.head->next->data<<endl;return;}
  JOSPH(A,m);
}

ps: 这个问题其实有点儿奇怪,我就按要求解决问题,别的不多考虑(老板要怎么做就怎么做呗):这哪里是随机的,明明随机数的下一个就一定是选出来的人(自己画个圈去试试看)~~~~~这中选人法一点儿也不随机,艾。。。

做了两天的数据结构课程设计（就是对一些特定问题写程序代码）：解决问题的思想是明确的，语法错误是容易改正的，只是内在的逻辑错误到时让我想撞墙——编译完，程序运行时后内存不时地出错，系统不时地提示错误.....................怎一个郁闷了得

 

下午又修改了一个程序，只是多添加了个  “—>next” 终于测试成功。一步之遥阿！

 

大部分的程序到是主体都测试成功了，老头子要写份报告，代码还要修饰一番.....................

说实话自己写的丑是丑了点儿，也不容易让别人懂（不像标准程序似的那么规范），但是能用就行啦！

怎么说也要有点儿自己的风格。

 

过几天贴代码上来，装B..................hoho

 

 

 

 

 

前几天 乱七八糟考完六级，混混沌沌的到了期末——火车票订了，考试也临近了，要开始啃书了：倒是发现不少有趣的东西：学了数据结构中的一些算法，加上运筹学的理论，还有离散数学的图论，这三个反复交错起来，原来不知道有什么用的树啊图啊看起来还是有点花头的。。。。。。。。

 

开始接触一个内容超未来的游戏：EVE online ..................不要鄙视我浪费青春，我只不过花了点时间儿在 研究例如 太空地质学、空间航行工程学、引力子物理学、跳跃通道发生学、信号聚焦研究、诱导力场理论研究、频率调制理论、跳跃引擎操作理论 等等。各位有对science fiction 比较感兴趣的也可以去试试！

世界杯开始一个多星期了，偶尔的看看...........没有什么好嗟叹的——自己也不是很热心这个! 无奈的是躺在床上听着楼里大呼小叫................

ps: 小朱，荷包说你下月回来！在德国带点纪念品来~~~~~~我会笑纳的！ 

恭亲王奕訢的府邸在柳阴街，前身是和珅的宅子......一路走过去的时候，还看到郭沫若故居：不过据说是王府的马厩；缴了门票钱，就随着人流，亦步亦趋的进去了。

此次参观的是王府的后花园（前面的都没开放），除了后门是个西洋门，花园假山、楼台水榭还是中国传统的建筑风格，布局也蛮精致的，作为后花园，的确和故宫的御花园有得一拼（主要是御花园太小，要是算上颐和园，那就比不来了）。进门是“一柱擎天”（一根石柱，好像有什么字在上面，真正叫什么忘了）；然后有个样子像蝙蝠的水池+两个榆钱树~~~~~~艾，都是那时候谐音之类的图个吉利。里面有个爱新觉罗家族的书画展~~~~不得不承认，个个字都写得不错！自惭形秽阿.......不过好像怎么都是抄唐诗三百首来着~~~~读着读着不免开心起来，这些个跟俺都挺熟！嘿嘿

别的没什么了，倒是假山的山洞里面有个康熙写得“福寿”字~~~~据说被和珅从皇室那儿偷偷搬来的，郁闷了后来的几代清帝王；走进假山，人人都在上面摸阿摸的（隔着个玻璃），手指轻轻点了下，算是沾上了点儿前朝帝王的福气！艾~~~叹口气，王侯将相，宁有种乎？

出了恭王府，吃了个“掉渣饼”来到了----雍和宫：藏传佛教的一个寺庙，以前是雍正出道前的府邸。以前倒是没怎么接触藏传佛教，还以为是和平时的佛教完全不同的另外一种宗教——喇嘛教！现在才知道，都是原是印度佛教的分支罢了：汉传/藏传佛教。宏伟的宫殿，袅袅的香烟，不过都弄得神秘兮兮的~~~~看了一个展厅里的一些挂着的古籍，仔细研究下，据本人猜测，n副小图配上特定的文字好像是藏人的识字挂图——估计宗教在西藏也有执行教育的功能（就像欧洲的要读书都要当个僧侣神父似的）：各种牲畜都有特有的字表示，让人感到好笑的是在禽兽配字的中间，嘿嘿嘿，还有个人拉屎图都有个文字呢！！！（有人证，不信的自己去看，门票自出）

不同于汉传佛教，藏传佛教还能阴阳双修（不知道他们叫什么，反正是可以由性行为哦），N个佛像都有ML的场面，脚下还踏着一些人身：正在诧异怎么这些个佛啊，菩萨啊，这么没有素质，众生平等的时候还践踏人权，灭绝人性阿——忽然听到旁边个mm说，这些被践踏着的人身代表着人性的种种罪恶，而不是指真实的人，便恍然大悟呵。。。。。

最让人吃惊的是，在灵隐寺里肥肥胖胖可爱的弥勒佛，结果在藏传佛教里倒是非常的苗条：看来汉族和藏族都在自己的理解上对佛教进行了改造。。。。。不说了不说了，佛教太博大精深了，自个儿去钻研罢！

 

 

花了半天的时间去了圆明园，虽然人不少，但地方够大，稍微偏僻一点儿就没啥人了。从南门进了倚春园，纷飞的柳絮（应该是的） 除了让人呼吸不畅外，用来营造浪漫的气氛还行。当天的天气也不错，说实话是这几天里面最适合出行的。接着是长春园，不过估计是管理的以遗址的名义什么都没修下，路按照鲁迅的话说都是“人走出来的”。情不自禁的想象一下，若早个一百多年，那这儿的风景是蛮迷人的，有个帝王的念经房什么都没剩下只有地基和柱子蹲，还附带着失去生机而显得突兀的假山，的确可惜了些。。。不过批评下现在管园子的，怎么说也把湖里的水给清清，别的可以说是遗迹不去修，但不要把厚厚的淤泥+绿油油的水也说成是那时候的洋鬼子一把火烧得吧。。。。

 

绕了福海，没力气去划船，只能瞟瞟湖中漂着的一条条五彩船........艾，顺便鄙夷下：北京人真没见识，丫的什么小小的一水塘，竟然都敢称海——福海，北海，后海，前海，中南海。。。。。迁身份证的不要扔板砖啊~~~~~~~~~~

 

最后到了受过九年义务教育的都不能不知道，被洋毛子一把火烧了只剩下几根柱子的“西洋楼”。追求时尚的皇室估计把这东西当作新鲜的玩具来玩的，估计他们还没等像吸收汉文化一样花个一两百年来了解欧洲文明，新鲜的把玩儿就给变成了像雅典卫城似的废墟。。。艾，不好意思地我还在上面道貌岸然的拍照以记录“TOBY到此一游”，惭愧归惭愧，游玩的好心情可不想因此而变得阴暗起来，都这样了100多年了，自己愤青有个屁用。。。。。

 

原来以为还有一半真正的“圆明园”要逛，结果发现不开放；为自己花的门票钱可惜的同时还暗自窃喜：终于不用再继续走了。。。。。yy下要是能潇洒的策马而行，在偌大的园子里停停走走，够NB；在其还是布衣一个，梦里做作皇帝梦好了，真的要是这样子，还是讨厌如此的负担，诚心说自己没什么强烈的使命感，责任感——估计主要是因为“能力越小，责任越小”。

 

PS：出来吃了北大西门的烤翅；然后打算从西门进北门出坐公交。。。。走了半圈巨郁闷！北大有东门南门西门，就是没有北门！！！拖着11路原路返回+鄙视下：你怎么说都占了一个街区，怎么不开个北门方便下！愤恨之下拍了两张北大龌龊的照片——取名：校园一角~~~~嘿嘿嘿

 

第二天去了颐和园，景点太多，几步路就是一个什么什么的，建筑风格么就是传统的飞檐雕栏+藏传佛教的几座塔倒是正在修的最雄伟最明显的XXX（名字不知道）有几分神似布达拉宫；上去的排云楼不错，不过好多都要单独收门票，到人家地头上没办法，也只得买了！也不多说，大家看看照片YY下就好啦。。。皇帝估计这辈子都轮不到咱们咯。。。。。。。（不要看我说得轻巧，我可爬上爬下跑前跑后——迷路的时候还重复走了一条路三遍，才好不容易的收集了些景观，看过的捧个场！）

 

下面两张就是北大校园一角，货真价实的呵~~~~