《The C++ Programming Language》for 达内科技 c++ 课件 及 源码笔记[完美]

C++ 笔记 第十五天 2007年4月11日 1、在头文件中 #ifndef _ACCOUNT_ //预编译选项，表示如果没有定义这个宏 #define _ACCOUNT_ //创建以_ACCOUNT_命名的宏 并声明类 #endif 2、链表 （1）解决数组必须连续存储的问题 链表是可以不连续的，通过每个节点的指针连接 （2）节点中一部分空间用于存放数据，另一部分是一个指向下一个节点的指针 （3）每个节点都是一个结构 struct node{ int data; //存储数据 node* next; //指向下一个节点的指针，是自己这个结构的类型 } （4）尾节点 --- 链表中的最后一个节点 --- 指针指向NULL 头节点 --- 要访问链表中的元素，必须要知道头节点的位置 把地址放在一个指针中 --- 头指针指向头节点，只是一个指针 --- 是必须存在的元素 （5）对链表的常见操作 --- 增删改查 （6）链表与数组的区别 数组：空间必须连续，数组是定长的，插入和删除需要遍历整个数组，效率不高。 取元素可直接使用下标，访问方便 链表：空间在内存中不必连续，通过指针连接 链表是不定长的，可以随时添加新节点，通过指针关联 对链表的插入删除，不需要移动节点位置，只对指针操作即可 访问元素，要从头指针开始遍历 当数据需要频繁的插入删除的时候，需要使用链表 当改动不大，查询频繁的时候，使用数组 潜规则 ： 能用数组就不用链表 ====================================================================== link.h ====================================================================== #ifndef _LINK_ #define _LINK_ using namespace std; class Node{ //节点类 public : int val; //保存数据 Node* next ; //保存下一个节点的地址 Node(){ //构造函数，把指针初始化为NULL next = NULL; } }; class Link{ protected : Node* head; //头指针 public : Link(); ~Link(); void insertTail(int); void insertHead(int); void del(int); int indexOf(int); //查询一个元素的下标 void update(int , int); void disp(); }; #endif ====================================================================== link.cc ====================================================================== #include "link.h" #include <iostream> using namespace std; Link::Link(){ head = NULL; } Link:: ~Link(){//释放空间，从头向尾释放 if(head != NULL){ Node *p = head; head = head->next; //把头节点向后移动 delete p; //抛弃原来的那个头节点 cout << "delete one ... " << endl; } } //尾插入 void Link::insertTail(int v){ Node *p = new Node; p->val = v; if(head == NULL){ head = p; //让新节点的指针指向新节点，即把新节点的地址保存在头指针中 return ; } Node * temp = head ; //用一个临时指针，从头节点开始找到 尾 while(temp -> next != NULL){ //表示temp不是尾节点 temp = temp -> next ; //用temp后面的一个指针为自己赋值，即指向下一个节点 } temp -> next = p; //尾插入，最后一个节点的指针保存新节点的地址 } //头插入 void Link::insertHead(int v){ Node *p = new Node; //创建新节点 p->val = v ; //保存数据 p->next = head; //让新节点的指针和头指针一样指向第一个节点 head = p; //让头节点指向新节点 } void Link::del(int v){ //找到被删除的节点 ， if(head == NULL ){ return ; } if(head -> val == v){ Node *p = head; head = head->next; delete head; } Node *p1 = head->next; //找值相同的一个 Node *p2 = head ; //跟在p1后面 while(p1 != NULL){ if(p1->val == v){ p2->next = p1 -> next; delete p1; break; } p1 = p1->next; p2 = p2->next; } } int Link::indexOf(int v){ //查询一个元素的下标 Node * p = head ; int counter = 0 ; while( p != NULL ){ if( p->val == v ){ return counter ; } p=p->next ; counter++ ; } return -1 ; } void Link::update(int v1 , int v2){ Node * p = head ; while( p != NULL ){ if( p->val == v1 ){ p->val = v2 ; } p = p->next ; } } void Link::disp(){ Node *p = head; while(p != NULL){ cout << p->val << " " ; p = p->next; } cout << endl; } 3、二叉树 每个节点最多只有两个分支的树,它有一个根指针,要指向这棵树的根节点(最顶端的节点). 左子树上的值小于其父节点的值，右子树上的值都大于其父节点上的值。 --- 排序二叉树 （1）周游（遍历） ：先序 --- 中左右 中序 --- 左中右 后序 --- 左右中 （2）非常方便查找 二叉查找树的常见操作: 1) 插入. 示例代码如下: Node* Tree::_insert(int v, Node* r){ //真正实现插入操作,返回插入以后的根 if(r == NULL){ //是一棵空树 （空子树） Node* p = new Node(v); //创建新节点 r = p; //让新节点成为根或者子节点 return r; } if( v < r->val){ //插到左子树上 r->left = _insert(v,r->left); return r; }else{ //插到右子树上 r->right = _insert(v,r->right); return r; } } 2) 查找. 示例代码如下: Node* & find( bnode* & root, const DATA& cd ) { if( root==NULL ) // 如果root节点是空,则为空树 return root; // 返回root指向的地址,即NULL else if( root->data==cd ) // 如果root节点就是要查找的数值 return root; // 返回root指向的地址,为了清晰,和上面的分开写 else if( cd < root->data ) // 如果root节点指向的值大于要查找的值 return find( root->left, cd ); // 返回查找root的左子树返回的地址 else return find( root->right, cd ); // 否则返回查找root的右子树返回的地址 } 3) 删除. 示例代码如下: 被删除的是树根（1）则选择右子树的树根做新树根，左子树可以整个挂在右子树最左侧的一个左节点上 右子树中最左边的一个节点，是最靠近左子树的树根的 （2）让左子树中的最大节点做新树根 Node* _del( int value , Node* r ){ if( r == NULL ){ //删除空树 return r ; } if( r->value == value ){ //删除树根 if(r->left==r->right){ //左右子树都是NULL的情况下 delete r ; return NULL; }else if( r->right == NULL ){ //�