同上篇,单链表,头指针存储链表长度.查找和删除分别有根据数据或节点位置来处理
#include <iostream> using namespace std; typedef struct DbNode{ int data; DbNode *Left; DbNode *Right; }DbNode; DbNode *DbCreate(){ DbNode *head = new DbNode, *p, *q; head -> data = 0; head -> Left = head -> Right = NULL; p = head; for( int i = 0; i < 10; ++i ){ q = new DbNode; q -> data = i; q -> Left = q -> Right = NULL; head -> data++; p -> Right = q; q -> Left = p; p = q; } return head; } void DbPrint( DbNode *head ){ DbNode *p = head -> Right; if( head == NULL ) return; while( p != NULL ){ cout << p -> data; p = p -> Right; } cout << endl; } int DbLen( DbNode *head ){ DbNode *p = head -> Right; int len = 0; while( p != NULL ){ len++; p = p -> Right; } return len; } DbNode *DbSeach1( DbNode *head, int data ){ if( head == NULL ){ return NULL; } DbNode *p = head -> Right; while( p != NULL ){ if( p -> data == data ) break; p = p -> Right; } return p; } DbNode *DbSeach2( DbNode *head, int pos ){ if( pos == 0 ) return head; DbNode *p = head; while( p -> Right!= NULL && pos-- ){ p = p -> Right; } if( pos != 0 ){ return p; } else{ cout << "error" << endl; return NULL; } } DbNode *DbInsert( DbNode *head, int pos, int data ){ DbNode *q = new DbNode; q -> data = data; q -> Left = q -> Right = NULL; DbNode *p = DbSeach2( head, pos ); if( pos != NULL ){ head -> data++; q -> Right = p -> Right; p -> Right -> Left = q; q -> Left = p; p -> Right = q; } return head; } DbNode *DbDelete( DbNode *head, DbNode *q ){ DbNode *p = q -> Left; if( p == NULL ){ head -> Right = q -> Right; q -> Right -> Left = head; } else if( q -> Right == NULL ){ p -> Right = NULL; } else{ head ->data --; q -> Right -> Left = p; p -> Right = q -> Right; } return head; } DbNode *DbDelete2( DbNode *head, int pos ){ DbNode *q = DbSeach2( head, pos ); head = DbDelete(head, q ); delete( q ); return head; } DbNode *DbDelete1( DbNode *head, int data ){ DbNode *q; while( ( q = DbSeach1(head, data ) ) != NULL ){ head = DbDelete(head, q ); delete( q ); } return head; } int main() { //建立双链表(带头) DbNode *head = DbCreate(); //求链表长度,头节点存储数据已经 int Len = DbLen( head ); cout << Len << endl; DbPrint( head ); int m, n; cin >> m; //按照查找数据m DbNode *temp = DbSeach1( head, m ); cout << temp -> data << endl; cin >> m; //按照位置查找 temp = DbSeach2( head, m ); cout << temp -> data << endl; cin >> m >> n; //插入数据 temp = DbInsert( head, m, n ); DbPrint( temp ); cin >> m; //根据数据删除 temp = DbDelete1( head, m ); DbPrint( temp ); cin >> m; //根据节点删除 temp = DbDelete2( head, m ); DbPrint( temp ); return 0; }