数据结构02章

第二章线性表一、逻辑结构定义1、线性表(LinearList)：一个线性表是n个数据元素的有限序列(a1,a2,…ai,ai+1,…an)。1)线性表的长度：n，即线性表中元素的个数；★空的线性表:n=0时;★位序:当n≥1时，元素ai位于表的第i个位置，或称ai是表中第i个元素(i=1,2,…,n)。称i为元素ai在表中的位序。★记录：在稍复杂的线性表中，一个数据元素可由若干数据项组成，常把这样的数据元素称为记录(Record)。含有大量记录的线性表又称文件(File)。2、线性表的特性：★同一线性表中的元素具有相同的特性(即属于同一数据对象)例：(A,B,C,……Z)字母表(6,17,20,50,100,…200)描述某种状态的数值表(r1,r2,r3,…ri-1,ri,ri+1,…rn)n个记录的线性表ri为线性表中的一个元素(这里是一个记录)线性表中的元素之间的关系是一种相邻关系，这种关系可描述为一个序偶的集合，即：R={ai-1,ai|ai-1,aiD2in}线性表(a1,a2,…ai,…an)中，ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，称ai+1是ai的直接后继元素。除i=1外，ai有且仅有一个直接前趋，除i=n外，ai有且仅有一个直接后继。a1是表中第一个元素，an是最后一个元素。线性表的逻辑结构特征：总存在第一个和最后一个元素；除第一个元素以外，每个元素总存在唯一一个直接前驱元素；除最后一个元素以外，每个元素总存在唯一一个直接后继元素。二、ADT线性表的运算1.ADT线性表定义：P19-20页关于线性表上定义的基本运算，主要有构造空表、求表长、取结点、查找、插入、删除等。此外，还有合并两个表，一个表拆成两个表，复制一个表，对线性表排序等运算。三、线性表的存储结构1.顺序存储(静态结构)：用一组地址连续的存储空间依次存放线性表的元素，因而又称“顺序表”。若线性表的每一个元素需占用L个存储单元则有：LOC(ai+1)=LOC(ai)+LLOC(ai)=LOC(a1)+(i-1)*LLOC(a1)是线性表中第一个元素在存储器中的地址，即线性表在存储器中的首地址（或基地址），LOC(ai)是元素ai在存储器中的地址。这种存储方式的特点：逻辑关系上相邻的两个元素在物理位置上也是相邻的。可以随机存取表中任一元素，它的存储位置可用一个简单，直观的公式表示。(因此线性表的顺序存储结构是一随机存取的存储结构)由于高级程序设计语言中的数组类型也有随机存取的特性，因而我们用数组来描述顺序存储结构。//------线性表的动态分配顺序存储结构------#defineLIST_INIT_SIZE100//初始分配存储量typedefstruct{ElemType*elem;//存储空间基址}SqList；在C语言中可用动态分配的一维数组来描述：#defineLISTINCREMENT10//分配增量intlength;//当前长度intlistsize;//当前分配存储量注意：C语言中，数组下标从“0”开始，故若L是SqList类型的顺序表，则表中第i个元素是L.elem[i-1]。以下我们介绍在顺序存储结构下线性表的初始化建空表、插入和删除等算法：构造空顺序表算法：P47StatusInitList_Sq(SqList&L){//构造一个空的线性表LL.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));returnOK;}//InitList_Sqif(!L.elem)exit(OVERFLOW);//存储分配失败插入算法，例①线性表L=(12,13,21,24,28,30,42)L在存储器中的映象为：在i=5的位置前插元素25之后121321242528304212345678插入后1213212428304212345678插入前元素序号一般情况下：在一个有n个元素的线性表中的第i个位置前插入一个元素，需将第n至第i个元素(共n-i+1个)向后移动一个位置，长度由n增加到n+1。设分配给该线性表的数组空间长度超过LIST_INIT_SIZE,则增加分配，增大存储容量。算法如下：P24StatusListInsert_Sq(SqList﹠L,inti,ElemTypee){//在线性表L中第i个元素之前插入元素e,for(p=&(L.elem[L.length-1]);p=q;--p)*(p+1)=*p;*q=e;++L.length;//插入e，表长增1//i的合法值为1=i=ListLength_Sq(L)+1newbase=(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为插入位置returnOK;if(i1||iL.length+1)returnERROR;//i值不合法if(L.length=L.listsize){//当前空间满，增加分配}//ListInsert_Sq②算法分析：算法主要耗费时间在移动元素上，而移动元素的个数与插入元素的位置i相关。由以上算法可见，算法中必须移动的元素个数为(n－i+1)(i=1,2,…,n)若i=n+1,则是最佳情况，即移动次数为0i=1,则是最坏情况，即移动次数为n平均性能：若在线性表中第i个元素之前插入一个元素的概率为Pi,则其平均移动次数为：1n1iiis1)i(nPE不失一般性，设在任一位置插入一个元素的概率相同，即1n1Pi则2n1)i(n1n1E1n1iis平均移动一半元素该算法的时间复杂度记为O(n)删除算法①例：在线性表(10,30,15,20,40,60,25)中删除第4个元素存储映象：1030152040602512345678删除前删除第4个元素1030154060252512345678删除后一般情况下，当在第i个位置删除一个元素时，需将第i+1个至第n个元素(共n-i个)依次向前移动一个位置，长度由n变成n-1。算法如下：P25StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在线性表L中删除第i个元素，并用e返回其值for(++p;p=q;++p)*(p-1)=*p;//后面元素左移－－L.length;//表长减1//i的合法值为1=i=ListLength_Sq(L)p=&(L.elem[i-1]);//p为被删除元素位置returnOK;if(i1||iL.length)returnERROR;//i值不合法}//ListDelete_Sqe=*p;//被删除元素值赋给eq=L.elem+L.length－1;//表尾元素的位置②算法分析:同插入算法，其耗费的时间主要在移动元素上，同理可以分析得,移动元素个数为：n-i(i=1,2,…,n)最佳情况：i=n时0次移动最坏情况：i=1时n－1次移动一般情况下平均性能：n1iidli)(nqE设n1qi则n1idl21ni)(nn1E时间复杂度为：O(n)其中：qi为删除第i个元素的概率。由以上所讨论可见顺序结构的线性表优点：a)无须为表示表中元素之间的逻辑关系增加额外的存储空间；b)随机访问表中元素,其存储位置可用一个直观的公式表示：LOC(ai)=LOC(a1)+(i-1)*L。a)在作插入和删除运算时需移动大量元素(特别是n较大时)b)对要求长度变化较大的线性表，必须按最大空间预先分配，使空间不能充分利用。为了避免以上问题，我们可以采用下面所介绍的链式存储结构来存储线性表。存在的问题：2.链式存储结构(动态结构)(1)线性链表(单向链表)此结构中以结点(Node)描述线性表中的数据元素，即数据域指针域由于链表的每个结点中只包含一个指针域，故又称线性链表（或单向链表）。其中:①数据域存储数据元素信息。指针域(链域)存储数据域中所存元素的直接后继元素在存储器中的地址(位置)。指针域中的值称为“指针”或称为“链”。由此可见，线性表的逻辑关系则由结点的指针域描述(表示),即：指针为数据元素之间的逻辑关系的映象。②n个结点链结成一个链表。线性表(a1,a2,…ai,…an)的链结构可描述为：La1a2aian^……La1a2aian^……或L为头指针(首指针)，存放表中第一个结点(或表头结点)在存储器中的地址。在带表头结点的链表中，L指向表头结点，在不带表头结点的链表中L指向首元结点。表头结点又称哨兵元素。表头结点可不存储任何信息，也可存储表的长度等附加信息。我们取后者。符号：(或NULL)表示空指针空链表：L或L=NULL或L其长度为“0”。例：设有线性表(ZHAO,QIAN,SUN,L1,ZHOU,WU,ZHENG,WANG)用链表表示为：LZHAOQIANSUNL1ZHOUWUZHENGWANG//------线性表的单链表存储结构------typedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;单链表的运算主要有建立单链表(头插法、尾插法和在链表开始结点前附加一个头结点的算法)、查找(按序号和按值)、插入、删除等。以上各运算的平均时间复杂度均为O(n).其主要时间是耗费在查找操作上。由上述可见，单链表可由表头指针唯一确定，在C中用结构体类型指针来描述：★头插法：逆向建立一个带表头结点的链表的算法：P30voidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值，建立带表头结点的单链表Lp—next=L—next;L—next=p;//插入到表头scanf(&p—data);//输入元素值for(i=n;i0;－－i){}//CreateList_LL=(LinkList)malloc(sizeof(Lnode));L—next=NULL;//先建立一个带头结点的空单链表p=(LinkList)malloc(sizeof(Lnode));//生成新结点}★尾插法：正向建立一个带表头结点的链表的算法(补充)：voidCreateList_L(LinkList&L,intn){//顺序输入n个元素的值，建立带表头结点的单链表Lq—next=p;//插入到表头scanf(&p—data);//输入元素值for(i=1;i=n;++i){}//CreateList_LL=(LinkList)malloc(sizeof(Lnode));L—next=NULL;//先建立一个带头结点的空单链表p=(LinkList)malloc(sizeof(Lnode));//生成新结点L—data=n;q=L;//表长存放在头结点的data域p—next=NULL;q=p;}//for在单链表中，每个元素的存储位置都包含在其直接前驱结点的指针域之中。假设p指向第i个元素，则p—next指向第i+1个元素。★查找元素算法：从链表中取第i个元素，必须从头指针出发寻找，因而，单链表是非随机存取结构。★从链表中取第i个元素的算法：P29StatusGetElem_L(LinkListL,inti,ElemType&e){//L为带头结点的单链表的头指针，当第i个元素存在时，//其值赋给e并返回OK，否则返回ERRORe=p—data;//取第i个元素returnOK;while(p&&ji)}//GetElem_L