北工商复习资料-算法讲义

《北工商复习资料-算法讲义》由会员分享，可在线阅读，更多相关《北工商复习资料-算法讲义（19页珍藏版）》请在金锄头文库上搜索。

1、1第一章抽象数据类型(ADT)：是指一个数学模型以及定义在该模型上的一组操作。 数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。数据的逻辑结构：元素间关系的表示，是具体关系的抽象。数据的存储结构：数据结构在计算机内存中的表示顺序存储结构：把逻辑上相邻的元素存储在物理位置相邻的存储单元里，元素间的逻辑关系由存储单元的相邻关系来体现，由此得到的存储表示称为顺序存储结构。链式存储结构：对逻辑上相邻的元素不要求其物理位置相邻，元素之间的逻辑关系通过附设指针字段表示，由此得到的存储表示称为链式存储结构。算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法的五个特性： 1、有穷性:对于

2、任意一组合法输入值，在执行有穷步骤之后一定能结束。2、确定性:组成算法的操作必须清晰无二义性。3、可行性(有效性):组成算法的操作必须能够在计算机上实现。4、有输入:0 个或多个输入；5、有输出 :1 个或多个输出；如何衡量一个正确算法的好坏？衡量的三个尺度： 运行所花费的时间（算法的时间特性） ； 所占用存储空间的大小（算法的空间特性） ； 其它（正确性、可读性、健壮性等） 。 第二章 线性表一、概念1.线性表：线性表是 n 个类型相同数据元素的有限序列，通常记作（a1, a2, a3, , an ） 。2.线性表的顺序存储结构：用一组连续的内存单元依次存放线性表的数据元素。3.线性表的链式

3、存储结构（1）线性链表（单链表）：用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。（2）双向链表：双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。（3）循环链表：循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点。二、算法1线性表的基本运算（不同存储结构下，线性表基本运算的特点）：初始化操作 InitList_Sq( SqList &L)功能：建立空的顺序表 LStatus InitList_Sq(SqList &L)/构造一个空的顺序表 LL.

4、elem=(ElemType* ) malloc (LIST_INIT_SIZE * sizeof(ElemType) );if (! L.elem) exit(OVERFLOW); /存储分配失败L. length=0; /空表长度为 0L.listsize = LIST_INIT_SIZE; /初始存储容量return OK;2 /InitList_Sq销毁操作 DestroyList_Sq(SqList &L)功能：回收为顺序表动态分配的存储空间Status DestroyList_Sq(SqList &L)if(!L.elem) return ERROR; /若表 L 不存在free(

5、L.elem); /若表 L 已存在，回收动态分配的存储空间L.elem = NULL;L.length = 0;L.Listsize = 0;return OK; /DestroyList_Sq置空操作 ClearList_Sq ( SqList &L) 功能：若 L 已存在，重新将其置成空表；Status ClearList_Sq ( SqList &L) if (!L.elem) return ERROR; / 若表 L 不存在L.length = 0; /若表 L 已存在，将 L 置空return OK;/ ClearList_SqStatus ClearList_Sq(SqList

6、*L) free (L.elem);L.elem =( ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem) exit(OVERFLOW);L.length = 0;L.Listsize = LIST_INIT_SIZE;return OK;取元素操作 GetElem_Sq(SqList L,int i, ElemType &e )功能：将顺序表中第 i 个元素赋值给 eStatus GetElem_Sq ( SqList *L, int i, ElemType &e ) if (i L.length -1) return E

7、RROR; / i 非法e = L.elem i-1 ; / 将顺序表中第 i 个元素赋值给 ereturn OK; / GetElem_Sq 插入操作 ListInsert_Sq ( &L, i, e )功能：在顺序表 L 的第 i 个元素之前插入一个新元素 e;Status ListInsert_Sq(SqList &L, int i , ElemType e) /在顺序表 L 中第 i 个位置之前插入新的元素 e,/ i 的合法值为 1iL.length+1,当 i =L.length+1 时, e 插在表尾if (iL.length+1) return ERROR; / i 值不合法i

8、f (L.length=L.listsize) return ERROR; /顺序表已满for ( j=L.length-1 ; j= i-1; -j) L.elemj+1= L.elem j; /插入位置及之后的元素后移一个位置L.elemi-1 =e; /插入 e3+L.length; /表长增 1return OK; /ListInsert_Sq删除操作 ListDelete_sq (SqList &L, int i, ElemType &e ) 功能：删除顺序表 L 的第 i 个元素，并用 e 返回Status ListDelete_Sq(SqList &L, int i, ElemT

9、ype &e)/在顺序表 L 中删除第 i 个元素，并用 e 返回其值/ i 的合法值为 1iL.length，/ 表空 L.length=0 则 i L.lengthif (iL.length) return ERROR; / i 值不合法或表空e = L.elemi-1; / 被删除元素的值赋给 efor ( j= i; jdata=e;s-prior=p-prior; p-prior-next=s; / 完成插入图示中的s-next=p; p-prior=s; /完成插入图示中的return OK;/LinstInsert_DuL2）删除操作算法Status ListDelete_DuL

10、(DuLinkList &L, int i, ElemType &e)/删除带头结点的双链循环线性表 L 的第 i 个元素，i 的合法值为 1i表长if(!p=GetElemP_DuL(L,i) /在 L 中确定第 i 个元素的位置指针 preturn ERROR; /p=NULL，第 i 个元素不存在e = p-data;p-prior-next = p-next; /完成删除图示中的 p-next-prior = p-prior; /完成删除图示中的 free(p); 5return OK;/LinstDelete_DuL第三章一、栈1、栈是限定仅能在表尾一端进行插入、删除操作的线性表。2

11、、栈的元素具有后进先出的特点。3、栈顶元素的位置由一个称为栈顶指针的变量指示，进栈、出栈操作要修改栈顶指针。 栈空的条件 s-top=s-base 栈满的条件s-top-s-base=stacksize 二、顺序栈基本操作的算法空栈：top=0满栈：top=MAXN1、初始化操作 InitStack(SqStack &S)功能：建一个空栈 S。Status InitStack(SqStack &S)/构造一个空栈 SS.base = (SElemType * )malloc(STACK_INIT_SIZE sizeof(SElemType);/为顺序栈动态分配存储空间if (! S. base

12、) exit(OVERFLOW); /存储分配失败S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; /InitStack_Sq2、销毁栈操作 DestroyStack(SqStack &S )功能：销毁一个已存在的栈。Status DestroyStack( SqStack &S)if (!S.base) return ERROR; /若栈未建立(尚未分配栈空间) free (S.base); / 回收栈空间S.base = S.top = NULL;S.stacksize = 0;return OK; / DestroyStack

13、_Sq3、出栈操作 Pop(SqStack &S, SElemType &e )功能：栈顶元素退栈，并用 e 返回。Status GetTop(SqStack S,SElemType &e)/ 若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR if(S.top=S.base) return ERROR;e=*(S.top-1);return OK;6Status Pop (SqStack &S, SElemType &e) / 若栈不空，则删除 S 的栈顶元素，/ 用 e 返回其值，并返回 OK；/ 否则返回 ERRORif (S.top = S.base) ret

14、urn ERROR;e = *-S.top;return OK;4、进栈操作 Push(SqStack &S, SElemType e)功能：元素 e 进栈; Status Push(SqStack &S, SElemType e) /将元素 e 插入栈成为新的栈顶元素 if (S.top - S.base = S.stacksize) /栈满，追加存储空间S.base= (SElemType * )realloc(S.base,(S.stacksize +STACKINCREMENT) * sizeof(SElemType); if (! S. base) exit (OVERFLOW);

15、/存储分配失败S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e; /元素 e 插入栈顶，修改栈顶指针return OK; /Push三、队列 1、队列是限定仅能在表尾一端进行插入，表头一端进行删除操作的线性表；2、队列中的元素具有先进先出的特点；队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示。 3、入队操作要修改队尾指针,出队操作要修改队头指针。空：Q.front = Q.rear满: (Q.rear+1)% MAXQSIZE = Q.front 四、循环队列队列的顺序存储和实现插入： 尾指针增 1 Q.rear+;删除： 头指针增 1 Q.front+。1、初始化操作 InitQueue_Sq(SqQueue &Q) 参数：Q 是存放队列的结构变量；功能：建一个空队列 Q；S