CHAP2线性表(数据结构)讲义.ppt

* 2.双向循环链表的操作 InitDBList (DL ) LocateDBList(DL, i ) LocateDBNode(DL, key) InsertDBNode(DL, i, x ) DeleteDBNode(DL, int i ) CreateDBList (DL ) * void InitDblList (DBLinkList DL ) { //初始化双向循环链表 } // InitDblList DL = new DBLNode; if(DL == NULL ){ cout存储分配错!\n; exit (1); } DL-prior = DL-next = DL ; //表头结点的链指针指向自己 (1)初始化双向循环链表 * DBLNode * LocateDBList( DBLinkList DL, int i ) {//按位查找 } // LocateDBList p=DL-next; j=1; while(p!= DL ji) { p = p-next; j++; } if(p== DL|| ji) return NULL; else return p; (2) 在双向循环链表中按位查找 * DBLNode * LocateDBNode( DBLinkList DL, ElemType key) {//按值查找 } // LocateDBNode p=DL-next; while(p!= DL key!=p-data) p = p-next; if(p== DL) return NULL; else return p ; (3) 在双向循环链表中按值查找 * (4)双向循环链表的前插操作算法 void dinsertbefor(DBLNode *p， ElemType x){ q = new DBLNode; q—data=x; // 数据域 q—prior=p—prior; q—next=p; p—prior—next=q; p—prior=q; } 算法时间复杂度为: O(1) x q b a P * int InsertDblNode(DBLinkList DL, int i, ElemType x ) {//前插法 } // InsertDblNode p = LocateDBList( DL, i ); //指针定位于插入位置 if ( !p ) return ERROR; q = new DBLNode ; //分配结点 q-data = x; q-prior=p-prior; q-next=p; //插入结点 p-prior-next=q; p-prior=q; * (5)双向链表的后插操作算法 void dinsertbefor(DBLNode *p， ElemType x){ q = new DBLNode; q—data=x; q-prior = p; p-next-prior = q; q-next = p-next; p-next = q; } 算法时间复杂度为: O(1) x q b a P * int InsertDblNode(DBLinkList DL, int i, ElemType x ) {//后插法 } // InsertDblNode p = LocateDBList( DL,i-1 ); //指针定位于插入位置 if ( !p ) return ERROR; q = new DBLNode ; //分配结点 q-data = x; q-prior = p; p-next-prior = q; //后插 q-next = p-next; p-next = q;*/ * (6)双向链表的删除操作算法 void ddeletenode(DBLNode *p) { p–prior–next=p–next; p–next–prior=p–prior; delete p; } 算法时间复杂度为: O(1) p-prior-next=p-next; p-next-pri