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.单链表

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

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

其中，存储单元由两部分构成，即数据域存储数据元素，指针域存储下一个元素所在的单元

如果表是a1,a2,…,an ，那么含有元素ai的那个单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n-1)。含有an的那个单元中的指针是空指针null。此外，通常我们还为每一个表设置一个表头单元header，其中的指针指向开始元素中所在的单元，但表头单元header中不含任何元素。设置表头单元的目的是为了使表运算中的一些边界条件更容易处理。这一点我们在后面可以看到。如果我们愿意单独地处理诸如在表的第一个位置上进行插人与删除操作等边界情况，也可以简单地用一个指向表的第一个单元的指针来代替表头单元。

上述这种用指针来表示表的结构通常称为单链接表，或简称为单链表或链表。单链表的逻辑结构如图1所示。表示空表的单链表只有一个单元，即表头单元header，其中的指针是空指针null。

第2章 线性表

图1 单链表示意图

为了便于实现表的各种运算，在单链表中位置变量的意义与用数组实现的表不同。在单链表中位置i是一个指针，它所指向的单元是元素ai-1所在的单元，而不是元素ai所在的单元(i=2,3,…,n)。位置1是指向表头单元header的指针。位置End(L)是指向单链表L中最后一个单元的指针。这样做的目的是为了避免在修改单链表指针时需要找一个元素的前驱元素的麻烦，因为在单链表中只设置指向后继元素的指针，而没有设置指向前驱元素的指针。

单链表存储结构

Typedef struct Lnode{ ElemType data;

Struct Lnode *next;//指向后继节点的指针 }Lnode, *LinkList;//线性链表的实质就是指针

基本运算

(1)ListInsert.L(L,i,e)

功能:在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行Insert(x,p)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为End(L)，那么表L变为a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。

实现P为指向a节点的指针，s为指向X节点的指针:s->next=p->next; p->next=s;

上述算法中，链表指针的修改情况见图2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库NOIP高中信息技术竞赛资料 - -数据结构(2)在线全文阅读。