一个不错的c++大数类(转载)

一个不错的大数类,虽然用到的可能性很小,但还是存着,以防万一。。(本来想用java的大数类来做题,接过语法总是出错,哎。。)
代码出处:http://blog.csdn.net/maybeevil/article/details/6413740

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXN 9999
#define MAXSIZE 1000
#define DLEN 4
using namespace std;
class BigNum;
istream& operator>>(istream&,  BigNum&);
ostream& operator<<(ostream&,  BigNum&);
class BigNum
{
public:
	int a[MAXSIZE];
	int len;
public:
	BigNum(){len = 1;memset(a,0,sizeof(a));}
	BigNum(const int);
	BigNum(const char*);
	BigNum(const BigNum &);  
	BigNum &operator=(const BigNum &);
	friend istream& operator>>(istream&,  BigNum&);
	friend ostream& operator<<(ostream&,  BigNum&);
	BigNum operator+(const BigNum &) const;
	BigNum operator-(const BigNum &) const;
	BigNum operator*(const BigNum &) const;
	BigNum operator/(const int  &) const;
	BigNum operator^(const int  &) const;
	int    operator%(const int  &) const;  
	bool   operator>(const BigNum & T)const;
	bool   operator==(const BigNum & T)const;
	bool   operator==(const int & t)const;
	bool   operator>(const int & t)const;
};
istream& operator>>(istream & in,  BigNum & b)
{
	char ch[MAXSIZE*4];
	int i = -1;
	in>>ch;
	int l=strlen(ch);
	int count=0,sum=0;
	for(i=l-1;i>=0;)
	{
		sum = 0;
		int t=1;
		for(int j=0;j<4&&i>=0;j++,i--,t*=10)
		{
			sum+=(ch[i]-'0')*t;
		}
		b.a[count]=sum;
		count++;
	}
	b.len =count++;
	return in;
	
}
ostream& operator<<(ostream& out,  BigNum& b)
{
	int i;  
	cout << b.a[b.len - 1];
	for(i = b.len - 2 ; i >= 0 ; i--)
	{
		cout.width(DLEN);
		cout.fill('0');
		cout << b.a[i];
	}
	return out;
}
BigNum::BigNum(const int b)
{
	int c,d = b;  
	len = 0;
	memset(a,0,sizeof(a));
	while(d > MAXN)
	{
		c = d - (d / (MAXN + 1)) * (MAXN + 1);
		d = d / (MAXN + 1);  a[len++] = c;
	}
	a[len++] = d;
}
BigNum::BigNum(const char*s)
{
	int t,k,index,l;
	memset(a,0,sizeof(a));
	l=strlen(s);  
	len=l/DLEN;
	if(l%DLEN)len++;
	index=0;
	for(int i=l-1;i>=0;i-=DLEN)
	{
		t=0;k=i-DLEN+1;
		if(k<0)k=0;
		for(int j=k;j<=i;j++)
			t=t*10+s[j]-'0';
		a[index++]=t;
	}
}
BigNum::BigNum(const BigNum & T) : len(T.len)
{
	int i;
	memset(a,0,sizeof(a));
	for(i = 0 ; i < len ; i++)  a[i] = T.a[i];
}
BigNum & BigNum::operator=(const BigNum & n)
{
	len = n.len;
	memset(a,0,sizeof(a));
	for(int i = 0 ; i < len ; i++)
		a[i] = n.a[i];
	return *this;
}
BigNum BigNum::operator+(const BigNum & T) const
{
	BigNum t(*this);
	int i,big;  
	big = T.len > len ? T.len : len;
	for(i = 0 ; i < big ; i++)
	{
		t.a[i] +=T.a[i];
		if(t.a[i] > MAXN)
		{
			t.a[i + 1]++;
			t.a[i] -=MAXN+1;
		}
	}
	if(t.a[big] != 0) t.len = big + 1;
	else t.len = big;  
	return t;
}
BigNum BigNum::operator-(const BigNum & T) const
{  
	int i,j,big;
	bool flag;
	BigNum t1,t2;
	if(*this>T)
	{
		t1=*this;
		t2=T;
		flag=0;
	}
	else
	{
		t1=T;
		t2=*this;
		flag=1;
	}
	big=t1.len;
	for(i = 0 ; i < big ; i++)
	{
		if(t1.a[i] < t2.a[i])
		{
			j = i + 1;
			while(t1.a[j] == 0) j++;
			t1.a[j--]--;
			while(j > i) t1.a[j--] += MAXN;
			t1.a[i] += MAXN + 1 - t2.a[i];
		}
		else t1.a[i] -= t2.a[i];
	}
	t1.len = big;
	while(t1.a[len - 1] == 0 && t1.len > 1)
	{
		t1.len--;
		big--;
	}
	if(flag)t1.a[big-1]=0-t1.a[big-1];
	return t1;
}
BigNum BigNum::operator*(const BigNum & T) const
{
	BigNum ret;
	int i,j,up;
	int temp,temp1;  
	for(i = 0 ; i < len ; i++)
	{
		up = 0;
		for(j = 0 ; j < T.len ; j++)
		{
			temp = a[i] * T.a[j] + ret.a[i + j] + up;
			if(temp > MAXN)
			{
				temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
				up = temp / (MAXN + 1);
				ret.a[i + j] = temp1;
			}
			else
			{
				up = 0;
				ret.a[i + j] = temp;
			}
		}
		if(up != 0)
			ret.a[i + j] = up;
	}
	ret.len = i + j;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
BigNum BigNum::operator/(const int & b) const
{
	BigNum ret;
	int i,down = 0;  
	for(i = len - 1 ; i >= 0 ; i--)
	{
		ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
		down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
	}
	ret.len = len;
	while(ret.a[ret.len - 1] == 0 && ret.len > 1) ret.len--;
	return ret;
}
int BigNum::operator %(const int & b) const
{
	int i,d=0;
	for (i = len-1; i>=0; i--)
	{
		d = ((d * (MAXN+1))% b + a[i])% b;  
	}
	return d;
}
BigNum BigNum::operator^(const int & n) const
{
	BigNum t,ret(1);
	int i;
	if(n<0)exit(-1);
	if(n==0)return 1;
	if(n==1)return *this;
	int m=n;
	while(m>1)
	{
		t=*this;
		for( i=1;i<<1<=m;i<<=1){
			t=t*t;
		}
		m-=i;
		ret=ret*t;
		if(m==1)ret=ret*(*this);
	}
	return ret;
}
bool BigNum::operator>(const BigNum & T) const
{
	int ln;
	if(len > T.len) return true;
	else if(len == T.len)
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln >= 0) ln--;
		if(ln >= 0 && a[ln] > T.a[ln]) return true;
		else return false;
	}
	else return false;
}
bool BigNum::operator==(const BigNum & T) const
{
	int ln;
	if(len != T.len) return false;
	else
	{
		ln = len - 1;
		while(a[ln] == T.a[ln] && ln-- );
		if(ln < 0) return true;
		else return false;
	}
}
bool BigNum::operator >(const int & t) const
{
	BigNum b(t);
	return *this>b;
}
bool BigNum::operator==(const int & t) const
{
	BigNum b(t);
	return *this==b;
}

第3章 查找与替换——cut、join以及awk基础


0.sed补充:sed的d命令:
    sed '/^#/d' file    删除正则匹配的行
cut与join
cut
1.语法:
    cut -c list [file……]
    cut -f list [-d delim][file……]
    (1)-c list
        以字符为单位,执行剪下操作。list为字符编号或范围(以逗号隔开),如:1,3,5-12,42
    (2)-f list
        一字段为单位,执行剪下操作。list为字段编号或范围(以逗号隔开)。
    (3)-d delim
        使用delim作为定界符。默认定界符为制表符(Tab)
2.注意:
    (1)字符编号和字段编号都是从1开始
    (2)若处理的是字段,则定界符隔开的即为各字段,而输出时字段也以给定的定界符隔开。
    (3)若命令行没有指定文件,则读取stdin。
    (4)cut能识别宽字符,所以“字符”与“字节”意义不同。
join
3.作用:join命令将多个文件结合在一起,每个文件里的每条记录,都共享一个键值(key).
键值:指的是记录中的主字段。
4.插幅高清大图


5.join的输入文件必须排好序
awk的基础知识
1.基本模式:awk 'program' [file……]
2.awk的命令针对行
3.program的基本架构
    pattern {action}
4.默认以空白与制表符(或混用)分割字段
5.可以通过修改变量FS变更分隔符,分隔符可以是ERE表达式
6.awk将每条记录内的字段数目存储到变量NF
7.$的含义
    $0:表示整条记录(默认,可省略)
    $1:表示第一个字段
    $2:表示第二个字段
    ……
    例:
        awk '{print $2,$NF}'    打印第1和最后一个字段(注意:要加逗号,不然输出将没有分隔符而连在一起)
        awk 'NF>0  {print $0}'    打印非空行
        $NF:最后一个字段(因为NF的数值是字段数目)
8.不指定action,默认为打印
9.设置字段分隔符:
    (1)-F选项:可以自动设置变量FS
        例:awk -F: '{print $1,$5}'        以:为分隔符
    (2)输出字段分隔符由变量OFS控制,可以用-v选项改变
        例:awk -F: -v 'OFS=**'    'print $1,$5'    以**为输出字段的分隔符
10.print自动换行,printf不会
例:awk -F:    '{printf "User %s is really %s\n",$1,$5}' /etc/passwd
11.BEGIN和END(一般写在文件中)
    (1)语法
        BEGIN {startup code}
        pattern1  {action1}
        pattern2  {action2}
        ……
        END {cleanup code}

    (2)可以有多个BEGIN和END语句块,awk按顺序执行,BEGIN必须位于起始处,END必须位于结尾
    (3)BEGIN可用来设置变量
        例:
            BEGIN {FS=":" ; OFS="**"}
12,对grep、sed、awk等的用途总结:
一般用grep删选特定行,用sed做替换,用awk删选指定字段或交换字段次序
 

leds、UserButton以及Timer的联用小练习

学会UserButton之后很想联合学过的这三个interface写点东西,好吧,小程序一个。。
定时器控制3个led的亮灭,UserButton用来控制定时器的开关。

#include<Timer.h>
#include<UserButton.h>
module ButtonTest2C @safe()
{
	uses
	{
		interface Boot;
		interface Leds;
		interface Get<button_state_t>;
		interface Notify<button_state_t>;
		interface Timer<TMilli> as Timer0;
	}
}
implementation
{
	uint8_t led_state=1;
	bool isrunning=FALSE;
	event void Boot.booted()
	{
		call Notify.enable();
		call Timer0.startPeriodic(2000);		

	}
	event void Timer0.fired()
	{
		call Leds.set((led_state++)%8);
	}
	event void Notify.notify(button_state_t state)
	{
		isrunning=call Timer0.isRunning();
		if(state==BUTTON_PRESSED)
		{
			if(isrunning==TRUE)
				call Timer0.stop();
			else
				call Timer0.startPeriodic(2000);
		}
	}
}

TinyOS——用UserButton控制led

这个程序用用几分钟写完,但是改错改了两天,这两天的空余时间在这个程序上花掉不少。最后居然发现是Boot接口没连接。。泪奔~
ButtonTestAppC.nc:

configuration ButtonTestAppC
{
}
implementation
{
	components ButtonTestC,MainC,LedsC,UserButtonC;
	ButtonTestC.Boot->MainC;
	ButtonTestC.Leds->LedsC;
	ButtonTestC.Get->UserButtonC;
	ButtonTestC.Notify->UserButtonC;
}

ButtonTestC.nc:

#include<UserButton.h>
module ButtonTestC @safe(){
	
	uses interface Boot;
	uses interface Leds;
	uses interface Get<button_state_t>;
	uses interface Notify<button_state_t>;
	    
}
implementation{
	uint8_t leds_state=0;
	event void Boot.booted()
	{
		call Notify.enable();
		call Leds.set(leds_state);
	}
	event void Notify.notify(button_state_t state)
	{
		if(state==BUTTON_PRESSED)
		{
			
			leds_state=call Leds.get();
			if(leds_state==0)
			{
				call Leds.led0On();
			}
			else if(leds_state==1)
			{
				call Leds.led0Toggle();
				call Leds.led1Toggle();
			}
			else if(leds_state==2)
			{
				call Leds.led1Toggle();
				call Leds.led2Toggle();

			}
			else if(leds_state==4)
			{
				call Leds.led2Toggle();
				call Leds.led0Toggle();
			}

		}
		
	}
}

基于大根堆的最大优先级队列

《算导》中的最大优先级队列伪代码用的是一维数组,元素只有优先级key,而没有本身的含义,这与实际应用不符,遂改为结构体数组。

//注意:二叉堆的根是heap[1];
#include<stdio.h>
#include<stdlib.h>
#define INT_MIN -2147483647
#define HEAP_INIT_SIZE 0
#define LENGTH 100 
typedef struct{
	int value;//元素本身的值
	int key;//优先级
}node;
node heap[LENGTH];
int heapsize=HEAP_INIT_SIZE,length=LENGTH;
void max_heapify(node *heap,int i);
void build_max_heap(node *heap);
int maxisum(node *heap);
int heap_extract_max(node *heap);
bool heap_increase_key(node *heap,int i,int key);
void max_heap_insert(node *heap,int key,int value);
int main()
{
	/*
	int i;
	max_heap_insert(heap,2,2);
	max_heap_insert(heap,200,200);
	max_heap_insert(heap,1000,1000);
	max_heap_insert(heap,50,50);
	heapsize=4;
	build_max_heap(heap);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].value);
	printf("\n");
	printf("%d\n",maxisum(heap));
	printf("%d\n",heap_extract_max(heap));
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].value);
	printf("\n");
	heap_increase_key(heap,2,400);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].key);
	printf("\n");
	max_heap_insert(heap,5444987,5444987);
	for(i=1;i<=heapsize;i++)
		printf("%d ",heap[i].key);
	printf("\n");
	system("pause");
	*/
	return 0;
}
void max_heapify(node *heap,int i)//根节点与孩子关系未确定,但子树都是堆
{
	int largest;
	int l=2*i,r=2*i+1;
	if(l<=heapsize&&heap[l].key>heap[i].key)
		largest=l;
	else
		largest=i;
	if(r<=heapsize&&heap[r].key>heap[largest].key)
		largest=r;
	if(largest!=i)
	{
		node t;
		t=heap[i];
		heap[i]=heap[largest];
		heap[largest]=t;
		max_heapify(heap,largest);
	}
	return;
}
void build_max_heap(node *heap)//将无序数组建成二叉堆
{
	//注意:建堆前应在调用者函数内设置好heapsize
	int i;
	for(i=heapsize/2;i>=1;i--)
	{
		max_heapify(heap,i);
	}
	return;
}
int maxisum(node *heap)//返回优先级最高的元素的优先级(即堆根的key域)
{
	return heap[1].key;
}
int heap_extract_max(node *heap)
{
	if(heapsize<1)
	{
		printf("heap underflow\n");
		return -1;
	}
	int max=heap[1].key;
	heap[1]=heap[heapsize];
	heapsize--;
	max_heapify(heap,1);
	return max;
}
bool heap_increase_key(node *heap,int i,int key)//将元素i的优先级提高到key
{
	if(key<heap[i].key)
		return false;
	heap[i].key=key;
	while(i>1 && heap[i/2].key<heap[i].key)//为什么不直接用max_heapify()?注意max_heapify()的使用条件
	{
		node t=heap[i];
		heap[i]=heap[i/2];
		heap[i/2]=t;
		i=i/2;
	}
	return true;
}
void max_heap_insert(node *heap,int key,int value)//插入优先级为key,值为value的元素
{
	heapsize++;
	heap[heapsize].key=INT_MIN;
	heap[heapsize].value=value;
	heap_increase_key(heap,heapsize,key);
	return;
}

算法导论——(二叉)堆和堆排序

这篇笔记不知道该发在acm还是数据结构,就数据结构吧。。
今天数电课还是挺有收获的,至少认识到3个知识点:1、原来一直认为单片机是早期的cpu,现在才知道整个单片机应当是mcu(微控制单元,以前一直以为mcu==cpu),而cpu是mcu的核心;2、单片机的RAM是SRAM,呵呵,原来是cache,怪不得这么快。。3.位异或可以看成单个位之间的相加,第一次听到这种理解,颇有醍醐灌顶之感。
好吧,还是来说说正题,关于堆.
1.(二叉)堆是完全二叉树
2.堆的高度:从下往上(最下面一层高度为0)(从0开始)。
3.高度与
4.约定:用一维数组存储堆,根是heap[1]
5.高度h和元素个数n的关系:h=floor(log(n))
6.如何将无序数组建成大根堆:对非叶子节点从下往上保持堆一遍
7.实现《算法导论》中的伪代码

//注意:二叉堆的根是heap[1];
#include<stdio.h>
#include<stdlib.h>
int heap[7];
int heapsize,length=6;
void max_heapify(int *heap,int i);
void build_max_heap(int *heap);
void heapsort(int *heap);
int main()
{
	/*
	int i=1,j=8;
	while(i<=6)
	{
		heap[i]=j--;
		i++;
	}
	build_max_heap(heap);
	heapsort(heap);
	for(i=1;i<=6;i++)
		printf("%d ",heap[i]);
	printf("\n");
	*/
	system("pause");
	return 0;
}
void max_heapify(int *heap,int i)//根节点与孩子关系未确定,但子树都是堆
{
	int largest;
	int l=2*i,r=2*i+1;
	if(l<=heapsize&&heap[l]>heap[i])
		largest=l;
	else
		largest=i;
	if(r<=heapsize&&heap[r]>heap[largest])
		largest=r;
	if(largest!=i)
	{
		int t;
		t=heap[i];
		heap[i]=heap[largest];
		heap[largest]=t;
		max_heapify(heap,largest);
	}
	return;
}
void build_max_heap(int *heap)//将无序数组建成二叉堆
{
	heapsize=length;
	int i;
	for(i=heapsize/2;i>=1;i--)
	{
		max_heapify(heap,i);
	}
	return;
}
//二叉排序
void heapsort(int *heap)//排序后为升序
{
	int i;
	for(i=length;i>=2;i--)
	{
		int t;
		t=heap[i];
		heap[i]=heap[1];
		heap[1]=t;
		heapsize--;
		max_heapify(heap,1);
	}
	return;
}

事实上,堆排序虽漂亮,但快排往往优于它,而且C++ STL中的sort()的内部就是快排,所以直接调用即可。

TinyOS——好吧,写个程序再说

TinyOS——好吧,写个程序再说
firstC.nc

#include "Timer.h"
module firstC @safe()
{
  uses interface Timer<TMilli> as Timer0;
  uses interface Leds;
  uses interface Boot;
}
implementation
{
  uint8_t count=1;
  event void Boot.booted()
  {
    call Timer0.startPeriodic( 250 );
  }

  event void Timer0.fired()
  {
    call Leds.set(count++);
  }
}

firstAppC.nc

configuration firstAppC
{
}
implementation
{
  components MainC, firstC, LedsC;
  components new TimerMilliC() as Timer0;


  firstC -> MainC.Boot;

  firstC.Timer0 -> Timer0;
  firstC.Leds -> LedsC.Leds;
}

昨天拿到了TelosB,好吧,改了下Blink,也算是写了本人的第一个nesC程序吧。
接下来对前几天看的一些内容做个总结:
1.接口的provider组件实现了该接口,在命令实现中触发相应的事件(signal 接口名.事件名)
2.大多数平台支持float,但double可能不行
3.任务是原子的,也就是说它是同步的,阻塞的。而tinyOS中大部分接口的命令和事件是异步的,非阻塞的(在新线程中运行)
4.关于post语句
(1)任务用post提交。虽然任务是同步的,但是任务的提交操作却是异步的,post语句会立即返回。
(2)post的返回值:error_t post
error_t是SUCCESS或者FAIL
(3)当且仅当任务队列中已经有相同任务时,返回FAIL,且不插入任务
5.使用不同变量的atomic语句可以互相抢占,也就是打破原子性;含有相同变量的atomic语句不能相互抢占
6.中断可以被延迟,甚至错过(这点有点不合理啊。。~),因为atomic代码的原子性
7.error_t可以取那些值:请查看tos/types/TinyError.h
8.其他一些就不记了,还是到时候翻下书吧。。
9.三个组件的情况
(1)
组件:MainC
接口:Boot
命令:无
事件:event void booted()
(2)
组件:LedsC
接口:Leds
命令:
command void led0Off()
command void led0On()
command void led0Toggle()
……
……(把led0Off的0分别改为1、2)
command uint8_t get()
command void set(uint8_t dt)
事件:无
(3)
组件:TimerMilliC()(需要实例化(有点像创建对象,用new))
接口:Timer
命令:
command void startPeriodic(uint32_t dt)
command void startOneShot(uint32_t dt)
command void stop()
事件:fired()

(顺序)双向栈的简单实现

忙死了,好想给自己一个停下来的借口。

//i==0表示栈1,其他则为栈2
#include<stdio.h>
#include<stdlib.h>
#define elemtype int
#define MAX_SIZE 100
typedef struct{
	elemtype *base;
	elemtype top1;
	elemtype top2;
}TWS;
void InitStack(TWS &tws);
bool push(TWS &tws,int i,elemtype e);
bool pop(TWS &tws,int i,elemtype &e);
void DestroyStack(TWS &tws);
int main()
{
	elemtype e;
	TWS tws;
	InitStack(tws);
	push(tws,0,1);
	push(tws,0,2);
	push(tws,0,3);
	while(tws.top1!=0)
	{
		pop(tws,0,e);
		printf("%d ",e);
	}
	printf("\n");

	push(tws,1,3);
	push(tws,1,2);
	push(tws,1,1);
	while(tws.top2!=MAX_SIZE-1)
	{
		pop(tws,1,e);
		printf("%d ",e);
	}
	printf("\n");

	DestroyStack(tws);
	system("pause");
	return 0;
}
void InitStack(TWS &tws)
{
	tws.base=(elemtype*)malloc(MAX_SIZE*sizeof(elemtype));
	if(!tws.base)
		exit(-1);
	tws.top1=0;
	tws.top2=MAX_SIZE-1;
	return;
}
bool push(TWS &tws,int i,elemtype e)
{
	if(tws.top1==tws.top2+1)
		return false;
	if(i==0)
		tws.base[tws.top1++]=e;
	else
		tws.base[tws.top2--]=e;
	return true;
}
bool pop(TWS &tws,int i,elemtype &e)
{
	if(i==0)
	{
		if(tws.top1==0)
			return false;
		e=tws.base[--tws.top1];
	}
	else
	{
		if(tws.top2==MAX_SIZE-1)
			return false;
		e=tws.base[++tws.top2];
	}
	return true;
}
void DestroyStack(TWS &tws)
{
	free(tws.base);
	tws.base=NULL;
	tws.top1=0;
	tws.top2=MAX_SIZE-1;
	return;
}

nesC——模块和配件的细节总结

模块和配件的细节总结
0.关于模块:
(1)默认的代码实现
<1>模块能为使用的接口命令或事件a指定默认的代码实现
<2>模块不能为提供的接口命令或事件a指定默认的代码实现
<3>如果a未与任何命令或事件进行绑定,就会执行默认的实现
<4>默认的命令或事件在定义时以default作为前缀
举例:

default command result_t Send.send(uint16_t address,uint8_t length,TOS_MsgPtr msg)
{
return SUCCESS;
}

(2)任务
<1>任务的返回类型为void,且无参数
<2>任务用post提交,提交后放入任务队列,然后立即返回
<3>post的返回值:提交成功返回1,否则返回0。post表达式的类型为unsigned char
(3)原子
<1>原子是运行的最小单位
<2>主要目的是确保运行时没有其他运算同时发生
<3>一般用于更新并发性的互斥变量
<4>原子代码内不能调用命令或触发事件
<5>原子代码内,控制只能正常流入和流出,禁止跳入跳出(goto、break、continue等)语句。
示例:

atomic{
语句;
语句;
……
}
或者
atomic 变量名=值;

一些关于configuration的细节总结
1.外部规范元素和内部规范元素
外部规范元素:configuration XXX{}中的元素(原文不是这样,用词比较专业化,个人理解应该是这个意思)
内部规范元素:implementation{}中的规范元素
2.一个组件始终只有一个实例。如果组件K被用于两个不同的配件,或是在同一个配件中被使用两次,在程序中仍然只有K的唯一实例。
3.同一个规范元素可以被多次绑定
举例:
(1)

configuration C{
	provides interface X;
}
implementation{
	components C1,C2;
	X=C1.X;
	X=C2.X;
}

当X中的命令被调用时,X中的事件将会被多次触发(“扇入”),以及多个函数的执行(“扇出”)
原因:因为C1、C2组件的X接口都与X接口关联,所以C1、C2组件中的X接口的对应命令代码都会被执行,两个代码都会触发事件。
(2)
当两个配件独立地绑定同一个接口时,多重绑定也会发生
举例:

configuration C{}
implementation{
	components C1,C2;
	C1.Y->C2.Y;
}

configuration D{}
implementation{
	components C3,C2;
	C3.Y->C2.Y;
}

4.隐式绑定
这个感觉没有什么重要的知识点,既然是初学,还是用完整写法,这方面以后用的时候再补充。

第3章 查找与替换——sed基础(下)

1.sed匹配特定行:只要在命令前置一个地址,就可以限制一条命令应用到哪些行
address command
2.地址的种类:
(1)正则表达式
限制命令应用于匹配正则表达式模式的行。
可与s命令搭配使用:
‘/oldfunc/ s/$/# XXX: migrate to newfunc/’ 在行末加上注释
‘/bob/ s//& and tom/g’ 注意:s命令中的空模式指的是“使用前一个正则表达式”,所 以这个语句等同于/bob/ s/bob/& and tom/g
(2)最终行(。。不太理解~)
符号$指“最后一行”。          建议看这本书,比较经典《sed and awk》高清版下载链接
例:
sed -n ‘$p’ ‘$1′ 快速打印文件的最后一行
注意:“最后一行”指的是输入数据的最后一行,即最后一个文件的最后一行
(3)行编号
使用绝对的行编号作为地址(暂时了解不多)
(4)范围
可指定行的范围,仅需将地址以逗号隔开
例:sed -n ’10,42p’ foo.xml 仅打印10——42行
sed ‘/foo/,/bar/ s/baz/quux/g’ 仅替换范围内的行
注意:1)对于上述第二个例子,范围表达式的两项一定在不同行中,同一行中的前后两个项不构成匹配。
2)经测试,如果只找到范围表达式中的前一项,则实际范围为前一项所在行——最后一行;反之,如果只找到后一项,则没有行匹配。
3)经测试,如果范围表达式中的后一项有多个,则匹配最先找到的那个;如果范围表达式的前一项有多个,也是匹配最先找到的那个。
4)经测试,如果范围表达式中的后一项在前面行,而前一项在后面行,则结果有点乱。。不分析,我认为应该尽量避免这种情况。

(5)否定正则表达式
在正则表达式后加上!表示将命令应用于不匹配于特定模式的每一行
例:’/tom/!s/bob/Bob/g’ 将没有tom的每一行里的所有bob替换为Bob
2.匹配的长度:
原则:
(1)匹配最长的最左边的子字符串。
(2)匹配空(null)字符串。
例:echo Tolstoy is worldly|sed ‘s/T.*y/Camus/’
Camus
echo abc|sed ‘s/b*/1/’
1abc
echo abc|sed ‘s/b*/1/g’
1a1c1
注意:上面第三个例子:中间为什么匹配b而没有匹配a与b以及b与c之间的null?
答:因为null字符串被看成比完全不匹配稍微长一些,比匹配一个字符短。然后回顾下原则(1)就明白了。

tinyos之nesC

继续来谈谈对tinyos和nesC的理解,当然了,是比较肤浅的见解
1.nesC的编程框架
nesC可以看成是C的一种方言。。。个人观点~~请无视==!
组件:分为module和configuration
module实现具体程序逻辑,configuration负责连接各个组件
接口:可以看成一些函数声明的集合。组件之间只能通过接口交流
接口具有双向性
接口一般在组件中实现
module分两类:
1.提供接口(provider):接口的提供者必须实现接口的所有命令
2.使用接口(user):接口的使用者必须实现接口的所有事件
举例:接口StdControl:
相应接口文件:里面只是StdControl的声明(这和JAVA是相似的)
接口提供者(组件):如果一个组件要具有开关一个元器件的功能,那它就应该提供StdControl,并实现它的命令
接口使用者(组件):如果一个组件要使用该元器件,则需要调用上述组件的StdControl接口,它就需要实现StdControl的事件,即当事件发生时做什么
由上述例子可见:很多组件可以提供同一个接口,当然它们的内部代码(功能)是不同的,这也是需要在configuration中连接的原因,个人感觉连接很像电子设计中的布线。。
2.本质上为什么要进行连接?
下面是个人的一些初步理解,错误之处请大牛指出
和标准c一样,nesC也有命名空间,不同在于,nesC的命名空间都是局部的,它没有一个全局的命名空间,组件内部的变量和函数都是私有的,所以说组件沟通的唯一方法是通过接口。
连接的本质也在这里,因为没有全局的命名空间,因此无法实现像标准c那样的连接(函数名在外部是无效的),甚至于像c++那样的动态绑定(函数指针实现),所以nesC通过configuration显式地连接,把调用名与具体实现关联。当然了,这样的连接是静态的。
3.关于命令和事件的一点看法:
接口的提供者实现命令,触发相应事件。当使用者调用的命令完成,该命令(在提供者内部)触发相对应的事件,并以某种方式(早上看的比较乱,居然忘了。。)向上到达使用者。
早上数据结构课上机,本来想的挺好,写好的程序给他看下就走人,结果人太多,他一个一个看,到12点还没轮到我。。好惨。不过正好利用这段时间看了下tinyos programming的一部分,受益匪浅,不知道为什么很多东西到现在又忘了,看来有些原理性的东西得再看。然后晚上本来想找个好点的编辑环境,发现实验室给的xubuntu的vim已经增加了nesC的语法高亮,哈哈,考虑周全,省心多了~~

第3章 查找与替换——sed基础(上)

最近真是有够忙的,不过仔细想想自己其实一直处在这种状态中,,,各种东西要去学。走在路上脑中一会儿跳出个nesC,一会儿想起某个数据结构题,想着想着又会出现个在线雇佣问题k的计算。。然后到了吃饭的时候,又该想想java的多态和c++的对比以及shell的那几个易忘点。总之,生活越来越快节奏了,唯一能应对的办法只有更拼了。。
好吧,该做的还是得做。复习下sed基础,记下笔记。。
1.语法:

	sed [-n] 'editing command' [file……]
	sed [-n] -e 'editing command' [file……]
	sed [-n] -f script-file [file……]

2.s命令:用于替换(或删除)
sed ‘s/tom/bob/’ name.list 将文件name.list中的tom替换成bob
3.关于定界符:
定界符可以是标点或斜杠,用户可以根据需要选择(如:文件中已经有斜杠,但没有:时,可以用:作为定界符)
4.sed如果没有指定输入文件,则输入为默认stdin;sed如果没有指定输出文件,则输出为默认stdout
5.&
&表示追加,例:sed ‘s/tom/&,a good boy’ name.list 在tom后面加上,a good boy
6.g
g是global的意思,以g结尾表示替换能够匹配的每一个,默认sed的s命令只替换匹配的第一个。
注意:特别的,可以以数i结尾表示替换匹配的第i个
例:

	echo tom reads well,tom writes well.>example.txt
	sed 's/tom/bob'<example.txt
	bob reads well,tom writes well.
	sed 's/tom/bob/g'<example.txt
	bob reads well,bob writes well.
	sed 's/tom/bob/2'<example.txt
	tom reads well,bob writes well.

7.注意特殊字符的转义:
\&、\/表示&、/的字面义
8.如果有多个命令,则使用-e
例:sed -e ‘s/tom/bob’ -e ‘s/shadow/sunshine’ file.txt
9.当命令有很多时,可以把命令写在脚本中

$cat fixup.sed
s/foo/bar/g
s/chicken/cow/g
s/draft animal/horse/g
……
$sed -f fixup.sed myfile.xml >myfile2.xml

10.sed会记得在脚本里遇到的最后一个正则表达式——不管它在哪。通过使用空的正则表达式,同一个正则表达式可以再使用。
s/tom/bob/3 替换第3个
s//2 替换第1个
11.sed是如何工作的?
sed一行一行地读取文件,将读到的行放到内存的一个区域————称之为模式空间。
sed按命令改变模式空间的内容,最后输出。
12.-n表示不打印模式空间的内容。p命令则相反。p可以覆盖在-n之上
例:
sed -n ‘s/tom/bob/’ name.list 完成替换后将不会显示
sed -n ‘//p’ index.html 仅显示带有的行
sed -e ‘s/e/E/g’ -e ‘/All/p’ sed-test.txt 对于这条,我发现结果打印出了替换后的文件,但是其中含有All的行连着打印了两次。
写了个文件sed-test.txt。通过上面的第三条指令,肯定两个事实:(1)sed对读入模式空间的一行文本依序执行所有命令选项,然后打印,然后读入另一行。(2)sed的命令选项是针对一行字符的。(这行是(1)的自然推论)例:sed ‘s/tom/bob/4′ 每一行的第4个tom都会被替换,如果不足4个,则不会替换。

13.在脚本中关闭sed的自动打印
通过在首行#n实现
#n
//p
14.正则表达式的一个易错点:
关于*和后向引用
例:
b* 匹配0个或多个b,如null字符、b、bb、bbb
.* 匹配所有字符,如abc、a14f5
[[:alpha:]]* 匹配所有字母,如abc、abdfhsa
\(['"]\).*\1 匹配两个’的出现或是两个”的出现(也就是说如果前面匹配成功的是’,则后面匹配’;反之亦然),如’gjd’、”dsk”只有这两种形式
区别:对于*,如果前置正则是确定的字符,则表示该字符的重现,如果前置正则是一个范围,则表示这个范围内字符的重现;对于后向引用,如果前置正则是一个范围或[]表达式等,则后面的”\数字“表示前面匹配成功的字符的重现,注意成功二字
注意:上面所指的字符可以扩展到表达式,如ERE中的()

数据结构作业——魔王语言解释

好吧,今天要上机,昨晚花了些时间把这个题目搞定,应该是几个题目中最简单的了。时间不多,因此程序健壮性明显不够,但是应付下老师,应该够了。。有时间再完善一下。

//括号中第一个不能为‘A’‘B’;不能出现()、([a-z])以及单个括号情况
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define elemtype char
#define STACK_INIT_SIZE	100
#define STACKINCREMENT 10
typedef struct Node{
	elemtype data;
	struct Node*next;
}NODE,*PNODE;
typedef struct{
	PNODE front;
	PNODE rear;
	int len;
}Queue;
typedef struct{
	elemtype *base;
	elemtype *top;
	int stacksize;
}SqStack;
void print(Queue &queue);
void change(SqStack &s,SqStack &ss,Queue &queue);
void init(elemtype a[],SqStack &s,SqStack &ss,Queue &queue);

bool InitStack(SqStack &s);
void DestroyStack(SqStack &s);
void ClearStack(SqStack &s);
bool StackEmpty(SqStack s);
int StackLength(SqStack s);
bool GetTop(SqStack s,elemtype &e);
bool push(SqStack &s,elemtype e);
bool pop(SqStack &s,elemtype &e);
void StackTraverse(SqStack &s);

void InitQueue(Queue &queue);
void DestroyQueue(Queue &queue);
void ClearQueue(Queue &queue);
bool QueueEmpty(Queue &queue);
int QueueLength(Queue &queue);
bool GetHead(Queue &queue,elemtype &e);
bool EnQueue(Queue &queue,elemtype e);
bool DeQueue(Queue &queue,elemtype &e);
bool QueueTraverse(Queue &queue);
int main()
{
	char a[100];

	while(gets(a)!=NULL)
	{
		SqStack s,ss;
		Queue queue;

		init(a,s,ss,queue);//初始化栈s、ss、队列queue。
		change(s,ss,queue);//将栈s中的字符依序出栈,括号中的字符处理后入栈ss,再入队;非括号中的字符处理后入队。
		print(queue);//出队列,输出解释后的文字

		DestroyStack(s);
		DestroyQueue(queue);
	}
	system("pause");
	return 0;
}
bool InitStack(SqStack &s)
{
	s.base=(elemtype *)malloc(STACK_INIT_SIZE*sizeof(elemtype));
	if(!s.base)
		exit(-1);
	s.top=s.base;
	s.stacksize=STACK_INIT_SIZE;
	return true;
}
void DestroyStack(SqStack &s)
{
	free(s.base);
	s.base=s.top=NULL;
	s.stacksize=0;
	return;
}
void ClearStack(SqStack &s)
{
	if(s.base==s.top)
		return;
	else
	{
		s.top=s.base;
		s.stacksize=0;
		return;
	}
}
bool StackEmpty(SqStack s)
{
	if(s.base==s.top)
		return true;
	else
		return false;
}
int StackLength(SqStack s)
{
	return s.top-s.base;
}
bool GetTop(SqStack s,elemtype &e)
{
	if(s.base==s.top)
		return false;
	e=*(s.top-1);
	return true;
}
bool push(SqStack &s,elemtype e)
{
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(elemtype *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(elemtype));
		if(!s.base)
			exit(-1);
		s.top=s.base+s.stacksize;
		s.stacksize+=STACKINCREMENT;
	}
	*s.top++=e;
	return true;
}
bool pop(SqStack &s,elemtype &e)
{
	if(s.base==s.top)
		return false;
	e=*--s.top;
	return true;
}
void StackTraverse(SqStack &s)
{
	if(s.base==s.top)
		return;
	elemtype *p=s.base;
	while(p!=s.top)
	{
		printf("%c ",*p);
		p++;
	}
	printf("\n");
	return;
}


void InitQueue(Queue &queue)
{
	queue.front=queue.rear=(PNODE)malloc(sizeof(NODE));
	if(!queue.front) exit(-1);
	queue.front->next=NULL;
	queue.len=0;
	return;
}
void DestroyQueue(Queue &queue)
{
	while(queue.front)
	{
		queue.rear=queue.front->next;
		free(queue.front);
		queue.front=queue.rear;
	}
	queue.len=0;
	return;
}
void ClearQueue(Queue &queue)
{
	PNODE p=queue.front->next,q;
	if(QueueEmpty(queue))
		return;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	queue.front->next=NULL;
	queue.rear=queue.front;
	queue.len=0;
	return;
}
bool QueueEmpty(Queue &queue)
{
	if(queue.len==0)
		return true;
	else
		return false;
}
int QueueLength(Queue &queue)
{
	return queue.len;
}
bool GetHead(Queue &queue,elemtype &e)//获取首节点的值
{
	if(queue.len==0)
		return false;
	e=queue.front->next->data;
	return true;
}
bool EnQueue(Queue &queue,elemtype e)
{
	PNODE p=(PNODE)malloc(sizeof(NODE));
	if(!p)
		return false;
	p->data=e;
	queue.rear->next=p;
	p->next=NULL;
	queue.rear=p;
	(queue.len)++;
	return true;
}
bool DeQueue(Queue &queue,elemtype &e)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	e=p->data;
	queue.front->next=p->next;
	if(queue.rear==p)
		queue.rear=queue.front;
	(queue.len)--;
	return true;
}
bool QueueTraverse(Queue &queue)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	while(p)
	{
		printf("%c ",p->data);
		p=p->next;
	}
	printf("\n");
	return true;
}
void print(Queue &queue)
{
	elemtype e;
	while(queue.len!=0)
	{
		DeQueue(queue,e);
		switch(e)
		{
			case 't':
				printf("天");
				break;
			case 'd':
				printf("地");
				break;
			case 's':
				printf("上");
				break;
			case 'a':
				printf("一只");
				break;
			case 'e':
				printf("鹅");
				break;
			case 'z':
				printf("追");
				break;
			case 'g':
				printf("赶");
				break;
			case 'x':
				printf("下");
				break;
			case 'n':
				printf("蛋");
				break;
			case 'h':
				printf("恨");
				break;
			default:
				break;
		}
	}
	printf("\n");
	return;
}
void change(SqStack &s,SqStack &ss,Queue &queue)
{
	elemtype e,temp;
	bool flag=false;

	while(!StackEmpty(s))
	{
		pop(s,e);
		if(e=='A'&&!flag)
		{
			EnQueue(queue,'s');
			EnQueue(queue,'a');
			EnQueue(queue,'e');
		}
		else if(e=='B'&&!flag)
		{
			EnQueue(queue,'t');
			EnQueue(queue,'s');
			EnQueue(queue,'a');
			EnQueue(queue,'e');
			EnQueue(queue,'d');
			EnQueue(queue,'s');
			EnQueue(queue,'a');
			EnQueue(queue,'e');
		}
		else if(e!='('&&e!=')')
		{
			if(!flag)
				EnQueue(queue,e);
			else
			{
				push(ss,e);
				push(ss,temp);
			
			}
			
		}
		else if(e=='(')
		{
			pop(s,e);
			temp=e;
			push(ss,temp);
			flag=true;
		}
		else if(e==')')
		{
			flag=false;
			while(!StackEmpty(ss))
			{
				pop(ss,e);
				EnQueue(queue,e);
			}
		}
	}
	return;
}
void init(elemtype a[],SqStack &s,SqStack &ss,Queue &queue)
{
	int len,i;
	InitStack(s);
	InitStack(ss);
	InitQueue(queue);
	len=strlen(a);
	for(i=len-1;i>=0;i--)
	{
		push(s,a[i]);
	}
	return;
}

第3章 查找与替换——(POSIX)ERE正则表达式

1.关于反斜杠:ERE中,\无论在哪,都表示转义,要表示\,需使用\\
2.ERE中没有后向引用
3.区间表达式:{} 与BRE的区别是没有反斜杠。
注意:如果{没有匹配的},则定义为”未定义状态“
4.? 匹配0个或1个前置正则表达式
5.+ 匹配1个或多个前置正则表达式
6.交替运算符(管道运算符)| :方括号表达式可以表示”匹配这个字符,或是那个字符……“,而交替运算符可以表示”匹配这个序列,或是那个序列,或是……“。
例如:read|write|see匹配read或write或see。|在ERE中优先级最低。
7.分组()
ERE运算符被应用到”前置正则表达式“。()运算符正是提供了”前置“的范围。
例如:(why)+ 匹配一个或连续的多个why
((read|write)[[:space:]]*)+ 匹配多个(包括一个)连续出现的read或write,且中间可能被空白隔开。
8.注意^abcd|efgh$和^(abcd|efgh)$的不同
前者:匹配起始处为abcd或结尾处为efgh的字符串行
后者:匹配正是abcd或正是efgh的字符串行
原因:|的优先级最低
9.ERE运算符的优先级

10.额外的GNU正则表达式运算符

11.unix程序及其正则表达式类型

12.grep默认使用BRE,加上-E选项则使用ERE。
13.通常,awk在其ERE中不支持区间表达式,为了可移植性,应当使用反斜杠转义{}。

链式队列的实现

#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	int data;
	struct Node*next;
}NODE,*PNODE;
typedef struct{
	PNODE front;
	PNODE rear;
	int len;
}Queue;
void InitQueue(Queue &queue);
void DestroyQueue(Queue &queue);
void ClearQueue(Queue &queue);
bool QueueEmpty(Queue &queue);
int QueueLength(Queue &queue);
bool GetHead(Queue &queue,int &e);
bool EnQueue(Queue &queue,int e);
bool DeQueue(Queue &queue,int &e);
bool QueueTraverse(Queue &queue);
int main()
{
	Queue queue;
	int e;
	/*
	InitQueue(queue);
	EnQueue(queue,1);
	EnQueue(queue,2);
	EnQueue(queue,3);
	EnQueue(queue,4);
	EnQueue(queue,5);
	QueueTraverse(queue);
	printf("%d\n",queue.len);
	DeQueue(queue,e);
	QueueTraverse(queue);
	printf("%d\n",queue.len);
	DestroyQueue(queue);
	system("pause");
	*/
	return 0;
}
void InitQueue(Queue &queue)
{
	queue.front=queue.rear=(PNODE)malloc(sizeof(NODE));
	if(!queue.front) exit(-1);
	queue.front->next=NULL;
	queue.len=0;
	return;
}
void DestroyQueue(Queue &queue)
{
	while(queue.front)
	{
		queue.rear=queue.front->next;
		free(queue.front);
		queue.front=queue.rear;
	}
	queue.len=0;
	return;
}
void ClearQueue(Queue &queue)
{
	PNODE p=queue.front->next,q;
	if(QueueEmpty(queue))
		return;
	while(p)
	{
		q=p;
		p=p->next;
		free(q);
	}
	queue.front->next=NULL;
	queue.rear=queue.front;
	queue.len=0;
	return;
}
bool QueueEmpty(Queue &queue)
{
	if(queue.len==0)
		return true;
	else
		return false;
}
int QueueLength(Queue &queue)
{
	return queue.len;
}
bool GetHead(Queue &queue,int &e)//获取首节点的值
{
	if(queue.len==0)
		return false;
	e=queue.front->next->data;
	return true;
}
bool EnQueue(Queue &queue,int e)
{
	PNODE p=(PNODE)malloc(sizeof(NODE));
	if(!p)
		return false;
	p->data=e;
	queue.rear->next=p;
	p->next=NULL;
	queue.rear=p;
	(queue.len)++;
	return true;
}
bool DeQueue(Queue &queue,int &e)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	e=p->data;
	queue.front->next=p->next;
	if(queue.rear==p)
		queue.rear=queue.front;
	(queue.len)--;
	return true;
}
bool QueueTraverse(Queue &queue)
{
	if(queue.len==0)
		return false;
	PNODE p=queue.front->next;
	while(p)
	{
		printf("%d ",p->data);
		p=p->next;
	}
	printf("\n");
	return true;
}