数据结构第3讲(浙江工业大学).ppt

List 列表类－最基本的线性表 存储结构 １．数组-直接访问O(1)，插入删除不方便O(n) 　　int mySize; T myArray[CAPACITY]; ２．动态数组－直接访问O(1),插入删除不方便O(n) 　　int mySize; int myCapacity; T *myArray; ３．链表（LinkedList）－顺序访问O(n),插入删除 方便O(1) Lecture 3 – Linked Lists Abstract Model of a List Obj. Node Composition Inserting at the Front of a LL Deleting from the Front of a LL Removing a Target Node Handling the Back of the List Inserting a Node at a specified Position Lecture 3 – Linked Lists Linked List Nodes Each Node is like a piece of a chain To insert a new link, break the chain at the desired location and simply reconnect at both ends of the new piece. Linked List Nodes Removal is like Insertion in reverse. Node Composition An 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. Abstract Model of a List Object data next data next data next data null first 2 0xbfffaa28 first 0xbfffaa20 0xbfffaa28 0xbfffaa60 0xbfffaa80 4 0xbfffaa60 6 0xbfffaa80 8 Null first是指向node类型的指针： nodeint *first; first=new nodeint(2,NULL); 0xbfffaa20 Node结点设计 Template typename T class node { public: T nodeValue; // data held by the node nodeT *next; // next node in the list node() : next(NULL) {} node(const T item, nodeT *nextNode = NULL) : nodeValue(item), next(nextNode) {} }; 1.如何生成链表 nodeint *nodeptr1,*nodeptr2; nodeptr1=new nodeint(1,null); nodeptr2=new nodeint(2,null); 思考：如何连接两个结点？ nodeptr1-next=nodeptr2; nodeptr3=new nodeint(3,null); nodeptr2-next=nodeptr3; 将1,2,3,4,5顺序插入链表（正向插入） nodeint *nodeptr1,*nodeptr2; for(int i=1;i6;i++) { nodeptr1=new nodeint(i,null); nodeptr1? } nodeptr1=new nodeint(1,null); for(int i=2;i6;i++) { nodeptr2=new nodeint(i,null); nodeptr1-next=nodeptr2; nodeptr1=nodeptr1-next; } 2. Creating a Linked List 2. Creating a Linked List 将1,2,3,4,5顺序插入链表（反向插入） nodeint *front=Null, *newNode; int i; for(i=1;i=