基本要素
1.リテラルまたは変数として表される値
2.演算子
すべての文字はリテラルとして解釈され、その文字自体にしかマッチしない。
一部のメタキャラクタは、grepやawkのようなプログラムで使われる拡張セットにしか存在しない。
メモリ管理
struct memblock {
int size;
unsigned char magic;
unsigned char occupied;
struct memblock *next;
struct memblock *prev;
};
#define HEADER_SIZE (sizeof(struct memblock))
#define DELTA 20
#define MEM_MAGIC 0xa5
#define WORDSIZE 4
#define WORD_ALIGN(n) (((n) + WORDSIZE - 1) & -WORDSIZE)
struct memblock block_chain;
#define HEAP_SIZE 10000
char memory_heap[HEAP_SIZE];
void initialize_memory()
{
struct memblock *h;
h = (struct memblock *)memory_heap;
block_chain.size = sizeof(block_chain);
block_chain.magic = MEM_MAGIC;
block_chain.occupied = 1;
block_chain.next = block_chain.prev = h;
h->size = HEAP_SIZE;
h->magic = MEM_MAGIC;
h->occupied = 0;
h->next = h->prev = & block_chain;
}
void *allocate_block(int size)
{
struct memblock *p, *s;
int nbytes;
nbytes = WORD_ALIGN(size + HEADER_SIZE);
for (p = block_chain.next; p != &block_chain; p = p->next){
if(!p->occupied && p->size >= nbytes){
if (p->size - nbytes > DELTA){
s = (struct memblock *)((char *)p + nbytes);
s->size = p->size - nbytes;
s->magic = MEM_MAGIC;
s->occupied = 0;
p->next->prev = s;
s->next = p->next;
p->next = s;
s->prev = p;
p->size = nbytes;
p->occupied = 1;
} else
p->occupied =1;
return (char *)p + HEADER_SIZE;
}
}
return NULL;
}
void free_block(void *block)
{
struct memblock *mem;
mem = (struct memblock *)((char *)block - HEADER_SIZE);
if(mem->magic != MEM_MAGIC)
return;
if (! mem->prev->occupied){
mem->next->prev = mem->prev;
mem->prev->next = mem->next;
mem->prev->size += mem->size;
mem = mem->prev;
}
if(! mem->next->occupied){
mem->next->next->prev = mem;
mem->size += mem->next->size;
mem->next = mem->next->next;
}
mem->occupied = 0;
}
パドック法による8クイーン
#include < stdio.h >
#include < stdlib.h >
#include < string.h >
#define SUCCESS 1
#define FAIL 0
#define FREE 1
#define NOT_FREE 0
#define N 8
int pos[N];
int col[N];
int down[2 * N - 1];
int up[2 * N - 1];
void init_board()
{
int i;
for (i = 0; i < N; i++)
pos[i] = -1;
for (i = 0; i < N; i++)
col[i] = FREE;
for(i = 0; i < 2 * N - 1; i++)
down[i] = FREE;
for (i = 0; i< 2 * N -1; i++)
up[i] = FREE;
}
void print_queens()
{
int i, j;
for(i = 0; i < N; i++){
for(j = 0; j < N; j++){
if(pos[i] == j)
printf("Q ");
else
printf(". ");
}
printf("\n");
}
printf("\n");
}
int try(int a)
{
int b;
for (b = 0; b < N; b++){
pos[a] = b;
col[b] = NOT_FREE;
up[a + b] = NOT_FREE;
down[a - b + (N-1)] = NOT_FREE;
if(a + 1 >= N)
return SUCCESS;
else {
if(try(a + 1) == SUCCESS)
return SUCCESS;
else {
pos[a] = -1;
col[b] = FREE;
up[a + b] = FREE;
down[a-b + (N-1)] = FREE;
}
}
}
return FAIL;
}
main()
{
init_board();
if(try(0) == SUCCESS)
print_queens();
else
printf("Sorry, but there is no solution.\n");
}
プログラマーの定義
仕様書どおりにプログラムを書くのがプログラマーの現場で多いかもしれないが、
力をつけるには、
1.問題を分析して、何をするプログラミングを書くのかを決める
2.どんなアルゴリズム、データ構造を使用すれば良いか選択する
3.実際にプログラムを書く
を繰り返す。
順序付きリスト同士の統合
#include < iostream >
#include < list >
using namespace std;
int main()
{
list< char > lst1, lst2;
int i;
for(i=0; i< 10; i+=2) lst1.push_back('A'+i);
for(i=1; i< 11; i+=2) lst2.push_back('A'+i);
cout << "lst1 content: ";
list< char >::iterator p = lst1.begin();
while(p != lst1.end()){
cout << *p;
p++;
}
cout << endl << endl;
cout << "lst2 content: ";
p = lst2.begin();
while(p != lst2.end()){
cout << *p;
p++;
}
cout << endl << endl;
lst1.merge(lst2);
if(lst2.empty())
cout << "lst2 is now empty\n";
cout << "merged lst1 content\n";
p = lst1.begin();
while(p != lst1.end()){
cout << *p;
p++;
}
return 0;
}
双方向リスト
#include < iostream >
#include < list >
using namespace std;
int main()
{
list lst;
list revlst;
int i;
for(i=0; i< 10; i++) lst.push_back('A'+i);
cout << "lst size = " << lst.size() << endl;
cout << "size: ";
list< char >::iterator p;
while(!lst.empty()){
p = lst.begin();
cout << *p;
lst.pop_front();
revlst.push_front(*p);
}
cout << endl << endl;
cout << "revlst size = ";
cout << revlst.size() << endl;
cout << "content: ";
p = revlst.begin();
while(p != revlst.end()){
cout << *p;
p++;
}
return 0;
}
リスト
#include < iostream >
#include < list >
using namespace std;
int main()
{
list lst;
int i;
for(i=0; i<10; i++) lst.push_back('A'+i);
cout << "size = " << lst.size() << endl;
list::iterator p;
cout << "content: ";
while(!lst.empty()){
p = lst.begin();
cout << *p;
lst.pop_front();
}
return 0;
}
オーバーロードバージョン
#include < iostream >
#include < vector >
using namespace std;
class Demo {
double d;
public:
Demo() { d = 0.0; }
Demo(double x){ d = x; }
Demo &operator=(double x){
d = x; return *this;
}
double getd() { return d; }
};
bool operator<(Demo a, Demo b)
{
return a.getd() < b.getd();
}
bool operator==(Demo a, Demo b)
{
return a.getd() == b.getd();
}
int main()
{
vector v;
int i;
for(i=0; i<10; i++)
v.push_back(Demo(i/3.0));
for(i=0; i
反復子を利用してベクトルにアクセス
#include < iostream > #includeusing namespace std; int main() { vector v; int i; for(i=0; i<10; i++) v.push_back(i); for(i=0; i<10; i++) cout << v[i] << " "; cout << endl; vector ::iterator p = v.begin(); while(p != v.end()){ cout << *p << " "; p++; } return 0; }
コンストラクタ
#include < iostream >
using namespace std;
class myclass {
int a;
public:
myclass(int x){ a= x; }
int geta() { return a; }
};
int main()
{
myclass ob(4);
cout << ob.geta();
return 0;
}