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

《北工商复习资料-算法讲义》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、类问题而规定的一个有限长的操作序列。算法的五个特性：1、有穷性:对于任意一组合法输入值，在执行有穷步骤Z后一定能结束。2、确定性:组成算法的操作必须清晰无二义性。3、可行性(有效性)：组成算法的操作必须能够在计算机上实现。4、有输入:0个或多个输入；5、有输出：1个或多个输出；如何衡量一个正确算法的好坏?衡量的三个尺度：•运行所花费的时间(算法的时间特性):•所占用存储空间的大小(算法的空间特性):•其它(正确性、可读性、健壮性等)。第二章线性表一、概念1•线性表：线性表是n个类型相同数据元素的有限序列，通常记作(al

3、,a2,a3,an)。2.线性表的顺序存储结构：用一组连续的内存单元依次存放线性表的数据元素。3•线性表的链式存储结构(1)线性链表(单链表)：用一组任意的存储单元存储线性表屮的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。(2)双向链表：双向链表屮，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。(3)循环链表：循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点。二、算法1.线性表的基本运算(不同存储结构下，线性

4、表基本运算的特点)：①初始化操作TnitList_Sq(SqList&L)功能：建立空的顺序表LStatusInitList_Sq(SqList&L){//构造一个空的顺序表LL.elem=(ElemType*)malloc(LIST_TNIT_STZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length^;〃空表长度为0L.listsize=L1ST_IN1T_S1ZE;//初始存储容量returnOK;}//TnitListSq①销毁操作Dest

5、royListSq(SqList&L)功能：冋收为顺序表动态分配的存储空间StatusDestroyListSq(SqList&L){if(!L.elem)returnERROR;//若表L不存在freed,elem);//若表L己存在，冋收动态分配的存储空间L.elem二NULL;L.length=0;L.Listsize=0;returnOK;}//DestroyList_Sq②置空操作ClearListSq(SqList&L)功能：若L已存在，重新将其置成空表；StatusClearListSq(SqList&L

6、){if(!L.elem)returnERROR;//若表L不存在L.length=0;//若表L己存在，将L置空returnOK;}//ClearList_SqStatusClearList,Sq(SqList*L){free(L.elem);L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.e1em)exit(OVERFLOW);L.length=0;L.Listsize=LIST_INIT_SIZE;returnOK;}③取元素操作Ge

7、tElem_Sq(SqListL,inti,ElemType&e)功能：将顺序表中第i个元素赋值给eStatusGetElemSq(SqList*L,inti,ElemType&e){if((i<1)

8、

9、(i>L.length-1))returnERROR;//i非法e=L.elem[i-1];//将顺序表屮第i个元素赋值给ereturnOK;}//GetElemSq④插入操作ListInsert_Sq(&L,i,e)功能：在顺序表L的第i个元素之前插入一个新元素e;StatusListlnsert^Sq(SqList

10、&L,inti,ElemTypee){〃在顺序表L中第i个位置之前插入新的元素e,//i的合法值为1WiWL.length+1,当i=L.length+1吋，e插在表尾if(i

11、

12、i>L.length+1)returnERROR;//i值不合法if(L.length>=L.listsize)returnERROR;//顺序表己