数据结构 (2).ppt

《数据结构 (2).ppt》由会员分享，可在线阅读，更多相关《数据结构 (2).ppt（30页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Main IndexContents1Main IndexContentsList List 列表类最基本的线性表列表类最基本的线性表存储结构存储结构存储结构存储结构数组数组数组数组-直接访问直接访问直接访问直接访问O(1)O(1)O(1)O(1)，插入删除不方便，插入删除不方便，插入删除不方便，插入删除不方便O(nO(nO(nO(n)intintintint mySizemySizemySizemySize;T;T;T;T myArrayCAPACITYmyArrayCAPACITYmyArrayCAPACITYmyArrayCAPACITY;动态数组直接访问动态数组直接访问动态数组直接访问

2、动态数组直接访问O(1),O(1),O(1),O(1),插入删除不方便插入删除不方便插入删除不方便插入删除不方便O(nO(nO(nO(n)intintintint mySizemySizemySizemySize;intintintint myCapacitymyCapacitymyCapacitymyCapacity;T*T*T*T*myArraymyArraymyArraymyArray;链表（链表（链表（链表（LinkedListLinkedListLinkedListLinkedList）顺序访问）顺序访问）顺序访问）顺序访问O(nO(nO(nO(n),),),),插入删除插入删除插入

3、删除插入删除 方便方便方便方便O(1)O(1)O(1)O(1)Lecture 3 Linked Lists Linked Lists1Main IndexContents2Main IndexContentsAbstract Model of a List Obj.Abstract Model of a List Obj.Node CompositionNode CompositionInserting at the Front of a LLInserting at the Front of a LLDeleting from the Front of a LLDeleting from t

4、he Front of a LLRemoving a Target NodeRemoving a Target NodeHandling the Back of the ListHandling the Back of the ListInserting a Node at a specified PositionInserting a Node at a specified PositionLecture 3 Linked Lists Linked Lists2Main IndexContents3Main IndexContentsLinked List NodesLinked List

5、NodeslEach Node is like a piece of a chainlTo insert a new link,break the chain at the desired location and simply reconnect at both ends of the new piece.3Main IndexContents4Main IndexContentsLinked List NodesLinked List NodeslRemoval is like Insertion in reverse.4Main IndexContents5Main IndexConte

6、ntsNode CompositionNode CompositionlAn individual Node is composed of two parts,a Data field containing the data stored by the node,and a Pointer field that marks the address of the next Node in the list.5Main IndexContentsAbstract Model of a List ObjectAbstract Model of a List Objectdata nextdata n

7、extdata nextdata nullfirst2 0 xbfffaa28first0 xbfffaa200 xbfffaa280 xbfffaa600 xbfffaa804 0 xbfffaa606 0 xbfffaa808 Nullfirst是指向是指向node类型的指针：类型的指针：node*first;first=new node(2,NULL);0 xbfffaa206Main IndexContents7Main IndexContentsNodeNode结点设计结点设计结点设计结点设计Template class node public:T nodeValue;/data h

8、eld by the node node*next;/next node in the list node():next(NULL)node(const T&item,node*nextNode=NULL):nodeValue(item),next(nextNode);7Main IndexContents8Main IndexContents1.1.如何生成链表如何生成链表如何生成链表如何生成链表node*nodeptr1,*nodeptr2;nodeptr1=new node(1,null);nodeptr2=new node(2,null);思考：如何连接两个结点？思考：如何连接两个结点

9、？nodeptr1-next=nodeptr2;nodeptr3=new node(3,null);nodeptr2-next=nodeptr3;8Main IndexContents9Main IndexContents将将1,2,3,4,51,2,3,4,5顺序插入链表顺序插入链表（正向插入）（正向插入）node*nodeptr1,*nodeptr2;for(int i=1;i6;i+)nodeptr1=new node(i,null);nodeptr1?nodeptr1=new node(1,null);for(int i=2;i6;i+)nodeptr2=new node(i,null

10、);nodeptr1-next=nodeptr2;nodeptr1=nodeptr1-next;2.Creating a Linked List2.Creating a Linked List9Main IndexContents10Main IndexContents2.Creating a Linked List2.Creating a Linked List将将1,2,3,4,51,2,3,4,5顺序插入链表顺序插入链表（反向插入）（反向插入）node*front=Null,*newNode;int i;for(i=1;i=5;i+)front=new node(i,front);10M

11、ain IndexContents11Main IndexContents2.Creating a Linked List2.Creating a Linked Listnode*front=Null,*newNode,*back;int i=0;while(i5)if(i=0)front=new node(i,NULL);back=front;elsenewNode=new node(i,NULL);back-next=newNode;back=back-next;i+;/不同的编程风格不同的编程风格11Main IndexContents12Main IndexContents3.1 3.

12、1 Inserting at the Front of a Linked ListInserting at the Front of a Linked List12Main IndexContents13Main IndexContents3.2 Handling the Back of the List3.2 Handling the Back of the List13Main IndexContents14Main IndexContents 3.3 Handling the Back of the List 3.3 Handling the Back of the Listnode*c

13、urr=front;while(curr!=null)curr=curr-next;14Main IndexContents15Main IndexContents3.4 Handling the Back of the List3.4 Handling the Back of the List with back pointer with back pointerThe initial list is empty:front=NULL,back=NULL.15Main IndexContents16Main IndexContentsa.Inserting a node at a.Inser

14、ting a node at back back with a back pointer with a back pointerNode*front,*back,*newNode;newNode=new node(item);If(front!=Null)back-next=newNode;elsefront=newNode;back=newNode;16Main IndexContents17Main IndexContentsb.Inserting a node at b.Inserting a node at front front with a back pointer with a

15、back pointerNode*front,*back,*newNode;newNode=new node(item,front);If(front=Null)back=newNode;front=newNode;17Main IndexContents18Main IndexContents3.5 Inserting and deleting a node3.5 Inserting and deleting a nodeInsert:newNode-next=curr;Prev-next=newNode;Delete:node*curr,*prev;prev-next=curr-next;

16、delete curr;18Main IndexContents19Main IndexContents3.6 Deleting From the Front of a 3.6 Deleting From the Front of a Linked ListLinked Listfrontfront/front=NULLDeleting front of a 1-node listDeleting front of a multi-node list/front=front-next19Main IndexContents20Main IndexContents3.7 Deleting a n

17、ode at 3.7 Deleting a node at frontfront with a back pointer with a back pointerNode*front,*back,*p;If(front!=Null)p=front;front=front-next;if(front=Null)back=Null;delete p:20Main IndexContents21Main IndexContents3.8 Deleting a Linked List3.8 Deleting a Linked Listnode*p;while(front!=Null)p=front;fr

18、ont=front-next;delete p;21Main IndexContents22Main IndexContents4.Traverse a Linked List4.Traverse a Linked List1.1.如何访问尾部元素如何访问尾部元素w while(fronthile(front-next!=Null)-next!=Null)front=front-next;front=front-next;2.2.如何全部遍历如何全部遍历while(frontwhile(front!=Null)!=Null)coutcoutnodeValuenodeValue;front=fr

19、ont=frontfront-next;-next;22Main IndexContents23Main IndexContents5.Removing a Target Node5.Removing a Target Node注意：前驱和当前指针，交替推进注意：前驱和当前指针，交替推进23Main IndexContents24Main IndexContentsTemplateVoid eraseValue(node*front,const T&target)node*curr=front,*prev=Null;bool foundItem=false;while(curr!=Null&!

20、foundItem)if(curr-nodeValue=target)if(prev=Null)front=front-next;elseprev-next=curr-next;delete curr;foundItem=true;elseprev=curr;curr=curr-next;24Main IndexContents25Main IndexContentsErasing nodes in descending order#include#include d_node.h#include d_nodel.h#include d_random.husing namespace std;

21、template node*getMax(node*front);template void eraseValue(node*&front,const T&target);25Main IndexContents26Main IndexContentsErasing nodes in descending orderint main()node*front=NULL,*p;randomNumber rnd;int listCount,i;cout listCount;for(i=0;i listCount;i+)front=new node(rnd.random(100),front);cou

22、t Original List of Values:;writeLinkedList(front,);cout endl;26Main IndexContents27Main IndexContentsErasing nodes in descending ordercout Output in Descending Order:;while(front!=NULL)p=getMax(front);cout nodeValue nodeValue);cout endl;return 0;27Main IndexContents28Main IndexContentsErasing nodes

23、in descending ordertemplate node*getMax(node*front)node*curr=front,*maxPtr=front;while(curr!=NULL)if(maxPtr-nodeValue nodeValue)maxPtr=curr;curr=curr-next;return maxPtr;28Main IndexContents存储池管理：存储池管理：用数组实现链表用数组实现链表node indexdatanext0Mill11Baker22Well33nice-14?5?6?7?29Main IndexContents作业：作业：P263-4,7,12P263-4,7,1230