数据结构学习笔记

梦里梦外; 2021-11-29 06:00 437阅读 0赞

一、链表  
 1、基本特征：内存节点是不连续的，节点之间通过指针彼此关联。  
   
2、基本操作：追加、插入、删除、遍历、伪随机访问！  
3、实现要点  
 1）追加：新建节点存放数据，令新节点的前指针指向当前尾节点，新节点的后指针为NULL，令当前尾节点的后指针指向新节点，尾指针指向新节点。考虑在空链表中追加第一个节点的情况！  
   
2）插入：新建节点存放数据，令新节点的前后指针指向前后节点！前后节点的后前指针指向新节点！考虑在头节点前插入的情况！  
   
3）删除：令被删除节点的前节点的后指针指向 被删除节点的后节点！被删除节点的后节点的前指针指向被删除节点的前节点。考虑删除头尾节点的情况！  
4）遍历：从头节点开始，沿着每个节点的后指针依次遍历节点数据直到尾节点！  
         -----------------正向遍历！  
          反之，从尾节点开始，沿着每个节点的前指针依次遍历节点数据直到头节点  
          -----------------反向（后向）遍历  
5）伪随机访问：在遍历的同时对节点做计数，直到找到所需要访问的特定位置(索引的节点！

二、二叉树  
 1、基本特征  
   1）表达树形结构的最简模型，每个节点的做多两个子节点。  
   2）单根，每个子节点有且仅有一个父节点，整颗数只有一个根节点  
  3）结构上递归特性，用递归的方法进行处理，可以简化算法！  
2、基本操作  
   生成遍历  
3、实现要点   
   1）由父及子的生成方式！  
   2） 三种遍历序：  
            前序遍历 DLR  
中序遍历 LDR    
后序遍历 LRD  
    3）有序二叉树（二叉搜索树）：  
       50 70 20 60 40 30 10 90 80      
       按照某种规则将一种无序的数据存入有序二叉树结构，而后对该数做中序遍历，  
    得到一个由小到大的有序数列！  
    规则：L < D < R  
                50  
          /     \\  
        20       70    
      /   \\      /   \\      
    10    40   60    90  
          /          /     
        30         80  
10-20-30-40-50-60-70-80-90

三、冒泡排序  
     13  23  20  12  15  31  19  26  14  37  
  1、算法  
1）比较相邻的元素，如果第一个比第二个大，就交换他们两个；  
2）对每一个相邻的元素做同样的工作，从开始的第一个到结尾的最后一对  
  经过这一步，最后的元素将是最大的值；      
3）针对所有的元素去重复以上步骤，除了最后一个！  
4）持续每次对越来越少的元素重复以上步骤，直到没有元素需要交换 。  
2、评价  
    平均时间复杂度O(N^2); 和数据量的平方成正比  
    稳定的，对数据样本的有序性非常敏感！  
void bubble(int data\[\],int size)  
\{  
       for(int i=0;i<size-1;i++)  
       \{  
         bool ordered=true;  
         for(int j=0;j<size-1-i;j++)  
          If(data\[j+1\]<data\[j\])  
          \{  int temp=data\[j\];  
            data\[j\]=data\[j+1\];  
            data\[j+1\]=temp;  
            ordered=false;\}  
         if(ordered)  
           break;

四、插入排序  
10  11  12  14  20  13  16  27  
                 ^         V  
1、算法  
1）从第一个元素开始，该元素可以认为已经有序；  
2）取出下一个元素，在已经有序的元素中从后向前扫描；  
3）若该元素大于新元素，则将该元素赋值到下一个位置！  
4）若该元素小于等于新元素，则新元素置到该元素之后！  
5）重复步骤2），直到处理完所有元素！  
2、评价：  
    平均时间复杂度O(N^2)，稳定，对样本的有序性非常敏感，但是赋值次数  
要比冒泡排序少，因此略优于冒泡排序！  
void insert(int data\[\],int size)  
\{  
        for(int i=1;i<size;i++)  
        \{ int temp=data\[i\];  
           int j;  
        for(j=i;j>0&&temp<data\[j-1\];j--)  
        \{   
          data\[j\]=data\[j-1\];  
         \}  
        if(j!=i)  
        data\[j\]=temp;｝｝  
五、选择排序  
11  12  34  45  77  32  
  1、算法：  
    1）首先在未排序序列中找到最小元素，放到排序序列的起始位置，  
2）然后再从剩余未排序的序列中寻找最小元素，放到排序序列的末尾  
3）……以此类推、直到全部元素排列完毕……  
2、评价：  
   平均时间复杂O（N^2），稳定，对样本的有序性就不敏感（比较多,交换少）  
 但是交换的次数少 ，因此一般情况下优于冒泡排序。  
void select (int data\[\],int size)\{  
        for(int i=0;i<size-1;i++)  
        \{   int min=i;  
            for(int j=i+1;j<size;j++)  
            \{  
              if(data\[j\]<data\[min\])  
              min=j;  
             \}  
       if(min!=i)  
       \{       int temp=data\[i\];  
               data\[i\]=data\[min\];  
               data\[min\]=temp;         \}｝｝  
六、快速排序  
    50  
 0  10  20  30  40  50  60  70  80  90  100   
                                  p  
i  
                                  j  
 0  10  80  30  60  50  40  70  20  90  100   
1、算法  
1）从数列中挑出一个元素称为基准；  
2）重组数列，所有比基准小的元素位于基准之前，所有比基准大的元素位于基准之后  
 与基准相等的元素可以放在任意一边，这个过程叫做分组；  
3）以递归的方式对小于基准的分组和大于基准的分组分别进行排序！  
2、评价  
  平均时间复杂度O（NlogN），不稳定，如果每次分组都能做到均匀划分，其排序速度最快！  
   
3、平均空间复杂度O（Nlog2N）  
qsort  
     void qsort(  
void\*base,  
size\_t  nmemb,  
size\_t  size,  
int(\*compar) (const void\*,const void\*));

七、线性查找  
  1）算法：从表头开始，依次将每一个值与目标元素进行比较，直到找到或找不到位置！  
2）评价：平均时间复杂度O（N），对样本的有序性没有要求！

八、二分查找（折半查找）  
    12  34  56  77  87  99  100  110  130  
  1、算法：（假设表中元素按有序排列）  
        将表的中间元素与查找目标比较，如果相等则查找成功，如果中间元素大于查找目标则在中间元素的左侧子表中继续查找，否则在中间元素的右侧子表中继续查找。重复以上过程，直到找到满足条件的元素为止 ----查找成功！或子表不存在----查找失败！  
2、平均时间复杂度O（logN），样本必须有序！