C++(day15)C++实务精选罕见资源大集合.docx

C++ 笔记 第十五天 2007 年 4 月 11 日 1、在头文件中 #ifndef _ACCOUNT_ //预编译选项，表示如果没有定义这个宏#define _ACCOUNT_ //创建以_ACCOUNT_命名的宏 并声明类 #endif 2、链表 解决数组必须连续存储的问题 链表是可以不连续的，通过每个节点的指针连接 节点中一部分空间用于存放数据，另一部分是一个指向下一个节点的指针 每个节点都是一个结构 struct node{ int data; //存储数据 node* next; //指向下一个节点的指针，是自己这个结构的类型 } 尾节点 --- 链表中的最后一个节点 --- 指针指向 NULL 头节点 --- 要访问链表中的元素，必须要知道头节点的位置 把地址放在一个指针中 --- 头指针指向头节点，只是一个指针 --- 是 必须存在的元素 对链表的常见操作 --- 增删改查 链表与数组的区别 数组：空间必须连续，数组是定长的，插入和删除需要遍历整个数组，效率不高。取元素可直接使用下标，访问方便 链表：空间在内存中不必连续，通过指针连接 链表是不定长的，可以随时添加新节点，通过指针关联 对链表的插入删除，不需要移动节点位置，只对指针操作即可访问元素，要从头指针开始遍历 当数据需要频繁的插入删除的时候，需要使用链表当改动不大，查询频繁的时候，使用数组 潜规则 ： 能用数组就不用链表 ====================================================================== 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){ //找到被删除