• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            A Za, A Za, Fighting...

            堅(jiān)信:勤能補(bǔ)拙

            題目來源: 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;
            }

             



            posted @ 2011-05-31 16:58 simplyzhao 閱讀(397) | 評論 (0)編輯 收藏
            題目出處: http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

            題目:定義棧的數(shù)據(jù)結(jié)構(gòu),要求添加一個(gè)min函數(shù),能夠得到棧的最小元素。要求函數(shù)minpush以及pop的時(shí)間復(fù)雜度都是O(1)
            #include "StackWithMin.h"
            #include
            <cstdio>
            #include
            <cstdlib>
            #include
            <cstring>

            const int StackWithMin::MAX_SIZE ;

            StackWithMin::StackWithMin() :
                top_index(
            -1), min_index(-1)
            {
                printf(
            "StackWithMin Constructor\n");
            }

            StackWithMin::
            ~StackWithMin()
            {
                printf(
            "StackWithMin Destructor\n");
            }

            int
            StackWithMin::top() 
            const
            {
                
            if(top_index == -1) {
                    printf(
            "top() failed: Stack Empty\n");
                    
            return -1;
                }

                
            return stack[top_index]; 
            }

            int
            StackWithMin::get_min() 
            const
            {
                
            if(min_index == -1) {
                    printf(
            "get_min() failed: Stack Empty\n");
                    
            return -1;
                }

                
            return stack[min_index];
            }

            void
            StackWithMin::push(
            int value)
            {
                
            if(top_index == -1) { /* stack empty */
                    stack[
            ++top_index] = value;
                    min_index 
            = top_index;
                    
            return;
                }
                stack[
            ++top_index] = value;
                
            if(value < stack[min_index]) {
                    index[top_index] 
            = min_index;
                    min_index 
            = top_index;
                }
            }

            int
            StackWithMin::pop()
            {
                
            if(top_index == -1) {
                    printf(
            "pop() failed: Stack Empty\n");
                    
            return -1;
                }
                
            int ret = stack[top_index];
                
            if(min_index == top_index)
                    min_index 
            = index[top_index];
                
            --top_index;
                
            return ret;
            }



            class StackWithMin
            {
                public:
                    StackWithMin();
                    ~StackWithMin();
                    int get_min() const;
                    int top() const;
                    void push(int value);
                    int pop();      
                private:
                    static const int MAX_SIZE = 101;
                    int top_index, min_index;
                    int stack[MAX_SIZE];
                    int index[MAX_SIZE];
            };









            posted @ 2011-05-25 15:49 simplyzhao 閱讀(262) | 評論 (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。

            posted @ 2011-05-24 15:24 simplyzhao 閱讀(531) | 評論 (0)編輯 收藏

            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è)單元上  

            posted @ 2011-05-24 14:12 simplyzhao 閱讀(464) | 評論 (0)編輯 收藏
            題目出處: http://zhedahht.blog.163.com/

            題目:輸入一棵二元查找樹,將該二元查找樹轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn),只調(diào)整指針的指向。

              比如將二元查找樹
               
                                                    10
                                                      /    \
                                                    6       14
                                                  /  \     /  \
                                                4     8  12    16
            轉(zhuǎn)換成雙向鏈表

            4=6=8=10=12=14=16


            思路:遞歸,在一時(shí)找不到遞歸的靈感的時(shí)候,多考慮考慮遞歸的參數(shù),有時(shí)更重要的是考慮遞歸的返回值
                  每處理一個(gè)節(jié)點(diǎn),首先獲取左子樹和右子樹所返回的鏈表,然后拼接

            代碼:
            #include<stdio.h>
            #include
            <string.h>
            #include
            <stdlib.h>

            /* Problem: Convert a binary search tree into a sorted linkedlist */
            /* When it comes to Tree-Structure, recursion is always the most common solution.
               When designing recursion solution, should consider:
                   1. the parameters
                   2(important). the return object
            */

            struct Node {
                
            int value;
                
            struct Node *left;
                
            struct Node *right;
            };

            struct Node *
            BTree2List(
            struct Node *root)
            {
                
            if(root == NULL)
                    
            return NULL;
                
            struct Node *ret = NULL;

                
            /* Convert the left tree into a sorted linkedlist */
                
            struct Node *l_linkedlist = BTree2List(root->left);
                ret 
            = l_linkedlist==NULL ? root : l_linkedlist;

                
            /* Convert the right tree into a sorted linkedlist */
                
            struct Node *r_linkedlist = BTree2List(root->right);
                
            while(l_linkedlist && l_linkedlist->right)
                    l_linkedlist 
            = l_linkedlist->right;

                
            /* Combine */
                
            if(l_linkedlist)
                    l_linkedlist
            ->right = root;
                root
            ->left = l_linkedlist;
                root
            ->right = r_linkedlist;
                
            if(r_linkedlist)
                    r_linkedlist
            ->left = root;
                
                
            return ret;
            }

            int main(int argc, char** argv)
            {
                
            struct Node a = {4, NULL, NULL};
                
            struct Node b = {8, NULL, NULL};
                
            struct Node c = {12, NULL, NULL};
                
            struct Node d = {16, NULL, NULL};
                
            struct Node e = {6, NULL, &b};
                
            struct Node f = {14&c, NULL};
                
            struct Node g = {10&e, &f};

                
            struct Node *ret = BTree2List(&g);
                
            while(ret && ret->right) {
                    ret 
            = ret->right;
                }

                
            while(ret) {
                    printf(
            "%d\n", ret->value);
                    ret 
            = ret->left;
                }

                
            return 0;
            }


            posted @ 2011-05-23 09:09 simplyzhao 閱讀(384) | 評論 (0)編輯 收藏

            時(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"來說明。

            posted @ 2011-05-22 17:57 simplyzhao 閱讀(270) | 評論 (0)編輯 收藏
            LC-Display
            Time Limit: 1000MSMemory Limit: 10000K
            Total Submissions: 10720Accepted: 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,00,0,00,1,00,1,00,0,00,1,00,1,00,1,00,1,00,1,0,
            10     1,0,10,0,10,0,10,0,11,0,11,0,01,0,00,0,11,0,11,0,1,
            11     0,0,00,0,00,1,00,1,00,1,00,1,00,1,00,0,00,1,00,1,0,
            12     1,0,10,0,11,0,00,0,10,0,10,0,11,0,10,0,11,0,10,0,1,
            13     0,1,00,0,00,1,00,1,00,0,00,1,00,1,00,0,00,1,00,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 }
            posted @ 2010-11-09 16:46 simplyzhao 閱讀(238) | 評論 (0)編輯 收藏
            轉(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ù)的范圍。

            posted @ 2010-11-05 17:53 simplyzhao 閱讀(245) | 評論 (0)編輯 收藏
            轉(zhuǎn)載:
            http://www.matrix67.com/blog/archives/263

            ------------------------------------------------------------------------------------------------------------------

            去年年底寫的關(guān)于位運(yùn)算的日志是這個(gè)Blog里少數(shù)大受歡迎的文章之一,很多人都希望我能不斷完善那篇文章。后來我看到了不少其它的資料,學(xué)習(xí)到了更多關(guān)于位運(yùn)算的知識(shí),有了重新整理位運(yùn)算技巧的想法。從今天起我就開始寫這一系列位運(yùn)算講解文章,與其說是原來那篇文章的follow-up,不如說是一個(gè)remake。當(dāng)然首先我還是從最基礎(chǔ)的東西說起。

            什么是位運(yùn)算?
                程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式儲(chǔ)存的。位運(yùn)算說穿了,就是直接對整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作。比如,and運(yùn)算本來是一個(gè)邏輯運(yùn)算符,但整數(shù)與整數(shù)之間也可以進(jìn)行and運(yùn)算。舉個(gè)例子,6的二進(jìn)制是110,11的二進(jìn)制是1011,那么6 and 11的結(jié)果就是2,它是二進(jìn)制對應(yīng)位進(jìn)行邏輯運(yùn)算的結(jié)果(0表示False,1表示True,空位都當(dāng)0處理):
                 110
            AND 1011
            ----------
                0010  -->  2

                由于位運(yùn)算直接對內(nèi)存數(shù)據(jù)進(jìn)行操作,不需要轉(zhuǎn)成十進(jìn)制,因此處理速度非常快。當(dāng)然有人會(huì)說,這個(gè)快了有什么用,計(jì)算6 and 11沒有什么實(shí)際意義啊。這一系列的文章就將告訴你,位運(yùn)算到底可以干什么,有些什么經(jīng)典應(yīng)用,以及如何用位運(yùn)算優(yōu)化你的程序。


            Pascal和C中的位運(yùn)算符號(hào)
                下面的a和b都是整數(shù)類型,則:
            C語言  |  Pascal語言
            -------+-------------
            a & b  |  a and b
            a | b  |  a or b
            a ^ b  |  a xor b
              ~a   |   not a
            a << b |  a shl b
            a >> b |  a shr b

                注意C中的邏輯運(yùn)算和位運(yùn)算符號(hào)是不同的。520|1314=1834,但520||1314=1,因?yàn)檫壿嬤\(yùn)算時(shí)520和1314都相當(dāng)于True。同樣的,!a和~a也是有區(qū)別的。


            各種位運(yùn)算的使用
                === 1. and運(yùn)算 ===
                and運(yùn)算通常用于二進(jìn)制取位操作,例如一個(gè)數(shù) and 1的結(jié)果就是取二進(jìn)制的最末位。這可以用來判斷一個(gè)整數(shù)的奇偶,二進(jìn)制的最末位為0表示該數(shù)為偶數(shù),最末位為1表示該數(shù)為奇數(shù).

                === 2. or運(yùn)算 ===
                or運(yùn)算通常用于二進(jìn)制特定位上的無條件賦值,例如一個(gè)數(shù)or 1的結(jié)果就是把二進(jìn)制最末位強(qiáng)行變成1。如果需要把二進(jìn)制最末位變成0,對這個(gè)數(shù)or 1之后再減一就可以了,其實(shí)際意義就是把這個(gè)數(shù)強(qiáng)行變成最接近的偶數(shù)。

                === 3. xor運(yùn)算 ===
                xor運(yùn)算通常用于對二進(jìn)制的特定一位進(jìn)行取反操作,因?yàn)楫惢蚩梢赃@樣定義:0和1異或0都不變,異或1則取反。
                xor運(yùn)算的逆運(yùn)算是它本身,也就是說兩次異或同一個(gè)數(shù)最后結(jié)果不變,即(a xor b) xor b = a。xor運(yùn)算可以用于簡單的加密,比如我想對我MM說1314520,但怕別人知道,于是雙方約定拿我的生日19880516作為密鑰。1314520 xor 19880516 = 20665500,我就把20665500告訴MM。MM再次計(jì)算20665500 xor 19880516的值,得到1314520,于是她就明白了我的企圖。
                下面我們看另外一個(gè)東西。定義兩個(gè)符號(hào)#和@(我怎么找不到那個(gè)圈里有個(gè)叉的字符),這兩個(gè)符號(hào)互為逆運(yùn)算,也就是說(x # y) @ y = x。現(xiàn)在依次執(zhí)行下面三條命令,結(jié)果是什么?
            x <- x # y
            y <- x @ y
            x <- x @ y

                執(zhí)行了第一句后x變成了x # y。那么第二句實(shí)質(zhì)就是y <- x # y @ y,由于#和@互為逆運(yùn)算,那么此時(shí)的y變成了原來的x。第三句中x實(shí)際上被賦值為(x # y) @ x,如果#運(yùn)算具有交換律,那么賦值后x就變成最初的y了。這三句話的結(jié)果是,x和y的位置互換了。
                加法和減法互為逆運(yùn)算,并且加法滿足交換律。把#換成+,把@換成-,我們可以寫出一個(gè)不需要臨時(shí)變量的swap過程(Pascal)。
            procedure swap(var a,b:longint);
            begin
               a:=a + b;
               b:=a - b;
               a:=a - b;
            end;

                好了,剛才不是說xor的逆運(yùn)算是它本身嗎?于是我們就有了一個(gè)看起來非常詭異的swap過程:
            procedure swap(var a,b:longint);
            begin
               a:=a xor b;
               b:=a xor b;
               a:=a xor b;
            end;


                === 4. not運(yùn)算 ===
                not運(yùn)算的定義是把內(nèi)存中的0和1全部取反。使用not運(yùn)算時(shí)要格外小心,你需要注意整數(shù)類型有沒有符號(hào)。如果not的對象是無符號(hào)整數(shù)(不能表示負(fù)數(shù)),那么得到的值就是它與該類型上界的差,因?yàn)闊o符號(hào)類型的數(shù)是用$0000到$FFFF依次表示的。下面的兩個(gè)程序(僅語言不同)均返回65435。
            var
               a:word;
            begin
               a:=100;
               a:=not a;
               writeln(a);
            end.

            #include <stdio.h>
            int main()
            {
                unsigned short a=100;
                a = ~a;
                printf( "%d\n", a );    
                return 0;
            }

                如果not的對象是有符號(hào)的整數(shù),情況就不一樣了,稍后我們會(huì)在“整數(shù)類型的儲(chǔ)存”小節(jié)中提到。

                === 5. shl運(yùn)算 ===
                a shl b就表示把a(bǔ)轉(zhuǎn)為二進(jìn)制后左移b位(在后面添b個(gè)0)。例如100的二進(jìn)制為1100100,而110010000轉(zhuǎn)成十進(jìn)制是400,那么100 shl 2 = 400。可以看出,a shl b的值實(shí)際上就是a乘以2的b次方,因?yàn)樵诙M(jìn)制數(shù)后添一個(gè)0就相當(dāng)于該數(shù)乘以2。
                通常認(rèn)為a shl 1比a * 2更快,因?yàn)榍罢呤歉讓右恍┑牟僮鳌R虼顺绦蛑谐艘?的操作請盡量用左移一位來代替。
                定義一些常量可能會(huì)用到shl運(yùn)算。你可以方便地用1 shl 16 - 1來表示65535。很多算法和數(shù)據(jù)結(jié)構(gòu)要求數(shù)據(jù)規(guī)模必須是2的冪,此時(shí)可以用shl來定義Max_N等常量。

                === 6. shr運(yùn)算 ===
                和shl相似,a shr b表示二進(jìn)制右移b位(去掉末b位),相當(dāng)于a除以2的b次方(取整)。我們也經(jīng)常用shr 1來代替div 2,比如二分查找、堆的插入操作等等。想辦法用shr代替除法運(yùn)算可以使程序效率大大提高。最大公約數(shù)的二進(jìn)制算法用除以2操作來代替慢得出奇的mod運(yùn)算,效率可以提高60%。


            位運(yùn)算的簡單應(yīng)用
                有時(shí)我們的程序需要一個(gè)規(guī)模不大的Hash表來記錄狀態(tài)。比如,做數(shù)獨(dú)時(shí)我們需要27個(gè)Hash表來統(tǒng)計(jì)每一行、每一列和每一個(gè)小九宮格里已經(jīng)有哪些數(shù)了。此時(shí),我們可以用27個(gè)小于2^9的整數(shù)進(jìn)行記錄。例如,一個(gè)只填了2和5的小九宮格就用數(shù)字18表示(二進(jìn)制為000010010),而某一行的狀態(tài)為511則表示這一行已經(jīng)填滿。需要改變狀態(tài)時(shí)我們不需要把這個(gè)數(shù)轉(zhuǎn)成二進(jìn)制修改后再轉(zhuǎn)回去,而是直接進(jìn)行位操作。在搜索時(shí),把狀態(tài)表示成整數(shù)可以更好地進(jìn)行判重等操作。這道題是在搜索中使用位運(yùn)算加速的經(jīng)典例子。以后我們會(huì)看到更多的例子。
                下面列舉了一些常見的二進(jìn)制位的變換操作。

                功能              |           示例            |    位運(yùn)算
            ----------------------+---------------------------+--------------------
            去掉最后一位          | (101101->10110)           | x shr 1
            在最后加一個(gè)0         | (101101->1011010)         | x shl 1
            在最后加一個(gè)1         | (101101->1011011)         | x shl 1+1
            把最后一位變成1       | (101100->101101)          | x or 1
            把最后一位變成0       | (101101->101100)          | x or 1-1
            最后一位取反          | (101101->101100)          | x xor 1
            把右數(shù)第k位變成1      | (101001->101101,k=3)      | x or (1 shl (k-1))
            把右數(shù)第k位變成0      | (101101->101001,k=3)      | x and not (1 shl (k-1))
            右數(shù)第k位取反         | (101001->101101,k=3)      | x xor (1 shl (k-1))
            取末三位              | (1101101->101)            | x and 7
            取末k位               | (1101101->1101,k=5)       | x and (1 shl k-1)
            取右數(shù)第k位           | (1101101->1,k=4)          | x shr (k-1) and 1
            把末k位變成1          | (101001->101111,k=4)      | x or (1 shl k-1)
            末k位取反             | (101001->100110,k=4)      | x xor (1 shl k-1)
            把右邊連續(xù)的1變成0    | (100101111->100100000)    | x and (x+1)
            把右起第一個(gè)0變成1    | (100101111->100111111)    | x or (x+1)
            把右邊連續(xù)的0變成1    | (11011000->11011111)      | x or (x-1)
            取右邊連續(xù)的1         | (100101111->1111)         | (x xor (x+1)) shr 1
            去掉右起第一個(gè)1的左邊 | (100101000->1000)         | x and (x xor (x-1))


                最后這一個(gè)在樹狀數(shù)組中會(huì)用到。


            Pascal和C中的16進(jìn)制表示
                Pascal中需要在16進(jìn)制數(shù)前加$符號(hào)表示,C中需要在前面加0x來表示。這個(gè)以后我們會(huì)經(jīng)常用到。

            整數(shù)類型的儲(chǔ)存
                我們前面所說的位運(yùn)算都沒有涉及負(fù)數(shù),都假設(shè)這些運(yùn)算是在unsigned/word類型(只能表示正數(shù)的整型)上進(jìn)行操作。但計(jì)算機(jī)如何處理有正負(fù)符號(hào)的整數(shù)類型呢?下面兩個(gè)程序都是考察16位整數(shù)的儲(chǔ)存方式(只是語言不同)。
            var
               a,b:integer;
            begin
               a:=$0000;
               b:=$0001;
               write(a,' ',b,' ');
               a:=$FFFE;
               b:=$FFFF;
               write(a,' ',b,' ');
               a:=$7FFF;
               b:=$8000;
               writeln(a,' ',b);
            end.

            #include <stdio.h>
            int main()
            {
                short int a, b;
                a = 0x0000;
                b = 0x0001;
                printf( "%d %d ", a, b );
                a = 0xFFFE;
                b = 0xFFFF;
                printf( "%d %d ", a, b );
                a = 0x7FFF;
                b = 0x8000;
                printf( "%d %d\n", a, b );
                return 0;
            }

                兩個(gè)程序的輸出均為0 1 -2 -1 32767 -32768。其中前兩個(gè)數(shù)是內(nèi)存值最小的時(shí)候,中間兩個(gè)數(shù)則是內(nèi)存值最大的時(shí)候,最后輸出的兩個(gè)數(shù)是正數(shù)與負(fù)數(shù)的分界處。由此你可以清楚地看到計(jì)算機(jī)是如何儲(chǔ)存一個(gè)整數(shù)的:計(jì)算機(jī)用$0000到$7FFF依次表示0到32767的數(shù),剩下的$8000到$FFFF依次表示-32768到-1的數(shù)。32位有符號(hào)整數(shù)的儲(chǔ)存方式也是類似的。稍加注意你會(huì)發(fā)現(xiàn),二進(jìn)制的第一位是用來表示正負(fù)號(hào)的,0表示正,1表示負(fù)。這里有一個(gè)問題:0本來既不是正數(shù),也不是負(fù)數(shù),但它占用了$0000的位置,因此有符號(hào)的整數(shù)類型范圍中正數(shù)個(gè)數(shù)比負(fù)數(shù)少一個(gè)。對一個(gè)有符號(hào)的數(shù)進(jìn)行not運(yùn)算后,最高位的變化將導(dǎo)致正負(fù)顛倒,并且數(shù)的絕對值會(huì)差1。也就是說,not a實(shí)際上等于-a-1。這種整數(shù)儲(chǔ)存方式叫做“補(bǔ)碼”。
            posted @ 2010-11-05 17:04 simplyzhao 閱讀(315) | 評論 (0)編輯 收藏
            Anagram Groups
            Time Limit: 1000MSMemory Limit: 65536K
            Total Submissions: 2318Accepted: 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 }
            posted @ 2010-11-05 15:38 simplyzhao 閱讀(617) | 評論 (0)編輯 收藏
            僅列出標(biāo)題
            共21頁: First 3 4 5 6 7 8 9 10 11 Last 

            導(dǎo)航

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            統(tǒng)計(jì)

            常用鏈接

            留言簿(1)

            隨筆分類

            隨筆檔案

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            久久综合香蕉国产蜜臀AV| 伊人久久大香线蕉AV一区二区| 久久国产成人精品麻豆| 色综合久久中文色婷婷| 久久人人添人人爽添人人片牛牛| 久久亚洲精品无码aⅴ大香| 99久久精品国产一区二区蜜芽| 中文字幕久久波多野结衣av| 精品久久久久久国产免费了| 亚洲色欲久久久综合网| 91视频国产91久久久| 久久亚洲AV成人无码国产| 亚洲一本综合久久| 2020国产成人久久精品| 久久国产精品久久久| 伊人久久五月天| 久久久久无码中| 国产福利电影一区二区三区久久老子无码午夜伦不 | 久久精品国产亚洲麻豆| 日本高清无卡码一区二区久久| 亚洲国产二区三区久久| 久久午夜福利无码1000合集| 久久91精品国产91久久户| 久久成人小视频| 99久久99久久精品国产片| 囯产精品久久久久久久久蜜桃| 成人免费网站久久久| 国产成人综合久久精品红 | 婷婷久久五月天| 99热精品久久只有精品| 久久久久亚洲AV无码网站| 久久大香香蕉国产| 狠狠色丁香久久婷婷综合_中| 蜜桃麻豆www久久| 99久久99久久久精品齐齐| 国产成人无码精品久久久性色 | 国产精品免费久久| 国产成人久久精品一区二区三区| 久久成人国产精品| 久久伊人精品一区二区三区| 久久露脸国产精品|