资源描述：
《ds_2010_22数据结构课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章线性表(2)《数据结构》主讲：林华《数据结构》主讲：林华线性表的顺序表示：用一组地址连续的存储单元依次存放线性表中的数据元素a1a2……ai-1ai……an线性表的起始地址称作线性表的基地址《数据结构》主讲：林华以“存储位置相邻”表示有序对>即：LOC(ai)=LOC(ai-1)+C一个数据元素所占存储量↑所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(aLOC(a1))+(i-1)×C↑基地址《数据结构》主讲：林华由于只要确定了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的存储
2、结构。《数据结构》主讲：林华顺序存储结构的线性表称为顺序表顺序表的特点：以元素在计算机内““物理位置相邻””来表示线性表中数据元素之间逻辑关系上的相邻。《数据结构》主讲：林华在高级程序设计语言中，数组类型具有随机存储的特性。通常用一维数组来描述数据结构中的顺序存储结构《数据结构》主讲：林华动态分配顺序存储结构的CC语言描述#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址,elem中存放ElemType型数据的基址intl
3、ength;//当前长度(数据元素的个数)intlistsize;//当前分配的存储空间大小//(以sizeof(ElemType)为单位)}SqList;//俗称顺序表《数据结构》主讲：林华线性表的基本操作在顺序表中的实现InitList_Sq(&LInitList_Sq(&L)//)//结构初始化LocateElem_Sq(LLocateElem_Sq(L,e,compare())//,e,compare())//查找ListInsert_Sq(&LListInsert_Sq(&L,i,e)//,i,e)//插入元素ListDelete_Sq(&LListDelete_Sq(&L,i)/
4、/,i)//删除元素《数据结构》主讲：林华线性表操作InitList_Sq(&LInitList_Sq(&L))结构初始化的实现：首先分析::（1）申请空间（2）空表长度为0（3）初始存储容量为LIST_INIT_SIZE《数据结构》主讲：林华StatusInitList_Sq(SqList&L){//构造一个空的线性表L.elem=(ElemType*)malloc(LIST_INIT_SIZE∗sizeof(ElemType));//将这片连续空间的基址强制转换为ElemType型指针赋给L.elemif(!L.elem)exit(OVERFLOW);//存储分配失败,则返回(OVERF
5、LOW)L.length=0;//否则设置空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量为LIST_INIT_SIZE个分配单位returnOK;算法时间复杂度时间复杂度：O(1)O(1)}//InitList_Sq《数据结构》主讲：林华线性表操作LocateElem_Sq(LLocateElem_Sq(L,e,compare()),e,compare())在顺序表LL中查找第11个值与ee满足判定条件compare()compare()的数据元素,,若找到,,则返回其在LL中的位序。否则返回00。查找定位的实现：《数据结构》主讲：林华首先分析::例如：顺序
6、表L.listsizeL.elem2375413854621723754138546217ppppppppppL.lengthppii112233441881234812348可见，基本操作是：将顺序表中的元素e=e=38385050逐个和给定值e相比较。《数据结构》主讲：林华intLocateElem_Sq(SqListL,ElemTypee,算法的时间复杂度为：Status(*compare)(ElemType,ElemType)){O(ListLength(L))//在顺序表中查询第一个满足判定条件的数据元素，//若存在，则返回它的位序，否则返回0//Status(*compare)(
7、ElemType,ElemType)整体是LocateElem_Sq的一个形参,将函数指针变量compare作为形参，compare中放的是函数的入口地址。函数需要两个ElemType型参数，函数自身返回Status型结果。i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;//(*comp
