[TOC]
数据结构总结
我要成为最棒的coder！
一、绪论
概念
- 程序=算法+数据结构
- 时间复杂度的运算
- 逻辑结构？
- 存储结构？
- 计算机算法必须具备
- 可以用抽象数据类型定义一个完整的数据结构
- 算法分析的目的是分析算法的效率以求改进
- 数据结构是相互之间存在一种或多种特定关系的数据集合。
问题
- 数据结构有逻辑结构、存储结构和基本操作三个方面组成？
- 时间复杂度的运算
二、线性表
问题
在老师给出的代码中
为什么老师在代码中一直使用struct Node?而不是直接一个Node了事？
真正的代码中是否通过INT返回来相应程序运行状态？
为什么要用memcpy和memset设置内容??
是否还有不带头结点的单链表？
概念
- 线性表：含有n个序列的线性结构
- 顺序表：储存空间连续的线性表
- 单链表：最简单的链式结构，每个元素节点包括数据域和地址域两个部分
- 静态链表：本质是高级语言中的一维数组，这种描述方法便于在没有指针类型的高级程序设计语言中使用链表结构。
0x01 线性表
0x01-1 创建
定义一个结构体，包含当前长度、总长度信息，以及指向数据区的指针；初始化过程中，传入一个该结构体指针的地址（二级指针），完成初始化；
代码：
typedef struct
{
Elemtype *pElem; //动态模式，只定义了一个指针，未分配数据的存储空间。本例假设每个元素都是char型，此处是实际应用中每个元素可能会是结构体变量或者结构体指针
int iCount; //当前长度
int iTotalLength; //线性表的总长度
}SeqList; //定义一个新类型，顺序表的类型名称
int InitList(SqList ** ppList)
{
SqList * Tmp;
Tmp = (SqList)malloc(sizeof(SqList));
if (Tmp == NULL)
{
return MALLOC_ERROR;
}
Tmp->pElem = (Elemtype *)malloc(LIST_INIT_SIZE * sizeof(SqList));
if (Tmp->pElem == NULL)
{
free(Tmp);
return MALLOC_ERROR;
}
Tmp->iCount = 0;
Tmp->iTotalLength = LIST_INIT_SIZE;
*ppList = Tmp;
return OK;
}
0x01-2 查找
傻瓜式比对
代码1：
int SearchByValue(SeqList *pList, Elemtype Value)
{
int pos=0;
//重要的步骤，参数校验！一定别忘了！如果Value有一定的现实含义，则还需要对其做参数有效性校验
if (pList==NULL)
{
return PARAM_ERROR;
}
while ( pos<=pList->iCount-1 && pList->pElem[pos]!= Value) //一边比较，一边往后移pos的值，直到找到或者到达有效数据的末尾
pos++;
if ( pos <= pList->iCount-1 ) //如果是以“找到”的姿态跳出while循环
return pos;
else
return NOTFIND; //如果是以“到末尾”的姿态跳出while循环
}
代码2：
int GetValue(SeqList *pList, int pos, Elemtype *pValue)
{
//重要的步骤，参数校验！一定别忘了！如果Value有一定的现实含义，则还需要对其做参数有效性校验
if (pList==NULL || pList->pElem==NULL || pos<1 || pos >pList->iCount || pValue==NULL)
{
return PARAM_ERROR;
}
*pValue= pList->pElem[pos]; //获得元素值
return 0;
}
0x01-3 插入
如果插入位置在空间之外，应该重新分配空间，使用realloc函数
代码1：
int SeqListInsert(SeqList *pList, int pos, Elemtype Value)
{
Elemtype *pNewBase, *p, *q;
if (pList==NULL || pList->pElem==NULL || pos <0 )
{
return PARAM_ERROR;
}
if ( pos > pList->iCount )
pos = pList->iCount ;
//如果当前已经装满，则需要扩展存储空间
if (pList->iCount == pList->iTotalLength)
{
pNewBase= (Elemtype *)realloc(pList->pElem, (pList->iTotalLength + LISTINCREMENT)*sizeof(Elemtype)); //请同学们进一步了解realloc的工作原理，当空间字节数较多时，该函数开销较大！
if (pNewBase== NULL)
{
return REALLOC_ERROR;
}
pList->pElem= pNewBase;
pList->iTotalLength= pList->iTotalLength + LISTINCREMENT;
}
// 可能存在说一次增加分配增加的份额不够
q= &(pList->pElem[pos]); //q 指向的这个元素及其后面所有元素都需要后移一格
for(p= &(pList->pElem[pList->iCount-1]) ; p>=q; p--) //从后面往前，循环，每个元素后移一格，直到腾出要插入的内存空间。当pos=0时，全体所有数据都需要后移一格；当pos>=iCount时，全体数据都不需要后移
*(p+1)= *p;
// 令一个整数等于正在处理的位置，然后和想要插入的pos相比对，然后后移
*q= Value; //实现插入操作
pList->iCount++; //元素增加，别忘了让有效长度值iCount加1――随时维护iCount值的准确性，以方便程序员即时读取，而不是在需要的时候才去数个数
return 0;
}
0x01-4 删除
Status ListDelete(SqList *L,int i,ElemType *e)
{ /* 初始条件：顺序线性表L已存在，1≤i≤ListLength(L) */
/* 操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1 */
ElemType *p,*q;
if(i<1||i>L->length) /* i值不合法 */
return ERROR;
p=L->elem+i-1; /* p为被删除元素的位置 */
*e=*p; /* 被删除元素的值赋给e */
q=L->elem+L->length-1; /* 表尾元素的位置 */
for(++p;p<=q;++p) /* 被删除元素之后的元素左移 */
*(p-1)=*p;
L->length--; /* 表长减1 */
return OK;
}
0x01-5 无序表合并
最优：能够选择是否查重，重新分配一个完整的空间，健壮性好
int DisorderSeqListMerge(SeqList *pListA, SeqList *pListB, int MergeOption, SeqList **pListC)
{
int i, ret;
if (pListA==NULL || pListA->pElem==NULL || pListB==NULL || pListB->pElem==NULL || MergeOption < 0 || MergeOption > 1 )
{
return PARAM_ERROR;
}
*pListC= (SeqList *)malloc( sizeof(SeqList));
if (*pListC==NULL)
{
return MALLOC_ERROR;
}
(*pListC)->iTotalLength= pListA->iTotalLength + pListB->iTotalLength;
(*pListC)->pElem= (Elemtype *)malloc( (*pListC)->iTotalLength * sizeof(Elemtype));
if ((*pListC)->pElem==NULL)
{
if ((*pListC) != NULL)
free(*pListC);
*pListC= NULL;
return MALLOC_ERROR;
}
//将A表的数据依次复制到C表数据区
for(i= 0; i<pListA->iCount; i++)
(*pListC)->pElem[i]= pListA->pElem[i];
(*pListC)->iCount= pListA->iCount;
for (i=0; i<pListB->iCount; i++)
{
ret = SearchByValue(pListA, pListB->pElem[i]);
if ( ret >= 0 && MergeOption==0) //现有重复的元素,且不允许重复
{
//什么都不做，不执行插入操作
}
else //没找到，没有重复的元素
{
SeqListInsert(*pListC, (*pListC)->iCount, pListB->pElem[i]); //将LB[i]插入到新表LC的末尾
}
}
// 没有释放A表和B表的空间
return 0;
}
0x01-6 有序表合并
定义两个暂时储存位，分别存放两个表中还没有存入的最小值，然后最小值进行比较，更小的那个存入，直到有一方表为空，此时直接将不为空的拼接到后续表中即可。
代码：
bool Merge(SeqList A, SeqList B, SeqList &C){
//合并有序顺序表A与B成为一个新的有序顺序表C
if(A.length+B.length>C.maxSize) //大于顺序表的最大长度
return false;
int i=0,j=0,k=0;
while(i<A.length && j<B.length){
//循环，两两比较，小者存入结果表
if(A.data[i] < B.data[j])
C.data[k++] = A.data[i++];
else
C.data[k++]=B.data[j++];
}
while(i<A.length) //还剩一个没有比较完的顺序表
C.data[k++] =A.data[i++];
while(j<B.length)
C.data[k++] = B.data[j++];
C.length=k;
return true;
}
0x02 单链表
0x02-1 创建
定义结构体：
typedef struct person
{
long ID; //4
char name[20]; //20
}Elemtype;
//单链表的单个数据结点的类型定义
typedef struct NODE //为什么要这样写？NODE和后面的NODE不是冲突了吗？
{
Elemtype data; //4
struct NODE *next; //4
}NODE, *pNODE; //如果定义数据结点的对象或变量，每个变量有24+4=28个字节
//单链表整体结构的类型定义
typedef struct LIST
{
int Count; //数据个数，即表长。该信息使用频繁，3种思路可做：1. 定义为pubblic权限的成员变量Count，增删清空等时候维护该变量，获取时直接以list1.Count的形式返回——有安全风险，且容易引发混乱，不提倡！
// 2. 定义成成员方法getCount()的形式，调用方法，临时去计算并返回长度值。 ——计算费时，不适合频繁使用，尤其是数据量很大的时候
// 3. 定义为private权限的成员变量Count，增删清空等时候维护该变量，获取时用public权限的成员方法getCount()去读取该变量。——这是实际普遍使用的方式
struct NODE *pHeadOfData; //指向单链表表头的指针，即书上所说的head指针。必须是private权限的，不允许其他类的对象来修改这个成员的值，对使用链表的程序员透明（即：不需要知道它的存在）。指向表头结点，一旦创建了链表对象，在销毁之前永不变。
//下面是不太重要或常用的一些成员，同学们可以自由发挥想一下，例如如下：
int maxValue; //一个并不成熟的设计，要求数据必须是可相互比较的类型，且删除后不好维护
int minValue;
struct NODE *pTailOfData //以方便快速定位到表尾结点（在数据的尾插法中可以用到）
// ......
}LIST, *LINKLIST; //如果定义对象，则每个对象有4+4+4+4=16个字节
创建代码：
int createList(LIST **ppList) //一般我们都将指向单链表第一个结点（或表头结点）的指针命名为head，这是习惯约定
{
struct LIST *pNewList;
struct NODE *pNewNode;
if (ppList==NULL) //参数校验，注意：此处校验的是ppList（不能为空，口袋必须要有！），不是*ppList（可以为NULL，表示有口袋，但是口袋里什么东西都没有）。
return PARAM_ERROR;
//创建一个表头结点，并用pNewList指向该空间
pNewNode = (struct NODE *)malloc(sizeof(struct NODE)); //申请空间，注意：申请的是一个表结点的空间(28个字节)
if (pNewNode==NULL)
{
return MALLOC_ERROR;
}
memset(pNewNode, 0, sizeof(struct NODE));
pNewNode->next = NULL; //空表，没有后续结点。表头结点的data域不需要处理，清0即可。另，养成良好习惯，当结点的next成员指向何方尚不明朗时，先置为NULL以防患于未然，避免野指针。
//创建一个表对象的空间，并用pNewList指向该空间
pNewList = (struct LIST *)malloc(sizeof(struct LIST)); //申请空间，注意：申请的是一个表对象的空间(16个字节)，而不是一个表结点的空间(28个字节)
if (pNewList==NULL)
{
free(pNewNode); //在发生异常，准备退出之前，先把之前成功申请的pNewNode结点空间给释放了！这一点很多程序员容易忽略，造成内存泄露！
return MALLOC_ERROR;
}
memset(pNewList, 0, sizeof(struct LIST));//为什么要设定为0？
pNewList->Count= 0; //设置该空表头的表长值为0
pNewList->pHeadOfData = pNewNode; //表对象的数据指针指向刚才建好的表头结点。
*ppList = pNewList; //给表头指针赋值为表头结点的地址。
//这是套路，先用一个临时变量pNewList去操作数据，然后交付给*ppList
return 0; //本函数是如何返回表头指针的？又如何调用本函数呢？思考这2个问题！能画出内存四区图来么？
}
创建2：
int createList2(LIST **ppList)
{
struct NODE *pNew;
struct NODE *pTail;
Elemtype Data;
if (ppList==NULL) //参数校验
return PARAM_ERROR;
createList(ppList); //调用之前定义的函数，产生一个空表
printf("请输入学生的5位证件号的值和姓名（空格隔开，ID值为0表示输入结束）：");
scanf("%ld", &(Data.ID));
scanf("%s", Data.name);
//创建并挂接后续的各个结点
while (Data.ID != END_ID) //程序员和用户已约定：当用户输入的数据为0（END_ID）时，表示数据录入的结束（注意，此约定不是唯一方法，仅供学习时适用）
{
//创建新的结点并赋值
pNew = (struct NODE *)malloc(sizeof(struct NODE)); //申请空间
if (pNew==NULL)
{
return MALLOC_ERROR;
}
memset(pNew, 0, sizeof(struct NODE));
pNew->data.ID= Data.ID; //为新结点的data域填入数据
memcpy(pNew->data.name, Data.name, strlen(Data.name));
pNew->next = NULL; //为新结点的next域填入数据，指向不行时填入NULL；或因为其是新的表尾结点，所以也应该将其next域填入NULL表示链表在结尾。
//将新结点挂接到原链表中，此步骤很关键！
pTail->next = pNew; //pTail专门指向链表当前的最后一个结点，此行代码实现了将新结点连入链表尾部（还记得王老师曾经讲过的指针赋值的那句口诀不？务必想起来！）
pTail = pNew; //pTail指向的结点已经不是链表的表尾结点了（挂接之后，pNew指向的结点才是新的表尾结点），故而刷新pTail，让其指向新的表尾结点。
printf("请输入学生的5位证件号的值和姓名（空格隔开，ID值为0表示输入结束）：");
scanf("%ld", &(Data.ID));
scanf("%s", Data.name);
}
return 0; //本函数是如何返回一个表的？思考这个问题！
} #### 0x02-2 查找
int SearchByPos(LIST *pList, int pos, NODE **ppNode)
{
int i;
NODE *p;
//参数校验
if (pList==NULL)
{
return PARAM_ERROR;
}
i= 0;
p= pList->pHeadOfData;
while ( i<pos && p->next!= NULL) //当没有数到逻辑顺序的第i个结点 并且 还没有到表尾的时候，则
{
p= p->next; //一边将p指针指向下一个结点
i++; //一边计数
}
if ( i==pos ) // 如果 i== pos，即p指向第pos个元素了
{
*ppNode= p; //如果是以“找到第pos个元素”的姿态跳出while循环
return 0;
}
else //如果是p->next== NULL，即以“到表尾”的姿态跳出while循环
{
*ppNode= NULL;
return NOTFIND;
}
}
0x02-3 插入
int Insert(LIST *pList, Elemtype value, int pos)
{
long len;
int ret;
struct NODE *pNew= NULL;
struct NODE *pPre= NULL;
//参数校验
if (pList==NULL)
{
return PARAM_ERROR;
}
//参数调整
len= pList->Count; //将长度信息读出来备用，len变量不定义也是可以的。
if (pos >= len)
pos= len;
if (pos <0)
pos= 0;
//插入第一步：申请新结点空间
pNew= (struct NODE *)malloc(sizeof(struct NODE));
if (pNew==NULL)
{
return MALLOC_ERROR;
}
//插入第二步：填值到新结点空间，准备就绪
memset(pNew, 0, sizeof(struct NODE));
pNew->data.ID= value.ID; //此处不能直接写成pNew->data= value;
memcpy(pNew->data.name, value.name, strlen(value.name));
pNew->next= NULL;
//插入第三步：找到第pos个结点，以备在其后插入新结点
ret= SearchByPos(pList, pos, &pPre);
if (ret== NOTFIND)
{
free(pNew);
return NOTFIND;
}
//插入第四步：插入结点
pNew->next= pPre->next;
pPre->next= pNew;
//插入第五步：长度值别忘了+1
pList->Count++;
return 0;
}
0x02-4 删除
int DelByPos(struct LIST *pList, int pos, Elemtype *pValue)
{
int ret;
struct NODE *pDel= NULL;
struct NODE *pPre= NULL;
//参数校验
if (pList==NULL)
{
return PARAM_ERROR;
}
//删除第一步：找到第pos-1个结点的地址，顺带着也就校验了pos值是否过大
ret= SearchByPos(pList, pos-1, &pPre); //要删除第pos个元素，在链表这种结构中，需要获取到第pos-1个元素的地址，以方便删除操作
if (ret== NOTFIND) //如果本来该表压根就没有第pos-1个元素，那无法完成删除，pos值过大！
{
return PARAM_ERROR;
}
//删除第二步：获取第pos个结点的地址并暂存该地址（函数的任务就是要删这个结点）
pDel= pPre->next;
if (pDel==NULL) //有第pos-1个结点，但恰好没有第pos个结点的情况，仍然归咎于pos参数传入错误
{
return PARAM_ERROR;
}
//删除第三步：将第pos个结点从链表中摘下来，使其脱离链表
pPre->next= pPre->next->next;
//删除第四步：（非必须的步骤）将该结点的值拷贝出来，以备上层函数可能使用
pValue->ID= pDel->data.ID;
memcpy(pValue->name, pDel->data.name, strlen(pDel->data.name));
//删除第五步：释放pDel指针所指向的结点空间（在堆区），注意，并不是释放pDel指针变量本身这4个字节哦！free之后，pDel变量仍然存在！成为了一个野指针！
free(pDel);
pDel=NULL; //指针复位操作。可以看出，pDel指针仍然存在，有值，但其指向的空间已被回收。为了避免误操作，特意将这4个字节的空间全部清0，即让pDel指针为NULL
//删除第六步：长度值别忘了-1
pList->Count--;
return 0;
}
0x02-5 无序合并
p = head1;
while(p->next)
p = p->next;
p->next = head2;
0x02-6 有序合并
head1=head1->next;
head2=head2->next;
while(head1!=NULL&&head2!=NULL)/*将排序好的链表1和2 的数据导入链表3*/
{
if(head1->data<=head2->data)
{
p=head1->next;
head1->next=head3->next;
head3->next=head1;
head1=p;
}
else
{
q=head2->next;
head2->next=head3->next;
head3->next=head2;
head2=q;
}
}
if(head1!=NULL)/*如果有链表1或2的数据不为空，将剩下的数据导入链表3中*/
{
p=head1;
while(p!=NULL)
{
q=p->next;
p->next=head3->next;
head3->next=p;
p=q;
}
}
if(head2!=NULL)
{
q=head2;
while(q!=NULL)
{
p=q->next;
q->next=head3->next;
head3->next=q;
q=p;
}
}
0x02-7 输出
void output(struct LIST *pList)
{
struct NODE *p;
if (pList==NULL) //参数如果不正确，则直接罢工
return;
p = pList->pHeadOfData->next; //"顺藤"，从pHeadOfData->next开始，跳过表头节点的Data域不打印
while (p != NULL) //到尾。注意，单链表的最后一个结点的next域的值为NULL，本块代码也是读取单链表的标准模板
{
printf("%6d ", p->data.ID); //"摸瓜"
printf("%s\n", p->data.name);
p = p->next; //千万别忘记本行代码，否则死循环了
}
return ;
}
0x03 单循环链表
0x03-1 求长度
int ListLength(LinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i=0;
LinkList p=L->next; /* p指向头结点 */
while(p!=L) /* 没到表尾 */
{
i++;
p=p->next;
}
return i;
}
0x03-2 合并
LinkList * Linklist_Connect(LinkList * h1, LinkList * h2)
{
LinkList * p1, * p2;
p1 = h1->next;
p2 = h2->next;
while(p1->next!=h1)
p1 = p1->next;
while(p2->next!=h2)
p2 = p2->next;
p1->next = p2->next->next;
p2->next = h1;
free(h2);
return h1;
}
0x04 双向链表
0x04-1 插入
Status ListInsert(DuLinkList L, int i, ElemType e) {
// 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1
// 改进算法2.18，否则无法在第表长+1个结点之前插入元素
DuLinkList p, s;
if (i < 1 || i > ListLength(L) + 1) // i值不合法
return ERROR;
p = GetElemP(L, i - 1); // 在L中确定第i个元素前驱的位置指针p
if (!p) // p=NULL,即第i个元素的前驱不存在(设头结点为第1个元素的前驱)
return ERROR;
s = (DuLinkList)malloc(sizeof(DuLNode));
if (!s)
return OVERFLOW;
s->data = e;
s->prior = p; // 在第i-1个元素之后插入
s->next = p->next;
p->next->prior = s;
p->next = s;
return OK;
}
0x04-2 删除
//这个Status如何定义
Status ListDelete(DuLinkList L, int i, ElemType *e) {
// 删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长
DuLinkList p;
if (i < 1) // i值不合法
return ERROR;
p = GetElemP(L, i); // 在L中确定第i个元素的位置指针p
if (!p) // p = NULL,即第i个元素不存在
return ERROR;
*e = p->data;
p->prior->next = p->next; // 此处并没有考虑链表头，链表尾
p->next->prior = p->prior;
free(p);
return OK;
}
0x05 静态链表（不考）
线性表的应用（不考，但想做一个小程序出来）
0x01 一元多项式的加减法
数据结构：两个储存位+一个指针指向下一个节点
0x02 约瑟夫环问题
代码1：
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define ListSize 100
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode, *LinkList;
LinkList Create(int n);
void Josephus(LinkList head,int n,int m);
void main()
{
LinkList h;
int n, m;
printf("请输入人数n:");
scanf("%d", &n);
printf("报数为m的人出列:");
scanf("%d", &m);
h = Create(n);
Josephus(h, n, m);
}
LinkList Create(int n)
{
LinkList head = NULL;
ListNode *s, *r;
int i;
for(i = 1; i <= n; i++)
{
s = (ListNode *)malloc(sizeof(ListNode));
s->data = i;
s->next = NULL;
if(head == NULL)
head = s;
else
r->next = s;
r = s;
}
r->next = head;
return head;
}
void Josephus(LinkList head,int n,int m)
{
ListNode *p,*q;
int i;
p = head;
while(p->next != p)
{
for(i = 1; i < m; i++) //报到m的人出列
{
q = p;
p = p->next;
}
q->next = p->next; //删除节点
printf("出列：%d\n", p->data);
free(p);
p = q->next; //p指向下一个结点，重新开始报数
}
printf("最后剩下的人:%d\n", p->data);
}
代码2：
int josephus_recursion(int n, int k) { //遞回版本
return n > 1 ? (josephus_recursion(n - 1, k) + k) % n : 0;
} ## 三、栈和队列 ### 问题 1. 为指针分配地址的时候，会记录指针的长度吗？如果不会的话，那么我们的free操作就只是在释放一个小指针，那我们在前面写malloc只是为了提示程序员？而不会告知计算机信息？
概念
- 栈：只允许在一端（栈顶）进行插入和删除的线性表，
- 队列：只允许在队尾一端进行插入操作，队头一端进行删除操作的线性表
- 链栈：类比链表和顺序表的关系，适合用来求解路径、迷宫问题
- 循环队列：普通的队列会浪费很多的空间，以数组为例，当队尾已经到达数组边界的时候，令队尾指针指向数组初节点，当
(rear+1)%MAXSIZE = front的时候，队满？这样是最不浪费空间的，好像也是完全OK的，这个数据结构的优势在于存储空间利用率高
0x01 栈
0x01-1 初始化栈
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define stack struct Stack
#define STACK_POP_ERR 42
struct Stack {
int val[10]; // 陣列空間
int top; // 堆疊頂端指標（栈顶）
};
int main() {
// 宣告并初始化資料結構空間
stack stk;
stk.top = 0;
// 推入四个
push(&stk, 3);
push(&stk, 4);
push(&stk, 1);
push(&stk, 9);
// 弹出三个
printf("%d ", pop(&stk));
printf("%d ", pop(&stk));
printf("%d ", pop(&stk));
return 0;
} #### 0x01-2 出栈
int pop(stack *stk) {
if (empty(stk))
return STACK_POP_ERR; // 不能彈出
else {
stk->top = stk->top - 1;
return stk->val[stk->top + 1];
}
}
0x01-3 进栈
void push(stack *stk, int x) {
stk->top = stk->top + 1;
stk->val[stk->top] = x;
}
0x02 链栈
0x02-1 初始化
typedef struct {
SLink top; // 棧頂指針
int length; // 棧中元素個數
} Stack;
// 构造空栈 S
void InitStack (Stack *S) {
S->top = NULL; // 設棧頂指針的初值為"空"
S->length = 0; // 空棧中元素個數為0
} #### 0x02-3 进栈
bool Push (Stack *S, ElemType e) {
ElemType * p; // 建新的結點
p = (ElemType *)malloc(sizeof(ElemType));
if (!p) // 存儲分配失敗
return false;
p->data = e;
p->next = S->top;// 鏈接到原來的棧頂
S->top = p; // 移動棧頂指針
++S->length; // 棧的長度增1
} #### 0x01-4 出栈
bool Pop (Stack *S, SElemType *e) {
if (!S->top)
return false;
else {
e = S->top -> data; // 返回棧頂元素
q = S->top;
S.top = S.top -> next; // 修改棧頂指針
--S.length; // 棧的長度減1
delete q; // 釋放被刪除的結點空間
return true;
}
}
0x03 栈的应用（不考）
0x04 链队列
0x04-1 创建
// 单链队列——队列的链式存储结构
typedef struct QNode {
QElemType data;
struct QNode *next;
} QNode, *QueuePtr;
typedef struct {
QueuePtr front, rear; // 队头、队尾指针
} LinkQueue;
// 链队列的基本操作(9个)
void InitQueue(LinkQueue *Q) {
// 构造一个空队列Q
Q->front = Q->rear = malloc(sizeof(QNode));
if (!Q->front)
exit(OVERFLOW);
Q->front->next = NULL;
}
0x04-2 判断是否为空
Status QueueEmpty(LinkQueue Q) {
// 若Q为空队列，则返回TRUE，否则返回FALSE
if (Q.front->next == NULL)
return TRUE;
else
return FALSE;
} #### 0x04-3 取队头元素
Status GetHead_Q(LinkQueue Q, QElemType *e) {
// 若队列不空，则用e返回Q的队头元素，并返回OK，否则返回ERROR
QueuePtr p;
if (Q.front == Q.rear)
return ERROR;
p = Q.front->next;
*e = p->data;
return OK;
}
0x04-4 入队列
void EnQueue(LinkQueue *Q, QElemType e) {
// 插入元素e为Q的新的队尾元素
QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
if (!p) // 存储分配失败
exit(OVERFLOW);
p->data = e;
p->next = NULL;
Q->rear->next = p;
Q->rear = p;
}
0x04-5 出队列
//看清题意中的队列是否带有头结点
Status DeQueue(LinkQueue *Q, QElemType *e) {
// 若队列不空，删除Q的队头元素，用e返回其值，并返回OK，否则返回ERROR
QueuePtr p;
if (Q->front == Q->rear)
return ERROR;
p = Q->front->next; // 指向头结点
*e = p->data;
Q->front = p->next; // 摘下头节点
if (Q->rear == p)
Q->rear = Q->front;
free(p);
return OK;
}
0x04-6 求队列长度
int QueueLength(LinkQueue Q) {
// 求队列的长度
int i = 0;
QueuePtr p;
p = Q.front;
while (Q.rear != p) {
i++;
p = p->next;
}
return i;
}
0x04-7 清空队列
void ClearQueue(LinkQueue *Q) {
// 将Q清为空队列
QueuePtr p, q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p) {
q = p;
p = p->next;
free(q);
}
} #### 0x04-8 销毁队列
void DestroyQueue(LinkQueue *Q) {
// 销毁队列Q(无论空否均可)
while (Q->front) {
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
}
0x05 循环队列
0x05-1 创建
// 队列的顺序存储结构(循环队列)
#define MAX_QSIZE 5 // 最大队列长度+1
typedef struct {
QElemType *base; // 初始化的动态分配存储空间
int front; // 头指针，若队列不空，指向队列头元素
int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
} SqQueue;
// 循环队列的基本操作(9个)
void InitQueue(SqQueue *Q) {
// 构造一个空队列Q
Q->base = malloc(MAX_QSIZE * sizeof(QElemType));
if (!Q->base) // 存储分配失败
exit(OVERFLOW);
Q->front = Q->rear = 0;
} #### 0x05-2 判断是否为空
Status QueueEmpty(SqQueue Q) {
// 若队列Q为空队列，则返回TRUE；否则返回FALSE
if (Q.front == Q.rear) // 队列空的标志
return TRUE;
else
return FALSE;
} #### 0x05-3 取队头元素
Status GetHead(SqQueue Q, QElemType *e) {
// 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
if (Q.front == Q.rear) // 队列空
return ERROR;
*e = Q.base[Q.front];
return OK;
}
0x05-4 入队列
Status EnQueue(SqQueue *Q, QElemType e) {
// 插入元素e为Q的新的队尾元素
if ((Q->rear + 1) % MAX_QSIZE == Q->front) // 队列满
return ERROR;
Q->base[Q->rear] = e;
Q->rear = (Q->rear + 1) % MAX_QSIZE;
return OK;
}
0x05-5 出队列
Status DeQueue(SqQueue *Q, QElemType *e) {
// 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR
if (Q->front == Q->rear) // 队列空
return ERROR;
*e = Q->base[Q->front];
Q->front = (Q->front + 1) % MAX_QSIZE;
return OK;
} #### 0x05-6 求队列长度
int QueueLength(SqQueue Q) {
// 返回Q的元素个数，即队列的长度
return (Q.rear - Q.front + MAX_QSIZE) % MAX_QSIZE;
}
0x05-7 清空队列
void ClearQueue(SqQueue *Q) {
// 将Q清为空队列
Q->front = Q->rear = 0;
} #### 0x05-8 销毁队列
void DestroyQueue(SqQueue *Q) {
// 销毁队列Q，Q不再存在
if (Q->base)
free(Q->base);
Q->base = NULL;
Q->front = Q->rear = 0;
} //在C语言中，某变量值置为NULL之后，再次分配内存时会回收这个地址吗？ ## 四、数组 ### 概念 数组内的存储必定是以一维的方式存储的，但不同编程语言的一维化方式不一样，分为行优先和列优先 ### 0x01 矩阵的压缩存储 为多个值相同的元只分配一个存储空间，对零元不分配空间 #### 0x01-1 对称矩阵 储存包括对角线在内的下三角数据进行储存即可，将n*n的数组存储到n*(n+1)/2的数组中 #### 0x01-2 稀疏矩阵 只对有值的地方进行存储，使用三元组队两个下标进行存储
typedef struct
{
int i,j;
ElemType e;
}Triple;
typedef struct
{
Triple data[MAXSIZE+1]
}
//转置运算也是通过三元组进行，横纵交换即可
0x02 矩阵运算
以后学人工智能和机器学习的话，应该会经常用到
五、树
问题：
非递归和递归分别适用于那种情况呢？
概念
树是n个节点的有限集 度是某节点的子节点个数 度为0的节点称为叶子 使用多颗树进行建模，称为森林 多叉树是没有回路的 二叉树：每个节点至多只有两棵子树，子树有左右之分
哈夫曼树：只注重叶子节点
- 不考虑权值的话，完全二叉树就是哈夫曼树
- 哈夫曼树中没有度为1的树
- 权值较大的节点与根的距离大于等于权值较小的节点与根的距离
- 哈夫曼树不唯一
- 一颗具有n个节点的树的节点总数为2n-1 WPL = 路径*权值
0x01 树的存储结构表示
0x01-1 双亲表示法
共两列，第一列存放数据，第二列存放父节点的下标，下标不算数据列，它只是用来查找数据的一个标识
0x01-2 孩子表示法
一列带有下标的标准链表节点，如果有孩子节点，就在地址域中延伸下去，同级的孩子节点顺序相邻，如果没有孩子节点，地址域则为NULL
0x01-3 孩子兄弟表示法
三列数据，左地址域指向孩子，右地址域指向下一个兄弟
0x02 二叉树
0x02-1 性质
- 在二叉树的第i层上，至多有2的（i-1）次方个节点
- 深度为k的二叉树，至多有(2的k次方-1)个节点
- 终端节点数=度为2的节点数+1
- 一颗深度为k且有2的k次方-1个节点的二叉树为满二叉树，再进行连续编号，就成为了完全二叉树
- 具有n个节点的完全二叉树的深度为[log2n]+1
- 对于完全二叉树
0x02-2 顺序存储结构
利用一维数组，按照完全二叉树的形式进行储存，随着深度k的增加，空间利用率会越来越低，适合矮胖型
0x02-3 链式存储结构
左右各有一个指针，适合高瘦型 （PS：之前树的表达形式都同样适用）
0x03 常见操作
0x03-1 创建
0x03-2 判断是否为空
0x03-3 遍历
- 先序：根左右
- 中序：左根右
- 后序：左右根
0x03-4 求左右孩子地址
0x04 反推二叉树
可以通过中序和后序以及一些定理，通过前或后序推测出根节点，再从中序中确定左和右，从序列推导出二叉树
- 在前序遍历序列/子序列中，第一个节点是该树/子树的根节点
- 在中序遍历系列/子序列中，该树/子树的根节点在其左右子树中序序列之间
- 在后续遍历序列/子序列中，最后一个节点是该树/子树的根节点
0x05 线索二叉树
这个老师好像没讲，看不太懂，明天早上再看？
0x05-1 前序遍历
0x05-2 中序遍历
0x05-3 后序遍历
0x06 树、森林、二叉树的转换
0x06-1 树->二叉树
- 加线：亲兄弟之间加一条线
- 去线：不同层之间只保留和第一个孩子的连线
- 形状调整
0x06-2 森林->二叉树
- 每棵树都转化为二叉树
- 依次把右侧树作为左侧树的右孩子连接起来
0x06-3 二叉树-》树
- 加线：若某节点的左孩子存在，则将这个节点的左孩子的右、再右，与这个节点连接起来
- 去线：删除原二叉树中所有节点与其右孩子节点的连线
- 形状调整
0x07 树和森林的遍历
0x07-1 先根遍历（树）
先访问根，再先根遍历每棵子树
0x07-2 后根遍历（树）
从左向右依次后跟遍历子树，再访问根节点
0x07-3 先序遍历（森林）
使用先根遍历所有的树
0x07-4 后序遍历（森林）
使用后根遍历所有的树
0x08 哈夫曼树（最优二叉树）
0x08-1 应用于判定过程
通过权值，减小尝试次数
0x08-2 哈夫曼编码
先是字频统计，然后是用短码表示频率高的，用长码表示频率低的，用根节点为1，之后的结点左为1，右为2
0x08-3 创建
选取权值最小的两棵树组成二叉树，它们的根节点最为新的元素补充进去，重复操作，最后合并两棵即可 如果题中没有特殊说明，则左小右大，如果两个值大小相等，则左侧挂单个节点
树的带权路径长度（WPL）是各个结点的路径长度乘结点权值的总和
六、图
概念
- 图：由顶点的有穷非空集合和顶点之间的边组成的G(V,E) V表示顶点的集合，E表示边的集合
- 边：元素之间的无向连线
- 弧：元素之间的有向连线
- 出度：指向的其它的箭头的数目
- 入度：被指向的箭头数目
- 连通图：任意两个元素都是连通的【】
- 生成树：n个节点、n-1条边
- 生成森林：类比上面的
- 无向完全图：任意节点之间都有边
- 有向完全图：任意节点之间都有互逆的弧
- 简单图：图中不存在顶点到自身的连线，并同一条连线不重复出现
- 网：带有权值的图
- 路径长度：路径上边或弧的数目
- 简单回路：出发点和终止点为同一个顶点，其他点都不相同
- 简单路径：所有点都不相同
- 强连通图：任意两点之间都相连
- 生成树：去掉一些边之后可以构成树
- 生成森林：去掉一些边之后可以构成森林
- 无向完全图：任意两个顶点之间都存在边
- 有向完全图：任意两个顶点之间都存在方向互为相反的弧
- 有向无环图（DAG）被用于描述一件事情的进行过程
- A0V-网：用顶点表示活动，用弧表示活动之间的优先关系
- 拓扑排序：就是对一个有向图进行构造拓扑序列的过程
- AOE-网：用弧来表示每个环节的活动，用顶点表示步骤环节开始或结束之后的状态，而弧上的权值表示进行该活动所需要的时间
- 关键路径：AOE-网中，能够从起点状态到完成终点状态的最长路径
- 连通分量：无向图中的极大连通子图。
0x01 储存结构
0x01-1 邻接矩阵表示法
行列、列行表示节点之间连通，无向图的邻接矩阵都是对称的，有向图则不一定 操作方便，但空间利用率太低，列为入度，行为出度（横出直入）
0x01-2 邻接表/逆邻接表表示法
一个一阶数组储存着各个结点，每一个节点都对应着一个单链表，表示这连通的其它节点，无向要比有向占用的储存空间大将近一倍 无序，编号来自于数组的下标，用来表示出度很方便 用逆邻接表表示入度 邻接表表示出度，逆邻接表表示入度 这种表示方法的优点就是避免了邻接矩阵中的空间过度浪费，缺点在于很难获知某个顶点的出度
0x01-3 十字链表表示法（不考）
横纵都有一个坐标，分别用来表示出度和入度 就是一个结构体带有五个属性，弧头结点标签、弧尾结点标签、权值域、同弧头的下一个节点地址、同弧尾的下一个节点地址
0x02 遍历
0x02-1 深度优先遍历
不断寻找未被访问的临接点，如果找不到，则退回上一步继续寻找
0x02-2 广度优先遍历
先访问一个结点，访问它的所有临接点，然后访问所有邻接点的邻接点
0x03 最小生成树
Prim算法以顶点为对象，适合于稠密图，Kruskal算法以边为对象，适合于稀疏图。
0x03-1 Prim算法
选取一个顶点，找距离非顶点集中顶点，与任一顶点集中任意点路径最短的边，然后到达那个节点，再选取路径最短的边。时间复杂度为n的平方
代码：
void MiniSpanTree_PRIM (MGraph G, VertexType u) {
/* 用普利姆算法從第u個頂點出發構造網G 的最小生成樹T,輸出T的各條邊。
記錄從頂點集U到V-U的代價最小的邊的輔助數組定義：
struct
{
VertexType adjvex;
VRtype lowcost;
}closedge[MAX_VERTEX_NUM];
*/
k = LocateVex(G, u);
for (j = 0 ; j < G.vexnum; j++) { //輔助數組初始化
if (j != k)
closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost}
}
closedge[k].lowcost = 0; //初始，U={u}
for (i = 1; i < G.vexnum ; i++) { //選擇其餘G.vexnum -1 個頂點
k = minimum(closedge); //求出T的下個結點：第k結點
// 此时 closedge[k].lowcost = MIN{ closedge[Vi].lowcost|closedge[Vi].lowcost>0,Vi∈V-U}
printf(closedge[k].adjvex, G.vexs[k]); //輸出生成樹的邊
closedge[k].lowcost = 0; //第k條邊併入U集
for (j = 0; j < G.vexnum; j++) {
if (G.arcs[k][j].adj < closedge[j].lowcost) //新頂點併入U後重新選擇最小邊
closedge[j] = {G.vex[k], G.arcs[k][j].adj};
}
}
}
0x03-2 Kruskal算法
在所有边进行挑选，只要不产生回路，就从小到大依次添加边
代码： 先将权值按照大小顺序进行排序，通过判断能够连接到的最大节点是否相等判断连接之后是否会产生回路，当不会产生回路的时候添加到边集中
时间复杂度为O(n log2n),其中n为边数
0x04 有向无环图及其应用
0x04-1 拓扑排序
每次都从AOV中选择一个入度为0的顶点，输出，然后删除此顶点以及所有和它相关的弧，重复上述操作，直到找不到入度为0的顶点为止，这个可以判断AOV中是否有回路，如果存在回路，则这个AOV图需要重新规划
0x04-2 关键路径问题
顶点i的最早呈现时间ve(i)：从出发点v1到vn的最长长度，不是最短距离！ 顶点i的最晚呈现时间vl(i)：与最终状态的最长路径的差值 最后ve和vl相等的数据点连起来就是关键路径
0x05 最短路径问题
0x05-1 Dijkstra算法（贪心算法）
/*
测试数据 教科书 P189 G6 的邻接矩阵 其中 数字 1000000 代表无穷大
6
1000000 1000000 10 100000 30 100
1000000 1000000 5 1000000 1000000 1000000
1000000 1000000 1000000 50 1000000 1000000
1000000 1000000 1000000 1000000 1000000 10
1000000 1000000 1000000 20 1000000 60
1000000 1000000 1000000 1000000 1000000 1000000
结果：
D[0] D[1] D[2] D[3] D[4] D[5]
0 1000000 10 50 30 60
*/
#include <iostream>
#include <cstdio>
#define MAX 1000000
using namespace std;
int arcs[10][10];//邻接矩阵
int D[10];//保存最短路径长度
int p[10][10];//路径
int final[10];//若final[i] = 1则说明 顶点vi已在集合S中
int n = 0;//顶点个数
int v0 = 0;//源点
int v,w;
void ShortestPath_DIJ()
{
for (v = 0; v < n; v++) //循环 初始化
{
final[v] = 0; D[v] = arcs[v0][v];
for (w = 0; w < n; w++) p[v][w] = 0;//设空路径
if (D[v] < MAX) {p[v][v0] = 1; p[v][v] = 1;}
}
D[v0] = 0; final[v0]=0; //初始化 v0顶点属于集合S
//开始主循环 每次求得v0到某个顶点v的最短路径 并加v到集合S中
for (int i = 1; i < n; i++)
{
int min = MAX;
for (w = 0; w < n; w++)
{
//我认为的核心过程--选点
if (!final[w]) //如果w顶点在V-S中
{
//这个过程最终选出的点 应该是选出当前V-S中与S有关联边
//且权值最小的顶点 书上描述为 当前离V0最近的点
if (D[w] < min) {v = w; min = D[w];}
}
}
final[v] = 1; //选出该点后加入到合集S中
for (w = 0; w < n; w++)//更新当前最短路径和距离
{
/*在此循环中 v为当前刚选入集合S中的点
则以点V为中间点 考察 d0v+dvw 是否小于 D[w] 如果小于 则更新
比如加进点 3 则若要考察 D[5] 是否要更新 就 判断 d(v0-v3) + d(v3-v5) 的和是否小于D[5]
*/
if (!final[w] && (min+arcs[v][w]<D[w]))
{
D[w] = min + arcs[v][w];
// p[w] = p[v];
p[w][w] = 1; //p[w] = p[v] + [w]
}
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
cin >> arcs[i][j];
}
}
ShortestPath_DIJ();
for (int i = 0; i < n; i++) printf("D[%d] = %d\n",i,D[i]);
return 0;
}
七、查找
概念
无需对数据修改的称为静态查找，需要进行修改的，称为动态查找 哈希查找：表内存在着某种映射关系，根据映射关系进行查找，如果规则冲突则根据某种方式去解决冲突8、 ASL: 平均查找长度，YASL是查找成功的，NASL是查找失败的 同义词：散列函数值相同的两个关键字
0x01 顺序查找（线性查找）：
以顺序表的形式挨个查找 成功情况下：平均查找长度：YASL=（n+1）/2 不成功：YASL = n
0x02 折半查找
对有序表进行查找，查找次数最多为[log2 n]（向下取整）+1
平均查找长度YASL = ((n+1)/n)log2 (n+1) -1,近似等于YASL = log2 (n+1) -1
代码1：
// 递归版本
int binary_search(const int arr[], int start, int end, int khey) {
if (start > end)
return -1;
int mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
if (arr[mid] > khey)
return binary_search(arr, start, mid - 1, khey);
if (arr[mid] < khey)
return binary_search(arr, mid + 1, end, khey);
return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
代码2：
// while循环
int binary_search(const int arr[], int start, int end, int khey) {
int mid;
while (start <= end) {
mid = start + (end - start) / 2; //直接平均可能會溢位，所以用此算法
if (arr[mid] < khey)
start = mid + 1;
else if (arr[mid] > khey)
end = mid - 1;
else
return mid; //最後檢測相等是因為多數搜尋狀況不是大於要不就小於
}
return -1;
}
平均查找长度为 log2(n+1) - 1
最糟糕情况下，平均查找长度为 log2(n+1) - [log2n]
0x03 索引查找
0x03-1 稠密索引
利用索引将无序表按照有序表的方式建立一个稠密索引，对应起来，但当数据量较大时，浪费空间，却浪费计算资源。
0x03-2 分块索引
块间有序，块内无序
0x04 二叉排序树（BST、二叉搜索树）
若左子树不为空，则左子树上所有结点的值均小于它根结点的值 若右子树不为空，则右子树上所有节点的值均大于它的根结点的值 它的左右子树也分别作为二叉排序树 对这棵树进行中序遍历，就可以得到一个有序的序列 （不可能有两个值是相等的？） 查找的算法复杂度为O(log2n)
0x04-1 创建
从无到有时会改变根节点的值，所以根节点参数为二重指针
0x04-2 查找
通过大小对比，判断是否存在要查找的值，如果没有，则通过参数外带的方式放回最后一个访问的结点。
0x04-3 插入
根据性质，查找某值，如果已经存在，则插入失败，如果没有存在则根据大小关系进行插入
0x04-4 删除
度为0的结点直接删，度为1的结点用子树代替本身，度为2的结点，删除之后，找根节点的前驱结点（左子树的右底）或者后驱结点（右子树的左底）替代自身，以此尽量减少变动
0x05 平衡二叉树（AVL树）
每个节点左子树和右子树的高度差不超过1的二叉排序树 平衡因子：左子树高度减去右子树高度
算法比较复杂，但之后必须要掌握
0x06 哈希查找
0x06-1 哈希函数的构造方法
要满足 ①计算简单； ②散列地址分布均匀 的特点
- 直接定址法 简单，并可以不冲突，但因为值域无法预测，所以无法解决空间复杂度的问题
- 数字分析法 采取特征中变化较大的部分去进行映射
- 折叠法 对数字分段相加，然后根据位数，确定最后几位作为哈希表的标准
- 除留取余法 mod
0x07 解决冲突
0x07-1 开放定址法
0x07-2 再哈希法
备用另一套哈希函数
0x07-3 链地址法
每个地方都是一个单链表，可无限后加数据
0x07-4 公共溢出区法
给冲突的数据另开辟一片新空间
0x08 性能分析
二次探测要比线性探测好，时间复杂度上用链地址法是最好的，只是会浪费空间 时间复杂度与填装因子的大小成正相关 填装银子等于填入表的记录个数比上哈希表长度 平均查找长度还取决于 ①哈希函数是否均匀 ②处理冲突的方法
八、排序
0x01 直接插入排序
从后向前进行比较，从而依次判断是否应该插入
#include <stdio.h>
#define MaxLength 101
void InsertOrderly(int * nums, int length, int new);
int main(void)
{
int length,new,i;
int nums[MaxLength];
printf("请输入排序序列的长度：（0<length<%d）\n",( MaxLength - 1));
scanf("%d", &length);
printf("请输入长度为%d的升序序列：\n", length);
for(i = 0;i < length;i++)
{
scanf("%d", &nums[i]);
}
printf("请输出您要插入的数字：\n");
scanf("%d", &new);
InsertOrderly(nums, length, new);
length++;
for(i = 0; i < length; i++)
{
printf("nums[%d] : %d\n", i, nums[i]);
}
return 0;
}
void InsertOrderly(int * nums, int length, int new)
{
int i,j,temp;
for(i = length-1; i >=0; i--)
{
temp = nums[i];
if(new < nums[i])
{
nums[i+1] = nums[i];
if(i == 0)
{
nums[i] = new;
}
}else{
nums[i+1] = new;
return;
}
}
}
需要根据课本中的代码进行一些优化
#include <stdio.h>
#define N 10
int main(void)
{
int i, j;
int temp;
int a[N] = { 1,2,3,4,5,6,7,0,9,8 };
for (i = 1; i < N; i++)
{
temp = a[i];
for (j = i - 1; j >= 0; j--)
{
if (a[j] > temp)
{
a[j + 1] = a[j];
}
else
{
break;
}
}
a[j + 1] = temp;
}
for (i = 0; i < N; i++)
{
printf("%d", a[i]);
}
printf("\n");
return 0;
}
0x02 希尔排序（不考代码）
以增量为间隔，进行移动排序，对于基本上是排好序的序列效率更高
希尔排序的增量序列是一个递减序列，序列中元素之间互素，序列的最后一个元素为1
维基百科中的希尔排序
0x03 冒泡排序
依次比较两个相邻元素，决定是否交换，因此第一次排序之后最大值一定排到序列的最后一位
#include
for ( i = 0; i < N; i++)
{
flag = 0;
for (j = 0; j < N - i - 1; j++)
{
if (a[j] > a[j + 1])
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
for ( i = 0; i < N; i++)
{
printf("%d", a[i]);
}
printf("\n");
return 0;
} 算法精髓，当某一次没有进行排序意味着已经有序，则退出比对 ### 0x04 快速排序 快速排序：以一个元素为枢纽，小在前，大在后，用两个指针去指向比较；排好之后的两段继续进行排序 好的情况下时间复杂度为，最坏情况下时间复杂度为，空间复杂度为O(log2n)
===C語言===
迭代法
<source lang=c line="1">
typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort(int arr[], const int len) {
if (len <= 0)
return; // 避免len等於負值時宣告堆疊陣列當機
// r[]模擬堆疊,p為數量,r[p++]為push,r[--p]為pop且取得元素
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[range.end];
int left = range.start, right = range.end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(arr[left], arr[right]);
}
if (arr[left] >= arr[range.end])
swap(arr[left], arr[range.end]);
else
left++;
r[p++] = new_Range(range.start, left - 1);
r[p++] = new_Range(left + 1, range.end);
}
}
</source>
递归法
<source lang="c" line="1">
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return; // 這是為了防止宣告堆疊陣列時當機
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (arr[left] < mid && left < right)
left++;
while (arr[right] >= mid && left < right)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
if (left)
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
</source>
0x05 简单选择排序
简单选择排序：从序列当众依次选择最小的、次小的……与对应位置的元素进行交换 是不稳定排序算法，时间复杂度为n的平方，空间复杂度为1
void swap(int *a,int *b) //交換兩個變數
{
int temp = *a;
*a = *b;
*b = temp;
}
void selection_sort(int arr[], int len)
{
int i,j;
for (i = 0 ; i < len - 1 ; i++)
{
int min = i;
for (j = i + 1; j < len; j++) //走訪未排序的元素
if (arr[j] < arr[min]) //找到目前最小值
min = j; //紀錄最小值
swap(&arr[min], &arr[i]); //做交換
}
} ### 0x06 堆排序 以完全二叉树的形式存放数据 大堆顶：根节点最大 从最后一个非叶子节点开始调整为大堆顶，调整一次之后，令树根和最后一个叶子元素交换（输出），重新调整 通过不断对根节点进行调整，可以输出从大到小的有序序列
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *b;
*b = *a;
*a = temp;
}
void max_heapify(int arr[], int start, int end) {
//建立父節點指標和子節點指標
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節點指標在範圍內才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個子節點大小，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節點大於子節點代表調整完畢，直接跳出函數
return;
else { //否則交換父子內容再繼續子節點和孫節點比較
swap(&arr[dad], &arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
int i;
//初始化，i從最後一個父節點開始調整
for (i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個元素和已排好元素前一位做交換，再從新調整，直到排序完畢
for (i = len - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
int i;
for (i = 0; i < len; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
0x07 归并排序
先把代码两个一组进行分组，然后在把每一组看成是一个元素重复分组，有序组之间的排序比较简单。
//迭代法
int min(int x, int y) {
return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
int seg, start;
for (seg = 1;= start, mid = min(start + seg, len), high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2)
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
while (start1 < end1)
b[k++] = a[start1++];
while (start2 < end2)
b[k++] = a[start2++];
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
int i;
for (i = 0; i < len; i++)
b[i] = a[i];
b = a;
}
free(b);
}
//递归法
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int len = end - start, mid = (len >> 1) + start;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2)
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
while (start1 <= end1)
reg[k++] = arr[start1++];
while (start2 <= end2)
reg[k++] = arr[start2++];
for (k = start; k <= end; k++)
arr[k] = reg[k];
}
void merge_sort(int arr[], const int len) {
int reg[len];
merge_sort_recursive(arr, reg, 0, len - 1);
}
0x08 基数排序
借助多关键字的思想对单逻辑关键字进行排序，分不同的方向去进行比较
#include<stdio.h>
#define MAX 20
//#define SHOWPASS
#define BASE 10
void print(int *a, int n) {
int i;
for (i = 0; i < n; i++) {
printf("%d\t", a[i]);
}
}
void radixsort(int *a, int n) {
int i, b[MAX], m = a[0], exp = 1;
for (i = 1; i < n; i++) {
if (a[i] > m) {
m = a[i];
}
}
while (m / exp > 0) {
int bucket[BASE] = { 0 };
for (i = 0; i < n; i++) {
bucket[(a[i] / exp) % BASE]++;
}
for (i = 1; i < BASE; i++) {
bucket[i] += bucket[i - 1];
}
for (i = n - 1; i >= 0; i--) {
b[--bucket[(a[i] / exp) % BASE]] = a[i];
}
for (i = 0; i < n; i++) {
a[i] = b[i];
}
exp *= BASE;
#ifdef SHOWPASS
printf("\nPASS : ");
print(a, n);
#endif
}
}
int main() {
int arr[MAX];
int i, n;
printf("Enter total elements (n <= %d) : ", MAX);
scanf("%d", &n);
n = n < MAX ? n : MAX;
printf("Enter %d Elements : ", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("\nARRAY : ");
print(&arr[0], n);
radixsort(&arr[0], n);
printf("\nSORTED : ");
print(&arr[0], n);
printf("\n");
return 0;
}
0x09 算法比较
PS：其中堆排序、归并排序、希尔排序的时间复杂度中对数函数的底都为2
从平均性能而言，快速排序最佳，其需要时间最省，但快速排序在最坏情况下的时间性能不如堆排序和归并排序。在n较大时，归并排序所需时间较堆排序更省，但归并排序所需的辅助存储量最多
简单排序指直接插入排序、冒泡排序和简单选择排序，其中直接插入排序最简单，当序列中的记录“基本有序”或n值较小时，他是最佳的排序方法，因此常将它和其他的排序方法，诸如快速排序、归并排序等结合在一起使用
基数排序的时间复杂度也可以写成O(dn)，因此适用于排序数量很大而关键字较少的序列
从方法的稳定性来看，基数排序是稳定的排序算法，直接插入排序和冒泡排序也是稳定的算法。性能较好的快速排序、堆排序和希尔排序等，都是不稳定排序方法。
归并排序也是一种稳定的排序算法
