2012年8月17日

平衡二叉树 (Balanced binary tree)

形态匀称的二叉树称为平衡二叉树 (Balanced binary tree) ,其严格定义是:
  一棵空树是平衡二叉树;若 T 是一棵非空二叉树,其左、右子树为 TL 和 TR ,令 hl 和 hr 分别为左、右子树的深度。当且仅当
   ①TL 、 TR 都是平衡二叉树;
   ② | hl - hr |≤ 1;
时,则 T 是平衡二叉树。
【例】如图 8.4 所示。
         
             (a)平衡二叉树           (b)非平衡二叉树
                      图8.3 平衡二叉树与非平衡二叉树
相应地定义 hl - hr 为二叉平衡树的平衡因子 (balance factor) 。因此,平衡二叉树上所有结点的平衡因子可能是 -1 , 0 , 1 。换言之,若一棵二叉树上任一结点的平衡因子的绝对值都不大于 1 ,则该树是就平衡二叉树。
动态平衡技术
1.动态平衡技术
Adelson-Velskii 和 Landis 提出了一个动态地保持二叉排序树平衡的方法,其基本思想是:
  在构造二叉排序树的过程中,每当插入一个结点时,首先检查是否因插入而破坏了树的平衡性,如果是因插入结点而破坏了树的平衡性,则找出其中最小不平衡子树,在保持排序树特性的前提下,调整最小不平衡子树中各结点之间的连接关系,以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树
2.最小不平衡子树
  以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论,不妨假设二叉排序树的最小不平衡子树的根结点为 A ,则调整该子树的规律可归纳为下列四种情况:
(1) LL 型:
  新结点 X 插在 A 的左孩子的左子树里。调整方法见图 8.5(a) 。图中以 B 为轴心,将 A 结点从 B 的右上方转到 B 的右下侧,使 A 成为 B 的右孩子。
      
          图8.5 平衡调整的4种基本类型(结点旁的数字是平衡因子)
(2)RR 型:
  新结点 X 插在 A 的右孩子的右子树里。调整方法见图 8.5(b) 。图中以 B 为轴心,将 A 结点从 B 的左上方转到 B 的左下侧,使 A 成为 B 的左孩子。
(3)LR 型:
  新结点 X 插在 A 的左孩子的右子树里。调整方法见图 8.5(c) 。分为两步进行:第一步以 X 为轴心,将 B 从 X 的左上方转到 X 的左下侧,使 B 成为 X 的左孩子, X 成为 A 的左孩子。第二步跟 LL 型一样处理 ( 应以 X 为轴心 ) 。
(4)RL 型:
  新结点 X 插在 A 的右孩子的左子树里。调整方法见图 8.5(d) 。分为两步进行:第一步以 X 为轴心,将 B 从 X 的右上方转到 X 的右下侧,使 B 成为 X 的右孩子, X 成为 A 的右孩子。第二步跟 RR 型一样处理 ( 应以 X 为轴心 ) 。
【例】
实际的插入情况,可能比图 8.5 要复杂。因为 A 、 B 结点可能还会有子树。现举一例说明,设一组记录的关键字按以下次序进行插入: 4 、 5 、 7 , 2 、 1 、 3 、 6 ,其生成及调整成二叉平衡树的过程示于图 8.6 。
  在图 8.6 中,当插入关键字为 3 的结点后,由于离结点 3 最近的平衡因子为 2 的祖先是根结点 5 。所以,第一次旋转应以结点 4 为轴心,把结点 2 从结点 4 的左上方转到左下侧,从而结点 5 的左孩子是结点 4 ,结点 4 的左孩子是结点 2 ,原结点 4 的左孩子变成了结点 2 的右孩子。第二步再以结点 4 为轴心,按 LL 类型进行转换。这种插入与调整平衡的方法可以编成算法和程序,这里就不再讨论了。

         图 8.6 二叉平衡树插入结点 ( 结点旁的数字为其平衡因子 )

posted @ 2012-08-17 14:42 章涛 阅读(211) | 评论 (0)编辑 收藏

2012年8月15日

指向函数的指针

(一) 用函数指针变量调用函数

  可以用指针变量指向整形变量、字符串、数组、结构体、也可以指向一个函数。一个函数在编译时被分配一个入口地址。这个入口地址就称为函数指针。可以用一个指针变量指向函数,然后通过该指针变量调用此函数。用简单的数值比较为例:

复制代码
1 #include <stdio.h>
2 #include <stdlib.h>
3
4  int main()
5 {
6 int max(int,int);
7 int (*p)(int,int);
8 int a,b,c;
9 p = max;
10 scanf("%d,%d",&a,&b);
11 c = (*p)(a,b);
12 printf("a=%d,b=%d,max=%d\n",a,b,c);
13 return 0;
14 }
15
16 int max(int x,int y)
17 {
18 int z;
19 if(x>y) z = x;
20 else z = y;
21 return(z);
22 }
复制代码

  main函数中的" c = max(a,b); " 包括了一次函数的调用。每一个函数都占用一段内存单元。因此,可以用一个指针变量指向一个函数,通过指针变量来访问它指向的函数。

  第7行:int (*p)( int,int );  用来定义 p 是一个指向函数的指针变量,该函数有两个整形参数,函数值为整形。注意 *p 两侧的括号不可省略,表示 p 先与 * 结合,是指针变量,然后再与后面的 ( ) 结合,表示此指针变量指向函数,这个函数值 (即函数的返回值) 是整形的。如果写成 int *p ( int,int ) ,由于( )的优先级高于 *,它就成了声明一个函数P( 这个函数的返回值是指向整形变量的指针)。

  赋值语句 p = max ; 作用是将函数 max 的入口地址赋给指针变量p。和数组名代表数组首元素地址类似,函数名代表该函数的入口地址。这时 p 就是指向函数 max 的指针变量,此时 p 和 max都指向函数开头,调用 *p 就是调用 max 函数。但是p作为指向函数的指针变量,它只能指向函数入口处而不可能指向函数中间的某一处指令处,因此不能用 *(p + 1)来表示指向下一条指令。

  注意:

  (1) 指向函数的指针变量的一般定义形式为:

  数据类型 (*指针变量名)(函数参数列表)

  这里数据类型就是函数返回值的类型

  (2) int (* p) ( int,int ); 它只是定义一个指向函数的指针变量 p, 它不是固定指向哪一个函数的,而只是表示定义这样一个类型的变量,它是专门用来存放函数的入口地址的。在程序中把哪一函数(该函数的值应该是整形的,且有两个整形参数)的地址赋给它,他就指向哪一个函数。在一个函数中,一个函数指针变量可以先后指向同类型的不同函数。

  (3) p = max; 在给函数指针变量赋值时,只需给出函数名而不必给出函数参数,因为是将函数的入口地址赋给 p ,而不涉及 实参和形参的结合问题,不能写成 p = max(a,b);

  (4) c = (*p)(a,b) 在函数调用时,只需将( *p ) 代替函数名即可,后面实参依旧。

  (5) 对于指向函数的指针变量,像 p++ ,p+n.....是无意义的。

  (二) 用指向函数的指针作为函数参数

  函数指针变量通常的用途之一就是把指针作为参数传递到其他函数。

  函数的参数可以是变量、指向变量的指针变量、数组名、指向数组的指针变量,也可以是指向函数的指针也可以作为参数,以实现函数地址的传递,这样就能够在被调用的函数中使用实参函数。

  void  sub ( int ( *x1) (int), int (*x2) (int,int) )

    {

      int a,b,i,j;

      a = (*x1)(i);      /* 调用 f1 函数 */

      b = (*x2)(i)(j);    /* 调用 f2 函数 */

    }

  如果实参为两个 函数名 f1 和 f2. 在函数首部定义x1、x2为函数指针变量,x1指向的函数有一个整形形参,x2指向的函数有两个形参。i 和 j 是函数f1 和 f2所要的参数。函数sub的形参 x1、x2(指针变量)在函数 sub 未被调用时并不占用内存单元,也不指向任何函数。在sub被调用时,把实参函数 f1 和 f2的入口地址传给形式指针变量 x1 和 x2.

  既然在 sub 函数中要调用 f1 和 f2 函数,为什么不直接调用f1 和 f2而要用函数指针变量呢? 确实,如果只是用到f1 和 f2 函数,完全可以在sub函数中直接调用f1 和 f2,而不必设指针变量 x1 和 x2。 但是,如果在每次调用sub时,调用的函数不是固定的,下次是f3 和 f4,再是f5 和 f6...这时用指针变量就比较方便了。

我们在类里面会定义成员函数,同时我们也希望定义成员函数指针。因此需要解决3个问题,第一怎么定义类的函数指针,第二赋值,第三使用。
我定义一个类,

class A
{
public:
    
int add(int,int);
    
int mul(int,int);
    
int div(int,int);
};

int A::add(int a,int b)
{
    
return a + b;
}

int A::mul(int a,int b)
{
    
return a * b;
}

int A::div(int a,int b)
{
    
return (b !=0 ? a/b : a);
}

我现在想要定义一个指针,指向A类型中返回值为int,参数为两个int的函数指针。熟悉C的同学马上会写出typedef int (*oper)(int,int)。但是这个用到C++里就有问题了,
因为我们知道,类的非static成员方法实际上还有this指针的参数。比如add方法,它实际的定义可能会这样int add(A* this,int a,int b);因此,我们不能简单把C语言里的那套东西搬过来,我们需要重新定义这种类型的指针。正确做法是加上类型,typedef int (A::*Action)(int,int)

typedef int (A::* Action)(int,int);

int main()
{
    A a;
    Action p 
= &A::add;
    cout 
<< (a.*p)(1,2<< endl;
    
return 0;
}

 

Action p = &A::add;这个就是赋值语句
调用的时候注意,直接这样(*p)(1,2)是不行的,它必须绑定到一个对象上
(a.*p)(1,2);我们也可以把类的函数指针定义在类的声明里。
class A
{
public:
    
int add(int,int);
    
int mul(int,int);
    
int div(int,int);

    
int (A::*oper)(int,int);
};

上面这种方式是针对非static成员函数的,那么static成员函数的函数指针应该怎么定义呢,还能用上面这种方式吗?我们知道static成员函数是没有this指针的,所以不会加上的类的限定,它的函数指针定义方式和C里面的函数指针定义方式一样的。

class A
{
public:
    
int add(int,int);
    
int mul(int,int);
    
int div(int,int);

    
static int sub(int,int);
};

int A::sub(int a,int b)
{
    
return a - b;
}

int main()
{
    
int (*pp)(int,int= &A::sub;
    cout 
<< (*pp)(10,5<< endl;
    
    
return 0;
}

总结起来,非static成员函数的函数指针需要加上类名,而static的成员函数的函数指针和普通的函数指针一样,没有什么区别。
另外注意一点的是
如果函数指针定义在类中,调用的时候有点区别。

class A
{
public:

    
int add(int,int);
    
int mul(int,int);
    
int div(int,int);

    
int (A::*pfunc)(int,int);
};

int main()
{
    A a;
    a.pfunc 
= &A::add;
    cout 
<< (a.*(a.pfunc))(1,2<< endl;
    
return 0;
}

 

posted @ 2012-08-15 15:42 章涛 阅读(209) | 评论 (0)编辑 收藏

2012年8月13日

关于set中存放的元素的排列顺序

1. set中存放的为数(整数,浮点数......)
在set中会按从小到大排列这些数
例:

#include <iostream>
#include <set>
using namespace std;

int main()
{
 set<float> a;
 a.insert(12.3);
 a.insert(60.3);
 a.insert(32.3);
 a.insert(822.1);
 a.insert(41140.1);
 a.insert(44449.8);
 set<float>::iterator p2a= a.begin();
 while(p2a!= a.end())
 {cout<< *p2a<< endl; ++p2a;}
 return 0;
}

[142]stxtopt05: /remote/us01home37/taoz/works/testset/ > g++ test.cc
[143]stxtopt05: /remote/us01home37/taoz/works/testset/ > ./a.out
12.3
32.3
60.3
822.1
41140.1
44449.8

2. set 中存放的为string
存入的string会按字母表顺序排列
例:

#include <iostream>
#include <string>
#include <set>
using namespace std;

int main()
{
 set<string> a;
 a.insert("bcdefg");
 a.insert("acdefg");
 a.insert("abdefg");
 a.insert("dabcefg");
 a.insert("bcdfg");
 a.insert("fabcdeg");
 set<string>::iterator p2a= a.begin();
 while(p2a!= a.end())
 {cout<< *p2a<< endl; ++p2a;}
 return 0;
}

[147]stxtopt05: /remote/us01home37/taoz/works/testset/ > g++ test.cc
[148]stxtopt05: /remote/us01home37/taoz/works/testset/ > ./a.out
abdefg
acdefg
bcdefg
bcdfg
dabcefg
fabcdeg

其他类型大家可以用上面的程序试试,至于存放类的话,还可以自己定义排列规则
所以,将数存入set中不仅可以去重,还可以排序哦

posted @ 2012-08-13 13:37 章涛 阅读(377) | 评论 (0)编辑 收藏

map类型.

1。目录
  1. map简介
  2. map的功能
  3. map的定义
  4. 在map中添加元素
  5. 查找并获取map中的元素
  6. 从map中删除元素
  7. map对象的迭代遍历 

2。map简介

map是一类关联式容器,它是模板类。关联的本质在于元素的值与某个特定的键相关联,而并非通过元素在数组中的位置类获取。它的特点是增加和删除节点对迭代器的影响很小,除了操作节点,对其他的节点都没有什么影响。对于迭代器来说,不可以修改键值,只能修改其对应的实值。

 

3。map的功能

  1. 自动建立Key - value的对应。key 和 value可以是任意你需要的类型,但是需要注意的是对于key的类型,唯一的约束就是必须支持<操作符
  2. 根据key值快速查找记录,查找的复杂度基本是Log(N),如果有1000个记录,最多查找10次,1,000,000个记录,最多查找20次。
  3. 快速插入Key - Value 记录。
  4. 快速删除记录
  5. 根据Key 修改value记录。
  6. 遍历所有记录。

4。map的定义

使用map得包含map类所在的头文件:#include <map> //注意,STL头文件没有扩展名.h

map对象是模板类,需要关键字和存储对象两个模板参数,基本的定义模式如下:


std:map<int, string> personnel;


这样就定义了一个以int为键,值为string的map对象personnel。

 

map中定义了以下三个类型:

  • map<K, V>::key_type : 表示map容器中,索引的类型;
  • map<K, V>::mapped_type : 表示map容器中,键所关联的值的类型;
  • map<K, V>::value_type : 表示一个pair类型,它的first元素具有const map<K, V>::key_type类型,而second元素则有map<K, V>::mapped_type类型

对迭代器进行解引用时,将获得一个引用,指向容器中一个value_type类型的值,对于map容器,其value_type是pair类型。

 

为了使用方便,可以对模板类进行一下类型定义,

typedef map<int, CString> UDT_MAP_INT_CSTRING; 
UDT_MAP_INT_CSTRING enumMap;

 

5。在map中添加元素

 

给map中添加元素主要有两种方法:

  •   使用下标操作符获取元素,然后给元素赋值

          For example:

          map<string, int> word_count; // 定义了一个空的map对象word_count;

          word_count["Anna"] = 1;

         

          程序说明:

          1.在word_count中查找键为Anna的元素,没有找到.

          2.将一个新的键-值对插入到word_count中,他的键是const string类型的对象,保存Anna。而他的值则采用直初始化,这就意味着在本例中指为0.

          3.将这个新的键-值对插入到word_count中

          4.读取新插入的元素,并将她的值赋为1.

          使用下标访问map与使用下标访问数组或者vector的行为是截然不同的:使用下标访问不存在的元素将导致在map容器中添加一个新的元素,他的键即为该下标值。

  • 使用map::insert方法添加元素

          map容器提供的insert操作:

          1. map.insert(e) : e是一个用在map中的value_type类型的值。如果键不存在,则插入一个值为e.second的新元素;如果键在map中已经存在,那么不进行任何操作。该函数返回一个pair类型,该pair类型的first元素为当前插入e的map迭代器,pair的second类型是一个bool类型,表示是否插入了该元素。

          2. map.insert(beg, end) : beg和end是迭代器,返回void类型

          3. map.insert(iter, e) : e是value_type类型的值,如果e.first不在map中,则创建新元素,并以迭代器iter为起点搜索新元素存储的位置,返回一个迭代器,指向map中具有给定键的元素。

         

          For example:

 

          word_count.insert(map<sting, int>::value_type("Anna", 1));

 

          word_count.insert(make_pair("Anna", 1)); 

 

          返回值:如果该键已在容器中,则其关联的值保持不变,返回的bool值为true。

6。查找并获取map中的元素

使用下标获取元素存在一个很危险的副作用:如果该键不在map容器中,那么下标操作会插入一个具有该键的新元素。

因此引入map对象的查询操作:

map.count(k) : 返回map中键k的出现次数(对于map而言,由于一个key对应一个value,因此返回只有0和1,因此可以用此函数判断k是否在map中)

map.find(k) :  返回map中指向键k的迭代器,如果不存在键k,则返回超出末端迭代器。

 

For example:

 

int occurs = 0;

if( word_count.cout("foobar") )

     occurs = word_count["foobar"];

 

int occurs = 0;

map<string, int>::iterator it = word_count.find("foobar");

if( it != word_count.end() )

     occurs = it ->second;

 

 

7。从map中删除元素

移除某个map中某个条目用erase()

该成员方法的定义如下:

  1. iterator erase(iterator it); //通过一个条目对象删除
  2. iterator erase(iterator first, iterator last);        //删除一个范围
  3. size_type erase(const Key& key); //通过关键字删除

8. map对象的迭代遍历

与其他容器一样,map同样提供begin和end运算,以生成用于遍历整个容器的迭代器。

posted @ 2012-08-13 10:03 章涛 阅读(286) | 评论 (0)编辑 收藏

2012年8月10日

float与double的范围和精度

1. 范围
  float和double的范围是由指数的位数来决定的。
  float的指数位有8位,而double的指数位有11位,分布如下:
  float:
  1bit(符号位) 8bits(指数位) 23bits(尾数位)
  double:
  1bit(符号位) 11bits(指数位) 52bits(尾数位)
  于是,float的指数范围为-127~+128,而double的指数范围为-1023~+1024,并且指数位是按补码的形式来划分的。
  其中负指数决定了浮点数所能表达的绝对值最小的非零数;而正指数决定了浮点数所能表达的绝对值最大的数,也即决定了浮点数的取值范围。
  float的范围为-2^128 ~ +2^128,也即-3.40E+38 ~ +3.40E+38;double的范围为-2^1024 ~ +2^1024,也即-1.79E+308 ~ +1.79E+308。

2.  精度
  float和double的精度是由尾数的位数来决定的。浮点数在内存中是按科学计数法来存储的,其整数部分始终是一个隐含着的“1”,由于它是不变的,故不能对精度造成影响。
  float:2^23 = 8388608,一共七位,这意味着最多能有7位有效数字,但绝对能保证的为6位,也即float的精度为6~7位有效数字;
  double:2^52 = 4503599627370496,一共16位,同理,double的精度为15~16位。

3.Oracle中Number类型

在Oracle中Number类型可以用来存储0,正负定点或者浮点数,可表示的数据范围在
1.0 * 10(-130) —— 9.9...9 * 10(125) {38个9后边带88个0}
的数字,当Oracle中的数学表达式的值>=1.0*10(126)时,Oracle就会报错。
Number的数据声明如下:
表示        作用        说明
Number(p, s)        声明一个定点数        p(precision)为精度,s(scale)表示小数点右边的数字个数,精度最大值为38,
Number(p)        声明一个整数        相当于Number(p, 0)
Number        声明一个浮点数        其精度为38,要注意的是scale的值没有应用,也就是说scale的指不能简单的理解为0,或者其他的数。

定点数的精度(p)和刻度(s)遵循以下规则:
?        当一个数的整数部分的长度 > p-s 时,Oracle就会报错
?        当一个数的小数部分的长度 > s 时,Oracle就会舍入。
?        当s(scale)为负数时,Oracle就对小数点左边的s个数字进行舍入。
?        当s > p 时, p表示小数点后第s位向左最多可以有多少位数字,如果大于p则Oracle报错,小数点后s位向右的数字被舍入

4.验证
create or replace function  func_test(p_type number) return number
is
/*
 功能:基于警度图数据同步
*/
 l_cnt number;
begin
 select p_type into l_cnt from dual;
 return l_cnt;
end func_test;
/
show err;

5.结论

number 的总长度是40位,其中可能包括:小数点,负号位。

select to_char(func_test(-987.1234567891234567891234567891234567891234)) from dual;
-987.12345678912345678912345678912345679   //包括小数点及负号位共40位
select to_char(func_test(9876.1234567891234567891234567891234567891234)) from dual;
9876.12345678912345678912345678912345679   //4位整数+小数点+35位小数=40位
select to_char(func_test(987.1234567891234567891234567891234567891234)) from dual;
987.123456789123456789123456789123456789   //3位整数+小数点+36位小数=40位
select to_char(func_test(1234567891234567891234567891234567891234)) from dual;
1234567891234567891234567891234567891234   //40位整数
select to_char(func_test(12345678912345678912345678912345678912345)) from dual;
1.2345678912345678912345678912345679E+40   //41位时精度发生丢失
1.2345678912345678912345678912345679×10^40 即 12345678912345678912345678912345678900000

posted @ 2012-08-10 09:05 章涛 阅读(352) | 评论 (0)编辑 收藏

2012年8月9日

文件结束标志符

cin.eof()返回流结束位,即按键 ctrl 和 z 键
如:
char gc;
while(!cin.eof()) //直至按ctrl+z键退出!
{
  cin>>gc;
  cout<<gc<<endl;
}

上面的是按ctrl+z退出
要自动退出可按下面的写:
char gc;
istream fin(....);
while(!fin.eof()) //读完文件自己退出!
{
  cin>>gc;
  cout<<gc<<endl;
}


posted @ 2012-08-09 19:38 章涛 阅读(181) | 评论 (0)编辑 收藏

这是一个linux常见命令的列表

那些有• 标记的条目,你可以直接拷贝到终端上而不需要任何修改,因此你最好开一个终端边读边剪切&拷贝
所有的命令已在Fedora和Ubuntu下做了测试

命令 描述
apropos whatis 显示和word相关的命令。 参见线程安全
man -t man | ps2pdf - > man.pdf 生成一个PDF格式的帮助文件
  which command 显示命令的完整路径名
  time command 计算命令运行的时间
time cat 开始计时. Ctrl-d停止。参见sw
nice info 运行一个低优先级命令(这里是info)
renice 19 -p $$ 使脚本运行于低优先级。用于非交互任务。
目录操作
cd - 回到前一目录
cd 回到用户目录
  (cd dir && command) 进入目录dir,执行命令command然后回到当前目录
pushd . 将当前目录压入栈,以后你可以使用popd回到此目录
alias l='ls -l --color=auto' 单字符文件列表命令
ls -lrt 按日期显示文件. 参见newest
ls /usr/bin | pr -T9 -W$COLUMNS 在当前终端宽度上打印9列输出
  find -name '*.[ch]' | xargs grep -E 'expr' 在当前目录及其子目录下所有.c和.h文件中寻找'expr'. 参见findrepo
  find -type f -print0 | xargs -r0 grep -F 'example' 在当前目录及其子目录中的常规文件中查找字符串'example'
  find -maxdepth 1 -type f | xargs grep -F 'example' 在当前目录下查找字符串'example'
  find -maxdepth 1 -type d | while read dir; do echo $dir; echo cmd2; done 对每一个找到的文件执行多个命令(使用while循环)
find -type f ! -perm -444 寻找所有不可读的文件(对网站有用)
find -type d ! -perm -111 寻找不可访问的目录(对网站有用)
locate -r 'file[^/]*\.txt' 使用locate 查找所有符合*file*.txt的文件
look reference 在(有序)字典中快速查找
grep --color reference /usr/share/dict/words 使字典中匹配的正则表达式高亮
归档 and compression
  gpg -c file 文件加密
  gpg file.gpg 文件解密
  tar -c dir/ | bzip2 > dir.tar.bz2 将目录dir/压缩打包
  bzip2 -dc dir.tar.bz2 | tar -x 展开压缩包 (对tar.gz文件使用gzip而不是bzip2)
  tar -c dir/ | gzip | gpg -c | ssh user@remote 'dd of=dir.tar.gz.gpg' 目录dir/压缩打包并放到远程机器上
  find dir/ -name '*.txt' | tar -c --files-from=- | bzip2 > dir_txt.tar.bz2 将目录dir/及其子目录下所有.txt文件打包
  find dir/ -name '*.txt' | xargs cp -a --target-directory=dir_txt/ --parents 将目录dir/及其子目录下所有.txt按照目录结构拷贝到dir_txt/
  ( tar -c /dir/to/copy ) | ( cd /where/to/ && tar -x -p ) 拷贝目录copy/到目录/where/to/并保持文件属性
  ( cd /dir/to/copy && tar -c . ) | ( cd /where/to/ && tar -x -p ) 拷贝目录copy/下的所有文件到目录/where/to/并保持文件属性
  ( tar -c /dir/to/copy ) | ssh -C user@remote 'cd /where/to/ && tar -x -p' 拷贝目录copy/到远程目录/where/to/并保持文件属性
  dd bs=1M if=/dev/sda | gzip | ssh user@remote 'dd of=sda.gz' 将整个硬盘备份到远程机器上
rsync (使用 --dry-run选项进行测试)
  rsync -P rsync://rsync.server.com/path/to/file file 只获取diffs.当下载有问题时可以作多次
  rsync --bwlimit=1000 fromfile tofile 有速度限制的本地拷贝,对I/O有利
  rsync -az -e ssh --delete ~/public_html/ remote.com:'~/public_html' 镜像网站(使用压缩和加密)
  rsync -auz -e ssh remote:/dir/ . && rsync -auz -e ssh . remote:/dir/ 同步当前目录和远程目录
ssh (安全 Shell)
  ssh $USER@$HOST command 在$Host主机上以$User用户运行命令(默认命令为Shell)
ssh -f -Y $USER@$HOSTNAME xeyes 在名为$HOSTNAME的主机上以$USER用户运行GUI命令
  scp -p -r $USER@$HOST: file dir/ 拷贝到$HOST主机$USER'用户的目录下
  ssh -g -L 8080:localhost:80 root@$HOST 由本地主机的8080端口转发到$HOST主机的80端口
  ssh -R 1434:imap:143 root@$HOST 由主机的1434端口转发到imap的143端口
wget (多用途下载工具)
(cd cmdline && wget -nd -pHEKk http://www.pixelbeat.org/cmdline.html) 在当前目录中下载指定网页及其相关的文件使其可完全浏览
  wget -c http://www.example.com/large.file 继续上次未完的下载
  wget -r -nd -np -l1 -A '*.jpg' http://www.example.com/ 批量下载文件到当前目录中
  wget ftp://remote/file[1-9].iso/ 下载FTP站上的整个目录
wget -q -O- http://www.pixelbeat.org/timeline.html | grep 'a href' | head 直接处理输出
  echo 'wget url' | at 01:00 在下午一点钟下载指定文件到当前目录
  wget --limit-rate=20k url 限制下载速度(这里限制到20KB/s)
  wget -nv --spider --force-html -i bookmarks.html 检查文件中的链接是否存在
  wget --mirror http://www.example.com/ 更新网站的本地拷贝(可以方便地用于cron)
网络(ifconfig, route, mii-tool, nslookup 命令皆已过时)
  ethtool eth0 显示网卡eth0的状态
  ethtool --change eth0 autoneg off speed 100 duplex full 手动设制网卡速度
  iwconfig eth1 显示无线网卡eth1的状态
  iwconfig eth1 rate 1Mb/s fixed 手动设制无线网卡速度
iwlist scan 显示无线网络列表
ip link show 显示interface列表
  ip link set dev eth0 name wan 重命名eth0为wan
  ip link set dev eth0 up 启动interface eth0(或关闭)
ip addr show 显示网卡的IP地址
  ip addr add 1.2.3.4/24 brd + dev eth0 添加ip和掩码(255.255.255.0)
ip route show 显示路由列表
  ip route add default via 1.2.3.254 设置默认网关1.2.3.254
tc qdisc add dev lo root handle 1:0 netem delay 20msec 增加20ms传输时间到loopback设备(调试用)
tc qdisc del dev lo root 移除上面添加的传输时间
host pixelbeat.org 查寻主机的DNS IP地址
hostname -i 查寻本地主机的IP地址(同等于host `hostname`)
whois pixelbeat.org 查寻某主机或莫IP地址的whois信息
netstat -tupl 列出系统中的internet服务
netstat -tup 列出活跃的连接
windows networking (samba提供所有windows相关的网络支持)
smbtree 寻找一个windows主机. 参见findsmb
  nmblookup -A 1.2.3.4 寻找一个指定ip的windows (netbios)名
  smbclient -L windows_box 显示在windows主机或samba服务器上的所有共享
  mount -t smbfs -o fmask=666,guest //windows_box/share /mnt/share 挂载一个windows共享
  echo 'message' | smbclient -M windows_box 发送一个弹出信息到windows主机(XP sp2默认关闭此功能)
文本操作 (sed使用标准输入和标准输出,如果想要编辑文件,则需添加<oldfile >newfile)
  sed 's/string1/string2/g' 使用string2替换string1
  sed 's/\(.*\)1/\12/g' 将任何以1结尾的字符串替换为以2结尾的字符串
  sed '/ *#/d; /^ *$/d' 删除注释和空白行
  sed ':a; /\\$/N; s/\\\n//; ta' 连接结尾有\的行和其下一行
  sed 's/[ \t]*$//' 删除每行后的空白
  sed 's/\([\\`\\"$\\\\]\)/\\\1/g' 将所有转义字符之前加上\
seq 10 | sed "s/^/      /; s/ *\(.\{7,\}\)/\1/" 向右排N(任意数)列
  sed -n '1000p;1000q' 输出第一千行
  sed -n '10,20p;20q' 输出第10-20行
  sed -n 's/.*<title>\(.*\)<\/title>.*/\1/ip;T;q' 输出HTML文件的<title></title>字段中的 内容
  sort -t. -k1,1n -k2,2n -k3,3n -k4,4n 排序IPV4地址
echo 'Test' | tr '[:lower:]' '[:upper:]' 转换成大写
tr -dc '[:print:]' < /dev/urandom 过滤掉不能打印的字符
history | wc -l 计算指定单词出现的次数
集合操作 (如果是英文文本的话export LANG=C可以提高速度)
  sort file1 file2 | uniq 两个未排序文件的并集
  sort file1 file2 | uniq -d 两个未排序文件的交集
  sort file1 file1 file2 | uniq -u 两个未排序文件的差 集
  sort file1 file2 | uniq -u 两个未排序文件的对称差集
  join -t'\0' -a1 -a2 file1 file2 两个有序文件的并集
  join -t'\0' file1 file2 两个有序文件的交集
  join -t'\0' -v2 file1 file2 两个有序文件的差集
  join -t'\0' -v1 -v2 file1 file2 两个有序文件的对称差集
数学
echo '(1 + sqrt(5))/2' | bc -l 方便的计算器(计算 φ)
echo 'pad=20; min=64; (100*10^6)/((pad+min)*8)' | bc 更复杂地计算,这里计算了最大的FastE包率
echo 'pad=20; min=64; print (100E6)/((pad+min)*8)' | python Python处理数值的科学表示法
echo 'pad=20; plot [64:1518] (100*10**6)/((pad+x)*8)' | gnuplot -persist 显示FastE包率相对于包大小的图形
echo 'obase=16; ibase=10; 64206' | bc 进制转换(十进制到十六进制)
echo $((0x2dec)) 进制转换(十六进制到十进制)((shell数学扩展))
units -t '100m/9.58s' 'miles/hour' 单位转换(公尺到英尺)
units -t '500GB' 'GiB' 单位转换(SIIEC 前缀)
units -t '1 googol' 定义查找
seq 100 | (tr '\n' +; echo 0) | bc 加N(任意数)列. 参见 add and funcpy
日历
cal -3 显示一日历
cal 9 1752 显示指定月,年的日历
date -d fri 这个星期五是几号. 参见day
date --date='25 Dec' +%A 今年的圣诞节是星期几
date --date '1970-01-01 UTC 2147483647 seconds' 将一相对于1970-01-01 00:00的秒数转换成时间
TZ=':America/Los_Angeles' date 显示当前的美国西岸时间(使用tzselect寻找时区)
  echo "mail -s 'get the train' P@draigBrady.com < /dev/null" | at 17:45 在指定的时间发送邮件
echo "DISPLAY=$DISPLAY xmessage cooker" | at "NOW + 30 minutes" 在给定的时间弹出对话框
locales
printf "%'d\n" 1234 根据locale输出正确的数字分隔
BLOCK_SIZE=\'1 ls -l 用ls命令作类适于locale()文件分组
echo "I live in `locale territory`" 从locale数据库中展开信息
LANG=en_IE.utf8 locale int_prefix 查找指定地区的locale信息。参见ccodes
locale | cut -d= -f1 | xargs locale -kc | less 显示在locale数据库中的所有字段
recode (iconv, dos2unix, unix2dos 已经过时了)
recode -l | less 显示所有有效的字符集及其别名
  recode windows-1252.. file_to_change.txt 转换Windows下的ansi文件到当前的字符集(自动进行回车换行符的转换)
  recode utf-8/CRLF.. file_to_change.txt 转换Windows下的ansi文件到当前的字符集
  recode iso-8859-15..utf8 file_to_change.txt 转换Latin9(西欧)字符集文件到utf8
  recode ../b64 < file.txt > file.b64 Base64编码
  recode /qp.. < file.txt > file.qp Quoted-printable格式解码
  recode ..HTML < file.txt > file.html 将文本文件转换成HTML
recode -lf windows-1252 | grep euro 字符表中查找欧元符号
echo -n 0x80 | recode latin-9/x1..dump 显示字符在latin-9中的字符映射
echo -n 0x20AC | recode ucs-2/x2..latin-9/x 显示latin-9编码
echo -n 0x20AC | recode ucs-2/x2..utf-8/x 显示utf-8编码
光盘
  gzip < /dev/cdrom > cdrom.iso.gz 保存光盘拷贝
  mkisofs -V LABEL -r dir | gzip > cdrom.iso.gz 建立目录dir的光盘镜像
  mount -o loop cdrom.iso /mnt/dir 将光盘镜像挂载到 /mnt/dir (只读)
  cdrecord -v dev=/dev/cdrom blank=fast 清空一张CDRW
  gzip -dc cdrom.iso.gz | cdrecord -v dev=/dev/cdrom - 烧录光盘镜像 (使用 dev=ATAPI -scanbus 来确认该使用的 dev)
  cdparanoia -B 在当前目录下将光盘音轨转录成wav文件
  cdrecord -v dev=/dev/cdrom -audio *.wav 将当前目录下的wav文件烧成音乐光盘 (参见cdrdao)
  oggenc --tracknum='track' track.cdda.wav -o 'track.ogg' 将wav文件转换成ogg格式
磁盘空间 (参见FSlint)
ls -lSr 按文件大小降序显示文件
du -s * | sort -k1,1rn | head 显示当前目录下占用空间最大的一批文件. 参见dutop
df -h 显示空余的磁盘空间
df -i 显示空余的inode
fdisk -l 显示磁盘分区大小和类型(在root下执行)
rpm -q -a --qf '%10{SIZE}\t%{NAME}\n' | sort -k1,1n 显示所有在rpm发布版上安装的,并以包字节大小为序
dpkg-query -W -f='${Installed-Size;10}\t${Package}\n' | sort -k1,1n 显示所有在deb发布版上安装的,并以KB包大小为序
dd bs=1 seek=2TB if=/dev/null of=ext3.test 建立一个大的测试文件(不占用空间). 参见truncate
监视/调试
tail -f /var/log/messages 监视Messages日志文件
strace -c ls >/dev/null 总结/剖析命令进行的系统调用
strace -f -e open ls >/dev/null 显示命令进行的系统调用
ltrace -f -e getenv ls >/dev/null 显示命令调用的库函数
lsof -p $$ 显示当前进程打开的文件
lsof ~ 显示打开用户目录的进程
tcpdump not port 22 显示除了ssh外的网络交通. 参见tcpdump_not_me
ps -e -o pid,args --forest 以树状结构显示进程
ps -e -o pcpu,cpu,nice,state,cputime,args --sort pcpu | sed '/^ 0.0 /d' 以CPU占用率为序显示进程
ps -e -orss=,args= | sort -b -k1,1n | pr -TW$COLUMNS 以内存使用量为序显示进程. 参见ps_mem.py
ps -C firefox-bin -L -o pid,tid,pcpu,state 显示指定进程的所有线程信息
ps -p 1,2 显示指定进程ID的进程信息
last reboot 显示系统重启记录
free -m 显示(剩余的)内存总量(-m以MB为单位显示)
watch -n.1 'cat /proc/interrupts' 监测文件/proc/interrupts的变化
系统信息 (参见sysinfo)
uname -a 查看内核/操作系统/CPU信息
head -n1 /etc/issue 查看操作系统版本
cat /proc/partitions 显示所有在系统中注册的分区
grep MemTotal /proc/meminfo 显示系统可见的内存总量
grep "model name" /proc/cpuinfo 显示CPU信息
lspci -tv 显示PCI信息
lsusb -tv 显示USB信息
mount | column -t 显示所有挂载的文件系统并对齐输出
# dmidecode -q | less 显示SMBIOS/DMI 信息
# smartctl -A /dev/sda | grep Power_On_Hours 系统开机的总体时间
# hdparm -i /dev/sda 显示关于磁盘sda的信息
# hdparm -tT /dev/sda 检测磁盘sda的读取速度
# badblocks -s /dev/sda 检测磁盘sda上所有的坏扇区
交互 (参见linux keyboard shortcut database)
readline Line editor used by bash, python, bc, gnuplot, ...
screen 多窗口的虚拟终端, ...
mc 强大的文件管理器,可以浏览rpm, tar, ftp, ssh, ...
gnuplot 交互式并可进行脚本编程的画图工具
links 网页浏览器
miscellaneous
alias hd='od -Ax -tx1z -v' 方便的十六进制输出。 (用法举例: • hd /proc/self/cmdline | less)
alias realpath='readlink -f' 显示符号链接指向的真实路径((用法举例: • realpath ~/../$USER)
set | grep $USER 在当前环境中查找
  touch -c -t 0304050607 file 改变文件的时间标签 (YYMMDDhhmm)
python -m SimpleHTTPServer Serve current directory tree at http://$HOSTNAME:8000/

posted @ 2012-08-09 17:25 章涛 阅读(105) | 评论 (0)编辑 收藏

一个类的对象作为另一个类的数据成员

一个类的对象作为另一个类的数据成员

一个类的对象作为另一个类的数据成员
如果一个类A的对象作为另一个类B的数据成员,则在类B的对象创建过程中,调用其构造函数的过程中,数据成员(类A的对象)会自动调用类A的构造函数。
但应注意:如果类A的构造函数为有参函数时,则在程序中必须在类B的构造函数的括号后面加一“:”和被调用的类A的构造函数,且调用类A的构造函数时的实参值必须来自类B的形参表中的形参。这种方法称为初始化表的方式调用构造函数。如:以上面定义的类X为例,在对类X的对象进行初始化时,必须首先初始化其中的子对象,即必须首先调用这些子对象的构造函数。因此,类X的构造函数的定义格式应为:
X::X(参数表0):成员1(参数表1),成员2(参数表2),…,成员n(参数表n)
{ ……}
其中,参数表1提供初始化成员1所需的参数,参数表2提供初始化成员2所需的参数,依此类推。并且这几个参数表的中的参数均来自参数表0,另外,初始化X的非对象成员所需的参数,也由参数表0提供。
在构造新类的对象过程中,系统首先调用其子对象的构造函数,初始化子对象;然后才执行类X自己的构造函数,初始化类中的非对象成员。对于同一类中的不同子对象,系统按照它们在类中的说明顺序调用相应的构造函数进行初始化,而不是按照初始化表的顺序。

试分析以下程序的执行结果:
#include <iostream.h>
#include <string.h>
class Student
{ public:
   Student(char *pName="No name")
      { cout<<"构造新同学:"<<pName<<endl;
         strncpy(name,pName,sizeof(name));
         name[sizeof(name)-1]='\0'; 
        }
 Student(Student &s)
      { cout<<"构造copy of "<<s.name<<endl;
         strcpy(name, " copy of ");
         strcat(name,s.name);
         }
~Student()
 { cout<<"析构 "<<name<<endl; }
    protected:
    char name[40];  };
class Tutor
{ public:
       Tutor(Student &s):student(s)//此为初始化表,调用
                                                     //Student的拷贝构造函数
       { cout<<"构造指导教师 \n";  }
   protected:
        Student student;
 };
void main()
{  Student st1;   //此处调用Student的构造函数Student(char 
           *pName="No name")
   Student st2("zhang"); //同上
   Tutor tutor(st2); //此处调用Tutor的构造函数Tutor(Student &s)
   //在构造tutor对象的过程中,用初始化表调用
   //Student类的拷贝构造函数Student(Student &s)
}
执行结果如下:
构造新同学:No name
构造新同学:zhang
构造copy of zhang
构造指导教师
析构  copy of zhang
析构 zhang
析构 No name

posted @ 2012-08-09 15:25 章涛 阅读(3125) | 评论 (0)编辑 收藏

C++中string--->char[] / char[]--->string

string--->char[]

string str = "abcd";
char *ch = str.c_str();

char[]--->string

#include <iostream>
#include <string>
using namespace std;
int main(void)
{
char str[]="hello";
//方法1
string ss1(str);
//方法2
string ss2;
ss2=str;
//方法3
string ss3;
ss3.insert(0,str);
cout<<ss1<<endl<<ss2<<endl<<ss3<<endl;
return 0;
}
语法:
const char *c_str();
c_str()函数返回一个指向正规C字符串的指针, 内容与本string串相同.
这是为了与c语言兼容,在c语言中没有string类型,故必须通过string类对象的成员函数c_str()把string 对象转换成c中的字符串样式。
注意:一定要使用strcpy()函数 等来操作方法c_str()返回的指针
比如:最好不要这样:
char* c;
string s="1234";
c = s.c_str(); //c最后指向的内容是垃圾,因为s对象被析构,其内容被处理

应该这样用:
char c[20];
string s="1234";
strcpy(c,s.c_str());
这样才不会出错,c_str()返回的是一个临时指针,不能对其进行操作

再举个例子
c_str() 以 char* 形式传回 string 内含字符串
如果一个函数要求char*参数,可以使用c_str()方法:
string s = "Hello World!";
printf("%s", s.c_str()); //输出 "Hello World!"

posted @ 2012-08-09 10:12 章涛 阅读(198) | 评论 (0)编辑 收藏

2012年8月2日

C++数据结构之单链表

线性表包含数据域和指针域。单链表用一组地址任意的存储单元存放线性表中的数据元素。

线性表包含 数据域和指针域 其中,data存储数据本身的值,next存储后继元素的地址 下面的图表示的是一个数据节点

单链表的结构示意图(包括空的单链表):

单链表的节点类:

  1.  template<classT>  
  2. classNode  
  3. {  
  4. public:  
  5. T data;//数据  
  6. Node<T> *next;//next指针  
  7. Node()  
  8. {  
  9. this->next=NULL;//构造空的节点  
  10. }  
  11. Node(T data,Node<T> *next=NULL)//构造一个节点  
  12. {  
  13. this->data=data;  
  14. this->next=next;  
  15. }  
  16. }; 

 

单链表类声明如下:

 

  1. #include<iostream>  
  2. #include "Node.h"//单链表节点类  
  3. template<classT>  
  4. classSinglyLinkedList //单链表类  
  5. {  
  6. public:  
  7. Node<T> *head;//单链表的头指针。  
  8. SinglyLinkedList();//构造空的单链表。  
  9. SinglyLinkedList(T value[], intn);//构造由指定的数组提供的单链表  
  10. ~SinglyLinkedList();//析构  
  11. boolisEmpty();//判断是否为空。  
  12. intlength();//获取长度  
  13. Node<T>* getNode(inti);//返回第i(i>=0)个节点指针  
  14. get(inti);//返回第i个元素  
  15. boolset(inti,T x);//设置第i个元素为x  
  16. template<classT> friend std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list);  
  17. Node<T>* insert(inti,T x);//插入第I个节点并返回第i个节点的指针  
  18. boolremove(inti,T& old);//删除第i个元素,将删除的元素存放到old  
  19. voidclear();//清空单链表  
  20. voidconcat(SinglyLinkedList<T> &list);//将List链接在当前单链表之后  
  21. }; 

 

单链表部分如构造空的链表对象,析构,判断为空的实现,没有要讲的算法,实现如下:

 

  1. template<classT>  
  2. SinglyLinkedList<T>::SinglyLinkedList()//构造空的单链表  
  3. {  
  4. this->head=NULL;  
  5.  }  
  6. template<classT>  
  7. SinglyLinkedList<T>::~SinglyLinkedList()//析构  
  8. {  
  9. clear();  
  10. }  
  11. template<classT>  
  12. boolSinglyLinkedList<T>::isEmpty()//判断链表是否为空  
  13. {  
  14. returnthis->head==NULL;  

 

单链表的遍历操作,遍历单链表是指从第一个节点开始访问,沿着节点的Next可依次访问单链表中的各个节点,并且各个节点只被访问一次。实现的单链表遍历的基本算法如下:

 

  1. intj=0;  
  2. Node<T> *p=head;  
  3. while(p!=NULL&&j<i)  
  4. {  
  5. j++;  
  6. p=p->next;  

 

单链表的length(),get(),set(),clear()和输出等操作都基于以上算法。

  1. template<classT>  
  2. intSinglyLinkedList<T>::length()  
  3. {  
  4.  inti=0;  
  5. Node<T> *p=head;//创建一个用于遍的变量  
  6. while(p!=NULL)  
  7. {  
  8. i++;  
  9. std::cout<<p->data;  
  10. p=p->next;  
  11. }  
  12.  returni;  
  13. }  
  14. template<classT>  
  15. Node<T>* SinglyLinkedList<T>::getNode(inti)  
  16. {  
  17. if(i<0)  
  18. returnNULL;  
  19. intj=0;  
  20. Node<T> *p=head;  
  21. while(p!=NULL&&j<i)  
  22. {  
  23. j++;  
  24. p=p->next;  
  25. }  
  26. returnp;  
  27. }  
  28. template<classT>  
  29. T SinglyLinkedList<T>::get(inti)  
  30. {  
  31. Node<T> *p=getNode(i);  
  32. if(p!=NULL)  
  33. returnp->data;  
  34. T d;  
  35. returnd;  
  36. //throw "单链表为空或者参数指定的元素不存在";  
  37. }  
  38. template<classT>  
  39. boolSinglyLinkedList<T>::set(inti,T x)  
  40. {  
  41. Node<T> *p=getNode(i);  
  42. if(p!=NULL)  
  43. {  
  44. p->data=x;  
  45. returntrue;  
  46. }  
  47. returnfalse;  
  48. }  
  49. template<classT>  
  50. std::ostream& operator<<(std::ostream& out,SinglyLinkedList<T> &list)  
  51. {  
  52. Node<T> *p=list.head;  
  53. out<<"(";  
  54. while(p!=NULL)  
  55. {  
  56. out<<p->data;  
  57. p=p->next;  
  58. if(p!=NULL)  
  59. out<<",";  
  60. }  
  61. out<<") ";  
  62. returnout;  
  63. }  
  64. template<classT>  
  65. voidSinglyLinkedList<T>::clear()  
  66. {  
  67. Node<T> *p=head;  
  68. while(p!=NULL)  
  69. {  
  70. Node<T> *q=p;  
  71. p=p->next;  
  72. delete q;  
  73. }  
  74. head=NULL;  
  75.  } 

单链表的插入操作,单链表不像顺序表,对与表的插入和删除很简单:

空表插入/头插入

  1. Node<T> *q=NULL;  
  2. if(head==NULL||i<0)//头插入(单链表为空或者)  
  3. {  
  4. q=newNode<T>(x,head);  
  5. head=q;  
  6. }  
  7. 中间插入/尾插入  
  8. p->next=newNode<T>(x,p->next);  
  9. 单链表insert()以及参数构造函数:  
  10.  template<classT>  
  11. Node<T>* SinglyLinkedList<T>::insert(inti,T x)  
  12. {  
  13. Node<T> *q=NULL;  
  14. if(head==NULL||i<0)//头插入(单链表为空或者)  
  15. {  
  16. q=newNode<T>(x,head);  
  17. head=q;  
  18. }  
  19. else 
  20. {  
  21. intj=0;  
  22. Node<T> *p=head;  
  23. while(p->next!=NULL&&j<i-1)  
  24. {  
  25. j++;  
  26. p=p->next;  
  27. }  
  28. q=newNode<T>(x,p->next);  
  29.  p->next=q;  
  30. }  
  31. returnq;  
  32. }  
  33.  template<classT>  
  34. SinglyLinkedList<T>::SinglyLinkedList(T table[],intn)  
  35. {  
  36. head=NULL;  
  37. if(n>0)  
  38. {  
  39. head=newNode<T>(table[0]);//创建节点  
  40.  Node<T> *rear=head;//创建一个指向头节点的指针  
  41. inti=1;  
  42.  while(i<n)  
  43. {  
  44. rear->next=newNode<T>(table[i++]);  
  45. rear=rear->next;  
  46. }  
  47. }  

 单链表的删除操作也分两类:

头删除

  1. Node<T> *q=head;  
  2. head=head->next;  
  3. delete q; 

中间/尾删除

  1. Node<T> *q=p->next;  
  2. if(q!=NULL)//判断删除节点  
  3. {  
  4. p->next=q->next;//让删除节点的前驱Next指针下一节点  
  5. delete q;//删除该节点  

单链表的删除函数remove()实现:

  1. template<classT>  
  2. boolSinglyLinkedList<T>::remove(inti,T &old)  
  3. {  
  4. if(i<0||head==NULL)  
  5. {  
  6. Node<T> *q=head;  
  7. old=q->data;  
  8. head=head->next;  
  9. delete q;  
  10.  }  
  11. else 
  12. {  
  13. Node<T> *p=getNode(i-1);//获取删除节点的前驱  
  14.  if(p!=NULL&&p->next!=NULL)//判断删除节点和删除节点是否为空  
  15. {  
  16. Node<T> *q=p->next;//新建一个节点指针,将删除接点复制过去  
  17. old=q->data;  
  18. p->next=q->next;//让删除节点的前驱Next指针下一节点  
  19. delete q;//删除该节点  
  20.  returntrue;  
  21. }  
  22.  }  
  23. returnfalse;  
  24. }  
  25. 单链表的链接函数:concat()  
  26. template<classT>  
  27. voidSinglyLinkedList<T>::concat(SinglyLinkedList<T> &list)  
  28. {  
  29. if(this->head==NULL)  
  30. {  
  31. this->head=list->head;  
  32. }  
  33. else 
  34. {  
  35. Node<T> *p=head;  
  36. while(p->next!=NULL)  
  37. {  
  38. p=p->next;  
  39. }  
  40. p=list->head;  
  41. }  
  42. list->head=NULL;//设置单链表为空,否则运行出错  

以上对C++单链表的分析 添加一个学生结构和一个测试函数:

  1. Student.h  
  2. structStudent  
  3. {  
  4. charnumber[10]; //学号  
  5. charname[20]; //姓名  
  6. doublescore; //得分  
  7. friend std::ostream& operator<<(std::ostream& out,Student &stu)  
  8. {  
  9. out<<"学号:"<<stu.number<<"姓名:"<<stu.name<<"得分:"<<stu.score;  
  10. returnout;  
  11. }  
  12. };  
  13. 主函数:  
  14. #include<iostream>  
  15. #include "SinglyLinkedList.h" 
  16. #include "Student.h" 
  17. void_TestToSinglyLinkedList()  
  18. {  
  19. Student data[]={{"090313018","Silvester",45.4},{"090313018","捐赠",45.4},{"090313018","版主",45.6}};  
  20. SinglyLinkedList<Student> m(data,3);  
  21. Student t;  
  22. std::cout<<(m.isEmpty()?"不为空!":"该链表为空!")<<std::endl;  
  23. std::cout<<"长度:"<<m.length()<<std::endl;  
  24. std::cout<<"移除2个学生"<<m.remove(1,t)<<std::endl;  
  25. std::cout<<"t:"<<t<<std::endl;  
  26. std::cout<<"2个学生信息"<<m.getNode(1)<<std::endl;  
  27. Student s={"415646","fdsfs",453.1};  
  28. std::cout<<m.get(1)<<m.set(1,s)<<m.insert(5,s)<<std::endl;  
  29. }  
  30. voidmain()  
  31.  {  
  32. _TestToSinglyLinkedList();  
  33. system("pause");  

提供源代码下载地址:http://39327.42la.com.cn/DataFile/Code/C++/SinglyLinkedList.zip

原文地址:http://www.cnblogs.com/Arrays/archive/2012/02/01/2335164.html

posted @ 2012-08-02 14:58 章涛 阅读(187) | 评论 (0)编辑 收藏

仅列出标题  下一页
<2019年10月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜