HeyHey说在前头
本篇将会结合个人理解，对一些我觉得值得讲的代码进行部分注释
基于严蔚敏版《数据结构(C语言版)》
后面想到什么了再补充
——XPIPI
第二章 线性表
算法2.4 顺序线性表的插入
书中算法
Status ListInsert_Sq(SqList &L,int i,ElemType e)
// L 线性表 i在第i个位置插入 e需要插入的元素
// 在顺序线性表L中第i个位置之前插入新的元素e
// i的合法值为 1 <= i <= ListLength.Sq(L) + 1
// ①验证合法性
if(i < 1 || i > L.length + 1) {
return ERROR;
}
// ②存储空间满了 需要增加分配的空间
if(L.length >= L.listsize){
// 注意：类似malloc，realloc在调用头文件stdlib.h后返回值为 (void *) 这里使用 (ElemType *) 强制转化为我们需要的数据类型的指针
newbase = (ElemType *)realloc(L.elem,L.listsize+LISTINCREMENT) * sizeof(ElemType);
// 此处的LISTINCREMENT为之前宏定义过的
if(!newbase){
exit(OVERFLOW);
/*
OVERFLOW为math.h的一个宏定义，值为3 也即exit(3); 表示运算溢出,存储分配失败
当然，你也可以自己宏定义OVERFLOW的值
*/
// 存储分配成功后进行新地址的赋值操作
L.elem = newbase;
L.listsize += LISTINCREMENT;
}
// ③找插入位置为q
q = &(L.elem[i-1]);
// 将q之后的元素全部右移
for(p = &(L.elem[L.length-1]);p >= q;--p){
*(p+1) = *p;
}
// 在q这个位置插入e，并增加表长
*q = e;
++L.length;
return OK;
}实现代码
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
//顺序表的存储结构定义
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
Status ListInsert_Sq(SqList &L,int pos,ElemType e){
if(pos < 1 || pos > L.length + 1) return ERROR;
if(L.length >= L.listsize){
int *newbase = (ElemType*)realloc(L.elem,(L.listsize + LISTINCREMENT) * sizeof(ElemType));
if(!newbase) return OVERFLOW;
L.elem = newbase;
L.listsize += LISTINCREMENT
}
for(int i = L.length;i >= pos - 1;--1){
L.elem[i + 1] = L.elem[i];
}
L.elem[pos-1] = e;
L.length++;
return OK;
}算法2.5 顺序线性表的删除
书中算法
Status ListDelete_Sq(SqList &L,int i,ElemType &e){
// L 线性表 i在第i个位置删除 e被删除的元素（此处为引用传递)
// 在顺序线性表L中删除第i个元素，并用e返回值
// i的合法值为 1 <= i <= ListLength.Sq(L)
// ①验证合法性
if(i < 1 || i > L.length) {
return ERROR;
}
// 找删除位置为p
p = &(L.elem[i-1]);
// 将p这个位置的值赋给e *p解引用
e = *p;
// 表尾元素标记 左边移动一个
q = L.elem+L.length-1;
// 将p之后的元素全部左移
for(++p;p <= q;++p){
*(p-1) = *p;
}
// 减少表长
--L.length;
return OK;
}实现代码
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
//顺序表的存储结构定义
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
Status ListDelete_Sq(SqList &L,int pos,ElemType &e){
if(pos < 1 || pos > L.length) return ERROR;
e = L.elem[pos-1];
for(int i = pos - 1;i < L.length - 1;++i){
// 不要用L.elem[i-1] = L.elem[i] 因为是从i开始的，如果i=pos-1=0的情况下会出错
L.elem[i] = L.elem[i+1];
}
L.length--;
return OK;
}算法2.7 顺序表的合并
书中算法
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
// 原顺序线性表La、Lb为非递减排列顺序表 Lc为结果顺序表
// 合并后Lc也为非递减排列顺序表（即升序）
// 用pa和pb表示La和Lb的基址
pa = La.elem;pb = Lb.elem;
// 合并后Lc的大小
Lc.listsize = Lc.length = La.length + Lb.length;
// 给Lc分配内存 并用pc表示Lc的基址
pc = Lc.elem = (ElemType *)malloc(Lc.lisesize * sizeof(ElemType));
// 分配内存溢出情况
if(!Lc.elem){ // 这里用!pc也是一样的
exit(OVERFLOW);
}
// 用pa_last和pb_last表示La和Lb的最后一个元素
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
// 比较当前pa和pb大小，并插入到Lc中
while(pa <= pa_last && pb <= pb_last){ // La和Lb都还有元素剩余
if(*pa <= *pb){
*pc++ = *pa++;
/* 看不懂？其实这一句等价于：
*pc=*pa;
pc++;
pa++;
也就是赋值，并分别移动指针
下面同理
*/
}
else *pc++ = *pb++;
}
// La和Lb有一个元素插入完了变成空表了 将另外一个还有元素的表直接全部插入到Lc后面
while(pa <= pa_last) *pc++ = *pa++;
while(pb <= pb_last) *pc++ = *pb++;
}实现代码
//函数状态码定义
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
//顺序表的存储结构定义
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
// 冒泡排序 还记得怎么写吗
Status ListSort_Sq(SqList &L){
for(int i = 0;i < L.length - 1;++i){
for(int j = 0;j < L.length - 1 - i;++j){
if(L.elem[j] > L.elem[j+1]){
swap(L.elem[j],L.elem[j+1]);
}
}
}
return OK;
}
// 本体在这儿
// 默认我们这里的La Lb已经排序好了（升序）
// !!这里是包含去重操作的 代码自己看
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
// i对应La j对应Lb k对应Lc
int i = 0, j = 0, k = 0;
Lc.elem = (ElemType*)malloc((La.length+Lb.length)*sizeof(ElemType));
if(!Lc.elem) return OVERFLOW;
while(i < La.length && j < Lc.length){
if(La.elem[i] < Lb.elem[j]){//当La的i号元素比Lb的j号元素小
if(k == 0 || Lc.elem[k-1] != La.elem[i]) {
// 条件：如果 L3 是空表 (k == 0) 或 L3 的最后一个元素不等于 L1.elem[i]
// 满足这个条件才加入这个元素 达成去重效果√
Lc.elem[k++] = La.elem[i];
}
// 满不满足去重条件La都要移动到下一个元素 i++
i++;
}else if (La.elem[i] > Lb.elem[j]) {//以下同理
if (k == 0 || Lc.elem[k - 1] != Lb.elem[j]){
Lc.elem[k++] = Lb.elem[j];
}
j++;
}else{//当La的i号元素比Lb的j号元素相等
if (k == 0 || Lc.elem[k - 1] != La.elem[i]){
// 满足条件后，随意添加其中一个
Lc.elem[k++] = La.elem[i];
}
i++;j++;
}
}
// La或Lb还没空
while(i < La.length){
if(k == 0 || Lc.elem[k-1] != La.elem[i]) {
Lc.elem[k++] = La.elem[i];
}
i++;
}
while(j < Lb.length){
if(k == 0 || Lc.elem[k-1] != Lb.elem[i]) {
Lc.elem[k++] = Lb.elem[i];
}
j++;
}
return OK;
/*
最终效果：
合并两个有序线性表；
去除重复元素；
保持结果有序
*/
}算法2.9 单链表的插入
书中算法 带头节点 i前插入
Status ListInsert_L(LinkList &L,int i,ElemType e){
// 在带头节点的单链线性表L中第i个位置之前插入元素e
// 将L赋给p 此时p代表头指针
p = L;
// j用于计数 从0开始
j = 0;
while(p && j < i-1){//p不为NULL且j比i-1小
p = p->next;
++j;
// 不断右移，直到到i-1结点结束
}
if(!p || j > i - 1){
// 两种情况：1.i比表长+1还大 p遍历到表尾最后指向NULL 2.i小于1 j>i-1 将一直为true
return ERROR;
}
// 生成新节点s
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
// 将s插入到L中 注意顺序不可变化
s->next = p->next;
p->next = s;
}实现代码
#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode ,*LinkList;
Status ListInsert_L(LinkList &L,int i,ElemType e){
LNode *p = L;
// 也可以是 LinkList p = L
int j = 0;
while(p && j < i-1){
p = p->next;
++j;
}
if(!p || j > i - 1) return ERROR;
LNode *s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}算法2.10 单链表的删除
书中算法
Status ListDelete_L(LinkList &L,int i,ElemType &e){
// 在带头节点单链线性表L中，删除第i个元素，并由e返回对应值
p = L;j = 0; // p代表头指针 j为计数器
while(p->next && j < i-1){ //p->next不为NULL且j比i-1小
p = p->next;
++j;
//找到第i个结点后，这个时候p是第i个结点的前驱
}
if(!(p->next) || j > i-1){
// 两种情况：1.对应i元素不存在 p遍历到表尾最后指向NULL 2.i小于1 j>i-1 将一直为true
return ERROR;
}
// 指针q指向需要删除的元素 下面两行顺序不可换
q = p->next;
// 被删除元素的前驱的后驱更改为被删除元素的后驱
p->next = q->next;
// 提取被删除的值
e = q->data;
// 释放结点内存
free(q);
return OK;
}实现代码
#define ERROR 0
#define OK 1
typedef int Status;
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LNode ,*LinkList;
Status ListDelete_L(LinkList &L,int i,ElemType &e){
LNode *p = L;
int j = 0;
while(p->next && j < i-1){
p = p->next;
++j;
}
if(!(p->next) || j > i-1) return ERROR;
LNode *q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}算法2.12 单链表的归并
书中算法
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
// La Lb 元素非递减排列（即递增）
// 归并得到的新Lc也为非递减排列 链表操作均为引用
// pa和pb用来表示La和Lb的首元结点
pa = La->next;pb = Lb->next;
// 用La的头结点作为Lc的头结点 当然你用Lb的也行:)
Lc = pc = La;
while(pa && pb){// pa和pb都没指向空
if(pa->data <= pb->data){// pa指向元素值小于或等于pb指向元素值
// 将pc指向结点的后驱改为pa指向结点
pc->next = pa;
// 将pc指向结点改为pa
pc = pa;
// 移动pa指针到下一个元素
pa = pa->next;
// 本质上可以理解成插入操作
}else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
// 类似于顺序表 可能存在剩余元素 因为链表的性质可以利用三目运算符
// 这里的pa如果是空的话是NULL 运行：pc->next = pb 反之运行：pc->next = pa
pc->next = pa?pa:pb;
free(Lb); //释放Lb头结点 如果前面用Lb当头结点了这里就释放La头结点
}
}实现代码
typedef int ElemType;
typedef struct LNode{
ElemType data;
struct LNode *next;//定义next为指向结构体LNode的指针
}LNode,*LinkList;
//LinkList也为一个指向结构体的指针 相当于 using LinkList = *LNode;
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
LinkList pa,pa,pc;
pa = La->next;
pb = Lb->next;
Lc = pc = La;
while(pa && pb){
if(pa->data <= pb->data){
pc->next = pa;
pc = pa;
pa = pa->next;
}else{
pc->next = pb;
pc = pb;
pb = pb->next;
}
}
pc->next = pa?pa:pb;
free(Lb);
}第三章 栈和队列
栈的入栈与出栈
// 顺序栈的入栈
Status Push(SqStack &S,SElemType e){
// 元素e入栈 先检查栈是否已满
if(S.top - S.base >= S.stacksize){ //栈满条件
// 若栈满，则重新分配存储空间
S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
// 当然也要考虑溢出导致分配失败情况
if(!S.base) exit(OVERFLOW);
// 移动栈顶指针到新的地址
// 因为重新分配的S.base地址发生了改变 所以这个时候S.top也要跟着改变
// 此时还没入栈 所以top指针就是指向扩充前的最大的那个元素
S.top = S.base + S.stacksize;
// 扩充后，栈的容量也要增加
S.stacksize += STACKINCREMENT;
}
// 如果栈没满，或者经过扩充后 在栈顶添加元素e
// 由于top指向的是栈顶的下一个位置 所以先将e压入栈顶 top指针再+1
*S.top++ = e;
// 等效为：*S.top = e; S.top++;
return OK;
}
// 顺序栈的出栈
Status Pop(SqStack &S,SElemType &e){
// 出栈一个元素，用e返回这个值 当然要先检查栈是否为空栈
if(S.top == S.base){ // 判断空栈条件
return ERROR;
}
// 同理，我们先给e赋值，然后top指针再-1
// 栈容量不变
e = *--S.top;
// 等效为： e = *S.top; S.top--;
return OK;
}代码实现
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
// define语句加分号是允许的（编译通过）但可能会出现问题 所以不推荐
typedef int SElemType;
typedef int Status;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status Push(SqStack &S,SElemType e){
if((S.top - S.base) >= S.stacksize){
S.base = (SElemType*)realloc(S.base,(S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top = e;
S.top++;
return OK;
}
Status Pop(SqStack &S,SElemType &e){
if(S.top == S.base) return ERROR;
e = *S.top;
S.top--;
return OK;
}算法3.1 栈的应用：进制转换
书上代码
void conversion(){
// 对于任意一个非负十进制整数，打印输出与其等值的八进制数
// 原理：取商留余法
InitStack(S);
// 输入一个非负十进制整数N
scanf("%d",N);
// 入栈，得到八进制数序列
while(N){ // N没被除成0前一直运行
// 把当前的N mod 8入栈
Push(S,N % 8);
// 每次入栈一个数 N = N/8
N /= 8;
}
// 出栈并打印结果
while(!(StackEmpty(S)){
Pop(S,e);
printf("%d",e);
}
}代码实现
一个十进制 -> X进制的示例：
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
typedef int SElemType;
typedef int Status;
typedef struct{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S)
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackEmpty(SqStack &S);
void conversion(){
// 输入需要转换为几进制
cin >> X;
// 输入需要转换的数字
cin >> num;
InitStack(S);
char ch[16] = {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
while(num){
Push(S,num % X);
num /= X;
}
int e;
while(!StackEmpty(S)){
Pop(S,e);
cout << e << " ";
}
cout << endl;
}队列的入队和出队
// 一种链队列
Status EnQueue(LinkQueue &Q,QElemType e){
// 将元素e插入到队尾 入队
// 动态申请空间
p = (QueuePtr)malloc(sizeof(QNode));
// 存储分配失败
if(!p) exit(OVERFLOW);
// p赋值并next指向NULL（作为新的队尾元素)
p->data = e;
p->next = NULL;
// p入队
Q.rear->next = p;
// 移动队尾指针
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q,QElemType &e){
// 若队列不为空，将Q的队头元素出队，并用e返回其值
// 首先判断是否为空
// 判断队列是否为空有三种方法，这里使用front=rear来判断，还有使用标记位flag和计数器count的方法
if(Q.front == Q.rear) return ERROR;
// 因为这里是链队列，指针p为头指针指向的下一个元素，也即首元元素(此时的队头)
p = Q.front->next;
// 此时p指向为即将出队的元素
e = p->data;
// 改变队列头指针指向的元素
// 也可以写成 Q.front->next = Q.front->next->next 这两种等效
Q.front->next = p->next;
// 特殊情况：如果此时队尾元素也是即将出队的元素p 就说明这个队列只有一个元素 出队后将队列置空
if(Q.rear == p) Q.rear = Q.front;
// 出队操作后释放p
free(p);
return OK;
}代码实现
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int QElemType;
typedef int Status;
typedef struct QNode{
QElemType data;
struct QNode *next;
}QNode,*QueuePtr;
typedef struct{
QueuePtr front,rear;
}LinkQueue;
Status EnQueue(LinkQueue &Q, QElemType e) {
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p)
exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q.rear->next = p;
Q.rear = p;
return OK;
}
Status DeQueue(LinkQueue &Q, QElemType &e) {
if (Q.rear == Q.front)
return ERROR;
QueuePtr p = Q.front->next;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
Q.rear = Q.front;
free(p);
return OK;
}第四章 串
串的模式匹配算法 算法4.5 4.6 4.7
我们都知道子串的定位操作通常称作串的模式匹配，一般来说常用的有BF算法(也称蛮力法）和KMP算法两种实现方式，其中
BF算法：时间复杂度O(n*m) KMP算法：时间复杂度(n+m)
BF算法伪代码
int Index(SString S,SString T,int pos){
// 返回子串T在主串S中第pos个字符之后的位置，若不存在，则函数值返回0
// 其中要求：T非空，1<=pos<=StrLength(S)
// 从pos位置开始查找
// 主串从pos开始 子串从头开始
i = pos; j = 1;
// 从起始位置逐个匹配子串与主串的元素
while(i <= S[0] && j <= T[0]){ // 注意，串的0下标位置存放串的长度，也即StrLength(S)
// 逐个字符进行匹配
if(S[i] == T[j]){
// 若字符匹配成功，主串子串均往后走一个元素
++i;
++j;
}else{
// 若字符匹配不成功，主串回溯到i-j+2位置，子串回到串头重新比较（实际效果：子串整体向下一位移动）
i = i - j + 2;
j = 1;
}
// 如果找到了这么个子串（也就是j成功走到了子串的最后一个元素的后一位），那就返回这个子串在主串中的起始位置
if(j > T[0]) return i - T[0];
// 没找到就返回0
else return 0;
}
}代码实现
#define MAXSTRLEN 255
// 定长顺序串存储表示
typedef char SString[MAXSTRLEN + 1];
int Index(SString S, SString T, int pos) {
int n = StrLength(S);
int m = StrLength(T);
// 边界检查
if (pos < 0 || pos >= n || m == 0 || m > n) {
return 0;
}
int i = pos;
int j = 0;
while (i < n && j < m) {
if (S[i] == T[j]) {
++i;
++j;
} else {
i = i - j + 1; // 从下一位置重新匹配
j = 0;
}
}
return (j == m) ? (i - m) : 0;
}KMP算法伪代码
int Index_KMP(SString S,SString T,int pos){
// 利用模式串T的next函数求T在主串S中第pos个字符之后位置的KMP算法
// 其中要求：T非空，1<=pos<=StrLength(S)
i = pos; j = 1;
while(i <= S[0] && j <= T[0]){
if(j == 0 || S[i] == T[j]){ // 与BF算法不同，在KMP算法中模式串回到开头(j==0)时，只能跳过当前主串字符，从主串下一个字符开始匹配
++i; ++j;
}else{
// 回退到部分匹配的位置
j = next[j];
}
}
if(j > T[0]) return i-T[0];
else return 0;
}emm....看上去跟BF算法基本差距主要在于next数组，那么这个数组怎么求得呢？
next数组与前后缀有关！具体定义可自行查阅资料。
void get_next(SString T,int next[]){
// 求模式串T的next函数值并存入
i = 1;
// 人为定义第一个是0 ，因为模式串T的第一个字符是不存在前后缀的
// 其实第二位也一定为1，但这里不手动定义
next[1] = 0;
// j 表示当前前缀长度（指向当前字符之前的最长相等前后缀的下一个位置）
j = 0;
while(i < T[0]){
if(j == 0 || T[i] == T[j]){
// 如果：
// 1. j == 0：表示当前字符没有可以匹配的前缀
// 2. T[i] == T[j]：表示当前字符与最长前缀的下一个字符匹配
++i;++j;
// 将当前字符对应的 next 值设为 j（最长相等前后缀长度）
next[i] = j;
}else {
// 如果当前字符与最长前缀的下一个字符不匹配
j = next[j]; // 回退 j，尝试更短的前缀匹配
}
}
}完整代码实现
#define MAXSTRLEN 255
typedef char SString[MAXSTRLEN + 1];
void get_next(SString T, int next[]) {
int i = 1, j = 0;
next[1] = 0;
while (i < T[0]) {
if (j == 0 || T[i] == T[j]) {
++i;
++j;
next[i] = j;
} else {
j = next[j];
}
}
}
int Index_KMP(SString S, SString T, int pos) {
int next[MAXSTRLEN + 1];
get_next(T, next);
int i = pos, j = 1;
while (i <= S[0] && j <= T[0]) {
if (j == 0 || S[i] == T[j]) {
++i;
++j;
} else {
j = next[j];
}
}
return (j > T[0]) ? (i - T[0]) : 0;
}第五章 数组与广义表
算法5.1 稀疏矩阵的普通转置操作 O(nu * tu)
Status TransposeSMartix(TSMatrix M, TSMatrix &T){
// 稀疏矩阵用三元组存储 求稀疏矩阵M的转置矩阵T
// T的行数 = M的列数
T.mu = M.nu;
// T的列数 = M的行数
T.nu = M.mu;
// T的非零元个数 = M的非零元个数
T.tu = M.tu;
if(T.tu){ // 避免对空矩阵进行操作
// 初始化指针q，指向T矩阵存储数组的起始位置，用来存储转置后的元素
q = 1;
// 外层循环遍历矩阵M的列
for(col = 1;col <= M.nu;++col)
// 内层循环遍历矩阵M的非零元素
for(p = 1;p <= M.tu;++p){
// 如果当前非零元素M.data[p]的列索引（M.data[p].j）等于当前列索引col
if(M.data[p].j == col){
// 将原矩阵M的行索引（M.data[p].i）赋值给转置矩阵T的数据项的列索引
T.data[q].i = M.data[p].j;
// 将原矩阵M的列索引（M.data[p].j）赋值给转置矩阵T的数据项的行索引
T.data[q].j = M.data[p].i;
// 将原矩阵M的非零元素值（M.data[p].e）赋值给转置矩阵T的数据项
T.data[q].e = M.data[p].e;
// 移动指针q，指向下一个位置
++q;
}
}
}
return OK;
}算法5.2 稀疏矩阵的快速转置操作 O(nu+tu)
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T){
// 快速将稀疏矩阵M转置为T
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if (T.tu) {
// 步骤 1：初始化并计算每列的非零元素个数
for (col = 1; col <= M.nu; ++col) {
num[col] = 0;
}
for (t = 1; t <= M.tu; ++t) {
// 对于每一个非零元素 M.data[t]，增加其所在列 (M.data[t].j) 的计数
++num[M.data[t].j];
}
// 步骤 2：计算每一列的第一个非零元素在 T 中的起始位置
cpot[1] = 1;
// cpot 数组用于存储转置后的矩阵 T 中，按列顺序每列第一个非零元素的位置。初始化 cpot[1] 为 1，表示第一列的第一个非零元素在 T 中的位置
for (col = 2; col <= M.nu; ++col) {
// 通过累加每列的非零元素个数，计算出第 col 列第一个非零元素在转置矩阵 T 中的位置
cpot[col] = cpot[col - 1] + num[col - 1];
}
// 步骤 3：转置
for (p = 1; p <= M.tu; ++p) {
// 获取当前非零元素所在列的列索引
col = M.data[p].j;
// 获取当前列 col 在转置矩阵 T 中的当前位置，保存在 q 中
q = cpot[col];
// 将 M 中当前非零元素的行列交换，存储到 T 中
T.data[q].i = M.data[p].j; // 将 M 中元素的列索引 (M.data[p].j) 存储为 T 中的行索引
T.data[q].j = M.data[p].i; // 将 M 中元素的行索引 (M.data[p].i) 存储为 T 中的列索引
T.data[q].e = M.data[p].e; // 将 M 中元素的值 (M.data[p].e) 存储到 T 中
// 将 cpot[col] 递增，表示该列的下一个非零元素在 T 中的位置
++cpot[col];
} // for
} // if
}代码实现
#define OK 1
#define MAXSIZE 255
typedef int ElemType;
typedef int Status;
// 用三元组存储稀疏矩阵
typedef struct{
int i, j;
ElemType e;
}Triple;
typedef struct{
Triple data[MAXSIZE];
int mu, nu, tu; //矩阵行数，列数和非0元个数
}TSMatrix;
//稀疏矩阵转置 （适用于 tu << mu × nu 的情况）
Status TransposeSMatrix(TSMatrix M,TSMatrix &T){
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if(T.tu){
int q = 1;
for(int col = 1; col <= M.nu; ++col){
for(int p = 1; p <= M.tu; ++p){
if(M.data[p].j == col){
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
q++;
}
}
}
}
return OK;
}
//稀疏矩阵的快速转置算法
Status FastTransposeSMatrix(TSMatrix M, TSMatrix &T){
int cpot[MAXSIZE + 1], num[MAXSIZE + 1]; //辅助数组
T.mu = M.nu; T.nu = M.mu; T.tu = M.tu;
if(T.tu){
for (col = 1; col <= M.nu; ++col) {
num[col] = 0;
}
for(int k = 1; k <= M.tu; k++) {
num[M.data[k].j]++;
}
cpot[1] = 1;
for(int col = 2; col <= M.mu; col++){
cpot[col] = cpot[col - 1] + num[col - 1];
}
for(int p = 1; p <= M.tu; p++){
int col = M.data[p].j;
int q = cpot[col];
T.data[q].i = M.data[p].j;
T.data[q].j = M.data[p].i;
T.data[q].e = M.data[p].e;
cpot[col]++;
}
}
return OK;
}第六章 树和二叉树
算法6.3 中序遍历二叉树的非递归（迭代）算法②
有两种方法 这里介绍书中的第二种
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e)){
// 采用二叉链表存储结构，Visit是对数据元素操作的应用函数
// 中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit
InitStack(S);
// 将指针 p 初始化为树的根节点 T，p 用于遍历树
p = T;
// while 循环用于遍历树，直到栈为空并且 p 指针为空为止
while (p || !StackEmpty(S)) {
if (p) { // 如果 p 不为空，说明当前节点存在
// 将当前节点 p 压入栈 S，保存节点，以便后续返回到该节点
Push(S, p);
// 移动到当前节点的左子树，继续向下遍历左子树
p = p->lchild;
} else { // 如果 p 为空，说明当前节点没有左子树，或者已经遍历完左子树
// 弹出栈顶元素，将栈顶元素赋值给 p，p 指向栈顶保存的节点
Pop(S, p);
if (!Visit(p->data)){
return ERROR;
}
// 移动到当前节点的右子树，准备遍历右子树
p = p->rchild;
} // else
} // while
return OK;
}算法6.4 先序序列创建二叉树（递归）
Status CreateBiTree(BiTree &T){
// 按先序次序输入二叉树中结点的值（一个字符） 空格字符代表空树
// 构造二叉链表表示的二叉树T
scanf(&ch);
// 如果是空字符，表示没有树的根节点，因此将树 T 设置为 NULL（空树）
if(ch == '') T = NULL;
else{
// 动态分配内存给新节点 T
if(!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
// 递归创建左右子树
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}代码实现
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
Status InOrderTraverse(BiTree T){
SqStack S;
InitStack(&S);
BiTree p = T;
while(p || !StackEmpty(&S)){
if(p != NULL){
Push(&S,p);
p = p->lchild;
}else{
Pop(&S,p);
printf("%d ",p->data);
p = p->rchild;
}
}
}
Status CreateBiTree(BiTree &T)
{
char ch=getchar();
if(ch=='.') {
T = NULL;
} else{
T = (BiTree)malloc(sizeof(BiTNode));
if(!T) exit(OVERFLOW);
T->data = ch;
CreateBiTree(&((*T)->lchild));
CreateBiTree(&((*T)->rchild));
}
return OK;
}第七章 图
算法7.4 7.5 深度优先搜索的存储结构和遍历
// 辅助数组，用来记录顶点是否已访问
Boolean visited[MAX];
// 用来访问函数指针
// VisitFunc是一个指向函数的指针 （int v)是这个函数的参数
// 因此这里实际上创建的是全局变量 VisitFunc
Status (*VisitFunc)(int v);
void DFSTraverse(Graph G, Status (*Visit)(int v)) {
// 对图G进行深度优先遍历
// 使用全局变量，使DFS函数不需要设置函数指针参数
VisitFunc = Visit;
// 对整个辅助数组进行初始化为未访问
for (v = 0; v < G.vexnum; ++v) {
visited[v] = FALSE;
}
// 对每一个顶点进行深度优先遍历
for (v = 0; v < G.vexnum; ++v) {
if (!visited[v]) {
// 对未访问的顶点进行DFS操作
DFS(G, v);
}
}
}
void DFS(Graph G, int v) {
// 从顶点v开始深度优先遍历
visited[v] = TRUE; // 标记为已访问
VisitFunc(v); // 执行访问操作
for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex(G, v, w)) {
if (!visited[w]) {
// 递归访问邻接点
DFS(G, w);
}
}
}算法实现（邻接表存储的图）
#define MAX_VERTEX_NUM 20
typedef VertexType int;
typedef InfoType int;
// 顶点访问状态
enum VisitIf { unvisited, visited };
// 边表结点
typedef struct EBox {
VisitIf mark; // 访问标记
int ivex, jvex; // 关联的顶点
struct EBox *ilink, *jlink; // 链接到下一个边的指针
InfoType* info; // 边的附加信息指针
} EBox;
// 顶点表结点
typedef struct VexBox {
VertexType data; // 顶点数据
EBox* firstedge; // 指向第一条关联边的指针
} VexBox;
// 图的定义（邻接多重表表示）
typedef struct {
VexBox adjmulist[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, edgenum; // 顶点数和边数
} AMLGraph;
// 辅助数组，用来记录顶点是否已访问
bool visited[MAX_VERTEX_NUM];
// 用来访问顶点的函数指针
void (*VisitFunc)(int);
// 深度优先遍历
void DFSTraverse(AMLGraph& G, void (*Visit)(int)) {
VisitFunc = Visit;
for (int v = 0; v < G.vexnum; ++v) {
visited[v] = false;
}
for (int v = 0; v < G.vexnum; ++v) {
if (!visited[v]) {
DFS(G, v);
}
}
}
// 从顶点v开始深度优先搜索
void DFS(AMLGraph& G, int v) {
visited[v] = true;
VisitFunc(v);
EBox* p = G->adjmulist[v].firstedge; // 获取顶点v的第一条边
while (p) {
w =
int w = (p->ivex == v) ? p->jvex : p->ivex; // 找到顶点v的邻接点
if (!visited[w]) {
DFS(G, w); // 递归访问未访问的邻接点
}
p = (p->ivex == v) ? p->ilink : p->jlink; // 移动到下一条边
}
}算法7.6 广度优先遍历
void BFSTraverse(Graph G,Status (*Visit)(int v)){
// 广度优先非递归遍历图G 辅助队列G 访问标志数组visited[]
for(v = 0;v < G.vexnum;++v){
visited[v] = FALSE;
}
// 初始化访问标志数组
// 初始化辅助队列
InitQueue(Q);
for(v = 0;v < G.vexnum;++v){
// 遍历访问未访问的结点
if(!visited[v]){
// 更改访问标志数组并访问顶点v
visited[v] = TRUE;
Visit(v);
// 将顶点v入队
EnQueue(Q,v);
// 如果队列不空
while(!QueueEmpty(Q)){
// 队头出列并赋值给u
DeQueue(Q,u);
for(w = FirstAdjVex(G,u); w >= 0; w = NextAdjVex(G,u,x)){
// w 为 v未访问的邻接顶点
if(!Visited[w]){
Visited[w] = TRUE;
Visit(w);
EnQueue(Q,w);
} // if
} // for
} // while
} // if
} // for
} // BFSTraverse算法实现 （邻接矩阵存储的图）
#define INFINITY INT_MAX
#define MAX_VERTEX_NUM 20
typedef VRType int;
typedef InfoType int;
typedef VertexType int;
typedef struct ArcCell{
VRType adj; // 邻接关系（1 表示有边，0 表示无边）
InfoType* info;
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct{
VertexType vexs[MAX_VERTEX_NUM];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
bool visited[MAX_VERTEX_NUM];
void BFStraverse(MGraph G){
for (int v = 0; v < G.vexnum; v++) visited[v] = False;
SqQueue Q;
InitQueue(&Q);
for (int v = 0; v < G.vexnum; v++) {
if (!visited[v]){
visited[v] = True; Visit(v);
EnQueue(&Q, v);
while (QueueEmpty(Q)){
int u;
DeQueue(&Q, &u);
for (int w = 0; w < G.numVertexes; w++){
if (G.arc[u][w] == 1 && !visited[w]){
visited[w] = True;
Visit[w];
EnQueue(&Q, w);
}
}
}
}
}
}第九章 查找
算法9.2 折半查找（二分查找）
// very Easy
int Search_Bin (SSTable ST,KeyType key){
// 在有序表ST中查找关键字为key的元素
// 找到返回对应位置，否则return 0
low = 1 ; // 左
high = ST.length; // 右
while(low <= high){ // 左右相遇终止
mid = (low + high) / 2; // 相当于逻辑右移一位（速度快点）
if (EQ(key,St.elem[mid].key)) return mid; // 找到了
else if (LT(key,St.elem[mid].key)) high = mid - 1; // key比当前的要小，移动high
else low = mid + 1; // key比当前的要大，移动low
}
return 0;
}算法实现 C
typedef ElemType int;
typedef struct{
ElemType* elem;
int length;
}SSTable;
int Search_Bin (SSTable ST,int key){
int left = 1;
int right = ST.length - 1;
while(low <= high && mid = (left+right) >> 1){
if(St.elem[mid] == key) return mid;
else if (St.elem[mid] > key) right = mid - 1;
else left = mid + 1;
}
return 0;
}
