NOIP高中信息技术竞赛资料 - -数据结构(2)

第2章 线性表

初始条件：线性表L存在。

操作结果：返回线性表L中所有元素的个数。 （3）取表元 格式：GetList(L，i)

初始条件：线性表L存在，且1≤i≤LengthList(L)。 操作结果：返回线性表L的第i个元素(ai)的值。 （4）按值查找 格式：LocateList(L，x)

初始条件：线性表L存在，x有确定的值。

操作结果：在线性表L中查找值为x的数据元素，并返回该元素在L中的位置。若L中有多个元素的值与x相同，则返回首次找到的元素的位置；若L中没有值为x的数据元素，返回一个特殊值（通常为-1）表示查找失败。

（5）插入操作

格式：InsertList(L，i，x)

初始条件：线性表L存在，i为插入位置（1≤i≤n+1，n为插入前的表长）。 操作结果：在线性表L的第i个元素(ai)位置上插入值为x的新元素，原序号为i,i+1, …,n的数据元素的序号插入后变为i+1,i+2, …,n+1，插入后表长=原表长+1。

（6）删除操作 格式：DeleteList(L，i)

初始条件：线性表L存在，i（1≤i≤n）为给定的待删除元素的位置值。 操作结果：在线性表L中删除序号为i的数据元素(ai)，删除后，原序号为i+1,i+2, …,n的数据元素的序号变为i,i+1, …,n-1，删除后表长=原表长-1。

注：以上给出的是线性表的基本运算，并不是全部运算，其它运算可用这些基本运算来实现，这些运算都是定义在逻辑结构层次上的运算，只有确定了存储结构之后，才能具体实现这些运算。

例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U B

void union(List &La ,List &Lb){

//将所有在线性表Lb中，但不在La中的数插入到La中 La.len=ListLength(La);

Lb.len=ListLength(Lb); //求两表的长度 for(i=1;i<=Lb.len;i++)

GetElem(Lb,i,e);//取Lb中第i个的元素复制给e If(!LocateElem(La,e,equal))

ListInsert(La,++La.len,e);//若其中不存在相同的，则插入 }//union

例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将la，lb归并为一个新的线性表lc且lc按值非递减。

第2章 线性表

例如 la=（3,5,8,11）,

Lb=(2,6,8,9,11,15,20) 则lc=(2,3,5,6,8,8,9,11,11,15,20)

分析：由于两表都是按照一定顺序进行排列，所有设置2个指针，分别指向a、b表，先分别比较比较最初指向的两数据，比较一下大小，谁小就放入到c表中，然后数小的指针向下移动，再进行比较。直到2表有一表结束,再将剩余的表存放到c中。

Void MergeList(List La, List Lb,List &Lc){ //已知线性表la和lb中的数据元素 InitList(Lc);//初始化表c Int i=j=1;k=0;

La.len=ListLength(La); Lb.len= ListLength(Lb);

While((i<= La.len)&&( (j<= Lb.len)){ GetElem（La,i,ai）;

GetElem（Lb,j,bj）;//获取数值 If(ai<=bj){

ListInsert(Lc,++k,ai); i++; }else{

ListInsert(Lc,++k,bj); j++; }//if结束

}//whie结束,其中一表结束；

While(i<=La.len){//表B数据全访问完，表a未到最后 GetElem（La,i++,ai）; ListInsert(Lc,++k,ai); }

While(j<=Lb.len){//表a数据全访问完，表b未到最后 GetElem（Lb,j++,bj）; ListInsert(Lc,++k,bj); }

}//程序结束

分析：上述2个算法的时间复杂度（基本操作的执行时间），例1为O(ListLength(La)*ListLength(Lb)),例2的时间复杂度为O(ListLength(La)+ListLength(Lb))。

2.2 线性表的顺序存储结构

线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。设线性表中每个元素需占用r个存储单元则

loc（ai+1 ）=loc（ai）+r

loc（ai）=loc（a1）+（i-1）*r

线性表的这种机内表示称做线性表的顺序存储结构或顺序映像，通常，称这种存储结构的线性表为顺序表。只要确定了存储线性表的起始位置，线性表中任

第2章 线性表

一数据元素可随机存储，所以线性表的顺序结构是一种随机存储的存储结构。

//======线性表的动态顺序存储结构

#define LIST_INIT_SIZE 100 // 初始分配量 #define LISTINCREMENT 10 //分配增量 Typedef struct{

Elemtype *elem; //存储空间基址 Int length; //当前长度

Int listsize; //当前分配的存储容量 }SqList;

Elem表示基地址，length指示线性表的当前长度。上述的含义是为顺序表分配一个

预定义大小的数据空间，并将当前的长度设为0；

Status InitList_sq(SqList &L){ //====创建一个空的线性表

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));// ElemType指数据类型，malloc新分配空间

If(!L.elem) exit(OVERFLOW);//存储分配失败 L.length=0;//空表长度为0

L.listsize= LIST_INIT_SIZE;//初始存储容量 Return ok； }//InitList_sq

在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。

Status ListInsert_sq(SqList &L,int I,ElemType e){ //在顺序表中插入一个新元素 e If(i<1||i>L.length+1) return Error;

If(L.length>= L.listsize){//当前存储空间已满，增加分配

Newbase=(ElemType*)realloc(L.elem,(LIST_INIT_SIZE+LISTINCREMENT)*sizeof(ElemType));// ElemType指数据类型，realloc再次分配，L.elem存储基地址

}//if

q=&(L.elem[i-1]);//q为插入位置 for(p=&(L.elem[L.length-1]);p>=q;--p){ *(p+1)=*q; }//for *q=e;//插入e ++ L.length； Return ok； }

第2章 线性表

执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间复杂度均为O(n)n为表的长度。

Status ListDelete_sq(SqList &L,int I,ElemType &e){ //在顺序表中插入一个新元素 e If(i<1||i>L.length+1) return Error; p=&(L.elem[i-1]);//p为删除位置 e=*p;

q=L.elem+L.length-1; for(++p;p<=q;++p){ *(p-1)=*p; }//for -- L.length； Return ok； }

2.3 线性表的链式存储结构

线性表顺序结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存储表中的任一元素，但是在插入删除时须移动大量元素。而线性表的链式存储由于其不要求逻辑上相邻，因此它没有顺序存储结构的弱点，但同时也失去了顺序表可随机存取的优点。

1.单链表

线性链表的特点是用一组任意的存储单元存储线性表的元素，用指针将存储表元素的那些单元依次串联在一起。这种方法避免了在数组中用连续的单元存储元素的缺点，因而在执行插入或删除运算时，不再需要移动元素来腾出空间或填补空缺。然而我们为此付出的代价是，需要在每个单元中设置指针来表示表中元素之间的逻辑关系，因而增加了额外的存储空间的开销。

为了将存储表元素的所有单元用指针串联起来，我们让每个单元包含一个元素域和一个指针域如图所示：

其中，存储单元由两部分构成，即数据域存储数据元素，指针域存储下一个元素所在 …… 此处隐藏：2630字，全部文档内容请下载后查看。喜欢就下载吧 ……