数据结构9课件

第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现习题2数据结构9线性结构是一个数据元素的有序（次序）集线性结构的基本特征:1．集合中必存在唯一的一个“第一元素”；2．集合中必存在唯一的一个“最后元素”；3．除最后元素在外，均有唯一的后继；4．除第一元素之外，均有唯一的前驱。数据结构92.1线性表的类型定义线性表（linear_list）是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。例如：（A,B,C,D,……Z） （6,17,28,50,92,188）在线性表中，一个数据元素可以由若干数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。数据结构9抽象数据类型线性表的定义如下：ADTList{数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0} //{称n为线性表的表长;称n=0时的线性表为空表。}数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n} //{设线性表为(a1，a2,....，an),称i为ai在线性表中的位序。}基本操作：

InitList(&L) 结构初始化 操作结果：构造一个空的线性表L。

DestroyList(&L) 销毁结构

初始条件：线性表L已存在。 操作结果：销毁线性表L。数据结构9ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无定义。数据结构9NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义。GetElem(L,cur_e,&next_e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare())初始条件：线性表L已存在，compare()是元素判定函数。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。数据结构9ListTraverse(L,visit())初始条件：线性表L已存在。操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1≤i≤LengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1≤i≤LengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。数据结构9ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1≤i≤LengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。}ADTList数据结构9例2-1假设有两个集合A和B分别用两个线性表LA和LB表示（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。1．从线性表LB中依次取得每个数据元素;GetElem(LB,i)→e2．依值在线性表LA中进行查访;LocateElem(LA,e,equal())3．若不存在，则插入之。ListInsert(LA,n+1,e)数据结构9voidunion(List&La,ListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){

GetElem(Lb,i,e); //取Lb中第i个数据元素赋给eif(!LocateElem(La,e,equal())ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之}}//union数据结构92.2线性表类型的实现--顺序映象用一组地址连续的存储单元依次存放线性表中的数据元素线性表的起始地址，称作线性表的基地址以“存储位置相邻”表示有序对<ai-1，ai>

即：所有数据元素的存储位置均取决于第一个数据元素的存储位置数据结构9顺序映像的C语言描述//-----线性表的动态分配顺序存储结构-----#defineLIST_INIT_SIZE80//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType*elem;//存储空间基址

intlength;//当前长度

intlistsize;//当前分配的存储容量(以sizeof(ElemType)为单位)}SqList;//俗称顺序表数据结构9线性表的初始化在顺序映像中的实现StatusInitList_Sq(SqList&L){//构造一个空的线性表L。L.elem=(ElemType)malloc(LISTINCREMENT*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败L.length=0;//长度为0L.listsize=LISTINCREMENT;//初始存储容量returnOK;}//InitList_Sq数据结构9线性表操作ListInsert(&L,i,e)的实现：问：插入元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,…,an)改变为(a1,…,ai-1,e,ai,…,an)数据结构9StatusListInsert_Sq(SqList&L,intpos,ElemTypee){//在顺序线性表L的第pos个元素之前插入新的元素e，//pos的合法值为1≤pos≤Listlength_Sq(L)+1if(pos<1||pos>L.length+1)returnERROR;//插入位置不合法if(L.length>=L.listsize){

//当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW); //存储分配失败L.elem=newbase; //新基址L.listsize+=LISTINCREMENT; //增加存储容量}q=&(L.elem[pos-1]); //q指示插入位置for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素右移*q=e; //插入e++L.length; //表长增1returnOK;}

//ListInsert_Sq数据结构9线性表操作ListDelete(&L,i,&e)的实现：问：删除元素时，线性表的逻辑结构发生什么变化？(a1,…,ai-1,ai,ai+1,…,an)改变为(a1,…,ai-1,ai+1,…,an)数据结构9StatusListDelete_Sq(SqList&L,intpos,ElemType&e){//在顺序线性表L中删除第pos个元素，并用e返回其值。//pos的合法值为1≤pos≤ListLength_Sq(L)if((pos<1)||(pos>L.length))returnERROR;//删除位置不合法p=&(L.elem[pos-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素左移--L.length;//表长减1returnOK;}

//ListDelete_Sq数据结构92.3线性表类型的实现－－链式映象一、单链表用一组地址任意的存储单元存放线性表中的数据元素。

元素 + 指针 = 结点

(数据元素的映象)

(指示后继元素存储位置的)

(表示数据元素)

以“结点的序列”表示线性表－－称作链表。以线性表中第一个数据元素a1的存储地址作为线性表的地址，为线性表的头指针。数据结构9单链表结构

(a)结点结构；(b)空表；(c)非空表DataNext(a)H(b)a0a1…an－1(c)H数据结构9二、结点和单链表的C语言描述typedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;在单链表前增加一个结点，称为表头结点。数据结构9带表头结点的单链表

(a)空表；(b)非空表HeadHeada0a1…an－1(a)(b)数据结构9看下面的程序段：inti,*pi; /*定义整型变量i和指向整型的指针变量pi*/pi=&i; /*将变量i的地址赋给指针(变量)pi*/i=5; /*对变量i赋整数值5*/printf("%d，"，i); /*输出i的值5和逗号*/*pi=10; /*对指针pi所指示的存储位置(变量i)赋值10*/printf("%d"，*pi); /*输出i的当前值10*/运行上面的程序段将显示：5，10。数据结构9

指针定义和运算254piipi＝&i;2545piii＝5;25410piipi＝10;pi&i＝254inti,*pi;*数据结构9单链表的插入和删除在单链表的指定结点(设由指针变量p指示)后面插入新结点(由q指示)的方法很简单，只需使用指针赋值语句q->Next=p->Next;和p->Next=q;，即修改两个结点的指针域的值就可以了，如图所示。数据结构9单链表的插入

(a)插入前；(b)插入后xqPq->Next＝p->Next；p->Next＝q；xpq(a)(b)数据结构9线性表的操作ListInsert(&L,i,e)在链表中的实现:基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针有序对<ai-1,ai>改变为<ai-1,e>和<e,ai>StatusListInsert_L(LinkListL,intpos,ElemTypee){//在带头结点的单链表L中第pos个数据元素之前插入数据元素ep=L;j=0;while(p&&j<pos-1){

p=p->next;++j;}

//寻找第pos-1个结点if(!p||j>pos-1)returnERROR; //pos小于1或者大于表长s=(LinkList)malloc(sizeof(LNode)); //生成新结点s->data=e;s->next=p->next;

//插入L中p->next=s;returnOK;}//LinstInsert_L数据结构9

删除操作如图所示。删除p所指示的结点时，只需修改一个指针：q->Next=p->Next，但还需使用free(p)语句回收结点占用的空间。这里，结点*q是结点*p的前驱结点(predecessor)。由此可见，在单链表中，为了删除一个结点，我们必须知道它的前驱结点。数据结构9单链表的删除

(a)删除前；(b)删除后qq->Next＝p->Next；pqp(a)(b)数据结构9StatusListDelete_L(LinkListL,intpos,ElemType&e){//在带头结点的单链表L中，删除第pos个元素，并由e返回其值p=L;j=0;while(p->next&&j<pos-1){//寻找第pos个结点，并令p指向其前趋p=p->next;++j;}if(!(p->next)||j>pos-1)returnERROR;//删除位置不合理q=p->next;p->next=q->next;

//删除并释放结点e=q->data;free(q);returnOK;}

//ListDelete_L算法的时间复杂度为:O(ListLength(L))数据结构9五、循环链表

另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点，如图为单链表的循环链表和带头结点的循环链表。最后一个结点的指针域的指针又指回第一个结点的链表数据结构9单循环链表(a)空表；(b)非空表(a)(b)Heada0a1…an－1Head数据结构9带表头结点的单循环链表(a)空表；(b)非空表(a)(b)Heada0a1…an－1Head数据结构9六、双向链表我们已经看到，在各种单链表中插入一个新结点时，需知道新结点插入位置的前驱结点，而当删除一个结点时也需知道该结点的前驱结点。常常为了得到前驱结点的地址，必须从头开始查找，这一过程是费时的。此外，在实际应用中，有时需要逆向访问表中元素，这对单链表结构来说显然是困难的。为解决这类问题，可将链表设计成双向链表(doublylinkedlist)。数据结构9

双向链表的每个结点包含三个域：Element、Prior和Next。其中，Element为元素域，Next域为指向后继结点的指针，新增的Prior域用以指向前驱结点。双向链表也可以带表头结点，并且也可构成双向循环链表。此时，表头结点的Next和Prior分别指向双向循环链表的头结点(或表头结点)和尾结点。带表头结点的双向循环链表的结构示意图如图所示。数据结构9带表头结点的双向循环链表(a)空表；(b)非空表(a)(b)HeadHeada0an－1…数据结构9//-----线性表的双向链表存储结构

-----typedefstructDuLNode{ElemTypedata; //数据域structDuLNode*prior; //指向前驱的指针域structDuLNode*next; //

指向后继的指针域}DuLNode,*DuLinkList;数据结构9线性表顺序存储结构的优缺点：1、优点（1）结构简单（2）可直接定位到表中任一元素，并可随机存取元素；连续存储速度快2、缺点（1）存储空间难于准确静态分配，大了浪费，小了不够（2）插入、删除操作大不方便，需移动大量数据元素，效率低数据结构9线性表链式存储结构的优缺点：1、优点（1）存储空间动态分配，可以按需使用（2）插入、删除结点操作时通常只要修改指针，不必移动数据元素2、缺点（1）每一结点附加指针域（2）非随机存取结构，查找定位操作需从头指针出发顺着链表扫描数据结构9习题22－1定义一个结构类型，它包括年、月、日。用该结构类型定义一个结构变量。

2－2设计一个算法，用来复制一个单链表

2－3设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素以逆序排列。

2－4设计一个算法，将一个单链表链接到另一个单链表的尾部。数据结构92－5设一维数组的每个元素具有前面的年、月、日结构类型，设计一个函数Cop