Urllib库Python爬虫应用

#Urllib库Python爬虫应用

##爬单个网页demo

1
2
3
import urllib2
response=urllib2.urlopen("http://www.baidu.com")
print response.read()

##分析爬网页的方法

1
response=urllib2.urlopen("http://www.baidu.com")

首先我们调用的是urllib2库里面的urlopen方法，传入一个URL，这个网址是百度首页，协议是HTTP协议，当然你也可以把HTTP换做FTP,FILE,HTTPS 等等，只是代表了一种访问控制协议，urlopen一般接受三个参数，它的参数如下：

1
urlopen(url,data,timeout)

第一个参数url即为URL，第二个参数data是访问URl要传送的数据，第三个timeout是设置超时时间。

第二三个参数是可以不传送的，data默认为空None，timeout默认为 socket._GLOBAL_DEFAULT_TIMEOUT

第一个参数URL是必须要传送的，在这个例子里面我们传送了百度的URL，执行urlopen方法之后，返回一个response对象，返回信息便保存在这里面。

1
print response.read()

##构造request
其实上面的urlopen参数可以传入一个request请求,它其实就是一个Request类的实例，构造时需要传入Url,Data等等的内容。比如上面的两行代码，我们可以这么改写

1
2
3
4
import urllib2
request=urllib2.Request("http://www.baidu.com")
response=urllib2.urlopen(request)
print response.read()

运行结果是完全一样的，只不过中间多了一个request对象，推荐大家这么写，因为在构建请求时还需要加入好多内容，通过构建一个request，服务器响应请求得到应答，这样显得逻辑上清晰明确。

##POST与GET数据传送
上面的程序演示了最基本的网页抓取，不过，现在大多数网站都是动态网页，需要你动态地传递参数给它，它做出对应的响应。所以，在访问时，我们需要传递数据给它。最常见的情况是什么？对了，就是登录注册的时候呀。

把数据用户名和密码传送到一个URL，然后你得到服务器处理之后的响应，这个该怎么办？下面让我来为小伙伴们揭晓吧！

数据传送分为POST和GET两种方式，两种方式有什么区别呢？

最重要的区别是GET方式是直接以链接形式访问，链接中包含了所有的参数，当然如果包含了密码的话是一种不安全的选择，不过你可以直观地看到自己提交了什么内容。POST则不会在网址上显示所有的参数，不过如果你想直接查看提交了什么就不太方便了，大家可以酌情选择。

“做个shell玩一玩”

shell.py ：Shell 的主程序，负责读取、解析并执行命令
func/ ：自定义模块，所有的自定义命令的实现函数文件都位于这里
init.py ：使 func 文件夹能作为 Python 模块被导入
cd.py ：实现了 Shell 的 cd 命令
constants.py ：定义了各种常量与路径
exit.py ：定义了 exit 命令，用来退出程序
getenv.py ：实现 getenv 命令，获取系统变量的值
history.py：实现 history 命令，展示输入的命令日志

#shell.py

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
import os
import sys
import shlex
import getpass
import socket
import signal
import subprocess
import platform
from func import *
built_in_cmds = {}
def tokenize(string):
    return shlex.split(string)
def preprocess(tokens):
    processed_token = []
    for token in tokens:
        if token.startswith('$'):
            processed_token.append(os.getenv(token[1:]))
        else:
            processed_token.append(token)
    return processed_token
def handler_kill(signum, frame):
    raise OSError("Killed!")
def execute(cmd_tokens):
    with open(HISTORY_PATH, 'a') as history_file:
        history_file.write(' '.join(cmd_tokens) + os.linesep)
    if cmd_tokens:
        cmd_name = cmd_tokens[0]
        cmd_args = cmd_tokens[1:]
        if cmd_name in built_in_cmds:
            return built_in_cmds[cmd_name](cmd_args)
        signal.signal(signal.SIGINT, handler_kill)
        if platform.system() != "Windows":
            p = subprocess.Popen(cmd_tokens)
            p.communicate()
        else:
            command = ""
            command = ' '.join(cmd_tokens)
            os.system(command)
    return SHELL_STATUS_RUN
def display_cmd_prompt():
    user = getpass.getuser()
    hostname = socket.gethostname()
    cwd = os.getcwd()
    base_dir = os.path.basename(cwd)
    home_dir = os.path.expanduser('~')
    if cwd == home_dir:
        base_dir = '~'
    if platform.system() != 'Windows':
        sys.stdout.write("[\033[1;33m%s\033[0;0m@%s \033[1;36m%s\033[0;0m] $ " % (user, hostname, base_dir))
    else:
        sys.stdout.write("[%s@%s %s]$ " % (user, hostname, base_dir))
    sys.stdout.flush()
def ignore_signals():
    if platform.system() != "Windows":
        signal.signal(signal.SIGTSTP, signal.SIG_IGN)
    signal.signal(signal.SIGINT, signal.SIG_IGN)
def shell_loop():
    status = SHELL_STATUS_RUN
    while status == SHELL_STATUS_RUN:
        display_cmd_prompt()
        ignore_signals()
        try:
            cmd = sys.stdin.readline()
            cmd_tokens = tokenize(cmd)
            cmd_tokens = preprocess(cmd_tokens)
            status = execute(cmd_tokens)
        except:
            _, err, _ = sys.exc_info()
            print(err)
def register_command(name, func):
    built_in_cmds[name] = func
def init():
    register_command("cd", cd)
    register_command("exit", exit)
    register_command("getenv", getenv)
    register_command("history", history)
def main():
    init()
    shell_loop()
if __name__ == "__main__":
    main()

#constants.py

1
2
3
4
5
6
import os
SHELL_STATUS_STOP = 0
SHELL_STATUS_RUN = 1
HISTORY_PATH = os.path.expanduser('~') + os.sep + '.shiyanlou_shell_history'

#exit.py

1
2
3
4
from .constants import *
def exit(args):
    return SHELL_STATUS_STOP

#getenv.py

1
2
3
4
5
6
from .constants import *
def getenv(args):
    if len(args) > 0:
        print(os.getenv(args[0]))
    return SHELL_STATUS_RUN

#history.py

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import sys
from .constants import *
def history(args):
    with open(HISTORY_PATH, 'r') as history_file:
        lines = history_file.readlines()
        limit = len(lines)
        if len(args) > 0:
            limit = int(args[0])
        start = len(lines) - limit
        for line_num, line in enumerate(lines):
            if line_num >= start:
                sys.stdout.write('%d %s' % (line_num + 1, line))
        sys.stdout.flush()
    return SHELL_STATUS_RUN

#init.py

1
2
3
4
5
from .cd import cd
from .exit import exit
from .getenv import getenv
from .history import history
from .constants import *

做个数独玩一玩

今天突发奇想，看到空间有一个数独，从前没有做过这类的东西，数独源于瑞士，后在美国发展、并在日本得以发扬光大的数学智力拼图游戏。拼图是九宫格（即3格宽×3格高）的正方形状，每一格又细分为一个九宫格。在每一个小九宫格中，分别填上1至9的数字，让整个大九宫格每一列、每一行的数字都不重复。
于是就想到可以用二维数组试想一下，然后就试了试。。。

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
class Shudo
{
	private:
		int DataBasic[9][9];
		int DataResult[9][9];
		bool isSloved;
	public:
	    void PrintA(){
			for(int i=0;i<=8;i++){
				for(int j=0;j<=8;j++){
					cout<<DataBasic[i][j]<<" ";
				}
				cout<<"\n";
			}
		}
		void PrintB(){
				for(int i=0;i<=8;i++){
				for(int j=0;j<=8;j++){
					cout<<DataResult[i][j]<<" ";
				}
				cout<<"\n";
			}
			
		}
		Shudo(int Data[9][9])
		{
			memcpy(DataBasic,Data,sizeof(DataBasic));
			isSloved=false;
		}
		bool isVaild(int i,int j)
		{
			int t=DataBasic[i][j];
			int k;
			for(k=0;k<9;k++)
			{
				if((j!=k)&&(t==DataBasic[i][k]))
					return false;
				if((i!=k)&&(t==DataBasic[k][j]))
					return false;
			}
			int iData=(i/3)*3;
			int jData=(j/3)*3;
			int k1,k2;
			for(k1=iData;k1<iData+3;k1++)
			{
				for(k2=jData;k2<jData+3;k2++)
				{
					if((k2==j)&&(k1==i))
					continue;
					if(t==DataBasic[k1][k2])
					return false;
				}
			}
			return true;
		}
		bool ShuduSlove()
		{
			int i,j,k;
			for(i=0;i<9;i++)
			{
				for(j=0;j<9;j++)
				{
					if(DataBasic[i][j]==0)
					{
						for(k=1;k<10;k++)
						{
							DataBasic[i][j]=k;
							if(isVaild(i,j)&&ShuduSlove())
							{
								if(!isSloved)
								memcpy(DataResult,DataBasic,sizeof(DataBasic));
									isSloved=true;
									return true;
							}
							DataBasic[i][j]=0;
						}
						return false;
					}
				}
			}
			return true;
		}
 } ;

先写了一个数独类，及9行9列的二维数组，用DataBasic表示初始的题目，用DataResult表示最后完成的题目，方法是挨个深度优先遍历后往里填，用isVaild()方法验证行列是否合适，合适就把值填到DataResult中。
找了一个题目试了一下，把它打出来：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 int main(){
 int data[9][9]={
 	{0,4,2,0,6,3,0,0,9},
	{6,0,0,0,1,0,0,0,5},
	{3,0,0,0,2,0,4,8,0},
	{1,0,0,5,0,2,6,0,8},
	{4,0,0,0,0,7,0,0,1},
	{9,0,5,6,0,0,0,0,7},
	{0,3,6,0,5,0,0,0,2},
	{2,0,0,0,7,0,0,0,4},
	{7,0,0,2,9,0,8,5,0},
	};
Shudo shudu(data);
shudu.PrintA();
shudu.ShuduSlove();
cout<<"\n";
shudu.PrintB();
return 0;
}

能出结果，还凑活

以后挂个GUI，估计就能用了。。。

”C++指针笔记“

指针是指向另外一个类型的复合类型，另外一种类型的复合类型，与引用类似，指针也实现了对其他对象的间接访问。然而指针与引用又有很多不同点。指针本身就是一个对象，允许对指针赋值和拷贝。和其他内置类型一样，在指针的生命周期内可以指向几个不同的对象。其次，指针无需在定义时赋值。合体它内置类型一样，在块的作用域内定义的指针如果没有被初始 化，也拥有一个不确定的值。

定义指针类型的方法将声明符写成d的形式，其中d是变量名，如果在同一条语句中定义了几条指针，每个变量前面都必须有符号：

1
2
int *iP1，*ip2;//ip1和iPhone都是指向int型对象的指针
int *p=&ival;//dp2是只想double类型对象的指针，dp是double型对象

#获取对象的地址
指针存放某个对象的地址，需要用到取地址符（操作符&):

1
2
int ival=42；
int *p=&ival；//p存放ival的地址，或者说p是ival的指针

第二条语句把P定义为一个指向int型的指针，随后初始化p令其指向名为ival的int对象。因为引用不是对象，没有实际地址，所以不能定义指向引用的指针。

1
2
3
4
5
double dval;
double *pd=&dval;//正确，初始化为double型的地址
double *pd2=pd;  //正确，初始值是指向double对象的指针
int *pi=pd;      //错误：指针pi类型和pd类型不同
pi=&dval;        //错误：试图把double型对象的地址赋给int型指针

因为在声明语句中指针的类型实际上被用于指定它所指向它所指向对象的类型，所以两者必须匹配。如果指针指向了一个其他类型的对象，对该对象的操作将发生错误。

#指针值
指针的值（即地址）用属下列4种状态之一：
1.指向一个对象。
2.指向紧邻对象所占空间的下一个位置。
3.空指针，意味着没有任何的指向对象。
4.无效指针，上述情况之外的其他值。

#利用指针访问对象
如果指针指向了一个对象，则允许用解引用符（操作符*）来访问该对象：

1
2
3
int ival=42;
int *p=&ival;//p存放着变量ival的地址，或者说p是指针变量ival的指针
cout<<p;     //42

对指针解引用直接赋值也可以得到相应的值。

#相关符号的多重含义判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<iostream>
using namespace std;
int main()
{
	int i=42;
	int &r=i;//&紧随类型名出现，因此是声明的一部分，r是一个引用 
	int *p;// 紧随类型名出现，因此是声明的一部分，p是一个指针 
	p=&i;//&出现在表达式中，是一个取地址符 
	*p=i;//*出现在表达式中，是一个解引用符 
	int &r2=*p;//&是声明的一部分，*是一个解引用符 
	return 0;
	/*int ival=42;
	int *p=&ival;
	cout<<*p;
	return 0;*/
 }

#空指针
空指针不指向任何对象，在试图使用一个指针之前可以首先检查是否为空。例如：

1
2
3
4
int *p1=nullptr;//等价于int *p=0；
int *p2=0;      //直接将p2初始化为字面常量0；
//需要先#include<cstdlib>
int *p3=NULL;   //等价于int *p3=0；

“C语言实现入门排序”

例子：乱序输入n个数，输出从小到大排序后的结果：

###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
#include<stdio.h>
int main()
{
    int i, j, n, a[100], temp;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++) //总共需冒泡n-1次
        {
            for(j=0;j<n-i-1;j++) //第i趟冒泡
            {
                if(a[j]>a[j+1]) //比较a[j]与a[j+1],使a[j+1]大于a[j]
                {
                    temp = a[j+1];
                    a[j+1] = a[j];
                    a[j] = temp;
                }
            }
        }
        for(i=0;i<n;i++) //打印
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

###2.选择排序

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
#include<stdio.h>
int main()
{
    int i, j, n, a[100], t, temp;
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        for(i=0;i<n-1;i++)           //总共排序n-1趟
        {
            t = i;
            for(j=i+1;j<n;j++)       //第i趟从a[i+1]~a[n-1]中选最小的数与a[i]交换
            {
                if(a[t]>a[j])	
                    t = j;
            }
            temp = a[i];
            a[i] = a[t];
            a[t] = temp;
        }
        for(i=0;i<n;i++)
            printf("%d ",a[i]);
        printf("\n");
    }
    return 0;
}

###3.快速排序

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
/*
1.假设数组为a[n]；
2.第一次排序过程如下：
    取x = 0 ( a[0]为中轴 )；
    i=0 (第一个元素下标), j=n-1(最后一个元素下标)；
    重复下面过程：(直到i>=j)
        {
            从a[j]起，向前找小于a[x]的元素，同时j--，找到后，a[j]与a[x]交换，x=j;
            从a[i]起，向后找大于a[x]的元素，同时i++，找到后，a[i]与a[x]交换，x=i;
         }
3.注意快排函数是迭代函数，必须要有结束条件   (因为忽略结束条件,调试了很久......)
4.再对a[low]~a[x-1]、a[x+1]~a[high]分别调用快排函数
*/
#include<stdio.h>
void quicksort(int a[],int low,int high);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        quicksort(a,0,n-1);
for(i=0;i<n;i++)
            printf("%d ",a[i]);
printf("\n");
    }
    return 0;
}
void quicksort(int a[],int low,int high)
{
    if(low>=high)  return;   //坑爹的结束条件，return后面不能跟数值
    int i=low, j= high, x=i, temp;
    while(i<j)
    {
        for(;a[j]>=a[x]&&i<j;j--);
        if(i<j)
        {
            temp = a[j];
            a[j] = a[i];
            a[i] = temp;
            x = j;
            i++;
        }
        else
            break;     //i>=j即可跳出本次while循环
        for(;a[i]<=a[x]&&i<j;i++);
        if(i<j)
        {
            temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            x = i;
            j--;
        }
        else
            break;     //跳出本次while循环
    }
    quicksort(a,low,x-1);
    quicksort(a,x+1,high);
}

###4.插入排序法

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
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void insertsort(int a[],int n);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        insertsort(a,n);
        show(a,n);
    }
    return 0;
}
void insertsort(int a[],int n)
{
    int i ,j ,k ,temp;
    for(i=1;i<n;i++)    //插入a[i]
    {
        j=i-1;
        for(;a[i]<a[j]&&j>=0;j--);  //寻找插入点
        j++;
        if(j==i)     //该数有序，不需要前插
            continue;
        else
        {
            temp=a[i];
            for(k=i-1;k>=j;k--) //将插入点后面的数依次后移一位
            {
                a[k+1]=a[k];
            }
            a[j]=temp;
        }
    }
}

###5.shell排序法

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
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void shellsort(int a[],int n);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        shellsort(a,n);
        show(a,n);
    }
    return 0;
}
void shellsort(int a[],int n)
{
    int k ,i ,j ,l ,temp;
    k = n/2;
    while(k>=1)
    {
        for(i=k;i<n;i++)
        {
            if(a[i]>=a[i-k])    //已经有序，不需要移动
                continue;
            else
            {
                for(j=i-k;a[j]>=a[i]&&j>=0;j=j-k); j+=k;    //寻找插入点a[j]
                temp = a[i];                //  保存a[i]
                for(l=i-k;l>=j;l-=k)        //依次向后移动k个位置
                {
                    a[l+k] = a[l];
                }
                a[j]=temp;      //插入
            }
        }
        k = k/2;
    }
}

###6.归并排序
归并排序是一种很容易进行并行化的算法，因为归并的各个数据区间都是独立的，没有依赖关系。并且归并排序是一种速度比较快的排序，且是一种稳定的排序算法，排序速度与关键词初始排列无关。
串行归并排序的算法大体的可以描述为：首先将要排序的表分成两个节点个数基本相等的子表，然后对每个子表进行排序，最后将排好序的两个子表合并成一个子表。在对子表进行排序时可以将子表再分解成两个节点数量基本相同的子表，当子表足够小时，也可以采用其他排序方法对子表进行排序，然后再对排好序的子表进行归并操作，最后将整个表排好序
算法流程图：

/*伪代码：
mergesort(int a[],int low,int high)；

if(high-low+1>2)执行如下几步：(3个及以上)
mid = (0+n)/2;
mergesort(a,low,mid-1);
mergesort(a,mid,high);进行本轮二路归并；bsort(int low,int mid,int high);
i=low,j=mid;
while(i=a[high]) 交换a[low],a[high];
*/

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
#include<stdio.h>
int other[100];
void exchange(int *a,int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void mergesort(int a[],int low,int high);
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        mergesort(a,0,n-1);
        show(a,n);
    }
    return 0;
}
void mergesort(int a[],int low,int high)
{
    if((high-low+1)>2)		//含3个以上
    {
        int mid = (high+low)/2;
        mergesort(a,low,mid);
        mergesort(a,mid+1,high);
        int i=low, j=mid+1, k=low;
        while(i<=mid&&j<=high)
        {
            if(a[i]<=a[j])
            {
                other[k++]=a[i++];
            }
            if(a[i]>a[j])
            {
                other[k++]=a[j++];
            }
        }
        while(i<=mid)
        {
            other[k++]=a[i++];
        }
        while(j<=high)
        {
            other[k++]=a[j++];
        }
        for(i=low;i<=high;i++)
            a[i]=other[i];
    }
    else		//含2及个以下
    {
        if(a[low]>a[high])
        {
            exchange(a+low,a+high);
        }
    }
}

###7.堆排序

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
//堆排序
/*(堆是一个完全二叉树，根结点值最大(小))
1.heapadjust(int a[],int i,int sizea)  功能:以a[i]为根，形成一个堆
  buildheap(int a[],int sizea)         功能:调用heapadjust()，使a[]形成一个堆
  heapsort(int a[],int sizea)          功能:do{建堆，输出堆顶}while(堆不空)
*/
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=0;i<n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void exchange(int *a,int *b)
{
    int t=*a;
    *a=*b;
    *b=t;
}
void heapadjust(int a[],int i,int sizea)
{
    int maxi=i;
    int l=2*i+1;
    int r=2*i+2;
    if(i<(sizea/2))     //a[i]为叶结点，则不需要调整
    {
        if(l<=(sizea-1)&&a[l]>a[i])    //左孩子比a[i]大的，取左孩子下标
        {
            maxi=l;
        }
        if(r<=(sizea-1)&&a[r]>a[maxi])  //右孩子最大，取右孩子下标
        {
            maxi=r;
        }
        if(maxi!=i)     //取比根大的孩子，与根调换
        {
            exchange(&a[maxi],&a[i]);
            heapadjust(a,maxi,sizea);   //跌倒，以a[maxi]为根，向下调整为大根堆。
        }
    }
}
//函数功能：从最后一个非叶结点起，向上直到根结点，逐步调整，建立大根对堆
void buildheap(int a[],int sizea)
{
    int i;
    for(i=(sizea/2-1);i>=0;i--)     //a[i]为最后一个非叶结点
    {
        heapadjust(a,i,sizea);
    }
}
void heapsort(int a[],int sizea)
{
    int i;
    int j=sizea;
    for(i=0;i<sizea;i++)    //每次循环，都会形成一个大根堆，堆顶元素a[0]最大
    {
        buildheap(a,j);
        exchange(&a[0],&a[--j]);    //将根(最大)结点交换到后面去
                                //堆中元素个数减一
    }
}
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=0;i<n;i++)
            scanf("%d",&a[i]);
        heapsort(a,n);
        show(a,n);
    }
    return 0;
}

###8.带哨兵的直接插入排序

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
/*从小到大排序
a[0]用作哨兵，当某个数a[i]，找插入位置时，先令a[0]=a[i]，再向前比较，当比较到a[0]时，说明插入位置为a[1],这样可以防止数组越界.
*/
#include<stdio.h>
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=1;i<=n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void dir_insert(int a[],int n)
{
    int i,j;
    for(i=2;i<=n;i++)
    {
        a[0]=a[i];
        for(j=i-1;a[j]>a[0];j--)  //插入位置：j
            a[j+1]=a[j];
        a[++j]=a[0];
    }
}
int main()
{
    int i, n, a[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&a[i]);
        dir_insert(a,n);
        show(a,n);
    }
    return 0;
}

###9.基数排序

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
//基数排序
/*假设输入数列最多为4位，且都是十进制数
  要做4次划分、收集
*/
#include<stdio.h>
#include<math.h>
#define N 4             //每个数最多4位
void show(int a[],int n)    //输出数组
{
    int i;
    for(i=1;i<=n;i++)
            printf("%d ",a[i]);
    printf("\n");
}
void radixsort(int c[],int i,int n)   //以第i位为依据进行划分和收集
{
    int a[10][30]={{0},{0},{0},{0},{0},{0},{0},{0},{0},{0}};    //a[i][]中收集本次划分基数为i的数
    int b[10]={0};      //b[i]表示本次本次划分后，基数为i的数的个数
    int j,k,l,m;
    k=pow(10,i);
    l=k/10;
    for(j=1;j<=n;j++)   //一次分配的过程
    {
        m=(c[j]%k)/l;       //判断c[j]在本次划分中被分到哪个部分
        a[m][b[m]++]=c[j];  //分配完毕后，基数为m的数为b[m]个
    }
    l=1;
    for(m=0;m<10;m++)   //收集
    {
        for(j=0;j<b[m];j++)
        {
            c[l++]=a[m][j];
        }
    }
}
void basesort(int c[],int n)
{
    int i;
    for(i=1;i<=N;i++)
    {
        radixsort(c,i,n);
    }
}
int main()
{
    int i, n, c[100];
    while(scanf("%d",&n)!=EOF)
    {
        for(i=1;i<=n;i++)
            scanf("%d",&c[i]);
        basesort(c,n);
        show(c,n);
    }
    return 0;
}

“LU矩阵分解实例”

下面给定一四阶矩阵，通过LU分解求逆矩阵。—
解：算法过程为：

第一步：求LU矩阵

通过（4）~（7）式可逐步进行矩阵L和U中元素的计算，如下所示：

经迭代计算，最后得到L和U矩阵为：


第二步：求L和U矩阵的逆u，l

（1）求U矩阵的逆

由式（9）可得矩阵U的逆的各元素计算如下：


（2）求L矩阵的逆

由（8）式可得L矩阵的逆的各元素计算如下

所以得到的逆矩阵为：

3）求A的逆矩阵
由式（10）可计算得到矩阵A的逆，如下：

由程序计算出的结果如下：

准IT工作者<br><br>CS专业学生