考前抱佛脚┭┮﹏┭┮
记住这里大量用了c++的引用。。好方便，但是答题的时候记得换成 *和全局变量
一个算法应该具有以下特性：
- 有穷性
- 确定性 不存在二义性
- 可行性
- 有输入
- 有输出
1<n<log2n<n<nlog2n<n2<n3 (多项式)|| <2n<n!(指数)
1.线性表
顺序存储
SqList 是线性表
/*基本运算：
InitList(&L);
DestoryList(&L);
ListEmpty(L);
ListLength(L);
DispList(L);
GetElem(L,i,&e);
LocateElem(L,e);
ListInsert(&L,i,e);
ListDelete(&L,i,&e);
*/
/*线性表的顺序存储
i--; //转化为物理序号
if(i<1 || i>L->length+1) //插入的时候是允许插入第 n+1 位置的，所以还要额外+1
最后不要忘了改一下k的符号
*/
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
} SqList; //顺序表类型
//需要改变的就传入引用，不需要改变的就直接传入指针就好了。
void CreateList(SqList *&L, ElemType a[], int n)
{
int i = 0, k = 0; //用来统计数量，i用来当索引，但是为什么不直接用i呢？
L = (SqList *)malloc(sizeof(SqList));
while (i < n)
{
L->data[i] = a[i];
k++;
i++;
}
L->length = k;
}
void InitList(SqList *&L)
{
L = (SqList *)malloc(sizeof(SqList));
L->length = 0;
}
void DestroyList(SqList *&L)
{
free(L);
}
bool ListEmpty(SqList *L)
{
return L->length == 0;
}
int ListLength(SqList *L)
{
return L->length;
}
void DispList(SqList *L)
{
for (int i = 0; i < L->length; i++)
{
printf("%d", L->data[i]);
printf("\n");
}
}
bool GetElem(SqList *L, int i, ElemType &e)
{
if (i < 1 || i > L->length)
return false;
e = L->data[i - 1];
return true;
}
int LocateElem(SqList *L, ElemType e)
{
int i = 0;
while (i < L->length && L->data[i] != e)
i++;
if (i >= L->length)
return 0;
else
return i + 1; //记住逻辑序号和物理序号差了一个1嗷
}
bool ListInsert(SqList *&L, int i, ElemType e)
{
int j = L->length;
if (i < 1 || i > L->length + 1) //插入的时候是允许插入最后一个位置的，所以还要额外+1
return false;
i--; //转化为物理序号
for (; j > i; j--)
L->data[j] = L->data[j - 1];
L->data[i] = e;
L->length++;
}
bool ListDelete(SqList *&L, int i, ElemType e)
{
if (i < 1 || i > L->length)
return false;
i--; //转换成物理非常重要！
int j = L->length;
while (j > i)
{
L->data[j - 1] = L->data[j];
}
L->length--;
}
//****************************************************************************************************
//删除L中所有值等于 x 的元素，双指针扫描
void delnode1(SqList *&L, ElemType x)
{
int k = 0, i = 0;
for (; i < L->length; i++)
{
if (L->data[i] != x)
{
L->data[k] == L->data[i];
k++;
}
}
L->length = k;
}
//用k记录个数
void delnode2(SqList *&L, ElemType x)
{
int k = 0, i = 0;
for (i = 0; i < L->length; i++)
{
if (L->data[i] == x)
k++;
else
L->data[i - k] = L->data[k];
}
L->length -= k;
}
//这一片巧妙利用“缺位，补位”的技巧，节省了许多空间和时间，直接对换会消耗一个额外内存，不如缺位补位
//感觉不够通用,不过现在懒得改了，很多二分的其实都是pattition，跟python提供的key函数参数一样
void partition1(SqList *&L)
{
int i = 0, j = L->length - 1;
ElemType pivot = L->data[0]; //中文翻译：枢
while (i < j)
{
while (j > i && L->data[j] > pivot)
j--;
L->data[i] = L->data[j];
while (i < j && L->data[i] < pivot)
i++;
L->data[j] = L->data[i];
}
L->data[i] = pivot;
}
//顺序表归并算法,要求不改变原有的LA和LB
void UnionList(SqList *LA, SqList *LB, SqList *&LC)
{
int i =0,j = 0,k = 0;//i,j为两组下标
while(i<LA->length && j<LB->length){
if (LA->data[i]<LB->data[j])
{
LC->data[k] = LA->data[i];
i++,k++;
}
else{
LC->data[k] = LB->data[j];
j++,k++;
}
}
while (i<LA->length)
{
LC->data[k] = LA->data[i];
i++,k++;
}
while (j<LB->length)
{
LC->data[k] = LB->data[j];
j++,k++;
}
LC->length = k;
}单链表
p是遍历用的节点，有一个工具节点用来接受创建或者进行删除，insert用s，delete用q
尾插法的工具节点r
/*单链表
记得要设置最后一个是NULL
LinkNode *pre = L,*p = L->next //这个初始化挺好的！！！
分析多或少1的时候，从开头0各和少数几个的极端情况分析。
头节点L是没有存放数据的，也不算进长度，这就解释了为什么p有时是L有时是L->next，
插入和删除都是先j<i-1找到第i-1然后操作,所以初始化为p = L，因为是对后面那个操作
*/
#include <stdio.h>
#include <malloc.h>
#define MaxSize 50
typedef int ElemType;
typedef struct LNode
{
ElemType data;
struct LNode *next;
} LinkNode; //顺序表类型
//头插法
/*这里如果只传指针的话，只是传了一个指针的副本，相当于告诉你我的地址在这里，你可以修改我地址里的东西，但是这没有什么意义，因为我需要操作的是这个指针，不然操作全都传不回去，相当于你把一个副本连在一个结构里了，虽然这个副本和原来的指针有着相同的地址，但是此时我并不需要这个地址，我此时需要的是指针本身。加引用才是把原本的指针传过来了。*/
void CreateListF(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s; //工具节点上线
L = (LinkNode *)malloc(sizeof(LinkNode));
L->next = NULL; //经典创建
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = a[i];
s->next = L->next;
L->next = s;
//头插四件套
}
}
//尾插法
void CreateListR(LinkNode *&L, ElemType a[], int n)
{
LinkNode *s, *r;
L = (LinkNode *)malloc(sizeof(LinkNode));
r = L;
for (int i = 0; i < n; i++)
{
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = a[i];
r->next = s;
r = s;
}
r->next = NULL;
}
void InitList(LinkNode *&L)
{
L = (LinkNode *)malloc(sizeof(LinkNode));
L->next = NULL;
}
void DestroyList(LinkNode *&L)
{
LinkNode *pre = L, *p = L->next; //这个初始化挺好的！！！
while (p != NULL)
{
free(pre);
pre = p;
p = p->next;
}
free(pre); //最后一步别忘了！！
}
bool ListEmpty(LinkNode *L)
{
return (L->next == NULL);
}
int ListLength(LinkNode *L)
{
int n = 0;
LinkNode *p = L;
while (p->next != NULL)
{
n++;
p = p->next;
}
return n;
}
void DispList(LinkNode *L)
{
LinkNode *p = L->next;
while (p != NULL)
{
printf("%d", p->data);
p->next;
}
printf("\n");
}
bool GetElem(LinkNode *L, int i, ElemType &e)
{
int j = 0;
if (i <= 0)
return false; //别漏了
LinkNode *p = L;
while (j < i && p)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
e = p->data;
return true;
}
}
//
int LocateElem(LinkNode *L, ElemType e)
{
int i = 1;//逻辑修正
LinkNode *p = L->next;
while (p != NULL && p->data != e)
{
p = p->next;
i++;
}
if (p == NULL)
return 0;
else
return i;
}
bool ListInsert(LinkNode *&L, int i, ElemType e)
{
int j = 0;
LinkNode *p = L, *s;
if (i <= 0)
return false;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = e;
s->next = p->next;
p->next = s;
return true;
}
}
bool ListDelete(LinkNode *&L, int i, ElemType &e)
{
int j = 0;
LinkNode *p = L, *q;
if (i <= 0)
return false;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
q = p->next;
if (q == NULL)
return false; //多检验一次，因为检验不到这里
/*不如直接if(!(p && p->next)) return false;*/
e = q->data;
p->next = q->next;
free(q);
return true;
}
}
//****************************************************************************************************
//删除一个单链表L中元素最大的节点（假设唯一）插入一个标记就好了
void delmaxnode(LinkNode *&L)
{
LinkNode *p = L->next, *pre = L, *maxp = p, *maxpre = pre;
while (p != NULL)
{
if (maxp->data < p->data)
{
maxp = p;
maxpre = pre;
}
pre = p;
p = p->next;
}
maxpre->next = maxp->next;
free(maxp);
}
//使元素递增有序排列，没有想象中巧妙
void sort(LinkNode *&L)
{
LinkNode *p, *pre, *q;
p = L->next->next;
L->next->next = NULL;
//p接下了第二个节点，原来的头和首被当作了新的有序链表
while (p != NULL)
{
q = p->next; //保存原来剩下的链
pre = L; //每次pre都从头扫描一遍。。。
while (pre->next != NULL && pre->next->data < p->data)
pre = pre->next;//找到合适的位置
p->next = pre->next;
pre->next = p;//p接在这
p = q;//去q保存的地方继续操作
}
}
void UnionList1(LinkNode *LA,LinkNode *LB,LinkNode *&LC){
LinkNode *pa = LA->next,*pb = LB->next,*r,*s;//尾插法和创建
LC =(LinkNode *)malloc(sizeof(LinkNode));
while(pa!=NULL && pb!=NULL){
if(pa->data < pb->data){
s =(LinkNode *)malloc(sizeof(LinkNode));
s->data = pa->data;
r->next = s;
r = s;
pa = pa->next;
}
else{
if(pb->data > pa->data){
s =(LinkNode *)malloc(sizeof(LinkNode));
s->data = pb->data;
r->next = s;
r = s;
pb = pb->next;
}
}
while (pa!=NULL)
{
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = pa->data;
r->next = s;
r = s;
pa = pa->next;
}
while (pb!=NULL)
{
s = (LinkNode *)malloc(sizeof(LinkNode));
s->data = pb->data;
r->next = s;
r = s;
pb = pb->next;
}
r->next =NULL;
}循环双链表
/*双链表
return true;//不要漏了
*/
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct DNode
{
ElemType data;
struct DNode *prior;
struct DNode *next;
} DLinkNode; //顺序表类型
//建立头插法
void CreateListF(DLinkNode *&L, ElemType a[], int n)
{
DLinkNode *s;
L = (DLinkNode *)malloc(sizeof(DLinkNode));
L->prior = L->next = NULL;
for (int i = 0; i < n; i++)
{
s = (DLinkNode *)malloc(sizeof(DLinkNode));
s->prior = L;
s->data = a[i];
s->next = L->next;
//一共要链4条，但是这一条可能不需要链接👇
if (L->next != NULL)
L->next->prior = s;
L->next = s;
}
}
void CreateListR(DLinkNode *&L, ElemType a[], int n)
{
DLinkNode *s, *r;
L = (DLinkNode *)malloc(sizeof(DLinkNode));
r = L;
for (int i = 0; i < n; i++)
{
s = (DLinkNode *)malloc(sizeof(DLinkNode));
s->data = a[i];
r->next = s;
s->prior = r;
r = s;
}
r->next = NULL;
}
//其余操作很多类似单链表，插入和删除有点区别罢了,工具节点叫s
bool ListInsert(DLinkNode *&L, int i, ElemType e)
{
int j = 0;
DLinkNode *p = L, *s;
if (i <= 0)
return false;
while (j < i - 1 && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
s = (DLinkNode *)malloc(sizeof(DLinkNode));
s->data = e;
s->prior = p;
s->next = p->next;
if (p->next != NULL)
p->next->prior = s;
p->next = s;
return true; //不要漏了
}
}
//****************************************************************************************************
//工具节点叫q
bool ListDelete(DLinkNode *&L, int i, ElemType &e)
{
int j = 0;
DLinkNode *p = L, *q;
if (i <= 0)
return false;
while (j < i && p != NULL)
{
j++;
p = p->next;
}
if (p == NULL)
return false;
else
{
q = p->next;
e = q->data;
p->next = q->next;
if (q->next != NULL)
q->next->prior = p;
free(q);
return true;
}
}
//逆置,头插法就能进行逆置,头节点还能保留
void reverse(DLinkNode *&L)
{
DLinkNode *p = L->next, *q;
L->next = NULL;
while (p != NULL)
{
q = p->next;
p->next = L->next;
if (L->next != NULL)
L->next->prior = p;
p->prior = L;
L->next = p->next;
p = q; //继续指向后继节点
}
}
//双链表的删除是不需要工具节点的，这里用一个循环双链表的例子展示一下,删除第一个data为x的节点
bool delelem(DLinkNode *&L, ElemType x)
{
DLinkNode *p = L->next; //不需要工具点，p可以直接指向操作节点，而不是前一个
while (p != L && p->data != x)
p = p->next;
if (p == L)
return false;
else
{
p->next->prior = p->prior;
p->prior->next = p->next;
free(p);
return true;
}
}
//循环双链表判断对称
bool Symm(DLinkNode *L)
{
bool same = true; //这类题的典型flag
DLinkNode *p = L->next;
DLinkNode *q = L->prior;
while (same)
{
if (p->data != q->data)
same = false;
else
{
if (p == q || p == q->prior)
break; //当相等（奇数）或相邻（偶数），为结束条件
q = q->prior;
p = p->next;
}
}
return same;
}2.栈和队列
顺序栈
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 50
typedef int ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int top;
} SqStack;
void InitStack(SqStack *&s)
{
s = (SqStack *)malloc(sizeof(SqStack));
s->top = -1;
}
void DestroyStack(SqStack *&s)
{
free(s);
}
bool StackEmpty(SqStack *s)
{
return s->top == -1;
}
bool Push(SqStack *&s, ElemType e)
{
if (s->top == MAXSIZE - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(SqStack *&s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
bool GetTop(SqStack *s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
//判断字符串是否为对称串
bool Symmetry(ElemType str[])
{
int i;
ElemType e;
SqStack *st;
InitStack(st);
for (i = 0; str[i] != '\0'; i++)
Push(st, str[i]);
for (int i = 0; str[i] != '\0'; i++)
{
Pop(st, e);
if (e != str[i])
{
DestroyStack(st);
return false;
}
DestroyStack(st);
return true;
}
}
/*
共享栈，适用于一方可能用到满，另一方还有很多空间
栈空：top1 == -1 top2 == MAXSIZE
栈满：top1 ==top2-1
进栈出栈的时候top2的操作和top1是反的
循环队列A[0..n-1]存放其元素值，F表示队头元素所在的前一个位置，R表示队尾元素的位置。则当前队列中的元素数是
当R>F时，元素个数为 R-F个
当R<F时，元素个数为 n - （F-R）= R-F+n个
*/
链栈
//选用带头结点的，更加便捷
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 50
typedef int ElemType;
typedef struct linknode
{
ElemType data;
linknode *next;
} LinkStNode; //这名字真长
void InitStack(LinkStNode *&s)
{
s = (LinkStNode *)malloc(sizeof(LinkStNode));
s->next = NULL;
}
void DestroyStack(LinkStNode *&s)
{
LinkStNode *pre = s, *p = s->next;
while (p != NULL)
{
free(pre);
pre = p;
p = p->next;
}
free(pre);
}
bool StackEmpty(LinkStNode *s)
{
return (s->next == NULL);
}
void Push(LinkStNode *&s, ElemType e)
{
LinkStNode *p;
p = (LinkStNode *)malloc(sizeof(LinkStNode));
p->data = e;
p->next = s->next;
s->next = p;
}
bool Pop(LinkStNode *&s, ElemType &e)
{
LinkStNode *p;
if (s->next == NULL)
return false;
p = s->next;
e = p->data;
s->next = p->next;
free(p);
return true;
}
bool GetTop(LinkStNode *s, ElemType &e)
{
if (s->next == NULL)
return false;
e = s->next->data;
return true;
}
//迷宫问题和逆波兰表达式在P87顺序队列
//在队头进行删除，在队尾进行插入
//记住，front指的是空的地方
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 50
typedef int Elemtype;
typedef struct
{
Elemtype data[MAXSIZE];
int front, rear;
} SqQueue;
void InitQueue(SqQueue *&q)
{
q = (SqQueue *)malloc(sizeof(SqQueue));
q->front = q->rear = -1;
}
void DestoryQueue(SqQueue *&q)
{
free(q);
}
bool QueueEmpty(SqQueue *q)
{
return (q->front == q->rear);
}
bool enQueue(SqQueue *&q, Elemtype e)
{
if (q->rear == MAXSIZE - 1)
return false;
q->rear++;
q->data[q->rear] = e;
return true;
}
bool deQueue(SqQueue *&q, Elemtype &e)
{
if (q->front == q->rear)
return false;
q->front++;
e = q->data[q->front];
return true;
}
/****************************************************************************************/
//环形队列
void InitQueue(SqQueue *&q)
{
q = (SqQueue *)malloc(sizeof(SqQueue));
q->front = q->rear = 0; //不是-1了
}
bool enQueue(SqQueue *&q, Elemtype e)
{
if ((q->rear + 1) % MAXSIZE == q->front)
return false;
q->rear = (q->rear + 1) % MAXSIZE;
q->data[q->rear] = e;
return true;
}
bool dequeue(SqQueue *&q, Elemtype e)
{
if (q->front == q->rear)
return false;
q->front = (q->front + 1) % MAXSIZE;
return true;
}
//这两个if判断条件挺有趣的
//队列非常有层次感，有很多妙用，既可以用于递归层次，又可以用于重复
//比如书上这个很强的1212报到1出列的问题
void number(int n)
{
int i;
ElemType e;
SqQueue *q;
for (int i = 0; i <= n; i++)
enQueue(q, i);
printf("报数出列顺序：\n");
while (!QueueEmpty(q))
{
dequeue(q, e);
printf("%d", e);
if (!QueueEmpty(q))
{
dequeue(q, e);
enQueue(q, e); //偶数惨遭重新排队哈哈
}
printf("\n");
DestoryQueue(q);
}
}
//还可以定制双端队列什么的，其实原理都差不多链队
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct qnode
{
ElemType data;
struct qnode *next;
} DataNode;
//需要一个链队节点
typedef struct
{
DataNode *front;
DataNode *rear;
} LinkQuNode;
void InitQueue(LinkQuNode *&q)
{
q = (LinkQuNode *)malloc(sizeof(LinkQuNode));
q->front = q->rear = NULL;
}
void DestroyQueue(LinkQuNode *&q)
{
DataNode *pre = q->front, *p;
if (pre != NULL)
{
p = pre->next;
while (p != NULL)
{
free(pre);
pre = p;
p = pre->next;
}
free(pre); //这个怎么总是忘掉啊！
}
free(q);
}
bool QueueEmpty(LinkQuNode *q)
{
return (q->rear == NULL);
}
void enqueue(LinkQuNode *&q, ElemType e) //因为无限长度，所以类型是bool
{
DataNode *p;
p = (DataNode *)malloc(sizeof(DataNode));
p->data = e;
p->next = NULL;
if (q->rear == NULL)
q->front = q->rear = p; //还要判断是不是空列表！！！
else
{
q->rear->next = p;
q->rear = p;
}
}
bool dequeue(LinkQuNode *&q, ElemType &e)
{
DataNode *t;
if (q->rear == NULL)
return false;
t = q->front;//两种情况都可以先将t指过来
if (q->front == q->rear) //只有一个节点
q->front = q->rear = NULL;
else
q->front = t->next;
free(t);
return true;
}
3.串
顺序串
若串S=′software′,其子串的数目是()
字符串的子串，就是字符串中的某一个连续片段。截取一个字符串长度需要一个起始位置和结束位置。字符串“software”有8个字符，可是设置间隔的位置有9个，使用C(9,2)=36即可求得字符串“software”的所有子串。因为题目标明空串也是子串，故还需要加上1，总共37个子串。所以答案选37
空格串是指由空格字符所组成的字符串，其长度等于空格个数。 。
组成串的数据元素只能是字符。
/*
StrAssign(&s,cstr)将cstr字符串内容赋给s
DestoryStr(&s)销毁串
StrCopy(&s,t)串复制，将串t赋给串s
StrEqual(s,t)
StrLength(s)
Concat(s,t)返回一个新串，不改变原来的串
SubStr(s,i,j)求子串
InsStr(s1,i,s2)字串插入
DelStr(s,i,j)字串删除
RepStr(s,i,j,t)字串替换
DispStr(s)串输出
*/#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 50
typedef struct
{
char data[MAXSIZE];
int length;
} SqString;
//把字符串转换成串的数据结构
void StrAssign(SqString &s, char cstr[])
{
int i;
for (int i = 0; cstr[i] != '\0'; i++)
s.data[i] = cstr[i];
s.length = i;
}
void DestoryStr(SqString &s) {} //因为这个不是malloc分配的，会自动回收
void StrCopy(SqString &s, SqString t)
{
int i;
for (i = 0; i < t.length; i++)
{
s.data[i] = t.data[i];
s.length = t.length;
}
}
//判断相等
bool StrEqual(SqString s, SqString t)
{
bool same = true;
int i;
if (s.length != t.length) //能用长度排除就直接去世吧
same = false;
else
for (i = 0; i < s.length; i++)
if (s.data[i] != t.data[i])
{
same = false;
break;
}
return same;
}
int StrLength(SqString s)
{
return s.length;
}
//链接
SqString Concat(SqString s, SqString t)
{
SqString str;
int i;
str.length = s.length + t.length;
for (i = 0; i < s.length; i++)
str.data[i] = s.data[i];
for (i = 0; i < t.length; i++)
str.data[s.length + i] = t.data[i];//从这时起，下标注意进行简单的计算
return str;
}
//求子串，返回从第i个字符开始的，连续j个字符组成的字串
SqString SubStr(SqString s, int i, int j)
{
int k;
SqString str;
str.length = 0;
if (i <= 0 || i > s.length || j < 0 || i + j - 1 > s.length)
//i+j-1注意一下下，理解不了就最简单的i=1,j=2,s
return str;
for (k = i - 1; k < i + j - 1; k++) //i-1开始，因为逻辑和物理差1
{
str.data[k - i + 1] = s.data[k];
}
str.length = j;
return str;
}
//这个里面的加减1有点骚，理解好了这类题就不怕了。
SqString IntStr(SqString s1, int i, SqString s2)
{
int j;
SqString str;
str.length = 0;
if (i <= 0 || i > s1.length + 1) //插入的时候是可以多插一位的
return str; //返回空串
for (j = 0; j < i - 1; j++)
str.data[j] = s1.data[j];
for (j = 0; j < s2.length; j++)
str.data[i + j - 1] = s2.data[j];
for (j = i - 1; j < s2.length; j++)
str.data[s2.length + j] = s1.data[j];
str.length = s1.length + s2.length;
return str;
}
SqString DelStr(SqString s, int i, int j)
{
int k;
SqString str;
str.length = 0; //便于返回空串
if (i <= 0 || i > s.length || i + j - 1 > s.length || j < 0)
return str;
for (k = 0; k < i; k++)
str.data[k] = s.data[k];
for (k = i + j - 1; k < s.length; k++)
str.data[k - j] = s.data[k];
str.length = s.length - j;
}
//将i开始到j的字串用t替换
//我好像有点明白了，他在for循环里用的索引对标某个长度，很简单，其他的操作通过改变数组索引的表达式来实现。
SqString RepStr(SqString s, int i, int j, SqString t)
{
int k = 0;
SqString str;
str.length = 0;
if (i <= 0 || i > s.length || i + j - 1 > s.length - 1 || j < 0)
return str;
for (k = 0; k < i; k++)
str.data[k] = s.data[k];
for (k = 0; k < t.length; k++)
str.data[k + j] = t.data[k];
for (k = i + j - 1; k < s.length; k++)
str.data[t.length - j + k] = s.data[k];
str.length = s.length - j + t.length;
return str;
}
void DispStr(SqString s)
{
int i;
if (s.length > 0)
{
for (i = 0; i < s.length; i++)
printf("%c", s.data[i]);
}
printf("\n");
}
//比较大小
int Strcmp(SqString s, SqString t)
{
int i, comlen;
if (s.length < t.length)
comlen = s.length;
else
comlen = t.length; //这里也包括了相等的情况
for (i = 0; i < comlen; i++)
if (s.data[i] > t.data[i])
return 1;
else if (s.data[i] < t.data[i])
return -1;
if (s.length == t.length)
return 0;
else if (s.length > t.length)
return 1;
else
return -1;
}
//求s中出现的第一个最长连续相同字符构成的平台，用index开始索引，maxlen保存长度
void LongestString(SqString s, int &index, int &maxlen)
{
index = maxlen = 0;
int length, i = 1, start; //用来保存局部的 这种全局和局部都有对应的变量！
while (i < s.length)
{
start = i - 1; //留个物理索引
length = 1;
while (i < s.length && s.data[i] == s.data[i - 1])
{
i++;
length++;
}
if (maxlen < length)
{
maxlen = length;
index = start;
}
}
}
//Brute-Force
int BF(SqString s, SqString t)
{
int i =0,j=0;
while(i<s.length && j<t.length)
{
if(s.data[i] == t.data[j])
i++,j++;
else
i = i-j+1,j=0;//i回退到最初的后一位，j清空
}
if(j>=t.length) return(i-t.length);
else return -1;
}链串（堆串）
#include <stdio.h>
#include <malloc.h>
//链串的创建都是用尾插法，因此都有一个工具节点r
//带头节点的单链表作为链串，结点大小是每个结点存储的字符个数,未占用的用特殊符号（#）填补
//链串中，节点大小越大，存储密度越大，基本操作有所不便，适合很少修改的情况，这里规定大小为1
typedef struct snode
{
char data; //存放字符
struct snode *next;
} LinkStrNode;
//要用尾插法保证顺序
void StrAssign(LinkStrNode *&s, char cstr[])
{
int i;
LinkStrNode *r, *p;
s = (LinkStrNode *)malloc(sizeof(LinkStrNode));
r = s;
for (i = 0; cstr[i] != '\0'; i++)
{
p = (LinkStrNode *)malloc(sizeof(LinkStrNode));
p->data = cstr[i];
r->next = p;
r = p;
}
}
void DestroyStr(LinkStrNode *&s)
{
LinkStrNode *pre = s, *p = s->next;
while (p != NULL)
{
free(p);
pre = p;
p = pre->next;
}
free(pre);
}
void StrCopy(LinkStrNode *&s, LinkStrNode *t)
{
LinkStrNode *p = t->next, *q, *r;
s = (LinkStrNode *)malloc(sizeof(LinkStrNode));
r = s;
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = NULL;
}
bool StrEqual(LinkStrNode *s, LinkStrNode *t)
{
LinkStrNode *p = s->next, *q = t->next; //直接比较本身
while (p != NULL && q != NULL && p->data == q->data)
{
p = p->next;
q = q->next;
}
if (p->data == NULL && q->data == NULL)
return true;
else
return false;
}
int StrLength(LinkStrNode *s)
{
int i = 0;
LinkStrNode *p = s->next;
while (p->data != NULL)
{
p = p->next;
i++;
}
return i;
}
//链接两个数组其实就是分别遍历一遍
LinkStrNode *Concat(LinkStrNode *s, LinkStrNode *t)
{
LinkStrNode *str, *p = s->next, *q = t->next, *r;
str = (LinkStrNode *)malloc(sizeof(LinkStrNode));
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
p = t->next; //这样直接转过来，少一个工具节点，是我蠢了
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = NULL;
return str;
}
//当参数不正确的时候返回一个空串，这里需要调用之前已经封装好的函数
LinkStrNode *Substr(LinkStrNode *s, int i, int j)
{
int k;
LinkStrNode *str, *p = s->next, *q, *r; //经典四件套哈哈
str = (LinkStrNode *)malloc(sizeof(LinkStrNode));
str->next = NULL; //先把空串准备好在这里
r = str;
if (i <= 0 || i > StrLength(s) || j < 0 || i + j - 1 > StrLength(s))
return str;
for (k = 1; k < i; k++) //这里的k取得是1，因为要取到逻辑顺序第i位的前一位，而不是物理顺序
p = p->next;
for (k = 1; k <= j; k++)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = p;
return str;
}
//怎么感觉这里所有的其实都差不多，都是链表啊啥的，没啥意思
LinkStrNode *InsStr(LinkStrNode *s, int i, LinkStrNode *t)
{
int k;
LinkStrNode *str, *p = s->next, *q, *r, *p1 = t->next;
str = (LinkStrNode *)malloc(sizeof(LinkStrNode));
str->next = NULL;
r = str;
if (i <= 0 || i > StrLength(s) + 1)
return str;
for (k = 1; k < i; k++)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
while (p1 != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p1->data;
r->next = q;
r = q;
p1 = p1->next;
}
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = NULL;
return str;
}
//这个基本上都是完全一样的，直接copy一部分，瞬间刷完，我吐了，这些那么相似的还搞
LinkStrNode *DelStr(LinkStrNode *s, int i, int j)
{
int k;
LinkStrNode *str, *p = s->next, *q, *r;
str = (LinkStrNode *)malloc(sizeof(LinkStrNode));
str->next = NULL;
if (i <= 0 || i > StrLength(s) || j < 0 || i + j - 1 > StrLength(s))
return str;
for (k = 1; k < i; k++)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
for (k = 0; k < j; k++) //这里的k应该是0，因为这个就不是逻辑序号，而是物理上的序号了
p = p->next;
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = NULL;
return str;
}
LinkStrNode *RepStr(LinkStrNode *s, int i, int j, LinkStrNode *t)
{
int k;
LinkStrNode *str, *p = s->next, *q, *r, *p1 = t->next;
str = (LinkStrNode *)malloc(sizeof(LinkStrNode));
str->next = NULL;
if (i <= 0 || i > StrLength(s) || j < 0 || i + j - 1 > StrLength(s))
return str;
for (k = 0; k < i - 1; k++) //这样的其实也是逻辑，所以i-1，使用哪种看自己喜欢吧
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
while (p1 != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
for (k = 0; k < j; k++)
p = p->next;
while (p != NULL)
{
q = (LinkStrNode *)malloc(sizeof(LinkStrNode));
q->data = p->data;
r->next = q;
r = q;
p = p->next;
}
r->next = NULL;
return str;
}
//好垃圾啊，，真的全都一样的，我感觉我都能背下来了
void DispStr(LinkStrNode s)
{
LinkStrNode *p = s->next;
while (p != NULL)
{
printf("%c", p->data);
p = p->next;
}
printf("\n");
}
//4.递归
只要确保了子结构和大结构 结构一致，就不用考虑过多细节，在设计算法的时候留意递归调用的意义，比如求树的深度，在某个地方需要子树的深度了，就直接调用就好，只用关心你这最宏观的一层，不用考虑内在的东西，这就是递归的魔力。因此【递归模型】非常重要
//在算法设计中，任何间接递归都可以转换为直接递归，这是自顶向下，同时考虑最底部的
//如果递归过程或者递归函数的递归调用语句是最后一条执行语句，则称为尾递归
/* 三个条件：
1.问题可以转化为1个或多个
2.递归调用的次数必须是有限的
3.必须有用来结束递归的条件
*/
用到递归的三种情况：
1. 数学公式，数列本身的定义就是递归的，比如n！和斐波那契数列
2. 数据结构是递归的，比如指向本身的链表，对于这样的结构，递归方法既方便又有效
但是要注意大结构和小结构保持一致性，比如对单链表设计递归算法时，通常采用不带头结点的单链表。
int Sum(LinkNode *L){
if(L == NULL) return 0;
else return(L->data + Sum(L->next))
}
3. 问题的求解是递归的，比如汉诺塔P149
void Hanoil (int n,char X,char Y,char Z)
{
if(n==1) printf("将第%d个盘片从%c移动到%c",n,X,Z)
else{
Hanoil(n-1,X,Z,Y)
printf("将第%d个盘片从%c移动到%c",n,X,Z)
}
}递归模型：递归出口和递归体，可以看P150
可以说递归的思想来自数学归纳法
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 50
typedef struct
{
int n;
char x, y, z;
bool flag;
} ElemType;
typedef struct
{
ElemType data[MAXSIZE];
int top;
} StackType;
void InitStack(StackType *&s)
{
s = (StackType *)malloc(sizeof(StackType));
s->top = -1;
}
void DestroyStack(StackType *&s)
{
free(s);
}
bool StackEmpty(StackType *s)
{
return s->top == -1;
}
bool Push(StackType *&s, ElemType e)
{
if (s->top == MAXSIZE - 1)
return false;
s->top++;
s->data[s->top] = e;
return true;
}
bool Pop(StackType *&s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
s->top--;
return true;
}
bool GetTop(StackType *s, ElemType &e)
{
if (s->top == -1)
return false;
e = s->data[s->top];
return true;
}
/*
共享栈，适用于一方可能用到满，另一方还有很多空间
栈空：top1 == -1 top2 == MAXSIZE
栈满：top1 ==top2-1
进栈出栈的时候top2的操作和top1是反的
*/
//********************************************************************
//一般，尾递归算法可以通过循环或者迭代转换为等价的非递归算法
int Fib2(int n)
{
int a = 1, b = 1, i, s;
if (n == 1 || n == 2)
return 1;
else
{
for (i = 3; i <= n; i++)
{
s = a + b;
a = b;
b = s;
}
return s;
}
}
/*对于不是尾递归的复杂递归，可以在 理解递归调用实现过程 的基础上
用栈来模拟递归执行过程(这是关键啊)，从而将其转换为等价的非递归算法*/
//汉诺塔问题的非递归实现：注意栈的结构决定了e1,e3的push顺序和实际执行顺序相反！
void Hanoi2(int n, char x, char y, char z)
{
StackType *st;
ElemType e, e1, e2, e3; //一共要用到这么多变量
if (n <= 0)
return;
InitStack(st);
e.n = n;
e.x = x;
e.y = y;
e.z = z;
Push(st, e);
while (!StackEmpty(st))
{
Pop(st, e);
if (e.flag == false)
{
e1.n = e.n - 1;
e1.x = e.y;
e1.y = e.x;
e1.z = e.z;
if (e1.n == 1)
e1.flag = true;
else
e1.flag = false;
Push(st, e1);
e2.n = e.n;
e2.x = e.x;
e2.y = e.y;
Push(st, e2);
e3.n = e.n - 1;
e3.x = e.x;
e3.y = e.z;
e3.z = e.y;
if (e3.n == 1)
e3.flag = true;
else
e3.flag = false;
Push(st, e3);
}
else
printf("将%d个盘片从%c移动到%c\n", e.n, e.x, e.z);
}
DestroyStack(st);
}
//递归算法执行中，最长的递归调用的链长称为该算法的递归调用深度
/*设计队规算法的基本步骤是先确定问题的递归模型，再转化成C/C++语言的函数
确定递归模型的步骤是：
1. 对原问题f(n)进行分析，假设出合理的小问题f(n-1)
2. 给出f(n)与f(n-1)甚至更多项之间的关系，也就是确定递归体，也
就是数学归纳法中的假设i = n-1成立，求证 i =n
3. 找到特定情况如f(1)作为递归出口
4. 注意栈的次序和你的逻辑次序可能需要一定的调整*/
//有0~i个元素，求最小值，思路是找到前面的最小值
double Min(double A[], int i)
{
double min;
if (i == 0)
return A[0];
else
{
min = Min(A, i - 1);
if (min > A[i])
return A[i];
else
return min;
}
}5.数组
通常只有读和写两种操作。
每个元素占k个存储单元，则LOC(ai) = LOC(a1)+(i-1) x k
二维数组大家都是按行存放的，为啥要搞出按列来。
特殊矩阵压缩
对于ai,j = bk
对称矩阵 P169
k = i(i+1)/2 + j i>=j k= j(j+1)/2 +i j>=i
下三角和对称矩阵十分相似，但是上三角还是有点差距的，最后一位有一个常数c P70
上三角：k = i(2n-i+1)/2 +j-i i<=j n(n+1)/2 i>j
下三角：k = i(i+1)/2 + j i>=j n(n+1)/2 i<j
三对角矩阵且存储到一维数组时，k = 2i+j b = 1
这样的压缩存储只需在算法中按公式作映射就可以实现随机存取
稀疏矩阵
非零元素具有随机性，用三元组表，十字链表比较复杂来存取
#include <stdio.h>
#include <malloc.h>
#define M 100 //行数
#define N 200 //列数
#define MaxSize 100 //假设最多只有100个非零项
typedef int ElemType;
typedef struct
{
int r; //行号
int c; //列号
ElemType d; //元素值
} TupNode;
typedef struct
{
int rows;
int cols;
int nums;
TupNode data[MaxSize];
} TSMatrix;
//从二维稀疏矩阵创建三元组表示,有点新奇哈哈
void CreateMat(TSMatrix &t, ElemType A[M][N])
{
int i, j;
t.rows = M;
t.cols = N;
t.nums = 0;
for (i = 0; i < M; i++)
for (j = 0; j < N; j++)
if (A[i][j] != 0)
{
t.data[t.nums].d = A[i][j];
t.data[t.nums].r = i;
t.data[t.nums].c = j;
t.nums++;
}
}
//三元组元素的赋值，不存在（0）时插入一个非零元素，存在时修改要理解好他这个数据结构是怎样的
bool Value(TSMatrix &t, ElemType x, int i, int j)
{
int k = 0, k1;
if (i < 0 || j < 0 || i >= t.rows || j >= t.cols)
return false;
while (k < t.nums && t.data[k].r < i)
k++;
while (k < t.nums && t.data[k].r == i && t.data[k].c < j)
k++; //这个查找方式。。。秀啊
if (t.data[k].r == i && t.data[k].c == j)
t.data[k].d = x; //存在这样的非0元素
else
{
for (k1 = t.nums - 1; k1 >= k; k1--) //这里注意带 =，不然第k项原本有意义的就被覆盖了
{
t.data[k1 + 1].r = t.data[k1].r;
t.data[k1 + 1].c = t.data[k1].c;
t.data[k1 + 1].d = t.data[k1].d;
}
t.data[k].r = i;
t.data[k].c = j;
t.data[k].d = x;
t.nums++;//最终四步处理
}
return true;
}
bool Assign(TSMatrix t, ElemType &x, int i, int j)
{
int k = 0;
if (i < 0 || j < 0 || i >= t.rows || j >= t.cols)
return false;
while (k < t.nums && t.data[k].r < i)
k++;
while (k < t.nums && t.data[k].r == i && t.data[k].c < j)
k++;
if (t.data[k].r == i && t.data[k].c == j)
{
x = t.data[k].d;
return true;
}
else
x = 0; //返回0
return false;
}
void DispMat(TSMatrix t)
{
int k;
if (t.nums <= 0)
return;
printf("\t%d\t%d\t%d\n", t.rows, t.cols, t.data);
printf("\t------------------------\t");
for (k = 0; k < t.nums; k++)
printf("\t%d\t%d\t%d\n", t.data[k].r, t.data[k].c, t.data[k].d);
}
//转置，把列号放在前面，那就要依次查找列号，高效的是快速转置
void TranTat(TSMatrix t, TSMatrix &tb)
{
int k, k1 = 0, v; //k1记录tb中的元素个数
tb.rows = t.cols;
tb.cols = t.rows;
tb.nums = t.nums;
if (t.nums != 0)
{
for (v = 0; v < t.cols; v++) //每一列都完整的遍历一遍，效率巨低。
for (k = 0; k < t.nums; k++)
if (t.data[k].c == v)
{
tb.data[k1].r = t.data[k].c;
tb.data[k1].c = t.data[k].r;
tb.data[k1].d = t.data[k].d;
k1++;
}
}
}
//接下来是十字链表的数据结构P178
#define Max ((M) > (N) ? M : N)
typedef struct mtxn
{
int row;
int col;
struct mtxn *right, *down; //向右循环的行指针和向下循环的列指针
union
{
ElemType value;
struct mtxn *link; //指向下个头节点
} tag;
} MatNode;
//代价是运算算法比较复杂广义表
广义表的特征：
- 广义表中的数据元素是有相对次序的
- 长度定义为最外层包含元素的个数
- 深度定义为包含括弧的重数，原子的深度为0，空表的深度为1
- 广义表可以共享，这种叫再入表
- 广义表可以是一个递归表，一个广义表可以是自己的子表，这种叫递归表，深度∞，长度有限
不讨论再入表和递归表，小写字母表示原子，大写字母表示广义表的表名
没有给出表明的叫做匿名表 ，用 · 表示
表头：head（GL）叫做表头，取第一个元素，tail（GL）为其余所有部分（包括原来的括号），显然一个广义表的表尾始终为一个广义表，空表无表头表尾：
A（）无表头表尾
B（e） 表头e 表尾（） 空的也会被算上！！
C（a，· （b,c,d）） 表头 a 表尾（（b,c,c））注意有两层括号，看来表尾会保持原有的深度
#include <stdio.h>
#include <malloc.h>
typedef int ElemType;
typedef struct lnode
{
int tag; //标识符 0为原子节点，1为表节点
union
{
ElemType data; //存放数据值
struct lnode *sublist; //指向子表的指针
} val;
struct lnode *link; //同一层的下一个元素
} GLNode;
//tag = 1的节点可以看成是一个单链表的头节点，指向子表的首节点,通过递归性，有两种解法
//解法1，把整个看成一个带头节点的单链表，种类分原子和子表，子表类似整个表，而原子则仅仅是原子处理罢了。
void fun1(GLNode *g)
{
GLNode *gl = g->val.sublist;
while (gl != NULL)
{
if (gl->tag == 1)
fun1(gl);//z
else
{
printf("原子处理语句");
}
gl = gl->link; //处理后继元素
}
}
//解法2，对于元素节点，其兄弟域的节点和整个广义表是相似的，对于表节点，其元素域和兄弟域的处理均与整个广义表相似
void fun2(GLNode *g)
{
if (g != NULL)
{
if (g->tag == 1) //为子表
fun2(g->val.sublist); //先递归处理表节点的元素域
else
{
printf("原子处理语句");
}
fun2(g->link); //处理两种节点的兄弟（不用分类，因为无论什么节点，兄弟都相似于整个表）
}
}
//实际问题中根据求解问题的特点自行选择其中来设计递归求解，比如计数：
int Count1(GLNode *g)
{
int n = 0;
GLNode *gl = g->val.sublist;
while (gl != NULL)
{
if (gl->tag == 0)
n++;
else
n += Count1(gl->val.sublist);
gl = gl->link;
}
return n;
}
int Count2(GLNode *g)
{
int n = 0;
GLNode *gl = g->val.sublist;
while (gl != NULL)
{
if (gl->tag == 1)
n += Count2(gl->val.sublist);
else
n++;
n += Count2(g->link);
}
return n;
}
int GLLength(GLNode *g)
{
int n = 0;
GLNode *gl = g->val.sublist;
while (g != NULL)
{
n++;
gl = gl->link; //只用算最表层的哈哈
}
return n;
}
int GLDepth(GLNode *g)
{
GLNode *gl;
int maxd = 0, dep; //maxd是同一层子表中深度的最大值
if (g->tag == 0)
return 0;
gl = g->val.sublist;
if (gl == NULL)
return 1;
//这下面这个操作还是挺妙的
while (gl != NULL)
{
if (gl->tag == 1)
{
dep = GLDepth(gl->val.sublist); //dep代表该节点的深度！自顶向下
if (dep > maxd)
maxd = dep;
}
gl = gl->link;
}
return (maxd + 1); //返回这一层的最大值到上一层的节点
}
//要输出成括号的形式还是有点麻烦的，元素直接输出值，子表则输出 ‘（’，空表输出‘#’，非空子表递归，再输出‘）’
//这里其实用到的就是递归思想，仅考虑一层。非常简单
void DispGL(GLNode *g)
{
if (g != NULL)
{
if (g->tag == 0)
printf("%c", g->val.data);
else
{
printf("(");
if (g->val.sublist == NULL)
printf("#");
else
DispGL(g->val.sublist);
printf(")"); //这个括号不要漏了
}
if (g->link != NULL)
{
printf(",");
DispGL(g->link); //兄弟应该在子表后面输出
}
}
}
//与输出对应的，建立广义表的链式存储结构,记得空表是 “#”，遇到则将g->val.sublist置空
//扫描到 （ 则用g递归开启一个子表节点，遇到 ）说明已经处理完，g置空
//时空复杂的均为O（n）
//切记把链式结构和符号表示分开想，不要混在一起！
//巧妙地递归逻辑，配合引用参数（注意这里默认一个元素是‘单个’字符）
//这里我一开始理解难受是因为它既有嵌套递归，又有把子任务视为平级的递归，害。
GLNode *CreateGL(char *&s)
{
GLNode *g;
char ch = *s++; //取一个字符,直接操作指针的话，便于后续调用
if (ch != '\0')
{
g = (GLNode *)malloc(sizeof(GLNode));
if (ch == '(')
{
g->tag = 1;
g->val.sublist = CreateGL(s);
}
else if (ch == ')')
g = NULL;
else if (ch == '#')
g = NULL;
else
{
g->tag = 0;
g->val.data = ch;
}
}
else
g = NULL; //若s扫描完，把g置空
ch = *s++;
if (g != NULL)
{
if (ch == ',')
g->link = CreateGL(s);
else
g->link = NULL;
}
return g;
}
//采用解法1,递归销毁，注意要灵活一点，顺序什么的不影响那么怎样方便怎样来
void DestroyGL(GLNode *&g)
{
GLNode *g1, *g2;
g1 = g->val.sublist;
while (g1 != NULL)
{
if (g1->tag == 0)
{
g2 = g1->link; //保存兄弟节点
free(g1);
g1 = g2;
}
else
{
g2 = g1->link;
DestroyGL(g1->val.sublist);
g1 = g2;
}
}
free(g);
}6.树
基本和存储
有树形表示法，文氏图表示法，凹入表示法和括号表示法等等。
树的定义是递归的，树的性质在P192
- 结点数 = 所有节点的出度（其实就是边数） + 1
- 度为m的树（就是节点中最大出度为m）中第i层上最多有m^(i-1)个节点，若每一层都是满的，称为满m次树
- 高度为h的m次树最多有(m^h - 1)/(m-1) 个节点
- 具有n个结点的m次树的最小高度为logm(n(m-1)+1)向大取整
其实性质2，3，4说的都是一种情况。。。
对于m次树，含有n个节点，那么最大高度maxh = n - (m-1) 显然，除了最后一个节点，其他度都为1就好了
基本运算有寻找特定节点，插入/删除特定节点，遍历
遍历的先中后原来是根节点的输出次序，一般都习惯先左后右。
//存储结构
#include <stdio.h>
#include <malloc.h>
//1.双亲存储，顺序存储，根节点的父节点设置为-1，其余设置为父节点在顺序中的位置
//求双亲容易，但是求某个节点的子节点难，要遍历整个存储结构
#define MaxSize 100 //假设最多只有100个非零项
#define MaxSons 100 //假设树的度为100
typedef int ElemType;
typedef struct
{
ElemType data;
int parent;
} PTree[MaxSize];
//2.子链存储，每个节点有指向所有孩子结点的指针，因为难以确定数目，统一用最大的【树的度】来分配
//找双亲费时，找孩子很方便，树的度与平均度偏差较大时，浪费
#define MaxSons 100 //假设树的度为100
typedef struct node
{
ElemType data;
struct node *sons[MaxSons];
} TSonNode;
//以此为基础求树的高度
int TreeHeight1(TSonNode *t)
{
TSonNode *p;
int i, h, maxh = 0;
if (t == NULL)
return 0;
else
{
for (i = 0; i < MaxSons; i++)
{
p = t->sons[i];
if (p != NULL)
{
h = TreeHeight1(p); //求子树的深度
if (maxh < h)
maxh = h;
}
}
}
return (maxh + 1);
}
//3.孩子兄弟链，每个节点三个域，一个元素，一个指向长子，一个指向兄弟
typedef struct tnode
{
ElemType data;
struct tnode *hp; //指向兄弟 horizontal point
struct tnode *vp; //指向孩子 vertical point
} TSBNode;
//其实这种结构是把树转换为二叉树的存储结构
//最大的优点就是方便的实现树和二叉树的相互转换,缺点时查找父节点麻烦
int TreeHeight2(TSBNode *t)
{
TSBNode *p;
int h, maxh = 0;
if (t == NULL)
return 0;
p = t->vp;
while (p != NULL) //遍历同一层的p
{
h = TreeHeight2(p->vp); //求出这一层的最大值
if (maxh < h)
maxh = h;
p = p->hp;
}
return maxh + 1;
}二叉树
呜呜呜，好长这里，冲冲冲！
二叉树是区分左右的，任何m次数都可以转化为二叉树结构
满二叉树：叶子节点都集中在二叉树的最下一层，所有分支节点都有左右孩子的树，只有度为0或2的节点。
可以进行层序编号，第一个是0，若节点为x，则左孩子为2x，右孩子为2x + 1
完全二叉树：只有最下两层节点度数可以小于2，且叶子节点全都靠左排列。
最多只有1个出度为1的节点，且节点有左孩子，结点总数n为奇数时没有出度为1的结点
满二叉树是完全二叉树的特例
二叉树性质：
非空二叉树上的叶子节点数等于双分支结点数+1
用到了：m(度的和) = n-1 度的和 = n1 + 2n2 n = n0(叶子结点数) + n1 + n2
非空二叉树的第i层最多只有2^(i-1)个结点
高度为h的二叉树最多有 2^h - 1 个结点
若节点为x，则左孩子为2x，右孩子为2x + 1，父节点为x/2 向下取整
具有n个节点的完全二叉树高度为 log2(n+1)向上取整 或者log2n向下取整 +1
树转二叉树：相邻兄弟加线，保留长子线，其余删除 森林则把根节点链接
二叉树转树：若某节点为双亲的左孩子，则把该节点的右孩子，右孩子的右孩子都与该节点的双亲连起来，
删除原二叉树中所有双亲结点与右孩子结点之间的连线。
#include <stdio.h>
#include <malloc.h>
/*先看看顺序存储结构
对于完全二叉树和满二叉树，可以实现随机存储，完全二叉树最后几个空的用 # 表示
对于一般的二叉树，可以增添一些不存在的空结点，使之成为一棵完全二叉树的形式。
图可以看看P204 */
#define MaxSize 100 //假设最多只有100个非零项
typedef int ElemType;
typedef ElemType SqBinTree[MaxSize];
//但是如果空的太多，会造成空间的大量浪费，但是查找子节点和父节点都很方便。
//当然还有一般顺序存储结构的缺点，就是插入，删除很不方便
//链式存储，称为二叉链，用根节点指针b唯一标识整个存储结构，称为二叉树b
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
//struct node *parent;
} BTNode;
//这样节省空间，但不方便访问父节点，可以增加一个指向父节点的指针域parent来解决。
//后续一般假设一棵二叉树中所有结点值均不同，为单个字符
//创建，销毁，按值查找（父），找孩子，求高度，输出 创建和输出都用括号表示法
//首先得理解二叉树的括号表示，模拟一个栈来实现,因为栈的实现很简单，并没有封装
//这个用栈保存双亲结点的思想太妙了！栈顶存放的是当前处理节点的父节点
void CreateBTree(BTNode *&b, char *str)
{
BTNode *St[MaxSize], *p; //St为顺序栈
int top = -1, k, j = 0; //j为str索引,k用来判断孩子类型
char ch;
b = NULL;
ch = str[j];
while (ch != '\0')
{
switch (ch)
{
case '(':
top++;
St[top] = p;
k = 1;
break;
case ')':
top--;
break;
case ',':
k = 2;
break;
default:
p = (BTNode *)malloc(sizeof(BTNode));
p->data = ch;
p->lchild = p->rchild = NULL;
if (b == NULL)
b = p; //这是只存在一次的还未建立根节点的情况
else
{
switch (k)//只有1和2的情况来回切换！
{
case 1:
St[top]->lchild = p;
break;
case 2:
St[top]->rchild = p;
break;
}
}
}
j++;
ch = str[j];
}
}
void DestroyBTree(BTNode *&b)
{
if (b != NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
//查找x的结点
BTNode *FindeNode(BTNode *b, ElemType x)
{
BTNode *p;
if (b == NULL)
return NULL;
else if (b->data == x)
return b;
else
{
p = FindeNode(b->lchild, x);
if (p != NULL)
return p;
else
return FindeNode(b->rchild, x);
//p
//这也把没找到的情况包含在内了，要学会简化代码
}
}
BTNode *LchildNode(BTNode *p)
{
return p->lchild;
}
BTNode *RchildNode(BTNode *p)
{
return p->rchild;
}
//求高度
int BTHeight(BTNode *b)
{
int lchild, rchild;
if (b == NULL)
return 0;
else
{
lchild = BTHeight(b->lchild);
rchild = BTHeight(b->rchild);
}
return (lchild > rchild ? lchild : rchild) + 1;
}
//终究还是比广义表简单不少啊,当是NULL的时候不操作，非常流弊
void DispBTree(BTNode *b)
{
if (b != NULL)
{
printf("%c", b->data);
if (b->lchild != NULL || b->rchild != NULL)
{
printf("(");
DispBTree(b->lchild);
printf(",");
DispBTree(b->rchild);
printf(")");
}
}
}
int main()
{
//突然想玩一下下
char str[MaxSize] = "A(B(D(,G))C(E,F))";
BTNode *BT;
CreateBTree(BT, str);
DispBTree(BT);
printf("\nI prefer Python, C is to complex and confused");
}
二叉树遍历
/*遍历，四种顺序，层次遍历是非递归的
一颗二叉树可以分为根节点和子树两类，根节点直接处理，子树递归处理
如果必须先处理子树，那就用后序，如果必须先处理根节点，那就用先序，否则随便
如果要区分左，右树，那就要考虑中序，但是比较少*/
void Preorder(BTNode *b)
{
if (b != NULL)
{
printf("%c", b->data);
Preorder(b->lchild);
Preorder(b->rchild);
}
}
void Inorder(BTNode *b)
{
if (b != NULL)
{
Inorder(b->lchild);
printf("%c", b->data);
Inorder(b->rchild);
}
}
void PostOrder(BTNode *b)
{
if (b != NULL)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
printf("%c", b->data);
}
}
//求给定二叉树的所有结点个数
int Nodes(BTNode *b)
{
if (b == NULL)
return 0;
else
return Nodes(b->lchild) + Nodes(b->rchild) + 1;
//这个是先左后右后根，是后续遍历
}
//输出所有的叶子节点
/*递归模型很重要！
f(b) === 不做任何事情 b=NULL
f(b) === 输出b的data域 b为叶子结点
f(b) === f(b->lchild);f(b->rchild) 其他情况*/
void DispLeaf(BTNode *b)
{
if (b != NULL)
{
if (b->lchild == NULL && b->rchild == NULL)
printf("%c", b->data);
DispLeaf(b->lchild);
DispLeaf(b->rchild);
}
}
//求深度，h置处置1，这个和之前那个稍微有点不同，具体分析
int Level(BTNode *b, ElemType x, int h = 1)
{
int l;
if (b == NULL)
return 0;
else if (b->data == x)
return h;
else
{
l = Level(b->lchild, x, h + 1);
if (l)
return l;
else
return (Level(b->rchild, x, h + 1)); //又见到了这种操作
}
}
//求b树第k层的结点数,h是用来传递参数，初始为1
//这是另一种递归思路，并没有回带的过程，利用了void和引用
//如果在c语言中，可以用全局变量来代替所谓的引用。
void Lnodenum(BTNode *b, int k, int h = 1, int &n)
{
if (b == NULL)
return;
else
{
if (k == h)
{
n++;
}
else if (h < k)
{
Lnodenum(b->lchild, h + 1, k, n);
Lnodenum(b->rchild, h + 1, k, n);
}
}
}
//输出x的结点的所有祖先,多判断一级的思维
bool ancestor(BTNode *b, ElemType x)
{
if (b == NULL)
return false;
else if (b->lchild != NULL && b->lchild->data == x || b->rchild != NULL && b->rchild->data == x)
{
putchar(b->data);
return true;
}
else if (ancestor(b->lchild, x) || ancestor(b->rchild, x))
{
putchar(b->data);
return true;
}
else
return false;
}
//非递归算法区域P218
//层次遍历算法
typedef struct
{
BTNode *data[MaxSize];
int front, rear;
} SqQueue;
void LevelOrder(BTNode *b)
{
BTNode *p;
SqQueue *qu;
enqueue(qu, b);
while (!QueueEmpty(qu))
{
deQueue(qu, p);
putchar(p->data);
if (p->lchild != NULL)
enqueue(qu, p->lchild);
if (p->rchild != NULL)
enqueue(qu, p->rchild);
}
}二叉树构造
由先序序列+中序序列，或者中序序列+后序序列唯一地确定一颗二叉树
实际上，先序序列的作用是确定一棵二叉树的根节点，中序序列的作用是确定左、右子树的中序序列，从而进一步确定先序序列，递归构造左右子树。
原理在P229
//二叉树的构造
//pre存放先序序列，in存放中序序列，n为二叉树的节点个数
//其实函数的参数选择同时得考虑递归时不同层级间需要的参数
BTNode *CreateBT1(char *pre, char *in, int n)
{
BTNode *b;
char *p;
int k;
if (n <= 0)
return NULL;
b = (BTNode *)malloc(sizeof(BTNode));
b->data = *pre; //根节点
for (p = in; p < in + n; p++)
if (*p == *pre)
break;
k = p - in; //确定根节点在in中的位置
b->lchild = CreateBT1(pre + 1, in, k);
b->rchild = CreateBT1(pre + k + 1, p + 1, n - k - 1);
//这里不能光考虑第一次的，要用通用的写法
return b;
}
//和上面基本一致
BTNode *CreateBT2(char *post, char *in, int n)
{
BTNode *b
char r, *p; //因为根节点在后头，所以得用一个变量单独保存
int k;
if (n <= 0)
return NULL;
b = (BTNode *)malloc(sizeof(BTNode));
r = *(post + n - 1);
b->data = r;
for (p = post; p < post + n; p++)
{
if (*p == r)
break;
}
k = p - post;
b->lchild = CreateBT2(post, in, k);
b->rchild = CreateBT2(post + k, p + 1, n - k + 1);
return b;
}哈夫曼
WPL Weighted Path Length 带权路径长度
定理：假如哈夫曼树有n个叶子结点，那么一共有2n+1个
//哈夫曼树采用数组存放，总的结点数可以算出来 P239
//前n个存放原结点（叶子结点），剩下的存放分支节点。
//思路是先将全部节点的parent、lchild、rchild赋值为-1,然后不断找最小的放在后面，同时补全信息
typedef struct
{
char data;
double weight;
int parent;
int lchild;
int rchild;
} HTNode;
void CreateHT(HTNode ht[], int n0)
{
int i, k, lnode, rnode;
double min1, min2;
for (i = 0; i < 2 * n0 + 1; i++)
ht[i].parent = ht[i].lchild = ht[i].rchild = -1;
for (i = n0; i < 2 * n0 - 1; i++)
{
min1 = min2 = 32767;
lnode = rnode = -1;
for (k = 0; k < i - 1; k++)
//通过确定两个最小值的相对次序来巧妙地处理该问题
if (ht[k].parent == -1)
{ //在尚未构造二叉树的结点中查找
if (ht[k].weight < min1)
{
min2 = min1;
rnode = lnode;
min1 = ht[k].weight;
lnode = k;
}
else if (ht[k].weight < min2)
{
min2 = ht[k].weight;
rnode = k;
}
}
ht[i].weight = ht[lnode].weight + ht[rnode].weight;
ht[i].lchild = lnode;
ht[i].rchild = rnode;
ht[lnode].parent = i;
ht[rnode].parent = i;
}
}
//哈夫曼编码,规定左分支为0，右分支为1
#define N 100
typedef struct
{
char cd[N]; //存放当前节点的哈夫曼编码
int start; //表明cd[start..n0]部分是哈夫曼编码
} HCode;
//这是个从下向上的过程，但是最终是顺序的
void CreateHCode(HTNode ht[], HCode hcd[], int n0)
{
int i, f, c;
HCode hc;
for (i = 0; i < n0; i++)
{
hc.start = n0;
c = i;
f = ht[i].parent; //初始化
while (f != -1)
{ //循环到根节点
if (ht[f].lchild == c)
hc.cd[hc.start--] = '0';
else
hc.cd[hc.start--] = '1';
c = f;
f = ht[f].parent;
}
hc.start++; //因为多减了一次，加回来
hcd[i] = hc;
}
}7.图
找强连通分量：先找一个有向环，如果外面的某个顶点到该环任意结点均有双向路径，则加入
带权图也称作网
矩阵、表存储
#define MAXV 100 //最大结点数
#define INF 32767 //所谓的正无穷，也就是没有路
#include <stdio.h>
#include <stdlib.h>
typedef int InfoType;
typedef struct
{
int no; //顶点编号
InfoType info; //其他信息
} VertexType;
typedef struct
{
int edges[MAXV][MAXV]; //邻接矩阵数组
int n, e; //顶点数、边数
VertexType vexs[MAXV]; //存放结点信息
} MatGraph;
/*适合储存边比较多的稠密图
邻接矩阵表示是唯一的，注意无向图、有向图每一行/列的意义
非常适合提取两个顶点之间的边，适用于该目的的算法*/
//邻接表结构是后续众多算法的基础，一定要弄清楚P259
//每个顶点一个链表，链接关联的边。其中的每个边结点表示一条！边！的信息，not 点
//头节点存储的则是顶点的信息，并指向首节点。
typedef struct ANode
{
int adjvex; //该边的临界点编号,指的是出边临界点
struct ANode *nextarc; //指向下个边的指针
int weight; //该边的相关信息
} ArcNode;
typedef struct Vnode
{
InfoType info;
ArcNode *firstarc;
} VNode;
typedef struct
{
VNode adjlist[MAXV]; //头节点数组
int n, e;
} AdjGraph;
//还有所谓的逆邻接表
/*邻接表的表示不唯一，取决于算法和输入次序，适合边数目稀疏的图
对于无向图，第i个单链表的边数目是顶点i的度，有向图则为出度，入度得统计所有的adjvex域为i的数目
适合提取某个顶点的所有临界点*/
//依次扫描，头插法插入。
void CreateAdj(AdjGraph *&G, int A[MAXV][MAXV], int n, int e)
{
int i, j;
ArcNode *p;
for (i = 0; i < n; i++)
G->adjlist[i].firstarc = NULL; //初始化
for (i = 0; i < n; i++)
for (j = n - 1; j >= 0; j--)
if (A[i][j] != 0 && A[i][j] != INF)
{
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->weight = A[i][j];
p->nextarc = G->adjlist[i].firstarc;
G->adjlist[i].firstarc = p;
}
G->n = n;
G->e = e;
}
//输出规则为先输出头结点的定点信息，再依次输出所有结点的顶点编号
void DispAdj(AdjGraph *G)
{
int i;
ArcNode *p;
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
printf("%3d:", i);
while (p != NULL)
{
printf("%3d[%d]", p->adjvex, p->weight);
p = p->nextarc;
}
printf("\n");
}
}
void DestroyAdj(AdjGraph *&G)
{
int i;
ArcNode *pre, *p;
for (i = 0; i < G->n; i++)
{
pre = G->adjlist[i].firstarc;
if (pre != NULL)
{
p = pre->nextarc;
while (p != NULL)
{
free(p);
pre = p;
p = pre->nextarc;
}
free(pre);
}
}
free(G); //别忘了把头节点数组也释放掉
}
//将邻接表转换为邻接矩阵
void ListToMat(AdjGraph *&G, MatGraph &g)
{
int i;
ArcNode *p;
for (i = 0; i < G->n; i++)
{
p = G->adjlist[i].firstarc;
while (p != NULL)
{
g.edges[i][p->adjvex] = p->weight;
p = p->nextarc;
}
}
g.n = G->n;
g.e = G->e;
}
/*十字链表
是给有向图用的，是邻接表和逆邻接表的结合，现在看其实非常简单。。不知道当时为啥讲那么久。*/图遍历及应用
//图的遍历，要求每个顶点仅被访问一次。
//因为图不像树，存在回路，得设置一个访问标记数组visited,当访问过时置1，否则为0
//深度优先Depyh First Search DFS
int visited[MAXV] = {0}; //全局置0,从v开始遍历
void DFS(AdjGraph *G, int v)
{
ArcNode *p;
visited[v] = 1;
printf("%2d", v);
p = G->adjlist[v].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
DFS(G, p->adjvex);
p = p->nextarc;
}
}
//广度优先算法Breadth First Search BFS,显然这种结构要用到队列
#include "linked_queue.cpp"
void BFS(AdjGraph *G, int v)
{
int w, i;
ArcNode *p;
LinkQuNode *qu;
InitQueue(qu);
int visited[MAXV];
for (i = 0; i < G->n; i++)
visited[i] = 0;
printf("%2d", v);
visited[v] = 1;
enqueue(qu, v);
while (!QueueEmpty(qu))
{
dequeue(qu, w);
p = G->adjlist[w].firstarc;
while (p != NULL)
{
if (visited[p->adjvex] == 0)
{
printf("%2d", p->adjvex);
visited[p->adjvex] = 1;
enqueue(qu, p->adjvex);
}
p = p->nextarc;
}
}
printf("\n");
}
//遍历非连通图
void DFS1(AdjGraph *G)
{
int i;
for (i = 0; i < G->n; i++)
if (visited[i] == 0)
DFS(G, i);
}
void BFS1(AdjGraph *G)
{
int i;
for (i = 0; i < G->n; i++)
if (visited[i] == 0)
BFS(G, i);
}
bool Connect(AdjGraph *G)
{
int i;
bool flag = true;
for (i = 0; i < G->n; i++)
visited[i] = 0;
DFS(G, 0);
for (i = 0; i < G->n; i++)
if (visited[i] == 0)
{
flag = false;
break;
}
return flag;
}
//图遍历算法的应用
//深度搜索判断是否存在路径。
void ExitPath(AdjGraph *G, int u, int v, bool &has)
{
int w;
ArcNode *p;
visited[u] = 1;
if (u == v)
{
has = true;
return;
}
p = G->adjlist[u].firstarc;
while (p != NULL)
{
w = p->adjvex;
if (visited[w] == 0)
ExitPath(G, w, v, has);
p = p->nextarc;
}
}
//输出从u到v的一条路径，假设已知u到v间有路径。
//只要正常遍历就好，绝对会输出一条路径，不过非常随机就是了。
void FindaPath(AdjGraph *G, int u, int v, int path[], int d)
{
//d表示path中的路径长度，初始为-1
int w, i;
ArcNode *p;
visited[u] = 1;
d++;
path[d] = u;
if (u == v)
{
for (i = 0; i <= d; i++)
{
printf("%d", path[i]);
printf("\n");
return;
}
}
p = G->adjlist[u].firstarc;
while (p != NULL)
{
w = p->adjvex;
if (visited[w] == 0)
FindaPath(G, w, v, path, d);
p = p->nextarc;
}
}
//这个递归还是让人想了一会
void FindALLPath(AdjGraph *G, int u, int v, int path[], int d)
{
//d表示path中的路径长度，初始为-1
int w, i;
ArcNode *p;
visited[u] = 1;
d++;
path[d] = u;
if (u == v)
{
for (i = 0; i <= d; i++)
{
printf("%d", path[i]);
printf("\n");
return;
}
}
p = G->adjlist[u].firstarc;
while (p != NULL)
{
w = p->adjvex;
if (visited[w] == 0)
{
FindALLPath(G, w, v, path, d);
p = p->nextarc; //递归体的核心就在这里
}
}
visited[u] = 0; //恢复环境，可以重复利用。
}
//后面的广度优先算法的应用暂时没有更新最小生成树
图的最小生成树是树的所有生成树中边上权值最小的。（实际上是选节点）
- n个顶点的话就有n - 1条边。
- 必须只使用该图中的边来构造
- 不能使用会产生回路的边。
这个应用有很多，求最小生成树的算法：Prim 、克鲁斯卡尔
只要遍历一次，就能得到生成树，分为深度优先生成树和广度优先生成树。
普利姆算法
P281 依次选择最小边，因为需要频繁取边，所以图采用邻接矩阵更合适
这体现出了从算法逻辑设计到代码实现的过程也并非易事的，需要一些巧妙的构思
// Prim算法
//建议先阅读一下P284,搞清楚lowcost(到U中的最小边)和closet（最小边对应的顶点）,这种实时更新最值的思想很有用，简化了算法
void Prim(MatGraph g, int v)
{
int lowcost[MAXV];
int MIN;
int closet[MAXV], i, j, k;
for (i = 0; i < g.n; i++)
{
lowcost[i] = g.edges[v][i];
closet[i] = v;
//初始化
}
for (i = 1; i < g.n; i++) //找出n - 1个顶点
{
MIN = INF;
for (j = 0; j < g.n; j++)
if (lowcost[j] != 0 && lowcost[j] < MIN)
{
MIN = lowcost[j];
k = j; //k记录最小边的顶点编号
}
printf("边(%d,%d)权为%d\n", closet[k], k, MIN); //输出最小生成树的一条边
lowcost[k] = 0; //标记k已经加入U中
for (j = 0; j < g.n; j++)
if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j])
{
lowcost[j] = g.edges[k][j];
closet[j] = k;
}
}
}克鲁斯卡尔算法
这才是正儿八经的选边。P285
当一个图有多个最小生成树时，这两个算法的求解结果不一定是相同的。
因为同样要频繁取边，也采用邻接矩阵来处理。
//关键在于如何判断选取一条边(i,j)加入到T中是否出现回路，可以通过判断顶点i,j是否同属于一个连通分量来解决
//利用vset[0..n-1]数组来完成，太厉害了，i和j处理时，改成i或j的vset值都可以
// Prim算法
//建议先阅读一下P284,搞清楚lowcost(到U中的最小边)和closet（最小边对应的顶点）,这种实时更新最值的思想很有用，简化了算法
void Prim(MatGraph g, int v)
{
int lowcost[MAXV];
int MIN;
int closet[MAXV], i, j, k;
for (i = 0; i < g.n; i++)
{
lowcost[i] = g.edges[v][i];
closet[i] = v;
//初始化
}
for (i = 1; i < g.n; i++) //找出n - 1个顶点
{
MIN = INF;
for (j = 0; j < g.n; j++)
if (lowcost[j] != 0 && lowcost[j] < MIN)
{
MIN = lowcost[j];
k = j; //k记录最小边的顶点编号
}
printf("边(%d,%d)权为%d\n", closet[k], k, MIN); //输出最小生成树的一条边
lowcost[k] = 0; //标记k已经加入U中
for (j = 0; j < g.n; j++)
if (lowcost[j] != 0 && g.edges[k][j] < lowcost[j])
{
lowcost[j] = g.edges[k][j];
closet[j] = k;
}
}
}
//克鲁斯卡尔
typedef struct
{
int u;
int v;
int w;
//起始顶点，终止顶点和权值
} Edge;
#define Maxsize 20000 //最大边数
void Kruskal(MatGraph g)
{
int i, j, u1, v1, sn1, sn2, k;
int vset[MAXV];
Edge E[Maxsize]; //存放所有的边
k = 0; //e数组的下标
//第一步，由g产生E
for (i = 0; i < g.n; i++)
for (j = 0; j < g.n; j++)
if (g.edges[i][j] != 0 && g.edges[i][j] != INF)
{
E[k].u = i;
E[k].v = k;
E[k].w = g.edges[i][j];
k++;
}
//InsertSort(E,g.e)//对所有的边按照权值排序
for (i = 0; i < g.n; i++)
vset[i] = i; //初始化辅助数组
k = 1; //表示当前构造生成树的第几条边，初始为1
j = 0; //E中边的下标，初始为0
//主体
while (k < g.n) //生成树有n-1条边
{
u1 = E[j].u;
v1 = E[j].v;
sn1 = vset[u1];
sn2 = vset[v1];
if (sn1 != sn2)
{
printf("(%d,%d):%d\n", u1, v1, E[j].w); //输出一条边
k++;
for (i = 0; i < g.n; i++)
if (vset[i] == sn2)
vset[i] = sn1;
}
j++;
}
}最短路径
突然想研究一下能不能上传文件
haha，那我到时候直接把源代码传上来好了，免得这个复制太难弄了
//不想做了。。狄克斯特拉算法和弗洛伊德算法，反正只考概念罢了拓扑排序
AOV
AOV网，用顶点表示活动，用有向边表示活动之间优先关系的有向图称为AOV网（顶点表示活动的网）
选择没有前驱的顶点输出，删去该顶点以及该顶点发出的所有边，重复以上二步
若全部顶点被输出，则不存在回路，否则存在回路
AOE
顶点表示事件，有向边表示活动，开始事件（源点），结束事件（汇点）
从源点到汇点所有路径中具有最大路径长度的路径称为关键路径。
建议看看P304
先进行一次拓扑排序，然后递归从头找最大，递归从尾找最小。
8.查找
线性表
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
//线性表分顺序和链式，只介绍顺序表，属于静态查找。
typedef int KeyType;
typedef struct
{
char name[100];
int years;
} InfoType;
typedef struct
{
KeyType key; //关键字
InfoType data; //其他数据
} RecType;
//顺序查找，ASL成功 = (n+1)/2 ASL失败 = n
int SeqSearch(RecType R[], int n, KeyType k)
{
int i = 0;
while (R[i].key != k && i < n)
i++;
if (i >= n)
return 0;
else
return i + 1; //逻辑值要加一
}
//从精简算法，提高查找速度的角度说，可以在R末尾增加一个关键字为k的记录为哨兵，就不用判断i是否超界
int SeqSearch1(RecType R[], int n, KeyType k)
{
int i = 0;
R[n].key = k;
while (R[i].key != k)
i++;
if (i == n)
return 0;
else
return i + 1;
}
//折半查找
//要求有序表,mid = (low+high)/2向下取整，成功返回逻辑序号，失败返回0
int BinSearch(RecType R[], int n, KeyType k)
{
int low = 0, high = n - 1, mid;
while (low <= high)
{
mid = (low + high) / 2;
if (k == R[mid].key)
return mid + 1;
if (k < R[mid].key)
high = mid - 1;
else
low = mid + 1;
}
return 0;
}
//好精简的算法！
//可以用判定树刻画，n种成功情况，成功时比较次数恰为层数和n+！种失败情况。失败时比较次数为层数-1
//ASLbn = log2(n+1)-1 最坏性能和平均性能相当接近,归纳起来复杂度为O（log2n）
//索引结构和分块查找
/*索引项一般为（关键字，地址），可以现在有序索引表中快速查找，然后通过地址找到
提高了查找效率，但是需要建立索引表会增加时空开销*/
#define MAXI 10000 //索引表最大容量。
typedef struct
{
KeyType key;
int link; //对应在存储表里的下标
} IdxType;
int IdxSearch(IdxType I[], int b, RecType R[], int n, KeyType k)
{
int s = (n + b - 1) / b; //s为每块的元素个数，I的长度为b
int low = 0, high = b - 1, mid, i;
while (low <= high)
{
mid = (low + high) / 2;
if (I[mid].key >= k)
high = mid - 1;
else
low = mid + 1;
}
//接下来在该块中顺序查找
i = I[high + 1].link; //记住是high+1，总会取到偏小的一个
while (i < I[high + 1].link + s - 1 && R[i].key != k)
i++;
if (i <= I[high + 1].link + s - 1)
return i + 1;
else
return 0;
}
/*折半查找配合时，成功查找的平均长度为ASLblk = ASLbn + ASLsq
= log2(b+1) -1 + (s+1)/2 = log2(n/s+1) + s/2 可见s即每块的长度越小越好*/
/*顺序查找时，ASLblk = ((b+1)+(s+1))/2 =1/2(n/s +s) +1 因为b = n/s向上取值，当s=根号n时最佳*/树表
如果要进行表的删除、插入操作，会带来很多额外开销，若要对动态查找表进行查找，可以用几种树来。
二叉排序树的中序序列就是排好序的表
查找的ASL成功和ASL失败在P328
#include <stdio.h>
#include <stdlib.h>
//假设各结点的关键字是唯一的
typedef int KeyType;
typedef struct
{
char name[100];
int years;
} InfoType;
typedef struct node
{
KeyType key;
InfoType data;
struct node *lchild, *rchild;
} BSTNode;
//用根节点bt来唯一标识一棵二叉排序树
//插入关键字k，若已有则返回假
bool InsertBST(BSTNode *&bt, KeyType k)
{
if (bt == NULL)
{
bt = (BSTNode *)malloc(sizeof(BSTNode));
bt->key = k;
bt->lchild = bt->rchild = NULL;
return true;
}
else if (k == bt->key)
return false;
else if (k < bt->key)
return InsertBST(bt->lchild, k);
else if (k > bt->key)
return InsertBST(bt->rchild, k);
}
//创建一棵二叉排序树是从一个空树开始，一直调用插入就好了。
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt = NULL;
int i = 0;
while (i < n)
{
InsertBST(bt, A[i]);
i++;
}
return bt;
}
//销毁算法和普通的二叉树算法一样
//查找就要方便很多
BSTNode *SearchBST(BSTNode *bt, KeyType k)
{
if (bt->key == NULL || bt->key = k)
return bt;
if (k < bt->key)
return SearchBST(bt->lchild, k);
else
return SearchBST(bt->rchild, k);
}
//求最大\最小结点可以利用性质
KeyType maxnode(BSTNode *p)
{
while (p->rchild != NULL)
p = p->rchild;
return (p->key);
}
KeyType minnode(BSTNode *p)
{
while (p->lchild != NULL)
p = p->lchild;
return (p->key);
}
//一定是叶子节点
//删除要分几种情况讨论，是最麻烦的。
//是叶子就直接删除，只有左、右子树就接上去
//同时有左右子树的话可以从左中选最大的结点r代替p，然后把r删除，也可以选右中最小的，一般前者平衡二叉树
平衡因子：左子树高度 - 右子树高度
平衡条件：平衡因子的绝对值小于1
前提是二叉排序树，
四种类型 调整前后中序序列相同是前提条件。这个建议看学校发的教材P283
删除的时候，如果不平衡了，可以通过左右孩子的平衡因子来判断做哪一种调整，P337
哈希表
又称散列表，设要存储的元素个数为n，设置一个长度为m>=n的连续内存单元，每个元素的关键字ki(i<=n-1)
为自变量，通过哈希函数映射到内存单元的地址h(ki)，并存储在这个内存单元中。
哈希冲突，不同的自变量映射到同一个地址
通常情况是关键字的取值区间远大于哈希地址的变化区间
查找性能取决于：
- 装填因子 α = n/m 应控制最终的α在0.6~0.9范围内
- 哈希函数应该使哈希地址尽可能均匀地分布在哈希地址空间上
- 合适的解决哈希冲突的策略。
构造哈希函数
构造哈希函数
根据关键字的结构和分布的不同可构造出许多不同的哈希函数，这里主要讨论几种常用的整数类型关键字的
直接定址法 h(k) = k + c
当关键字分布基本连续时比较好
除留余数法 h(k) = k mod p (p <= m)
这种该方法的关键是选好p，使得概率分布较平均，p奇数好，不大于m的素数效果最好
数字分析法
提取关键字较均匀的数字位，适合所有关键字值都已知的情况
还有平方取中法，折叠法等。
解决冲突
开放地址法(也叫再散列法)：
线性探测法
容易产生堆积问题，d0 = h(k) di = ( (d(i-1) + 1) mod m)
平方探测法
d0 = h(k) di = ( (d0 +- i2) mod m)
不一定能探测到哈希表上的所有单元，但最少能探测到一半的单元
还有伪随机序列法，双哈希函数法等
再哈希法：
同时构造多个哈希函数，一个冲突就换另一个
#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
//用开放地址法构造的哈希表的运算算法
#define NULLKEY -1 //空关键字值
#define DELKEY -2 //被删除关键字值
typedef int KetType;
typedef struct
{
KetType key;
int count; //探测次数域
} HashTable;
void InsertHT(HashTable ha[], int &n, int m, int p, KetType k)
{
int i, adr;
adr = k % p; //adr是关键字k对应的哈希值
if (ha[adr].key == NULLKEY || ha[adr].key == DELKEY) //可以直接放入
{
ha[adr].key = k;
ha[adr].count = 1;
}
else
{
i = 1; //i 记录k发生的次数
do
{
adr = (adr + 1) % m;
i++;
} while (ha[adr].key != NULLKEY && ha[adr].key != DELKEY);
ha[adr].key = k;
ha[adr].count = i; //设置探测次数
}
n++; //哈希表中总元素个数增1
}
void CreateHT(HashTable ha[], int &n, int m, int p, KetType keys[], int nl)
{
//由关键字序列keys[0..nl-1]创建哈希表
for (int i = 0; i < m; i++)
{
ha[i].key = NULLKEY;
ha[i].count = 0;
}
n = 0;
for (int i = 0; i < nl; i++)
InsertHT(ha, n, m, p, keys[i]); //插入nl个
}
//删除算法
//在开放地址法处理的哈希表上不能简单的删除，因为在查找算法中空是查找失败，应该置特殊值
bool DeleteHT(HashTable ha[], int &n, int m, int p, KetType k)
{
int adr;
adr = k & p;
while (ha[adr].key != NULLKEY && ha[adr].key != DELKEY)
adr = (adr + 1) % m;
if (ha[adr].key == k)
{
ha[adr].key = DELKEY;
return true;
}
else
return false;
}
void SearchHT(HashTable ha[], int m, int p, KetType k)
{
int i = 1, adr;
adr = k % p;
while (ha[adr].key != NULLKEY && ha[adr].key != k)
{
i++;
adr = (adr + 1) % m; //线性探测
}
if (ha[adr].key == k)
printf("Success:%d compare %d times", k, i);
else
printf("fail");
}ASL成功为关键字列表中每个关键字的比较次数的平均数
ASL失败为直到空时的探测次数，P357 记得要算上自己的这次
拉链法：
此时的装填因子可以设定为大于1
优点：无堆积现象，平均查找长度较短，适合无法定长的情况，元素较大时指针开销可忽略不计，删除操作容易实现
#include <stdio.h>
#include <stdlib.h>
//拉链法
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node *next;
} NodeType;
typedef struct
{
NodeType *firstp;
} HashTable;
//理解这个HashTable ha数组，下标即为“地址”
void InsertHT(HashTable ha[], int &n, int p, KeyType k)
{
int adr;
adr = k % p;
NodeType *q;
q = (NodeType *)malloc(sizeof(NodeType));
q->key = k;
q->next = NULL;
if (ha[adr].firstp == NULL)
ha[adr].firstp = q;
else
{
q->next = ha[adr].firstp;
ha[adr].firstp = q;
}
n++;
}
void CreateHT(HashTable ha[], int &n, int m, int p, KeyType keys[], int nl)
//由关键字序列keys[0..nl-1]创建哈希表
{
for (int i = 0; i < m; i++)
ha[i].firstp = NULL;
n = 0;
for (int i = 0; i < nl; i++)
InsertHT(ha, n, p, keys[i]);
}
//删除算法 在逻辑上更为简单，可以直接删除
bool DeleteHT(HashTable ha[], int &n, int m, int p, KeyType k) //删除哈希表中的关键字k
{
int adr;
adr = k % p;
NodeType *q, *preq;
q = ha[adr].firstp;
if (q = NULL)
return false;
if (q->key == k)
{
ha[adr].firstp = q->next;
free(q);
n--;
return true;
}
//首节点不为k时
preq = q;
q = q->next;
while (q != NULL)
{
if (q->key == k)
break;
q = q->next;
}
if (q != NULL)
{
preq->next = q->next;
free(q);
n--;
return true;
}
else
return false;
}
void SearchHT(HashTable ha[], int p, KeyType k)
{
int i = 0, adr;
adr = k % p;
NodeType *q = ha[adr].firstp;
while (q != NULL)
{
i++;
if (q->key == k)
break;
q = q->next;
}
if (q != NULL)
printf("success");
else
printf("fail");
}ASL成功就是比较次数求平均嘛
ASL不成功 就是每条链的结点数求平均哈哈，有几个结点就白比较了几次
9.内排序
此处的关键字是可以重复的
根据相同关键字排序后相对次序是否改变可分为稳定和不稳定，这相对于所有可能的输入实例
在排序中不需要进行数据的内、外存交换，称之为内排序。
需要关键字比较的方法有插入排序、选择排序、交换排序、归并排序
不需要的方法有基数排序
基于比较的排序主要进行两种操作：比较+移动
正序：关键字顺序正好和排序顺序相同，反序则相反。
比较排序的最好的平均理论时间复杂度为O(nlog2n) 比如堆排序、二路归并、快速排序 P367
插入排序
#include <stdlib.h>
#include <stdio.h>
//基本数据类型
typedef int KeyType;
typedef struct
{
int one;
char two;
} InfoType;
typedef struct
{
KeyType key;
InfoType data;
} RecType;
//插入排序
//直接插入排序
void InsertSort(RecType R[], int n)
{
int i, j;
RecType tmp;
for (i = 1; i < n; i++)
{
if (R[i].key < R[i - 1].key) //如果直接就大于有序区最大的，
{
tmp = R[i];
j = n - 1;
do
{
R[j + 1] = R[j];
j--;
} while (j >= 0 && R[j].key > tmp.key);
R[j + 1] = tmp;
}
}
}
//折半插入排序
//在有序区查找位置时用折半查找就好了
void BinInsertSort(RecType R[], int n)
{
int i, j, low, high, mid;
RecType tmp;
for (i = 1; i < n; i++)
{
if (R[i].key < R[i - 1].key)
{
tmp = R[i];
low = 0;
high = i - 1;
while (low <= high)
{
mid = (low + high) / 2;
if (tmp.key < R[mid].key)
high = mid - 1;
else
low = mid + 1;
}
for (j = i - 1; j >= high + 1; j--)
R[j + 1] = R[j];
R[high + 1] = tmp;
}
}
}
//希尔排序
//这和上一章查找好像啊，分组插入,原理我感觉是避免高次运算的爆炸增长
//这里取di+1 = di/2向下取整,d1 = n/2
void ShellSort(RecType R[], int n)
{
int i, j, d = n / 2;
RecType tmp;
while (d > 0)
{
for (i = d; i < n; i++) //这个上下界真是绝了，一步到位全部都排好，我还想了一会
{
tmp = R[i];
j = i - d;
while (j >= 0 && tmp.key < R[j].key)
{
R[j + d] = R[j];
j = j - d;
}
R[j + d] = tmp;
}
d = d / 2;
}
}交换排序
//交换排序
//冒泡排序,从后开始，把有序的冒到最前面
void BubbleSort(RecType R[], int n)
{
int i, j;
RecType tmp;
for (i = 0; i < n - 1; i++)
for (j = n - 1; j > i; j--)
if (R[j].key < R[j - 1].key)
{
tmp = R[j];
R[j] = R[j - 1];
R[j - 1] = tmp;
}
}
//实际上，一旦某一趟不出现任何元素交换，就说明排好序了，可以用一个flag来达到这点
//快速排序 当年初学感觉非常巧妙的算法哈哈
//选一个枢纽（一般第一个），然后将所有的放在其前后，递归进行处理
int partition(RecType R[], int s, int t)
{ //从头尾向中扫描
int i = s, j = t;
RecType tmp = R[i];
while (i < j)
{
while (j > i && R[j].key >= tmp.key)
j--;
R[i] = R[j];
while (i > j && R[i].key <= tmp.key)
i++;
R[j] = R[i];
}
R[i] = tmp;
return i;
}
void QuickSort(RecType R[], int s, int t) //对R[s...t]元素进行快速排序
{
int i;
if (s < t)
{
i = partition(R, s, t);
QuickSort(R, s, i - 1);
QuickSort(R, s + 1, t);
}
}选择排序
//选择排序
//基本思路是每一趟都挑出最大、最小的，适合从大量元素中选择一部分排序元素
//简单选择选择
//分成有序区和无序区，从无序区选出最的后与无序区第一个元素交换，之所以叫简单排序是因为找最小值的方法是简单的两两比较
void SelectSort(RecType R[], int n)
{
int i, j, k;
RecType tmp;
for (i = 0; i < n - 1; i++)
{
k = i;
for (j = i + 1; j < n; j++)
if (R[j].key < R[k].key)
k = j; //k记录最值的位置
if (k != i)
{
tmp = R[k];
R[k] = R[i];
}
}
}
//堆排序
/*看成是一颗完全二叉树的顺序存储结构，大根堆，小根堆，挑选最大元素是采用筛选方法实现的
筛选：假定某节点左右子树是大根堆，选择子节点和本身最大的上来，由于可能会破坏子树，因此递归判断*/
void sift(RecType R[], int low, int high)
{
int i = low, j = 2 * i; //low是根节点,j指向当前结点的孩子
RecType tmp = R[i];
while (j <= high)
{
if (j < high && R[j].key < R[j + 1].key)
j++; //看看两个孩子谁大
if (tmp.key < R[j].key)
{
R[i] = R[j];
i = j;
j = 2 * i; //这个索引的变换有点巧妙
}
else
break; //筛选结束
}
R[i] = tmp;
}
//构建初始堆，从最后一个分支点n/2向下取整开始，反复筛选
//for(i = n/2;i>=1;i--) sift(R,i,n)
void HeapSort(RecType R[], int n)
{
int i;
RecType tmp;
for (i = n / 2; i >= 1; i--)
sift(R, i, n); //建立初始堆
//每次抽掉“根”，就是堆上最大那个
for (i = n; i >= 2; i--)
{
tmp = R[1];
R[1] = R[i];
R[i] = tmp;
sift(R, 1, i - 1);
}
}归并排序
多次将两个或以上的有序表合成一个新的有序表。我们研究二路归并
先分成n个长度为1的，两两归并成n/2个向上取整的有序序列，依次类推直到得到长度为n的有序序列
我不想写啦！！！！P389自己看图吧
基数排序
借助多关键字排序的思想堆单关键字进行排序。通过“分配”、“收集”
单关键字R[i].key 由d位数字组成，每一位的值都在(0 , r)之间，二进制r为2
最低位LSD和最高位优先MSD。选择方式由数据序列特点决定，越重要的位越放在后面.
想看原理在P390
//基数排序
#define MAXD 10000 //最大关键字位数
#define MAXR 10 //每一位的取值上限（开区间）
typedef struct node
{
char data[MAXD]; //存放关键字的各位
struct node *next; //指向下一个结点
} NodeType;
//输入数据为p为首节点的单链表
void RadixSort(NodeType *&p, int r, int d)
{
NodeType *head[MAXR], *tail[MAXR], *t;
int i, j, k;
for (i = 0; i < d - 1; i++)
{
for (j = 0; j < r; j++)
head[j] = head[i] = NULL; //初始化指针
while (p != NULL) //将原链表所有节点分配到链队
{
k = p->data[i] - '0'; //找到第k个链队
if (head[j] == NULL)
{
head[k] = p;
tail[k] = p;
}
else
{
tail[j]->next = p;
tail[k] = p;
}
p = p->next;
}
p = NULL; //重新用p来收集所有节点
for (j = 0; j < r; j++)
{
if (head[j] != NULL) //找到第一个非空链队,通过首位指针处理，中间已经连好了
{
if (p == NULL)
{
p = head[j];
t = tail[j];
}
else
{
t->next = head[j];
t = tail[k]; //如果不是第一个,就连上来
}
}
}
t->next = NULL; //别忘了！！！！！卧槽结束了！
}
}虽然课后习题一道没写
虽然后面跳过了一些明显不考的算法，但是终于在考试前5天写完了还是好开心
但是还有大雾和微积分:cry:
学弟学妹们，虽然这门数据结构在未来会被淘汰，但是它的绩点很重啊QWQ,不要向我一样临时抱佛脚QWQ
试验一下新功能，把我的代码看能不能直接放在这方便你们下载
👆
待补充
串：KMP
稀疏矩阵快速转置
二叉树遍历的非递归
最短路径的两种算法
AOV和AOE
平衡二叉树的算法实现
归并排序
明年学算法设计前应该会写完这些
