oracle基础操作

建表用户授权等基本操作

1.sqlplus登陆

sqlplus

2.连接到指定用户

conn scott/tiger as sysdba

3.创建新用户

create user zwr identified by zwrpasswd;

4.修改密码

alter user zwr identified by zwrnewpasswd;

5.创建表空间

create [temporary] tablespace  ts_zwr datafile '/ts_zwr/zwr_data.dbf' size 200M;

6.分配表空间

alter user zwr default tablespace ts_zwr;
alter user zwr default temporary tablespace ts_zwr_temp;

7.授权用户表空间

grant create session,create table,create view,create sequence,unlimited tablespace to zwr; 

19.查询

20.导出/导入dmp相关

create directory dump as '/home/oracle/dumpfiles';
grant read,write on directory dump to zs_prod;
impdp system/manager directory=dump dumpfile=zs_prod20180427.dmp schemas=zs_prod;
impdp system/manager directory=dump dumpfile=zs_prod20180427.dmp logfile=prod schemas=zs_prod ;

Better understanding Linux secondary dependencies solving with examples

除了man 资料外觉得是挺详细的资料,收藏!

http://www.kaizou.org/2015/01/linux-libraries/

08 Jan 2015 by David Corvoysier

A few months ago I stumbled upon a linking problem with secondary dependencies I couldn’t solved without overlinking the corresponding libraries.

I only realized today in a discussion with my friend Yann E. Morin that not only did I use the wrong solution for that particular problem, but that my understanding of the gcc linking process was not as good as I had imagined.

This blog post is to summarize what I have now understood.

There is also a small repository on github with the mentioned samples.

A few words about Linux libraries

This paragraph is only a brief summary of what is very well described in The Linux Documentation Project library howto.

Man pages for the linux linker and loader are also a good source of information.

There are three kind of libraries in Linux: static, shared and dynamically loaded (DL).

Dynamically loaded libraries are very specific to some use cases like plugins, and would deserve an article on their own. I will only focus here on static and shared libraries.

Static libraries

A static library is simply an archive of object files conventionally starting with thelib prefix and ending with the .a suffix.

Example:

libfoobar.a

Static libraries are created using the ar program:

$ ar rcs libfoobar.a foo.o bar.o

Linking a program with a static library is as simple as adding it to the link command either directly with its full path:

$ gcc -o app main.c /path/to/foobar/libfoobar.a

or indirectly using the -l/L options:

$ gcc -o app main.c -lfoobar -L/path/to/foobar

Shared libraries

A shared library is an ELF object loaded by programs when they start.

Shared libraries follow the same naming conventions as static libraries, but with the .sosuffix instead of .a.

Example:

libfoobar.so

Shared library objects need to be compiled with the -fPIC option that produces position-independent code, ie code that can be relocated in memory.

$ gcc -fPIC -c foo.c
$ gcc -fPIC -c bar.c

The gcc command to create a shared library is similar to the one used to create a program, with the addition of the -shared option.

$ gcc -shared -o libfoobar.so foo.o bar.o

Linking against a shared library is achieved using the exact same commands as linking against a static library:

$ gcc -o app main.c libfoobar.so

or

$ gcc -o app main.c -lfoobar -L/path/to/foobar

Shared libraries and undefined symbols

An ELF object maintains a table of all the symbols it uses, including symbols belonging to another ELF object that are marked as undefined.

At compilation time, the linker will try to resolve an undefined symbol by linking it either statically to code included in the overall output ELF object or dynamically to code provided by a shared library.

If an undefined symbol is found in a shared library, a DT_NEEDED entry is created for that library in the output ELF target.

The content of the DT_NEEDED field depends on the link command: – the full path to the library if the library was linked with an absolute path, – the library name otherwise (or the library soname if it was defined).

You can check the dependencies of an ELF object using the readelf command:

$ readelf -d main

or

$ readelf -d libbar.so

When producing an executable a symbol that remains undefined after the link will raise an error: all dependencies must therefore be available to the linker in order to produce the output binary.

For historic reason, this behavior is disabled when building a shared library: you need to specify the --no-undefined (or -z defs) flag explicitly if you want errors to be raised when an undefined symbol is not resolved.

$ gcc -Wl,--no-undefined -shared -o libbar.so -fPIC bar.c

or

$ gcc -Wl,--no-undefined -shared -o libbar.so -fPIC bar.c

Note that when producing a static library, which is just an archive of object files, no actual ‘linking’ operation is performed, and undefined symbols are kept unchanged.

Library versioning and compatibility

Several versions of the same library can coexist in the system.

By conventions, two versions of the same library will use the same library name with a different version suffix that is composed of three numbers:

  • major revision,
  • minor revision,
  • build revision.

Example:

libfoobar.so.1.2.3

This is often referred as the library real name.

Also by convention, the library major version should be modified every time the library binary interface (ABI) is modified.

Following that convention, an executable compiled with a shared library version is theoretically able to link with another version of the same major revision.

This concept if so fundamental for expressing compatibility between programs and shared libraries that each shared library can be associated a soname, which is the library name followed by a period and the major revision:

Example:

libfoobar.so.1

The library soname is stored in the DT_SONAME field of the ELF shared object.

The soname has to be passed as a linker option to gcc.

$ gcc -shared -Wl,-soname,libfoobar.so.1 -o libfoobar.so foo.o bar.o

As mentioned before, whenever a library defines a soname, it is that soname that is stored in the DT_NEEDED field of ELF objects linked against that library.

Solving versioned libraries dependencies at build time

As mentioned before, libraries to be linked against can be specified using a shortened name and a path:

$ gcc -o app main.c -lfoobar -L/path/to/foobar

When installing a library, the installer program will typically create a symbolic link from the library real name to its linker name to allow the linker to find the actual library file.

Example:

/usr/lib/libfoobar.so -> libfoobar.so.1.5.3

The linker uses the following search paths to locate required shared libraries:

  • directories specified by -rpath-link options (more on that later)
  • directories specified by -rpath options (more on that later)
  • directories specified by the environment variable LD_RUN_PATH
  • directories specified by the environment variable LD_LIBRARY_PATH
  • directories specified in DT_RUNPATH or DT_RPATH of a shared library are searched for shared libraries needed by it
  • default directories, normally /lib and /usr/lib
  • directories listed inthe /etc/ld.so.conf file

Solving versioned shared libraries dependencies at runtime

On GNU glibc-based systems, including all Linux systems, starting up an ELF binary executable automatically causes the program loader to be loaded and run.

On Linux systems, this loader is named /lib/ld-linux.so.X (where X is a version number). This loader, in turn, finds and loads recursively all other shared libraries listed in theDT_NEEDED fields of the ELF binary.

Please note that if a soname was specified for a library when the executable was compiled, the loader will look for the soname instead of the library real name. For that reason, installation tools automatically create symbolic names from the library soname to its real name.

Example:

/usr/lib/libfoobar.so.1 -> libfoobar.so.1.5.3

When looking fo a specific library, if the value described in the DT_NEEDED doesn’t contain a /, the loader will consecutively look in:

  • directories specified at compilation time in the ELF object DT_RPATH (deprecated),
  • directories specified using the environment variable LD_LIBRARY_PATH,
  • directories specified at compile time in the ELF object DT_RUNPATH,
  • from the cache file /etc/ld.so.cache, which contains a compiled list of candidate libraries previously found in the augmented library path (can be disabled at compilation time),
  • in the default path /lib, and then /usr/lib (can be disabled at compilation time).

Proper handling of secondary dependencies

As mentioned in the introduction, my issue was related to secondary dependencies, ie shared libraries dependencies that are exported from one library to a target.

Let’s imagine for instance a program main that depends on a library libbar that itself depends on a shared library libfoo.

We will use either a static libbar.a or a shared libbar.so.

foo.c

int foo()
{
    return 42;
}

bar.c

int foo();

int bar()
{
    return foo();
}

main.c

int bar();

int main(int argc, char** argv)
{
    return bar();
}

Creating the libfoo.so shared library

libfoo has no dependencies but the libc, so we can create it with the simplest command:

$ gcc -shared -o libfoo.so -fPIC foo.c

Creating the libbar.a static library

As said before, static libraries are just archives of object files, without any means to declare external dependencies.

In our case, there is therefore no explicit connection whatsoever between libbar.a and libfoo.so.

$ gcc -c bar.c
$ ar rcs libbar.a bar.o

Creating the libbar.so dynamic library

The proper way to create the libbar.so shared library it by explicitly specifying it depends on libfoo:

$ gcc -shared -o libbar2.so -fPIC bar.c -lfoo -L$(pwd)

This will create the library with a proper DT_NEEDED entry for libfoo.

$ readelf -d libbar.so
Dynamic section at offset 0xe08 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
...

However, since undefined symbols are not by default resolved when building a shared library, we can also create a “dumb” version without any DT_NEEDED entry:

$ gcc -shared -o libbar_dumb.so -fPIC bar.c

Note that it is very unlikely that someone actually chooses to create such an incomplete library on purpose, but it may happen that by misfortune you encounter one of these beasts in binary form and still need to link against it (yeah, sh… happens !).

Creating the main executable

Linking against the libbar.a static library

As mentioned before, when linking an executable, the linker must resolve all undefined symbols before producing the output binary.

Trying to link only with libbar.a produces an error, since it has an undefined symbol and the linker has no clue where to find it:

$ gcc -o app_s main.c libbar.a
libbar.a(bar.o): In function `bar':
bar.c:(.text+0xa): undefined reference to `foo'
collect2: error: ld returned 1 exit status

Adding libfoo.so to the link command solves the problem:

$ gcc -o app main.c libbar.a -L$(pwd) -lfoo

You can verify that the app binary now explicitly depends on libfoo:

$ readelf -d app
Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
...

At run-time, the dynamic linker will look for libfoo.so, so unless you have installed it in standard directories (/lib or /usr/lib) you need to tell it where it is:

LD_LIBRARY_PATH=$(pwd) ./app

To summarize, when linking an executable against a static library, you need to specify explicitly all dependencies towards shared libraries introduced by the static library on the link command.

Note however that expressing, discovering and adding implicit static libraries dependencies is typically a feature of your build system (autotools, cmake).

Linking against the libbar.so shared library

As specified in the linker documentation, when the linker encounters an input shared library it processes all its DT_NEEDED entries as secondary dependencies:

  • if the linker output is a shared relocatable ELF object (ie a shared library), it will add all DT_NEEDED entries from the input library as new DT_NEEDED entries in the output,
  • if the linker ouput is a non-shared, non-relocatable link (our case), it will automatically add the libraries listed in the DT_NEEDED of the input library on the link command line, producing an error if it can’t locate them.

So, let’s see what happens when dealing with our two shared libraries.

Linking against the “dumb” library

When trying to link an executable against the “dumb” version of libbar.so, the linker encounters undefined symbols in the library itself it cannot resolve since it lacks theDT_NEEDED entry related to libfoo:

$ gcc -o app main.c -L$(pwd) -lbar_dumb
libbar_dumb.so: undefined reference to `foo'
collect2: error: ld returned 1 exit status

Let’s see how we can solve this.

Adding explicitly the libfoo.so dependency

Just like we did when we linked against the static version, we can just add libfoo to the link command to solve the problem:

$ gcc -o app main.c -L$(pwd) -lbar_dumb -lfoo

It creates an explicit dependency in the app binary:

$ readelf -d app
Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libbar_dumb.so]
 0x0000000000000001 (NEEDED)             Shared library: [libfoo.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
...

Again, at runtime you may need to tell the dynamic linker where libfoo.so is:

$ LD_LIBRARY_PATH=$(pwd) ./app

Note that having an explicit dependency to libfoo is not quite right, since our application doesn’t use directly any symbols from libfoo. What we’ve just done here is called overlinking, and it is BAD.

Let’s imagine for instance that in the future we decide to provide a newer version oflibbar that uses the same ABI, but based on a new version of libfoo with a different ABI: we should theoretically be able to use that new version of libbar without recompiling our application, but what would really happen here is that the dynamic linker would actually try to load the two versions of libfoo at the same time, leading to unpredictable results. We would therefore need to recompile our application even if it is still compatible with the newest libbar.

As a matter of fact, this actually happened in the past: a libfreetype update in the debian distro caused 583 packages to be recompiled, with only 178 of them actually using it.

Ignoring libfoo dependency

There is another option you can use when dealing with the “dumb” library: tell the linker to ignore its undefined symbols altogether:

$ gcc -o app main.c -L$(pwd) -lbar_dumb -Wl,--allow-shlib-undefined

This will produce a binary that doesn’t declare its hidden dependencies towards libfoo:

$ readelf -d app
Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libbar_dumb.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
...

This isn’t without consequences at runtime though, since the dynamic linker is now unable to resolve the executable dependencies:

$ ./app: symbol lookup error: ./libbar_dumb.so: undefined symbol: foo

Your only option is then to load libfoo explicitly (yes, this is getting uglier and uglier):

$ LD_PRELOAD=$(pwd)/libfoo.so LD_LIBRARY_PATH=$(pwd) ./app
Linking against the “correct” library
Doing it the right way

As mentioned before, when linking against the correct shared library, the linker encounters the libfoo.so DT_NEEDED entry, adds it to the link command and finds it at the path specified by -L, thus solving the undefined symbols … or at least that is what I expected:

$ gcc -o app main.c -L$(pwd) -lbar
/usr/bin/ld: warning: libfoo.so, needed by libbar.so, not found (try using -rpath or -rpath-link)
/home/diec7483/dev/linker-example/libbar.so: undefined reference to `foo'
collect2: error: ld returned 1 exit status

Why the error ? I thought I had done everything by the book !

Okay, let’s take a look at the ld man page again, looking at the -rpath-link option. This says:

When using ELF or SunOS, one shared library may require another. This happens when an “ld -shared” link includes a shared library as one of the input files. When the linker encounters such a dependency when doing a non-shared, non-relocatable link, it will automatically try to locate the required shared library and include it in the link, if it is not included explicitly. In such a case, the -rpath-link option specifies the first set of directories to search. The -rpath-link option may specify a sequence of directory names either by specifying a list of names separated by colons, or by appearing multiple times.

Ok, this is not crystal-clear, but what it actually means is that when specifying the path for a secondary dependency, you should not use -L but -rpath-link:

$ gcc -o app main.c -L$(pwd) -lbar -Wl,-rpath-link=$(pwd)

You can now verify that app depends only on libbar:

$ readelf -d app
Dynamic section at offset 0xe18 contains 25 entries:
  Tag        Type                         Name/Value
 0x0000000000000001 (NEEDED)             Shared library: [libbar.so]
 0x0000000000000001 (NEEDED)             Shared library: [libc.so.6]
...

And this is finally how things should be done.

You may also use -rpath instead of -rpath-link but in that case the specified path will be stored in the resulting executable, which is not suitable if you plan to relocate your binaries. Tools like cmake use the -rpath during the build phase (make), but remove the specified path from the executable during the installation phase(make install).

Conclusion

To summarize, when linking an executable against:

  • a static library, you need to specify all dependencies towards other shared libraries this static library depends on explicitly on the link command.

  • a shared library, you don’t need to specify dependencies towards other shared libraries this shared library depends on, but you may need to specify the path to these libraries on the link command using the -rpath/-rpath-link options.

Note however that expressing, discovering and adding implicit libraries dependencies is typically a feature of your build system (autotools, cmake), as demonstrated in my samples.

C/C++拾遗一

一. new是一个操作符,具体的实现:

1.调用 operate new 函数 分配内存空间!

2.然后调用构造函数!

3.返回正确的指针!

所以new 跟 malloc 的基本差别:

1.属性上:new 是个运算符,malloc 是个函数,malloc 可等同与operate new 函数(operate new stl中的实现就是调用了 malloc)

2.功能上,new 比malloc 多了调用构造函数的过程!

引申:

如果需要限制类对象实例只能分配在堆上:那么我们只需要做的事情是把析构函数设置为私有,这样编译器管理不了对象的生命周期就不能分配在栈上,当然我们需要设置一个公有函数实现对象的释放!同时因为按照编程习惯new/delete 都是成对出现的,现在析构私有,则delete 会报错,所以我们把new 也封装到一个静态函数中去!不直接使用 new!

如果需要限制类对象示例只能分配在栈上:把operate new  函数重载为私有,则new 运算符就调用不了operate new 函数!

二、虚函数实现

C++多态的实现依靠虚函数,而虚函数又是通过虚函数表来实现的。那么里面的实现细节需要关注如下几点:

1.位置:为了最大化查找虚函数效率,V-Table  的指针存放在对象实例最前面的位置!

2.虚函数在虚表中的组织形式:

    2.1.V-Table 存储的是一个类的所有虚函数指针,虚函数地址基类的放在前面,子类在后面,按顺序存储。

    2.2.如果子类中有覆盖基类的,则子类的对象实例中,在虚函数表中,该虚函数地址直接覆盖基类的虚函数地址!

   2.3.如果存在多重继承,会有多个虚函数表,子类虚函数放在第一个虚函数表中,如果存在覆盖,则全部基类函数都被覆盖!

安全性:

因为虚函数表是顺序存储的,所以有时候我们其实可以通过直接函数指针直接寻址的的方式绕过编译器检查访问到一些不能访问的函数,如子类存在而父类中没有的,受保护的虚函数等!

详情见:(http://ibinguo.net/2009/06/)

三、对象内存空间

这个也只讲个皮毛,深入的话还是要对汇编,编译原理有深入了解!

前面讲虚函数、虚表的时候,就说了,虚表指针是放在对象实例最前面的位置。那么再来看看类的各种不同成员,不同继承关系的对象内存分布

1.单一继承结构:虚表在最前面,并且虚函数按照顺序在虚表中排列,而各成员变量也按照声明的顺序排列!

2.多重继承结构:每个基类一个虚表,而成员变量紧跟在虚表后面,并且共同的基类每个基类都会重复!

歧义:因为每个基类都有一个重复基类的成员,所以不同子类在调用的时候编译器就不知道要调用具体哪个一个,调用的时候需要加上具体的基类名!

3.由于2的歧义性问题,C++还有一个虚继承,这样多重继承就不会有多个重复拷贝,但是虚继承的基类会在最下面!

四、初始化异常处理

为了处理构造函数成员初始化列表产生的异常,必须将构造函数编写为函数测试块(function try block)。

template <class T> Handle<T>::Handle(T *p)

try : ptr(p), use(new size_t(1))

{

  // empty function body

} catch(const std::bad_alloc &e) {

  handle_out_of_memory(e);

}

关键字try出现在成员初始化列表之前,测试块的复合语句包围了构造函数的函数体。catch子句既可以处理从成员初始化列表中抛出的异常,也可以处理从构造函数函数体中抛出的异常。

数据结构与算法( 七)字符串串算法

编程中还是经常用到字符串匹配的算发。

一.字符串匹配算法

字符串匹配算法通常分为两个步骤:预处理(Preprocessing)和匹配(Matching)。预处理就是计算每次匹配的时候滑动窗口,所以算法的总运行时间为预处理和匹配的时间的总和。

朴素的字符串匹配算法

从左向右匹配,每次匹配一个字串, 匹配失败后 向右移动一个字串。具体流程如下:

1.

首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

2.

因为B与A不匹配,搜索词再往后移。

3.

就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

4.

接着比较字符串和搜索词的下一个字符,还是相同。

5.

直到字符串有一个字符,与搜索词对应的字符不相同为止。

6.

这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。(下面部分就是KMP改进过程,原理在后面中讲)

7.

一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

8.

怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

9.

已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

  移动位数 = 已匹配的字符数 – 对应的部分匹配值

因为 6 – 2 等于4,所以将搜索词向后移动4位。

10.

因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

11.

因为空格与A不匹配,继续后移一位。

12.

逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

13.

逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

KMP算法

KMP算法是在朴素算法上的优化,因为我们发现,匹配失败后,每次向右移动一个字串,能不能移动多几个字串呢?

其实这也是以空间,时间,换时间的方式。进行一个预处理。

其实就是要找到匹配过的字串中的前缀与后缀匹配的字串长度,这样直接移动过去就好了,再演化一下,预处理就是先建立起部分匹配表(索引(hash)),寻找待匹配字串的前缀集与后缀集中的匹配长度。这样就可以计算出失败后的位移长度。

下面介绍《部分匹配表》是如何产生的。

首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

15.

“部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

  - ”A”的前缀和后缀都为空集,共有元素的长度为0;

  - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

  - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

  - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

  - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

  - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

  - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

16.

“部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

数据结构与算法( 六)图

没有最好的数据结构,只有最适合的数据结构,没有最快的算法,只有最适合的算法。

图是一种常见的非线性数据结构,探究图,其实就是将非线性数据线性化的尝试。

图的遍历部分发现一个博客写得挺好,直接修改转过来了

http://www.cnblogs.com/dolphin0520/archive/2011/07/13/2105236.html

一.图定义

1.有向图:边有方向的图。 无相图:边无方向。

2.无向完全图:任两个点之间都有边的图。

3.有向完全图:任两点之间都存在两个有向边的图。

4.路径:任两个顶点之间经过的顶点序列集,长度是顶点序列之间边的的数目。

5.简单路径:路径中没有重复的顶点。

6.连通图:任两个顶点之间都存在路径的图

7.连通分量(极大连通子图):image

8.连通图的生成树:包含图中全部的顶点,但只有n-1条边

9.图可以使用2维数组来表示他们之间的关系,(邻接矩阵单元值为0,表示没有边,1表示有边)。

image

二.图的遍历

图的遍历是树的遍历的推广,是按照某种规则(或次序)访问图中各顶点依次且仅一次的操作,亦是将网络结构按某种规则线性化的过程

由于图存在回路,为区别一顶点是否被访问过和避免顶点被多次访问,在遍历过程中,应记下每个访问过的顶点,即每个顶点对应有一个标志位,初始为False,一旦该顶点被访问,就将其置为True,以后若又碰到该顶点时,视其标志的状态,而决定是否对其访问。

对图的遍历通常有”深度优先搜索“和”广度优先搜索“方法,二者是人工智能的一个基础。

深度优先搜索(Depth First Search,简称DFS)

算法思路:

类似树的先根遍历。设初始化时,图中各顶点均未被访问,从图中某个顶点(设为V0)出发,访问V0,然后搜索V0的一个邻接点Vi,若Vi未被访问,则访问之,在 搜索Vi的一个邻接点(深度优先)…。若某顶点的邻接点全部访问完毕,则回溯(Backtracking)到它的上一顶点,然后再从此顶点又按深度优先的方法搜索下去,…,直到能访问的顶点都访问完毕为止。

设图G10如下图所示:

通过深度优先如下:

广度优先搜索(Breadth First Search),简称BFS

算法思路:

类似树的按层次遍历。初始时,图中各顶点均未被访问,从图中某顶点(V0)出发,访问V0,并依次访问V0的各邻接点(广度优先)。然后,分别从这些被访问过的顶点出发,扔仍按照广度优先的策略搜索其它顶点,….,直到能访问的顶点都访问完毕为止。

为控制广度优先的正确搜索,要用到队列技术,即访问完一个顶点后,让该顶点的序号进队。然后取相应队头(出队),考察访问过的顶点的各邻接点,将未访问过的邻接点访问 后再依次进队,…,直到队空为止。

通过广度优先如下:

下面看一下实现代码:

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX 20
  5. //访问记录
  6. int visit[MAX];
  7. //图的结构设计
  8. typedef struct
  9. {
  10. int vex[MAX];//记录顶点
  11. int adjmatrix[MAX][MAX];//邻接矩阵
  12. int n;//顶点的个数
  13. }GRAPH;
  14. //初始化图
  15. int init_graph(GRAPH *pG)
  16. {
  17.     memset(pG,0,sizeof(GRAPH));
  18.     pG->n = -1;
  19.     printf(“input vex\n”);
  20. while(scanf(“%d”,&pG->vex[++pG->n]));
  21. while(getchar() != ‘\n’);
  22. #ifndef _DEBUG_
  23. int i = 0;
  24. for(i = 0;i < pG->n ;i ++)
  25. {
  26.         printf(“V%d “,pG->vex[i]);
  27. }
  28.     printf(“\n”);
  29. #endif
  30.     return 0;
  31. }
  32. //获取顶点的位置
  33. int locatevex(GRAPH *pG,int vex)
  34. {
  35. int i = 0;
  36. for(i = 0;i < pG->n;i ++)
  37. {
  38. if(pG->vex[i] == vex )
  39.             return i;
  40. }
  41.     return 0;
  42. }
  43. //输入图的顶点之间的边
  44. int input_edge(GRAPH *pG)
  45. {
  46. int vex1,vex2;
  47. int i,j;
  48.     printf(“input edge(i,j):\n”);
  49. //任意字母键结束
  50. while(scanf(“(%d,%d)”,&vex1,&vex2))
  51. {
  52.         getchar();
  53.         i = locatevex(pG,vex1);
  54.         j = locatevex(pG,vex2);
  55.         pG->adjmatrix[i][j] = pG->adjmatrix[j][i] = 1;
  56. }
  57. #ifndef _DEBUG_
  58. int m,n;
  59. for(m = 0;m < pG->n;m ++)
  60. {
  61. for(n = 0;n < pG->n; n ++)
  62. {
  63.             printf(“%d “,pG->adjmatrix[m][n]);
  64. }
  65.         printf(“\n”);
  66. }
  67. #endif
  68.     return 0;
  69. }
  70. //栈的设计
  71. typedef struct
  72. {
  73. int buf[MAX];
  74. int n;
  75. }Stack;
  76. //创建空栈
  77. Stack *create_empty_stack()
  78. {
  79.     Stack *stack;
  80.     stack = (Stack *)malloc(sizeof(Stack));
  81.     stack->n = -1;
  82.     return stack;
  83. }
  84. //出栈
  85. int pop_stack(Stack *stack)
  86. {
  87. int temp;
  88.     temp = stack->buf[stack->n];
  89.     stack->n –;
  90.     return temp;
  91. }
  92. //入栈
  93. int push_stack(Stack *stack,int data)
  94. {
  95.     stack->n ++;
  96.     stack->buf[stack->n] = data;
  97.     return 0;
  98. }
  99. //判断空栈
  100. int is_empty_stack(Stack *stack)
  101. {
  102. if(stack->n == -1)
  103.         return 1;
  104. else
  105.         return 0;
  106. }
  107. int visit_all(GRAPH *pG)
  108. {
  109. int i = 0;
  110. for(i = 0;i < pG->n; i ++)
  111. {
  112. if(visit[i] != 1)
  113.             break;
  114. }
  115. if(i == pG->n)
  116.         return 1;
  117. else
  118.         return 0;
  119. }
  120. //图的深度非递归遍历
  121. int DFS(GRAPH *pG,int v)
  122. {
  123.     Stack *stack;
  124. int i = 0;
  125.     stack = create_empty_stack();
  126.     push_stack(stack,pG->vex[v]);
  127.     visit[v] = 1;
  128.     printf(“V%d “,pG->vex[v]);
  129. while(!is_empty_stack(stack) || !visit_all(pG))
  130. {
  131. for(i = 0;i < pG->n;i ++)
  132. {
  133. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  134.                 break;
  135. }
  136. if(i == pG->n)
  137. {
  138.             v = pop_stack(stack);
  139. }else{
  140.             v = i;
  141.             push_stack(stack,pG->vex[v]);
  142.             visit[v] = 1;
  143.             printf(“V%d “,pG->vex[v]);
  144. }
  145. }
  146.     printf(“\n”);
  147.     return 0;
  148. }
  149. //队列的设计
  150. typedef struct node
  151. {
  152. int data;
  153.     struct node *next;
  154. }ListNode;
  155. typedef struct
  156. {
  157.     ListNode *front;
  158.     ListNode *rear;
  159. }Queue;
  160. //创建空队列
  161. Queue *create_empty_queue()
  162. {
  163.     Queue *queue;
  164.     ListNode *head;
  165.     queue = (Queue *)malloc(sizeof(Queue));
  166.     head = (ListNode *)malloc(sizeof(ListNode));
  167.     queue->front = queue->rear = head;
  168.     return queue;
  169. }
  170. //判断队列是否为空
  171. int is_empty_queue(Queue *queue)
  172. {
  173. if(queue->rear == queue->front)
  174.         return 1;
  175. else
  176.         return 0;
  177. }
  178. //入队
  179. int EnterQueue(Queue *queue,int data)
  180. {
  181.     ListNode *temp;
  182.     temp = (ListNode *)malloc(sizeof(ListNode));
  183.     temp->data = data;
  184.     temp->next = NULL;
  185.     queue->rear->next = temp;
  186.     queue->rear = temp;
  187.     return 0;
  188. }
  189. //出队
  190. int DelQueue(Queue *queue)
  191. {
  192.     ListNode *temp;
  193.     temp = queue->front;
  194.     queue->front = queue->front->next;
  195.     free(temp);
  196.     temp = NULL;
  197.     return queue->front->data;
  198. }
  199. //图的广度遍历
  200. int BFS(GRAPH *pG,int v)
  201. {
  202.     Queue *queue = create_empty_queue();
  203. int i = 0;
  204.     memset(&visit,0,sizeof(visit));
  205.     EnterQueue(queue,v);
  206.     visit[v] = 1;
  207. while(!is_empty_queue(queue))
  208. {
  209.         v = DelQueue(queue);
  210.         printf(“V%d “,pG->vex[v]);
  211. for(i = 0;i < pG->n;i ++)
  212. {
  213. if(visit[i] == 0 && pG->adjmatrix[v][i] == 1)
  214. {
  215.                 EnterQueue(queue,i);
  216.                 visit[i] = 1;
  217. }
  218. }
  219. }
  220.     printf(“\n”);
  221.     return 0;
  222. }
  223. int main()
  224. {
  225.     GRAPH G;
  226. int n;
  227. //输入顶点,初始化图
  228.     init_graph(&G);
  229. //初始化邻接矩阵
  230.     input_edge(&G);
  231. //图的深度遍历
  232.     DFS(&G, 0);
  233. //图的广度遍历
  234.     BFS(&G,0);
  235.     return 0;
  236. }

输出结果:

C点(三)G

前面基本总结介绍了C/C++的基础点,现在再总结下需要注意的高级点。

一.C++模板

模板是泛型编程的基础,泛型编程即以一种独立于任何特定类型的方式编写代码。

模板是创建泛型类或函数的蓝图或公式。库容器,比如迭代器和算法,都是泛型编程的例子,它们都使用了模板的概念。

每个容器都有一个单一的定义,比如 向量,我们可以定义许多不同类型的向量,比如 vector <int>vector <string>

您可以使用模板来定义函数和类,接下来让我们一起来看看如何使用。

函数模板

模板函数定义的一般形式如下所示:

template <class type> ret-type func-name(parameter list)
{
   // 函数的主体
}  

在这里,type 是函数所使用的数据类型的占位符名称。这个名称可以在函数定义中使用。

下面是函数模板的实例,返回两个数种的最大值:

#include &lt;iostream&gt; #include &lt;string&gt; using namespace std; template &lt;typename T&gt; inline T const&amp; Max (T const&amp; a, T const&amp; b) { return a &lt; b ? b:a; } int main () { int i = 39; int j = 20; cout &lt;&lt; "Max(i, j): " &lt;&lt; Max(i, j) &lt;&lt; endl; double f1 = 13.5; double f2 = 20.7; cout &lt;&lt; "Max(f1, f2): " &lt;&lt; Max(f1, f2) &lt;&lt; endl; string s1 = "Hello"; string s2 = "World"; cout &lt;&lt; "Max(s1, s2): " &lt;&lt; Max(s1, s2) &lt;&lt; endl; return 0; }

类模板

正如我们定义函数模板一样,我们也可以定义类模板。泛型类声明的一般形式如下所示:

template <class type> class class-name {
.
.
.
}

在这里,type 是占位符类型名称,可以在类被实例化的时候进行指定。您可以使用一个逗号分隔的列表来定义多个泛型数据类型。

下面的实例定义了类 Stack<>,并实现了泛型方法来对元素进行入栈出栈操作:

#include &lt;iostream&gt; #include &lt;vector&gt; #include &lt;cstdlib&gt; #include &lt;string&gt; #include &lt;stdexcept&gt; using namespace std; template &lt;class T&gt; class Stack { private: vector&lt;T&gt; elems; // 元素 public: void push(T const&amp;); // 入栈 void pop(); // 出栈 T top() const; // 返回栈顶元素 bool empty() const{ // 如果为空则返回真。 return elems.empty(); } }; template &lt;class T&gt; void Stack&lt;T&gt;::push (T const&amp; elem) { // 追加传入元素的副本 elems.push_back(elem); } template &lt;class T&gt; void Stack&lt;T&gt;::pop () { if (elems.empty()) { throw out_of_range("Stack&lt;&gt;::pop(): empty stack"); } // 删除最后一个元素 elems.pop_back(); } template &lt;class T&gt; T Stack&lt;T&gt;::top () const { if (elems.empty()) { throw out_of_range("Stack&lt;&gt;::top(): empty stack"); } // 返回最后一个元素的副本 return elems.back(); } int main() { try { Stack&lt;int&gt; intStack; // int 类型的栈 Stack&lt;string&gt; stringStack; // string 类型的栈 // 操作 int 类型的栈 intStack.push(7); cout &lt;&lt; intStack.top() &lt;&lt;endl; // 操作 string 类型的栈 stringStack.push("hello"); cout &lt;&lt; stringStack.top() &lt;&lt; std::endl; stringStack.pop(); stringStack.pop(); } catch (exception const&amp; ex) { cerr &lt;&lt; "Exception: " &lt;&lt; ex.what() &lt;&lt;endl; return -1; } } 
二.多线程
//参数依次是:创建的线程id,线程参数,调用的函数,传入的函数参数
        int ret = pthread_create(&tids[i], NULL, say_hello, NULL);
三.C/C++标准库
C标准函数库

image

C++ 标准函数库

继承了C标准函数库及做了一些线程上的修改

C++标准类库

STL,输入输出等,重点就是STL。

C点(一)C++基础点

基于C的基础上再补充C++的一些基础要点。

一.数组指针

#include &lt;iostream&gt; using namespace std; const int MAX = 3; int main () { int var[MAX] = {10, 100, 200}; for (int i = 0; i &lt; MAX; i++) { *var = i; // 这是正确的语法 *(var + i) = 20;//正确 var++; // 这是不正确的 } return 0; } 

二.引用 vs 指针
区别:

引用很容易与指针混淆,它们之间有三个主要的不同:

  • 不存在空引用。引用必须连接到一块合法的内存。
  • 一旦引用被初始化为一个对象,就不能被指向到另一个对象。指针可以在任何时候指向到另一个对象。
  • 引用必须在创建时被初始化。指针可以在任何时间被初始化。
引用的使用:

作为形参使用:更加安全高效,不需要内存复制操作。

作为返回值:被引用的对象不能超出作用域。

int&amp; func() { int q; //! return q; // 在编译时发生错误 static int x; return x; // 安全,x 在函数作用域外依然是有效的 }

三.类对象-封装
拷贝构造函数

拷贝构造函数是一种特殊的构造函数,它在创建对象时,是使用同一类中之前创建的对象来初始化新创建的对象。拷贝构造函数通常用于:

  • 通过使用另一个同类型的对象来初始化新创建的对象。

  • 复制对象把它作为参数传递给函数。

  • 复制对象,并从函数返回这个对象。

如果在类中没有定义拷贝构造函数,编译器会自行定义一个。如果类带有指针变量,并有动态内存分配,则它必须有一个拷贝构造函数。拷贝构造函数的最常见形式如下:

#include &lt;iostream&gt; using namespace std; class Box { double width; public: friend void printWidth( Box box ); void setWidth( double wid ); }; // 成员函数定义 void Box::setWidth( double wid ) { width = wid; } // 请注意:printWidth() 不是任何类的成员函数 void printWidth( Box box ) { /* 因为 printWidth() 是 Box 的友元,它可以直接访问该类的任何成员 */ cout &lt;&lt; "Width of box : " &lt;&lt; box.width &lt;&lt;endl; } // 程序的主函数 int main( ) { Box box; // 使用成员函数设置宽度 box.setWidth(10.0); // 使用友元函数输出宽度 printWidth( box ); return 0; }
内联函数

C++ 内联函数是通常与类一起使用。如果一个函数是内联的,那么在编译时,编译器会把该函数的代码副本放置在每个调用该函数的地方。

对内联函数进行任何修改,都需要重新编译函数的所有客户端,因为编译器需要重新更换一次所有的代码,否则将会继续使用旧的函数。

如果想把一个函数定义为内联函数,则需要在函数名前面放置关键字 inline,在调用函数之前需要对函数进行定义。如果已定义的函数多于一行,编译器会忽略 inline 限定符。

在类定义中的定义的函数都是内联函数,即使没有使用 inline 说明符。

类静态成员与静态函数

我们可以使用 static 关键字来把类成员定义为静态的。当我们声明类的成员为静态时,这意味着无论创建多少个类的对象,静态成员都只有一个副本。

静态成员在类的所有对象中是共享的。如果不存在其他的初始化语句,在创建第一个对象时,所有的静态数据都会被初始化为零。我们不能把静态成员放置在类的定义中,但是可以在类的外部通过使用范围解析运算符 :: 来重新声明静态变量从而对它进行初始化,如下面的实例所示。

如果把函数成员声明为静态的,就可以把函数与类的任何特定对象独立开来。静态成员函数即使在类对象不存在的情况下也能被调用,静态函数只要使用类名加范围解析运算符 :: 就可以访问。

静态成员函数只能访问静态数据成员,不能访问其他静态成员函数和类外部的其他函数。

静态成员函数有一个类范围,他们不能访问类的 this 指针。您可以使用静态成员函数来判断类的某些对象是否已被创建.

#include <iostream> using namespace std; class Box { public: static int objectCount; // 构造函数定义 Box(double l=2.0, double b=2.0, double h=2.0) { cout <<"Constructor called." << endl; length = l; breadth = b; height = h; // 每次创建对象时增加 1 objectCount++; } double Volume() { return length * breadth * height; } static int getCount() { return objectCount; } private: double length; // 长度 double breadth; // 宽度 double height; // 高度 }; // 初始化类 Box 的静态成员 int Box::objectCount = 0; int main(void) { // 在创建对象之前输出对象的总数 cout << "Inital Stage Count: " << Box::getCount() << endl; Box Box1(3.3, 1.2, 1.5); // 声明 box1 Box Box2(8.5, 6.0, 2.0); // 声明 box2 // 在创建对象之后输出对象的总数 cout << "Final Stage Count: " << Box::getCount() << endl; return 0; }

四.继承+多态

继承:is-a

多态:以虚函数实现,进行面向对象的抽象。同时通过纯虚函数,实现接口设计编程。

五.异常处理

C++ 标准的异常

C++ 提供了一系列标准的异常,定义在 <exception> 中,我们可以在程序中使用这些标准的异常。它们是以父子类层次结构组织起来的,如下所示:

C++ 异常的层次结构

下表是对上面层次结构中出现的每个异常的说明:

image

定义新的异常

可以通过继承和重载 exception 类来定义新的异常。下面的实例演示了如何使用 std::exception 类来实现自己的异常

#include &lt;iostream&gt; #include &lt;exception&gt; using namespace std; struct MyException : public exception { const char * what () const throw () { return "C++ Exception"; } }; int main() { try { throw MyException(); } catch(MyException&amp; e) { std::cout &lt;&lt; "MyException caught" &lt;&lt; std::endl; std::cout &lt;&lt; e.what() &lt;&lt; std::endl; } catch(std::exception&amp; e) { //其他的错误 } }

抛出异常+捕获异常

throw:

double division(int a, int b) { if( b == 0 ) { throw "Division by zero condition!"; } return (a/b); }

try…catch…

try { // 保护代码 }catch( ExceptionName e1 ) { // catch 块 }catch( ExceptionName e2 ) { //任何异常,作为保护代码使用 }catch(... ) { // catch 块 }

六.内存管理

new 可以对内存进行初始化操作即有构造函数,malloc只申请分配内存。

七.预处理*宏

# 和 ## 运算符

# 和 ## 预处理运算符在 C++ 和 ANSI/ISO C 中都是可用的。# 运算符会把 replacement-text 令牌转换为用引号引起来的字符串。

## 运算符用于连接两个令牌。

#include <iostream>
using namespace std;

#define concat(a, b) a ## b
int main()
{
   int xy = 100;
   
   cout << concat(x, y);
   return 0;
}

c点(一)C基础点

记录下C编程的一些基础注意点。常量,全局变量,局部变量,形参变量,作用域,运算符,修饰符。

编译,环境

一.常量

使用 #define 预处理器。:

#include &lt;stdio.h&gt; #define LENGTH 10 #define WIDTH 5 #define NEWLINE '\n' 

使用 const 关键字。:

const int LENGTH = 10; const int WIDTH = 5; const char NEWLINE = '\n';

二:变量+作用域

任何一种编程中,作用域是程序中定义的变量所存在的区域,超过该区域变量就不能被访问。C 语言中有三个地方可以声明变量:

  1. 在函数或块内部的局部变量
  2. 在所有函数外部的全局变量
  3. 形式参数的函数参数定义中

让我们来看看什么是局部变量、全局变量和形式参数。

局部变量

在某个函数或块的内部声明的变量称为局部变量。它们只能被该函数或该代码块内部的语句使用。局部变量在函数外部是不可知的。

全局变量

全局变量是定义在函数外部,通常是在程序的顶部。全局变量在整个程序生命周期内都是有效的,在任意的函数内部能访问全局变量。

全局变量可以被任何函数访问。也就是说,全局变量在声明后整个程序中都是可用的。

形式参数

函数的参数,形式参数,被当作该函数内的局部变量,它们会优先覆盖全局变量。

初始化局部变量和全局变量

当局部变量被定义时,系统不会对其初始化,您必须自行对其初始化。定义全局变量时,系统会自动对其初始化。

image

#include &lt;stdio.h&gt; /* 全局变量声明 */ int a = 20; int main () { /* 在主函数中的局部变量声明 */ int a = 10; int b = 20; int c = 0; int sum(int, int); printf ("value of a in main() = %d\n", a); c = sum( a, b); printf ("value of c in main() = %d\n", c); return 0; } /* 添加两个整数的函数 */ int sum(int a, int b) { printf ("value of a in sum() = %d\n", a); printf ("value of b in sum() = %d\n", b); return a + b; }
三.存储类
auto 存储类:

auto 存储类是所有局部变量默认的存储类。

register 存储类

register 存储类用于定义存储在寄存器中而不是 RAM 中的局部变量。这意味着变量的最大尺寸等于寄存器的大小(通常是一个词),且不能对它应用一元的 ‘&’ 运算符(因为它没有内存位置)。

static 存储类

static 存储类指示编译器在程序的生命周期内保持局部变量的存在,而不需要在每次它进入和离开作用域时进行创建和销毁。因此,使用 static 修饰局部变量可以在函数调用之间保持局部变量的值。

static 修饰符也可以应用于全局变量。当 static 修饰全局变量时,会使变量的作用域限制在声明它的文件内。

在 C 编程中,当 static 用在类数据成员上时,会导致仅有一个该成员的副本被类的所有对象共享。

extern 存储类

extern 存储类用于提供一个全局变量的引用,全局变量对所有的程序文件都是可见的。当您使用 ‘extern’ 时,对于无法初始化的变量,会把变量名指向一个之前定义过的存储位置。

四.运算符

位运算符

位运算符作用于位,并逐位执行操作。&、 | 和 ^ 的真值表如下所示:

image

假设如果 A = 60,且 B = 13,现在以二进制格式表示,它们如下所示:

A = 0011 1100

B = 0000 1101

—————–

A&B = 0000 1100

A|B = 0011 1101

A^B = 0011 0001

~A  = 1100 0011

下表显示了 C 语言支持的位运算符。假设变量 A 的值为 60,变量 B 的值为 13,则:

image

五.形参

image

引用:

/* 函数定义 */ void swap(int &amp;x, int &amp;y) { int temp; temp = x; /* 保存地址 x 的值 */ x = y; /* 把 y 赋值给 x */ y = temp; /* 把 temp 赋值给 y */ return; }

指针:

/* 函数定义 */ void swap(int *x, int *y) { int temp; temp = *x; /* 保存地址 x 的值 */ *x = *y; /* 把 y 赋值给 x */ *y = temp; /* 把 temp 赋值给 y */ return; }

六.指针+数组
数组:

#include &lt;stdio.h&gt; /* 函数声明 */ double getAverage(int arr[], int size); int main () { /* 带有 5 个元素的整型数组 */ int balance[5] = {1000, 2, 3, 17, 50}; double avg; /* 传递一个指向数组的指针作为参数 */ avg = getAverage( balance, 5 ) ; /* 输出返回值 */ printf( "平均值是: %f ", avg ); return 0; }

数组指针:

数组名是一个指向数组中第一个元素的常量指针。因此,在下面的声明中:

double balance[50];

balance 是一个指向 &balance[0] 的指针,即数组 balance 的第一个元素的地址。因此,下面的程序片段把 p 赋值为 balance 的第一个元素的地址:

double *p;
double balance[10];

p = balance;

使用数组名作为常量指针是合法的,反之亦然。因此,*(balance + 4) 是一种访问 balance[4] 数据的合法方式。

一旦您把第一个元素的地址存储在 p 中,您就可以使用 *p、*(p+1)、*(p+2) 等来访问数组元素。

指针的指针

指向指针的指针是一种多级间接寻址的形式,或者说是一个指针链。通常,一个指针包含一个变量的地址。当我们定义一个指向指针的指针时,第一个指针包含了第二个指针的地址,第二个指针指向包含实际值的位置。

C 中指向指针的指针

七.字符串
字符串

在 C 语言中,字符串实际上是使用 null 字符 ‘\0′ 终止的一维字符数组。因此,一个以 null 结尾的字符串,包含了组成字符串的字符。

下面的声明和初始化创建了一个 “Hello” 字符串。由于在数组的末尾存储了空字符,所以字符数组的大小比单词 “Hello” 的字符数多一个。

char greeting[6] = {'H', 'e', 'l', 'l', 'o', '\0'};

依据数组初始化规则,您可以把上面的语句写成以下语句:

char greeting[] = "Hello";

以下是 C/C++ 中定义的字符串的内存表示:

C/C++ 中的字符串表示

其实,您不需要把 null 字符放在字符串常量的末尾。C 编译器会在初始化数组时,自动把 ‘\0′ 放在字符串的末尾。

操作字符串的函数

image

八.可变参数

有时,您可能会碰到这样的情况,您希望函数带有可变数量的参数,而不是预定义数量的参数。C 语言为这种情况提供了一个解决方案,它允许您定义一个函数,能根据具体的需求接受可变数量的参数。下面的实例演示了这种函数的定义。

int func(int, ... ) 
{
   .
   .
   .
}

int main()
{
   func(1, 2, 3);
   func(1, 2, 3, 4);
}

请注意,函数 func() 最后一个参数写成省略号,即三个点号(),省略号之前的那个参数总是 int,代表了要传递的可变参数的总数。为了使用这个功能,您需要使用 stdarg.h 头文件,该文件提供了实现可变参数功能的函数和宏。具体步骤如下:

  • 定义一个函数,最后一个参数为省略号,省略号前面的那个参数总是 int,表示了参数的个数。
  • 在函数定义中创建一个 va_list 类型变量,该类型是在 stdarg.h 头文件中定义的。
  • 使用 int 参数和 va_start 宏来初始化 va_list 变量为一个参数列表。宏 va_start 是在 stdarg.h 头文件中定义的。
  • 使用 va_arg 宏和 va_list 变量来访问参数列表中的每个项。
  • 使用宏 va_end 来清理赋予 va_list 变量的内存。

现在让我们按照上面的步骤,来编写一个带有可变数量参数的函数,并返回它们的平均值:

#include <stdio.h>
#include <stdarg.h>

double average(int num,...)
{

    va_list valist;
    double sum = 0.0;
    int i;

    /* 为 num 个参数初始化 valist */
    va_start(valist, num);

    /* 访问所有赋给 valist 的参数 */
    for (i = 0; i < num; i++)
    {
       sum += va_arg(valist, int);
    }
    /* 清理为 valist 保留的内存 */
    va_end(valist);

    return sum/num;
}

int main()
{
   printf("Average of 2, 3, 4, 5 = %f\n", average(4, 2,3,4,5));
   printf("Average of 5, 10, 15 = %f\n", average(3, 5,10,15));
}

当上面的代码被编译和执行时,它会产生下列结果。应该指出的是,函数 average() 被调用两次,每次第一个参数都是表示被传的可变参数的总数。省略号被用来传递可变数量的参数。

Average of 2, 3, 4, 5 = 3.500000
Average of 5, 10, 15 = 10.000000
九.字符串

 

strlen():返回的长度不包括空结束字符 sizeof() 运算符

int _tmain(int argc, _TCHAR* argv[]) { char str[10] = "1234567"; const char* cstr = "1234567"; void * pvoid; int len = strlen("1234567");// len = 7; len = sizeof("1234567");// len = 8 * sizeof(char) = 8; len = sizeof(str); // len = 10* sizeof(char) = 10; len = sizeof(pvoid);// len = 4 ;指针长度 len = sizeof(cstr);// len = 4 = sizeof(void *) len = strlen(cstr); // len = 7* sizeof(char) = 7; return 0; }

STL容器解析

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树(红黑树)等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

一.使用原则

当对象很大时,建立指针的容器而不是对象的容器

1 STL基于拷贝的方式的来工作,任何需要放入STL中的元素,都会被复制。

2 只涉及到指针拷贝操作, 没有额外类的构造函数和赋值构造函数的调用;

3.对象是指针的话,容器销毁前需要自行销毁指针所指向的对象;否则就造成了内存泄漏;

4.对象是指针的话, 使用排序等算法时,需要构造基于对象的比较函数,如果使用默认的比较函数,其结果是基于指针大小的比较,而不是对象的比较;

二.使用场景

deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
vector与deque的比较:
一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
三:deque支持头部的快速插入与快速移除,这是deque的优点。
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。

数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。