数据结构初步

《数据结构初步》由会员分享，可在线阅读，更多相关《数据结构初步（66页珍藏版）》请在金锄头文库上搜索。

1、Neusoft Group Ltd.Date: 31 七月 2024数据结构初步Stillwatersrundeep.流静水深流静水深,人静心深人静心深Wherethereislife,thereishope。有生命必有希望。有生命必有希望Neusoft Group Ltd.Date: 31 七月 2024第一部分第一部分 数据结构基础知数据结构基础知识识Neusoft Group Ltd.Date: 31 七月 2024数据结构数据结构数据结构：数据结构：是一门研究非数值计算的程序设计问题中计算机操作对象以及它们之间的关系和操作等等的学科。Neusoft Group Ltd.Date: 31

2、 七月 2024基本概念基本概念数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。Neusoft Group Ltd.Date: 31 七月 2024 数据的逻辑结构数据的逻辑结构 数据的存储结构数据的存储结构 数据的运算：检索、排序、插入、删除、修改等数据的运算：检索、排序、插入、删除、修改等 线性结构线性结构 非线性结构非线性结构 顺序存储顺序存储 链式存储链式存储 线性表线性表栈栈队队树形结构树形结构图形结

3、构图形结构数据结构的三个方面：数据结构的三个方面：Neusoft Group Ltd.Date: 31 七月 2024主要内容主要内容 1.1 线性表以及其应用1.2 栈、队列1.3 排序、查找Neusoft Group Ltd.Date: 31 七月 20241.1 1.1 线性表以及其应用（线性表以及其应用（1 1）线性表线性表分为静态线性表和动态线性表静态线性表特征：表中节点的存储是连续的，占用一块连续存储区，一般节点的数量是固定的；存储表示如下图数据结构如下图数据1后继:2数据2后继:3数据3后继:4数据n1后继:n数据nendtypedef struct Data_t data; /

4、数据域 int next; /后继域Node_t, *PNode_t;/提供的操作有 ：初始化、插入、删除等。Neusoft Group Ltd.Date: 31 七月 2024线性表线性表顺序存储结构特定：借助元素在存储器中的相对位置（即，物理位置相邻）来表示数据元素之间的逻辑关系。缺点：插入、删除时，需移动大量数据。一次性分配内存空间。表的容量难以扩充。Neusoft Group Ltd.Date: 31 七月 2024图顺序存储结构内存结构示意图 Neusoft Group Ltd.Date: 31 七月 20241.1 1.1 线性表以及其应用（线性表以及其应用（2 2）动态线性表特征

5、：表中节点的存储是不连续的，一般节点的数量是不固定的；存储表示如下图数据结构如下图typedef struct Data_t data; /数据域 Node_t* next; /后继域Node_t, *PNode_t;/提供的操作有 ：初始化、插入、删除等。数据1后继数据2后继数据3后继数据n1后继数据nendNeusoft Group Ltd.Date: 31 七月 2024链式存储结构链式存储结构链式存储结构是计算机中的另一种最基本和最主要的数据存储结构。和顺序存储结构不同，初始时链式存储结构为空链，每当有新的数据元素需要存储时用户向系统动态申请所需的存储空间插入链中。Neusoft Gr

6、oup Ltd.Date: 31 七月 2024链式存储结构链式存储结构每个结点有两个域，其中存储数据元素信息的域称为整数域；存储直接后继存储位置的域称为指针域。structNodeintdata;structNode*Next;typedefstructNodeNode_t;Neusoft Group Ltd.Date: 31 七月 2024链式存储结构存储线性结构数据元素集合的方法是用结点（Node）构造链。线性结构数据元素的特点是：除第一个和最后一个元素外，每个元素只有一个惟一的前驱和一个惟一的后继。链式结构中每个结点除数据域外还有一个或一个以上的指针域，数据域用来存放数据元素，指针域用

7、来构造数据元素之间的关系。只有一个指针域的结点结构如图所示。Neusoft Group Ltd.Date: 31 七月 2024图只有一个指针域的结点结构 数据域指针域datanext或Neusoft Group Ltd.Date: 31 七月 2024根据指针域的不同和结点构造链的方法不同，链式存储结构存储线性结构数据元素的方法主要有单链、单循环链和双向循环链等三种。这三种结构中每一种又有带头结点结构和不带头结点结构两种。头结点是指头指针所指的不存放数据元素的结点。其中，带头结点的链式结构在表的存储中更为常用，不带头结点的链式结构在堆栈和队列的存储中更为常用。Neusoft Group Lt

8、d.Date: 31 七月 2024我们把图中头结点的数据域部分涂上阴影，以明显表示该结点为头结点。图2和图3中的指针域为指向下一个结点的指针。图4中结点右部的指针域为指向下一个结点的指针，结点左部的指针域为指向上一个结点的指针。在以后的图示中，头指针将用head表示。Neusoft Group Ltd.Date: 31 七月 2024图2 带头结点的单链结构 (a)空链； (b)非空链 Neusoft Group Ltd.Date: 31 七月 2024图3 带头结点的单循环链结构 (a)空链； (b)非空链 Neusoft Group Ltd.Date: 31 七月 2024图4 带头结点

9、的双循环链结构 (a)空链； (b)非空链 Neusoft Group Ltd.Date: 31 七月 2024图中的符号“”表示空指针，空指针在算法描述中用NULL表示。空指针是一个特殊标识，用来标识链的结束。NULL在C中宏定义为0，因此空指针在C中也就是0地址。为与顺序表中数据元素从a0开始相一致，讨论链表时数据元素也从a0开始。链式存储结构也可以方便地存储非线性结构的数据元素。链式存储结构存储非线性结构数据元素的最典型的例子是链式结构的二叉树。Neusoft Group Ltd.Date: 31 七月 2024添加插入删除Neusoft Group Ltd.Date: 31 七月 20

10、24图 单链表在第一个位置删除结点过程t = p-next;p-next = t-next;dispose(t);Neusoft Group Ltd.Date: 31 七月 2024图 单链表在第一个位置插入结点过程 （a）插入前； （b）插入后 new(s); s.data=x; s.next=head.next;head.next=s;heada0a1an1xs( a )heada0a1an1x( b )Neusoft Group Ltd.Date: 31 七月 2024循环链表循环链表(circular linked list)循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特

11、点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p或p-next=NULL循环链表p或p-next=Hhh空表Neusoft Group Ltd.Date: 31 七月 2024双向链表双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。Neusoft Group Ltd.Date: 31 七月 2024双向链表（doublelinkedlist）结点定义Typedet struct DuLNodeElemType data;struc

12、t DuLNode *prior;struct DuLNode *next; DuLNode,*DuLinkList;priorelementnextL空双向循环链表：非空双向循环链表： LABbcapppriornext= p= pnextproir;Neusoft Group Ltd.Date: 31 七月 2024栈和队列栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表栈（stack）一、栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾栈顶，表头栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2.栈底栈顶.出栈进栈栈s=(a1,a

13、2,an)Neusoft Group Ltd.Date: 31 七月 2024栈的表示和实现栈的表示和实现栈有两种存储表示方法:顺序栈链栈Neusoft Group Ltd.Date: 31 七月 2024顺序栈实现：top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF栈的初始空间为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空Neusoft Group Ltd.Da

14、te: 31 七月 2024链栈栈顶栈顶 .topdata link栈底入栈算法出栈算法 .栈底toptopxptop .栈底topqNeusoft Group Ltd.Date: 31 七月 2024栈的应用举例由于栈结构具有的后进先出的固有特性，致使栈成为程序设计中常用的工具。数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)Neusoft Group Ltd.Date: 31 七月 2024例如(159)10=(237)8，其运算过程如下:nndiv8n

15、mod81591971923202实际情况:(159)10=(237)815981982802 3 7 余 7余 3余 2toptop7top73top732Neusoft Group Ltd.Date: 31 七月 2024队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)允许插入的一端队头(front)允许删除的一端队列特点：先进先出(FIFO)a1 a2 a3.an 入队出队frontrear队列Q=(a1,a2,an)Neusoft Group Ltd.Date: 31 七月 2024队列的顺序存储结构实现：用一维数组实现sqMfr

16、ont=0rear=0123450队空123450frontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素后一位置；front指示队头元素位置初值front=rear=0空队列条件：front=rear入队列：sqrear+=x;出队列：x=sqfront+;rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontNeusoft Group Ltd.Date: 31 七月 2024存在问题设数组长度为M，则：当front=0,re

17、ar=M时，再有元素入队发生溢出真溢出当front0,rear=M时，再有元素入队发生溢出假溢出解决方案队首固定，每次出队剩余元素向下移动浪费时间循环队列基本思想：把队列设想成环形，让sq0接在sqM-1之后，若rear+1=M,则令rear=0;0M11frontrear.实现：利用“模”运算入队：rear=(rear+1)%M;sqrear=x;出队：front=(front+1)%M;x=sqfront;队满、队空判定条件Neusoft Group Ltd.Date: 31 七月 2024循环队列上的插入操作（进队列）StatusEnQueue(SqQueue&Q,QElemTypee)

18、 if(Q.rear+1)%MXASIZE=Q.front)returnERROR;/队列满Q.baseQ.rear=e;/新元素存放到队尾Q.rear=(Q.rear+1)%MAXQSIZE;/修改队为指示器returnOK; 0 1 0 1 C 0 1 7 2 7 2 7 2C 6 3 6 3 6 3 5 4 5 4 5 4 A B A B D D E F E G图313 循环队列上的插入Q.rearQ.rearQ.rearQ.frontQ.frontQ.front满队列空队列Neusoft Group Ltd.Date: 31 七月 20243）循环队列的删除把队头元素删除StatusD

19、eQueue(SqQueue&Q,QElemTypee) if(Q.front=Q.rear) returnERROR;/队列空e=Q.baseQ.front;/删除当前队头元素Q.front=(Q.front+1)%MAXQSIZE;/修改队头指示器 returnOK; G A B C C D G D F E F E图314 循环队列的删除过程Q.rearQ.rearQ.rearQ.front（1）满 （2）删除A、B后的队列 （3） 删除最后一个元素空队列Q.frontQ.frontNeusoft Group Ltd.Date: 31 七月 2024链队列结点定义typedef struc

20、t Qnode QElemType data; struct Qnode *next;Qnode, *QueuePtr;头结点 .front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾typedef struct QueuePtr front; QueuePtr rear;LinkQueue;Neusoft Group Ltd.Date: 31 七月 2024frontrearx入队xfrontreary入队xyfrontrearx出队xyfront rear空队front reary出队Neusoft Group Ltd.Date: 31 七月

21、 2024问题问题栈的数据结构有什么特点队列的数据结构有什么特点Neusoft Group Ltd.Date: 31 七月 2024查找查找查找也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素关键字是数据元素中某个数据项的值，它可以标识一个数据元素查找方法评价查找速度占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的Neusoft Group Ltd.Date: 31 七月 2024顺序查找查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较

22、算法描述Ch7_1.ci例 0 1 2 3 4 5 6 7 8 9 10 11 5 13 19 21 37 56 64 75 80 88 92找6464监视哨iiii比较次数=5比较次数：查找第n个元素： 1查找第n1个元素：2.查找第1个元素： n查找第i个元素： n+1i查找失败： n+1Neusoft Group Ltd.Date: 31 七月 2024折半查找查找过程：每次将待查记录所在区间缩小一半适用条件：采用顺序存储结构的有序表算法实现设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,high=n,mid=(low+hi

23、gh)/2让k与mid指向的记录比较若k=rmid.key，查找成功若krmid.key，则low=mid+1重复上述操作，直至lowhigh时，查找失败Neusoft Group Ltd.Date: 31 七月 2024算法描述lowhighmid例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92找211 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88

24、92lowhighmidCh7_2.cNeusoft Group Ltd.Date: 31 七月 2024例 1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid找701 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhighmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92low highmid1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80

25、88 92lowhighmidNeusoft Group Ltd.Date: 31 七月 20241 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92lowhigh1185210741936判定树：1 2 3 4 5 6 7 8 9 10 115 13 19 21 37 56 64 75 80 88 92Neusoft Group Ltd.Date: 31 七月 2024分块查找查找过程：将表分成几块，块内无序，块间有序；先确定待查记录所在块，再在块内查找适用条件：分块有序表算法实现用数组存放待查记录,每个数据元素至少含有关键字域建立索引

26、表，每个索引表结点含有最大关键字域和指向本块第一个结点的指针算法描述Ch7_3.cNeusoft Group Ltd.Date: 31 七月 20241 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 1822 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 5322 48 861 7 13索引表查38Neusoft Group Ltd.Date: 31 七月 2024ASL最大最小两者之间表结构有序表、无序表 有序表分块有序表存储结构顺序存储结构线性链表顺序存储结构 顺序存储结构线性链表查找方法比较顺序查找折半查找分

27、块查找Neusoft Group Ltd.Date: 31 七月 2024排序排序排序定义将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序Neusoft Group Ltd.Date: 31 七月 2024交换排序冒泡排序排序过程将第一个记录的关键字与第二个记录的关键字进行比较，若为逆序r1.keyr2.key，则交换；然后比

28、较第二个记录与第三个记录；依次类推，直至第n-1个记录和第n个记录比较为止第一趟冒泡排序，结果关键字最大的记录被安置在最后一个记录上对前n-1个记录进行第二趟冒泡排序，结果使关键字次大的记录被安置在第n-1个记录位置重复上述过程，直到“在一趟排序过程中没有进行过交换记录的操作”为止Neusoft Group Ltd.Date: 31 七月 20241.3 1.3 排序、查找排序、查找(1)(1)排序排序常用的排序方法冒泡排序程序:voidBubbleSort(inta,n)inti,j;intx;for(i=1;in;i+)for(j=0;jaj+1)/进行交换x=aj;aj=aj+1;aj+

29、1=x;Neusoft Group Ltd.Date: 31 七月 2024插入排序插入排序直接插入排序排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序算法描述Neusoft Group Ltd.Date: 31 七月 2024例49 38 65 97 76 13 27i=2 38 (38 49) 65 97 76 13 27i=3 65 (38 49 65) 97 76 13 27i=4 97 (38 49 65 97) 76 13 27i=5 76 (38 49 65 76 97) 13 27i=6 13

30、 (13 38 49 65 76 97) 27i=1 ( )i=7 (13 38 49 65 76 97) 2727jjjjjj977665493827 (13 27 38 49 65 76 97)排序结果：Neusoft Group Ltd.Date: 31 七月 2024折半插入排序排序过程：用折半查找方法确定插入位置的排序叫例i=1 (30) 13 70 85 39 42 6 20i=2 13 (13 30) 70 85 39 42 6 20i=7 6 (6 13 30 39 42 70 85 ) 20.i=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20

31、(6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sjmi=8 20 (6 13 30 39 42 70 85 ) 20sji=8 20 (6 13 20 30 39 42 70 85 )Neusoft Group Ltd.Date: 31 七月 2024算法描述Ch8_2.cNeusoft Group Ltd.Date: 31 七月 20241.3 1.3 排序排序 (2)(2)常用的排序方法选择排序程序:voidSelectSort(inta,intn)inti,j,k;intxfor(i=1;in;i+)/进行n-1次

32、选择和交换k=i-1;for(j=i;jn;j+)if(ajak)k=j;x=ai-1;ai-1=ak;ak=x; Neusoft Group Ltd.Date: 31 七月 2024选择排序简单选择排序排序过程首先通过n-1次关键字比较，从n个记录中找出关键字最小的记录，将它与第一个记录交换再通过n-2次比较，从剩余的n-1个记录中找出关键字次小的记录，将它与第二个记录交换重复上述操作，共进行n-1趟排序后，排序结束Neusoft Group Ltd.Date: 31 七月 2024快速排序基本思想：通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字

33、小，则可分别对这两部分记录进行排序，以达到整个序列有序排序过程：对rst中记录进行一趟快速排序，附设两个指针i和j，设枢轴记录rp=rs，x=rp.key初始时令i=s,j=t首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换重复上述两步，直至i=j为止再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止Neusoft Group Ltd.Date: 31 七月 2024例初始关键字： 49 38 65 97 76 13 27 50 ijxji 完成一趟排序： ( 27 38 13) 49 (76 97

34、65 50) 分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97) 快速排序结束： 13 27 38 49 50 65 76 974927ijijij4965ji1349ij4997ijNeusoft Group Ltd.Date: 31 七月 2024希尔排序特点子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列希尔排序可提高排序速度，因为分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序增量序列取法无除1以外的公因子最后一个增量值必

35、须为1Neusoft Group Ltd.Date: 31 七月 2024希尔排序希尔排序(缩小增量法缩小增量法)排序过程：先取一个正整数d1n，把所有相隔d1的记录放一组，组内进行直接插入排序；然后取d2d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止Neusoft Group Ltd.Date: 31 七月 2024第二部分第二部分 问题与习题问题与习题Neusoft Group Ltd.Date: 31 七月 2024问题问题 Q1. 为了描述并解决先进先出特征的问题，我们一般会采用考虑以下哪种数据结构A,队列B,栈C,树D,二叉树Q2.为了描述并解决先进后出特征的问题，我们一般会采用考虑以下哪种数据结构（）。A,队列B,栈C,树D,二叉树Q3.对线性表进行二分法查找，其前提条件是A,线性表以顺序方式存储，并且按关键码值排好序B,线性表以顺序方式存储，并且按关键码值的检索频率排好序C,线性表以链接方式存储，并且按关键码值排好序D,线性表以链接方式存储，并且按关键码值的检索频率排好序Neusoft Group Ltd.Date: 31 七月 2024习题习题题目10详细参见习题集。Neusoft Group Ltd.Date: 31 七月 2024谢谢！