学习进度追踪【0321 - 0328】

  1. 1. M：函数的四种特性 & 函数图像  102M；
  2. 2. C：指针 - 函数 - 递归调用 - 全局变量 93M；
  3. 3. LC：周竞赛题回顾，不多于93M；

顺序表的特点

1，随机访问，类似于哈希存储，能够通过数据类型占用字节数和元素位序直接访问对应内存地址的值；
2，存储密度高，相对于链表存储方式的一句废话，链表的结点除了存储元素，还需要存储元素的指针；
3，拓展容量不方便，初始空间不足，想要传递更多元素只能放弃治疗，动态分配内存需要全员移位，时间复杂度为O(N)，性能不优；
4，插入删除元素不方便，插入需要从右到左移动该元素之后的所有元素，删除操作需要从左到右移动该元素之后的所有元素，时间复杂度为O(N)

顺序表-初始化和动态分配

image.png

  1. /*-使用malloc & free实现为线性表动态分配内存空间-*/
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #define InitSize 10
  6. // 定义线性表的数据结构
  7. typedef struct {
  8.     int* data;  // 动态分配数组的指针
  9.     int Maxsize;  // 数组的最大长度
  10.     int length;  // 数组的当前长度
  11. }SqList;
  13. // 初始化线性表
  14. void InitList(SqList& L) {
  15.     // 用malloc 函数申请一片连续的内存空间
  16.     L.data = (int*)malloc(InitSize * sizeof(int));  // 强制类型转换
  17.     L.length = 0;
  18.     L.Maxsize = InitSize;
  19. }
  21. // 增加线性表长度
  22. void IncreaseSize(SqList &L, int len) {
  23.     int *p = L.data;
  24.     L.data = (int*)malloc((L.Maxsize + len) * sizeof(int));
  25.     for (int i = 0; i < L.length; i++) {
  26.         L.data[i] = p[i];  // 将数据复制到新区域
  27.     }
  28.     L.Maxsize = L.Maxsize + len;  // 顺序表最大长度增减 len(长度)
  29.     free(p);  // 释放内存空间
  30. }
  32. //  主函数，分别调用
  33. int main(void)
  34. {
  35.     SqList L;
  36.     InitList(L);
  37.     IncreaseSize(L, 5);
  38.     return 0;
  39. }
  40. //

顺序表—-插入和删除操作

  1. /*顺序表的按位查找*/
  2. #define MaxSize 10  /*定义最大长度*/
  3. typedef struct {
  4.     ElemType data[MaxSize];  /*用静态的数组存放数据元素---静态分配*/
  5.     int length;                         /*顺序表的当前长度*/
  6. } SqList;                                 /*顺序表的类型定义---静态分配方式*/
  8. ElemType GetElem(SqList L, int i){
  9.     return L.data[i - 1];                                 /*为增强健壮性可以在此判断输入值是否合法*/
  10. }
  12. /*顺序表的按位查找动态分配方式*/
  13. #define InitSize 10  /*顺序表的初始长度*/
  14. typedef struct{
  15.     ElemType *data;  /*指明动态分配数组的指针*/
  16.     int MaxSize;        /*顺序表的最大容量*/
  17.     int length;           /*顺序表的当前长度*/
  18. } SeqList;                 /*顺序表的类型定义---动态分配方式*/
  20. ElemType GetElem(SeqList L, int i){
  21.     return L.data[i - 1];               /*即使定义为数组，仍然可以用下标的方式访问*/
  22. }
  27. /*顺序表的按值查找*/
  28. typedef struct {
  29.     int * data;                             /*指定动态分配数组的指针*/
  30.     int MaxSize;                         /*顺序表的最大容量*/
  31.     int length;                            /*顺序表的当前长度*/
  32. }
  33. /*在顺序表L中查找第一个值为e的元素，并返回其位序*/
  34. int LocateElem(SeqList L, int e){
  35.     for (int i = 0; i < L.length; i++){
  36.         if (L.data[i] == e)             /*基本数据类型：int, char, double, float等都可以用运算符“==”比较*/
  37.             return i + 1;               /*返回值是该元素的位序，因此值加一*/
  38.     }
  39.     return 0;
  40. }
  41. int main(void)
  42. {
  43.     LocateElem(L, 9);               /*调用该函数，查找目标元素*/
  44.     return 0;
  45. }
  46. /*复杂度分析：
  47. 1， 最好情况，待查找元素就在表头，那么一次循环就可以找到
  48. 2，最坏情况，待查找元素就在表尾或者不在数组之中，那么需要查找n次，n为该数组的长度
  49. 3， 平均情况，概率为: 1/n, 总共执行 (1/2) *[n(n + 1)] * ( 1/ n) = 1/2 * (n + 1) 近似于n
  50. */

求解问题集

解引用地址运算符—-*和读取地址运算符—-&的意义

解引用地址运算符

链表

概念上与线性表的比较

链表的存储密度低，除数据域之外还有指针域；

顺序表连续存储，更改容量需要付出n+m的空间，非常不便；

链表更改数据只需要修改指针，数据可以不连续存放，但失去随机存储的特性，需要从头到尾遍历；

对链表定义的理解

  1. struct LNode{               /*建立一个结构体*/
  2.     ElemType data;              /*定义一个数据域，用来存放数据元素*/
  3.     struct LNode *next;         /*对数据域本身套娃，可以理解为重定义数据域，改为指针域，但原来的位置不变，可能不均等的二分*/
  4. };
  5. typedef struct LNode LNode;             /*使用typedef结构体重命名的能力，对结构体重新命名*/
  6. typedef struct LNode *LinkList;            /*生成俩变量，一个存储数据，一个存储指针*/
  7. LNode * L；             /*声明一个指向单链表第一个结点的指针*/
  8. LinkList * L;               /*声明一个指向单链表第一个结点的指针*/
  9. /*--要表示一个单链表时，只需要声明一个头指针L，指向单链表第一个结点--*/

用代码定义一个链表

  1. /*---用代码定义一个不带头结点的链表---*/
  2. typedef struct LNode{
  3.     ElemType datif
  4.     struct LNode *next;
  5. } LNode, *LinkList;

定义一个不带头结点的单链表

  1. #include <stdbool.h>
  2. /*初始化一个空的单链表*/
  3. bool InitList(LinkList &L){
  4.     if (L = NULL);               /*空表，暂时没有数据，也是为了清除脏数据*/
  5.         return true;            /*程序健壮性，建立空链表成功则进行回报*/
  6.     else
  7.         return false;
  8. }
  9. void test(){
  10.     LinkList L;             /*声明一个指向单链表的指针*/
  11.     /*初始化一个空表*/
  12.     InitList(L);
  13.     /*其他代码*/
  14. }

定义一个带头结点的单链表

  1. /*-----定义一个带头结点的单链表-------*/
  2. typedef struct LNode{
  3.     ElemType data;
  4.     struct LNode *next;
  5. } LNode, *LinkList;
  7. bool InitList(LinkList &L){
  8.     L = (LNode*)malloc(sizeof(LNode));
  9.     if (L == NULL)
  10.         return false;
  11.     L->next = NULL;
  12.     return true;
  13. }
  14. void test(){
  15.     LinkList L;             /*声明一个指向单链表的指针*/
  16.     /*初始化一个空表*/
  17.     InitList(L);
  18.     /*后续代码*/
  19. }
  20. /*判断是否为空*/
  21. bool Empty(Linklist L){
  22.     if(L->next == NULL)
  23.         return true;
  24.     else
  25.         return false;
  26. }

链表的插入

  1. /*---------------线性表的插入----------------*/
  2. #include <stdio.h>
  3. #include <stdbool.h>
  4. typdef struct LNode{
  5.     ElemType data;
  6.     struct LNode *next;
  7. }LNode, LinkList;
  9. bool ListInsert(LinkList &L, int i, ElemType e){
  10.     if (i < 1)              /*判断位序是否合法*/
  11.         return false;
  12.     LNode *p;       /*指针p指向当前扫描到的结点*/
  13.     int j = 0;          /*当前p指向的是第几个结点，是实指还是初始化*/
  14.     p = L;
  15.     while (p != NULL && j < i - 1){             /*循环找到第i-1个结点，链表不为空，且最大搜寻长度为i-1*/
  16.         p = p->next;        /**/
  17.         j++;
  18.     }
  19.     if (p == NULL)
  20.             return false;
  21.     LNode *s = (LNode*)malloc(sizeof(LNode));               /*创造了一个临时变量存储待插入值*/
  22.     s->data = e;                /*将值导入临时空间*/
  23.     s->next = p->next;          /将后一个结点的指针先指向临时空间/
  24.     p->next = s;                /*头结点的下一个空间指针指向临时空间*/
  25.     return true;
  26. }