題目來源:
http://zhedahht.blog.163.com/blog/static/25411174201142733927831/
題目：輸入一棵二叉樹的根結(jié)點(diǎn)，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結(jié)點(diǎn)的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX(a, b) ((a)>(b) ? (a) : (b))
#define ABS(x) ((x)>=0 ? (x) : ((x)*(-1)))
struct Node {
void *data;
struct Node *left, *right;
};
int
depth(struct Node *root)
{
if(root == NULL)
return 0;
int ldepth = depth(root->left);
int rdepth = depth(root->right);
return MAX(ldepth, rdepth) + 1;
}
int
btree_isbalanced_naive(struct Node *root) /* return 1 if balanced, or return 0 */
{
if(root == NULL)
return 1;
int ldepth = depth(root->left);
int rdepth = depth(root->right);
int diff = ldepth - rdepth;
if(ABS(diff) > 1)
return 0;
return (btree_isbalanced_naive(root->left) && btree_isbalanced_naive(root->right));
}
int
btree_isbalanced(struct Node *root, int *depth)
{
if(root == NULL) {
*depth = 0;
return 1;
}
int ldepth, rdepth, diff;
if(!btree_isbalanced(root->left, &ldepth) || !btree_isbalanced(root->right, &rdepth))
return 0;
*depth = MAX(ldepth, rdepth) + 1;
diff = ldepth - rdepth;
return (ABS(diff)<=1 ? 1 : 0);
}
int
main(int argc, char **argv)
{
struct Node a = {NULL, NULL, NULL};
struct Node b = {NULL, NULL, NULL};
struct Node c = {NULL, NULL ,NULL};
struct Node d = {NULL, &b, NULL};
struct Node e = {NULL, &a, &d};
struct Node f = {NULL, NULL, NULL};
struct Node g = {NULL, &e, &f};
int ret1 = btree_isbalanced_naive(&g);
printf("%s\n", ret1 ? "YES" : "NO");
int dpth = 0;
int ret2 = btree_isbalanced(&g, &dpth);
printf("%s : %d\n", ret2 ? "YES" : "NO", dpth);
return 0;
}
當(dāng)注釋掉大塊代碼時(shí)，使用"#if 0"比使用"/**/"要好，因?yàn)橛?/**/"做大段的注釋要防止被注釋掉的代碼中有嵌套的"/**/",這會(huì)導(dǎo)致注釋掉的代碼區(qū)域不是你想要的范圍，當(dāng)被注釋掉的代碼很大時(shí)容易出現(xiàn)這種情況，特別是過一段時(shí)間后又修改該處代碼時(shí)更是如此。
在這里順便對條件編譯（#ifdef, #else, #endif, #if等）進(jìn)行說明。以下分3種情況：
1. 情況1：
#ifdef _XXXX
...程序段1...
#else
...程序段2...
#endif
這表明如果標(biāo)識(shí)符_XXXX已被#define命令定義過則對程序段1進(jìn)行編譯；否則對程序段2進(jìn)行編譯。
2:情況2：
#ifndef _XXXX
...程序段1...
#else
...程序段2...
#endif
這里使用了#ifndef，表示的是if not def。當(dāng)然是和#ifdef相反的狀況（如果沒有定義了標(biāo)識(shí)符_XXXX，那么執(zhí)行程序段1，否則執(zhí)行程序段2）。
3：情況3：
#if 常量
...程序段1...
#else
...程序段2...
#endif
這里表示，如果常量為真（非0，隨便什么數(shù)字，只要不是0），就執(zhí)行程序段1，否則執(zhí)行程序段2。
C++中的operator new與new operator，看上去挺像的兩姐妹，卻有天壤之別。
operator new
（1） 只分配所要求的空間，不調(diào)用相關(guān)對象的構(gòu)造函數(shù)。當(dāng)無法滿足所要求分配的空間時(shí)，則
->如果有new_handler，則調(diào)用new_handler，否則
->如果沒要求不拋出異常（以nothrow參數(shù)表達(dá)），則執(zhí)行bad_alloc異常，否則
->返回0
（2） 可以被重載
（3） 重載時(shí)，返回類型必須聲明為void*
（4） 重載時(shí)，第一個(gè)參數(shù)類型必須為表達(dá)要求分配空間的大小（字節(jié)），類型為size_t
（5） 重載時(shí)，可以帶其它參數(shù)
new operator
（1） 調(diào)用operator new分配足夠的空間，并調(diào)用相關(guān)對象的構(gòu)造函數(shù)
（2） 不可以被重載
相應(yīng)地，operator delete與delete operator有相似的特性。
舉個(gè)例子
class X
{
public:
…………
static void* operator new(size_t size)
{
return ::operator new(size);
}
static void operator delete(void* pointee)
{
::operator delete(pointee);
}
…………
};
X* px = new X();
該行代碼中的new為new operator，它將調(diào)用類X中的operator new，為該類的對象分配空間，然后調(diào)用當(dāng)前實(shí)例的構(gòu)造函數(shù)。
delete px;
該行代碼中的delete為delete operator，它將調(diào)用該實(shí)例的析構(gòu)函數(shù)，然后調(diào)用類X中的operator delete，以釋放該實(shí)例占用的空間。
new operator與delete operator的行為是不能夠也不應(yīng)該被改變，這是C++標(biāo)準(zhǔn)作出的承諾。而operator new與operator delete和C語言中的malloc與free對應(yīng)，只負(fù)責(zé)分配及釋放空間。但使用operator new分配的空間必須使用operator delete來釋放，而不能使用free，因?yàn)樗鼈儗?nèi)存使用的登記方式不同。反過來亦是一樣。
你可以重載operator new和operator delete以實(shí)現(xiàn)對內(nèi)存管理的不同要求，但你不能重載new operator或delete operator以改變它們的行為。
當(dāng)重載operator new時(shí)，可以提供更多的參數(shù)，在new一個(gè)對象時(shí)，通過在關(guān)鍵字new后的括號(hào)傳遞額外的參數(shù)。比如以下的類
class A
{
public:
…………
static void* operator new(size_t size, const string& example)
{
cout << example << endl;
return ::operator new(size);
}
…………
};
A* pa = new (“This will be printed out in operator new”) A();
新標(biāo)準(zhǔn)的C++允許以這樣的方式傳遞一個(gè)名為nothrow的參數(shù)，以表明當(dāng)為該對象分配空間失敗時(shí)，不拋出異常，而是返回0，以兼容舊標(biāo)準(zhǔn)new的行為。比如
class B {};
B* pb = new (nothrow) B();
當(dāng)然這只能對那些使用默認(rèn)operator new操作符的類。對已經(jīng)重載了operator new的類（比如上面的X和A），如果不聲明能接受nothrow參數(shù)，自然無法享受C++標(biāo)準(zhǔn)帶來的禮物。
--------
我們經(jīng)常看到這么一句話： operator new 可以重載， placement new 不可重載。其實(shí)此處所說的不可重載應(yīng)該是指全局的 placement new 不可重載，對于類域中的 placement new 是可以重載的，而且只要重載了任何一種形式的 operator new 都應(yīng)該順便重載 placement new ， 即 void * operator new(std::size_t count, void *ptr) 。
操作符重載一般用于特定類型，名字解析過程同一般的函數(shù)重載。 Operator new 由于其特殊性，編譯器提供了默認(rèn)提供 6 種全局重載形式，同時(shí)還允許用戶提供自定義的全局 operator new ，其參數(shù)甚至可以和全局版本一樣，除全局 placement new 外。對于類域，任何形式的 new 都是可以重載的，包括 placement new 形式。
全局的 operator new( 函數(shù) ) 有六種重載形式
void *operator new(std::size_t count)
throw(std::bad_alloc); // 一般的版本
void *operator new(std::size_t count, // 兼容早版本的 new
const std::nothrow_t&) throw(); // 內(nèi)存分配失敗不會(huì)拋出異常
void *operator new(std::size_t count, void *ptr) throw(); //placement 版本
void *operator new[](std::size_t count) //
throw(std::bad_alloc);
void *operator new[](std::size_t count, //
const std::nothrow_t&) throw();
void *operator new[](std::size_t count, void *ptr) throw();
重載 operator new 規(guī)則
重載 operator new 的參數(shù)個(gè)數(shù)是可以任意的 , 只需要保證第一個(gè)參數(shù)為 size_t, 返回類型為 void * 即可 , 而且其重載的參數(shù)類型也不必包含自定義類型 . 更一般的說 , operator new 的重載更像是一個(gè)函數(shù)的重載 , 而不是一個(gè)操作符的重載 . 如：
全局重載示例：
void* operator new(size_t size) // 重載成功
{
printf("global new\n");
return malloc(size);
//return ::operator new(size); // 遞歸調(diào)用提示 (warning)
}
//void *operator new(std::size_t size, void *ptr) // 無法重載
//{
// printf("global new\n");
// return ::operator new(size,ptr);
//}
void * operator new(size_t size, const std::nothrow_t& e) // 重載成功 , 遞歸調(diào)用提示 (warning)
{
printf("global new\n");
return ::operator new(size, e);
}
一般形式的 operator new 重載示例：
void * operator new(size_t size, int x, int y, int z)
{
...
}
X * pX = new (1, 2, 3) X;
char data[1000][sizeof(foo)];
inline void* operator new(size_t size, int n)
{
return data[n];
}
就可以使用這樣有趣的語法來創(chuàng)建對象 :
foo *p=new(6) foo(); // 把對象創(chuàng)建在 data 的第六個(gè)單元上
時(shí)常在cpp的代碼之中看到這樣的代碼:
#ifdef __cplusplus
extern "C" {
#endif
//一段代碼
#ifdef __cplusplus
}
#endif
這樣的代碼到底是什么意思呢？首先，__cplusplus是cpp中的自定義宏，那么定義了這個(gè)宏的話表示這是一段cpp的代碼，也就是說，上面的代碼的含義是:如果這是一段cpp的代碼，那么加入extern "C"{和}處理其中的代碼。
要明白為何使用extern "C"，還得從cpp中對函數(shù)的重載處理開始說起。在c++中，為了支持重載機(jī)制，在編譯生成的匯編碼中，要對函數(shù)的名字進(jìn)行一些處理，加入比如函數(shù)的返回類型等等.而在C中，只是簡單的函數(shù)名字而已，不會(huì)加入其他的信息.也就是說:C++和C對產(chǎn)生的函數(shù)名字的處理是不一樣的.
比如下面的一段簡單的函數(shù)，我們看看加入和不加入extern "C"產(chǎn)生的匯編代碼都有哪些變化:
int f(void)
{
return 1;
}
在加入extern "C"的時(shí)候產(chǎn)生的匯編代碼是:
.file "test.cxx"
.text
.align 2
.globl _f
.def _f; .scl 2; .type 32; .endef
_f:
pushl %ebp
movl %esp， %ebp
movl $1， %eax
popl %ebp
ret
但是不加入了extern "C"之后
.file "test.cxx"
.text
.align 2
.globl __Z1fv
.def __Z1fv; .scl 2; .type 32; .endef
__Z1fv:
pushl %ebp
movl %esp， %ebp
movl $1， %eax
popl %ebp
ret
兩段匯編代碼同樣都是使用gcc -S命令產(chǎn)生的，所有的地方都是一樣的，唯獨(dú)是產(chǎn)生的函數(shù)名，一個(gè)是_f，一個(gè)是__Z1fv。
明白了加入與不加入extern "C"之后對函數(shù)名稱產(chǎn)生的影響，我們繼續(xù)我們的討論:為什么需要使用extern "C"呢？C++之父在設(shè)計(jì)C++之時(shí)，考慮到當(dāng)時(shí)已經(jīng)存在了大量的C代碼，為了支持原來的C代碼和已經(jīng)寫好C庫，需要在C++中盡可能的支持C，而extern "C"就是其中的一個(gè)策略。
試想這樣的情況:一個(gè)庫文件已經(jīng)用C寫好了而且運(yùn)行得很良好，這個(gè)時(shí)候我們需要使用這個(gè)庫文件，但是我們需要使用C++來寫這個(gè)新的代碼。如果這個(gè)代碼使用的是C++的方式鏈接這個(gè)C庫文件的話，那么就會(huì)出現(xiàn)鏈接錯(cuò)誤.我們來看一段代碼:首先，我們使用C的處理方式來寫一個(gè)函數(shù)，也就是說假設(shè)這個(gè)函數(shù)當(dāng)時(shí)是用C寫成的:
//f1.c
extern "C"
{
void f1()
{
return;
}
}
編譯命令是:gcc -c f1.c -o f1.o 產(chǎn)生了一個(gè)叫f1.o的庫文件。再寫一段代碼調(diào)用這個(gè)f1函數(shù):
// test.cxx
//這個(gè)extern表示f1函數(shù)在別的地方定義，這樣可以通過
//編譯，但是鏈接的時(shí)候還是需要
//鏈接上原來的庫文件.
extern void f1();
int main()
{
f1();
return 0;
}
通過gcc -c test.cxx -o test.o 產(chǎn)生一個(gè)叫test.o的文件。然后，我們使用gcc test.o f1.o來鏈接兩個(gè)文件，可是出錯(cuò)了，錯(cuò)誤的提示是:
test.o(.text + 0x1f):test.cxx: undefine reference to 'f1()'
也就是說，在編譯test.cxx的時(shí)候編譯器是使用C++的方式來處理f1()函數(shù)的，但是實(shí)際上鏈接的庫文件卻是用C的方式來處理函數(shù)的，所以就會(huì)出現(xiàn)鏈接過不去的錯(cuò)誤:因?yàn)殒溄悠髡也坏胶瘮?shù)。
因此，為了在C++代碼中調(diào)用用C寫成的庫文件，就需要用extern "C"來告訴編譯器:這是一個(gè)用C寫成的庫文件，請用C的方式來鏈接它們。
比如，現(xiàn)在我們有了一個(gè)C庫文件，它的頭文件是f.h，產(chǎn)生的lib文件是f.lib，那么我們?nèi)绻贑++中使用這個(gè)庫文件，我們需要這樣寫:
extern "C"
{
#include "f.h"
}
回到上面的問題，如果要改正鏈接錯(cuò)誤，我們需要這樣子改寫test.cxx:
extern "C"
{
extern void f1();
}
int main()
{
f1();
return 0;
}
重新編譯并且鏈接就可以過去了.
總結(jié)
C和C++對函數(shù)的處理方式是不同的.extern "C"是使C++能夠調(diào)用C寫作的庫文件的一個(gè)手段，如果要對編譯器提示使用C的方式來處理函數(shù)的話，那么就要使用extern "C"來說明。
LC-Display
| Time Limit: 1000MS | | Memory Limit: 10000K |
| Total Submissions: 10720 | | Accepted: 4221 |
Description
A friend of you has just bought a new computer. Until now, the most powerful computer he ever used has been a pocket calculator. Now, looking at his new computer, he is a bit disappointed, because he liked the LC-display of his calculator so much. So you decide to write a program that displays numbers in an LC-display-like style on his computer.
Input
The input contains several lines, one for each number to be displayed. Each line contains two integers s, n (1 <= s <= 10, 0 <= n <= 99 999 999), where n is the number to be displayed and s is the size in which it shall be displayed.
The input file will be terminated by a line containing two zeros. This line should not be processed.
Output
Output the numbers given in the input file in an LC-display-style using s "-" signs for the horizontal segments and s "|" signs for the vertical ones. Each digit occupies exactly s+2 columns and 2s+3 rows. (Be sure to fill all the white space occupied by the digits with blanks, also for the last digit.) There has to be exactly one column of blanks between two digits.
Output a blank line after each number. (You will find a sample of each digit in the sample output.)
Sample Input
2 12345
3 67890
0 0
Sample Output
-- -- --
| | | | | |
| | | | | |
-- -- -- --
| | | | |
| | | | |
-- -- --
--- --- --- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- ---
| | | | | | | |
| | | | | | | |
| | | | | | | |
--- --- --- ---Source
思路:
這題，不會(huì)...
無奈看其他人代碼，發(fā)現(xiàn)居然可以寫的這么簡潔...佩服...
代碼:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 10
5 int n;
6 char str[MAX_LEN];
7 const int mark[5][10][3] = {
8 /* 0 1 2 3 4 5 6 7 8 9 */
9 0,1,0, 0,0,0, 0,1,0, 0,1,0, 0,0,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0,
10 1,0,1, 0,0,1, 0,0,1, 0,0,1, 1,0,1, 1,0,0, 1,0,0, 0,0,1, 1,0,1, 1,0,1,
11 0,0,0, 0,0,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,1,0, 0,0,0, 0,1,0, 0,1,0,
12 1,0,1, 0,0,1, 1,0,0, 0,0,1, 0,0,1, 0,0,1, 1,0,1, 0,0,1, 1,0,1, 0,0,1,
13 0,1,0, 0,0,0, 0,1,0, 0,1,0, 0,0,0, 0,1,0, 0,1,0, 0,0,0, 0,1,0, 0,1,0 };
14
15 int
16 main(int argc, char **argv)
17 {
18 int j, k, p, q, w;
19 while(scanf("%d %s", &n, str) != EOF) {
20 if(!n)
21 break;
22 for(j=0; j<5; j++) {
23 if(j%2 == 0) {
24 for(p=0; str[p]!='\0'; p++) {
25 printf(" "); /* mark[j][k][0] */
26 k = str[p] - '0';
27 for(q=0; q<n; q++)
28 printf("%s", mark[j][k][1]?"-":" ");
29 printf(" "); /* mark[j][k][2] */
30 printf(" ");
31 }
32 printf("\n");
33 } else {
34 for(q=0; q<n; q++) {
35 for(p=0; str[p]!='\0'; p++) {
36 k = str[p] - '0';
37 printf("%s", mark[j][k][0]?"|":" ");
38 for(w=0; w<n; w++)
39 printf(" ");
40 printf("%s", mark[j][k][2]?"|":" ");
41 printf(" ");
42 }
43 printf("\n");
44 }
45 }
46 }
47 printf("\n");
48 }
49 return 0;
50 }
轉(zhuǎn)自：
http://hi.baidu.com/cive/blog/item/f6899418726669b44aedbcc9.html------------------------------------------------------------------------------------------------------------------
數(shù)在計(jì)算機(jī)中是以二進(jìn)制形式表示的。
數(shù)分為有符號(hào)數(shù)和無符號(hào)數(shù)。
原碼、反碼、補(bǔ)碼都是有符號(hào)定點(diǎn)數(shù)的表示方法。
一個(gè)有符號(hào)定點(diǎn)數(shù)的最高位為符號(hào)位，0是正，1是副。
以下都以8位整數(shù)為例，
原碼就是這個(gè)數(shù)本身的二進(jìn)制形式。
例如
0000001 就是+1
1000001 就是-1
正數(shù)的反碼和補(bǔ)碼都是和原碼相同。
負(fù)數(shù)的反碼是將其原碼除符號(hào)位之外的各位求反
[-3]反=[10000011]反=11111100
負(fù)數(shù)的補(bǔ)碼是將其原碼除符號(hào)位之外的各位求反之后在末位再加1。
[-3]補(bǔ)=[10000011]補(bǔ)=11111101
一個(gè)數(shù)和它的補(bǔ)碼是可逆的。
為什么要設(shè)立補(bǔ)碼呢？
第一是為了能讓計(jì)算機(jī)執(zhí)行減法：
[a-b]補(bǔ)=a補(bǔ)+（-b）補(bǔ)
第二個(gè)原因是為了統(tǒng)一正0和負(fù)0
正零：00000000
負(fù)零：10000000
這兩個(gè)數(shù)其實(shí)都是0，但他們的原碼卻有不同的表示。
但是他們的補(bǔ)碼是一樣的，都是00000000
特別注意，如果+1之后有進(jìn)位的，要一直往前進(jìn)位，包括符號(hào)位！（這和反碼是不同的！）
[10000000]補(bǔ)
=[10000000]反+1
=11111111+1
=(1)00000000
=00000000(最高位溢出了，符號(hào)位變成了0）
有人會(huì)問
10000000這個(gè)補(bǔ)碼表示的哪個(gè)數(shù)的補(bǔ)碼呢？
其實(shí)這是一個(gè)規(guī)定，這個(gè)數(shù)表示的是-128
所以n位補(bǔ)碼能表示的范圍是
-2^(n-1)到2^(n-1)-1
比n位原碼能表示的數(shù)多一個(gè)
又例：
1011
原碼：01011
反碼：01011 //正數(shù)時(shí)，反碼＝原碼
補(bǔ)碼：01011 //正數(shù)時(shí)，補(bǔ)碼＝原碼
-1011
原碼：11011
反碼：10100 //負(fù)數(shù)時(shí)，反碼為原碼取反
補(bǔ)碼：10101 //負(fù)數(shù)時(shí)，補(bǔ)碼為原碼取反＋1
0．1101
原碼：0.1101
反碼：0.1101 //正數(shù)時(shí)，反碼＝原碼
補(bǔ)碼：0.1101 //正數(shù)時(shí)，補(bǔ)碼＝原碼
-0．1101
原碼：1.1101
反碼：1.0010 //負(fù)數(shù)時(shí)，反碼為原碼取反
補(bǔ)碼：1.0011 //負(fù)數(shù)時(shí)，補(bǔ)碼為原碼取反＋1
總結(jié)：
在計(jì)算機(jī)內(nèi)，定點(diǎn)數(shù)有3種表示法：原碼、反碼和補(bǔ)碼
所謂原碼就是前面所介紹的二進(jìn)制定點(diǎn)表示法，即最高位為符號(hào)位，“0”表示正，“1”表示負(fù)，其余位表示數(shù)值的大小。
反碼表示法規(guī)定：正數(shù)的反碼與其原碼相同；負(fù)數(shù)的反碼是對其原碼逐位取反，但符號(hào)位除外。
補(bǔ)碼表示法規(guī)定：正數(shù)的補(bǔ)碼與其原碼相同；負(fù)數(shù)的補(bǔ)碼是在其反碼的末位加1。
1、原碼、反碼和補(bǔ)碼的表示方法
（1） 原碼：在數(shù)值前直接加一符號(hào)位的表示法。
例如： 符號(hào)位 數(shù)值位
[+7]原= 0 0000111 B
[-7]原= 1 0000111 B
注意：a. 數(shù)0的原碼有兩種形式：
[+0]原=00000000B [-0]原=10000000B
b. 8位二進(jìn)制原碼的表示范圍：-127～+127
2）反碼：
正數(shù)：正數(shù)的反碼與原碼相同。
負(fù)數(shù)：負(fù)數(shù)的反碼，符號(hào)位為“1”，數(shù)值部分按位取反。
例如： 符號(hào)位 數(shù)值位
[+7]反= 0 0000111 B
[-7]反= 1 1111000 B
注意：a. 數(shù)0的反碼也有兩種形式，即
[+0]反=00000000B
[- 0]反=11111111B
b. 8位二進(jìn)制反碼的表示范圍：-127～+127
3）補(bǔ)碼的表示方法
1）模的概念：把一個(gè)計(jì)量單位稱之為模或模數(shù)。例如，時(shí)鐘是以12進(jìn)制進(jìn)行計(jì)數(shù)循環(huán)的，即以12為模。在時(shí)鐘上，時(shí)針加上（正撥）12的整數(shù)位或減去（反撥）12的整數(shù)位，時(shí)針的位置不變。14點(diǎn)鐘在舍去模12后，成為（下午）2點(diǎn)鐘（14=14-12=2）。從0點(diǎn)出發(fā)逆時(shí)針撥10格即減去10小時(shí)，也可看成從0點(diǎn)出發(fā)順時(shí)針撥2格（加上2小時(shí)），即2點(diǎn)（0-10=-10=-10+12=2）。因此，在模12的前提下，-10可映射為+2。由此可見，對于一個(gè)模數(shù)為12的循環(huán)系統(tǒng)來說，加2和減10的效果是一樣的；因此，在以12為模的系統(tǒng)中，凡是減10的運(yùn)算都可以用加2來代替，這就把減法問題轉(zhuǎn)化成加法問題了（注：計(jì)算機(jī)的硬件結(jié)構(gòu)中只有加法器，所以大部分的運(yùn)算都必須最終轉(zhuǎn)換為加法）。10和2對模12而言互為補(bǔ)數(shù)。
同理，計(jì)算機(jī)的運(yùn)算部件與寄存器都有一定字長的限制（假設(shè)字長為8），因此它的運(yùn)算也是一種模運(yùn)算。當(dāng)計(jì)數(shù)器計(jì)滿8位也就是256個(gè)數(shù)后會(huì)產(chǎn)生溢出，又從頭開始計(jì)數(shù)。產(chǎn)生溢出的量就是計(jì)數(shù)器的模，顯然，8位二進(jìn)制數(shù)，它的模數(shù)為28=256。在計(jì)算中，兩個(gè)互補(bǔ)的數(shù)稱為“補(bǔ)碼”。
2）補(bǔ)碼的表示： 正數(shù)：正數(shù)的補(bǔ)碼和原碼相同。
負(fù)數(shù)：負(fù)數(shù)的補(bǔ)碼則是符號(hào)位為“1”，數(shù)值部分按位取反后再在末位（最低位）加1。也就是“反碼+1”。
例如： 符號(hào)位 數(shù)值位
[+7]補(bǔ)= 0 0000111 B
[-7]補(bǔ)= 1 1111001 B
補(bǔ)碼在微型機(jī)中是一種重要的編碼形式，請注意：
a.采用補(bǔ)碼后，可以方便地將減法運(yùn)算轉(zhuǎn)化成加法運(yùn)算，運(yùn)算過程得到簡化。正數(shù)的補(bǔ)碼即是它所表示的數(shù)的真值，而負(fù)數(shù)的補(bǔ)碼的數(shù)值部份卻不是它所表示的數(shù)的真值。采用補(bǔ)碼進(jìn)行運(yùn)算，所得結(jié)果仍為補(bǔ)碼。
b.與原碼、反碼不同，數(shù)值0的補(bǔ)碼只有一個(gè)，即 [0]補(bǔ)=00000000B。
c.若字長為8位，則補(bǔ)碼所表示的范圍為-128～+127；進(jìn)行補(bǔ)碼運(yùn)算時(shí)，應(yīng)注意所得結(jié)果不應(yīng)超過補(bǔ)碼所能表示數(shù)的范圍。
Anagram Groups
| Time Limit: 1000MS | | Memory Limit: 65536K |
| Total Submissions: 2318 | | Accepted: 649 |
Description
World-renowned Prof. A. N. Agram's current research deals with large anagram groups. He has just found a new application for his theory on the distribution of characters in English language texts. Given such a text, you are to find the largest anagram groups.
A text is a sequence of words. A word w is an anagram of a word v if and only if there is some permutation p of character positions that takes w to v. Then, w and v are in the same anagram group. The size of an anagram group is the number of words in that group. Find the 5 largest anagram groups.
Input
The input contains words composed of lowercase alphabetic characters, separated by whitespace(or new line). It is terminated by EOF. You can assume there will be no more than 30000 words.
Output
Output the 5 largest anagram groups. If there are less than 5 groups, output them all. Sort the groups by decreasing size. Break ties lexicographically by the lexicographical smallest element. For each group output, print its size and its member words. Sort the member words lexicographically and print equal words only once.
Sample Input
undisplayed
trace
tea
singleton
eta
eat
displayed
crate
cater
carte
caret
beta
beat
bate
ate
abet
Sample Output
Group of size 5: caret carte cater crate trace .
Group of size 4: abet bate beat beta .
Group of size 4: ate eat eta tea .
Group of size 1: displayed .
Group of size 1: singleton .
Source
思路:
這題將排序發(fā)揮到了極致啊呵呵，排序來排序去就AC了
代碼:
1 /* 47MS */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_NUM 30001
6 #define MAX_LEN 36
7 #define MAX_OUT 5
8 struct Word {
9 char word[MAX_LEN];
10 char word_cmp[MAX_LEN];
11 } words[MAX_NUM];
12
13 struct Summary {
14 struct Word *first;
15 int count;
16 } smmry[MAX_NUM];
17
18 int total, total_category;
19
20 int
21 cmp_char(const void *arg1, const void *arg2)
22 {
23 return (*(char *)arg1) - (*(char *)arg2);
24 }
25
26 int
27 cmp_words(const void *arg1, const void *arg2)
28 {
29 int ret = strcmp(((struct Word *)arg1)->word_cmp, ((struct Word *)arg2)->word_cmp);
30 if(ret == 0)
31 ret = strcmp(((struct Word *)arg1)->word, ((struct Word *)arg2)->word);
32 return ret;
33 }
34
35 int
36 cmp_category(const void *arg1, const void *arg2)
37 {
38 int ret = ((struct Summary *)arg2)->count - ((struct Summary *)arg1)->count;
39 if(ret == 0)
40 ret = strcmp(((struct Summary *)arg1)->first->word, ((struct Summary *)arg2)->first->word);
41 return ret;
42 }
43
44 int
45 main(int argc, char **argv)
46 {
47 int i, j, num, len;
48 total = total_category = 0;
49 while(scanf("%s", words[total].word) != EOF) {
50 len = strlen(words[total].word);
51 strcpy(words[total].word_cmp, words[total].word);
52 qsort(words[total].word_cmp, len, sizeof(char), cmp_char);
53 ++total;
54 }
55 qsort(words, total, sizeof(struct Word), cmp_words);
56
57 num = 1;
58 for(i=1; i<total; i++) {
59 if(strcmp(words[i].word_cmp, words[i-1].word_cmp) == 0)
60 ++num;
61 else {
62 smmry[total_category].first = words+i-num;
63 smmry[total_category].count = num;
64 ++total_category;
65 num = 1;
66 }
67 }
68 smmry[total_category].first = words+i-num;
69 smmry[total_category++].count = num;
70 qsort(smmry, total_category, sizeof(struct Summary), cmp_category);
71
72 total_category = total_category < MAX_OUT ? total_category : MAX_OUT;
73 for(i=0; i<total_category; i++) {
74 printf("Group of size %d: %s ", smmry[i].count, smmry[i].first->word);
75 for(j=1; j<smmry[i].count; j++)
76 if(strcmp((smmry[i].first+j)->word, (smmry[i].first+j-1)->word) != 0)
77 printf("%s ", (smmry[i].first+j)->word);
78 printf(".\n");
79 }
80 }