第一章算法 算法是解决某个特定问题的一种方法或一个过程。
算法的特性可行性；确定性；有穷性；输入；输出
数据结构：
简单地说，数据结构(Data Structure)是相互Z间存在一种或多种特定关系的数据元索的集合 数据结构与算法的关系：
确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法； 算法描述语言是一种页向人而非机器的算法描述T具，
其他的描述工具还有：传统流稈图N・S结构化流稈图伪代码
算法设计基本方法列举法归纳法递推法递归法减半递推技术冋溯法
递推关系往往是归纳分析的结果；递归的基础是归纳法；
递归分类頁接递归；间接递归
lvoid hanoi(int n，char A, char B, char C){
2 if(n==l)
3 then move(l, A, C);
4else {5 hanoi(n-l, A, C, B);
6 move(n, A, C);
7 hanoi(n-l, B, A, C);
8}
9}
void trial(int i’int n){
/*进入木函数时，在nxn棋盘前已放置了互不攻击的i-1个棋了。 现从第i行起示示续棋了选择合适的位置，当i>n时，求得合法布 局并输出。*/
if(i > n)
then输出棋盘的当前布局；
else for(j = 1; j v二n; ++j){
在第i行第j列放一个棋了；
if(当前布局合法)trialfi+l, n);
移走第i行第j列的棋子；
}
}
算法时间复杂度指执行算法所需要的计算工作量。
算法空间复杂度指执行算法所需要的内存空间。
算法评价标准正确性可读性健壮性时间与空间效率
第二章数据结构
线性表定义线性表是由 n(n^O)个类型相同的数据元素组成的有限序列。通常表示成
下列形式：L=(al, a2,…J其中L为线性表名称,ai为纟ft成该线性表的数据元素；
顺序存储结构
线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表屮的毎个数据元素。 线性表的逻辑结构与存储结构(物理结构)一致；线性表屮所有元素所占存储空间是连续的 线性表屮各元素按逻辑顺序依次存放；
丿帧序线"性表插入在顺序线性表SL第idx个数据元素之前插入数据元素elem
void insert(SeqList SL, int idx, ElemType elem) {
//检杳是否有剩余空间
if (SL.Iength== MAX_LIST_SIZE)
return ERROR;//检查idx值是否合法
二叉树的基本性质
if (idx<0 11 idx>SL.Iength)
return ERROR;//将线性表笫i个元素Z后的所有元素向后移动
for (j=SL.Iength-l; j>=idx-l; j--)
SL.elems[j+l]=SL.elemsU]；//将新元素的内容放入线性表的第i个位置，
SL.elems[idx-l]=elem;
SL.Iength++;
}
顺序线性表删除删除顺序线性表第idx个数据元素
ElemType delete(SeqList SL, int idx) {// 检测线性表是否为空 if(isEmpty(SL)) return ERROR; //检查idx值是否合法 if (idx<0 11 i>=SL.Iength)
return ERROR; //将欲删除的数据元素内容保存在变量elem屮
ElemType elem=SL.elems[i-l];//将线性表第i+1个元索ZfJ的所有元索向前移动 for (j=i;j<SL」ength;j++)
SL.elems[j-l]=SL.elems[j]；
SL.Iength-;
return elem;
}
链式存储结构链式存储结构指用一-组任意的存储单元(可以连续，也可以不连续)存储
线性表屮的数据元素，而数据元素Z间的逻辑关系由存储结点的指针域来确定。
线性表屮的数据元素在存储单元屮的存放顺序与逻辑顺序不一定一致；访问数据元素时, 只能由头指针进入链表，并通过结点的指针域向后扫描其余结点
链式线性表插入在链表 LL屮第idx个数据元素之前插入数据元素elem int insert(LinkedList LL, int idx, ElemType elem){
lino de* p, s;
int j;//开辟新结点空间
s=(ll no de*)malloc(sizeof(ll no de));
讦(s==NULL) return ERROR;
s->data=elem;
if (idx<0 11 i>length(LL)) return ERROR;// 寻第 i-1 个结点
for (p=LL.headj=O;p&&j<i-l;p=p->next;j++); //W新结点插入到链表中 sonext=p->next; p・>next=s;
return OK;
}
ElemType delete(LinkedList LL, int idx) {
lino de* p, s;
int j；
if (idx<0 11 idx>length(LL)) return ERROR; // 寻第 i-1 个结点 for(p=LL.headj=0;p && j<idx-l;p=p->nextj++); 〃用 s 指向将要删除的结点 s=p->n ext;
ElemType elem=s->data;
p・>n ext=s->n ext;
free(s);
return elem;
}
栈定乂栈是一种特殊的线性表，即LIFO线性表（Last In First Out,示进先出）。栈的特点在 于限泄插入和删除数据元索的操作只能在线性表的一端进行
顺序栈基本操作
入栈
void push(SeqStack SS, ElemType elem) { if (SS.top==MAX_STACK_SIZE-l) ERROR("The Stack is full");
else SS.elems[++SS.top]=elem;
}
出栈
ElemType pop(SeqStack SS) { if(isEmpty(SS))
ERROR("Stack is empty");
else
return SS.p-];
}
栈的链式存储结构
入栈 void push(LinkedStack LS, ELemType elem) {
p=(ls no de*)malloc(sizeof(ls no de));
if(!p)
ERROR(,zOverflow");
else {
p->data=elem;
p-〉n p;
IS.top=p;
}
}
出栈
ElemType pop(LinkedStack LS) {
if(isEmpty(LS))
ERROR(/zStack is empty");
else {
ElemType p->data;
p;
LS.top=p->next;
free(p);
return elem;
}
}
队歹！J定义队列也是一种特殊的线性表，即FIFO线性表(First In First Out,先进先出)
队列特殊性在于限定插入操作在线性表的一端进行，而删除操作在线性表的另一端;插入端 和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端称 为队头,用一个“队头指针”指示；
队列顺序存储
入对操作
void enQueue(SeqQueue SQ, ElemTYpe elem) {
讦((SQ.rear+l)%MAX_QUEUE_SIZE==SQ.front)
ERROR(/zOverfloww);
else {
SQ.rear=(SQ.rear+l)%MAX_QUEUE_SIZE;
SQ.ar]=elem;
}
}
出对操作
ElemType deQueue(SeqQueue SQ) {
if (isEmpty(SQ))
ERROR("Queue is empty");
else {
SQ.front=(Q.front+l)%MAX_QUEUE_SIZE
return SQ.elems[SQ.front];
}
}
队列的链式存储
入对操作
void enQueue(LinkedQueue LQ, ElemType elem) {
s=(lq no de*)malloc(sizeof(lq no de));
ERROR;
s->data=elem;
s->next=NULL;
LQ.rear- >n ext=s;
LQ.rear 二 s;
}
出对操作
ElemType deQueue(LinkedQueue LQ) {
if(isEmpty(LQ))
ERROR;
else {
ElemType elem=LQ.front・>next->data;
s=LQ.fr ont・>n ext;
LQ.fr ont・>n ext=s-〉n ext;
free(s);
return elem;
}
}
二叉树二叉树是另一种树形结构。二叉树与树形结构的区别：每个结点最多有两棵了 树；了树有左右之分；
满二叉树如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。
完全二叉树 有一棵深度为h,具有n个结点的二叉树，若将它与一棵同深度的满二叉 树屮的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树屮的每个结点分别 与满二叉树屮编号为的结点位置一一对应，则称这棵二叉树为完全二叉树。
二叉树基本性质
性质一在二叉树的笫i层上至多有个结点
性质二深度为k的二叉树至多有/ 一 1个结点(k^l).
性质三对于任意一棵二叉树BT,如果度为0的结点个数为nO,度为2的结点个数为n2则 有 n0=n2+l.
性质四具有n个结点的完全二叉树的深度为Llog2nJ+lo其中,llog2nJ的结果是不大TLlog2nJ 的最大整数。
性质五对于有n个结点的完全二叉树屮的所有结点按从上到下，从左到右的顺序进行编号， 则对任意一个结点i (lWiWn),都有：o如果i=l,则结点i是这棵完全二叉树的根， 没有双亲；否则其双亲结点的编号为li/2_l;。如果2i>n,则结点i没有左孩了；否则 其左孩了结点的编号为2i;o如果2i+l>n,则结点i没有右孩了；否则其右孩结点的 编号为2i+l;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。