【链表】
链表是一种线性数据结构，与数组不同，它不连续存储数据。链表中的每个元素称为节点，包含数据域和指针域，指针域指向下一个节点。在C++中，可以使用结构体来定义链表节点。例如：
```cpp
typedef struct node {
int age; // 数据域
struct node *next; // 指针域，指向下一个节点
} Node, *pNode;
```
插入节点到链表末尾的代码如下：
```cpp
void main(void) {
Node *no;
pNode p = NULL;
int x = 5;
while (1) {
no = (Node *)malloc(sizeof(node));
no->age = x;
no->next = p;
p = no;
}
}
```
【数组排序】
数组排序中常见的算法是冒泡排序，它通过重复遍历数组，比较相邻元素并根据需要交换它们的位置来实现排序。以下是一个简单的冒泡排序实现：
```cpp
void sort(int* arr) {
int i, j;
for (i = 0; i < arr[len - 1]; i++) { // 注意：这里应该是 arr[len - 1]
for (j = 0; j < arr[len] - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int t;
t = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = t;
}
}
}
}
// 注意：在调用sort函数之前，需要确保arr数组长度可用，例如：arr[len]
```
【类与对象】
C++中的类是创建对象的蓝图，它可以包含数据成员（变量）和成员函数（方法）。构造函数是在创建对象时自动调用的特殊函数，析构函数则在对象生命周期结束时调用。拷贝构造函数用于创建一个已存在对象的副本。例如：
```cpp
class shape {
private:
public:
shape() { cout << "this is a shape"; } // 构造函数
~shape() { cout << "this is not a shape"; } // 析构函数
shape(const shape& s) {} // 拷贝构造函数
const shape& operator=(const string& s) {} // 赋值运算符
};
```
【模板】
模板是C++中的泛型编程工具，允许我们创建可应用于不同类型的数据的函数或类。例如，下面是一个简单的模板函数，用于增加正数：
```cpp
template <class T>
T func(T x) {
if (x > 0)
x += 1;
return x;
}
```
【容器STL】
标准模板库（STL）是C++的一部分，提供了一组容器，如`list`，`vector`等，方便管理和操作数据。例如，下面展示了如何使用`list`容器：
```cpp
#include <iostream>
#include <list>
int main() {
std::list<std::string> str;
str.push_back("hello");
}
```
【运算符重载】
C++允许重载运算符，以自定义其行为。例如，对于复数类`complex`，我们可以重载加法和乘法运算符：
```cpp
class complex {
double re, im;
public:
complex(double r, double i): re(r), im(i) {}
complex operator+(complex); // 加法运算符
complex operator*(complex); // 乘法运算符
};
```
【动态内存管理】
C++提供了`malloc`/`free`和`new`/`delete`来处理动态内存。例如：
```cpp
int *p = (int*)malloc(sizeof(int) * length);
int *p = new int[length];
delete[] p;
```
**题目要求设计的部分：**
1. **栈的设计**：
使用模板类实现一个栈，支持任意类型。栈的基本操作包括初始化、压栈、出栈。可以使用数组作为底层数据结构：
```cpp
template <class T>
#define MAXSIZE 1024
typedef struct {
T data[MAXSIZE];
int len;
} Dstack, *pstack;
void initStack(pstack &pst) {
pst = (pstack)malloc(sizeof(Dstack));
pst->len = -1;
}
void push(pstack &pst, T tt) {
if (pst->len < MAXSIZE - 1) {
pst->len += 1;
pst->data[pst->len] = tt;
}
}
// 其他如pop、isEmpty等操作
```
2. **图形类设计**：
设计一个图形类层次结构，包括基类`CShape`和派生类`CPoint`, `CLine`, `CCury`, `CRect`, `CEclipse`。每个类应实现计算面积（`CacuArea`）、判断点是否在图形内（`PtInShape`）以及绘制（`Draw`）等方法：
```cpp
class CShape {
private:
int ar;
public:
CShape() : ar(0) {}
virtual ~CShape() {}
virtual int area() { return ar; }
virtual bool PtInShape() {}
virtual void draw() {}
};
class CPoint : public CShape {
private:
public:
};
class CLine : public CShape {
private:
public:
};
class CRect : public CShape {
private:
public:
};
// 类Cury, CEclipse类似
```
3. **链表设计**：
使用模板类实现链表，支持在指定位置插入（`insertBefore`, `insertAfter`）、移除（`removeAt`）和获取元素（`getAt`）等操作：
```cpp
template <class T>
typedef struct node {
T data;
struct node* next;
} Dnode, *Pnode;
void insertBefore(Pnode &head, T value, Pnode pos) {
Dnode *newNode = new Dnode;
newNode->data = value;
newNode->next = pos;
if (pos == head)
head = newNode;
else
pos->prev->next = newNode;
pos->prev = newNode;
}
// 其他如insertAfter, removeAt, getAt等操作
```
以上内容涵盖了链表、数组排序、类和对象、模板、STL容器、运算符重载以及动态内存管理等多个C++编程知识点。
