信息学奥赛NOIP数据结构链表、堆ppt课件.ppt

《信息学奥赛NOIP数据结构链表、堆ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、链表本节内容【单】链表双链表循环链表例题问题导入数组实现的线性表的插入与删除时间复杂度O（n）链表链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于数组线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度。structNode{intelement;Node*next;};intmain(){Nodenode

2、1,node2;node1={1,NULL};node2={2,NULL};Node*p=&node2;node1.next=p;cout<element;}1&node22NULL链表节点结构体#includeusingnamespacestd;structNode{intelement;Node*next;};intmain(){Nodenode[5];for(inti=0;i<5;i++){node[i]={i,NULL};cout<

3、++.h>usingnamespacestd;structNode{intelement;Node*next;};structListTable{Node*head;};链表其实是第一个结点的地址intmain(){Nodenode1,node2;node1={1,NULL};node2={2,NULL};Node*p=&node2;node1.next=p;ListTablelist1={NULL};list1.head=&node1;cout<element;}head2-----------NULL1-----------&no

4、de2插入结点操作代码Nodenode3={3,NULL};//把3插入到1之后（2之前）node3.next=&node2;node1.next=&node3;Node*temp=list1.head;while(temp!=NULL){cout<element;temp=temp->next;}封装成函数list004node*insert_node(node*head,intpos,intdata){node*item=NULL;node*p;item=(node*)malloc(sizeof(node));item->data=data;

5、if(pos==0)//插在head后面{head->next=item;//head后面是itemreturnhead;}p=search_node(head,pos);//获得pos的节点指针if(p!=NULL){item->next=p->next;//item指向原pos节点的后一个节点p->next=item;//把item插入到pos的后面}returnhead;}删除一个结点node*delete_node(node*head,intpos)//删除节点{node*item=NULL;node*p=head->next;if(p=NULL){p

6、rintf("linkisempty!");returnNULL;}p=search_node(head,pos-1);//获得位置pos节点的指针if(p!=NULL&&p->next!=NULL){item=p->next;p->next=item->next;deleteitem;}returnhead;}双链表问题导入如果在高速公路上，路况不熟，还没有导航。我要到正确的服务区。如果我下早了一个服务区，问题不大。如果我下晚了一个服务区，就很头大。思考双链表structNode{Node*prevNode;Node*nextNode;intelement;

7、};//链表结构体，记录了链表的首节点和尾节点指针，以及节点总个数structList{Node*firstNode;Node*lastNode;intlen;};intmain(){Noden1={NULL,NULL,1};Noden2={NULL,NULL,2};Listl1={NULL,NULL,2};l1.firstNode=&n1;l1.lastNode=&n2;n1.nextNode=&n2;n2.prevNode=&n1;//逆序输出链表？}Node*p=l1.lastNode;while(p!=NULL){cout<element;p=

8、p->prevNode;}双链表的插入