精华内容
下载资源
问答
  • 本文转载自: ... ...微软等公司数据结构+算法面试100题(第1-100题)首次完整亮相    作者:July、2010年12月6日。 更新:现今,这100题的答案已经全部整理出来了,微软面

    本文转载自:

    http://blog.csdn.net/v_july_v/article/details/6057286


    微软等公司数据结构+算法面试100题(第1-100题)首次完整亮相  
                         
     

    作者:July、2010年12月6日。

    1. 更新:现今,这100题的答案已经全部整理出来了,微软面试100题2010年版全部答案集锦:http://blog.csdn.net/v_july_v/article/details/6870251
    2. 关于此100道面试题的所有一切详情,包括答案,资源下载,帖子维护,答案更新 都请参考此文: 横空出世,席卷Csdn [评微软等数据结构+算法面试100题]
    3. 以下100题中有部分题目整理自何海涛的博客(http://zhedahht.blog.163.com/)。十分感谢。
      --------------------------------------------------- 

     

    微软等100题系列V0.1版终于结束了。

    从2010年10月11日当天最初发表前40题以来,直至此刻,整理这100题,已有近2个月。

    2个月,因为要整理这100题,很多很多其它的事都被我强迫性的搁置一旁,

    如今,要好好专心去做因这100题而被耽误的、其它的事了。

     

    这微软等数据结构+算法面试100题系列(是的,系列),到底现在、或此刻、或未来,对初学者有多大的意义,

    在此,我就不给予评说了。

    由他们自己来认定。所谓,公道自在人心,我相信这句话。

     

    任何人,对以下任何资料、题目、或答案,有任何问题,欢迎联系我。

    作者邮箱:

    zhoulei0907@yahoo.cn

    786165179@qq.com

     

    作者声明:

    转载或引用以下任何资料、或题目,请注明作者本人July及出处。

    向您的厚道致敬,谢谢。

     

    好了,请享受这完完整整的100题吧,这可是首次完整亮相哦。:D。

    -----------------------------------

    1.把二元查找树转变成排序的双向链表(树)
     题目:
    输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
    要求不能创建任何新的结点,只调整指针的指向。
       10
      / /
      6  14
     / / / /
    4  8 12 16
     转换成双向链表
    4=6=8=10=12=14=16。
     
     首先我们定义的二元查找树 节点的数据结构如下:
     struct BSTreeNode
    {
      int m_nValue; // value of node
      BSTreeNode *m_pLeft; // left child of node
      BSTreeNode *m_pRight; // right child of node
    };

     
    2.设计包含min函数的栈(栈)
    定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。
    要求函数min、push以及pop的时间复杂度都是O(1)。

     
    3.求子数组的最大和(数组)
    题目:
    输入一个整形数组,数组里有正数也有负数。
    数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。
    求所有子数组的和的最大值。要求时间复杂度为O(n)。

    例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5,和最大的子数组为3, 10, -4, 7, 2,
    因此输出为该子数组的和18。

     

    4.在二元树中找出和为某一值的所有路径(树)

    题目:输入一个整数和一棵二元树。
    从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
    打印出和与输入整数相等的所有路径。
    例如 输入整数22和如下二元树
        10  
      /   /   
     5    12   
    / \     
    4  7
    则打印出两条路径:10, 12和10, 5, 7。

    二元树节点的数据结构定义为:
    struct BinaryTreeNode // a node in the binary tree
    {
    int m_nValue; // value of node
    BinaryTreeNode *m_pLeft; // left child of node
    BinaryTreeNode *m_pRight; // right child of node
    };

     

    5.查找最小的k个元素(数组)
    题目:输入n个整数,输出其中最小的k个。
    例如输入1,2,3,4,5,6,7和8这8个数字,则最小的4个数字为1,2,3和4。

     
    第6题(数组)
    腾讯面试题: 
    给你10分钟时间,根据上排给出十个数,在其下排填出对应的十个数 
    要求下排每个数都是先前上排那十个数在下排出现的次数。 
    上排的十个数如下: 
    【0,1,2,3,4,5,6,7,8,9】

    举一个例子, 
    数值: 0,1,2,3,4,5,6,7,8,9 
    分配: 6,2,1,0,0,0,1,0,0,0 
    0在下排出现了6次,1在下排出现了2次, 
    2在下排出现了1次,3在下排出现了0次.... 
    以此类推..


    第7题(链表)
    微软亚院之编程判断俩个链表是否相交
    给出俩个单向链表的头指针,比如h1,h2,判断这俩个链表是否相交。
    为了简化问题,我们假设俩个链表均不带环。

    问题扩展:
    1.如果链表可能有环列?
    2.如果需要求出俩个链表相交的第一个节点列?

     
    第8题(算法)
    此贴选一些 比较怪的题,,由于其中题目本身与算法关系不大,仅考考思维。特此并作一题。
    1.有两个房间,一间房里有三盏灯,另一间房有控制着三盏灯的三个开关,

    这两个房间是 分割开的,从一间里不能看到另一间的情况。
    现在要求受训者分别进这两房间一次,然后判断出这三盏灯分别是由哪个开关控制的。
    有什么办法呢?

    2.你让一些人为你工作了七天,你要用一根金条作为报酬。金条被分成七小块,每天给出一块。
    如果你只能将金条切割两次,你怎样分给这些工人?

    3. ★用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。
      ★用一种算法在一个循环的链接表里插入一个节点,但不得穿越链接表。
      ★用一种算法整理一个数组。你为什么选择这种方法?
      ★用一种算法使通用字符串相匹配。
      ★颠倒一个字符串。优化速度。优化空间。
      ★颠倒一个句子中的词的顺序,比如将“我叫克丽丝”转换为“克丽丝叫我”,

    实现速度最快,移动最少。
      ★找到一个子字符串。优化速度。优化空间。
      ★比较两个字符串,用O(n)时间和恒量空间。
      ★假设你有一个用1001个整数组成的数组,这些整数是任意排列的,但是你知道所有的整数都在1到1000(包括1000)之间。此外,除一个数字出现两次外,其他所有数字只出现一次。假设你只能对这个数组做一次处理,用一种算法找出重复的那个数字。如果你在运算中使用了辅助的存储方式,那么你能找到不用这种方式的算法吗?
      ★不用乘法或加法增加8倍。现在用同样的方法增加7倍。

     


    第9题(树)
    判断整数序列是不是二元查找树的后序遍历结果
    题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。
    如果是返回true,否则返回false。

    例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:

             8
          /  /
         6    10
        / /  / /
       5  7 9  11
    因此返回true。
    如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列,因此返回false。

     

    第10题(字符串)
    翻转句子中单词的顺序。
    题目:输入一个英文句子,翻转句子中单词的顺序,但单词内字符的顺序不变。

    句子中单词以空格符隔开。为简单起见,标点符号和普通字母一样处理。
    例如输入“I am a student.”,则输出“student. a am I”。

     
    第11题(树)
    求二叉树中节点的最大距离...

    如果我们把二叉树看成一个图,父子节点之间的连线看成是双向的,
    我们姑且定义"距离"为两节点之间边的个数。
    写一个程序,
    求一棵二叉树中相距最远的两个节点之间的距离。

     

    第12题(语法)
    题目:求1+2+…+n,
    要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句(A?B:C)。

     

    第13题(链表):
    题目:输入一个单向链表,输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
    链表结点定义如下:  
    struct ListNode
    {
      int m_nKey;
      ListNode* m_pNext;
    };

     

    第14题(数组):
    题目:输入一个已经按升序排序过的数组和一个数字,
    在数组中查找两个数,使得它们的和正好是输入的那个数字。
    要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
    例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。

     

    第15题(树):
    题目:输入一颗二元查找树,将该树转换为它的镜像,
    即在转换后的二元查找树中,左子树的结点都大于右子树的结点。
    用递归和循环两种方法完成树的镜像转换。  
    例如输入:
      8
      / /
      6 10
     // //
    5 7 9 11

    输出:
       8
      / /
     10 6
     // //
    11 9 7 5

    定义二元查找树的结点为:
    struct BSTreeNode // a node in the binary search tree (BST)
    {
      int m_nValue; // value of node
      BSTreeNode *m_pLeft; // left child of node
      BSTreeNode *m_pRight; // right child of node
    };

     

    第16题(树):
    题目(微软):
    输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。  
    例如输入

       8
      / /
     6 10
    / / / /
    5 7 9 11

    输出8 6 10 5 7 9 11。

     

    第17题(字符串):
    题目:在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。  
    分析:这道题是2006年google的一道笔试题。

     


    第18题(数组):
    题目:n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,
    每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。
    当一个数字删除后,从被删除数字的下一个继续删除第m个数字。
    求出在这个圆圈中剩下的最后一个数字。
    July:我想,这个题目,不少人已经 见识过了。

     


    第19题(数组、递归):
    题目:定义Fibonacci数列如下:  
      / 0 n=0
    f(n)= 1 n=1
      / f(n-1)+f(n-2) n=2

    输入n,用最快的方法求该数列的第n项。
    分析:在很多C语言教科书中讲到递归函数的时候,都会用Fibonacci作为例子。
    因此很多程序员对这道题的递归解法非常熟悉,但....呵呵,你知道的。。

     

    第20题(字符串):
    题目:输入一个表示整数的字符串,把该字符串转换成整数并输出。
    例如输入字符串"345",则输出整数345。

     

    第21题(数组)
    2010年中兴面试题
    编程求解:
    输入两个整数 n 和 m,从数列1,2,3.......n 中 随意取几个数,
    使其和等于 m ,要求将其中所有的可能组合列出来.

     

    第22题(推理):
    有4张红色的牌和4张蓝色的牌,主持人先拿任意两张,再分别在A、B、C三人额头上贴任意两张牌,
    A、B、C三人都可以看见其余两人额头上的牌,看完后让他们猜自己额头上是什么颜色的牌,
    A说不知道,B说不知道,C说不知道,然后A说知道了。
    请教如何推理,A是怎么知道的。
    如果用程序,又怎么实现呢?

     
    第23题(算法):
    用最简单,最快速的方法计算出下面这个圆形是否和正方形相交。"  
    3D坐标系 原点(0.0,0.0,0.0)
    圆形:
    半径r = 3.0
    圆心o = (*.*, 0.0, *.*)

    正方形:
    4个角坐标;  
    1:(*.*, 0.0, *.*)
    2:(*.*, 0.0, *.*)
    3:(*.*, 0.0, *.*)
    4:(*.*, 0.0, *.*)

     

    第24题(链表):
    链表操作,单链表就地逆置,
     

    第25题(字符串):
    写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
    功能:
    在字符串中找出连续最长的数字串,并把这个串的长度返回,
    并把这个最长数字串付给其中一个函数参数outputstr所指内存。
    例如:"abcd12345ed125ss123456789"的首地址传给intputstr后,函数将返回9,
    outputstr所指的值为123456789

     

    26.左旋转字符串(字符串)

    题目:
    定义字符串的左旋转操作:把字符串前面的若干个字符移动到字符串的尾部。

    如把字符串abcdef左旋转2位得到字符串cdefab。请实现字符串左旋转的函数。
    要求时间对长度为n的字符串操作的复杂度为O(n),辅助内存为O(1)。

     

    27.跳台阶问题(递归)
    题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。
    求总共有多少总跳法,并分析算法的时间复杂度。

    这道题最近经常出现,包括MicroStrategy等比较重视算法的公司
    都曾先后选用过个这道题作为面试题或者笔试题。

     

    28.整数的二进制表示中1的个数(运算)
    题目:输入一个整数,求该整数的二进制表达中有多少个1。
    例如输入10,由于其二进制表示为1010,有两个1,因此输出2。

    分析:
    这是一道很基本的考查位运算的面试题。
    包括微软在内的很多公司都曾采用过这道题。

     
    29.栈的push、pop序列(栈)
    题目:输入两个整数序列。其中一个序列表示栈的push顺序,
    判断另一个序列有没有可能是对应的pop顺序。
    为了简单起见,我们假设push序列的任意两个整数都是不相等的。 

    比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。
    因为可以有如下的push和pop序列:
    push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
    这样得到的pop序列就是4、5、3、2、1。
    但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

     
    30.在从1到n的正数中1出现的次数(数组)
    题目:输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

    例如输入12,从1到12这些整数中包含1 的数字有1,10,11和12,1一共出现了5次。
    分析:这是一道广为流传的google面试题。

     

    31.华为面试题(搜索):
    一类似于蜂窝的结构的图,进行搜索最短路径(要求5分钟)

     

    32.(数组、规划)
    有两个序列a,b,大小都为n,序列元素的值任意整数,无序;
    要求:通过交换a,b中的元素,使[序列a元素的和]与[序列b元素的和]之间的差最小。
    例如:  
    var a=[100,99,98,1,2, 3];
    var b=[1, 2, 3, 4,5,40];

     
    33.(字符串)
    实现一个挺高级的字符匹配算法:
    给一串很长字符串,要求找到符合要求的字符串,例如目的串:123
    1******3***2 ,12*****3这些都要找出来
    其实就是类似一些和谐系统。。。。。

     
    34.(队列)
    实现一个队列。
    队列的应用场景为:
    一个生产者线程将int类型的数入列,一个消费者线程将int类型的数出列

     
    35.(矩阵)
    求一个矩阵中最大的二维矩阵(元素和最大).如:
    1 2 0 3 4
    2 3 4 5 1
    1 1 5 3 0
    中最大的是:
    4 5
    5 3
    要求:(1)写出算法;(2)分析时间复杂度;(3)用C写出关键代码

     
    第36题-40题(有些题目搜集于CSDN上的网友,已标明):
    36.引用自网友:longzuo(运算)
    谷歌笔试:
    n支队伍比赛,分别编号为0,1,2。。。。n-1,已知它们之间的实力对比关系,
    存储在一个二维数组w[n][n]中,w[i][j] 的值代表编号为i,j的队伍中更强的一支。

    所以w[i][j]=i 或者j,现在给出它们的出场顺序,并存储在数组order[n]中,
    比如order[n] = {4,3,5,8,1......},那么第一轮比赛就是 4对3, 5对8。.......
    胜者晋级,败者淘汰,同一轮淘汰的所有队伍排名不再细分,即可以随便排,
    下一轮由上一轮的胜者按照顺序,再依次两两比,比如可能是4对5,直至出现第一名

    编程实现,给出二维数组w,一维数组order 和 用于输出比赛名次的数组result[n],
    求出result。

     

    37.(字符串)
    有n个长为m+1的字符串,
    如果某个字符串的最后m个字符与某个字符串的前m个字符匹配,则两个字符串可以联接,
    问这n个字符串最多可以连成一个多长的字符串,如果出现循环,则返回错误。

     

    38.(算法)
    百度面试:
    1.用天平(只能比较,不能称重)从一堆小球中找出其中唯一一个较轻的,使用x次天平,
    最多可以从y个小球中找出较轻的那个,求y与x的关系式。

    2.有一个很大很大的输入流,大到没有存储器可以将其存储下来,
    而且只输入一次,如何从这个输入流中随机取得m个记录。

    3.大量的URL字符串,如何从中去除重复的,优化时间空间复杂度

     
    39.(树、图、算法)
    网易有道笔试:
    (1).
    求一个二叉树中任意两个节点间的最大距离,
    两个节点的距离的定义是 这两个节点间边的个数,
    比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。

    (2).
    求一个有向连通图的割点,割点的定义是,如果除去此节点和与其相关的边,
    有向图不再连通,描述算法。

     

    40.百度研发笔试题(栈、算法)
    引用自:zp155334877
    1)设计一个栈结构,满足一下条件:min,push,pop操作的时间复杂度为O(1)。

    2)一串首尾相连的珠子(m个),有N种颜色(N<=10),
    设计一个算法,取出其中一段,要求包含所有N中颜色,并使长度最短。
    并分析时间复杂度与空间复杂度。

    3)设计一个系统处理词语搭配问题,比如说 中国 和人民可以搭配,
    则中国人民 人民中国都有效。要求:

      *系统每秒的查询数量可能上千次;
      *词语的数量级为10W;
      *每个词至多可以与1W个词搭配

    当用户输入中国人民的时候,要求返回与这个搭配词组相关的信息。


    41.求固晶机的晶元查找程序(匹配、算法)
    晶元盘由数目不详的大小一样的晶元组成,晶元并不一定全布满晶元盘,

    照相机每次这能匹配一个晶元,如匹配过,则拾取该晶元,
    若匹配不过,照相机则按测好的晶元间距移到下一个位置。
    求遍历晶元盘的算法 求思路。

     

    42.请修改append函数,利用这个函数实现(链表):

    两个非降序链表的并集,1->2->3 和 2->3->5 并为 1->2->3->5
    另外只能输出结果,不能修改两个链表的数据。

     

    43.递归和非递归俩种方法实现二叉树的前序遍历。

     

    44.腾讯面试题(算法):
    1.设计一个魔方(六面)的程序。
    2.有一千万条短信,有重复,以文本文件的形式保存,一行一条,有重复。
    请用5分钟时间,找出重复出现最多的前10条。

    3.收藏了1万条url,现在给你一条url,如何找出相似的url。(面试官不解释何为相似)

     

    45.雅虎(运算、矩阵):
    1.对于一个整数矩阵,存在一种运算,对矩阵中任意元素加一时,需要其相邻(上下左右)

    某一个元素也加一,现给出一正数矩阵,判断其是否能够由一个全零矩阵经过上述运算得到。
    2.一个整数数组,长度为n,将其分为m份,使各份的和相等,求m的最大值
      比如{3,2,4,3,6} 可以分成{3,2,4,3,6} m=1; 
      {3,6}{2,4,3} m=2
      {3,3}{2,4}{6} m=3 所以m的最大值为3

     


    46.搜狐(运算):
    四对括号可以有多少种匹配排列方式?比如两对括号可以有两种:()()和(())


    47.创新工场(算法):
    求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}

     

    48.微软(运算):
    一个数组是由一个递减数列左移若干位形成的,比如{4,3,2,1,6,5}
    是由{6,5,4,3,2,1}左移两位形成的,在这种数组中查找某一个数。

     

    49.一道看上去很吓人的算法面试题(排序、算法):
    如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)

     

    50.网易有道笔试(sorry,与第39题重复):
    1.求一个二叉树中任意两个节点间的最大距离,两个节点的距离的定义是 这两个节点间边的个数,
    比如某个孩子节点和父节点间的距离是1,和相邻兄弟节点间的距离是2,优化时间空间复杂度。

    2.求一个有向连通图的割点,割点的定义是,
    如果除去此节点和与其相关的边,有向图不再连通,描述算法。
    -------------------------------------------------------------------


    51.和为n连续正数序列(数组)。
    题目:输入一个正数n,输出所有和为n连续正数序列。

    例如输入15,由于1+2+3+4+5=4+5+6=7+8=15,所以输出3个连续序列1-5、4-6和7-8。
    分析:这是网易的一道面试题。

     


    52.二元树的深度(树)。

    题目:输入一棵二元树的根结点,求该树的深度。

    从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的长度为树的深度。

    例如:输入二元树:
                                                10
                                              /     /
                                            6        14
                                          /         /   /
                                        4         12     16

    输出该树的深度3。

    二元树的结点定义如下:

    struct SBinaryTreeNode // a node of the binary tree
    {
          int               m_nValue; // value of node
          SBinaryTreeNode  *m_pLeft;  // left child of node
          SBinaryTreeNode  *m_pRight; // right child of node
    };
    分析:这道题本质上还是考查二元树的遍历。

     

    53.字符串的排列(字符串)。
    题目:输入一个字符串,打印出该字符串中字符的所有排列。
    例如输入字符串abc,则输出由字符a、b、c所能排列出来的所有字符串
    abc、acb、bac、bca、cab和cba。

    分析:这是一道很好的考查对递归理解的编程题,
    因此在过去一年中频繁出现在各大公司的面试、笔试题中。

     

    54.调整数组顺序使奇数位于偶数前面(数组)。

    题目:输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,
    所有偶数位于数组的后半部分。要求时间复杂度为O(n)。

     

    55.(语法)
    题目:类CMyString的声明如下:
    class CMyString
    {
    public:
          CMyString(char* pData = NULL);
          CMyString(const CMyString& str);
          ~CMyString(void);
          CMyString& operator = (const CMyString& str);

    private:
          char* m_pData;
    };
    请实现其赋值运算符的重载函数,要求异常安全,即当对一个对象进行赋值时发生异常,对象的状态不能改变。

     

    56.最长公共字串(算法、字符串)。

    题目:如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,

    则字符串一称之为字符串二的子串。

    注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。
    请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。

    例如:输入两个字符串BDCABA和ABCBDAB,字符串BCBA和BDAB都是是它们的最长公共子串,
    则输出它们的长度4,并打印任意一个子串。

    分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,

    因此一些重视算法的公司像MicroStrategy都把它当作面试题。

     


    57.用俩个栈实现队列(栈、队列)。

    题目:某队列的声明如下:

    template<typename T> class CQueue
    {
    public:
          CQueue() {}
          ~CQueue() {}

          void appendTail(const T& node);  // append a element to tail
          void deleteHead();               // remove a element from head

    private:
         T> m_stack1;
         T> m_stack2;
    };

    分析:从上面的类的声明中,我们发现在队列中有两个栈。
    因此这道题实质上是要求我们用两个栈来实现一个队列。
    相信大家对栈和队列的基本性质都非常了解了:栈是一种后入先出的数据容器,
    因此对队列进行的插入和删除操作都是在栈顶上进行;队列是一种先入先出的数据容器,
    我们总是把新元素插入到队列的尾部,而从队列的头部删除元素。

     


    58.从尾到头输出链表(链表)。

    题目:输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:
    struct ListNode
    {

          int       m_nKey;
          ListNode* m_pNext;
    };
    分析:这是一道很有意思的面试题。
    该题以及它的变体经常出现在各大公司的面试、笔试题中。

     


    59.不能被继承的类(语法)。
    题目:用C++设计一个不能被继承的类。

    分析:这是Adobe公司2007年校园招聘的最新笔试题。
    这道题除了考察应聘者的C++基本功底外,还能考察反应能力,是一道很好的题目。

     

     

    60.在O(1)时间内删除链表结点(链表、算法)。

    题目:给定链表的头指针和一个结点指针,在O(1)时间删除该结点。链表结点的定义如下:

    struct ListNode

    {

          int        m_nKey;

          ListNode*  m_pNext;

    };

    函数的声明如下:
    void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);

    分析:这是一道广为流传的Google面试题,能有效考察我们的编程基本功,还能考察我们的反应速度,

    更重要的是,还能考察我们对时间复杂度的理解。
    -------------------------------------------------------------------------

     

    61.找出数组中两个只出现一次的数字(数组)
    题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。
    请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    分析:这是一道很新颖的关于位运算的面试题。

     


    62.找出链表的第一个公共结点(链表)。
    题目:两个单向链表,找出它们的第一个公共结点。

    链表的结点定义为:
    struct ListNode

    {

          int         m_nKey;

          ListNode*   m_pNext;

    };

    分析:这是一道微软的面试题。微软非常喜欢与链表相关的题目,
    因此在微软的面试题中,链表出现的概率相当高。

     


    63.在字符串中删除特定的字符(字符串)。
    题目:输入两个字符串,从第一字符串中删除第二个字符串中所有的字符。

    例如,输入”They are students.”和”aeiou”,

    则删除之后的第一个字符串变成”Thy r stdnts.”。

    分析:这是一道微软面试题。在微软的常见面试题中,与字符串相关的题目占了很大的一部分,
    因为写程序操作字符串能很好的反映我们的编程基本功。

     


    64. 寻找丑数(运算)。
    题目:我们把只包含因子2、3和5的数称作丑数(Ugly Number)。例如6、8都是丑数,
    但14不是,因为它包含因子7。习惯上我们把1当做是第一个丑数。
    求按从小到大的顺序的第1500个丑数。

    分析:这是一道在网络上广为流传的面试题,据说google曾经采用过这道题。

     


    65.输出1到最大的N位数(运算)
    题目:输入数字n,按顺序输出从1最大的n位10进制数。比如输入3,

    则输出1、2、3一直到最大的3位数即999。
    分析:这是一道很有意思的题目。看起来很简单,其实里面却有不少的玄机。

     

    66.颠倒栈(栈)。
    题目:用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5},1在栈顶。
    颠倒之后的栈为{5, 4, 3, 2, 1},5处在栈顶。


     

    67.俩个闲玩娱乐(运算)。

    1.扑克牌的顺子
    从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。
    2-10为数字本身,A为1,J为11,Q为12,K为13,而大小王可以看成任意数字。

    2.n个骰子的点数。
    把n个骰子扔在地上,所有骰子朝上一面的点数之和为S。输入n,
    打印出S的所有可能的值出现的概率。

     


    68.把数组排成最小的数(数组、算法)。
    题目:输入一个正整数数组,将它们连接起来排成一个数,输出能排出的所有数字中最小的一个。
    例如输入数组{32,  321},则输出这两个能排成的最小数字32132。
    请给出解决问题的算法,并证明该算法。

    分析:这是09年6月份百度的一道面试题,
    从这道题我们可以看出百度对应聘者在算法方面有很高的要求。

     


    69.旋转数组中的最小元素(数组、算法)。
    题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个排好序的数组的一个旋转,

    输出旋转数组的最小元素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转,该数组的最小值为1。

        分析:这道题最直观的解法并不难。从头到尾遍历数组一次,就能找出最小的元素,
    时间复杂度显然是O(N)。但这个思路没有利用输入数组的特性,我们应该能找到更好的解法。

     


    70.给出一个函数来输出一个字符串的所有排列(经典字符串问题)。
    ANSWER 简单的回溯就可以实现了。当然排列的产生也有很多种算法,去看看组合数学,

    还有逆序生成排列和一些不需要递归生成排列的方法。
    印象中Knuth的<TAOCP>第一卷里面深入讲了排列的生成。这些算法的理解需要一定的数学功底,
    也需要一定的灵感,有兴趣最好看看。

     


    71.数值的整数次方(数字、运算)。

    题目:实现函数double Power(double base, int exponent),求base的exponent次方。
    不需要考虑溢出。

    分析:这是一道看起来很简单的问题。可能有不少的人在看到题目后30秒写出如下的代码:
    double Power(double base, int exponent)
    {

          double result = 1.0;
          for(int i = 1; i <= exponent; ++i)
                result *= base;
          return result;
    }

     

     

    72.(语法)
    题目:设计一个类,我们只能生成该类的一个实例。
    分析:只能生成一个实例的类是实现了Singleton模式的类型。

     

     
    73.对称字符串的最大长度(字符串)。

    题目:输入一个字符串,输出该字符串中对称的子字符串的最大长度。
    比如输入字符串“google”,由于该字符串里最长的对称子字符串是“goog”,因此输出4。

    分析:可能很多人都写过判断一个字符串是不是对称的函数,这个题目可以看成是该函数的加强版。

     


    74.数组中超过出现次数超过一半的数字(数组)

    题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。

    分析:这是一道广为流传的面试题,包括百度、微软和Google在内的多家公司都
    曾经采用过这个题目。要几十分钟的时间里很好地解答这道题,
    除了较好的编程能力之外,还需要较快的反应和较强的逻辑思维能力。

     

     

    75.二叉树两个结点的最低共同父结点(树)
    题目:二叉树的结点定义如下:
    struct TreeNode
    {

        int m_nvalue;
        TreeNode* m_pLeft;
        TreeNode* m_pRight;
    };

    输入二叉树中的两个结点,输出这两个结点在数中最低的共同父结点。
    分析:求数中两个结点的最低共同结点是面试中经常出现的一个问题。这个问题至少有两个变种。

     


    76.复杂链表的复制(链表、算法)

    题目:有一个复杂链表,其结点除了有一个m_pNext指针指向下一个结点外,
    还有一个m_pSibling指向链表中的任一结点或者NULL。其结点的C++定义如下:
     struct ComplexNode
    {
        int m_nValue;
        ComplexNode* m_pNext;
        ComplexNode* m_pSibling;
    };

    下图是一个含有5个结点的该类型复杂链表。
    图中实线箭头表示m_pNext指针,虚线箭头表示m_pSibling指针。为简单起见,
    指向NULL的指针没有画出。

                                     
    请完成函数ComplexNode* Clone(ComplexNode* pHead),以复制一个复杂链表。 
    分析:在常见的数据结构上稍加变化,这是一种很新颖的面试题。
    要在不到一个小时的时间里解决这种类型的题目,我们需要较快的反应能力,
    对数据结构透彻的理解以及扎实的编程功底。

     

     


    77.关于链表问题的面试题目如下(链表):

    1.给定单链表,检测是否有环。
     使用两个指针p1,p2从链表头开始遍历,p1每次前进一步,p2每次前进两步。如果p2到达链表尾部,
    说明无环,否则p1、p2必然会在某个时刻相遇(p1==p2),从而检测到链表中有环。

     

    2.给定两个单链表(head1, head2),检测两个链表是否有交点,如果有返回第一个交点。

            如果head1==head2,那么显然相交,直接返回head1。
    否则,分别从head1,head2开始遍历两个链表获得其长度len1与len2,假设len1>=len2,
    那么指针p1由head1开始向后移动len1-len2步,指针p2=head2,
    下面p1、p2每次向后前进一步并比较p1p2是否相等,如果相等即返回该结点,
    否则说明两个链表没有交点。


    3.给定单链表(head),如果有环的话请返回从头结点进入环的第一个节点。
            运用题一,我们可以检查链表中是否有环。
            如果有环,那么p1p2重合点p必然在环中。从p点断开环,
    方法为:p1=p, p2=p->next, p->next=NULL。此时,原单链表可以看作两条单链表,
    一条从head开始,另一条从p2开始,于是运用题二的方法,我们找到它们的第一个交点即为所求。


    4.只给定单链表中某个结点p(并非最后一个结点,即p->next!=NULL)指针,删除该结点。
     办法很简单,首先是放p中数据,然后将p->next的数据copy入p中,接下来删除p->next即可。

    5.只给定单链表中某个结点p(非空结点),在p前面插入一个结点。
      办法与前者类似,首先分配一个结点q,将q插入在p后,接下来将p中的数据copy入q中,
    然后再将要插入的数据记录在p中。

     

    78.链表和数组的区别在哪里(链表、数组)?

    分析:主要在基本概念上的理解。
    但是最好能考虑的全面一点,现在公司招人的竞争可能就在细节上产生,
    谁比较仔细,谁获胜的机会就大。

     
    79.(链表、字符串)
    1.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法?
    2.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法?
    3.请编写能直接实现strstr()函数功能的代码。


     

    80.阿里巴巴一道笔试题(运算、算法)

    问题描述:
    12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
    这个笔试题,很YD,因为把某个递归关系隐藏得很深。

     

    先来几组百度的面试题:

    ===================

    81.第1组百度面试题
    1.一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],
    其左边的数都小于等于它,右边的数都大于等于它。
    能否只用一个额外数组和少量其它空间实现。
    2.一个文件,内含一千万行字符串,每个字符串在1K以内,
    要求找出所有相反的串对,如abc和cba。
    3.STL的set用什么实现的?为什么不用hash?

     

    82.第2组百度面试题
    1.给出两个集合A和B,其中集合A={name},
    集合B={age、sex、scholarship、address、...},
    要求:
    问题1、根据集合A中的name查询出集合B中对应的属性信息;
    问题2、根据集合B中的属性信息(单个属性,如age<20等),查询出集合A中对应的name。

    2.给出一个文件,里面包含两个字段{url、size},
    即url为网址,size为对应网址访问的次数,
    要求:
    问题1、利用Linux Shell命令或自己设计算法,
    查询出url字符串中包含“baidu”子字符串对应的size字段值;
    问题2、根据问题1的查询结果,对其按照size由大到小的排列。
    (说明:url数据量很大,100亿级以上)

     

    83.第3组百度面试题
    1.今年百度的一道题目
    百度笔试:给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。
    要求:空间复杂度O(1),时间复杂度为O(n)。

    2.百度笔试题
    用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。
    memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
    分析:
    由于可以把任何类型的指针赋给void类型的指针
    这个函数主要是实现各种数据类型的拷贝。

     

    84.第4组百度面试题
    2010年3道百度面试题[相信,你懂其中的含金量]
    1.a~z包括大小写与0~9组成的N个数
    用最快的方式把其中重复的元素挑出来。
    2.已知一随机发生器,产生0的概率是p,产生1的概率是1-p,现在要你构造一个发生器,
    使得它构造0和1的概率均为1/2;构造一个发生器,使得它构造1、2、3的概率均为1/3;...,
    构造一个发生器,使得它构造1、2、3、...n的概率均为1/n,要求复杂度最低。
    3.有10个文件,每个文件1G,
    每个文件的每一行都存放的是用户的query,每个文件的query都可能重复。
    要求按照query的频度排序.

     

    85.又见字符串的问题
    1.给出一个函数来复制两个字符串A和B。
    字符串A的后几个字节和字符串B的前几个字节重叠。
    分析:记住,这种题目往往就是考你对边界的考虑情况。
    2.已知一个字符串,比如asderwsde,寻找其中的一个子字符串比如sde的个数,
    如果没有返回0,有的话返回子字符串的个数。

     
    86.
    怎样编写一个程序,把一个有序整数数组放到二叉树中?
    分析:本题考察二叉搜索树的建树方法,简单的递归结构。
    关于树的算法设计一定要联想到递归,因为树本身就是递归的定义。

    而,学会把递归改称非递归也是一种必要的技术。
    毕竟,递归会造成栈溢出,关于系统底层的程序中不到非不得以最好不要用。
    但是对某些数学问题,就一定要学会用递归去解决。

     

    87.
    1.大整数数相乘的问题。(这是2002年在一考研班上遇到的算法题)
    2.求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
    3.实现strstr功能,即在父串中寻找子串首次出现的位置。
    (笔试中常让面试者实现标准库中的一些函数)

     


    88.2005年11月金山笔试题。编码完成下面的处理函数。
    函数将字符串中的字符'*'移到串的前部分,

    前面的非'*'字符后移,但不能改变非'*'字符的先后顺序,函数返回串中字符'*'的数量。
    如原始串为:ab**cd**e*12,
    处理后为*****abcde12,函数并返回值为5。(要求使用尽量少的时间和辅助空间)

     

    89.神州数码、华为、东软笔试题
    1.2005年11月15日华为软件研发笔试题。实现一单链表的逆转。
    2.编码实现字符串转整型的函数(实现函数atoi的功能),据说是神州数码笔试题。如将字符
    串 ”+123”123, ”-0123”-123, “123CS45”123, “123.45CS”123, “CS123.45”0
    3.快速排序(东软喜欢考类似的算法填空题,又如堆排序的算法等)
    4.删除字符串中的数字并压缩字符串。
    如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。
    (下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
    5.求两个串中的第一个最长子串(神州数码以前试题)。
    如"abractyeyt","dgdsaeactyey"的最大子串为"actyet"。

     


    90.
    1.不开辟用于交换数据的临时空间,如何完成字符串的逆序
    (在技术一轮面试中,有些面试官会这样问)。
    2.删除串中指定的字符
    (做此题时,千万不要开辟新空间,否则面试官可能认为你不适合做嵌入式开发
    3.判断单链表中是否存在环。

     

    91.
    1.一道著名的毒酒问题
    有1000桶酒,其中1桶有毒。而一旦吃了,毒性会在1周后发作。
    现在我们用小老鼠做实验,要在1周内找出那桶毒酒,问最少需要多少老鼠。
    2.有趣的石头问题
    有一堆1万个石头和1万个木头,对于每个石头都有1个木头和它重量一样,
    把配对的石头和木头找出来。

     

     

    92.
    1.多人排成一个队列,我们认为从低到高是正确的序列,但是总有部分人不遵守秩序。
    如果说,前面的人比后面的人高(两人身高一样认为是合适的),
    那么我们就认为这两个人是一对“捣乱分子”,比如说,现在存在一个序列:
    176, 178, 180, 170, 171
    这些捣乱分子对为
    <176, 170>, <176, 171>, <178, 170>, <178, 171>, <180, 170>, <180, 171>, 
    那么,现在给出一个整型序列,请找出这些捣乱分子对的个数(仅给出捣乱分子对的数目即可,不用具体的对)

    要求:
    输入:
    为一个文件(in),文件的每一行为一个序列。序列全为数字,数字间用”,”分隔。
    输出:
    为一个文件(out),每行为一个数字,表示捣乱分子的对数。

    详细说明自己的解题思路,说明自己实现的一些关键点。
    并给出实现的代码 ,并分析时间复杂度。
    限制:
    输入每行的最大数字个数为100000个,数字最长为6位。程序无内存使用限制。

     

    93.在一个int数组里查找这样的数,它大于等于左侧所有数,小于等于右侧所有数。
    直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数,

    一个解答:这需要两次遍历,然后再遍历一次原数组,
    将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

    给出这个解答后,面试官有要求只能用一个辅助数组,且要求少遍历一次。

     

    94.微软笔试题
    求随机数构成的数组中找到长度大于=3的最长的等差数列9 d- x' W) w9 ?" o3 b0 R
    输出等差数列由小到大: 
    如果没有符合条件的就输出
    格式:
    输入[1,3,0,5,-1,6]
    输出[-1,1,3,5]
    要求时间复杂度,空间复杂度尽量小

     

    95.华为面试题
    1 判断一字符串是不是对称的,如:abccba
    2.用递归的方法判断整数组a[N]是不是升序排列

     

    96.08年中兴校园招聘笔试题
    1.编写strcpy 函数
    已知strcpy 函数的原型是
    char *strcpy(char *strDest, const char *strSrc);
    其中strDest 是目的字符串,strSrc 是源字符串。不调用C++/C 的字符串库函数,请
    编写函数 strcpy

     


    最后压轴之戏,终结此微软等100题系列V0.1版。
    那就,
    连续来几组微软公司的面试题,让你一次爽个够:
    ======================
    97.第1组微软较简单的算法面试题
    1.编写反转字符串的程序,要求优化速度、优化空间。 
    2.在链表里如何发现循环链接?
    3.编写反转字符串的程序,要求优化速度、优化空间。
    4.给出洗牌的一个算法,并将洗好的牌存储在一个整形数组里。 
    5.写一个函数,检查字符是否是整数,如果是,返回其整数值。
    (或者:怎样只用4行代码编写出一个从字符串到长整形的函数?)


    98.第2组微软面试题
    1.给出一个函数来输出一个字符串的所有排列。
    2.请编写实现malloc()内存分配函数功能一样的代码。
    3.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。 
    4.怎样编写一个程序,把一个有序整数数组放到二叉树中? 
    5.怎样从顶部开始逐层打印二叉树结点数据?请编程。 
    6.怎样把一个链表掉个顺序(也就是反序,注意链表的边界条件并考虑空链表)?


    99.第3组微软面试题
    1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。
    现在有若干条材质相同的绳子,问如何用烧绳的方法来计时一个小时十五分钟呢?
    2.你有一桶果冻,其中有黄色、绿色、红色三种,闭上眼睛抓取同种颜色的两个。
    抓取多少个就可以确定你肯定有两个同一颜色的果冻?(5秒-1分钟) 
    3.如果你有无穷多的水,一个3公升的提捅,一个5公升的提捅,两只提捅形状上下都不均匀,
    问你如何才能准确称出4公升的水?(40秒-3分钟) 
    一个岔路口分别通向诚实国和说谎国。
    来了两个人,已知一个是诚实国的,另一个是说谎国的。
    诚实国永远说实话,说谎国永远说谎话。现在你要去说谎国,
    但不知道应该走哪条路,需要问这两个人。请问应该怎么问?(20秒-2分钟)


    100.第4组微软面试题,挑战思维极限
    1.12个球一个天平,现知道只有一个和其它的重量不同,问怎样称才能用三次就找到那个球。

    13个呢?(注意此题并未说明那个球的重量是轻是重,所以需要仔细考虑)(5分钟-1小时) 
    2.在9个点上画10条直线,要求每条直线上至少有三个点?(3分钟-20分钟) 
    3.在一天的24小时之中,时钟的时针、分针和秒针完全重合在一起的时候有几次?
    都分别是什么时间?你怎样算出来的?(5分钟-15分钟)

     

    终结附加题:
    微软面试题,挑战你的智商
    ==========
    说明:如果你是第一次看到这种题,并且以前从来没有见过类似的题型,
    并且能够在半个小时之内做出答案,说明你的智力超常..)
    1.第一题 . 五个海盗抢到了100颗宝石,每一颗都一样大小和价值连城。他们决定这么分: 
    抽签决定自己的号码(1、2、3、4、5) 
                              
    首先,由1号提出分配方案,然后大家表决,当且仅当超过半数的人同意时,
    按照他的方案进行分配,否则将被扔进大海喂鲨鱼 
    如果1号死后,再由2号提出分配方案,然后剩下的4人进行表决,
    当且仅当超过半数的人同意时,按照他的方案进行分配,否则将被扔入大海喂鲨鱼。

    依此类推 
    条件:每个海盗都是很聪明的人,都能很理智地做出判断,从而做出选择。
    问题:第一个海盗提出怎样的分配方案才能使自己的收益最大化?

     

    2.一道关于飞机加油的问题,已知: 
    每个飞机只有一个油箱,  
    飞机之间可以相互加油(注意是相互,没有加油机)  
    一箱油可供一架飞机绕地球飞半圈, 
    问题:
    为使至少一架飞机绕地球一圈回到起飞时的飞机场,至少需要出动几架飞机?
    (所有飞机从同一机场起飞,而且必须安全返回机场,不允许中途降落,中间没有飞机场) 
      //欢迎,关注另外不同的更精彩的100题V0.2版,和此V0.1版的答案等后续内容。

    完。

     

    此外,关于此100道面试题的所有一切详情,包括答案,资源下载,帖子维护,答案更新都请参考此文:横空出世,席卷Csdn [评微软等数据结构+算法面试100题]


     

    作者声明:
    本人July对以上所有任何内容和资料享有版权,转载请注明作者本人July及出处。
    向您的厚道致敬。谢谢。二零一零年十二月六日。 


    展开全文
  • 深入了解GCD:Part 1/2

    2015-03-10 16:30:33
    因为应用程序的并发处理是一件很棘手的事情,而且GCD的API是基于C语言编写的,它并不像Objective-C语言那样更容易理解。深入学习Grand Central Dispatch 分为两篇教程来学习。 这个两篇教程中,第一个教程解

    虽然 Grand Central Dispatch (简称GCD)这项技术已经出现很久,但并不是每个人都能很好的运用它并得到甜头。这个是也是能理解的;因为应用程序的并发处理是一件很棘手的事情,而且GCD的API是基于C语言编写的,它并不像Objective-C语言那样更容易理解。深入学习Grand Central Dispatch 分为两篇教程来学习。

    在这个两篇教程中,第一个教程解释下GCD是做什么的,以及展示一些GCD的基本功能。在第二篇教程中,你讲会学习到GCD提供的更高级的功能。

    Learn about concurrency in this Grand Central Dispatch in-depth tutorial series.

    Learn about concurrency in this Grand Central Dispatch in-depth tutorial series.

    什么是GCD?

    GCD是 libdispatch 的统称,而libdispatch 是苹果为了在多核硬件(如iOS、OS X)上提供处理并发代码的库。GCD具有如下优点:

    • GCD能帮助你分配繁重计算任务并且保持在后台运行,帮你提高App的响应速度
    • GCD帮你提供易用的并发模式,不仅仅是锁和线程,帮组你避免在开发并发程序时的bug
    • GCD具有在常见模式(如单例模式)以最原始的语句优化,使你的代码具有更高的效率

    本教程认为你对Block以及GCD有基本的了解,如果你对GCD不了解,请先学习:iOS上多线程和GCD入门教程 

     

    GCD术语

    想要理解 GCD ,你要先熟悉与线程和并发相关的几个概念。这两者都可能比较模糊和微妙,所以在开始学习 GCD 之前我们先简要地回顾一下它们。

    串行、并行 

    所谓串行并行描述是相对而言,串行是指在同一时间只执行一个任务,并行是指在同一个时间可能执行多个任务。

    虽然这些术语被广泛应用,本教程旨在让你假设一个任务为Objective-C的Block,如果不知道Block是什么,请参考 iOS 5如何使用Block 。事实上,你完全可以在GCD上使用函数指针,但是这个会比较困难。因此,Block是最佳选择,它让你更加容易理解。

    同步、异步

    在GCD中,同步异步是为了描述一个函数相对于该函数要求GCD执行完成的另一个任务。

    同步方法只在它完成它需要做的任务后才会返回。

    异步方法刚好和同步方法相反,它不会等待任务完成才返回,它会立即返回。所以异步不会阻塞当前线程执行另一个函数(任务)。

    需要注意的是:当你读到同步函数“阻塞(Block)”当前线程,或函数是一个“阻塞”函数或阻塞操作时,不要被搞糊涂了!动词“阻塞”描述了函数如何影响它所在的线程而与名词“代码块(Block)”没有关系。代码块描述了用 Objective-C 编写的一个匿名函数,它能定义一个任务并被提交到 GCD 。(这一段其实是在说:Block这个词语有两个意思 不要弄错了,根据具体场景来理解就好了。)

    临界区

    就是一段代码不能被并发执行,也就是,两个线程不能同时执行这段代码。这很常见,因为代码去操作一个共享资源,例如一个变量若能被并发进程访问,那么它很可能会变成你所想要的结果。

    竞态条件

    这种状况是指基于特定序列或时机的事件的软件系统以不受控制的方式运行的行为,例如程序的并发任务执行的确切顺序。竞态条件可导致无法预测的行为,而不能通过代码检查立即发现。

    死锁

    两个(有时更多)东西——在大多数情况下,是线程——所谓的死锁是指它们都卡住了,并等待对方完成或执行其它操作。第一个不能完成是因为它在等待第二个的完成。但第二个也不能完成,因为它在等待第一个的完成。

    线程安全

    线程安全的代码能在多线程或并发任务中被安全的调用,而不会导致任何问题(数据损坏,崩溃,等)。线程不安全的代码在某个时刻只能在一个上下文中运行。一个线程安全代码的例子是 NSDictionary。你可以在同一时间在多个线程中使用它而不会有问题。另一方面,NSMutableDictionary 就不是线程安全的,应该保证一次只能有一个线程访问它。

    上下文切换 

    一个上下文切换指当你在单个进程里切换执行不同的线程时存储与恢复执行状态的过程。这个过程在编写多任务应用时很普遍,但会带来一些额外的开销。

     

    并发执行 

    并发和并行通常被一起提到,所以值得花些时间解释它们之间的区别。

    并发代码的不同部分可以“同步”执行。然而,该怎样发生或是否发生都取决于系统。多核设备通过并行来同时执行多个线程;然而,为了使单核设备也能实现这一点,它们必须先运行一个线程,执行一个上下文切换,然后运行另一个线程或进程。这通常发生地足够快以致给我们并发执行地错觉,如下图所示:

    Concurrency_vs_Parallelism-1

    Concurrency_vs_Parallelism

    虽然你可以编写代码在 GCD 下并发执行,但 GCD 会决定有多少并行的需求。并行要求并发,但并发并不能保证并行。

    更深入的观点是并发实际上是关于构造。当你在脑海中用 GCD 编写代码,你组织你的代码来暴露能同时运行的多个工作片段,以及不能同时运行的那些。如果你想深入此主题,看看 this excellent talk by Rob Pike 。

     

    队列

     

    GCD提供了dispatch queues(调度队列)来执行代码段,这些队列以FIFO(先进先出)的方式来管理你用GCD提交的任务。这保证了你先提交的任务现执行,即第一个任务添加到队列中就第一个开始执行,第二个添加的任务将第二个执行,知道队列的最后一个任务。
    所有的调度队列(dispatch queues)自身都是现成安全的,你能通过多个线程来访问它们。当你了解调度队列是如何为你嗲吗的不同部分提供线程安全,那么GCD的优势就更加明显,要加强利用GCD的优势,正确使用调度类型和调度函数是很关键的一步。
    在本节中,将通过简单的例子来讲解两种由GCD提供的调度队列,并且知道如何使用调度函数添加任务到队列中。

    串行队列

    在串行队列中,同一时间队列中只有一个任务在执行,每个任务只有在前一个任务执行完成后才能开始执行。而且,你不知道在一个Block(任务)执行结束到下一个Block(任务)开始执行之间的这段时间时间是多长,如下图所示:

    Serial-Queue-480x272

    这些任务的执行时机完全是在GCD的控制之下;你能唯一保证的是:GCD一次只能执行一个任务以及它会按照你添加到队列中的先后顺序来执行任务。
    在串行队列中,不会有两个任务并发执行,因此不会出现临界区访问的风险;对于你添加的这些任务来说,就从竞态条件下保护了临界区。因此如果访问临界区的唯一方式是通过提交任务到任务调队队列中,那么你就不必担心访问临界区的安全问题了。

     

    并发队列

    在并发队列中,你唯一能保证的是,这些任务会按照被添加的顺序开始执行。但是任务可以以任何顺序完成,你不知道在执行下一个任务是从什么时候开始,或者说任意时刻有多个Block(任务)运行,这个完全是取决于GCD。
    下图展示一个任务计划的执行,GCD管理了四个任务的并发:

    687474703a2f2f63646e332e72617977656e6465726c6963682e636f6d2f77702d636f6e74656e742f75706c6f6164732f323031342f30312f436f6e63757272656e742d51756575652d343830783237322e706e67

    注意:Block 1,2和3都是立马开始运行,一个接着一个。在Block 0 开始后,Block 1 等待了好一会才开始执行。同样,Block 3 在Block 2 开始后才开始执行,但是在Block 2 完成之前完成。

    在什么时候执行Block完全是由GCD来决定,如果一个Block的执行时间与另外一个Block重叠,GCD就会决定是否讲另一个任务运行在不同的核上,除非那个核不能使用,否则GCD讲通过切换上下文方式将任务运行在另一个核上。
    有趣的是,GCD为你提供了至少5种特定的队列,可以根据你的需要来选择不同队列类型。

     队列类型

    首先,系统给你提供了一个叫做 主队列(main queue)的特殊队列,它和串行队列一样,在同一时间只能执行一个任务。然而,他能保证所有的任务都在主线程上执行,只有主线程是唯一一个被允许去刷新UI的线程。这个队列是用于给UIView发送消息或推送通知。
    系统也给你提供了几个并发线程。比如说:全局调度队列(Global Dispatch Queues)。目前全局队列有四种不同的优先级:后台(background)、低(low)、默认(default)和高(high)。你应该要明白,Apple的API也会使用这些队列,所以你添加的任何任务都不会是这些队列中唯一的任务。
    最后,你能创建自己的串行或并行队列。这意味着你至少拥有五个调度队列的完全使用权,这个五个队列是:主队列、四个全局调队队列以及你自己创建的队列。
    以上是调队队列的大框架。
    GCD的“艺术”可以归结为:选择合适的调度队列方法来提交你的任务。要体验到GCD的艺术最好的方式是实际动手跟着做下面的例子,在例子中我们会提出一些需要注意的地方(容易出错啊什么的)。


     

    入门

     


     

    由于本教程的目的是:优化和安全调用GCD来执行不同线程的代码,那么你讲从一个叫GoodlyPuff的项目开始,并且做到最后。
    GoodlyPuff 是一个没有优化、并非线程安全的App,它使用了Core Image框架中的人脸检测API来检测人脸上的眼睛。被检查的图片,从本地相册选取,或者预先设置好URL从互联网上下载。

    项目下载在这里

    项目下载完成后,解压到一个你认为方便的目录,用xcode编译运行,这个App看起来像这样:

    Workflow1
    主意:当你选择 Le Internet 操作来下载图片时,会有一个UIAlertView过早弹出。你将会在教程二重得到修复。

    GoodlyPuff值得注意的四个类:

    • PhotoCollectionViewController: 这个是App启动后的第一个View Controlller,它展示你所选图片的缩略图
    • PhotoDetailViewController: 它执行添加icon到图片眼睛上的逻辑,并用一个UIScrollView来显示结果。
    • Photo: 这个一个类组,他更具一个NSURL的实例,或者一个ALAsset的实例来实例化照片。这个类提供一个图像、缩略图以及从URL下载的状态。
    • PhotoManager: 管理所有的图片实例对象。

     

    使用 dispatch_sync 处理后台任务

     

    回到你下载的App中,你从相机胶卷中添加一些图片,或使用Le Internet下载一下。
    注意:当你按下 PhotoCollectionViewController 中的一个 UICollectionViewCell 到生成一个新的 PhotoDetailViewController 之间花了多久时间;你会注意到一个明显的滞后,特别是在比较慢的设备上查看很大的图。

    在重载 UIViewController 的 viewDidLoad 时容易加入太多杂波(too much clutter),这通常会引起视图控制器出现前更长的等待。如果可能,最好是卸下一些工作放到后台,如果它们不是绝对必须要运行在加载时间里。

    这听起来像是 dispatch_async 能做的事情!

    打开 PhotoDetailViewController 并用下面的实现替换 viewDidLoad :

    下面说明下上面代码的作用:

    1. 你首先将工作从主线程移到全局线程。因为这是一个 dispatch_async() ,Block 会被异步地提交,意味着调用线程地执行将会继续。这就使得 viewDidLoad 更早地在主线程完成,让加载过程感觉起来更加快速。同时,一个人脸检测过程会启动并将在稍后完成。
    2. 在这里,人脸检测过程完成,并生成了一个新的图像。既然你要使用此新图像更新你的 UIImageView ,那么你就添加一个新的 Block 到主线程。记住——你必须总是在主线程访问 UIKit 的类。
    3. 最后,你用 fadeInNewImage: 更新 UI ,它执行一个淡入过程切换到新的icon眼睛图像

    编译并运行你的应用;选择一个图像然后你会注意到视图控制器加载明显变快,新的icon眼睛稍微在之后就加上了。这给应用带来了不错的效果,和之前的显示差别巨大。

    进一步,如果你试着加载一个超大的图像,应用不会在加载视图控制器上“卡住”,这就使得应用具有很好伸缩性。

    正如之前提到的, dispatch_async 添加一个 Block 都队列就立即返回了。任务会在之后由 GCD 决定执行。当你需要在后台执行一个基于网络或 CPU 紧张的任务时就使用 dispatch_async ,这样就不会阻塞当前线程。

    下面是一个关于在 dispatch_async 上如何以及何时使用不同的队列类型的快速指导:

    • 自定义串行队列:当你想串行执行后台任务并追踪它时就是一个好选择。这消除了资源争用,因为你知道一次只有一个任务在执行。注意若你需要来自某个方法的数据,你必须内联另一个 Block 来找回它或考虑使用 dispatch_sync。
    • 主队列(串行):这是在一个并发队列上完成任务后更新 UI 的共同选择。要这样做,你将在一个 Block 内部编写另一个 Block 。以及,如果你在主队列调用 dispatch_async 到主队列,你能确保这个新任务将在当前方法完成后的某个时间执行。
    • 并发队列:这是在后台执行非 UI 工作的共同选择。

    使用 dispatch_after 延后任务

     

    稍微考虑一下应用的 UX(用户体验) 。是否用户第一次打开应用时会困惑于不知道做什么?你是这样吗?

    如果用户的 PhotoManager 里还没有任何照片,那么显示一个提示会是个好主意!然而,你同样要考虑用户的眼睛会如何在主屏幕上浏览:如果你太快的显示一个提示,他们的眼睛还徘徊在视图的其它部分上,他们很可能会错过它。

    显示提示之前延迟一秒钟就足够捕捉到用户的注意,他们此时已经第一次看过了应用。

    添加如下代码到到 PhotoCollectionViewController.m 中 showOrHideNavPrompt 的废止实现里:

    showOrHideNavPrompt 在 viewDidLoad 中执行,以及 UICollectionView 被重新加载的任何时候。按照注释数字顺序看看:
    1. 你声明了一个变量指定要延迟的时长。
    2. 然后等待 delayInSeconds 给定的时长,再异步地添加一个 Block 到主线程。

    编译并运行应用。应该有一个轻微地延迟,这有助于抓住用户的注意力并展示所要做的事情。

    dispatch_after 工作起来就像一个延迟版的 dispatch_async 。你依然不能控制实际的执行时间,且一旦 dispatch_after 返回也就不能再取消它。

    不知道何时适合使用 dispatch_after ?
    1. 自定义串行队列:在一个自定义串行队列上使用 dispatch_after 要小心。你最好坚持使用主队列。
    2. 主队列(串行):是使用 dispatch_after 的好选择;Xcode 提供了一个不错的自动完成模版。
    3. 并发队列:在并发队列上使用 dispatch_after 也要小心;你会这样做就比较罕见。还是在主队列做这些操作吧。

     

    让你的单例线程安全

    单例,不论喜欢还是讨厌,它们在 iOS 上的流行情况就像网上的猫。 :]

    一个常见的担忧是它们常常不是线程安全的。这个担忧十分合理,基于它们的用途:单例常常被多个控制器同时访问。

    单例的线程担忧范围从初始化开始,到信息的读和写。PhotoManager 类被实现为单例——它在目前的状态下就会被这些问题所困扰。要看看事情如何很快地失去控制,你将在单例实例上创建一个控制好的竞态条件。

    导航到 PhotoManager.m 并找到 sharedManager ;它看起来如下:

    当前状态下,代码相当简单;你创建了一个单例并初始化一个叫做 photosArray 的 NSMutableArray 属性。

    然而,if 条件分支不是线程安全的;如果你多次调用这个方法,有一个可能性是在某个线程(就叫它线程A)上进入 if 语句块并可能在 sharedPhotoManager 被分配内存前发生一个上下文切换。然后另一个线程(线程B)可能进入 if ,分配单例实例的内存,然后退出。

    当系统上下文切换回线程A,你会分配另外一个单例实例的内存,然后退出。在那个时间点,你有了两个单例的实例——很明显这不是你想要的(译者注:这还能叫单例吗?)!

    要强制这个(竞态)条件发生,替换 PhotoManager.m 中的 sharedManager 为下面的实现:

    上面的代码中你用 NSThread 的 sleepForTimeInterval: 类方法来强制发生一个上下文切换。

    打开 AppDelegate.m 并添加如下代码到 application:didFinishLaunchingWithOptions: 的最开始处:

    这里创建了多个异步并发调用来实例化单例,然后引发上面描述的竞态条件。

    编译并运行项目;查看控制台输出,你会看到多个单例被实例化,如下所示:

    4673_140428093939_1

    注意到这里有好几行显示着不同地址的单例实例。这明显违背了单例的目的,对吧?

    这个输出向你展示了临界区被执行多次,而它只应该执行一次。现在,固然是你自己强制这样的状况发生,但你可以想像一下这个状况会怎样在无意间发生。

    注意:基于其它你无法控制的系统事件,NSLog 的数量有时会显示多个。线程问题极其难以调试,因为它们往往难以重现。
    要纠正这个状况,实例化代码应该只执行一次,并阻塞其它实例在 if 条件的临界区运行。这刚好就是 dispatch_once 能做的事。

    在单例初始化方法中用 dispatch_once 取代 if 条件判断,如下所示:

    编译并运行你的应用;查看控制台输出,你会看到有且仅有一个单例的实例——这就是你对单例的期望!:]

    现在你已经明白了防止竞态条件的重要性,从 AppDelegate.m 中移除 dispatch_async 语句,并用下面的实现替换 PhotoManager 单例的初始化:

    dispatch_once() 以线程安全的方式执行且仅执行其代码块一次。试图访问临界区(即传递给 dispatch_once 的代码)的不同的线程会在临界区已有一个线程的情况下被阻塞,直到临界区完成为止。

    4673_140428094022_1

    需要记住的是,这只是让访问共享实例线程安全。它绝对没有让类本身线程安全。类中可能还有其它竞态条件,例如任何操纵内部数据的情况。这些需要用其它方式来保证线程安全,例如同步访问数据,你将在下面几个小节看到。

     

    处理读者与写者问题

    线程安全实例不是处理单例时的唯一问题。如果单例属性表示一个可变对象,那么你就需要考虑是否那个对象自身线程安全。

    如果问题中的这个对象是一个 Foundation 容器类,那么答案是——“很可能不安全”!Apple 维护一个有用且有些心寒的列表,众多的 Foundation 类都不是线程安全的。 NSMutableArray,已用于你的单例,正在那个列表里休息。

    虽然许多线程可以同时读取 NSMutableArray 的一个实例而不会产生问题,但当一个线程正在读取时让另外一个线程修改数组就是不安全的。你的单例在目前的状况下不能预防这种情况的发生。

    要分析这个问题,看看 PhotoManager.m 中的 addPhoto:,转载如下:

    这是一个写方法,它修改一个私有可变数组对象。

    现在看看 photos ,转载如下:

    这是所谓的读方法,它读取可变数组。它为调用者生成一个不可变的拷贝,防止调用者不当地改变数组,但这不能提供任何保护来对抗当一个线程调用读方法 photos 的同时另一个线程调用写方法 addPhoto: 。

    这就是软件开发中经典的读者写者问题。GCD 通过用 dispatch barriers 创建一个读者写者锁 提供了一个优雅的解决方案。

    Dispatch barriers 是一组函数,在并发队列上工作时扮演一个串行式的瓶颈。使用 GCD 的障碍(barrier)API 确保提交的 Block 在那个特定时间上是指定队列上唯一被执行的条目。这就意味着所有的先于调度障碍提交到队列的条目必能在这个 Block 执行前完成。

    当这个 Block 的时机到达,调度障碍执行这个 Block 并确保在那个时间里队列不会执行任何其它 Block 。一旦完成,队列就返回到它默认的实现状态。 GCD 提供了同步和异步两种障碍函数。

    下图显示了障碍函数对多个异步队列的影响:

    4673_140428094116_1

     

    注意到正常部分的操作就如同一个正常的并发队列。但当障碍执行时,它本质上就如同一个串行队列。也就是,障碍是唯一在执行的事物。在障碍完成后,队列回到一个正常并发队列的样子。

    下面是你何时会——和不会——使用障碍函数的情况:
    1. 自定义串行队列:一个很坏的选择;障碍不会有任何帮助,因为不管怎样,一个串行队列一次都只执行一个操作。
    2. 全局并发队列:要小心;这可能不是最好的主意,因为其它系统可能在使用队列而且你不能垄断它们只为你自己的目的。
    3. 自定义并发队列:这对于原子或临界区代码来说是极佳的选择。任何你在设置或实例化的需要线程安全的事物都是使用障碍的最佳候选。

    由于上面唯一像样的选择是自定义并发队列,你将创建一个你自己的队列去处理你的障碍函数并分开读和写函数。且这个并发队列将允许多个多操作同时进行。

    打开 PhotoManager.m,添加如下私有属性到类扩展中:

    找到 addPhoto: 并用下面的实现替换它:

    你新写的函数是这样工作的:
    1. 在执行下面所有的工作前检查是否有合法的相片。
    2. 添加写操作到你的自定义队列。当临界区在稍后执行时,这将是你队列中唯一执行的条目。
    3. 这是添加对象到数组的实际代码。由于它是一个障碍 Block ,这个 Block 永远不会同时和其它 Block 一起在 concurrentPhotoQueue 中执行。
    4. 最后你发送一个通知说明完成了添加图片。这个通知将在主线程被发送因为它将会做一些 UI 工作,所以在此为了通知,你异步地调度另一个任务到主线程。
    这就处理了写操作,但你还需要实现 photos 读方法并实例化 concurrentPhotoQueue 。

    在写者打扰的情况下,要确保线程安全,你需要在 concurrentPhotoQueue 队列上执行读操作。既然你需要从函数返回,你就不能异步调度到队列,因为那样在读者函数返回之前不一定运行。

    在这种情况下,dispatch_sync 就是一个绝好的候选。

    dispatch_sync() 同步地提交工作并在返回前等待它完成。使用 dispatch_sync 跟踪你的调度障碍工作,或者当你需要等待操作完成后才能使用 Block 处理过的数据。如果你使用第二种情况做事,你将不时看到一个 __block 变量写在 dispatch_sync 范围之外,以便返回时在 dispatch_sync 使用处理过的对象。

    但你需要很小心。想像如果你调用 dispatch_sync 并放在你已运行着的当前队列。这会导致死锁,因为调用会一直等待直到 Block 完成,但 Block 不能完成(它甚至不会开始!),直到当前已经存在的任务完成,而当前任务无法完成!这将迫使你自觉于你正从哪个队列调用——以及你正在传递进入哪个队列。

    下面是一个快速总览,关于在何时以及何处使用 dispatch_sync :
    1. 自定义串行队列:在这个状况下要非常小心!如果你正运行在一个队列并调用 dispatch_sync 放在同一个队列,那你就百分百地创建了一个死锁。
    2. 主队列(串行):同上面的理由一样,必须非常小心!这个状况同样有潜在的导致死锁的情况。
    3. 并发队列:这才是做同步工作的好选择,不论是通过调度障碍,或者需要等待一个任务完成才能执行进一步处理的情况。

    继续在 PhotoManager.m 上工作,用下面的实现替换 photos :

    这就是你的读函数。按顺序看看编过号的注释,有这些:
    1. __block 关键字允许对象在 Block 内可变。没有它,array 在 Block 内部就只是只读的,你的代码甚至不能通过编译。
    2. 在 concurrentPhotoQueue 上同步调度来执行读操作。
    3. 将相片数组存储在 array 内并返回它。

    最后,你需要实例化你的 concurrentPhotoQueue 属性。修改 sharedManager 以便像下面这样初始化队列:

    这里使用 dispatch_queue_create 初始化 concurrentPhotoQueue 为一个并发队列。第一个参数是反向DNS样式命名惯例;确保它是描述性的,将有助于调试。第二个参数指定你的队列是串行还是并发。

    注意:当你在网上搜索例子时,你会经常看人们传递 0 或者 NULL 给 dispatch_queue_create 的第二个参数。这是一个创建串行队列的过时方式;明确你的参数总是更好。
    恭喜——你的 PhotoManager 单例现在是线程安全的了。不论你在何处或怎样读或写你的照片,你都有这样的自信,即它将以安全的方式完成,不会出现任何惊吓。

    A Visual Review of Queueing 队列的虚拟回顾

    依然没有 100% 地掌握 GCD 的要领?确保你可以使用 GCD 函数轻松地创建简单的例子,使用断点和 NSLog 语句保证自己明白当下发生的情况。

    我在下面提供了两个 GIF动画来帮助你巩固对 dispatch_async 和 dispatch_sync 的理解。包含在每个 GIF 中的代码可以提供视觉辅助;仔细注意 GIF 左边显示代码断点的每一步,以及右边相关队列的状态。

    dispatch_sync 回顾

    4673_140428094354_1

    下面是图中几个步骤的说明:
    1. 主队列一路按顺序执行任务——接着是一个实例化 UIViewController 的任务,其中包含了 viewDidLoad 。
    2. viewDidLoad 在主线程执行。
    3. 主线程目前在 viewDidLoad 内,正要到达 dispatch_sync 。
    4. dispatch_sync Block 被添加到一个全局队列中,将在稍后执行。进程将在主线程挂起直到该 Block 完成。同时,全局队列并发处理任务;要记得 Block 在全局队列中将按照 FIFO 顺序出列,但可以并发执行。
    5. 全局队列处理 dispatch_sync Block 加入之前已经出现在队列中的任务。
    6. 终于,轮到 dispatch_sync Block 。
    7. 这个 Block 完成,因此主线程上的任务可以恢复。
    8. viewDidLoad 方法完成,主队列继续处理其他任务。

    dispatch_sync 添加任务到一个队列并等待直到任务完成。dispatch_async 做类似的事情,但不同之处是它不会等待任务的完成,而是立即继续“调用线程”的其它任务。

    dispatch_async 回顾

    4673_140428094507_1

     

     

     

    1.主队列一路按顺序执行任务——接着是一个实例化 UIViewController 的任务,其中包含了 viewDidLoad 。
    2. viewDidLoad 在主线程执行。
    3.主线程目前在 viewDidLoad 内,正要到达 dispatch_async 。
    4.dispatch_async Block 被添加到一个全局队列中,将在稍后执行。
    5.viewDidLoad 在添加 dispatch_async 到全局队列后继续进行,主线程把注意力转向剩下的任务。同时,全局队列并发地处理它未完成地任务。记住 Block 在全局队列中将按照 FIFO 顺序出列,但可以并发执行。
    6.添加到 dispatch_async 的代码块开始执行。
    7.dispatch_async Block 完成,两个 NSLog 语句将它们的输出放在控制台上。

    在这个特定的实例中,第二个 NSLog 语句执行,跟着是第一个 NSLog 语句。并不总是这样——着取决于给定时刻硬件正在做的事情,而且你无法控制或知晓哪个语句会先执行。“第一个” NSLog 在某些调用情况下会第一个执行。

    下一步怎么走?
    在本教程中,你学习了如何让你的代码线程安全,以及在执行 CPU 密集型任务时如何保持主线程的响应性。

    你可以下载 GooglyPuff 项目,它包含了目前所有本教程中编写的实现。在本教程的第二部分,你将继续改进这个项目。

    如果你计划优化你自己的应用,那你应该用 Instruments 中的 Time Profile 模版分析你的工作。对这个工具的使用超出了本教程的范围,你可以看看 如何使用Instruments 来得到一个很好的概述。

    同时请确保在真实设备上分析,而在模拟器上测试会对程序速度产生非常不准确的印象。

    在教程的下一部分,你将更加深入到 GCD 的 API 中,做一些更 Cool 的东西。

    展开全文
  • 我们可以将接收到的数据存储一个全局队列中,然后另外的程序流程中将数据从同一个全局队列中取出来,经过一定的处理之后将消息发送到另外的模块。这样做可以降低程序的性能瓶颈。 本文用实际的C代码示例了...

    概述
    最近有在校的学生朋友在问我,数据结构中的队列在实际的软件开发项目中有什么样的用处。

    大家都知道,队列的特点是先入先出,即数据是按照入队列的顺序出队列的。在实际的软件开发项目中,当一个中间模块需要接收和发送大量的消息时,队列就可以大展身手了。我们可以将接收到的数据存储在一个全局队列中,然后在另外的程序流程中将数据从同一个全局队列中取出来,经过一定的处理之后将消息发送到另外的模块。这样做可以降低程序的性能瓶颈。

    本文用实际的C代码示例了简单的数据入队列和出队列的方法,大家可据此了解队列的实际用法,也可参照来实现更加复杂的队列操作。

    C代码

    /**********************************************************************
    * 版权所有 (C)2016, Zhou Zhaoxiong
    *
    * 文件名称:QueueUse.c
    * 文件标识:无
    * 内容摘要:示例队列的使用(入队和出队)
    * 其它说明:无
    * 当前版本:V1.0
    * 作    者:Zhou Zhaoxiong
    * 完成日期:20160811
    *
    **********************************************************************/
    #include <stdio.h>
    #include <string.h>
    #include <ftw.h>
    #include <pthread.h>
    #include <time.h>
    
    
    // 重定义数据类型
    typedef signed   int        INT32;
    typedef unsigned int        UINT32;
    typedef unsigned char       UINT8;
    
    // 宏定义
    #define     MAX_QUEUE      10000          // 最大队列元素个数
    
    // 结构体变量
    typedef struct
    {
        UINT32 iID;             // 编号
        UINT8  szInfo[100];     // 描述
    } T_StructInfo;
    
    // 全局变量定义
    T_StructInfo g_tQueue[MAX_QUEUE] = {0};      // 队列结构体
    UINT32 g_iQueueHead = 0;                     // 队列头部索引
    UINT32 g_iQueueTail = 0;                     // 队列尾部索引
    pthread_mutex_t     g_mutex_queue_cs;        // 互斥信号量
    pthread_cond_t      queue_cv;
    pthread_mutexattr_t g_MutexAttr;
    
    // 函数声明
    void PutDataIntoQueue(void);
    void GetDataFromQueue(void);
    INT32 EnQueue(T_StructInfo tQueueData);
    INT32 DeQueue(T_StructInfo *ptStructData);
    void Sleep(UINT32 iCountMs);
    
    
    /****************************************************************
    * 功能描述: 主函数
    * 输入参数: 无
    * 输出参数: 无
    * 返 回 值: 0-执行完成
    * 其他说明: 无
    * 修改日期       版本号        修改人        修改内容
    * -------------------------------------------------------------
    * 20160811        V1.0     Zhou Zhaoxiong     创建
    ****************************************************************/
    INT32 main(void)
    {
        pthread_mutex_init(&g_mutex_queue_cs, &g_MutexAttr);
        pthread_cond_init(&queue_cv, NULL);
    
    
        // 在循环中执行入队和出队操作
        while (1)
        {
            PutDataIntoQueue();  // 数据入队
    
    
            Sleep(5 * 1000);     // 间隔5秒
    
    
            GetDataFromQueue();  // 数据出队
    
    
            Sleep(60 * 1000);    // 每一分钟执行一次出队和入队
        }
    
    
        return 0;
    }
    
    
    
    
    /****************************************************************
    * 功能描述: 将数据加入队列中
    * 输入参数: 无
    * 输出参数: 无
    * 返 回 值: 0-成功   -1-失败
    * 其他说明: 无
    * 修改日期       版本号        修改人        修改内容
    * -------------------------------------------------------------
    * 20160811        V1.0     Zhou Zhaoxiong     创建
    ****************************************************************/
    void PutDataIntoQueue(void)
    {
        T_StructInfo tQueueData = {0};
        static UINT32 iCountNum = 0;
    
    
        // 对结构体的变量进行赋值
        tQueueData.iID = iCountNum;
        snprintf(tQueueData.szInfo, sizeof(tQueueData.szInfo) - 1, "zhou%d", iCountNum);
    
    
        // 计数值累加
        iCountNum ++;
        if (iCountNum >= MAX_QUEUE-1)
        {
            iCountNum = 0;
        }
    
    
        // 将数据加入队列(一直等到加入成功之后才退出)
        while (EnQueue(tQueueData) == -1)
        {
            Sleep(1000);       // 加入失败,1秒后重试
        }
    
    
        // 打印加入的数据
        printf("PutDataIntoQueue: ID=%d, Info=%s\n", tQueueData.iID, tQueueData.szInfo);
    }
    
    
    
    
    /****************************************************************
    * 功能描述: 将数据取出队列中
    * 输入参数: 无
    * 输出参数: 无
    * 返 回 值: 0-成功   -1-失败
    * 其他说明: 无
    * 修改日期       版本号        修改人        修改内容
    * -------------------------------------------------------------
    * 20160811        V1.0     Zhou Zhaoxiong     创建
    ****************************************************************/
    void GetDataFromQueue(void)
    {
        T_StructInfo tQueueData = {0};
    
    
        if (DeQueue(&tQueueData) == -1)
        {
            return;
        }
    
    
        // 打印取出的数据
        printf("GetDataFromQueue: ID=%d, Info=%s\n", tQueueData.iID, tQueueData.szInfo);
    }
    
    
    
    
    /****************************************************************
    * 功能描述: 数据入队列
    * 输入参数: tQueueData-队列数据
    * 输出参数: 无
    * 返 回 值: 0-成功   -1-失败
    * 其他说明: 无
    * 修改日期       版本号        修改人        修改内容
    * -------------------------------------------------------------
    * 20160811        V1.0     Zhou Zhaoxiong     创建
    ****************************************************************/
    INT32 EnQueue(T_StructInfo tQueueData)
    {
        INT32  iRetVal  = 0;
        UINT32 iNextPos = 0;
    
    
        pthread_mutex_lock(&g_mutex_queue_cs);
        iNextPos = g_iQueueTail + 1;
    
    
        if (iNextPos >= MAX_QUEUE)
        {
            iNextPos = 0;
        }
    
    
        if (iNextPos == g_iQueueHead)
        {
            iRetVal = -1;   // 已达到队列的最大长度
        }
        else
        {
            // 入队列
            memset(&g_tQueue[g_iQueueTail], 0x00,  sizeof(T_StructInfo));
            memcpy(&g_tQueue[g_iQueueTail], &tQueueData, sizeof(T_StructInfo));
    
    
            g_iQueueTail = iNextPos;
        }
    
    
        pthread_cond_signal(&queue_cv);
        pthread_mutex_unlock(&g_mutex_queue_cs);
    
    
        return iRetVal;
    }
    
    
    
    
    /****************************************************************
    * 功能描述: 数据出队列
    * 输入参数: ptStructData-队列数据
    * 输出参数: 无
    * 返 回 值: 0-成功   -1-失败
    * 其他说明: 无
    * 修改日期       版本号        修改人        修改内容
    * -------------------------------------------------------------
    * 20160811        V1.0     Zhou Zhaoxiong     创建
    ****************************************************************/
    INT32 DeQueue(T_StructInfo *ptStructData)
    {
        T_StructInfo tQueueData = {0};
    
    
        if (ptStructData == NULL)
        {
            return -1;
        }
    
    
        pthread_mutex_lock(&g_mutex_queue_cs);
    
    
        while (g_iQueueHead == g_iQueueTail)
        {
            pthread_cond_wait(&queue_cv, &g_mutex_queue_cs);
        }
    
    
        memset(&tQueueData, 0x00, sizeof(T_StructInfo));
        memcpy(&tQueueData, &g_tQueue[g_iQueueHead], sizeof(T_StructInfo));
        g_iQueueHead ++;
    
    
        if (g_iQueueHead >= MAX_QUEUE)
        {
            g_iQueueHead = 0;
        }
    
    
        pthread_mutex_unlock(&g_mutex_queue_cs);
        memcpy(ptStructData, &tQueueData, sizeof(T_StructInfo));
    
    
        return 0;
    }
    
    
    
    
    /**********************************************************************
    * 功能描述: 程序休眠
    * 输入参数: iCountMs-休眠时间(单位:ms)
    * 输出参数: 无
    * 返 回 值: 无
    * 其它说明: 无
    * 修改日期      版本号       修改人        修改内容
    * ------------------------------------------------------------------
    * 20160811       V1.0     Zhou Zhaoxiong     创建
    ********************************************************************/ 
    void Sleep(UINT32 iCountMs)
    {
        struct timeval t_timeout = {0};
    
    
        if (iCountMs < 1000)
        {
            t_timeout.tv_sec  = 0;
            t_timeout.tv_usec = iCountMs * 1000;
        }
        else
        {
            t_timeout.tv_sec  = iCountMs / 1000;
            t_timeout.tv_usec = (iCountMs % 1000) * 1000;
        }
        select(0, NULL, NULL, NULL, &t_timeout);    // 调用select函数阻塞程序
    }

    程序运行情况
    我们将上面编写好的QueueUse.c文件上传到Linux机器上,使用“gcc -g -o QueueUseQueueUse.c”命令编译之后,生成QueueUse文件。之后,执行“QueueUse”命令,即可看到程序的运行结果(结果会不断地更新)如下:

    ~/zhouzx/Test/QueueUse> QueueUse
    PutDataIntoQueue: ID=0, Info=zhou0
    GetDataFromQueue: ID=0, Info=zhou0
    PutDataIntoQueue: ID=1, Info=zhou1
    GetDataFromQueue: ID=1, Info=zhou1
    PutDataIntoQueue: ID=2, Info=zhou2
    GetDataFromQueue: ID=2, Info=zhou2
    PutDataIntoQueue: ID=3, Info=zhou3
    GetDataFromQueue: ID=3, Info=zhou3

    我们看到,数据先是被加入到队列中,然后再从队列中取出来。

    程序说明
    第一,在本程序中,入队列和出队列是在同一个函数中完成的,但是,在实际开发项目的程序中,入队列和出队列一般是在不同的程序流程(两个不同的线程)中完成的。

    第二,本程序的数据入队列操作是在EnQueue函数中完成的,数据出队列操作是在DeQueue函数中完成的,全局变量g_tQueue用于存放需要处理的数据。

    第三,在实际开发项目的程序中,有可能会有很多流程都会调用入队列和出队列的函数,为了防止多个流程同时向队列中加入数据或取出数据,在EnQueue和DeQueue函数中使用了锁操作。也就是说,在操作数据之前,先用pthread_mutex_lock函数执行加锁操作,在处理完数据之后,再用pthread_mutex_unlock函数执行解锁操作。

    第四,在实际开发项目中,为了防止程序从队列中取数据的速率过快而使得下游模块处理不过来,我们常在从队列取出数据之后发消息的流程中控制数据的发送速率,具体每秒钟发送多少条可在配置文件中设置。

    展开全文
  • 1 简介 公路使用过程中会受到各种... 本文数字图像处理技术的基础上对路面裂缝图像检测识别系统进行了研究。主要工作和结论如下: 1.本文首先分析了公路路面裂缝检测系统的结构、各种模块的选择以及工作原理,从硬

    1 简介

    公路在使用过程中会受到各种车辆的反复磨损以及各种其他因素影响,最终路面就会出现严重影响公路正常运行的破损。现行的主要路面破损检测方式是人工检测,这种检测方式不仅耗费大量的人力物力,而且速度极慢,严重影响了道路的检测维护进程。这些路面破损中主要以裂缝的形式表现,所以开发一套路面裂缝自动检测图像识别系统具有重要的理论意义和使用价值。 本文在数字图像处理技术的基础上对路面裂缝图像检测识别系统进行了研究。主要工作和结论如下: 1.本文首先分析了公路路面裂缝检测系统的结构、各种模块的选择以及工作原理,从硬件到软件设计了路面裂缝检测系统。硬件设备主要由检测装置平台、图像采集系统、图像处理系统、供电系统、照明系统组成。软件部分则是基于Matlab GUI的路面裂缝图像处理系统。并且经过多次实际路面裂缝检测试验,成功的验证了检测系统的设计思想和硬件选择的正确性。 2.依据公路路面裂缝图像数据的特点对裂缝进行了图像的增强平滑处理,然后此基础之使用6种边缘检测算子对路面裂缝特征进行了裂缝提取,进而在此基础上提出了8方向Sobel检测算子,并验证了8方向Sobel检测算法在对去除图像噪声改善路面裂缝图像质量方面有明显的效果。 3.应用了腐蚀、膨胀、细化等数学形态学处理方法对路面裂缝图像进行了处理,然后利用阈值判别法分辨出了线性裂缝和网状裂缝,在此基础上又利用投影法分辨出了横向裂缝和纵向裂缝,最后根据分类后的情况计算了网状裂缝的外接面积以及横向裂缝与纵向裂缝的长度,经验证对裂缝类型的判断准确率率可达到80%左右。​

    2 部分代码

    function varargout = Gui_Main(varargin)
    % GUI_MAIN M-file for Gui_Main.fig
    %     GUI_MAIN, by itself, creates a new GUI_MAIN or raises the existing
    %     singleton*.
    %
    %     H = GUI_MAIN returns the handle to a new GUI_MAIN or the handle to
    %     the existing singleton*.
    %
    %     GUI_MAIN('CALLBACK',hObject,eventData,handles,...) calls the local
    %     function named CALLBACK in GUI_MAIN.M with the given input arguments.
    %
    %     GUI_MAIN('Property','Value',...) creates a new GUI_MAIN or raises the
    %     existing singleton*. Starting from the left, property value pairs are
    %     applied to the GUI before Gui_Main_OpeningFcn gets called. An
    %     unrecognized property name or invalid value makes property application
    %     stop. All inputs are passed to Gui_Main_OpeningFcn via varargin.
    %
    %     *See GUI Options on GUIDE's Tools menu. Choose "GUI allows only one
    %     instance to run (singleton)".
    %
    % See also: GUIDE, GUIDATA, GUIHANDLES
    
    % Edit the above text to modify the response to help Gui_Main
    
    % Last Modified by GUIDE v2.5 29-Mar-2011 22:28:58
    
    % Begin initialization code - DO NOT EDIT
    gui_Singleton = 1;
    gui_State = struct('gui_Name',       mfilename, ...
       'gui_Singleton',  gui_Singleton, ...
       'gui_OpeningFcn', @Gui_Main_OpeningFcn, ...
       'gui_OutputFcn',  @Gui_Main_OutputFcn, ...
       'gui_LayoutFcn', [] , ...
       'gui_Callback',   []);
    if nargin && ischar(varargin{1})
       gui_State.gui_Callback = str2func(varargin{1});
    end
    
    if nargout
      [varargout{1:nargout}] = gui_mainfcn(gui_State, varargin{:});
    else
       gui_mainfcn(gui_State, varargin{:});
    end
    % End initialization code - DO NOT EDIT
    
    
    % --- Executes just before Gui_Main is made visible.
    function Gui_Main_OpeningFcn(hObject, eventdata, handles, varargin)
    % This function has no output args, see OutputFcn.
    % hObject   handle to figure
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    % varargin   command line arguments to Gui_Main (see VARARGIN)
    
    % Choose default command line output for Gui_Main
    handles.output = hObject;
    handles.Result = [];%定义结果变量
    handles.File = [];%定义文件路径变量
    % Update handles structure
    guidata(hObject, handles);%传递参数
    clc; warning off all;%清除命令行,警告
    InitAxes(handles);%初始化坐标轴
    
    % UIWAIT makes Gui_Main wait for user response (see UIRESUME)
    % uiwait(handles.figure1);
    
    
    % --- Outputs from this function are returned to the command line.
    function varargout = Gui_Main_OutputFcn(hObject, eventdata, handles)
    % varargout cell array for returning output args (see VARARGOUT);
    % hObject   handle to figure
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    
    % Get default command line output from handles structure
    varargout{1} = handles.output;
    
    
    % --- Executes on button press in pushbuttonOpenFile.
    function pushbuttonOpenFile_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonOpenFile (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    [filename, pathname] = uigetfile({'*.jpg;*.tif;*.png;*.gif;*.bmp','All Image Files';...
       '*.*','All Files' },'载入图像',...
       fullfile(pwd, 'images'));%选择打开文件
    if isequal(filename, 0) || isequal(pathname, 0)
       return;%如果文件没选中,重新选择
    end
    I = imread(fullfile(pathname, filename));%读取图像
    Result = Process_Main(I);%进行图像处理
    handles.File = fullfile(pathname, filename);%保存路径
    handles.Result = Result;%保存结果
    guidata(hObject, handles);%传递数据
    InitAxes(handles)%初始化坐标轴
    axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
    
    
    % --- Executes on button press in pushbuttonHisteq.
    function pushbuttonHisteq_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonHisteq (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');
       axes(handles.axes2); imshow(handles.Result.hist); title('直方图均衡化图像');%图像显示
    end
    
    
    
    % --- Executes on button press in pushbuttonMedfilt.
    function pushbuttonMedfilt_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonMedfilt (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');
       axes(handles.axes2); imshow(handles.Result.Medfilt); title('中值滤波图像');%图像显示
    end
    
    
    % --- Executes on button press in pushbuttonBw.
    function pushbuttonBw_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonBw (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.Bw); title('二值图像');%图像显示
    end
    
    % --- Executes on button press in pushbuttonEnance.
    function pushbuttonEnance_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonEnance (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.Enance); title('增强图像');%图像显示
    end
    
    % --- Executes on button press in pushbuttonBwfilter.
    function pushbuttonBwfilter_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonBwfilter (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.Bw); title('二值图像');%图像显示
       axes(handles.axes3); imshow(handles.Result.BwFilter); title('二值图像滤波');%图像显示
    end
    
    % --- Executes on button press in pushbuttonCrackRec.
    function pushbuttonCrackRec_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonCrackRec (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.Bw); title('二值图像');%图像显示
       axes(handles.axes3); imshow(handles.Result.BwFilter); title('二值图像滤波');%图像显示
       axes(handles.axes4); imshow(handles.Result.CrackRec); title('裂缝识别');%图像显示
    end
    
    
    % --- Executes on button press in pushbuttonCrackJudge.
    function pushbuttonCrackJudge_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonCrackJudge (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.BwFilter); title('二值图像滤波');%图像显示
       axes(handles.axes3); imshow(handles.Result.CrackRec); title('裂缝识别');%图像显示
       axes(handles.axes4); imshow(handles.Result.CrackJudge); title('裂缝判断');%图像显示
    end
    
    % --- Executes on button press in pushbuttonCrackLoc.
    function pushbuttonCrackLoc_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonCrackLoc (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.CrackJudge); title('裂缝图像');%图像显示
       axes(handles.axes3); imshow(handles.Result.CrackJudge); title(handles.Result.str);%图像显示
       axes(handles.axes4); imshow(handles.Result.CrackJudge); title('裂缝标记图像');%图像显示
       hold on;
       rectangle('Position', handles.Result.rect, 'EdgeColor', 'g', 'LineWidth', 2);%标记矩形框
       hold off;
    end
    
    % --- Executes on button press in pushbuttonProject.
    function pushbuttonProject_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonProject (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');%图像显示
       axes(handles.axes2); imshow(handles.Result.CrackJudge); title('裂缝图像');%图像显示
       axes(handles.axes3); plot(1:size(handles.Result.Image, 1), handles.Result.Projectr);%画出行投影
       title('行投影');
       axes(handles.axes4); plot(1:size(handles.Result.Image, 2), handles.Result.Projectc);%画出列投影
       title('列投影');
    end
    
    
    % --- Executes on button press in pushbuttonClose.
    function pushbuttonClose_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonClose (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    choice = questdlg('确定退出?', ...
       '退出', ...
       '是','否','否');
    switch choice
       case '是'
           close;
       otherwise
           return;
    end
    
    
    
    % --- Executes on button press in pushbuttonSaveResult.
    function pushbuttonSaveResult_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonSaveResult (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    try
       if ~isempty(handles.File)
           raw = [];
           xlsfile = fullfile(pwd, 'Result/result.xls');
           if exist(xlsfile, 'file')
              [num, txt, raw] = xlsread(xlsfile);
           end
           
           F = [];
           F{1, 1} = '文件名';
           F{1, 2} = '阈值信息';
           F{1, 3} = '面积信息';
           F{1, 4} = '长度信息';
           F{1, 5} = '最大宽度信息';
           F{1, 6} = '最小宽度信息';
           F{1, 7} = '形状信息';
           
           F{2, 1} = handles.File;
           F{2, 2} = handles.Result.BwTh;
           F{2, 3} = handles.Result.BwArea;
           F{2, 4} = handles.Result.BwLength;
           F{2, 5} = handles.Result.BwWidthMax;
           F{2, 6} = max(handles.Result.BwWidthMin,0.01);
           F{2, 7} = handles.Result.str;
           
           F = [raw; F];
           xlswrite(xlsfile, F);
           
           msgbox('保存结果成功!', '信息提示框');
       end
    catch
       msgbox('保存结果失败,请检查程序!', '信息提示框');
    end
    
    
    % --- Executes on button press in pushbuttonBridge.
    function pushbuttonBridge_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonBridge (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.Result)
       axes(handles.axes1); imshow(handles.Result.Image); title('原图像');
       axes(handles.axes2); imshow(handles.Result.BwFilter); title('二值图像滤波');
       axes(handles.axes3); imshow(handles.Result.CrackJudge); title('裂缝判断');
       axes(handles.axes4); imshow(handles.Result.CrackBridge); title('裂缝拼接');
    end
    
    
    % --- Executes on button press in pushbuttonSaveImage.
    function pushbuttonSaveImage_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonSaveImage (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    [filename, pathname] = uiputfile({'*.jpg;*.tif;*.png;*.gif','All Image Files';...
       '*.*','All Files' },'Save Image',...
       fullfile(pwd, 'Result/result.png'));%选择图像保存路径
    if ~isequal(filename, 0)
       imwrite(handles.Result.BwEnd, fullfile(pathname, filename));%写出图像
       msgbox('保存图像成功!', '信息提示框');%提示框
    end
    
    
    % --- Executes on button press in pushbuttonDiplay.
    function pushbuttonDiplay_Callback(hObject, eventdata, handles)
    % hObject   handle to pushbuttonDiplay (see GCBO)
    % eventdata reserved - to be defined in a future version of MATLAB
    % handles   structure with handles and user data (see GUIDATA)
    if ~isempty(handles.File)%图像信息是否为空
       F = [];
       F{1} = sprintf('文件名:%s', handles.File);
       F{2} = sprintf('阈值信息%.2f', handles.Result.BwTh);
       F{3} = sprintf('面积信息%.2f', handles.Result.BwArea);
       F{4} = sprintf('长度信息%.2f', handles.Result.BwLength);
       F{5} = sprintf('最大宽度信息%.2f', handles.Result.BwWidthMax);
       F{6} = sprintf('最小宽度信息%.2f', max(handles.Result.BwWidthMin,0.01));
       F{7} = sprintf('形状信息%s', handles.Result.str);
       listdlg('PromptString', '参数显示:',...
           'Name', '参数信息', ...
           'ListSize', [300, 150], ...
           'SelectionMode','single',...
           'ListString', F);
    end
    

    3 仿真结果

    4 参考文献

    [1]董钦. 路面裂缝图像检测识别系统研究. (Doctoral dissertation, 华东交通大学).

    部分理论引用网络文献,若有侵权联系博主删除。

    5 MATLAB代码与数据下载地址

    见博客主页

    展开全文
  • 对于刚接触actor的我,第一感觉就像redis一样,每个actor就是一个redis 实例,都有自己消息队列,actor相互通信通过将消息发给对方,消息发送进对方的消息队列,等待对方线程处理。来看看我们之前做项目的痛点。 ...
  • 压缩包内含2张测试用的320x240大小的yuv格图片,用于测试YUV查看器能否正常打开。 RawViewer1.0是一款用于查看播放yuv文件的播放器,支持查看播放及几何变换,可水平镜像、垂直镜像、图像转置、图像缩放与旋转等。 ...
  • 图论基础知识与常见图处理算法

    千次阅读 2019-06-30 21:34:58
    1.图论应用广泛,例如地图中规划最短路线、搜索引擎中的网页链接(结点为网页)、电路板上元件之间的连接、商业交易中用连接表示现金和商品买卖方之间的转移、编译器使用图表示大型软件系统中各模块之间的关系等...
  • HIT 软件构造Lab1–过程...文章目录HIT 软件构造Lab1--过程分析1 实验目标概述2 实验环境配置3.1 Magic Squares3.1.1 isLegalMagicSquare()3.1.2 generateMagicSquare()3.2 Turtle Graphics3.2.1 Problem 1: Clon...
  • 比较两句话text1和text2之间是否有关联)、模型Flask部署 系统联调测试与部署 离线部分+在线部分:命名实体审核任务RNN模型、命名实体识别任务BiLSTM+CRF模型、BERT中文预训练+微调模型、werobot服务+flask 做命名...
  • 汇编语言#编写两个子程序,分别实现:1)使用选择法排序,按成绩从高到低的进行排序;2)分别统计学生某门课程成绩中各分数段的成绩的人数,并输出 选择排序(Selection sort)是一种简单直观的排序算法。它的工作...
  • 这个M行N列的队伍中,每个人对应一个坐标,从最左上角的(0,0)到右下角的(M-1,N-1)。这些人还会进行一次报数,报数顺序是按照类似蜗牛壳形状的顺时针方向由外圈像内圈报数,当报数的个位数为7且十位数为奇数的...
  • 目前,Tensorflow已被广泛应用于文本处理,语音识别和图像识别等多项机器学习和深度学习领域。 基础框架 分为三层:应用层、接口层和核心层 应用层 提供了机器学习相关的训练库、预测库和针对Python、C++和Java等...
  • 本文翻译自 http://www.raywenderlich.com/60749/grand-central-dispatch-in-depth-part-1 原作者:Derek Selander 译者:@nixzhu 虽然 GCD 已经出现过一段时间了,但不是每个人都明了其主要内容。这...
  • MySQL必知必会:No.1

    2020-07-29 10:30:09
    1、Q:如何将.sql文件加载到数据库中? 直接进入到需要存储表的数据库(例如yyn),用source .sql文件的路径;注意window中路径\t可能会有一些转义运算符,所以需要注意用"\"来解决这个问题。
  • 【软考-软件设计师】(七).数据结构 概述 数据结构关键还是得看自己学的怎么样。。。 稀疏矩阵 用代入法更快 不用计公式。。。。。。。。。 (比如:直接代入数据到选项中来排错,) 不过还是会算出公式才好,这才...
  • 简介: 虽然用 Java™ 语言编写的程序理论上是不会出现“内存泄漏”的,但是有时对象不再作为程序的逻辑状态的一部分之后仍然不被垃圾收集。本月,负责保障应用程序健康的工程师 Brian Goetz 探讨了无意识的...
  • 1.把二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6....
  • 2:(*.*, 0.0, *.*) 3:(*.*, 0.0, *.*) 4:(*.*, 0.0, *.*)   第24题(链表): 链表操作,单链表就地逆置,   第25题(字符串): 写一个函数,它的原形是int continumax(char *outputstr,char *intputstr) 功能: ...
  • 使用 MediaCodec 的关键一步是 configure, start 之前配置是必须的。以解码为例,并且直接解码到外部提供的 surface 上,所以输入的 surface 不为空。 configure(…) 提供给外部调用的 public 方法内部调用了...
  • 【C#进阶3-4】C#设计模式

    千次阅读 2020-05-19 10:00:41
    用途 在软件系统中,经常有这样一些特殊的类,必须保证它们系统中只存在一个实例,才能确保它们的逻辑正确性、以及良好的效率。 如何绕过常规的构造器,提供一种机制来保证一个类只有一个实例? 这应该是类设计者...
  • 条件变量(Condition Variable)8.6 条件变量(Condition Variables)——可利用临界区或SRWLock锁来实现 8.6.1 条件变量的使用 (1)条件变量机制就是为了简化 “生产者-消费者”问题而设计的一种线程同 ...poj3186 ...
  • 1. 统计字母的使用频率一、题目:统计字母的使用频率二、目的与...2.基本要求:1)要求用C语言编程,Visual C++环境下调试完成;2)要求按照程序功能分成几个功能模块来实现,各个功能模块分别使用函数来完成;3)...
  • 点击下方公众号「关注」和「星标」回复“1024”获取独家整理的学习资料!ZooKeeper 是什么?ZooKeeper 是一个开源的分布式协调服务。它是一个为分布式应用提供一致性服务的软件...
  • IOS:ASIHttpRequest学习2

    2014-07-24 16:46:00
    让简单的API完成复杂...新的版本中,还加入了Objective-C闭包Block的支持,让我们的代码更加轻简灵活。 下面就举例说明它的API用法。 发起一个同步请求 同步意为着线程阻塞,主线程中使用此方法会使应用
  • 1. Introduction(简介)(请读自行阅读) This document provides software architecture information, development environment information and optimization guidelines. 本文档提供了软件架构信息、开发环境信息和...
  • 【.Net MF深入研究】中断处理机制

    千次阅读 2009-05-04 17:13:00
    .Net Micro Framework的中断处理机制相对比较简单,不支持中断嵌套,中断优先级功能的实现由相关硬件提供支持,软件层面仅仅进行相关优先级的设定即可。下面以TI DM335开发板为例简单介绍一下相关技术细节(这里仅...
  • “数据结构”课程设计题目

    万次阅读 多人点赞 2016-09-09 18:38:24
    “数据结构”课程设计题目 1、城市链表 [问题描述] 将若干城市的信息,存入一个带头结点的单链表。结点中的城市信息包括:城市名,城市的位置坐标。要求能够利用城市名和位置坐标进行...由学生依据软件工程的测试
  • 算法1

    2019-09-24 10:33:23
    1.把二元查找树转变成排序的双向链表题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14/ \ / \4 8 12 16转换成双向链表4=6=8=10=12=14...
  • 原文 ...   ...代码文件注释变量常量整数浮点数布尔类型字符自定义函数块(block)指针异常处理枚举结构预处理 这么多内容?!亲!您能慢慢来吗~ O-C教官来了,训练马上开始!还没冲咖啡?

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,093
精华内容 837
关键字:

在所出列的:1,字处理软件,2