第11章-常见的数据结构-教学PPT181127.pptx

单击此处编辑母版标题样式,编辑母版文本样式,第二级,第三级,第四级,第五级,2018-11-27,#,第,11,章 常见的数据结构,链表,栈,队列,11.1,链表,链表,是线性表的一种。线性表是由具有相同特性的数据元素组成的一个有限序列，在,C,语言中，线性表有顺序存储和链式存储两种结构，其中以顺序形式存储的线性表称为顺序表，以链式存储的线性表称为链表,。,11.1,链表,C,语言中的数组、字符串都可视为存储简单数据的顺序表，顺序表必须占用一整块事先分配好的、大小固定的存储空间，这不利于内存空间管理，因此在对数据灵活性要求较高的程序中，一般会使用链表存储数据。,11.1.1,链表概述,根据,其逻辑结构，链表通常被分为,单链表,、,双向链表,、,循环链表,等，其中单链表的结构最为,简单,。,11.1.1,链表概述,链表,的每个节点都包含两个部分：存储元素本身的,数据域,和存储下一个结点地址的,指针域,。,如果节点中只有指向后继节点的指针，那么这些节点组成的链表称为单向,链表,。,11.1.1,链表概述,链表,可,进行,的基本,操作,如下：,创建,-,createList,(),：创建链表，并将链表初始化为空；,插入,-insertNode(),：向链表中插入一个节点；,删除,-delNode(),：删除链表其中的某一个节点；,遍历,-printList(),：获取定义链表中存数的数据,。,11.1.2,链表的结构,链表,节点声明如下：,typedef struct linkNode,int data;,struct linkNode*next;,ListNode,pHead;,左侧代码,以,结构体的形式声明了链表节点,ListNode,、,pHead,，该节点包含两个成员，其中成员,data,为数据域，可用于存储整型数据；成员,next,为指针域，用于存储指向下一个节点的指针。使用此结构定义的链表头指针,pHead,的数据域可用于存储链表长度。,11.1.3,链表的实现,1,、创建链表,若要使用链表，需在声明节点之后先创建链表，并对链表初始化。链表的创建实质上就是头节点的创建，若创建一个空链表，则链表头节点的指针应指向,NULL,，数据域存储的链表长度应为,0,。,11.1.3,链表的实现,pHead,*createList(),/,创建头,指针,pHead*ph=(ListNode*)malloc(sizeof(ListNode);,ph-,data=0;,/,初始化链表长度,ph-next=NULL;,/,初始化头指针指向,return ph;,11.1.3,链表的实现,2,、插入节点,单,链表通过节点的指针域来记录下一个节点的位置，从而实现所有节点的连接，因此，当插入一个新元素时，修改节点指针域的指向关系，再修改链表头节点中链表的长度，使其值加,1,即可。向链表中插入节点的常用方式有,头插法,和,尾插法,两种。,11.1.3,链表的实现,（,1,）头插法,头,插法是向链表头部插入新元素，即将新元素插入链表头节点之后。,11.1.3,链表的实现,（,1,）头插法,此,操作分为如下两步：,使新节点的指针指向头节点之后的节点（空链表中即指向,NULL,，非空链表中指向,head-,next,）；,使头节点指针指向新,节点。,11.1.3,链表的实现,int,insertHead(pHead*ph,int data,),/,创建新节点,ListNode*newNode=(ListNode*)malloc(sizeof(ListNode);,if(NULL=newNode),return-1;,newNode-data=data;,newNode-,next=ph-next,;,/,插入新,节点,ph-next=newNode;,ph-,data,+;/,链表长度加,1,return 0;,11.1.3,链表的实现,（,2,）尾插法,尾,插法即将待插入节点插入到最后一个节点之后，使得插入节点成为尾节,点,。,11.1.3,链表的实现,（,2,）尾插法,与,头插法不同的是，使用尾插法向链表中插入新节点时，需先找到链表的尾节点，之后才能执行插入操作。使用尾插法插入新元素的链表,如下图。,11.1.3,链表的实现,int,insertTail(pHead*ph,int data,),pHead*p=ph;,while,(p-next!=NULL,),/,找到尾节,点,p=p-next,;,ListNode,*newNode=(ListNode*)malloc(sizeof(ListNode);,if(NULL=newNode),return-1,;,newNode-data=data;,newNode-next=NULL,;,/,插入新,节点,p-next=newNode;,ph-,data,+;/,链表长度加,1,return 0,;,11.1.3,链表的实现,3,、删除节点,要,删除单链表中的元素，只需要使该元素前驱节点（当前节点的上一个节点）中的指针指向该元素的后继节点（当前节点之后的节点），释放该节点占用的内存空间，再使链表长度减,1,即可。,11.1.3,链表的实现,3,、删除节点,删除节点的,操作,分为如下两步：,（,1,）前驱节点指针保存删除节点的后继,节点；,（,2,）释放指针保存删除节点的内存,空间。,删除第二个元素,67,后的新链表,如,下图,。,11.1.3,链表的实现,3,、删除节点,单,链表只能根据当前节点的,next,指针找到后继节点，不能由当前节点找到其前驱节点；前驱节点指向后继节点后，亦无法利用前驱节点访问已删除的节点,。,综上所述，,在,执行删除操作之前，应先找到并记录待删除节点和其前驱节点，释放删除节点后，前驱节点指针域保存删除节点的后继节点地址。,11.1.3,链表的实现,int,delNode(pHead*ph,int pos,),pHead,*p=ph,;,/,判断链表是否为,空,if,(NULL=p-next,),printf,(,链表为空,n);,return,-1,;,/,判断位置是否,合理,int,len=ph-data,;,if(poslen,),printf,(,位置错误,n);,return,-2,;,/,找到并记录要删除的节点及其前驱节点,ListNode,*pre=ph;,for,(int i=0;i next,;,pre-,next=p-next;,ph-,data-;,free(p,);,return,0;,11.1.3,链表的实现,4,、遍历链表,遍历,链表即逐个访问链表节点，读取节点中存储的数据。在代码中可在循环中移动链表指针，实现,遍历,。,void,printList(pHead*ph),pHead,*p=ph;,while,(p-next!=NULL),p,=p-next;,printf,(%3d,p-data);,11.1.3,链表的实现,5,、获取链表长度,创建,的链表头节点中存放了链表长度，因此只需访问链表头节点的数据域，便可获取链表长度。,int,getLength(pHead*ph),return ph-data;,11.2,栈,洗碗,时，将洗好的碗一个叠一个地摆放在橱柜中；用碗时，再将碗逐个取下。摆放碗时是由下而上依次放置，而取碗时是自顶向下逐个选取。,11.2,栈,如,上述这种现象，也就是先放入的东西后被取到，后放入的东西优先被取到，我们认为其遵循“后进先出”原则，在数据结构中也有一种数据结构遵循这个规则，它就是,栈（,stack,）,。,11.2.1,什么是栈,栈,也是一种线性表，但它是受到限制的线性表。像之前我们学习链表，它可以在任意位置进行插入、删除操作，而栈，类似于盛放碗的碗橱，仅允许在一端进行这些,操作,。,11.2.1,什么是栈,栈,中允许执行插入和删除操作的一端称为,栈顶,（,top,），在栈顶层的元素称为,栈顶元素,；不允许执行插入和删除操作的一端称为,栈底,。向一个栈中插入新元素又称为,入栈、压栈,，入栈之后该元素被放在栈顶元素的上面，成为新的栈顶元素；从一个栈中删除元素又称为,出栈、弹栈,，是把栈顶元素删除，使其相邻元素成为新的栈顶元素。,11.2.1,什么是栈,执行,入栈操作,时，会先将元素插入到栈中，然后按照数据入栈的先后顺序，从下往上依次排列。每当插入新的元素时，栈顶指针就会向上移动，指向新插入的元素,。,执行,出,栈,操作,时,，,栈顶的元素会被先弹出，接着按照后进先出的原则将栈中的元素弹出。弹出栈顶元素后，栈顶指针就向下移动，指向原栈顶下面的一个元素，这个元素就成为了新的栈顶元素。,11.2.1,什么是栈,当,栈已满时，不能继续执行入栈操作。同理，栈为空时，也不能继续执行出栈操作。,11.2.1,什么是栈,若要,从栈中获取元素，只能通过栈顶指针取到栈顶元素，无法取得其它元素。例如在图,11-10,中，,an,没有被弹出时，无法读取到下面的元素。,注 意,11.2.1,什么是栈,栈,的常用操作如下：,Create,(),：创建栈（初始化栈）；,Push,(),：入栈；,isEmpty,(),：判空；,Pop,(),：出栈；,getTop,(),：获取栈顶元素,。,Destory,(),：销毁栈。,11.2.2,栈的链式存储与实现,使用,链式结构存储的栈简称链栈，它与链表的存储结构相同，都用指针来建立各节点之间的逻辑关系。但为,方便,实现栈的操作，链栈中特别设置了栈顶指针,top,来记录栈顶元素。,11.2.2,栈的链式存储与实现,1,、链栈的存储结构,使用,struct,关键字声明链栈的节点和链,栈,。,/,节点结构,typedef,struct,Node,int,data;,/,数据,struct,Node*next;,/,指针,pNode,;,/,栈结构,typedef struct Stack,pNode,*top;,/,栈顶元素指针,int,size;,/,栈大小,LinkStack;,11.2.2,栈的链式存储与实现,2,、创建链栈,LinkStack,*Create(),/,创建,栈,LinkStack*lstack=(LinkStack*)malloc(sizeof(struct Stack);,if(NULL=lstack,),printf(,创建失败,n);,return NULL,;,lstack-top=NULL;,lstack-size=0;,return lstack,;,11.2.2,栈的链式存储与实现,2,、创建链栈,Create,(),函数中首先定义了栈指针,lstack,，并为该指针开辟空间，其次对指针进行判断，若指针为,NULL,，说明地址开辟失败，打印“创建失败”并返回,NULL,；若指针不为,NULL,，对栈指针进行初始化：使栈顶指针,lstack-top,指向,NULL,，将栈的大小,lstcak-size,设置为,0,。初始化完成后返回栈指针，栈创建成功。,11.2.2,栈的链式存储与实现,3,、入栈,入,栈操作的实现原理与链表中头插法的实现原理相同,int,Push(LinkStack*lstack,int val,),pNode*node=(pNode*)malloc(sizeof(struct Node);,if(NULL=,node),return,-1;,node-data=val;,node-next=lstack-top;,/,入栈,lstack-top=node;,/,更新栈顶指针,top,lstack-size+;,return 0,;,11.2.2,栈的链式存储与实现,3,、入栈,函数接收链栈和一个整型数据作为参数。,Push(),函数中首先创建了节点类型的指针,node,，并为该指针开辟了存储空间，其次对该指针进行判断，若指针为,NULL,，说明内存开辟失败，返回,-1,；若指针不为,NULL,，先使用参数,val,接收的数据为新节点的数据域,node-data,赋值，使用栈顶指针为新节点的指针域赋值，再更新栈顶指针，使其指向新节点，最后使栈的大小加,1,，入栈完成。,11.2.2,栈的链式存储与实现,4,、,出,栈,只有,栈不为空时才能出栈，因此在出栈之前一般需先对栈进行判空判断。当栈顶元素指向空或栈的大小为,0,时，说明栈为,空,。,int,IsEmpty(LinkStack*lstack)/,判断栈是否为空,if(lstack-top=NULL|lstack-size=0),return 1;,return 0;,11.2.2,栈的链式存储与实现,4,、,出,栈,int,Pop(LinkStack*lstack),if(IsEmpty(lstack,),return-1;,/,判断栈是否为,空,pNode*node=lstack-top;,lstack-top=lstack-top-next;,/,从栈中删除元素,int topData=node-data;,free(node);,/,释放,空间,lstack-,size-;,/,长度减,1,return topData,;,11.2.2,栈的链式存储与实现,因为,在返回之前原栈顶已被销毁，所以在调用,free(),函数释放空间之前先使用变量,topData,接收原栈顶的数据。,注 意,11.2.2,栈的链式存储与实现,5,、获取栈顶元素,获取,栈顶元素即读取栈顶节点中存储的数据，此操作与出栈操作不同，它不会删除节点。,/,获取栈顶,元素,int,getTop(LinkStack*lstack),if(lstack-size=0),return NULL;,return lstack-top-top;,11.2.2,栈的链式存储与实现,6,、清空栈,清,空栈即使栈中元素依次出,栈,。,void,Clear(LinkStack*lstack),/,只要栈不为空就删除栈顶元素,while,(lstack-size0),Pop(lstack);,printf(,栈清空成功！,n);,11.2.2,栈的链式存储与实现,7,、销毁栈,销毁,栈是指释放栈所占据的所有空间。因为前面的代码为栈和栈中各个节点都开辟了空间，所以在销毁栈时需要先依次销毁栈中节点，再销毁栈本身。,void,Destory(LinkStack*lstack,),Clear(lstack,);,/,先清空,free(lstack);,/,再销毁,printf(,栈销毁成功！,n);,11.2.2,栈的链式存储与实现,栈,应在所有节点都销毁之后销毁。,注 意,11.3,队列,队列,是只允许在表的一端进行插入，在另一端进行删除的线性表，它遵循的是“先进先出”原则。,11.3.1,什么是队列,在,生活中，大家肯定都有过排队买票的经历，在排队买票时，排在前面的人先买到票离开排队的队伍，然后轮到后面的人买；如果又有人来买票，就依次排到队尾。买票的过程中，队伍中的人从头到尾依次出列。,11.3.1,什么是队列,像,排队这样，先来的先离开，后来的排在队尾后离开，我们称之为“先进先出”（,First In First Out,，简称,FIFO,）原则。在数据结构中，也有一种数据结构遵循这一原则，那就是队列（,Queue,）。,11.3.1,什么是队列,队列,和栈一样，也是一种受限制的线性表，它只允许在一端进行插入操作，在另一端进行删除操作。其中允许删除的一端称为队头（,front,），允许插入的一端称为队尾（,rear,）。向队列中插入元素称为入队，从队列中删除元素称为出队。,顺序,队列,11.3.1,什么是队列,队列,中会有一个指针指向队头，这个指针称为,队头指针,。当有元素出队时，队头指针向后移动，指向下一个元素，下一个元素成为新的队头元素（类似于栈的栈顶指针）。,队列,中也会有一个指针指向队尾，称为,队尾指针,，队尾指针是指向最后一个元素之后的空指针。当有元素需要入队时，就插入到队尾指针所指位置处，插入之后，队尾指针向后移动，指向下一个空位。,11.3.1,什么是队列,队列,常见操作：,Create,(),：创建队列；,Push,(),：入队；,Out,(),：出队；,getLength,(),：获取队列长度；,getHead,(),：获取队头元素；,Clear,(),：清空队列；,Destory,(),：销毁队列。,11.3.2,链式队列的存储与实现,使用,链表存储的队列称为链式队列，链式队列中同样包含队头指针,front,和队尾指针,rear,。为方便理解和使用链队，通常会为链队增加一个头节点，此时需要注意的是，链式队列的队头指针,front,指向头节点，队尾指针,rear,指向的是链表中的最后一个节点。,11.3.2,链式队列的存储与实现,1,、链式队列的存储结构,/,链队节点,typedef struct Node,int,data;,/,数据,域,struct,Node*next;,/,指针域,pNode;,typedef,struct Queue,/,链队,结构,pNode,*front;,/,队头指针,pNode,*rear;,/,队尾指针,int,length;,/,队列长度,LQueue;,11.3.2,链式队列的存储与实现,2,、链队的实现,链队的常用操作包括创建、入队、出队、清空队列和销毁队列，在讲解这些操作的实现方法之前，先来了解在发生插入、删除操作时链队中各指针的变化,情况,。,11.3.2,链式队列的存储与实现,2,、链队的实现,(,a)(d),依次表示：空队列、元素,a1,入队、元素,a2,入队、元素,a1,出队,。,空,队列的队头指针,front,和队尾指针,rear,都指向队列的头节点。,向,空队列中插入新节点后，队头指针,front,和队尾指针,rear,都发生变化，指向新插入的节点,。,11.3.2,链式队列的存储与实现,2,、链队的,实现,向,非空队列中插入新节点后，只有队尾指针,rear,发生变化，指向新节点，队头指针,front,无需变化。,出,队时队头指针,front,变化，指向第二个元素，第一个元素所占节点空间被释放。,11.3.2,链式队列的存储与实现,（,1,）创建链队,LQueue,*Create(),/,创建队列,/,为头结点分配,空间,LQueue,*Lq=(LQueue*)malloc(sizeof(LQueue,);,if,(NULL=Lq,),printf,(,创建失败,n);,return,NULL,;,Lq-,front=Lq;,Lq-,rear=Lq;,Lq-,length=0;,return,Lq,;,11.3.2,链式队列的存储与实现,Create(),函数,先,创建了队列头节点,Lq,，并为其分配空间，其次对指针进行判断，若指针为,NULL,，说明内存开辟失败，打印“创建失败”并返回,NULL,；若指针不为,NULL,，使队头指针和队尾指针都指向头节点，并初始化队列长度为,0,。最后将队列头节点指针返回。,11.3.2,链式队列的存储与实现,（,2,）入队,由于,队列为空与非空时的操作不完全相同，在入队之前需先判断队列是否为,空,。,/,判断队列是否为空,int,IsEmpty(LQueue*Lq,),if(Lq-length=0),return 1;,return 0;,11.3.2,链式队列的存储与实现,（,2,）入队,入队,操作的原理与使用尾插法向链表中插入元素的原理相同，当然新节点入队后还需要修改队头指针和队尾指针的指向：若队列为空，新节点入队后，应使队头和队尾指针分别指向新节点；若队列不为空，新节点入队后只需使队尾指针指向新节点即可。,11.3.2,链式队列的存储与实现,void,Insert(LQueue*Lq,int val),/,入队,/,创建并初始化新节点,pNode*pn=(pNode*)malloc(sizeof(pNode);,pn-data=val;,pn-next=NULL;,Lq-rear-next=pn,;,/,插入尾节点,Lq-,rear=pn,;,/,更改尾节点指向,if(IsEmpty(Lq,)/,如果原队列为空，队头指针指向新节点,Lq-front=pn;,Lq-length,+;,11.3.2,链式队列的存储与实现,Insert,(),接收两个参数，其中参数,Lq,用于接收待操作的链表，参数,val,用于接收新节点中存储的数据。,Insert(),函数首先创建新节点，为其开辟地址空间，并将其初始化；其次将新节点插入队尾，并使尾指针指向新节点；之后判断原队列是否为空，若为空则使队头指针也指向新节点；最后使队列长度加,1,，入队操作完成。,11.3.2,链式队列的存储与实现,（,3,）出队,出,队操作实际就是删除队头元素，使队头指针指向第二个元素，并使队列长度减,1,。,11.3.2,链式队列的存储与实现,int,Del(LQueue*Lq,)/,出队,if(IsEmpty(Lq,),printf(,队列为空,n);,return NULL,;,pNode*pTmp=Lq-front,;,/,临时指针，记录待删除节点,Lq-front=pTmp-next;,int delData=pTmp-data,;,/,记录待删除节点中的元素,free(pTmp);,Lq-length-;,return delData,;,11.3.2,链式队列的存储与实现,Del,(),接收待操作的链表作为参数，并返回待删除节点中的元素。,Del(),函数首先对队列进行判断，若队列为空，无需删除；若队列不为空，先定义临时指针记录队头节点，其次修改队头指针使其指向第二个节点，然后定义变量,delData,记录待删除节点中存储的元素，之后释放待删除节点占用的存储空间，使队列长度减,1,，最后返回已删除节点中存储的数据，出队操作完成。,11.3.2,链式队列的存储与实现,（,4,）清空队列,清空队列是使队列中的节点依次出,队,。,void,Clear(LQueue*Lq),/,将队列,Lq,清空,while(Lq-length),Del(Lq);,printf(,队列已经清空！,n);,11.3.2,链式队列的存储与实现,（,5,）销毁队列,队列,在销毁之前应先被清空，之后再释放队列头节点占用的,空间,。,void,Destory(LQueue*Lq,)/,销毁,Clear(Lq);,/,清空,free(Lq);,/,销毁头节点,printf(,队列已销毁！,n);,11.4,阶段案例,机器运算,一、案例描述,计算机在对数据进行运算时,，,会先将运算表达式转换成逆波兰表达式。逆波兰表达式是一种不需要括号的后缀表达方式，进行转换时数据会被保存在栈中，当需要计算时，再利用栈先进后出的特点来进行字符的匹配检查以及表达式的计算。例如表达式“,1+3*,（,2+5,）”在计算机中会先被转换为“,1325+*+,”再进行运算。,11.4,阶段案例,机器运算,一、案例描述,本,案例要求编写程序实现以下目标：,1,、,将,运算式（操作数为,09,）转换为波兰表达式；,2,、,根据,波兰表达式计算运算式的结果。,11.4,阶段案例,机器运算,二、案例分析,1,、将运算式转换为波兰表达式,将运算式转换为逆波兰表达式即在遍历过程中将中缀表达式转换为后缀表达式，此过程中数据使用栈来存储，且遵循以下规则,：,对于数字：直接输出；,11.4,阶段案例,机器运算,二、案例分析,对于,符号,：,左括号,：进栈，不管栈中是否有元素；,运算符,：若此时栈为空，直接进栈；,若,栈中有元素，则与栈顶符号进行优先级比较：,若,新符号优先级高，则新符号进栈（默认左括号优先级最低，直接入栈）,；,11.4,阶段案例,机器运算,二、案例分析,若,新符号优先级低，将栈顶符号弹出并输出，之后使新符号进栈；,右括号,：不断将栈顶符号弹出并输出，直到匹配到左括号，再接着读取下,一,个,符号；须注意，左右括号匹配完成即可，并不将其输出,；,遍历,结束：将栈中所有的符号弹出并输出。,11.4,阶段案例,机器运算,二、案例分析,2,、后缀表达式的运算,对于,数字：进栈；,对于,符号：,从栈中弹出右操作数；,从栈中弹出左操作数；,然后,根据符号进行运算，将运算结果压入栈中；,遍历,结束，栈中唯一数字就是运算结果。,11.4,阶段案例,机器运算,三、案例实现思路,根据,案例分析中的规则，可将程序代码模块化为,5,个功能函数和一个主函数。,（,1,）符号判断,判断读取到的符号是数字、运算符还是左括号或右括号。,（,2,）优先级比较,比较符号的优先级，方便确定新符号进栈时的操作。,11.4,阶段案例,机器运算,三、案例实现思路,（,3,）中缀转后缀,接收中缀表达式，根据中缀转后缀的规则，调用符号判断函数和优先级比较函数实现表达式的转换，并返回转换结果。,（,4,）运算符操作,根据不同的运算符执行不同的操作，并返回操作结果。,11.4,阶段案例,机器运算,三、案例实现思路,（,5,）后缀表达式运算,接收后缀表达式，根据后缀表达式的运算规则，调用符号判断函数、运算符操作函数对后缀表达式进行运算，并返回运算结果。,（,6,）主函数,主函数中调用中缀转后缀的函数，为其传入中缀表达式，记录其返回结果；调用后缀表达式运算函数，将中缀转后缀的结果作为参数传入该函数，接收该函数的返回值并打印。,11.5,本章小结,本章,主要讲解了,C,语言中的,3,种基本数据结构，分别是链表、栈和队列。通过本章的学习，读者应该能够掌握这,3,种数据结构的存储原理、定义以及常用操作。掌握本章的内容将有助于优化程序中的数据存储，提高程序的运行效率。,