会计学2第2章线性表2.1线性表的逻辑结构定义：一个线性表是n个数据元素(yuánsù)的有限序列类C描述建空表，求长度，定位，插入等基本操作利用基本操作实现复杂操作如线性表合并P20例2－1线性表合并union算法(suànfǎ)2.1ListLength，GetElem，LocateElem，ListInsert时间复杂度forXLocateElem即O（ListLength(Lb)xListLength(La)）P21例2－2有序表合并到第三个表MergeList算法(suànfǎ)2.2时间复杂度O（ListLength(Lb)+ListLength(La)）672.2线性表的顺序存储结构顺序表：定义：用一组地址连续的存储单元存放一个(yīɡè)线性表叫~元素地址计算方法：LOC(ai)=LOC(a1)+(i-1)*LLOC(ai+1)=LOC(ai)+L其中：L—一个(yīɡè)元素占用的存储单元个数LOC(ai)—线性表第i个元素的地址P22图2.2特点：实现逻辑上相邻—物理地址相邻实现随机存取实现：可用C语言的一维数组实现插入定义(dìngyì)：线性表的插入是指在第i（1in+1）个元素之前插入一个新的数据元素x，使长度为n的线性表11内存算法时间复杂度T(n)设Pi是在第i个元素之前插入一个元素的概率(gàilǜ)，则在长度为n的线性表中插入一个元素时，所需移动的元素次数的平均次数为：删除(shānchú)定义：线性表的删除(shānchú)是指将第i（1in）个元素删除(shānchú)，使长度为n的线性表15内存算法评价设Qi是删除(shānchú)第i个元素的概率，则在长度为n的线性表中删除(shānchú)一个元素所需移动的元素次数的平均次数为：顺序存储结构的优缺点优点逻辑(luójí)相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充2.3线性表的链式存储结构特点：用一组任意(rènyì)的存储单元存储线性表的数据元素利用指针实现了用不相邻的存储单元存放逻辑上相邻的元素每个数据元素ai，除存储本身信息外，还需存储其直接后继的信息结点数据域：元素本身信息指针域：指示直接后继的存储位置实现(shíxiàn)h单链表的基本运算(yùnsuàn)取元素：GetElem_LP29算法2.824StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值p=L;j=0;while(p->next&&j<i-1){//寻找第i个结点，并令p指向(zhǐxiànɡ)其前趋p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;//删除并释放结点e=q->data;free(q);returnOK;}//ListDelete_LvoidCreateList_L(LinkList&L,intn){//算法2.11//逆位序输入n个元素的值，建立带表头结点(jiédiǎn)的单链线性表LL=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点(jiédiǎn)的单链表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点(jiédiǎn)scanf(&p->data);//输入元素值p->next=L->next;L->next=p;//插入到表头}}//CreateList_L27单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外(éwài)存储空间不能随机存取，查找速度慢循环链表(circularlinkedlist)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发(chūfā)均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p->next=NULL循环链表p或p->next=H双向链表（doublelinkedlist）单链表具有单向性的缺点(quēdiǎn)结点定义32ListInsert_DuL1.s->prior=p->prior;2.p->prior->next=s;3.s->next=p;4.p->prior=s;342.4线性表的应用(yì