资源描述：
《隐藏信息检测与还原技术ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、Ch.2线性表12§2.1线性表的逻辑结构线性表由n(n≥0)个结点a1,…,an组成的有限序列记作：L=(a1,a2,…,an)属性：长度n，结点数目n=0时为空表ai：一般是同一类型3§2.1线性表的逻辑结构逻辑特征当L≠Ф时，有且仅有1个开始结点a1和1个终端结点an，a1仅有一直接后继，an仅有一直接前驱内部结点ai（2≤i≤n-1）均有一直接前驱ai-1和一直接后继ai+1结点之间的逻辑关系是由位置次序决定的，ai处在表的第i个位置。该关系为线性(全序)的，故称L为线性表。4§2.1线性
2、表的逻辑结构举例英文字母表(A,B,…,Z)扑克牌点数(2,3,…,10,J,Q,K,A)学生成绩表等ai----抽象符号。具体应用可能是一个结构类型的对象基本运算InitList(L),ListLength(L),GetNode(L,i)…等复杂运算可通过基本运算去构造5§2.2线性表的顺序存储结构§2.2.1顺序表定义：将线性表中结点按逻辑次序依次存储在一组地址连续的存储单元里。由此存储的L称为顺序表。地址计算设结点大小为l个单元，其中第1个单元为该结点地址Loc(ai)=Loc(a1)+(i
3、-1)*lL的基地址§2.2.1顺序表特征随机存储只需存储结点。无需用辅助空间存储逻辑关系。但空闲大小不易确定，易浪费空间静态分配（当用向量实施时）亦可动态申请空间，但copy成本大（扩充表时）。67§2.2.1顺序表实现：用向量实现#defineListSize100;//假定typedefintDataType;//依具体使用定typedefstruct{DataTypedata[ListSize];//存放结点intlength;//当前表长n}Seqlist;8§2.2.2顺序表上实现的基
4、本运算1.插入基本思想在L的第i个位置上插入一新结点x(1≤i≤n+1)。x(a1,…,ai-1,ai,ai+1,…,an)→(a1,…,ai-1,x,ai,…,an+1)为保持结点的物理顺序和逻辑顺序一致，须：将an,…,ai依次后移1位，空出ith位置插入x表长加19§2.2.2顺序表上实现的基本运算算法voidInsertList(SeqList*L,DataTypex,inti){intj;//注意c数组1st位置的下标为0.ai的位置是data[i-1].if(i<1
5、
6、i>L->len
7、gth+1)//1≤i≤n+1是合法插入位置Error(“Positionerror!”);if(L->length>=ListSize)Error(“Overflow”);//溢出for(j=L->length-1;j>=i-1;j--)L->data[j+1]=L->data[j];//结点后移L->data[i-1]=x;//插入xL->length++;//长度加1};10§2.2.2顺序表上实现的基本运算分析循环后移，移动节点数为n-i+1，时间与相关最好情况：当i=n+1，不移动O(1
8、)常数时间解释O(n0)与n无关最坏情况：当i=1，全部后移O(n)平均性能设任何合法位置上插入的概率相等：(位置i插入的概率)当位置i确定时，后移次数亦确定：n-i+1.故表中平均移动结点为：即插入时，平均移动表中一半结点11§2.2.2顺序表上实现的基本运算2.删除基本思想在L中删除ith结点(1≤i≤n)。(a1,…,ai-1,ai,ai+1,…,an)→(a1,…,ai-1,ai+1,…,an-1)为保持物理与逻辑顺序一致，须：前移：将ai+1,…,an依次前移1位，填补删除ai留下的空间
9、表长减112§2.2.2顺序表上实现的基本运算算法voidDeleteList(SeqList*L,inti){intj，n=L->length;if(i<1
10、
11、i>n)Error(“Positionerror!”);//非法位置for(j=i;j<=n-1;j++)L->data[j-1]=L->data[j];//结点后移L->length--;//长度减1};13§2.2.2顺序表上实现的基本运算分析前移次数与n和i相关，移动节点数n-i。最好情况：当i=n，不移动O(1)最坏情况：当i=1
12、，前移n-1次O(n)平均性能：14§2.3线性表的链式存储结构顺序表缺点：移动节点，不利于动态插入和删除优点：随机存取，得到第i个结点的时间为O(1)与表长和位置无关§2.3.1单链表（线性链表）存储方法用一组任意存储单元来存放结点（可连续，亦可不连续）为表示逻辑关系，须存储后继或前驱信息15§2.3.1单链表（线性链表）结点结构数据域指针域（链域）next指向该结点的后继（的地址）表示开始结点无前驱，用头指针表示终端结点无后继，next域为空（NULL）16§2.3.1单链表（
