搜索
第一章算法算法是解决某个特定问题的一种方法或一个过程。算法的特性可行性；确定性；有穷性；输入；输出数据结构：简单地说，数据结构(DataStructure)是相互之间存在一种或多种特定关系的数据元素的集合数据结构与算法的关系：确定使用的数据结构，并在此基础上设计对此数据结构实施各种操作的算法;算法描述语言是一种面向人而非机器的算法描述工具，其他的描述工具还有：传统流程图N-S结构化流程图伪代码算法设计基本方法列举法归纳法递推法递归法减半递推技术回溯法递推关系往往是归纳分析的结果;递归的基础是归纳法;递归分类直接递归;间接递归1voidhanoi(intn,charA,charB,charC){2if(n==1)3thenmove(1,A,C);4else{5hanoi(n-1,A,C,B);6move(n,A,C);7hanoi(n-1,B,A,C);8}9}voidtrial(inti,intn){/*进入本函数时，在nxn棋盘前已放置了互不攻击的i-1个棋子。现从第i行起后后续棋子选择合适的位置，当in时，求得合法布局并输出。*/if(in)then输出棋盘的当前布局;elsefor(j=1;j=n;++j){在第i行第j列放一个棋子;if(当前布局合法)trial(i+1,n);移走第i行第j列的棋子;}}算法时间复杂度指执行算法所需要的计算工作量。算法空间复杂度指执行算法所需要的内存空间。算法评价标准正确性可读性健壮性时间与空间效率‰第二章数据结构线性表定义线性表是由n(n≥0)个类型相同的数据元素组成的有限序列。通常表示成下列形式：L=(a1,a2,…,)其中L为线性表名称,ai为组成该线性表的数据元素;顺序存储结构线性表的顺序存储结构是指用一组连续的存储单元依次存储线性表中的每个数据元素。线性表的逻辑结构与存储结构(物理结构)一致;线性表中所有元素所占存储空间是连续的线性表中各元素按逻辑顺序依次存放;顺序线性表插入在顺序线性表SL第idx个数据元素之前插入数据元素elemvoidinsert(SeqListSL,intidx,ElemTypeelem){//检查是否有剩余空间if(SL.length==MAX_LIST_SIZE)returnERROR;//检查idx值是否合法if(idx0||idxSL.length)returnERROR;//将线性表第i个元素之后的所有元素向后移动for(j=SL.length-1;j=idx-1;j--)SL.elems[j+1]=SL.elems[j];//将新元素的内容放入线性表的第i个位置，SL.elems[idx-1]=elem;SL.length++;}顺序线性表删除删除顺序线性表第idx个数据元素ElemTypedelete(SeqListSL,intidx){//检测线性表是否为空if(isEmpty(SL))returnERROR;//检查idx值是否合法if(idx0||i=SL.length)returnERROR;//将欲删除的数据元素内容保存在变量elem中ElemTypeelem=SL.elems[i-1];//将线性表第i+1个元素之后的所有元素向前移动for(j=i;jSL.length;j++)SL.elems[j-1]=SL.elems[j];SL.length--;returnelem;}链式存储结构链式存储结构指用一组任意的存储单元(可以连续，也可以不连续)存储线性表中的数据元素,而数据元素之间的逻辑关系由存储结点的指针域来确定。线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；‰访问数据元素时，只能由头指针进入链表，并通过结点的指针域向后扫描其余结点链式线性表插入在链表LL中第idx个数据元素之前插入数据元素elemintinsert(LinkedListLL,intidx,ElemTypeelem){llnode*p,s;intj;//开辟新结点空间s=(llnode*)malloc(sizeof(llnode));if(s==NULL)returnERROR;s-data=elem;if(idx0||ilength(LL))returnERROR;//寻找第i-1个结点for(p=LL.head,j=0;p&&ji-1;p=p-next;j++);//将新结点插入到链表中s-next=p-next;p-next=s;returnOK;}链式线性表删除删除链表LL中的第idx个数据元素，并返回其值ElemTypedelete(LinkedListLL,intidx){llnode*p,s;intj;if(idx0||idxlength(LL))returnERROR;//寻找第i-1个结点for(p=LL.head,j=0;p&&jidx-1;p=p-next,j++);//用s指向将要删除的结点s=p-next;ElemTypeelem=s-data;p-next=s-next;free(s);returnelem;}栈定义栈是一种特殊的线性表，即LIFO线性表(LastInFirstOut,后进先出)。栈的特点在于限定插入和删除数据元素的操作只能在线性表的一端进行顺序栈基本操作入栈voidpush(SeqStackSS,ElemTypeelem){if(SS.top==MAX_STACK_SIZE-1)ERROR(“TheStackisfull”);elseSS.elems[++SS.top]=elem;}出栈ElemTypepop(SeqStackSS){if(isEmpty(SS))ERROR(“Stackisempty”);elsereturnSS.elems[SS.top--];}栈的链式存储结构入栈voidpush(LinkedStackLS,ELemTypeelem){p=(lsnode*)malloc(sizeof(lsnode));if(!p)ERROR(“Overflow”);else{p-data=elem;p-next=LS.top;lS.top=p;}}出栈ElemTypepop(LinkedStackLS){if(isEmpty(LS))ERROR(“Stackisempty”);else{ElemTypeelem=LS.top-data;p=LS.top;LS.top=p-next;free(p);returnelem;}}队列定义队列也是一种特殊的线性表，即FIFO线性表(FirstInFirstOut,先进先出)队列特殊性在于限定插入操作在线性表的一端进行，而删除操作在线性表的另一端;插入端和删除端都是浮动的。通常我们将插入端称为队尾，用一个“队尾指针”指示；而删除端称为队头，用一个“队头指针”指示;队列顺序存储入对操作voidenQueue(SeqQueueSQ,ElemTYpeelem){if((SQ.rear+1)%MAX_QUEUE_SIZE==SQ.front)ERROR(“Overflow”);else{SQ.rear=(SQ.rear+1)%MAX_QUEUE_SIZE;SQ.elems[SQ.rear]=elem;}}出对操作ElemTypedeQueue(SeqQueueSQ){if(isEmpty(SQ))ERROR(“Queueisempty”);else{SQ.front=(Q.front+1)%MAX_QUEUE_SIZEreturnSQ.elems[SQ.front];}}队列的链式存储入对操作voidenQueue(LinkedQueueLQ,ElemTypeelem){s=(lqnode*)malloc(sizeof(lqnode));if(!s)ERROR;s-data=elem;s-next=NULL;LQ.rear-next=s;LQ.rear=s;}出对操作ElemTypedeQueue(LinkedQueueLQ){if(isEmpty(LQ))ERROR;else{ElemTypeelem=LQ.front-next-data;s=LQ.front-next;LQ.front-next=s-next;free(s);returnelem;}}二叉树二叉树是另一种树形结构。二叉树与树形结构的区别：‰每个结点最多有两棵子树;‰子树有左右之分;满二叉树如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。完全二叉树‰有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1-n的结点位置一一对应，则称这棵二叉树为完全二叉树。二叉树基本性质性质一在二叉树的第i层上至多有2i−1个结点(i≥1).性质二深度为k的二叉树至多有2k−1个结点(k≥1).性质三对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2则有n0=n2+1.性质四具有n个结点的完全二叉树的深度为⎣log2n⎦+1。其中，⎣log2n⎦的结果是不大于⎣log2n⎦的最大整数。性质五对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i(1≤i≤n)，都有：o如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为⎣i/2⎦;o如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i;o如果2i+1n，则结点i没有右孩子；否则其右孩结点的编号为2i+1;图定义图是一个二元组V,E。其中V是顶点的有穷非空集合，E是两个顶点之间关系的集合基本概念完全图具有n(n-1)条弧的有向图称作有向完全图;‰具有n(n-1)/2条边的无向图称作无向完全图;路径长度路径上边或弧的数目;简单路径顶点没有重复出现的路径;创建有向图邻接表voidcreateGraph(AdjListadj,intn){//初始化顶点数组for(i=0;in;i++){scanf(&adj[i].adjvex);adj[i].firstarc=NULL;}//输入弧scanf(&i,&j);while(i){s=(edgenode*)malloc(sizeof(edgenode));//创建新的弧结点s-adgvex=j-1;s-nextarc=adj[i-1].firstarc;//将新的弧结点插入到相应的位置adj[i-1].firstarc=s;//输入下一条弧scanf(&i,&j);}}图的遍历从图的某一顶点出发访遍图中所有顶点，且使每一顶点仅被访问一次，这一过程称为图的遍历。两种遍历方式‰深度优先遍历树的先根遍历的扩展‰广度优先遍历树的层次遍历的扩展第三章查找查找‰在数据元素集合中查找满足某种条件的数据元素的过程称为查找;顺序查找基本思想将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，顺序表的顺序查找描述/*设置了监视哨的顺序表查找，查找关键字值等于指定值k的记录，*若查找成功，返回记录存放位置的下标值，否则返回0。*/intsearch(SeqListSL，KeyTypek){i=n;//设置监视哨SL[0].key=k;while(SL[i].key!=k)i--;returni;}链表的顺序查找描述/**LL为带头结点链表的头指针，查找关键字值等于k的记录，*查找成功，返回指向找到的结点的指针，查找失败返回空指针。*/llnode*search(LinkedListLL,KeyTypek){p=LL-next;while((p!=NULL)&&(p-key!=k))p=p-next;returnp;}折半查找描述intsearch(SeqListSL,KeyTypek){//置初始查找范围的低、高