分类目录归档:LINUX C & ARM & C51

快速排序 - 分治策略

看了书之后,自己写了一遍,留个印记
[ssj@main ~]$ cat my.c
#include <stdio.h>
int data[]={2,4,3,34,32,4,23,4,234,234,2,532,34,1,31,5,21,312,3,1523,12,3};
quick_sort(int data[],int low,int high)
{
int i,j,pivot;
if (low<high)
{
i=low;
j=high;
pivot=data[low];

while(i<j){
while(i<j&&data[j]>=pivot)j–;
if(i<j)data[i++]=data[j];
while(i<j&&data[i]<=pivot)i++;
if(i<j)data[j–]=data[i];
}
data[i]=pivot;
quick_sort(data,low,i-1);
quick_sort(data,i+1,high);

}

}
main()
{
int i;
for(i=0;i<=22;i++)
{printf("%d ",data[i]);}
printf("n");
quick_sort(data,0,22);
for(i=0;i<=22;i++){printf("%d ",data[i]);}
printf("n");

}

进程与线程的关系

进程的两个特点:
资源所有权:进程是一个可拥有资源的独立单位;
调度/执行:进程同时又是一个可以独立调度和分派的基本单位;

引入线程的目的:
因为进程是一个资源拥有者,因而在进程的创建、撤消和切换中,系统必须为之付出较大的时空
开销。也因此,在系统中所设置的进程数目不宜过多,进程切换的频率也不宜过高,同时也限制了并
发程序的进一步提高。在操作系统中引入线程,是为了减少程序并发执行时所付出的时空开销,使操
作系统具有更好的并发性。

线程的实质:
线程是进程中的一个实体,是被系统独立调度和分派的基本单位,一个进程可有多个线程;
线程除运行必需的资源外,不拥有系统资源,但它可与同属一进程的其它线程共享进程所拥有的全部资源;
一个线程可创建和撤消另一线程;同一进程中的线程间可并发执行;
线程间相互制约;线程在运行中呈现间断性;
线程有就绪、阻塞、执行三种基本状态;

线程与进程的比较
引入线程的OS
调度:线程为调度和分派的基本单位。进程为拥有资源的基本单位。
并发性:进程间可并发执行,一个进程中的多个线程间也可并发执行。
拥有资源:进程是拥有资源的一个独立单位线程不拥有系统资源。
系统开销:线程切换的开销远小于进程切换的开销;有的系统线程切换、同步和通信都无须OS内核的干预

传统的OS
调度:拥有资源和独立调度、分派的基本单位都是进程。
并发性:进程间可并发执行。
拥有资源:进程是拥有资源的一个独立单位。
系统开销:进程切换的开销远大于线程切换的开销;进程切换涉及OS内核。

线程的功能特征
和进程一样,线程具有执行状态,且可以与另一个线程同步。
线程状态—-和进程一样,线程的主要状态有运行、就绪和阻塞。一般来说,挂起状态对线程
没有什么意义。与线程状态变化相关的有四种基本操作:
  产生(Spawn): 当产生一个新进程时,同时也为该进程产生一个线程,随后,进程中的线程可以
  在同一个进程中产生另一个线程,并为新线程提供指令指针和参数。
  阻塞(Block): 当线程需要等待一个事件时,它将自己阻塞,此时处理器转而执行另一个就绪线程。
  解除阻塞(Unlock): 当阻塞一个线程的事件发生时,该线程被转移到就绪队列中。
  结束(Finish): 当一个线程完成时,其寄存器上下文和栈都被释放。
  线程同步—-一个线程对资源任何的修改都会影响同一个进程中其他线程的环境。因此,需要对各种
  线程的活动进行同步。

线程的分类
线程可分以下两类:
内核支持线程—-线程的创建、撤消和切换都由内核实现。
用户级线程——线程的创建、撤消和切换都不利用系统调用来实现,与内核无关。

两类线程的比较:
内核支持线程
线程的调度与切换速度:与进程的调度与切换十分相似。
系统调用:调度以线程为单位。
线程执行时间:线程多的进程获得CPU时

用户级线程
线程的调度与切换速度:发生在一个应用进程的各线程间,无须OS内核的干预,规则远比进程调度和切换的规则简单。切换速度特别快。
系统调用:一个线程调度看作整个进程的行为。
线程执行时间:进程运行速度与其拥有线程的数量成反比。

C 优先级与结合性

优先级:决定哪部分表达式先计算。
结合性:计算时是从左向右顺序,还是从右向左的顺序。

例1:
b=++a;

先看优先级:++ 优先级比 = 要高,先算++。
再看结合性:++ 的结合性是从右到左,这里就是它,直接算。
现在就剩下 = 号了,优先级就它一个了,但结合性还是 从右到左,那么现在把a 的值取出来赋值给 b 。
所以: 整个结果相当于
a = a + 1; b=a;

例2:
b=a++;

先看优先级,++ 虽然高,但是后置的(它的结合性是从左到右),这就意味着它返回左值。而返回值后就必须进行下面的计算
这里是 = ,运算全部完成后才能进行自身++运算,所以它最后算。我们这里先看 = ,再看结合性: 从右到左。故取 a 的值
赋值给 b ; 最后 a 的值加1 。
相当于: b=a; a = a + 1;

例3:
a+=b-=++c+4+e++;

这个够复杂吧,谁先? 单目运算符前缀 ++ 先算,然后是 + ,赋值运算最后。
然后看结合性。 -= += 都是从右到左,右边先算。故:
上例分解为:++c;b= b- e+c+4;a=a+b;e++

赋值运算符:结合性从右到左
先确定优先级,然后确定结合性。相同优先级的前提下,就要看结合性
结合性表示的是同级优先级,即同级运算符中的优先级。
优先级表示的是全局优先级,即不同运算符中的优先级。

对于自增自减表达式
前缀:先于表达式中其它部分的运算进行计算;
后缀:后于表达式中其它部分的运算进行计算。

++A ; 结合性,从右到左。 变量在右,返回右值。
//先看到 ++ 再看到 A ,返回 A 时 A 已经自增。

A++ ; 结合性,从左到右。 变量在左,返回左值。
//先看到 A,可以返回值,直接返回。A 本身再自增。

再来看看 B=A++; B=++A; 很容易就知道运算关系是怎么样的了,下面进行说明:

A++,执行后置运算,后计算A自增。先返回变量A的值参与表达式中其它部分的运算,整个表达式计算完成后,A才自增。
因其间返回的临时值参是一个常量,故该表达式不能写成:
A++ = 100;// 常量不能赋值

++A,执行前置运算,先计算A自增,然后返回A自增后的值。因为A自增操作已经完成,不必返回临时常量,直接返回A本身即可。
所以该表达式最终返回值是一个变量,故可以写成:
++A = 200; // 变量可以赋值

注意,理解它们, ++A, A++ ,要把它们当一个整体来看,即最小单位。在这里是没什么左右的,不要再分解它们。

自己总结的优先级
1. 括号操作符与关联和后置的自加自减(同级从左到右结合)
() isdigit('1')
[] array[4]
-> prt->age=34;
. *obj.age=34;
++ i++
— i–

2. 单字元的前置运算符(从右到左)
! if(!done)
~ flages=~flages;
++ ++i
— –i
+ int i=+1;
– int i=-1;
* int *p;
& p=&a;
sizeof sizeof(int);

3.数字运算符(乘除取模,高于加减 从左到右)

* i=2*4;
/ i=4/2;
% i=4%3;

+ i=2+4;
– i=4-2;

4.位移运算(从左到右)
>> int flages=flages<<2;
<<

5.比较大小(<,>高于==,!= 从左到右)
< if (i<2)
<=
>
>=

== if (i==2)
!=

6.位运算(&,^,|优先级从高到低,从左向右)
& flages=flages&42;
^
|

7.逻辑运算(从左到右)
&&
||

8.(右向左)
? : int i=(a>b)?a:b

9.赋值(从右向左)
=,+=,-=,*=,/=,%=,&=,^=,|=,<<=,>>=

10.
throw throw eclass("message");

11.逗号
, for (i=0,j=0;i<10;i++,j++)

C 语言 优先级

Operators Associativity
() [] -> . left to right
! ~ ++ — + – * (type) sizeof right to left
* / % left to right
+ – left to right
<< >> left to right
< <= > >= left to right
== != left to right
& left to right
^ left to right
| left to right
&& left to right
|| left to right
?: right to left
= += -= *= /= %= &= ^= |= <<= >>= right to left

C ++ 优先级列表
http://www.kumouse.com/C++%20operator_precedence.html