发表于 | 分类于 | 阅读次数:

Python是一门极其灵活和简洁的语言，但其执行效率并不理想，相反C/C++的写法相对来说就复杂多了，但是C/C++却有很好的执行效率。而Python提供了可扩展的底层API给编程人员，可以通过它编程实现功能后，给Python上层调用，这样就将Python的灵活性和C/C++的效率结合起来了~

一些比较有用的资料

http://web.mit.edu/people/amliu/vrut/python/ext/intro.html

http://www.ibm.com/developerworks/cn/linux/l-pythc/#icomments

https://docs.python.org/2/c-api/index.html

C/C++代码如何导出到Python

  1. 加入Python的头文件

    1
    #include <python2.7/Python.h>

  2. 导出方法表和模块

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    //定义模块的方法表，这边有两个例子函数
    //get_args(): 获取Python中的参数并在终端打印
    //isorder(): 判断一个Python的列表是否是升序排列的
    static PyMethodDef PyDemoMethods[] = {
        { "get_args", get_args, METH_VARARGS, "None."},
        { "isorder", isorder, METH_VARARGS, "None."},
        { NULL, NULL, 0, NULL }
    };

    //编译后会生成Python可以import的模块PyDemo
    PyMODINIT_FUNC initPyDemo(void)
    {
        PyObject *m = Py_InitModule("PyDemo", PyDemoMethods);
        if (m == NULL)
            return;
    }

编译和链接

C/C++ 的源码在Linux编译成.so文件给Python调用

g++ -shared -fpic pydemo.cpp -o PyDemo.so

在C/C++中获取并打印Python的参数

其中在C/C++中的函数都需要遵循这个函数原型进行扩展

1
static PyObject* get_args(PyObject *self, PyObject *args)

其中PyObject是Python中的对象，Python是一门完全面向对象的语言，它的所有对象在C语言中都是以PyObject结构体来表现的

参数args提供了一个变长参数表给C/C++语言

1
PyArg_ParseTuple(args, "ids", &i, &d, &s)

这行代码用来获取Python中的参数，”ids” 用来描述有三个参数，分别是整型(i)、双精度浮点数(d)和字符串(s)

其中C/C++语言的变量作为参数时需要加上取地址符&

对于字符串类型，在C/C++中声明一个指针就行了，不需要对其分配空间，因为在参数解析后其会指向原先运行时数据所在的内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static PyObject* get_args(PyObject *self, PyObject *args)
{
    int i;
    double d;
    char *s;
    if (!PyArg_ParseTuple(args, "ids", &i, &d, &s)){
    	return NULL;
    }
    cout << i << endl;
    cout << setiosflags(ios::fixed) << setprecision(2) << d << endl;
    cout << s << endl;
    Py_INCREF(Py_None);
    return Py_None;
}

判断一个Python列表是否升序

上面一个例子只是简单的获取参数并打印，现在看下如何对Pyhton中的List对象进行操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static PyObject* isorder(PyObject *self, PyObject *args)
{
    PyObject* pList = NULL;  //声明一个对象指针
    Py_ssize_t i;            //下标i需要用这个结构体进行定义

    if (!PyArg_ParseTuple(args, "O", &pList)){ //Python中的参数作为对象传入("O")
    	return NULL;
    }
    if (!PyList_Check(pList))
    	return NULL;

    //遍历列表比较相邻对象
    for (i = 1; i < PyList_Size(pList); i++){
    	if (PyObject_Compare(PyList_GetItem(pList, i-1), PyList_GetItem(pList, i)) != -1){
    		Py_INCREF(Py_False);
    		return Py_False;
        }
    }

    Py_INCREF(Py_True);
    return Py_True;
}

其中上面两个例子返回None和布尔对象时都用了Py_INCREF这个宏~

是Python内部对于这些对象有引用计数的机制，在使用这些对象进行返回时，就需要使用这个宏更新它的计数

六、在Python中调用:

1
2
3
4
5
import PyDemo
def test():
    print(PyDemo.get_args(1, 4.7, "hello"))
    l = [1,2,0,4]
    print(PyDemo.isorder(l))

发表于 | 分类于 | 阅读次数:

最近在写个爬虫程序，用到用到了标准库中的HTMLParser模块。

一、示例程序：

其实这个框架用起来非常简单：

在handle_starttag方法中编写代码对开始标记进行处理

在handle_endtag中编写代码对结束标记进行处理

在handle_data中编写代码对中间的数据进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from HTMLParser import HTMLParser
class DemoParser(HTMLParser):
    def reset(self):
    	HTMLParser.reset(self)

    def handle_starttag(self, tag, attrs):
    	print tag, attrs

    def handle_endtag(self, tag):
    	print tag

    def handle_data(self, data):
    	print data

def test():
    html = '''
        <a href="http://localhost/public_html"> Test </a>
        '''
    p = DemoParser()
    p.feed(html)

if __name__ == '__main__':
    test()

二、将页面解析成标签树：

这里说一下如何借助HTMLParser这个模块将网页解析成标签树的形式，实现的思路比较简单，就是创建一个节点类（HTMLNode)，记录标签(TAG)、属性(ATTRS)，数据(DATA)这些信息，更进一步地可以利用动态添加属性的机制，直接从ATTRS创建每个属性和相应的值

在节点类(HTMLNode)之中将树本身的相关的信息(孩子链表、深度、父节点等信息)定义成私有成员不允许外部直接访问，再实现相应的对树操作的方法，这样完成了对这个数据结构的封装。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class HTMLNode:
    def __init__(self, tag , attrs, data=None, root=None, depth=0):
    	# define children, depth, root as private.
    	self.__children = []
    	self.__depth = depth
    	# top node of a tree, set root refer to itself.
    	# otherwise, set root refer to it's parent.
    	if root == None:
    		self.__root = self
    	else:
    		self.__root = root
    	# define tag, attrs, data as public.
    	self.tag  = tag
    	self.attrs = attrs
    	self.data = data

    def lchild(self, i):
    	# index children list from left to right.
    	if len(self.__children) > 0:
    		return self.__children[i]

    def rchild(self, i):
    	# index children list from right to left.
    	if len(self.__children) > 0:
    		n = len(self.__children)
    		return self.__children[n-i-1]

    def add(self, node):
    	# add a node to children list.
    	node.__root = self
    	node.__depth = self.__depth + 1
    	self.__children.append(node)

    def parent(self):
    	return self.__root

    def num(self):
    	return len(self.__children)

    def depth(self):
    	return self.__depth

    def trvs(self, visit_in_func, visit_out_func=None):
    	visit_in_func(self)
    	for child in self.__children:
    		child.trvs(visit_in_func, visit_out_func)
    	if visit_out_func != None:
    		visit_out_func(self)
    	return

其中 trvs()方法递归去访问节点和节点的子树，这边传入了两个函数，一个在进入时调用，一个在退出前调用，对HTML进行处理的时候具体去实现这两个函数对这颗标签树进行访问。

写个一个简单的测试代码，用于以增加缩进量的形式格式化输出HTML代码便于阅读（不过这边没有对内容进行转码，转换后的HTML文件再打开就不对了，只能用来阅读它的结构）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# visit_in and visit_out function use to test.
def visit_in(n):
    if n.tag == None: return
    if n!=None:
    	print '%s<%s '%('    '*(n.depth()-1),n.tag),
    	for i in range(0, len(n.attrs)):
    		if i == len(n.attrs)-1:
    			print '%s=\"%s\">'%(n.attrs[i][0],n.attrs[i][1]),
    		else:
    			print '%s=\"%s\" '%(n.attrs[i][0],n.attrs[i][1]),
    	if n.data != None:
    		if n.tag == 'script':
    			repr_code_lines = n.data.split('\n')
    			for code_line in repr_code_lines:
    				print '\n%s%s'%('    '*(n.depth()), code_line),
    			print
    		else:
    			while n.data.find('  ')!=-1:
    				n.data = n.data.replace('  ',' ')
    			n.data = n.data.replace('\r\n', ' ')
    			n.data = n.data.replace('\n', ' ')
    			n.data = n.data.replace(' ', '')
    			n.data = n.data.replace('\t\t','\t')
    			n.data = n.data.replace('\t','')
    			if n.data != '':
    				print '\n%s%s'%('    '*(n.depth()),n.data)
    	if n.num() != 0:
    		if n.data == None:
    			print
    		elif n.data == '':
    			print

def visit_out(n):
    if n.tag == None: return
    if n.num() != 0 or n.data != None:
    	print '%s</%s>'%('    '*(n.depth()-1), n.tag)
    else:
    	print '</%s>'%(n.tag)

下面来看如何建立这棵树，算法比较简单，先创建一个根节点，然后定义一个pre对象保持始终引用当前节点的对象，如果遇到新的开始标记，就将该标记加入到孩子链表中，然后pre对象引用的是孩子链表中的最右边节点；如果遇到了结束标记，就将pre对象返回上层的父节点

编码的时候发现两个问题，一个是有一些标签可以不书写结束标记的，那么就需要特殊处理，否则会出错，我的解决方法时将这些标签定义成terminated(终结的)如果遇到这些标签时直接跳出返回上层节点；另一个是发现有些标签不匹配，这边是出现了多出了结束标记的情况，我的解决方法是用了个辅助堆栈进行检查，在处理结束标记时，先检查栈顶元素，如果栈顶元素作为开始标记不和当前结束标记匹配，就丢弃这个结束标记。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class HTMLTreeParser(HTMLParser):
    terminated = ( 'meta','link','br', 'img', 'input', 'frame', 'col', 
                    'hr', 'base','option', 'area','param')

    def reset(self):
    	HTMLParser.reset(self)
    	self.tree = HTMLNode(None,None)
    	self.pre = self.tree
    	self.stack = []
    	return

    '''
    def inc(self,key):
    	for i in range(0, len(self.count)):
    		if self.count[i][0] == key:
    			self.count[i][1] = self.count[i][1] + 1
    			return
    	self.count.append([key, 1])

    def dec(self, key):
    	for i in range(0, len(self.count)):
    		if self.count[i][0] == key:
    			self.count[i][1] = self.count[i][1] - 1
    			return
    	self.count.append([key, 0])
    '''

    def handle_starttag(self, tag, attrs):
    	self.pre.add(HTMLNode(tag,attrs))
    	self.pre = self.pre.rchild(0)
    	# some terminated tags have not endtag </xx>.
    	if tag in HTMLTreeParser.terminated:
    		self.pre = self.pre.parent()
    	else:
    		self.stack.append(tag)
    	return

    def handle_endtag(self, tag):
    	if tag in HTMLTreeParser.terminated:
    		return
    	else:
    		# use stack to check whether endtag match to starttag.
    		if len(self.stack) == 0 or self.stack[len(self.stack)-1] != tag:
    			return
    		else:
    			self.stack.pop()
    	self.pre = self.pre.parent()
    	return

    def handle_data(self, data):
    	self.pre.data = data
    	return

    def parse_html(self, html):
    	self.feed(html)
    	return self.tree

测试的时候编写代码打开有道词典的页面：

1
2
3
4
5
6
7
8
9
10
11
def test():
    params = {'keyfrom':'dict.index','q': 'test'}
    url = 'http://dict.youdao.com/search?'+urllib.urlencode(params)
    opener = urllib2.build_opener()
    opener.addheaders = [('User-Agent',
        'Mozilla/5.0 (X11; Ubuntu; Linux x86_64; rv:31/0) Gecko/20100101 Firefox/31.0')]
    f = opener.open(url)
    html=f.read()
    hp=HTMLTreeParser()
    T=hp.parse_html(html)
    T.trvs(visit_in, visit_out)

发表于 | 分类于 | 阅读次数:

简单说下Yacc部分的内容

预备知识： Lex部分的内容，编译原理的文法知识，先试着写上下文无关文法就好了

调试过程中写这两个函数：

  1. cat(P) 用来打印数据，这个不用多说，就是把 P[0] … P[n-1] 打印

  2. carry(P) 则是用来传递数据，很简单：P[0] = P[1] + … + P[n-1]，

注意到：

上面的相加只是是字符串连接的形式，目的是传递到左边的P[0]使得递归解析继续

也可以说这边的目的只是通过TOKEN字符串来看这个yacc解析器的工作过程，而不做具体的语法分析！

1
2
3
4
5
6
7
8
9
10
11
12
def cat(P):
    print(""" + P[0]) + """ ,(':'),
    for i in range(1,len(P)):
        print(P[i]),
    print

def carry(P):
    P[0] = ""
    for i in range(1, len(P)):
        P[0] = P[0] + P[i]
    cat(P)
    return P

后面写文法，首先Yacc会根据写好的文法生成一个Table，写的文法有问题这里就会报错如果只是写一个简单的上下文无关文法边注意下按照它去展开，必须是可终结的就可以正常解析了这边可终结的就是说展开后最末端的文法定义，就是我们在Lex里定义的Token那些东西

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
# 语句列表：
# 由一个语句列表加一条语句 or 单独一条语句
def p_statement_list(p):
    ''' statement_list : LBRACE statement_list RBRACE
                        | statement statement_list
                        | statement '''
    carry(p)

# 语句 : if语句 or 非if语句
def p_statement(p):
    ''' statement : if_else_statement
                  | noif_statement '''
    carry(p)
    return

# 非if语句：
# 赋值+分号 or 函数表达式+分号 or 分号
def p_noif_statement(p):
    ''' noif_statement : assignment SEMI
                        | func_expression SEMI
                        | SEMI '''
    carry(p)
    return

# 后面这一些是if结构文法，注意要使他无歧义，注释不写了…
def p_if_else_statement(p):
    ''' if_else_statement : matched
                          | unmached '''
    carry(p)

def p_statement_matched(p):
    ''' matched : IF LPAREN boolean_expression RPAREN matched ELSE matched
                | if_else_statement_clause'''
    carry(p)

def p_statement_unmached(p):
    ''' unmached : IF LPAREN boolean_expression RPAREN if_else_statement
                  | IF LPAREN boolean_expression RPAREN matched ELSE unmached '''
    carry(p)

def p_if_else_statement_clause(p):
    ''' if_else_statement_clause : noif_statement
                                  | LBRACE statement_list RBRACE '''
    carry(p)

# 赋值：标识符 (=, +=, –=, =, *=, %= ) 表达式
def p_statement_assignment(p):
    ''' assignment : identifier EQUALS expression
                    | identifier PLUSEQUAL expression
                    | identifier MINUSEQUAL expression
                    | identifier TIMESEQUAL expression
                    | identifier DIVEQUAL expression
                    | identifier MODEQUAL expression  '''
    carry(p)

# 表达式：(算术，布尔，函数) 表达式
def p_expression(p):
    ''' expression : math_expression
                    | boolean_expression
                    | func_expression '''
    carry(p)

# 数学表达式：这部分考虑运算符优先级顺序~
def p_math_expression(p):
    ''' math_expression : math_expression PLUS math_expression_term
                        | math_expression MINUS math_expression_term
                        | math_expression_term
                        '''
    carry(p)

def p_boolean_expression(p):
    ''' boolean_expression : TRUE '''
    carry(p)

# 多项式中的项：由因子的乘除运算组成 or 一个单独的因子
def p_math_expression_term(p):
    ''' math_expression_term : math_expression_term TIMES math_expression_factor
                              | math_expression_term DIVIDE math_expression_factor
                              | math_expression_term MODULO math_expression_factor
                              | math_expression_factor '''
    carry(p)

# 因子：变量 or 常量 or 函数表达式 or 括号因子(在算术表达式左右加括号)
def p_math_expression_factor(p):
    ''' math_expression_factor : identifier
                                | constant
                                | func_expression
                                | LPAREN math_expression RPAREN'''
    carry(p)

def p_func_expression(p):
    ''' func_expression : func_expression_term LPAREN argument_list RPAREN '''
    carry(p)

def p_func_expression_term(p):
    ''' func_expression_term : func_expression PERIOD identifier
                              | identifier '''
    carry(p)

def p_argument_list(p):
    ''' argument_list : argument_list COMMA argument_term
                      | argument_term '''
    carry(p)

def p_argument_term(p):
    ''' argument_term : func_expression
                      | math_expression
                      | assignment
                      | identifier
                      | constant '''
    carry(p)

def p_constant(p):
    '''constant : DECCONST
              | FLOATCONST
              | CHARCONST
              | STRINGCONST'''
    carry(p)

def p_identifier(p):
    ''' identifier : ID'''
    carry(p)

def p_empty(p):
    'empty : '
    pass

然后是Yacc的用法：

1
2
3
4
5
6
7
8
9
### test for yacc
def yacc_test():
    lx = lex.lex()
    fp = open(sys.argv[1])
    codes = fp.read()
    fp.close()
    parser = yacc.yacc(debug=True,debuglog=log)
    parser.parse(codes)
    return

发表于 | 分类于 | 阅读次数:

官方文档： http://www.dabeaz.com/ply/ply.html#ply_nn3

Lex: 一个词法分析器的生成器

完成一个从代码到LexToken流的转换

  1. 定义词法规则
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
tokens = keywords + [
        # Literals (identifier, integer constant, float constant, string constant, char const)
        'ID', 'DECCONST', 'HEXCONST', 'FLOATCONST', 'STRINGCONST', 'CHARCONST',

        # Operators (+,-,*,/,%,|,&,~,^,<<,>>, ||, &&, !, <, <=, >, >=, ==, !=)
        'PLUS', 'MINUS', 'TIMES', 'DIVIDE', 'MOD',
        'OR', 'AND', 'NOT', 'XOR', 'LSHIFT', 'RSHIFT',
        'LOR', 'LAND', 'LNOT',
        'LT', 'LE', 'GT', 'GE', 'EQ', 'NE',

        # Assignment (=, *=, /=, %=, +=, -=, <<=, >>=, &=, ^=, |=)
        'EQUALS', 'TIMESEQUAL', 'DIVEQUAL', 'MODEQUAL', 'PLUSEQUAL', 'MINUSEQUAL',
        'LSHIFTEQUAL','RSHIFTEQUAL', 'ANDEQUAL', 'XOREQUAL', 'OREQUAL',

        # Increment/decrement (++,--)
        'INCREMENT', 'DECREMENT', 'MODULO',

        # Structure dereference (->)
        'ARROW',

        # Ternary operator (?)
        'TERNARY',

        # Delimeters ( ) [ ] { } , . ; :
        'LPAREN', 'RPAREN',
        'LBRACKET', 'RBRACKET',
        'LBRACE', 'RBRACE',
        'COMMA', 'PERIOD', 'SEMI', 'COLON',

        'ANNOTATION',

        'CPPCOMMENT', 'COMMENT',
        # Ellipsis (...)
        'ELLIPSIS'
    ]

其中keywords是一个由保留字组成的一个集合，tokens则有keywords部门再加上词法规则对应的名称

  1. 定义规则

对于tokens里面的每个名称，使用例如 t_name = r”…” 的方式使用正则表达式进行定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# Integer literal
t_DECCONST = r'[\dA-Fa-f]+([uU]|[lL]|[uU][lL]|[lL][uU])?'
t_HEXCONST = r'(0[Xx])[\dA-Fa-f]+([uU]|[lL]|[uU][lL]|[lL][uU])?'

# Floating literal
t_FLOATCONST = r'((\d+)(\.\d+)(e(\+|-)?(\d+))? | (\d+)e(\+|-)?(\d+))([lL]|[fF])?'

# String literal
t_STRINGCONST = r'\"([^\\\n]|(\\.))*?\"'

# Character constant 'c' or L'c'
t_CHARCONST = r'(L)?\'([^\\\n]|(\\.))*?\''

# Identifiers, and map to keywords
def t_ID(t):
    r'[A-Za-z_][A-Za-z0-9_]*'  
    t.type = keywords_map.get(t.value, "ID")
    return t

# Comment (C-Style)
def t_COMMENT(t):
    r'/\*(.|\n)*?\*/'
    t.lexer.lineno += t.value.count('\n')
    return t

# Comment (C++-Style)
def t_CPPCOMMENT(t):
    r'//.*\n'
    t.lexer.lineno += 1
    return t

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")

def t_error(t):
    #print("Illegal character: '%s'" % t.value[0])
    t.lexer.skip(1)

有些需要特殊处理的部分用了def t_name() 这种函数来表示

比如:

在t_ID() 里面需要对标识符进行查找，来判断是否为保留字

在t_COMMENT() 里面需要跳过注释中的’\n’来加上相应的行号，使其以代码中的行号保持一致

另外有t_error() 来对词法错误进行处理…

测试代码:

1
2
3
4
5
6
7
8
9
10
def lex_test():
    lx = lex.lex()
    fp = open(sys.argv[1])
    codes = fp.read()
    fp.close()
    lx.input(codes)
    while True:
        tok = lx.token()
        if not tok: break
        print(tok)

可以看到打印出的Tokens流了

发表于 | 分类于 | 阅读次数:

共享内存就是允许两个或更多的进程可以访问一块共享的内存区域进行数据交换，是最快的IPC了。如果服务器端进程在共享内存区进行读写，就不允许客户端进程对共享内存进行访问了，这时候的IPC也就要对多个进程同步，使用信号量什么的来管理这一块共享区域了…

先来一个简单的应用：创建共享内存->映射共享内存 然后就可以进行读/写访问了…

头文件: sys/shm.h

用来创建共享内存的函数：

int shmget(key_t key,size_t size, int flag);

Returns: shared memory ID if OK, -1 on error.

如果成功则返回共享内存的ID

用来映射共享内存的函数：

void shmat(int shmid, const void addr, int flag);

Returns: pointer to shared memory segment if OK, -1 on error.

如果成功则返回一个指向共享内存区域的指针

下面是一个简单的例程，通过命令行读取一个文件，执行fork后先由子进程读取文件中数据并写入共享内存中，子进程退出后，父进程从共享内存中读取数据输出到标准输出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include "apue.h"
#include <sys/shm.h>
#include <fcntl.h>
#define ARRAY_SIZE      40000
#define MALLOC_SIZE     40000
#define SHM_SIZE        100000
#define SHM_MODE        0600
#define BUFFSIZE        128
char array[ARRAY_SIZE];
int main(int argc,char *argv[])
{
        int shmid;
        char *ptr,*shmptr;
        pid_t pid;
        char writebuf[BUFFSIZE],readbuf[BUFFSIZE];
        int i,j,n;
        int fd;
        char *p,*q;
        if (argc!=2)
        {
                perror("usage: a.out filename");
                exit(1);
        }
        printf("array[] from %lx to %lxn", (unsigned long)&array[0],
                (unsigned long)&array[ARRAY_SIZE]);
        printf("statck around %lxn", (unsigned long) &shmid);  
        /* 分配堆空间 */
        if ((ptr = malloc(MALLOC_SIZE))==NULL)
                perror("malloc error");
        printf("malloced from %lx to %lxn", (unsigned long)ptr,
                (unsigned long)ptr+MALLOC_SIZE);
        /* 创建共享内存 */
        if ((shmid=shmget(IPC_PRIVATE,SHM_SIZE,SHM_MODE))<0)
                perror("shmget error");
        /* 映射共享内存 */
        if ((shmptr=shmat(shmid,0,0))==(void *)-1)
                perror("shmat error");
        printf("shared memory attached from %lx to %lxn",
                (unsigned long)shmptr, (unsigned long)shmptr+SHM_SIZE);
        if ((pid=fork())<0)
        {
                perror("fork error");
        }
        else if (pid==0)        /* 子进程 */
        {
                /* 向共享内存写数据后退出 */
                printf("子进程向共享内存写数据...n");
                if ((fd=open(argv[1],O_RDWR,0))==-1)
                {
                        printf("不能打开文件:%sn",argv[1]);
                        exit(1);
                }
                p = shmptr;
                while ((n=read(fd,readbuf,BUFFSIZE))>0)
                {
                        for (i = 0; i < n; i++)
                                *p++=readbuf[i];
                }
                *p=-1;
                printf("子进程写数据完毕n");
                exit(0);
        }
        else    /* 父进程 */
        {
                if (waitpid(pid,NULL,0)!=pid)   /* 等子进程退出 */
                        perror("waitpid error");
                /* 从共享内存中读数据 */
                printf("父进程读取数据...n");  
                p = shmptr;
                while (*p!=EOF) printf("%c",*p++);
        }
        if (shmctl(shmid,IPC_RMID,0)<0) /* 移除共享内存 */
                perror("shmctl error");
        exit(0);
}

发表于 | 分类于 | 阅读次数:

Linux/Unix下管道通信仅限与父子进程和兄弟进程之间，另外一种是FIFO（First In First Out，先进先出) 也叫有名管道是可以令两个没有关系的进程进行通信的，其实编程时把FIFO就当成是一种特殊的文件来处理就行了，先进先出的一端读数据一端写数据想必是很清楚，还有就是它是不能lseek函数的。

一、创建FIFO文件的过程就类似创建文件的creat函数：

int mkfifo(const char *pathname, mode_t mode);

/ Returns: 0 if OK, -1 on error /

创建文件后，可以像打开普通文件一样使用open()函数打开FIFO文件，之后就可以使用read,write等函数来对这个文件进行操作了。

二、关于打开文件时候的 O_NONBLOCK (非阻塞)选项：

  1. 在正常情况下(默认没有设置O_NONBLOCK选项)，以只读模式打开FIFO，也就是读进程中打开一个FIFO文件时，如果没有其他进程向FIFO写数据，那么读进程在执行open函数中就开始阻塞，直到有其他进程打开了FIFO写数据时，读进程中的open函数才返回。

  2. 在设置了O_NONBLOCK选项的情况，读进程在打开FIFO文件时立刻从open函数中返回并且可以开始从FIFO中读数据的操作。但是如果在读进程还没有准备好读数据时一个写进程以只写模式打开一个FIFO文件时，open函数返回-1，并且errno置为ENXIO。

编程的时候就是先让读进程准备好从FIFO读取数据，然后写进程再朝FIFO写数据就行了。

fifo_read.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <fcntl.h>
#define FILE_MODE  (S_IRUSR|S_IWUSR|S_IRGRP|S_IROTH)
#define FIFO "myfifo"
#define BUFFSIZE 128
int main(int argc, char *argv[])
{
    int fd;
    int n;
    char buf[BUFFSIZE];
    if (mkfifo(FIFO,FILE_MODE)<0)
    {
        if (errno==EEXIST)
            perror("FIFO 文件已经存在");
        else
            perror("创建FIFO文件错误");
    }
    if((fd=open(FIFO,O_RDONLY|O_NONBLOCK,0))==-1)
    {
        perror("打开FIFO失败");
        unlink(FIFO);
        exit(1);
    }
    while (1)
    {
        if ((n=read(fd,buf,BUFFSIZE))>0)
            printf("%d Bytes Read From FIFO:  %s n",n,buf);
        else if (n==0)
            printf("当前FIFO是空的.n");
        else
            perror("从FIFO读取失败n");
        sleep(1);
    }
    if (close(fd)==-1)
    {
        perror("关闭FIFO失败");
        unlink(FIFO);
        exit(1);
    }
    unlink(FIFO);
    exit(0);
}

fifo_write.c:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <sys/stat.h>
#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <fcntl.h>
#define FILE_MODE  (S_IRUSR | S_IWUSR | S_IRGRP | S_IROTH)
#define FIFO "myfifo"
#define BUFFSIZE 128
int main(int argc, char *argv[])
{
    int fd;
    size_t n;
    char buf[BUFFSIZE] = "This is a IPC Message";
    if ((fd = open(FIFO,O_WRONLY|O_NONBLOCK,0))==-1)
    {
        err_sys("打开FIFO失败");
        unlink(FIFO);
        exit(1);
    }
    while (1)
    {
        if ((n=write(fd,buf,BUFFSIZE))>0)
            printf("%d Bytes Write To FIFO : %s n",n,buf);
        else
            err_sys("不能写FIFOn");
        sleep(1);
    }
    if (close(fd)==-1)
    {
        err_sys("关闭FIFO失败");
        unlink(FIFO);
        exit(1);
    }
    unlink(FIFO);
    exit(0);
}

发表于 | 分类于 | 阅读次数:

Step1:根据一个单词的首尾字符建立有向图，记录出度和入度。

Step2:使用并查集判断是否连通(就是查找计数公共祖先数目)

Step3:判断Euler通路(回路)

如果是一个Euler回路，那么所有的顶点出度等于入度。

如果判断一个Euler通路，就要找：

一个起始点（出度-入度=1）的顶点

一个终点（入度-出度=1）的顶点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#define TEST printf("Here Is Ok\n");
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum boolean{false,true};
#define MAX(x,y) ((x)>(y)?(x):(y))
#define MIN(x,y) ((x)<(y)?(x):(
int in[26],out[26];
int app[26];
int pre[26];
int io[2
int find(int x)
{
    if (pre[x]!=x)
        pre[x] = find(pre[x]);
    return pre[x];

void unionSet(int a,int b)
{
    int x,y;
    x = find(a);
    y = find(b);
    if (x!=y)
        pre[x] = y;
}
//并查集查祖先节点
int countRoot()
{
    register int i;
    int cnt = 0;
    for (i = 0; i < 26; i++)
    {
        if (app[i] && find(i)==i)
            cnt++;
    }
    return cnt;
}
int main()
{
    freopen("in.txt","r",stdin);
    int T,n;
    char a,b,c;
    register int i,k;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        getchar();
        for (i = 0; i < 26; i++) pre[i] = i;
        memset(in,0,sizeof(in));
        memset(out,0,sizeof(out));
        memset(app,0,sizeof(app));
        while (n--)
        {
            a = getchar();
            a-='a';
            out[a]++;
            while (b = c,(c = getchar())!='\n');
            b-='a';
            in[b]++;
            app[a] = app[b] = true;
            unionSet(a,b);
        }
        if (countRoot()>1)
        {
            puts("The door cannot be opened.");
            continue;
        }
        for (i = 0,k = 0; i < 26; i++)
        {
            if (app[i] && out[i]!=in[i])
                io[k++] = i;
        }
        //Euler回路
        if (k==0)
        {
            puts("Ordering is possible.");
            continue;
        }
        //Euler通路
            if (k==2 &&(out[io[0]]-in[io[0]]==1 && in[io[1]]-out[io[1]]==1 ||out[io[1]]-in[io[1]]==1 &&in0]]-out[io[0]]==1))
        {
            puts("Ordering is possible.");
            continue;
        }
        puts("The door cannot be opened.");
    }
    getch();
    return 0;
}

发表于 | 分类于 | 阅读次数:

简单难度的线段树，题意是给定编号1…N的N个球，然后给定数据对区间[a,b]上的球进行染色一次，最后要求输出每个球被染色的次数。先建立线段树，然后对每个操作区间[a,b]上的次数在树上进行维护，最后遍历一次统计出次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define Maxn 100001
struct node
{
    int LEFT;
    int RIGHT;
    int nCount;
}TREE[Maxn*3];
int Total[Maxn];
void BUILD(int r,int a,int b)
{
    TREE[r].LEFT = a;
    TREE[r].RIGHT = b;
    TREE[r].nCount = 0;
    int MID;
    if(a==b)
        return;
    MID = (a+b)>>1;
    BUILD(r<<1,a,MID);
    BUILD((r<<1)+1,MID+1,b);
}
void UPDATA(int r,int a,int b)
{
    int MID;
    if(a==TREE[r].LEFT && b==TREE[r].RIGHT)
        TREE[r].nCount++;
    else
    {
        MID = (TREE[r].LEFT+TREE[r].RIGHT)>>1;
        if(b <= MID)
            UPDATA(r<<1,a,b);
        elseif( a > MID)
            UPDATA((r<<1)+1,a,b);
        else
        {
            UPDATA(r<<1,a,MID);
            UPDATA((r<<1)+1,MID+1,b);
        }
    }
}
void SUM(int r)
{
    int i;
    for(i = TREE[r].LEFT; i <= TREE[r].RIGHT;i++)
        Total[i]+=TREE[r].nCount;
    if(TREE[r].LEFT==TREE[r].RIGHT)
        return;
    else
    {
        SUM(r<<1);
        SUM((r<<1)+1);
    }
}
int main()
{
    freopen("Sample Input.txt","r",stdin);
    int N;
    int i,j,a,b;
    while(scanf("%d",&N),N)
    {
        BUILD(1,1,N);
        for(i = 1; i <= N; i++)
        {
            scanf("%d%d",&a,&b);
            UPDATA(1,a,b);
        }
        memset(Total,0,sizeof(Total));
        SUM(1);
        for(i = 1; i <= N; i++)
        {
            if(i==1)
                printf("%d",Total[i]);
            else
                printf(" %d",Total[i]);
        }
        printf("\n");
    }
    getch();
    return 0;
}

发表于 | 分类于 | 阅读次数:

转化为图后求最短路径。

1
2
IF road[i].x2 >= road[j].x1 && road[i].x2 <= road[j].x2 THEN
    建立一条边

然后由DIJKSTRA对求顶点1到其他边的最短路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 2001
int mat[Maxn][Maxn];
int M,N;
int dist[Maxn];
int used[Maxn];
enum boolean {FALSE,TRUE};
const int inf = 0x0fffffff;
struct node
{
    int x1;
    int x2;
    int w;
}road[Maxn];
void DIJSTRA(int s)
{
    int i,j,k;
    int min;
    for (i = 1; i <= N; i++)
    {
        dist[i] = mat[s][i];
        used[i] = FALSE;
    }
    used[s] = TRUE;
        for (i = 1; i < N; i++)
        {
        min = inf;
        for (j = 1; j <= N; j++)
        {
            if (used[j]==FALSE && dist[j] < min)
            {
                min = dist[j];
                k = j;
            }
        }
        used[k] = TRUE;
        for (j = 1; j <= N; j++)
        {
            if (used[j]==FALSE && dist[j] > dist[k]+mat[k][j])
                dist[j] = dist[k]+mat[k][j];
        }
    }
}
int main()
{
    int T;
    int i,j,k;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&N,&M);
        for (i = 1; i <= N; i++)
        {
            for (j = 1; j <= N; j++)
                mat[i][j] = inf;
            mat[i][i] = 0;
        }
        for (i = 1; i <= N; i++)
            scanf("%d%d%d",&road[i].x1,&road[i].x2,&road[i].w);
        for (i = 1; i <= N; i++)
        {
            for (j = i+1; j <= N; j++)
            {
                if (road[i].x2 >= road[j].x1 && road[i].x2 <= road[j].x2)
                    mat[i][j] = road[j].w;
            }
        }
        DIJSTRA(1);
        for (i = 1; i <= M; i++)
        {
            scanf("%d",&k);
            if (dist[k]<inf)
                printf("%d\n",road[1].w+dist[k]);
            else
                printf("-1\n");
        }
    }
    return 0;
}

发表于 | 分类于 | 阅读次数:

题目描述一个容器有三种操作，压入a，删除a，查询容器中比a大的第k个数。

利用树状数组快速求前n项和修改元素的性质。

对于插入和删除操作都是从a处开始简单更新树状数组+1或者-1

查询的时候利用sum（x）快速求出比x小的有多少个的性质，因为sum(x)的值是在[0,Maxm]都是单调递增的，因此可以从区间[a,Maxm]进行二分查找，找出比a大的第k个数.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define Maxn 300005
#define Maxm 100005
enum boolean{FALSE,TRUE};
int A[Maxm];
int C[Maxn];
int lowbit(int t){ return -t & t;}
int plus(int pos,int num)
{
    while (pos<Maxn)
    {
        C[pos]+=num;
        pos+=lowbit(pos);
    }
    return TRUE;
}
int sum(int end)
{
    int sum = 0;
    while (end>0)
    {
        sum += C[end];
        end -= lowbit(end);
    }
    return sum;
}
int query(int a,int k)
{
    int mid,low,high;
    int i,j,t;
    if(sum(Maxm)-sum(a)<k)   //判断是否可能存在
        return FALSE;
    i = sum(a);               //记录容器中比a小的数的个数
    low = a;
    high = Maxm;
    while (low <= high)       //二分找到第k大
    {
        mid = (low+high)>>1;
        t = sum(mid);
        if (A[mid] && t-A[mid]<k+i && t-i>=k)
            break;
        else if (t < k+i)
            low = mid+1;
        else
            high = mid-1;
    }
    printf("%d\n",mid);
    return TRUE;
}
int main()
{
    int T,i,a,k,s;
    freopen("Sample Input.txt","r",stdin);
    while (scanf("%d",&T)!=EOF)
    {
        memset(C,0,sizeof(C));
        memset(A,0,sizeof(A));
        while(T--)
        {
            scanf("%d",&s);
            if (!s)
            {
                scanf("%d",&a);
                plus(a,1);
                A[a]++;
            }
            else if (s==1)
            {
                scanf("%d",&a);
                if (A[a] <= 0)
                    printf("No Elment!\n");
                else
                {
                    plus(a,-1);
                    A[a]--;
                }
            }
            else
            {
                scanf("%d%d",&a,&k);
                if (!query(a,k))
                    printf("Not Find!\n");
            }
        }
    }
    getch();
    return 0;
}