数据结构&排序

三、链表，栈，队列，二叉树

（一）链表
(1)链表：由设计为大小合适的小的容器组成，这些容器可以根据需要链接在一起。
      由头指针管理的结点
   数组的缺陷
   动态数组的缺陷
   数组是在编译时分配内存的，所以数组的大小是不可改变的，可是链表是动态的，所以
   可以在需要的时候增加和减小链表的长度。
   （要加长要减短很容易。 链表来源于生活，如火车、 钻石用底座镶嵌连接起来--节点）
   节点中放数据和指向下一个节点的指针：
     --------   -----------   -----------   -----------
     | head |-->|数据|指针|-->|数据|指针|-->|数据|NULL|
     --------   -----------   -----------   -----------
     头指针     头节点          内部节点        尾节点    

   struct Node{
         T data;     //数据
         Node* next; //指向下一个节点，而不是数据
   }；
   若改造成类：
   class Node{
   public:           //加public  或者  设置友元 来提供访问权
         T data;
         Node* next;
   };  
   链表家庭组成：
     头节点： 其工作是管理链表的头。  第一个节点
     尾节点： 最后一个  next==NULL  初始时，头节点的Next指针指向尾节点（既是头，也是尾）。
     内部节点：存放数据类型。  
     头指针：指向头一个节点的指针，只有4byte

(2)链表的特点
   a.非常重要的数据结构  （应用非常广泛）
   b.灵活              数组必须连续存放，而链表不要求连续，只要零碎空间；
   c.比数组节省空间    因为数组可能会浪费原来申请的空间，而链表要多少申请多少；
                       数组必须连续存放，而链表不要求连续，只要零碎空间；
   d.访问比较慢        后续数据必需从头遍历数据才可访问到；
   e.操作比较复杂      通过封装一些函数来解决。

(3)链表的操作
   通常把头指针封装成一个链表类   Node* head; 
  插入
   a.插入第一个节点：
    1).准备节点
       申请空间         Node* p = new Node;
       设置data         p->data = ...;
       设置next=NULL    p->next = NULL;
    2).head指向新节点     head = p;
   b.插入第二个节点：(前插法---新节点总是成为头节点)
    1).准备节点
    2).让新节点的next成员指向旧节点   p->next = head;
    3).让head指向新节点  head = p;
   插入第一个节点也可用以上三个步骤（一般复杂步骤兼容简单步骤）
   头插法优点：只需要与head打交道，效率最高；
         缺点：顺序与插入颠倒了   （应用于栈 再好不过）
   c.插入第二个节点：(后插法)
    1).准备节点
    2).找到尾节点的next成员
    写一个函数来找  返回类型Node*&  （注意：返回的是Node*的引用，才可以修改它）
    3).让它指向新节点
   d.在任意位置插入新节点： (涵盖了前插、后插的通用算法)：         
    1).准备新节点
    2).找到链表中要插入位置的指针pn         
    3).让新节点的next成员指向要指入的位置    p->next = pn;
    4).让找到的指针指向新节点       pn = p;

     对于第2步举个例子，发现规律：
--------   ------------   -----------    ------------   ------------
| head |-->|数据0|指针|-->|数据1|指针|-->|数据2|指针|-->|数据3|NULL|
--------   ------------   -----------    ------------   ------------

     0   pt = head;
     1   pt->next;
     2   pt=pt->next;    pt->next
     3   pt=pt->next;    pt->next
           两次
     ...
     n号 pt=pt->next;    pt->next     //得出结论
           n-1次

    提醒：链表中只有两种的指针：head 和 next
          pt = pt->next 使pt指向pt的下一个节点（前提要有下一个，否则段错误）
    建议：一定要多画图！多画图自己就会有思路
    ---------------------------------------------------------
    查找功能分析步骤：
    1.定义一个指向第一个节点的指针
    2.反复：2.1如果指针为空，找不到数据；
            2.2如果非空，看节点中的数据是否是要找的数据
                         2.2.1  是，找到了
                         2.2.2  不是，让指针指向下一个节点
    函数代码如下：
    int find( T d )
    {
        Node* pt = head;
        int pos = 0;         //记录找到节点编号
        while( pt!=NULL )
        {
             if( pt->data==d )
                 return pos;   //找到返回节点编号
             pt = pt->next;
             ++pos;
        }
             return -1;      //找不到返回无效值
    }
    ---------------------------------------------------------   
    更新功能的步骤分析：
    1.查找数据，取得在链表中的位置
    2.根据位置取得指向节点的指针
    3.通过指针修改节点中的数据

    函数代码如下：
    bool update( T d1, T d2 )
    {
         int pos = find(d1);
         if( pos==-1 )
             return false;
         Node* pt = getp(pos);
         pt->data = d2;
         return true;
    } 
    --------------------------------------------------------- 
    删除功能的步骤分析：
    1.找到要删的数据所在的位置 pos
    2.取得指向要删节点位置的指针 pn
    3.把指针保存一份 pt=pn;
    4.让pn指向下一个节点   pn = pn->next;
    5.释放空间 delete pt;

    函数代码如下：
    bool erase( T d )
    {
         int pos = find(d);
         if( pos==-1 )
              return false;
         Node*& pn = getp(pos);
         Node* pt = pn;
         pn = pn->next;
         delete pt;
         --len;
         return true;
    }
    ---------------------------------------------------------
    取链表头：
    T getHead()
    {
        if( empty())
            return T();
        return head->data;
    }
    取链表尾：
    T getTail()
    {
        if( empty())
            return T();
        return getp(len-1)->data;
    }
    ---------------------------------------------------------
(4)双向链表 （了解）
   多维护了一个指针，可以前后遍历
   struct Node{
        int v;
        Node *prev;
        Node *next;
   };
   以空间换取时间

（二）栈
    （1）LIFO（只要实现这一特征就是栈）
    （2）常用方法：push(),pop(),isempty(),count(),clear(),reset()等
     ( 3 ) 栈的实现: 用数组实现，用链表实现
（三）队列
    （1）FIFO；
    （2）常用方法：insert(),pop()等；
（四）二叉树
  （1）每个节点最多只有两个分支的树,它有一个根指针,要指向这棵树的根节点(最顶端的节点). 左子树上的值小于其父节点的值，右子树上的值都大于其父节点上的值。    ---  排序二叉树
          （2）周游（遍历） ：
       先序  ---  中左右
                       中序  ---  左中右    
                       后序  ---  左右中
          （3）二叉查找树的常见操作:增，删，查，改，遍历；
               主要的思想是迭代；
         （4）非常方便查找

四、常用算法
（一）算法
         有穷性 --- 在保证执行有限步骤之后确定能够结束
         确切性 --- 每条语句具体干什么
         输入输出 --- 所有的算法都有输出，打印屏幕，写文件，写DB
（二）常用的重要的方法（必须掌握下列排序的思想）
      排序
（1）冒泡排序：用得是多轮排序，只比较相邻的数据对。只要发生过交换就要继续，如果没有发生交换排序完成。
规律：每一轮下来都会把最大的一个排好序。
适用于：只有少数是乱序的时候
void sort(){
bool bSwap;//不可以在do里面定义，不然在while()中就不能使用了
do{
bSwap=false;//是否交换过？
for(int i=0;i<n-1;i++){
if(a[i]>a[i+1]){
int t=a[i];
a[i]=a[i+1];
a[i+1]=t;
bSwap=true;//交换过
}
}
n--;//优化,因为每一次最大的都会排好序，所以可以少比一个数。
}while(bSwap); //只要发生过交换就再来一次
}
        时间7秒10240个数据
int main(){
const int N=1024;
int a[n];
for(int i=0;i<N;i++)
a[i] = N-i;//保存的是1
long t1=time(NULL);
sort(a,N);
long t2=time(NULL);
cout<<"time:"<< t2-t1 <<endl;
for(int i=0;i<10;i++)
cout<<a[i]<<' ';
cout<<endl;
}

（2）选择排序：每次都找最大（最小）的元素放在应该放的位置
1反复i=0 i--n-1
1.1在未排序的数据中找到最小的元素。
1.1.1反复（j=i-n-1）,以前做过递归选择排序
1.2把最小元素，跟下标为i的元素交换。

写void sort(int *a,n);对数组中N个元素排序。用选择排序法。
void sort(int *a , int n){
for(int i=0;i<n-1;i++){
int pos=i;
for(int j=i;j<i-n-1;j++){
if(a[j]<a[pos]){
pos=j;
}
}
int p=a[pos];
a[pos]=a[i];
a[i]=p;
}
}

#include<ctime>
int main(){
const num=10240;
int a[num];
for(int i=0;i<num;i++){
a[i]=num-i;
}
long t1=time(NULL);
sort(a,num);
long t2=time(NULL);
for(int i=0;i<8;i++){
cout<<a[i]<<' ';
cout<<endl;
cout<<"time:"<<t2-t1<<endl;
}
return 0;
}
时间2秒10240个数据

（3）插入排序：将头两个元素排序.把接下来的数据依次将每一个元素排到正确的位置.直到所有的元素都排完.前面一个数据不比要插入的数据大了,就是要插入的位置.凡是比它大的数据都要向后移动.
void sort(int *a,int n){
    for(int i=1;i<n;i++){
int cur=a[i];
int j;
for(j=i;j>0&&a[j-1]>a[j];j--){
a[j]=a[j-1];//大量的数据移动,所以速度慢点.
}
a[j]=cur;
   }
}
时间3秒10240个数据

（4）快速排序：效率最高的排序算法.
  找一个分界值,把数据分成两组,对每一组在分成两组,知道只有最后一组数据只有一个数据为止.把大于分界值得放在一边,把不小于分界值得放在另一边.对这两小组在继续.
数组 {503，87，512，61，908，170，897，275，653，462}
    1） [462 87 275 61 170] 503 [897 908 653 512]
    2） [170 87 275 61] 462 503 [897 908 653 512]
    3） [61 87] 170 [275] 462 503 [897 908 653 512]
    4） 61 [87] 170 [275] 462 503 [897 908 653 512]
    5） 61 87 170 [275] 462 503 [897 908 653 512]
    6） 61 87 170 275 462 503 [897 908 653 512]
    7） 61 87 170 275 462 503 [512 653] 897 [908]
      8） 61 87 170 275 462 503 512 [653] 897 [908]
    9） 61 87 170 275 462 503 512 653 897 [908]
   10） 61 87 170 275 462 503 512 653 897 908

void swap(int& x,int & y){
int t=x;
x=y;
y=t;
}
void sort(int *a,int n){
if(n<=1){return ;}
int pivot=a[n>>1];//a[0],a[n-1],a[n/2]找谁居中作为分界值.这里简单处理选a[n/2];
swap(a,a[n>>1]);
int *p=new int[n];
int* lp=p;
int* rp=p+(n-1);
int pivot=*a;
int *pt=a;//为了效率
for(int i=1;i<n-1;i++){
if(pivot>*pt){
*lp++=*pt;
}else{
*rp--=*pt;
}
}
*lp=pivot;
pt=a;
lp=p;
for(int i=0;i<n;i++){
*pt++=*lp++;
}
delete[] p;
int left=rp-p;
sort(a,left);
sort(a+left+1,n-left-1);
}