### 数据结构基础知识点详解
#### 一、语句频度计算
在计算机科学中，**语句频度**指的是特定代码段中某条语句被执行的次数。这有助于我们了解算法的时间复杂度。
##### 示例代码解析
考虑如下代码段：
```c
for(i=1;i<=n;i++)
for(j=1;j<=i;j++)
for(k=1;k<=j;k++)
x=x+1;
```
这段代码中`x=x+1;`语句的频度可以通过分析三层循环来计算：
1. **最外层循环**: `for(i=1;i<=n;i++)` 运行`n`次。
2. **中间层循环**: 对于每一个`i`值，`for(j=1;j<=i;j++)`运行`i`次。
3. **内层循环**: 对于每一个`j`值，`for(k=1;k<=j;k++)`运行`j`次。
因此，对于每一个`i`值，语句`x=x+1;`总共执行`1 + 2 + 3 + ... + i`次。根据等差数列求和公式，可以得出：
- 当`i=1`时，`1 = (1+1) * 1 / 2 = (1+1)/2`
- 当`i=2`时，`1 + 2 = (1+2) * 2 / 2 = (2+2^2)/2`
- 当`i=3`时，`1 + 2 + 3 = (1+3) * 3 / 2 = (3+3^2)/2`
- ...
- 当`i=n`时，`1 + 2 + 3 + … + n = (1+n) * n / 2 = (n+n^2)/2`
综合以上公式，整个代码段中`x=x+1;`语句的总频度`f(n)`可以通过以下公式计算：
- `f(n) = [(1+2+3+…+n) + (1+2+3+…+n)] / 2`
- `f(n) = [n(n+1)/2 + n(n+1)(2n+1)/6] / 2`
- `f(n) = n(n+1)(n+2)/6`
- `f(n) = n/6 + n/2 + n/3`
最终得到语句频度为`f(n) = O(n)`。
#### 二、多项式值计算算法
问题要求编写一个算法计算多项式`Pn(x) = a0 + a1x + a2x^2 + ... + anx^n`的值`P(x)`，不使用求幂函数。
##### 算法设计
我们可以利用多项式的性质来简化计算过程：
1. **初始化**:
- `p = 1` (x的0次幂)
- `s = 0`
2. **循环**:
- `for i from 0 to n`
- `s = s + a[i] * p`
- `p = p * x`
或者：
1. **初始化**:
- `p = x` (x的1次幂)
- `s = a[0]`
2. **循环**:
- `for i from 1 to n`
- `s = s + a[i] * p`
- `p = p * x`
##### 输入输出方式
- **参数传递**：通过参数列表直接传递输入数据。
- **优点**：清晰、易于理解和维护。
- **缺点**：可能会导致代码重复。
- **全局变量传递**：通过全局变量隐式传递输入数据。
- **优点**：减少了参数的数量，使函数更加简洁。
- **缺点**：降低了代码的可读性和可维护性。
建议使用参数传递方式，因为它更符合良好的编程实践。
#### 三、线性表的基本概念
在数据结构中，**线性表**是最基本的数据结构之一，包括**顺序表**和**链表**。
##### 头指针、头结点与首元素结点的区别
- **头指针**：指向线性表中第一个元素结点的指针。
- **头结点**：在链表的第一个元素结点之前增加的一个特殊结点，用于简化操作。
- **首元素结点**：线性表中的第一个数据元素结点。
##### 单链表操作
- **插入结点**:
- 在`P`结点后插入`S`结点:
```c
S->next = P->next;
P->next = S;
```
- 在`P`结点前插入`S`结点:
```c
while(P->next != Q) P = P->next;
S->next = P->next;
P->next = S;
```
- 在表首插入`S`结点:
```c
S->next = L;
L = S;
```
- 在表尾插入`S`结点:
```c
while(P->next != NULL) P = P->next;
P->next = S;
S->next = NULL;
```
#### 四、有序线性表的操作
- **插入操作**:
- 方法1: 找出插入位置，进行元素移动。
- 方法2: 参见指定教材P.229。
- **删除操作**:
- 删除自第`i`个元素开始的`k`个元素，需要注意边界条件和元素的有效性。
#### 五、高效删除算法
考虑一个以单链表存储的递增有序线性表，需要删除所有大于`mink`且小于`maxk`的元素。此操作需要遍历链表，找到满足条件的第一个结点的前驱结点和最后一个结点的后继结点，然后依次释放中间的结点。算法的时间复杂度为`O(n)`，其中`n`为链表中元素的个数。
