文档介绍：数据结构与算法
-
Review
数据结构
算法
C++
算法的五个重要特性
有穷性:一个算法必须总是在执行有穷步之后结束,且每一步都可在有穷时间内完成;
确定性:算法中每一条指令必须有确切的含义;
可行性:一个算法是能行的,即算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现;
输入:一个算法有零个或多个输入,这些输入取自某个特定的对象集;
输出:一个算法有一个或多个输出,这些输出是同输入有着某些特定关系的量。
算法设计的要求
正确性(Correctness)
语法正确
对一般数据,执行结果正确
对苛刻数据,执行结果正确
对所有数据,执行结果正确
可读性(Readability)
健壮性(Robustness)
效率与低存储量要求
ADT in C++
class ctr {
public:
ctr() { n = 0; } constructor
~ctr() { cout << "bye"; }; destructor
void add( int i = 1) { n = n + i; }
int val( ) { return n; }
private:
int n;
};
Usage
ctr c; (1); cout << ();
ctr* p = new ctr(); c->add(1); cout << c->val();
Inheritance
class A { ancestor
public:
A() { n = 0; }
void add( int i ) { n = n + i; }
virtual int val() { return n; }
protected: private would deny access to D
int n;
};
class D : public A { descendant
public:
D() : A() { }
int val() { return n \% 2; }
};
C++ Techniques
templates -- template<classT> class C { ... }
overloading -- void read(int); voi read(float)
friends -- to bypass protection
type conversions -- by class constructors or type operators
type coercion -- by explicit casts (is dangerous)
smart pointers -- by overloading de-reference
class ctr { C++ techniques
public:
ctr(int i = 0) { n = i; }
ctr(const char* s = "0") { n = itoa(s); }
void operator++() { n = n + 1; }
int operator()() { return n; }
operator char*() { return atoi(n); }
private:
int n;
};
Usage
ctr c; c++; cout << (char*) c << " is " << c();
线性表
线性表的类型定义
线性表的顺序表示和实现
线性表的链式表示和实现
一元多项式的表示及相加
什么是线性表
C
B
A
线性表是一个结点序列。对线性表的基本操作包括:插入结点、删除结点,而且可以对表中任意位置的结点做取值、替换操作。其它重要的操作还有合并、分裂。
位置
1
2
3
序号
0
1
2