数据结构第2章复习:1.算法及分析----渐近时间复杂度2.线性表的定义ADTList{数据对象:D={ai
|ai∈ElemSet,i=1,2,……,nn>=0}数据关系:R={|ai-1,ai∈D,i
=2,……n}基本操作:（1）InitList(&L)（2）ListEmpty(L)（3）Li
stLength(L)（4）GetElem(L,i,&e)（5）ListInsert(&L,i,e)（6）L
istDelete(&L,i,&e)……}ADTList如何表示和实现线性表呢
？存储结构顺序结构链式结构内存空间线性表：（a1,a2,a3,……ai-1,ai,ai+1,……an)a1a2
ai-1aiai+1ana3......内存空间顺序表a1a2a3ai-1aiai+1
anT单链表顺序表示指的是用一组地址连续的存储单元依次存储线性表的数据元素。假设线性表的每个元素占L个
字节单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。线性表中任一元素ai的存储位置为：
LOC（ai）=LOC(a1)+(i-1)L2.2线性表的顺序表示与实现可见，线性表中只要确
定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。顺序表的特点
：（1）可以随机存取任一元素；（2）插入、删除操作麻烦，需要移动数据元素。查找操作简单逻辑结构与存储结构一
致1.在C语言中可用动态分配的一维数组描述
typedefSqList;新类型固有类型？struct{
ElemTypeelem;//存储空间基址intlength;//当
前长度intlistsize;//当前分配的存储容量
//(以sizeof(ElemType)为单位)}内存空间基址typedef
struct{ElemTypeelem;//存储空间基址intlength;//
当前长度intlistsize;//当前分配的存储容量//(
以sizeof(ElemType)为单位)}SqList;//俗称顺序表#defineLIST_IN
IT_SIZE100//线性表存储空间的初始分配量#defineLIS
TINCREMENT10//线性表存储空间的分配增量线性表的动态分配顺序存储结构
采用顺序存储结构如何实现线性表的基本操作？第2步判断：存储分配是否成功？(1)初始化顺序表StatusInitLi
st_Sq(SqList&L){//构造一个空的线性表}//
InitList_Sq2.线性表的基本操作在顺序表中的实现L.elem=(ElemType)malloc(L
IST_INIT_SIZE?sizeof(ElemType));第1步：分配顺序表存储空
间if(!L.elem)exit(OVERFLOW);returnL.length=0;L.list
size=LIST_INIT_SIZE；returnOK;第3步：给表长和存储空间大小赋值第4步返回成功标志（1）I
nitList(&L)构造一个空的线性表Lmain(){}int
i,n;SqlistL;InitList_Sq(L);printf(("n=?“);
scanf("%d",&n);for(i=1;i<=n;++i)printf("e
lem[%d]=?",i);scanf("%d",&L.elem[i-1]);
L.length++;}创建含有个n元素的线性表{如何建立一个顺序表呢?
(2)顺序表的插入StatusListInsert_Sq(SqList&L,inti,ElemTypee)
{}//ListInsert_Sq1）确定插入位置q;2）将表尾至q位置的元素
往后移动一个位置；3）往q位置插入e.（4）表长增1；（5）返回成功标志。（1）判断i值是否合法？若不合法，则
返回出错；（不合法范围：i<1或i>L.length+1)（2）若i合法，接着应该判断：当前空间是否已满？
若满，则追加存储空间，否则，直接转下一步。（3）在i之前插入e；StatusListInsert_Sq(SqList
&L,inti,ElemTypee){……}//ListInsert_
Sqif(L.length>=L.listsize){newbase=(ElemType)reallo
c(L.elem,
(L.listsize+LISTINCREMENT)sizeof(ElemType));
if(!newbase)exit(OVERFLOW);L.elem=newbase;
L.listsize+=LISTINCREMENT;}if(i<1||i>L
.length+1)returnERROR;……q=&(L.elem[i-1]);//
q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)
(p+1)=p;q=e;
++L.length;returnOK;}//ListI
nsert_Sq(3)顺序表的删除StatusListDelete_Sq(SqList&L,int
i,ElemType&e){}//ListDelete_Sq（1）判断i是否合法？若不合法
，则返回出错信息；（不合法范围：i<1或i>L.length)（2）确定被删除元素的位置p并将删除元素赋给e;（3
）删除i位置元素；1）确定表尾元素位置q;2）将p+1位置的元素至表尾往前移动一个位置；（4）表长减1；（5）
返回成功标志。StatusListDelete_Sq(SqList&L,inti,ElemType&e){
}//ListDelete_Sq
if((i<1)||(i>L.length))returnERROR;p=&(L.e
lem[i-1]);e=p;q=L.elem+L.length-1;//表尾元素的位置for(
++p;p<=q;++p)(p-1)=p;--L.length;returnOK；顺
序表的插入、删除算法分析当在顺序表中某个位置上插入或删除一个元素时，其时间主要耗费在移动元素上（即移动元素的操作为预估算法时
间复杂度的基本操作），而移动元素的个数取决于插入或删除元素的位置。假设Pi是在第i个元素之前插入一元素的概率，则在长度为n的
顺序表中插入一个元素时所需移动元素次数的平均次数为：在顺序表中任意位置插入元素等概率情况下：Pi=1/(n+1)则
假设qi是删除第i个元素的概率，则在长度为n的顺序表中删除一个元素时所需移动元素次数的平均次数为：在
顺序表中任意位置插入元素等概率情况下：qi=1/n则可见，在顺序表中插入或删除一个元素
，平均约移动顺序表中一半元素。若表长为n，则算法ListInsert_Sq和ListDelete_Sq的时间复杂度均为：O(n)总结:1.顺序表的表示2.顺序表的实现（1）初始化一个顺序表（2）在顺序表中插入一个元素（3)在顺序表中删除一个元素预习：两个有序的顺序表合并算法作业：向一个长度为n的顺序表中的第i个元素（0≤i≤n-1）之前插入一个元素时，需向后移动__________个元素。2.在一个长度为n的顺序表中删除第i个元素（0≤i≤n-1）时，需向前移动_________个元素。实验作业：用C语言或C++语言，编程实现建立一个顺序表，在此表中插入一个元素，删除一个元素。数据结构第2章 |
|
