长驱直入骑士帮

目录与文件属性:编写ls 习题

Tue, 16 Mar 2010 23:33:43 +0800

3.3 每个用户都有用户名,每个用户名都有对应的用户ID,是否可能两个不同的用户名对应一个相同的ID?是否允许同一个用户拥有两个不同的 ID?如果有root权限,可以试一试,创建两个用户,改成同一个ID,但有不同的用户名和密码,这两个用户是否可以修改对方的文件?who输出什么?ls -l输出什么?命令id输出什么?相互发送Email呢?从中能够看出些什么?多个用户使用同一个ID还有什么其它用途?

a.两个不同的用户名可以对应一个相同的ID.
添加名为beta的用户到系统中，并更改密码

useradd beta
passwd beta

查看alpha,beta的id信息

id alpha
id beta

通过修改/etc/passwd文件改变beta的uid

vi /etc/passwd

改变test文件的用户和组属性

chown beta:beta test

以下是一系列测试

ls -l test
$ ls -l test
-rw-r--r-- 1 alpha beta 28 2010-02-19 18:23 test
$ id alpha
uid=1000(alpha) gid=1000(alpha) 组=1000(alpha),4(adm),20(dialout),24(cdrom),46(plugdev),106(lpadmin),121(admin),122(sambashare),125(uml-net)
$ id beta
uid=1000(alpha) gid=1000(alpha) 组=1000(alpha)
$ ./who2
beta     tty2     Feb 19 18:21
alpha    tty7     Feb 19 18:27
alpha    pts/0    Feb 19 18:47

b.同一个用户不能拥有两个ID.即使在/etc/passswd中添加另一个ID,系统也只使用第一条记录.

c.不同用户名对应一个相同的UID,相互发送Email:
如果内部程序以用户名为依据,alpha与beta各自接收自己的邮件
如果以 UID为依据,alpha与beta会同时接收对方的邮件
从中可以看到程序设计方面可以依据于用户名或UID,两种方式有各自的优点.

3.4 与普通的文件一样,目录也有特殊属性位,其中包含set-user-ID和set-group-ID位,使set-user-ID有效对目录有什么影响,如果有,那么是什么?为什么?如果没有影响,那么你能想象出这些位有什么作用吗?

a.set- user-ID对目录没有影响.
b.set-group-ID对目录有影响.

例如:
root用户:
mkdir /test
chmod 777 /test
test用户:
touch /test/test1
ls -l /test/test1
-rw-r--r-- 1 test1 test2 0 2009-01-17 23:31 /test/test1
设置set-group-ID位:
chmod 2777 /test
test 用户:
touch /test/test2
ls -l /test/*
-rw-r--r-- 1 test1 test2 0 2009-01-17 23:31 /test/test1
-rw-r--r-- 1 test1 root 0 2009-01-17 23:33 /test/test2
测试结果说明,用目录设置了set-group-ID位,在该目录下新建文件的组同父目录的组一致.

3.5 每个文件的执行权限都可以被打开或关闭,假设一个纯文本文件具有执行权限,它是否可以被执行,如果一个包含可执行代码的文件,如对 C语言编译后的可执行文件a.out,没有执行权限的话,它是否可以被执行?讨论执行权限和可执行代码之间的区别.它们之间的关系吗?参见命令file的联机帮助
解答:
1)它可以执行,它是以Shell script的方式执行.
2)对C语言编译的可执行文件a.out,没有执行权限是不可以被执行的.
3)执行权限本身是一种存储在inode中的数据结构.可执行代码仅是物理文件内部的一种组织结构.
例如用file查看文件类型:
file /etc/passwd /bin/ls
/bin/ls: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), for GNU/Linux 2.6.8, dynamically linked (uses shared libs), stripped
/etc/passwd: ASCII text
用objdump名字查看可执行文件的头信息 :
objdump -xd /bin/ls|more
/bin/ls: file format elf32-i386
/bin/ls
architecture: i386, flags 0x00000112:
EXEC_P, HAS_SYMS, D_PAGED
start address 0x08049a80

3.6 每个用户都有用户名和用户ID,这可以被认为是两种标识系统,为什么要这样?能不能直接用户名来表示文件所有者?为什么?能不能只用其中一种标识系统?两套表示系统有什么优缺点?如果由你来设计系统,你会如何设计?
解答:
1)两种标识系统分别针对于用户管理与系统管理.
2)不能用用户名来表示文件所有者,因为文件的所有者与所属组存储于inode节点中.
使用用户名管理系统只是方便于用户层面的应用管理.而内核用inode节点中的uid和gid管理文件和识别文件所有者
3)Unix/Linux一直沿用这两套管理方式来管理文件所有者.而Windows系统则沿用用户名的管理方式.
UNIX的管理方式,主要优点是授权与管理更集中于用户及UID上.比如uid为0代表 Root用户权限.而另外一个用户如果UID为0,即
同样拥有Root权限,这一切不依赖于用户名.
而WINDOWS管理方式如果要达到以上的效果,只能用组的方式来管理,即将要授权的用户归属于administrators组.
4)系统的设计是一个全方面的设计过程,依据于对文件,对inode,对用户的管理等等.
而一部系统应该包括有用户名和用户名对应的ID,而对应用层面有效的管理应该用用户名,而系统内部的运行和执行流程的控制
应该用ID.

3.7 命令dirent的联机帮助中提到了系统调用getdents(2),它的功能是什么?与readdir有什么关系?
解答:
man getdents
This is not the function you are interested in. Look at readdir(3) for
       the POSIX conforming C library interface. This page documents the bare
       kernel system call interface.
       The system call getdents() reads several dirent structures from the
       directory pointed at by fd into the memory area pointed to by dirp.
       The parameter count is the size of the memory area.
int getdents(unsigned int fd, struct dirent *dirp, unsigned int count);
其中fd为指向目录文件的文件描述符，该函数根据fd所指向的目录文件读取相应dirent结构，并放入dirp中，其中count为dirp中返回的数据量，正确时该函数返回值为填充到dirp的字节数当查询文件或者目录的相关信息时，Linux系统用sys_getedents 来执行相应的查询操作，并把得到的信息传递给用户空间运行的程序该调用返回的项的格式和struct dirent 不同，因此用户应该尽量使用可移植的POSIX 函数 readdir
struct dirent *readdir(DIR *dir)读取目录,返回一个指向目录的当前记录的指针.

3.8 命令ls -l的输出中有这样的一项drwxr-xr-x,表示这是一个目录,它的文件甩有者有全部权限,组用户和其它用户只有读和执行的权限,对于文件而言,执行权限意味着计算机可以执行其中包含的机器代码或脚本语句,对于目录而言,执行权限有什么意思?可以用chmod来关掉这个目录的执行权限.看看会发生什么?
解答:
目录有读权限可以列出目录的文件,即有读权限可以读取directory数据结构中的内容,反之则不能
读取目录信息,比如:ls -l /test/
ls: cannot open directory /test/: Permission denied
目录有写权限,即有写权限写入到directory数据结构中.反之则不能写入到目录中.比如:
touch test
touch: cannot touch `test': Permission denied
目录有执行权限,即有进入到目录的权限.反之则不能进入目录.比如:
cd /test/
-su: cd: /test/: Permission denied

用户、文件操作与联机帮助---习题解答

Mon, 08 Feb 2010 20:30:59 +0800

感谢超级玛丽博客的帮助。
2.1 在UNIX中有一个w命令,这个命令与who有关,运行这个命令,并阅读它的联想帮助,找出它提供了哪些who没有提供的信息?
其中有哪些信息来自utmp这个文件,这些信息各是什么含义?其他信息来自哪里?

w - Show who is logged on and what they are doing.
    例如，按下w后的输出为：
15:04:04 up 2 min, 2 users, load average: 1.02, 0.63, 0.24
USER     TTY      FROM              LOGIN@   IDLE   JCPU   PCPU WHAT
alpha    tty7     :0               15:02    2:17 11.06s 0.13s gnome-session
alpha    pts/0    :0.0             15:04    0.00s 0.35s 0.01s w
    而按下who后的输出为：
alpha    tty7         2010-02-04 15:02 (:0)
alpha    pts/0        2010-02-04 15:04 (:0.0)
    手册中提示到:
    The header shows, in this order, the current time,
how long the system has been running, how many users are currently
logged on, and the system load averages for the past 1, 5, and 15 minutes.
    信息来自/var/run/utmp和/proc两个文件。

2.2 用户登录的时候,登录信息会被记录在utmp文件中,在注销的时候，文件中相应的记录会被删除.如果用户正在使用系统的时候，系统突然崩溃，很明显，这时候utmp文件的内容会有问题，在系统重新启动的时候，会对utmp做文件处器呢？系统会不会重新为每一条可用终端建立记录？查阅相关的联机帮助和头文件，以及启动脚本，来找出上述问题的答案，可以在自己的机器上做实验来验证自己的想法.

囿于目前所知，在ＵＢＵＮＴＵ系统下面找不到有帮助的信息，貌似ＵＢＵＮＴＵ的启动同其他Ｌｉｎｕｘ发行版本有很大不同。
以下是来自超级玛丽博客的解答：

系统引导的时候，会执行/etc/rc.sysinit脚本文件.
在/etc/rc.sysinit脚本文件中找到以下行.
# Clean up utmp/wtmp
> /var/run/utmp
touch /var/log/wtmp
chgrp utmp /var/run/utmp /var/log/wtmp
chmod 0664 /var/run/utmp /var/log/wtmp
说明在重新启动的时候，系统会清空/var/run/utmp文件，系统不会重新为每一条可用终端建立记录. 对wtmp文件，如果有wtmp文件，同步时间戳，没有wtmp文件，则新建空的wtmp文件.
utmp文件是当前系统中，用户连线的记录，用户LOGIN则插入记录到utmp文件，LOGOUT则删除记录.用w/who命令可查看. wtmp文件是系统记录用户登入/登出历史.用 last命令可查看.

2.3 做个实验，把一个文件复制到/dev/tty:cp1 cp1.c /dev/tty .这时复制的目标文件是一个终端。对终端的读写操作与一个普通文件进行读写是一样的.接下来做实验，从终端读，这时会从键盘读写字符。然后写入到文件中，输入是以回车符+[CTRL-D] 作为结束标志的.

    /dev/tty 是当前的终端.
    ./cp1 cp1.c /dev/tty 将cp1.c文件中的内中输出到当前终端上.
    同样的，./cp1 /dev/tty test 将当前终端上的内容输出到test文件中.

2.4 标准C函数如fopen,getc,fclose,fgets的实现都包含内核级的缓冲,它们用到了一个结构FILE，并以此为基础构造了类似 utmplib的中间层,在头文件中找到结构FILE的成员描述。将其与utmplib.c中的变量做比较.

stdio.h中显示:

typedef struct _IO_FILE FILE

struct _IO_FILE {
  int _flags;        /* High-order word is _IO_MAGIC; rest is flags. */
#define _IO_file_flags _flags

  /* The following pointers correspond to the C++ streambuf protocol. */
  /* Note:  Tk uses the _IO_read_ptr and _IO_read_end fields directly. */
  char* _IO_read_ptr;    /* Current read pointer */
  char* _IO_read_end;    /* End of get area. */
  char* _IO_read_base;    /* Start of putback+get area. */
  char* _IO_write_base;    /* Start of put area. */
  char* _IO_write_ptr;    /* Current put pointer. */
  char* _IO_write_end;    /* End of put area. */
  char* _IO_buf_base;    /* Start of reserve area. */
  char* _IO_buf_end;    /* End of reserve area. */
  /* The following fields are used to support backing up and undo. */
  char *_IO_save_base; /* Pointer to start of non-current get area. */
  char *_IO_backup_base;  /* Pointer to first valid character of backup area */
  char *_IO_save_end; /* Pointer to end of non-current get area. */

  struct _IO_marker *_markers;

  struct _IO_FILE *_chain;

  int _fileno;
#if 0
  int _blksize;
#else
  int _flags2;
#endif
  _IO_off_t _old_offset; /* This used to be _offset but it's too small.  */

#define __HAVE_COLUMN /* temporary */
  /* 1+column number of pbase(); 0 is unknown. */
  unsigned short _cur_column;
  signed char _vtable_offset;
  char _shortbuf[1];

  /*  char* _save_gptr;  char* _save_egptr; */

  _IO_lock_t *_lock;
#ifdef _IO_USE_OLD_IO_FILE
};

我们在utmplib.h有起到类似作用的变量：

#define NRECS 16
#define UTSIZE (sizeof utmp)

static char utmpbuf[NRCES*UTSIZE];
static int  fd_utmp;
static int cur_rec;
static int num_recs;

注意到，带有buf字眼的char* _IO_buf_base，char* _IO_buf_end用来描述缓冲取区的，这与utmplib.h中的utmpbuf的作用类似。

p.s:

open()和fopen()的区别：

前者属于低级IO，后者是高级IO。
前者返回一个文件描述符(用户程序区的)，后者返回一个文件指针。
前者无缓冲，后者有缓冲。
前者与 read, write 等配合使用，后者与 fread, fwrite等配合使用。
后者是在前者的基础上扩充而来的，在大多数情况下，用后者。
open 是系统调用 fopen是C的库函数。

2.5 怎么来确定数据已经被写到磁盘上(不是被缓冲)?采用缓冲技术时，内核会把要写入磁盘的数据放在缓冲区，然后在它认为合适的时候定候写入磁盘。阅读相应的联机帮助，找到能够确定地把数据写入磁盘的方法.

A successful return from write() does not make any guarantee that data has been committed to disk. In fact, on some buggy implementations, it does not even guarantee that space has successfully been reserved for the data. The only way to be sure is to call fsync(2) after you are done writing all your data.

2.6 UNIX允许一个文件同时被多个进程打开，也允许一个进程同时打开好几个文件，做多次打开文件的实验:
(1)以读的方式打开文件
(2)以写的方式打开文件
(3)再次以读的方式打开文件
这时有3个文件描述符，接下来:
(4)从第一个文件描述符(以下简称fd)中读 20字符，显示读到的内容.
(5)从第二个fd写入"testing 123...".
(6)从第三个fd读出20字符，显示读到的内容.

源程序如下：

#include <stdio.h>
#include <fcntl.h>
#include <stdlib.h>

#define PATH_FILE "/tmp/test"
#define PATH_TTY "/dev/tty"
#define SHOW_NUM 20

int main(int argc,char* argv[]){
    int firstfd,secondfd,thirdfd,ttyfd,n_chars;
    char showrow[SHOW_NUM];
    char writrow[]={"testing 123..."};

    if((firstfd=open(PATH_FILE,O_RDONLY))==-1){
        perror(PATH_FILE);
        exit(1);
    }

    if((secondfd=open(PATH_FILE,O_WRONLY))==-1){
        perror(PATH_FILE);
        exit(1);
    }

    if((thirdfd=open(PATH_FILE,O_RDONLY))==-1){
        perror(PATH_FILE);
        exit(1);
    }

    if((ttyfd=open(PATH_TTY,O_RDWR))==-1){
        perror(PATH_FILE);
        exit(1);
    }

    n_chars=read(firstfd,&showrow,SHOW_NUM);
    printf("Read 20 chars from test file... \n");
    if(write(ttyfd,&showrow,SHOW_NUM)!=n_chars){
        fprintf(stderr,"Error:Write error to");
        perror(PATH_TTY);
    }

    printf("\nWrite chars to test file... \n");
    if(write(secondfd,&writrow,sizeof(writrow))!=sizeof(writrow)){
        fprintf(stderr,"Error:Write error to");
        perror(PATH_FILE);
    }

    printf("Read 20 chars from test file... \n");
    n_chars=read(thirdfd,&showrow,SHOW_NUM);
    if(write(ttyfd,&showrow,SHOW_NUM)!=n_chars){
        fprintf(stderr,"Error:Write error to");
        perror(PATH_TTY);
    }
    printf("\n");


    close(firstfd);
    close(secondfd);
    close(thirdfd);
    close(ttyfd);
    exit(0);
}

运行结果如下：
Read 20 chars from test file...
(一月 01, 2010 23:
Write chars to test file...
Read 20 chars from test file...
testing 123...0 23:

2.7 联机帮助man中可以查看关于命令,系统调用,系统设备等帮助信息，如何才能了解man 的使用方法,在你的系统中，man分为几个小节?它们分别是什么?

输入命令man man，看到man分为九节：

       1   Executable programs or shell commands
       2   System calls (functions provided by the kernel)
       3   Library calls (functions within program libraries)
       4   Special files (usually found in /dev)
       5   File formats and conventions eg /etc/passwd
       6   Games
       7   Miscellaneous (including macro packages and conven-
           tions), e.g. man(7), groff(7)
       8   System administration commands (usually only for root)
       9   Kernel routines [Non standard]

2.8 本章提到文件 utmp中还包含了一些记录,它们与已登录用户的信息无关，那么它们存放的是什么？各代表什么含义?

参看man utmp.

2.9 lseek可以将文件指针移动文件的末尾以后，如:
lseek(fd,100,SEEK_END)
将指针移动文件末尾再往后100个字节的地方。如果从文件末尾以后100个字符的地方开始读会出现什么情况。如果从文件末尾以后100个字符的地方开始写会出现什么情况？从100字节增加到20000字符，再写入"hello"看看会有什么结果,用ls -l来检查文件的长度，再用ls -s试试.

     将指针移动文件末尾再往后100个字节的地方。如果从文件末尾以后100个字符的地方开始读会出现读失败的情况.
     从100个字符的地方开始写会出现,在100个字符之后写入新的字符情况.如指针移动100个字符，再写入100个字符，就是文件大小增加100,又增加写入的100个字符,共200个字符.
     从100个字节增加到20000字符，再写入hello，用ls -l 检查,文件大小为20005个字节。用cat打印文件，只打印出hello字样.
用ls -s查看，返回4,只由用4个block的大小.

基于链接法的散列表的c++实现

Fri, 31 Jul 2009 20:56:50 +0800

我们知道,散列表解决冲突的时候分为开散列和闭散列两种方法.其中,开散列其实就是链接法(chaining),而闭散列就是开放寻址法(open addressing).开放寻址法根据寻找下一个桶的方法分为线性探查法(linear probing)、二次探查法(quadratic probing)、双散列法.这些方法的性能如下图所示:

可以看出,链接法的性能十分理想.以下即为基于链接法的散列表的模版类,其中仅仅包含了Insert,Search,Delete三个操作:

   1: int hash(int key){   2:     return key%7;   3: }   4:     5: template<class E,class K >   6: struct HashNode{   7:     E ele;   8:     K key;   9:     HashNode<E,K>* link;  10:     HashNode(HashNode<E,K>* ptr=NULL) {link=ptr;}  11:     HashNode(const E& e1,K k1,HashNode<E,K>* ptr=NULL){  12:         ele=e1; key=k1; link=ptr;  13:     }  14: };  15:    16:    17: template<class E,class K>  18: class ChainedHash{  19:     public:  20:         void Init(int s){  21:             Size=s;   22:             HNArray=new HashNode<E,K>* [Size];  23:             for(int i=0;i<Size;i++) {  24:                 HNArray[i]=new HashNode<E,K>(NULL);  25:                }  26:             }  27:         bool Insert(E& e1,K k1);  28:         bool Search(E& e1,K k1);  29:         bool Delete(E& e1,K k1);  30:     protected:  31:         int Size;  32:         HashNode<E,K>* * HNArray;   33: };  34:    35: template <class E,class K>  36: bool ChainedHash<E,K>::Insert(E& e1,K k1){  37:     HashNode<E,K>* p=new HashNode<E,K>(e1,k1,NULL);  38:     HashNode<E,K>* temp=HNArray[hash(k1)];   39:     if(temp->link==NULL){  40:         temp->link=p; delete temp; return true;}  41:     if(temp->link!=NULL){  42:         p->link=temp->link; temp->link=p; delete temp;   43:         return true;}  44: }  45:    46: template<class E,class K>  47: bool ChainedHash<E,K>::Search(E& e1,K k1){   48:     HashNode<E,K>* temp=HNArray[hash(k1)];  49:     while(temp!=NULL){  50:         if(temp->key==k1) {e1=temp->ele; return true;}  51:             else temp=temp->link;  52:     }  53:         return false;  54: }  55:    56: template<class E,class K>  57: bool ChainedHash<E,K>::Delete(E& e1,K k1){  58:     HashNode<E,K>* temp=HNArray[hash(k1)];  59:     while(temp!=NULL){  60:         if(temp->link->key==k1) {  61:             e1=temp->link->ele;   62:             HashNode<E,K>* p=temp->link;  63:             temp->link=p->link;   64:             p->link=NULL;  65:             delete p;  66:                 return true;  67:         }  68:         else temp=temp->link;  69:     }  70:     return false;  71: }

Windows下安装GCC4.4.0

Sat, 25 Jul 2009 11:53:21 +0800

在POJ1002的AC过程中,经历了数次的RE,郁闷不已.百思不得其解的时候,换了个台州大学的JO系统,一次提交就AC了,我就更加不解了.郁闷中忽然想起,北大的系统g++的版本是4.4.0,而我本地用的是3.4.5,于是回POJ把编译器换成C++,一次通过.随后,我试图查询台大的G++版本,但没有成功.

无论如何,编译器的版本,已经影响到我的ACM之路了,于是下定决心升级GCC.其实我在两个月前就试图升级,但没有成功.找到这篇博客: （原创）安装GCC4.4攻略(带MinGW),按照上面的提示,经过繁复的下载,解压后终于得到一个mingw文件夹,没有添加path,兴奋地测试了Hello World!程序,但是系统却提示"没有找到libgcc_s_dw2-1.dll组件",又是一段时间的郁闷.

在郁闷中继续寻找解决方案,在上面那篇博客中发现提到了什么tdm’s gcc/mingw,于是到网站Twilight Dragon Media,总算找到了一个好东西tdm-mingw-1.905.0-webdl.exe.这是一个类似于mingw-5.1.3.exe的安装程序,我选择了TDM's GCC/ALL Languages的安装选项,注意在选择下载镜像的时候,选择台湾省的NCHC服务器(赞台湾省的高等院校一个,看看台湾同胞为世界的开源事业做的贡献,鄙视一下大陆的高等院校的奉献观念),速度很快,一路next完,等待程序的自动下载,安装.安装完成后,迫不及待的在run了一遍Hello World!程序,一切顺利.

不过,等到我拿原来在3.4.5下编译通过的1002的代码在4.4.0下编译时,居然也顺利通过,但是放到POJ上,依然提示RE,估计是POJ的G++系统设置有错误,这就是我无法解决的了.

以下是我安装GCC4.4.0的总结:

1.Mingw-5.1.4.exe可以顺利安装GCC3.4.5,无法安装GCC4.4.0,但是3.4.5还是比较稳定的版本,有许多来不及升级到4.4.0的JO系统还在使用这一版本,因此兼容性有保证.

2.手动安装的官方GCC4.4.0可以编译源文件,但是需要注意编译命令有所改变,原来的 g++ –g example.cpp –o example的命令会生成一个较3.4.5下的相同命令大的多的可执行程序(Hello World!经4.4.0编译可以达到3.9M,但在3.4.5下相同的命令只有400K),如果想要减小可执行程序的体积,要用 g++ –s example.cpp –o example,可以达到与3.4.5下的-g命令相同的效果,但是注意以上两个命令都是动态链接库,如果生成的可执行程序的文件夹中不包含libgcc_s_dw2-1.dll,会无法运行程序,解决问题的方法是在原有的命令后添加-static是的编译时选择静态链接.

3.TDM's GCC由于是第三方编译,因此在使用感受上与由Mingw-5.1.4.exe安装的官方GCC3.4.5版本一模一样,可以说是最佳选择.

4.刚刚才发现GCC4.4.1竟然已经发布了,追逐技术的脚步有时是一件费力又不讨好的事,目前还不值得为0.0.1的升级去折腾,不过回望过去,GCC4.4.0是4月22日发布,而TDM's GCC4.4.0是5月1日发布,就是说过十天左右,TDM将发布相应的版本,到时再下不迟.

POJ1442解题报告

Thu, 23 Jul 2009 23:02:58 +0800

近日看了CLRS的不朽巨著<算法导论>的第六章,冲动地想立刻实现.于是,拿起键盘一蹴而就,写完堆的代码,g++竟然一遍通过.不得不佩服的CLRS的言简意赅,书上代码的简洁通用.当然,简洁的代码可能在健壮性上有所欠缺,但是对于具体的问题却是又好又快的解决方案.因此,CLRS的 <算法导论>尤其适合用来做ACM的题目.

实现完堆以后,总觉得终究需要习题的磨练,于是上POJ上找寻用堆来做的题目,找到了1442 Black Box 问题.用了将近一刻钟读懂题目,题目还是很好理解的,测试数据将一个数组的数据依次给出,在其中某个时刻要求你给出当前所有已给的数据中按从小到大排排在第i位的数据.思路还是很快可以形成的:每次用插入排序将所有已给的数据排序.但这样一个很大的问题就是,插入排序在交换数组数据的位置时浪费了太多的时间,必然会 TLE.堆排序也同样会遭遇这样的处境,解决问题的关键在于,为什么一定要给数据排序,现在我们只需要给出第i个大的数就行了,我们可以把数据前i-1个较小的"删掉",那第i大的数就成了最小的数,或者我们把后n-i个较大的删掉,那第i大的数就成了最大的数.最最方便的数据结构就是由堆进化而来又比堆应用广泛得多的优先级队列,其实上述第一个方案描述的是最小优先级队列,第二个方案描述的是最大优先级队列.优先级队列每一次能够在O(lgn)的时间里给出最大的数据.

有了上述的准备,代码就好写的多了:

1.应用了STL的priority_queue结构,用了500ms的时间解决问题.

   1: #include <iostream>   2: #include <queue>   3: #include <algorithm>   4: using namespace std;   5:     6: int M,N,c[30002],p[30002],i,j,value;   7:     8: int main(){   9:     cin>>M>>N;  10:     for(i=1;i<=M;i++)  11:         cin>>c[i];  12:     p[0]=0;  13:     for(i=1;i<=N;i++)  14:         cin>>p[i];  15:     priority_queue <int> a,b;  16:     for(i=1;i<=N;i++){  17:         for(j=p[i-1]+1;j<=p[i];j++){  18:             a.push(c[j]);  19:             if(a.size()>i-1){  20:                 value=-a.top();  21:                 a.pop();  22:                 b.push(value);  23:             }  24:         }  25:         value=-b.top();  26:         b.pop();  27:         a.push(value);  28:         cout<<a.top()<<endl;  29:     }  30:     return 0;  31: }

2.自己动手写了个priority_queue的代码,具体算法与1中一模一样,用了440ms的时间解决问题.

   1: #include <iostream>   2: using namespace std;   3:     4: #define Parent(i) ((i-1)/2)   5: #define Left(i)   (2*i+1)   6: #define Right(i)  (2*i+2)   7:     8: void Max_Heapify(int A[],int i,int& H_Size){   9:     int l=Left(i),r=Right(i),largest;  10:     if(l<=H_Size && A[l]>A[i])  11:         largest=l;  12:     else largest=i;  13:     if(r<=H_Size && A[r]>A[largest])  14:         largest=r;  15:     if(largest!=i){  16:         int temp=A[i];  17:         A[i]=A[largest];  18:         A[largest]=temp;  19:         Max_Heapify(A,largest,H_Size);  20:     }  21: }  22:    23: int Heap_Maximum(int A[]){  24:     return A[0];  25: }  26:    27: int Heap_Extract_Max(int A[],int& H_Size){  28:     if(H_Size<1)  29:         return 1000000;  30:     int max=A[0];  31:     A[0]=A[H_Size-1];  32:     H_Size=H_Size-1;  33:     Max_Heapify(A,0,H_Size);  34:     return max;  35: }  36:    37: void Heap_Increase_Key(int A[],int i,int key){  38:     if(key<A[i]) return;  39:     A[i]=key;  40:     while(i>0 && A[Parent(i)]<A[i]){  41:         int temp;  42:         temp=A[i];  43:         A[i]=A[Parent(i)];  44:         A[Parent(i)]=temp;  45:         i=Parent(i);  46:     }  47: }  48:    49: void Max_Heap_Insert(int A[],int key,int& H_Size){  50:     H_Size++;  51:     A[H_Size-1]=-2000000000;  52:     Heap_Increase_Key(A,H_Size-1,key);  53: }  54:    55:    56: int M,N,c[30002],p[30002],i,j,value;  57:    58: int main(){  59:     cin>>M>>N;  60:     for(i=1;i<=M;i++)  61:         cin>>c[i];  62:     p[0]=0;  63:     for(i=1;i<=N;i++)  64:         cin>>p[i];  65:     int a[30002],b[30002],AH_Size=0,BH_Size=0;  66:     for(i=1;i<=N;i++){  67:         for(j=p[i-1]+1;j<=p[i];j++){  68:             Max_Heap_Insert(a,c[j],AH_Size);  69:               70:             if(AH_Size>i-1){  71:                 value=-Heap_Extract_Max(a,AH_Size);  72:                   73:                 Max_Heap_Insert(b,value,BH_Size);  74:             }  75:         }  76:         value=-Heap_Extract_Max(b,BH_Size);  77:         Max_Heap_Insert(a,value,AH_Size);  78:         cout<<Heap_Maximum(a)<<endl;  79:     }  80:     return 0;  81: }  82:      83:  

在这道题目的AC过程中,还是有几点感悟的:

1.STL可能会使你的代码变得相当的简洁,但是在空间和时间上必然会造成一定的损失,尤其是在空间上的损失在有些情况下是非常可怕的事,比如将来做单片机的开发,你会发现以字节来计算的空间是如此的宝贵.STL当然很强大,但是在大多数情况下我们并不需要STL的所有功能,我们需要为STL那些对问题没用的代码付出巨大的空间的代价吗?

2.在北大的grid的JudgeOnline系统上,我的第二段代码居然得到了TLE的结果,而在南开的JO上更是竟然得到了WA的结果,最后还是在天大的JO上AC过了,赞天津大学一个.

位图的应用

Fri, 10 Jul 2009 11:47:05 +0800

编程珠玑 Chapter1

位图或位向量图作为一个集合，表示的这样的一个数据结构：

用字符串 0 1 1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 表示集合 {1,2,3,5,8,13}.

位图的应用需要数据有如下的特性:

1.输入数据限制在相对较小的范围内;

2.数据没有重复;

3.除了单一整数外,没有任何其他关联数据.

但很可惜的是,大多数待排序数据没有这些特性(就是说这些特性在大多数情况下是很难满足的).

习题1 如果不缺内存，如何使用一个具有库的语言来实现一种排序算法以表示和排序集合

解题报告:

拥有库的语言,C/C++/JAVA都是很好的选择,由于目前只会C++,因此对于我来说别无选择. 而对于C++,实现排序的库有太多的选择,典型的有STL中的stdlib.h中的qsort和algorithm中的sort.对于这两者的区别,在这里不想多谈(其实我并不清楚,大概了解的是stdlib是C的产物,而algorithm的后代,不过,sort在使用上比较简单).

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

int main(){

vector<int> a;

for(int i=0;i<=5;i++) a.push_back(i-5);

sort(a.begin(),a.end());

for(int i=0;i<5;i++) cout<<a[i]<<' ';

return 0;

}

习题二如何使用位逻辑运算（例如与、或、移位）来实现位向量

解题报告：

一开始当然没有想到要用位逻辑运算来实现位向量，而是用十进制来实现（这是理所当然的事）。

用一个一维数组a[10000000]来存储至多1E7个号码，考虑整数m,一旦发现这个号码，根据我们的算法，应当置a[m]=1.

好的，一切看起来都如此完美，简单的算法，出色的时间效率，差强人意的空间效率.但上机起来就不是这回事了:

#include <fstream>

#include <iostream>

using namespace std;

int main(){

ifstream in;

ofstream outt;

in.open("c:/project/out.txt");

outt.open("c:/project/outt.txt");

bool a[10000000];

for(int i=0;i<10000000;i++) a[i]=false;

int m;

for(int i=0;i<1000000;i++)

{in>>m; a[m]=true;}

for(int i=0;i<10000000;i++)

if(a[m]==true) outt<<m<<endl;

in.close();

outt.close();

return 0;

}

但是美好的想法在现实面前是如此的脆弱,这段代码在运行的时候出错了,原因是数组越界.好吧,现在我可以承认,数组开到1E7是不现实的,这该如何是好?

现在是时候回到位逻辑运算了,这是一种模仿计算机底层二进制运算的运算方法,十分高效,但是第一次看上去会显得晦涩难懂,等到将它与十进制运算联系起来后,会发现它相当有用.

整个的思想是,a[10000000]显得太过巨大的原因是每一个元素a[i]只保留了一个bool值或者是一个整型值0或1,如果我们把每一个元素包含的内容扩充,使之保留尽可能多的号码是否存在的信息,那么数组范围会得到明显的下降.

事实上,我们是用每一个元素表示一个32位的二进制字符串,这样这个元素可以保留相邻32个号码是否存在的信息,数组范围就下降到10000000/32了.例如对于号码89256,由于89256 mod 32=2789…8,这样我们应该置a[2789]中32位字符串的第8位(从低位数起)为1.

现在问题的关键是,如何用位逻辑运算来表示这种操作. 关于位逻辑运算的知识,你应当去参考手头的C++教材,因为在这里我无法讲的比教材更好:

#define WORD 32

#define SHIFT 5 //移动5个位,左移则相当于乘以32,右移相当于除以32取整

#define MASK 0x1F //六进制下的31

#define N 10000000

//置位函数——用"|"操作符,i&MASK相当于mod操作

//m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1)

void set(int i)

{a[i>>SHIFT]|=(1<<(i&MASK));}

//清除位操作，用&~操作符

void clear(int i)

{a[i>>SHIFT]&=~(1<<(i&MASK));}

//测试位操作用&操作符

int test(int i)

{return a[i>>SHIFT]&(1<<(i&MASK));}

重要的是要从十进制运算的思维转化为二进制运算,位逻辑运算不过是工具而已.

习题三在你自己的系统上实现位图排序并度量其运行时间

解题报告:

#define WORD 32

#define SHIFT 5 //移动5个位,左移则相当于乘以32,右移相当于除以32取整

#define MASK 0x1F //六进制下的31

#define N 10000000

#include <fstream>

#include <iostream>

using namespace std;

//置位函数——用"|"操作符,i&MASK相当于mod操作

//m mod n 运算，当n = 2的X次幂的时候,m mod n = m&(n-1)

void set(int i)

{a[i>>SHIFT]|=(1<<(i&MASK));}

//清除位操作，用&~操作符

void clear(int i)

{a[i>>SHIFT]&=~(1<<(i&MASK));}

//测试位操作用&操作符

int test(int i)

{return a[i>>SHIFT]&(1<<(i&MASK));}

int main(){

ifstream in;

ofstream outt;

in.open("c:/project/out.txt");

outt.open("c:/project/outt.txt");

int m;

for(int i=0;i<N;i++) clear(i);

for(int i=0;i<N/10;i++) {in>>m; set(m);}

for(int i=0;i<N;i++) {if(test(i)==1) outt<<i<<endl;}

in.close();

outt.close();

return 0;

}

为什么说这个算法时空效率达到极致呢？我们对１００万个不重复的正整数（１000,0000以内）的文件进行测试：

	系统排序	C++/STL.set	C++/sort	C++/位图
总时间(s)	89	38	12.6	10.7
计算时间(s)	79	28	2.4	0.5
内存使用(MB)	0.8	70	4	1.25

（本测试数据是在较旧的电脑上测试的，但还是体现性能的差距）
第一行是总时间，第二行的计算时间是总时间减去数据读取耗时１０.２秒。虽然通用C++程序使用内存和ＣＰＵ时间是专用C++程序（C++位图）的５０倍，但是它的使用仅需要一半的代码，并能很容易扩展到其他问题上，这也是专用C++程序最大的缺点吧。

测试博客中的公式输入

Sat, 13 Jun 2009 13:14:10 +0800

这是一段用于测试博客中的公式输入的文本：

用word2007+mathtype6.5输入的公式：

用word2007输入的公式：