当前位置：首页 > ds >正文

C程序题案例分析

ds 2025/5/9 7:01:38

大纲要求

掌握C程序设计语言
掌握常用数据结构及其操作
掌握排序算法、查找算法
灵活应用算法设计策略

一、算法设计的基础知识

1. 指针

2. 常用数据结构

1）线性表

2）队列

3）栈

4）堆

5）数组

6）树

7）Huffman树

8）图

二、常用算法设计技术

1）迭代法

2）穷举搜索法

3）递推法

4）递归法

5）回溯法

6）贪心法

7）分治法

8）动态规划法

三、例题

一、算法设计的基础知识

1. 指针

本质与类型
- 本质：存储内存地址的变量
- 类型意义：
  - 决定指针运算的步长（如int*步长为4字节）
  - 指定操作的内存单元大小（如char*操作1字节）
数组名与指针的关系
- 数组名是常指针（首地址不可修改）
- 示例：
```
int arr[3] = {1, 2, 3};
int *p = arr;  // arr等价于&arr[0]
```
指针作为函数参数
- 值传递原则：
  - 修改指针指向的内容：直接传递指针（如void func(int *p)）
  - 修改指针本身：传递二级指针（如void alloc(char **p)）

#include <stdio.h>   
int main() {int array3[6] = {100,101,102,103,110,111};printf("%x\n", array3); // 输出数组首地址（十六进制）int *p = array3;        // 数组名作为指针while (p <= &array3[5]) { printf("%8d", *(p++)); // 指针遍历数组}return 0;   
}

数组名是指向首元素的常指针。
指针自增操作 *(p++) 按类型大小移动（如 int 移动4字节）。

2. 常用数据结构

1）线性表

概念

由相同数据类型的节点组成的有限序列，存在唯一首节点（无前驱）和尾节点（无后继）。
基本操作：初始化（Initiate）、插入（Insert）、删除（Delete）、查找（Locate）等。

存储结构对比

类型	优点	缺点
顺序存储	随机访问快（O(1)）	插入/删除需移动元素
链式存储	动态扩展灵活	访问需遍历（O(n)）

链式变种

单链表：节点含数据域 + 后继指针。
循环链表：尾节点指向头节点，形成环。
双向链表：节点含前驱 + 后继指针，支持双向遍历。

typedef struct Node {int data;struct Node *next;   
} Node;// 插入操作示例（未完整，需补充）   
void Insert(Node **head, int value) {Node *newNode = (Node*)malloc(sizeof(Node));newNode->data = value;newNode->next = *head;*head = newNode;
}

链式存储：单链表
链表的节点通过 malloc 动态分配内存。
插入操作需处理指针指向的修改。

2）队列

特性

先进先出（FIFO），队尾插入，队首删除。

实现方式

顺序队列：数组实现，需处理假溢出（循环队列）。
链队列：链表实现，无空间限制。
优先级队列：按优先级出队，常用堆实现。

// 链队列节点结构   
typedef struct QNode {int data;struct QNode *next;   
} QNode;// 入队操作（需维护队尾指针rear）   
void EnQueue(QNode **rear, int value) {QNode *newNode = (QNode*)malloc(sizeof(QNode));newNode->data = value;newNode->next = NULL;(*rear)->next = newNode;*rear = newNode;   
}

3）栈

特性

后进先出（LIFO），仅在栈顶（表尾）插入/删除。

实现方式

顺序栈：数组实现，需预设大小。
链栈：链表实现，无容量限制。

应用场景

函数调用栈、表达式求值、括号匹配。

// 链栈节点结构（文档中用于二叉树非递归遍历）   
typedef struct SNode {BiTree elem;  // 存储二叉树节点指针struct SNode *next;   
} SNode;// 压栈操作   
void Push(SNode **top, BiTree node) {SNode *newNode = (SNode*)malloc(sizeof(SNode));newNode->elem = node;newNode->next = *top;*top = newNode;    
}

4）堆

定义

完全二叉树，满足堆性质：
- 大顶堆：父节点 ≥ 子节点
- 小顶堆：父节点 ≤ 子节点

典型应用

堆排序（时间复杂度 O(nlogn)）
优先级队列

// 调整堆的代码未完整给出 
void HeapAdjust(int a[], int s, int m) {/* 将序列a[s..m]调整为一个大顶堆 */// 具体实现 
}// 初始化堆的步骤：   
for (int i = n/2; i > 0; i--) HeapAdjust(a, i, n);

5）数组

类型

静态数组：编译时分配固定大小（如 int a[10]）。
动态数组：运行时分配（如 malloc）。

特殊矩阵存储

对称矩阵：仅存储上/下三角。
稀疏矩阵：三元组（行、列、值）压缩存储。

// 动态数组分配（文档中指针部分示例）   
void GetMemory(char **p) {*p = (char*)malloc(100 * sizeof(char));   
}int main() {char *arr = NULL;GetMemory(&arr);  // 动态分配数组空间strcpy(arr, "Dynamic Array");free(arr);    
}

6）树

二叉树性质

第 i 层最多有 2^(i-1) 个节点。
叶子节点数 n0 = n2 + 1（n2 为度为2的节点数）。

遍历方式

递归实现：代码简洁，可能栈溢出。
非递归实现：借助栈（中序）或队列（层序）。

特殊二叉树

类型	特点
满二叉树	每一层节点数达到最大值。
完全二叉树	除最后一层外节点数满，最后一层左对齐。
AVL树	左右子树高度差 ≤ 1，平衡二叉查找树。
二叉查找树	左子树值 < 根 < 右子树值。

// 二叉树节点结构    
typedef struct BiTNode {int data;struct BiTNode *lchild, *rchild;    
} BiTNode, *BiTree;// 中序遍历递归实现    
void InOrder(BiTree root) {if (root) {InOrder(root->lchild);printf("%d ", root->data);InOrder(root->rchild);}
}