链队列

浏览次数: 八月 31st, 2010 / No Comments » / by 小黑

额,今天的是链队列~

命令行运行输出效果如下:

  1. 将10入队
  2. 将20入队
  3.  
  4. 打印此队列:
  5. 10->20->NULL
  6.  
  7. 将30入队
  8.  
  9. 打印此队列:
  10. 10->20->30->NULL
  11.  
  12. 弹出10
  13. 弹出20
  14.  
  15. 打印此队列:
  16. 30->NULL
  17.  
  18. 弹出30
  19.  
  20. 打印此队列:
  21. NULL
  22.  
  23. 将40入队
  24.  
  25. 打印此队列:
  26. 40->NULL

下面是源码

  1. /**
  2. * 链队列
  3. */
  4. typedef int Elemtype;
  5.  
  6. /**
  7. * 队列节点
  8. */
  9. typedef struct LQNode
  10. {
  11.     Elemtype data;
  12.     struct LQNode *next;
  13. }LQNode,*LinkedQNode;
  14.  
  15. /**
  16. * 队列头和尾节点
  17. */
  18. typedef struct
  19. {
  20.     LinkedQNode front,rear;
  21. }LQueue,*LinkedQueue;
  22.  
  23.  
  24. /**
  25. * 链队初始化
  26. */
  27. LinkedQueue LinkedQueueInit(void){
  28.     LinkedQueue Q;
  29.     LinkedQNode n;
  30.     Q = (LinkedQueue) malloc(sizeof(LQueue));
  31.     n = (LinkedQNode) malloc(sizeof(LQNode));
  32.     n->next = NULL;
  33.     Q->front = Q->rear = n;
  34.     return Q;
  35. }
  36.  
  37.  
  38. /**
  39. * 打印整个队列
  40. */
  41. void LinkedQueueDump(LinkedQueue q)
  42. {
  43.     printf("\n打印此队列:\n");
  44.     LinkedQNode tmp;
  45.     tmp = q->front->next;
  46.     while (tmp!=NULL){
  47.         printf("%d->",tmp->data);
  48.         tmp = tmp->next;
  49.     }
  50.     printf("NULL\n\n");
  51.     return;
  52. }
  53.  
  54. /**
  55. * 入队
  56. */
  57. void LinkedQueueIn(LinkedQueue q,Elemtype data){
  58.     LinkedQNode tmp = (LinkedQNode) malloc(sizeof(LQNode));
  59.     tmp->data = data;
  60.     tmp->next = NULL;
  61.     q->rear->next = tmp;//原来的尾节点指向新节点
  62.     q->rear = tmp;//指针指向刚加的节点
  63.     printf("将%d入队\n",data);
  64. }
  65.  
  66. /**
  67. * 出队
  68. */
  69. Elemtype LinkedQueueOut(LinkedQueue q){
  70.     //判断队列不为空
  71.  
  72.     if(q->front==q->rear){
  73.         err("队列为空了!");
  74.     }
  75.     Elemtype x;
  76.     LinkedQNode tmp = q->front->next;
  77.     q->front->next = tmp->next;
  78.     x = tmp->data;
  79.     free(tmp);
  80.     if(q->front->next==NULL){//因为入队的时候,rear增加,所以最后一个出队的时候,头指针指向NULL,需要把尾指针和头指针指向同一地址
  81.         q->rear = q->front;
  82.     }
  83.     printf("弹出%d\n",x);
  84.     return x;
  85. }
  86.  
  87.  
  88.  
  89. int main(int argc, char **argv) {
  90.     LinkedQueue q = LinkedQueueInit();
  91.     LinkedQueueIn(q,10);
  92.     LinkedQueueIn(q,20);
  93.     LinkedQueueDump(q);
  94.     LinkedQueueIn(q,30);
  95.     LinkedQueueDump(q);
  96.     LinkedQueueOut(q);
  97.     LinkedQueueOut(q);
  98.     LinkedQueueDump(q);
  99.     LinkedQueueOut(q);
  100.     LinkedQueueDump(q);
  101.     LinkedQueueIn(q,40);
  102.     LinkedQueueDump(q);
  103.     return 0;
  104. }

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 算法研究

队列

浏览次数: 八月 30th, 2010 / No Comments » / by 小黑

此次是队列~ FIFO~

  1. /**
  2. * 队列
  3. */
  4.  
  5. #define MAXSIZE 100
  6. #define MODCAL(x) x%100
  7.  
  8.  
  9. typedef struct {
  10.     int data[MAXSIZE];
  11.     int front,rear;
  12. } SeqQueue;
  13.  
  14.  
  15. SeqQueue SeqQueueInit(void){
  16.     SeqQueue Q;
  17.     Q.rear=Q.front=0;
  18.     return Q;
  19. }
  20.  
  21. int SeqQueueFull(SeqQueue *p){
  22.     if(MODCAL(p->rear+1)==p->front) return 1;
  23.     else return 0;
  24. }
  25.  
  26. int SeqQueueEmpty(SeqQueue *p){
  27.     if(p->rear==p->front) return 1;
  28.     else return 0;
  29. }
  30.  
  31. int SeqQueueOut(SeqQueue *p){
  32.     if(SeqQueueEmpty( p )){
  33.         err("队列空了!");
  34.     }
  35.     int x;
  36.     p->front = MODCAL(p->front+1);
  37.     x = p->data[p->front];
  38.     printf("%d 出队了\n",x);
  39.     return x;
  40. }
  41.  
  42. void SeqQueueIn(SeqQueue *q,int data){
  43.     if(SeqQueueFull(q)){
  44.         err("队列满了!");
  45.     }
  46.     q->rear=MODCAL(q->rear+1);
  47.     q->data[q->rear] = data;
  48. }
  49.  
  50.  
  51. void dump(SeqQueue *p){
  52.     printf("当前队列情况:");
  53.     int tmp = p->rear;
  54.     while(p->front!=tmp){
  55.         printf("<-%d",p->data[tmp]);
  56.         tmp=(tmp-1)%MAXSIZE;
  57.     }
  58.     printf("\n");
  59. }
  60.  
  61.  
  62. int main(int argc, char **argv) {
  63.     SeqQueue q = SeqQueueInit();
  64.     dump(&q);
  65.     SeqQueueIn(&q,10);
  66.     SeqQueueIn(&q,20);
  67.     dump(&q);
  68.     SeqQueueOut(&q);
  69.     dump(&q);
  70.     return 0;
  71. }

运行后输出以下信息

  1. 当前队列情况:
  2. 当前队列情况:<-20<-10
  3. 10 出队了
  4. 当前队列情况:<-20

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 算法研究

汉诺塔(栈,递归)

浏览次数: 八月 26th, 2010 / 1 Comment » / by 小黑

汉诺塔问题~ 想了想,根据算法书籍完成
使用栈以及递归完成

是使用数组作为栈的数据区还是使用链作为栈的数据区,我认为这个是根据数据的变动频率作为参考依据,如果变动很频繁或有移动的操作,我认为应该考虑使用链,因为链的节点移动对数据产生的波动比较小,以下盘子在x,y,z柱子之间移动511次全部都是指针的计算,效率还不错~ 当然要自己释放和管理内存了~

  1. /**
  2. * 汉诺塔程序
  3. */
  4. #define LINKNODEINIT() (LinkNode) malloc(sizeof(Node));
  5. #define PANZI 9 //盘子数量
  6.  
  7. typedef struct Node{
  8.     int data;
  9.     struct Node *next;
  10. }Node, *LinkNode;
  11.  
  12. int step = 0;
  13.  
  14. /**
  15. * 初始化节点
  16. */
  17. LinkNode linkedStackInit(void){
  18.     LinkNode l=LINKNODEINIT();
  19.     if(l==NULL) err("malloc error!");
  20.     l->next = NULL;
  21.     return l;
  22. }
  23.  
  24. /**
  25. * 插入节点
  26. */
  27. void linkedStackInsert(LinkNode s,int data){
  28.     LinkNode l = LINKNODEINIT();
  29.     if(l==NULL) err("malloc error!");
  30.     l->next = s->next;
  31.     l->data = data;
  32.     s->next = l;
  33. }
  34.  
  35. /**
  36. * 把节点打印出来
  37. */
  38. void dump(LinkNode s){
  39.     if(s->next!=NULL){
  40.         s=s->next;
  41.         while(s!=NULL){
  42.             printf("%d\n",s->data);
  43.             s=s->next;
  44.         }
  45.     }
  46. }
  47.  
  48. /**
  49. * 把s柱的盘子移动到t柱上
  50. */
  51. void hanoiMove(LinkNode s,LinkNode t){
  52.     //判断s柱是否为空
  53.     if(s->next==NULL) err("被移动的柱子没有盘子!");
  54.     else{
  55.         LinkNode tmpS,tmpT,tmpSS;
  56.  
  57.         tmpSS = s->next->next;
  58.         tmpS = s->next;
  59.         tmpT = t->next;
  60.  
  61.         t->next = tmpS;
  62.         tmpS->next = tmpT;
  63.         s->next = tmpSS;
  64.         step++;
  65.     }
  66. }
  67.  
  68. /**
  69. * 核心算法:
  70. * 其实就是两个盘子在不停的移动,每次取两个盘子(大小),就有如下规则,先移动小盘,让其以y柱作为辅助,从x柱移动到z柱,然后移动大盘,从x柱移动到z柱子,再把小盘以x柱为辅助,从y柱移动到z柱上,这样小盘就在大盘上面了~
  71. *
  72. * 实现是使用链栈,然后移动节点完成
  73. *
  74. */
  75. void hanoi(int n,LinkNode x,LinkNode y,LinkNode z){
  76.     if(n==1){
  77.         hanoiMove(x,z);
  78.     }else{
  79.         hanoi(n-1,x,z,y);
  80.         hanoiMove(x,z);
  81.         hanoi(n-1,y,x,z);
  82.     }
  83. }
  84.  
  85. int main(int argc, char **argv) {
  86.     //初始化汉诺塔
  87.     LinkNode x = linkedStackInit();
  88.     LinkNode y = linkedStackInit();
  89.     LinkNode z = linkedStackInit();
  90.     int i;
  91.     for(i=PANZI;i>0;i--){
  92.         linkedStackInsert(x,i);
  93.     }
  94.     printf("x的盘子:\n");
  95.     dump(x);
  96.  
  97.     hanoi(PANZI,x,y,z);
  98.     printf("\n移动了%d次后\n\n",step);
  99.  
  100.     printf("x的盘子:\n");
  101.     dump(x);
  102.     printf("z的盘子:\n");
  103.     dump(z);
  104.  
  105.     return 0;
  106. }

运行后结果如下:

  1. x的盘子:
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6
  8. 7
  9. 8
  10. 9
  11.  
  12. 移动了511次后
  13.  
  14. x的盘子:
  15. z的盘子:
  16. 1
  17. 2
  18. 3
  19. 4
  20. 5
  21. 6
  22. 7
  23. 8
  24. 9

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 算法研究

链栈

浏览次数: 八月 25th, 2010 / No Comments » / by 小黑

链栈其实就是单链表使用头插法~ 呵呵~

记得四则运算法则不?原来可以通过栈来完成的~

下面代码:

  1. typedef struct Node{
  2.     int data;
  3.     struct Node *next;
  4. }Node, *LinkNode;
  5.  
  6. #define LINKNODEINIT() (LinkNode) malloc(sizeof(Node));
  7.  
  8. LinkNode init(void){
  9.     LinkNode l=LINKNODEINIT();
  10.     if(l==NULL) err("malloc error!");
  11.     l->next = NULL;
  12.     return l;
  13. }
  14.  
  15. void insert(LinkNode s,int data){
  16.  
  17.     LinkNode l = LINKNODEINIT();
  18.     if(l==NULL) err("malloc error!");
  19.     l->next = s->next;
  20.     l->data = data;
  21.     s->next = l;
  22. }
  23.  
  24. int top(LinkNode s){
  25.     if(s->next == NULL){
  26.         return 0;
  27.     }else{
  28.         return s->next->data;
  29.     }
  30. }
  31.  
  32.  
  33. int cal(int x,int y,int op){
  34.     switch(op){
  35.     case '+':return (x+y);
  36.     case '-':return (x-y);
  37.     case '*':return (x*y);
  38.     case '/':return (x/y);
  39.     default:return 0;
  40.     }
  41. }
  42.  
  43. int pop(LinkNode s){
  44.     int x;
  45.     if(s->next==NULL){
  46.         err("link stack empty!");
  47.     }
  48.  
  49.     x = s->next->data;
  50.     LinkNode tmp = s->next;
  51.     s->next = s->next->next;
  52.     free(tmp);
  53.     tmp = NULL;
  54.     return x;
  55. }
  56.  
  57. void dump(LinkNode s){
  58.     s = s->next;
  59.     while(s!=NULL){
  60.         printf("%d\n",s->data);
  61.         s = s->next;
  62.     }
  63. }
  64.  
  65. int precede(int i,int y){
  66.     if(i=='#') return '<';
  67.     else if(y=='#') return '>';
  68.     else if(y=='(') return '<';
  69.     else if(i=='('&&y==')') return '=';
  70.     else if(i!='('&&y==')') return '>';
  71.  
  72.     if(y=='+'||y=='-')
  73.     {
  74.         if(i!='*'||i!='/') return '<';
  75.         else return '>';
  76.     }
  77.  
  78.     if(y=='*'||y=='/')
  79.     {
  80.         if(i!='*'||i!='/') return '<';
  81.         else return '>';
  82.     }
  83. }
  84.  
  85.  
  86. int main(int argc, char **argv) {
  87.     LinkNode optr = init();
  88.     insert(optr,'#');
  89.     LinkNode opch = init();
  90.     char *s = "2+3*(2+5*(6/1))#";
  91.     int i=0;
  92.     while((s[i]!='#')||top(optr)!='#'){
  93.         if(s[i]>='0' && s[i]<='9'){
  94.             printf("insert to opch:%d\n",s[i]-48);
  95.             insert(opch,s[i]-48);
  96.             i++;
  97.         }else switch(precede(top(optr),s[i])){
  98.         case '<':
  99.             insert(optr,s[i]);
  100.             printf("insert to optr:%c\n",s[i]);
  101.             i++;
  102.             break;
  103.         case '=':
  104.             pop(optr);
  105.             printf("pop from optr:%c\n",s[i]);
  106.             i++;
  107.             break;
  108.         case '>':
  109.             insert(opch,cal(pop(opch),pop(opch),pop(optr)));
  110.         }
  111.     }
  112.     //optr 出栈,一直到optr栈顶为#为止
  113.     dump(opch);
  114.     return 0;
  115. }

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 算法研究

终于开始了MAC编程

浏览次数: 七月 30th, 2010 / 2 Comments » / by 小黑

RT,呵呵~ 经过几天的折磨后可以开始简单Object-c了~ 哈哈~

和web编程完全不一样,要非常小心内存泄露问题~

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: object-c

工作三年写过最长的一条SQL

浏览次数: 七月 16th, 2010 / 1 Comment » / by 小黑

作用是推荐好友的~ 范围是好友的好友(即2度)合并谁订阅过我的人~

  1. SELECT ma.uid,COUNT(1) AS p FROM match_ea ea LEFT JOIN match_ma ma ON ea.qid=ma.qid AND ea.aid=ma.aid 
  2. INNER JOIN (
  3.     SELECT DISTINCT uid FROM (
  4.     SELECT DISTINCT uid FROM friend WHERE fuid IN (SELECT fuid FROM friend WHERE uid=121 AND STATUS=1)
  5.     UNION SELECT uid FROM follow WHERE fuid=121
  6. ) b 
  7.     WHERE 
  8.         NOT EXISTS (SELECT NULL FROM friend WHERE uid=121 AND fuid=b.uid AND STATUS=1)
  9. ) c ON c.uid=ma.uid
  10. WHERE ea.uid=121
  11. GROUP BY uid ORDER BY p DESC LIMIT 10

此SQL有性能问题,呵呵~ 好友人数太多或订阅我的人数太多就会出现问题的~ 慎用,目前自己项目的SNS已经更新了更高效的作法~ :)

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: mysql

mango 性能没有我想象中的好~

浏览次数: 六月 23rd, 2010 / No Comments » / by 小黑

最近在执行一个大型运算,数据库记录大约6000w, 使用其中200w对于mango进行测试, 但性能几乎让我大跌眼镜…

准备给mango填充数据

  1. set_time_limit(0);
  2. $m = new Mongo('localhost:27017');
  3. $collection = $m->selectDB('test')->selectCollection('match');
  4. $collection->ensureIndex(array("uid"=>1),array("unique"=>true));
  5. $person = NULL;
  6. $i=$j=1;
  7. $answer=array();
  8. for($i=1;$i<=1000000;$i++){
  9.     $answer=array();
  10.     for($j=1;$j<=20;$j++){
  11.         $answer[]=mt_rand(1,5);
  12.     }
  13.     $person = array("uid"=>$i,"answer"=>implode("",$answer));
  14.     $collection->insert($person);
  15. }

使用mango进行map/reduce进行运算

  1. m = function () {
  2.     var i = this.answer;
  3.     var n = 0;
  4.     var s = 0;
  5.     for (n; n < i; n++) {
  6.         if (this.answer[n] == matchs[n]) {
  7.             s++;
  8.         }
  9.     }
  10.     emit(this.uid,s);
  11. }
  12. r = function(k,vals) {
  13.     var sum=0;
  14.     for(var i in vals) sum += parseInt(vals[i]);
  15.     return sum;
  16. }
  17. res = db.match.mapReduce(m,r,{scope:{matchs:"21453214254123145213"}});
  18. //这里几乎卡死,1个CPU四核,其中1个核跑满,可见mango的map/reduce真的是单进程的...

还是改用mysql靠谱,对数据进行分表后,同样使用map/reduce取数据,大约能在1s内准确完成计算,这里不给出mysql的解决方案了哈~ 就是感叹下mango没有那么牛X的性能…

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: php, 项目经验

流量观察

浏览次数: 六月 3rd, 2010 / No Comments » / by 小黑

最近通过观察引潜网的流量,发现一个很有规律的事情~

就是周四的流量都较少,为啥会这么有趣呢?
想了想,可能大家周一到周三上班都没怎么效率,到周四发现工作还有很多没做完,就周四的工作效率非常高,到周五的时候因为快要放假心都不知道飞那里去了…

所以大家的周四的工作效率是最高的~ 要把握好周四哦~ 哈哈哈~

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 心路历程

向左旋转一个一维向量

浏览次数: 五月 21st, 2010 / No Comments » / by 小黑

先取模运算得出真实要旋转的次数,如果旋转次数比向量长度要大,会有边界问题~
然后把向量分成两部分进行翻转 向量X分成两部分为 ab 旋转的意思就是要把 ab 变成 ba , 先把a翻转成 r(a) 再翻转b成为r(b) 在把整个进行翻转 r(r(a)r(b)) 就成为了ba

  1. #include <stdio.h>
  2. char str[9] = "abcdefgh\0";
  3. void reverse(int act,int end){
  4.     int tmp;
  5.     for (;act<end;act++,end--){
  6.         tmp = str[act];
  7.         str[act]=str[end];
  8.         str[end]=tmp;
  9.     }
  10. }
  11.  
  12. int main(void){
  13.     int i=3;//左旋转次数
  14.     int n = 8;//长度
  15.  
  16.     i=i%n;
  17.  
  18.     reverse(0,i-1);
  19.     reverse(i,n-1);
  20.     reverse(0,n-1);
  21.     printf("%s\n",str);
  22.     return 0;
  23. }

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: 算法研究

exit()可能会关闭标准输出

浏览次数: 五月 1st, 2010 / No Comments » / by 小黑

在写多进程或多线程程序的时候要特别注意这个问题,如果调用exit可能会冲洗所有标准I/O流,并有可能关闭标准I/O流

下面是例子

  1. int main(int argc, char **argv) {
  2.     int var;
  3.     pid_t pid;
  4.  
  5.     var=8;
  6.     printf("before fork\n");
  7.  
  8.     if((pid=vfork())<0){
  9.         err_sys("fork error!");
  10.     }else if(pid==0){//子进程
  11.         glob++;
  12.         var++;
  13.         exit(0);//错误的使用
  14.                 _exit(0);//应该这样调用
  15.     }
  16.     printf("pid=%d ,glob=%d, var=%d\n",getpid(),glob,var);
  17.     return 0;
  18. }

在某些系统上面编译运行后会发现没有任何输出,而上面的程序我只是让子进程退出,但是父进程为什么也不见有输出呢?原来exit关闭了标准输出,这个时候printf的返回值是”-1″…就是输出不成功!现在大家明白了吧~ 正确的应该调用 _exit(0);

Submit Article :- BlinkList + Blogmarks + Digg + Del.icio.us + Ekstreme Socializer + Feedmarker + Furl + Google Bookmarks + ma.gnolia + Netvouz + RawSugar + Reddit + Scuttle + Shadows + Simpy + Spurl + Technorati + Unalog + Wink

Posted in: c/c++

Older Entries