《数据结构学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构学习教案.pptx（43页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1数据结构数据结构(sh j ji u)第一页，共43页。线性结构是一个数据元素的有序（次序）集线性结构是一个数据元素的有序（次序）集 线性结构的基本特征线性结构的基本特征:1集合中必存在集合中必存在(cnzi)唯一的一个唯一的一个“第一元素第一元素”；2集合中必存在集合中必存在(cnzi)唯一的一个唯一的一个“最后元素最后元素”；3除最后元素在外，均有唯一的后继；除最后元素在外，均有唯一的后继；4除第一元素之外，均有唯一的前驱。除第一元素之外，均有唯一的前驱。第1页/共43页第二页，共43页。2.1 线性表的类型定义线性表的类型定义线性表（linear_list）是最常用(chnyn)
2、且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。例如：（A,B,C,D,Z）（6,17,28,50,92,188）在线性表中，一个数据元素可以由若干数据项（item）组成。在这种情况下，常把数据元素称为记录（record），含有大量记录的线性表又称文件（file）。第2页/共43页第三页，共43页。抽象数据类型线性表的定义如下：ADTList数据对象(duxing)：Dai|aiElemSet,i=1,2,.,n,n0/称n为线性表的表长;称n=0时的线性表为空表。数据关系：R1|ai-1,aiD,i=2,.,n/设线性表为(a1，a2,.，an),称i为ai在线性表中的位
3、序。基本操作：InitList(&L)结构初始化操作结果：构造一个空的线性表L。DestroyList(&L)销毁结构初始条件：线性表L已存在。操作结果：销毁线性表L。第3页/共43页第四页，共43页。ListEmpty(L)初始条件：线性表L已存在。操作结果(jigu)：若L为空表，则返回TRUE，否则FALSE。ListLength(L)初始条件：线性表L已存在。操作结果(jigu)：返回L中元素个数。PriorElem(L,cur_e,&pre_e)初始条件：线性表L已存在。操作结果(jigu)：若cur_e是L的元素，但不是第一个，则用pre_e返回它的前驱，否则操作失败，pre_e无
4、定义。第4页/共43页第五页，共43页。NextElem(L,cur_e,&next_e)初始条件：线性表L已存在。操作结果：若cur_e是L的元素，但不是最后一个，则用next_e 返回它的后继，否则操作失败，next_e 无定义。GetElem(L,cur_e,&next_e)初始条件：线性表L已存在，1iLengthList(L)操作结果：用e返回L中第i个元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是元素判定函数(hnsh)。操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0。第
5、5页/共43页第六页，共43页。ListTraverse(L,visit()初始条件：线性表L已存在。操作结果：依次(yc)对L的每个元素调用函数visit()。一旦visit()失败，则操作失败。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。PutElem(L,i,&e)初始条件：线性表L已存在，1iLengthList(L)操作结果：L中第i个元素赋值同e的值。ListInsert(&L,i,e)初始条件：线性表L已存在，1iLengthList(L)+1操作结果：在L的第i个元素之前插入新的元素e，L的长度增1。第6页/共43页第七页，共43页。ListD
6、elete(&L,i,&e)初始条件：线性表L已存在且非空，1iLengthList(L)操作结果：删除L的第i个元素，并用(bnyn)e返回其值，L的长度减1。ADTList第7页/共43页第八页，共43页。例例2-1 假设有两个集合假设有两个集合A和和B分别用两个线性表分别用两个线性表LA和和LB表示表示(biosh)（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合AAB。上述问题可演绎为，要求对线性表作如下操作：扩大线性表上述问题可演绎为，要求对线性表作如下操作：扩大线性表LA，将存在于线性表，将存在于线性表LB
7、中而不存在于线性表中而不存在于线性表LA中的数据元素插入到线性表中的数据元素插入到线性表LA中去。中去。1从线性表从线性表LB中依次取得每个数据元素中依次取得每个数据元素;GetElem(LB,i)e2依值在线性表依值在线性表LA中进行查访中进行查访;LocateElem(LA,e,equal()3若不存在，则插入之。若不存在，则插入之。ListInsert(LA,n+1,e)第8页/共43页第九页，共43页。void union(List&La,List Lb)/将所有在线性表将所有在线性表Lb中但不在中但不在La中的数据元素插入到中的数据元素插入到La中中La_len=ListLength
8、(La);Lb_len=ListLength(Lb);/求线性表的长度求线性表的长度(chngd)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第9页/共43页第十页，共43页。2.2 线性表类型线性表类型(lixng)的实现的实现-顺序映象顺序映象用一组地址连续的存储单元依次存放线性表中的数据(shj)元素线性表的起始地址，
9、称作线性表的基地址以“存储位置相邻”表示有序对即：所有数据元素(yuns)的存储位置均取决于第一个数据元素(yuns)的存储位置第10页/共43页第十一页，共43页。顺序映像的顺序映像的C C语言描述语言描述(mio sh)(mio sh)/-/-线性表的动态分配顺序存储结构线性表的动态分配顺序存储结构-#define LIST_INIT_SIZE 80/#define LIST_INIT_SIZE 80/线性表存储空间的初始分配量线性表存储空间的初始分配量#define LISTINCREMENT 10/#define LISTINCREMENT 10/线性表存储空间的分配增量线性表存储空间
10、的分配增量typedef struct typedef struct ElemType*elem;/ElemType*elem;/存储空间基址存储空间基址 int length;/int length;/当前长度当前长度 int listsize;/int listsize;/当前分配的存储容量当前分配的存储容量(以以sizeof(ElemType)sizeof(ElemType)为单位为单位)SqList;/SqList;/俗称俗称 顺序表顺序表第11页/共43页第十二页，共43页。线性表的初始化在顺序映像中的实现线性表的初始化在顺序映像中的实现Status InitList_Sq(SqLi
11、st&L)/构造一个空的线性表构造一个空的线性表L。L.elem=(ElemType)malloc(LISTINCREMENT*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);/存储分配存储分配(fnpi)失败失败L.length=0;/长度为长度为0L.listsize=LISTINCREMENT;/初始存储容量初始存储容量return OK;/InitList_Sq第12页/共43页第十三页，共43页。线性表操作ListInsert(&L,i,e)的实现：问：插入元素时，线性表的逻辑结构发生什么(shnme)变化？(a1,ai-1,ai,an)改变为(
12、a1,ai-1,e,ai,an)第13页/共43页第十四页，共43页。Status ListInsert_Sq(SqList&L,int pos,ElemType e)/在顺序线性表在顺序线性表L的第的第pos个元素之前插入新的元素个元素之前插入新的元素e，/pos的合法值为的合法值为1posListlength_Sq(L)+1if(pos L.length+1)return ERROR;/插入位置不合法插入位置不合法if(L.length=L.listsize)/当前存储空间已满，增加分配当前存储空间已满，增加分配newbase=(ElemType*)realloc(L.elem,(L.li
13、stsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/存储分配失败存储分配失败(shbi)L.elem=newbase;/新基址新基址L.listsize+=LISTINCREMENT;/增加存储容量增加存储容量q=&(L.elempos-1);/q指示插入位置指示插入位置for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;/插入位置及之后的元素右移插入位置及之后的元素右移*q=e;/插入插入e+L.length;/表长增表长增1return OK;/ListInsert_Sq第1
14、4页/共43页第十五页，共43页。线性表操作ListDelete(&L,i,&e)的实现：问：删除(shnch)元素时，线性表的逻辑结构发生什么变化？(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an)第15页/共43页第十六页，共43页。Status ListDelete_Sq(SqList&L,int pos,ElemType&e)/在顺序线性表在顺序线性表L中删除第中删除第pos个元素，并用个元素，并用e返回其值。返回其值。/pos的合法值为的合法值为1posListLength_Sq(L)if(pos L.length)return ERROR;/删除位置删
15、除位置(wi zhi)不合法不合法p=&(L.elempos-1);/p为被删除元素的位置为被删除元素的位置(wi zhi)e=*p;/被删除元素的值赋给被删除元素的值赋给eq=L.elem+L.length-1;/表尾元素的位置表尾元素的位置(wi zhi)for(+p;p Next=p-Next;q-Next=p-Next;和和p-Next=q;p-Next=q;，即修改两个，即修改两个(lin)(lin)结点的指针域的值就结点的指针域的值就可以了，如图所示。可以了，如图所示。第23页/共43页第二十四页，共43页。单链表的插入(chr)(a)插入(chr)前；(b)插入(chr)后xqP
16、q-Nextp-Next；p-Nextq；xpq(a)(b)第24页/共43页第二十五页，共43页。线性表的操作ListInsert(&L,i,e)在链表中的实现:基本操作为:找到线性表中第i-1个结点，修改其指向后继(huj)的指针有序对改变为和StatusListInsert_L(LinkListL,intpos,ElemTypee)/在带头结点的单链表L中第pos个数据元素之前插入数据元素ep=L;j=0;while(p&jnext;+j;/寻找第pos-1个结点if(!p|jpos-1)returnERROR;/pos小于1或者大于表长s=(LinkList)malloc(sizeof
17、(LNode);/生成新结点s-data=e;s-next=p-next;/插入L中p-next=s;returnOK;/LinstInsert_L第25页/共43页第二十六页，共43页。删除操作如图所示。删除删除操作如图所示。删除p p所指示的结点时，只需修改所指示的结点时，只需修改一个指针：一个指针：q-Next=p-Nextq-Next=p-Next，但还需使用，但还需使用free(p)free(p)语句回收语句回收结点占用结点占用(zhn yn)(zhn yn)的空间。这里，结点的空间。这里，结点*q*q是结点是结点*p*p的前的前驱结点驱结点(predecessor)(predece
18、ssor)。由此可见，在单链表中，为了删除。由此可见，在单链表中，为了删除一个结点，我们必须知道它的前驱结点。一个结点，我们必须知道它的前驱结点。第26页/共43页第二十七页，共43页。单链表的删除(shnch)(a)删除(shnch)前；(b)删除(shnch)后qq-Nextp-Next；pqp(a)(b)第27页/共43页第二十八页，共43页。Status ListDelete_L(LinkList L,int pos,ElemType&e)/在带头结点的单链表在带头结点的单链表L中，删除中，删除(shnch)第第pos个元素，个元素，并由并由e返回其值返回其值p=L;j=0;while
19、(p-next&j next;+j;if(!(p-next)|j pos-1)return ERROR;/删除删除(shnch)位置不合理位置不合理q=p-next;p-next=q-next;/删除删除(shnch)并释放并释放结点结点e=q-data;free(q);return OK;/ListDelete_L算法的时间复杂度为算法的时间复杂度为:O(ListLength(L)第28页/共43页第二十九页，共43页。五、循环链表五、循环链表 另一种形式的链式存储结构。它的特点是表另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表中最后一个结点的指针域指向头结
20、点，整个链表形成形成(xngchng)(xngchng)一个环。由此，从表中任一结点一个环。由此，从表中任一结点出发均可找到表中其他结点，如图为单链表的循出发均可找到表中其他结点，如图为单链表的循环链表和带头结点的循环链表。环链表和带头结点的循环链表。最后一个结点的指针域的指针又指回第一个结点最后一个结点的指针域的指针又指回第一个结点的链表的链表第29页/共43页第三十页，共43页。单循环链表(a)空表；(b)非空表(a)(b)Heada0a1an1Head第30页/共43页第三十一页，共43页。带表头(biotu)结点的单循环链表(a)空表；(b)非空表(a)(b)Heada0a1an1He
21、ad第31页/共43页第三十二页，共43页。六、双向链表六、双向链表 我们已经看到，在各种单链表中插入一个新结点时，需知道新结点插入位置的前驱结点，而当删除一个结点时也需知道该结点的前驱结点。常常为了得到前驱结点的地址，必须从头开始查找，这一过程是费时的。此外，在实际应用中，有时需要逆向访问表中元素，这对单链表结构我们已经看到，在各种单链表中插入一个新结点时，需知道新结点插入位置的前驱结点，而当删除一个结点时也需知道该结点的前驱结点。常常为了得到前驱结点的地址，必须从头开始查找，这一过程是费时的。此外，在实际应用中，有时需要逆向访问表中元素，这对单链表结构(jigu)(jigu)来说显然是困难
22、的。为解决这类问题，可将链表设计成双向链表来说显然是困难的。为解决这类问题，可将链表设计成双向链表(doubly linked list)(doubly linked list)。第32页/共43页第三十三页，共43页。双向链表的每个结点包含三个域：Element、Prior和Next。其中，Element为元素域，Next域为指向(zh xin)后继结点的指针，新增的Prior域用以指向(zh xin)前驱结点。双向链表也可以带表头结点，并且也可构成双向循环链表。此时，表头结点的Next和Prior分别指向(zh xin)双向循环链表的头结点(或表头结点)和尾结点。带表头结点的双向循环链表的
23、结构示意图如图所示。第33页/共43页第三十四页，共43页。带表头(biotu)结点的双向循环链表(a)空表；(b)非空表(a)(b)HeadHeada0an1第34页/共43页第三十五页，共43页。/-线性表的双向链表存储结构-typedefstructDuLNodeElemTypedata;/数据域structDuLNode*prior;/指向(zhxin)前驱的指针域structDuLNode*next;/指向(zhxin)后继的指针域DuLNode,*DuLinkList;第35页/共43页第三十六页，共43页。线性表顺序存储结构的优缺点：线性表顺序存储结构的优缺点：1 1、优点、优点
24、（1 1）结构简单）结构简单（2 2）可直接定位）可直接定位(dngwi)(dngwi)到表中任一元素，并可随机到表中任一元素，并可随机存取元素；连续存储速度快存取元素；连续存储速度快2 2、缺点、缺点（1 1）存储空间难于准确静态分配，大了浪费，小了不）存储空间难于准确静态分配，大了浪费，小了不够够（2 2）插入、删除操作大不方便，需移动大量数据元素，）插入、删除操作大不方便，需移动大量数据元素，效率低效率低第36页/共43页第三十七页，共43页。线性表链式存储结构的优缺点：线性表链式存储结构的优缺点：1 1、优点、优点（1 1）存储空间动态分配，可以）存储空间动态分配，可以(ky)(ky)
25、按需使用按需使用（2 2）插入、删除结点操作时通常只要修改指针，不必移）插入、删除结点操作时通常只要修改指针，不必移动数据元素动数据元素2 2、缺点、缺点（1 1）每一结点附加指针域）每一结点附加指针域（2 2）非随机存取结构，查找定位操作需从头指针出发顺）非随机存取结构，查找定位操作需从头指针出发顺着链表扫描着链表扫描第37页/共43页第三十八页，共43页。习习 题题 221定义一个结构类型，它包括年、月、日。用该结构类型定义一个结构变量。22设计一个算法，用来复制一个单链表23设有长度为n的一维整型数组A，设计一个算法，将原数组中的元素(yuns)以逆序排列。24设计一个算法，将一个单链表
26、链接到另一个单链表的尾部。第38页/共43页第三十九页，共43页。25设一维数组的每个元素具有前面的年、月、日结构类型，设计一个函数Copy，用来实现数组的整体赋值。26编写一个函数NewArray，用来创建一个最多有MaxSize个元素的动态一维数组，设数组元素具有前面的年、月、日结构类型。此函数返回一个指针(zhzhn)，指向动态一维数组的起始位置。27设有长度为n的一维整型数组A，设计一个算法，将该数组中所有的负数存放在数组的前部，而所有的正数存放在负数的后面。第39页/共43页第四十页，共43页。28设有长度为n的一维整型数组A，数组中元素各不相同。设计一个算法，该算法以数组的第一个元
27、素为基准元素，对各元素在数组中的位置作重新调整，将所有(suyu)比该基准元素小的元素存放在基准元素的前面部分，所有(suyu)比基准元素大的元素存放在基准元素后面部分。第40页/共43页第四十一页，共43页。212设计一个算法(sunf)，将单链表中结点以逆序排列。逆序的单链表中的结点均为原表中的结点。213设计一个函数，用以建立一个带表头结点的单循环链表。设表中元素的类型为整型，元素值从键盘输入。214设计一个函数，用以打印一个带表头结点的单循环链表。设表中元素的类型为整型。注意循环链表的结束判断。215设计一个函数，用来清空一个带表头结点的单循环链表。请注意带表头结点的单循环链表的空表形式。第41页/共43页第四十二页，共43页。216单链表中每个结点存放一个字符。设计一个算法，将该单链表按字母、数字和其他字符拆成三个单循环链表(利用原来结点)。217设计一个算法，将一个带表头结点的双向循环链表链接到另一个带表头结点的双向循环链表的尾部。注意，新链表只需一个表头结点。对习题中要求设计的所有算法，若不加特殊说明，都必须：(1)写出相关数据结构(shjjiu)的C语言类型说明；(2)算法用C语言函数表示。在设计链表操作的算法时，请考虑链表可能为空表的情况。第42页/共43页第四十三页，共43页。