数据结构第二章课件

第2章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4一元多项式的表示及相加第一章12/8/20221线性结构：一个数据元素的有序（次序）且是有限的集合。12/8/20222线性结构的基本特征：①存在唯一的一个“第一个”的数据元素；②存在唯一的一个“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一的一个前驱；④除最后一个元素外，每个元素均有唯一的一个后继。12/8/20223抽象数据类型线性表的定义ADTList{

数据对象：

D={ai|ai∈ElemSet,i=1,2,…,n,n≥0}

｛n为线性表的表长；n=0时的线性表为空表｝数据关系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,3,…,n}｛设线性表为(a1,a2,…ai,…an),称i为ai在线性表中的位序。｝12/8/202252.2线性表的顺序表示和实现线性表的顺序表示：用一组地址连续的存储单元依次存放线性表中的数据元素。

a1a2…ai-1ai…an线性表的起始地址称做线性表的基地址12/8/20226以”有序对相邻”表示<ai-1,ai>即：LOC(ai)=LOC(ai-1)+l一个数据元素所占存储量所有数据元素的存储位置均取决于第一个数据元素的存储位置LOC(ai)=LOC(a1)+(i-1)×l基地址12/8/20227顺序映像的C语言描述＃defineLIST_INIT_SIZE100

//线性表存储空间的初始分配量#defineLISTINCREMENT10

//线性表存储空间的分配增量typedefstruct｛ElemType*elem;//存储空间基址intlength;//当前长度intlistsize;//当前分配的存储容量//（以sizeof(ElemType)为单位）｝SqList;//俗称顺序表12/8/20228线性表操作：ListInsert(&L,i,e)的实现：(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)a1a2…ai-1ai…ana1a2…ai-1eai…an12/8/202210考虑平均的情况：假设在第i个元素之前插入的概率为Pi则在长度为n的线性表中插入一个元素所需移动元素次数的期望值为：

n+1Eis

=∑pi(n-i+1)i=1若假定在线性表中任何一个位置进行插入的概率都是相等的，则移动元素的期望值为：

n+1Eis

=∑(n-i+1)×1/(n+1)=n/2i=112/8/202212StatusListDelete_Sq(SqList&L,inti,ElemType&e)｛//在顺序线性表L中删除第i个元素，并用e返回其值//i的合法值为1≦i≦listlength_Sq(L)if(i<1‖i>L.length)returnERROR;

//删除位置不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的值for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后左移的元素--L.length;//表长减1returnOK;｝//ListDelete_Sq此算法的时间复杂度为：O(n)12/8/202214考虑平均的情况：假设删除第i个元素的概率为qi则在长度为n的线性表中删除一个元素所需移动元素次数的期望值为：

nEdl

=∑qi(n-i)i=1若假定在线性表中任何一个位置进行删除的概率都是相等的，则移动元素的期望值为：

nEdl

=∑(n-i)×1/n=(n-1)/2

i=112/8/202215线性表操作：LocateElem(L,e,compare())的实现：intLocateElem_Sq(SqlistL,ElemTypee,Status(*compare)(ElemType,ElemType))｛i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while((i<=L.length)&&!(*compare)(*p++,e))i++;if(i<=l.length)returni;elsereturn0;｝//LocateElem_Sq基本操作：进行两个元素之间的比较算法时间复杂度：O(L.length)12/8/202216线性表的顺序存储结构优缺点优点：1.可以随机存取表中任一元素；2.表长是显值；缺点：在进行插入和删除操作时，需移动大量元素。12/8/2022172.3线性表的链式表示和实现一.单链表用一组任意的存储单元存储线性表的数据元素。以元素（数据元素的映像）+指针（指示直接后继元素的存储位置）=结点（表示数据元素）以“结点的序列”表示线性表—称作链表以线性表中第一数据元素a1的存储地址作为线性表的地址，称做线性表的头指针。a1a2an∧……12/8/202218三.单链表操作的实现线性表的操作：GetElem(L,i,&e)在链表中的实现：基本操作：使指针p始终指向线性表中第j个数据元素12/8/202220StatusGetElem_L(LinkListL,inti,ElemType&e)｛//L为带头结点的单链表的头指针

p=Lnext;j=1;

//初始化，P指向第一个结点，j为计数器while(p&&j<i)｛ p=pnext;++j;｝//顺指针向后查找，直到p指向第i个元素或p为空if(!p‖j>i)retunERROR;//第i个元素不存在e=pdata;returnOK;｝//GetElem_L算法的时间复杂度为：O(n)12/8/202221StatusListInsert_L(LinkList&L,inti,ElemTypee)｛

p=L;j=0;while(p&&j<i-1)｛p=pnext;++j;｝if(!p‖j>i-1)returnERROR;s=(LinkList)malloc(sizeof(LNode));//生成新结点sdata=e;snext=pnext;pnext=s;//插入L中returnOK;｝//ListInsert_L时间复杂度：O(n)12/8/202223线性表的操作：ListDelete(&L,i,&e)在链表中的实现：基本操作：找到线性表中第i－1个结点，修改其指向后继的指针有序对<ai-1,ai>和<ai,ai+1>改变为<ai-1,ai+1>12/8/202224单链表的建立：CreatList(&L,n):从“空表”初始状态起，依次建立各元素结点，并逐个插入链表。12/8/202226voidCreateList_L(LinkList&L,intn)｛L=(LinkList)malloc(sizeof(LNode));Lnext=NULL;

//先建立一个带头结点的单链表for(i=n;i>0;--i)｛p=(LinkList)malloc(sizeof(LNode));scanf(&pdata);//输入元素值pnext=Lnext;Lnext=p;//插入到表头｝｝//CreateList_L时间复杂度：O(n)12/8/202227用上述定义的单链表实现线性表的操作，存在的问题1.单链表的表长是一个隐含的值；2.在单链表的最后一个元素最后插入元素时，需遍历整个链表；3.在链表中，元素的“位序”概念淡化，结点的“位置”概念强化。改进链表的设置：1.增加“表长”、“表头指针”和“表尾指针”三个数据域；2.将基本操作由”位序”改为“指针”12/8/202228Pnextprior=p=ppriornexta1ai

ai