数据结构第二章教程.ppt

第2章 线性表;线性结构：一个数据元素的有序（次序）且是有限的集合。 ;线性结构的基本特征： ① 存在唯一的一个 “第一个”的数据元素； ② 存在唯一的一个 “最后一个”的数据元素； ③ 除第一个元素外，每个元素均有唯一的一个前驱； ④ 除最后一个元素外，每个元素均有唯一的一个后继。 ;2.1 线性表的类型定义;抽象数据类型线性表的定义;2.2 线性表的顺序表示和实现;以”有序对相邻”表示ai-1,ai 即：LOC(ai) =LOC(ai-1) +l 一个数据元素所占存储量 所有数据元素的存储位置均取决于第一个数据元素的存储位置 LOC(ai) =LOC(a1) +(i-1)×l 基地址 ;顺序映像的C语言描述 ＃define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量 #define LISTINCREMENT 10 //线性表存储空间的分配增量 typedef struct｛ ElemType *elem; //存储空间基址 int length; //当前长度 int listsize; //当前分配的存储容量 // （以sizeof(ElemType)为单位） ｝SqList; //俗称顺序表;线性表的初始化操作 Status InitList_Sq(SqListL) ｛ //构造一个空的线性表 L.elem =(ElemType *) malloc (LIST_INIT_SIZE*sizeof(ElemType) ); if (!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0; //空表长度为0 L.listsize=LIST_INIT_SIZE; //初始存储容量 return OK; ｝//InitList_Sq 在顺序表中，第i个数据元素是L.elem[i-1];线性表操作： ListInsert(L,i,e)的实现： (a1,…,ai-1,ai,…,an)改变为 (a1,…,ai-1,e,ai,…,an);Status ListInsert_Sq(SqList L, int i,ElemType e) ｛ if (i1 ‖iL.length +1) return ERROR; if(L.length =L.listsize) ｛ newbase = (ElemType *) realloc(L.elem,(L.listsize +LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(OVERFLOW); L.elem =newbase; L.listsize + = LISTINCREMENT; ｝ q =(L.elem[i-1]); //q指示插入位置 for(p =(L.elem[L.length-1]);p=q; --p) *(p +1) =*p; //插入位置及之后的元素右移 *q =e; //插入e + +L.length; //表长增1 return OK; ｝//ListInsert_Sq 算法时间复杂度：O(n);考虑平均的情况： 假设在第i个元素之前插入的概率为Pi 则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为： n+1 Eis = ∑pi(n-i+1) i = 1 若假定在线性表中任何一个位置进行插入的概率都是相等的，则移动元素的期望值为： n+1 Eis = ∑(n-i+1) ×1/(n+1) =n/2 i = 1 ;线性表操作： ListDelete(L,i,e)的实现： (a1,…,ai-1,ai, ai+1,…,an)改变为 (a1,…,ai-1, ai+1,…,an) ;Status ListDelete_Sq(SqList L,int i,ElemType e) ｛ //在顺序线性表L中删除第i个元素，并用e返回其值 //i的合法值为1≦i ≦listlength_Sq(L) if (i1 ‖iL.length) return ERROR;