顺序表

• 了解几个关键点

  • C语言面向过程编程，所以C中对象是指存储（多个）值的物理内存，一个对象中可能未存储实际值，但它存储时就有相应的大小

  • C++面向对象编程，所以C++中对象是指类对象，它包括数据集合和操作集合

  • #define Size 5后面不要分号（；）

  • 在软件（程序）中需要一种方法访问对象（内存），就是声明变量

    int entity=3;

    对该声明进行理解：创建了名为entity的标识符，这个标识符用来指定特定对象（这段内存），而且往对象中存储值（3）。所以标识符是软件访问硬件的一种方式。

  • typedef用于取数据类型的别名

    typedef int ElementType;//typedef 类型 取别名
    int i = 0;
    ElementType j = 0;

• malloc函数

  • 形式：(void*)malloc(参数)

  • 接受一个参数：所需的内存的字节数

  • malloc会找到匿名（没有名字标识符）空闲内存块，无法用名字访问，但是malloc会返回动态分配内存块的首字节地址，所以可以用指针访问到内存块，分配失败时返回空指针

  • 此处的(void*)是指向void的指针，相当于通用指针。应坚持强制类型转换

• malloc深度理解

  • 用malloc()创建数组

    double* ptr;
    ptr=(double *)malloc(30*sizeof(double));

    • 此代码为30个double类型的值请求内存空间，并设置ptr指向该位置。但是ptr只是指向一个double的空间，不是30个double的块空间，类比数组名是数组首元素的地址，所以当ptr指向块的首元素时，可以像数组一样使用它

    • 这时用指针表示数组：ptr[0]来访问首元素，ptr[1]来访问第二个元素

• free()函数

  • free(指针形参)用于释放掉malloc()分配的动态内存

• 顺序表

  • 数据集合（顺序表中涉及的数据）

    typedef struct ArrayList {//数据集合int* element;//存放数据元素的数组int size;//当前元素的个数int length;//顺序表中数组的长度/数据的总容量
    }MyArray;//别名

  • 操作集合（顺序表中对数据操作——增删改查）

    MyArray initArray()//初始化数组
    {MyArray array;//创建一个结构体空间//动态分配5个内存的块array.element=(int*)malloc(Size*sizeof(int));if(array.element=NULL){printf("分配内存失败");exit(0);}array.size=0;array.length=Size;return array;
    }
    ​
    /*
    int key:一个元素
    MyArray* myarray:待查找的数组
    */
    void insert(int key,MyArray* myarray)//添加一个元素
    {//只要当前元素个数小于数组长度 就可以添加if(myarray->size<myarray->length){myarray->element[myarray->size]=key;myarray->size++;}else{printf("数组已经存满")；}
    }
    ​
    void index_insert(int key, MyArray* myarray);//向指定位置的地方添加元素
    ​
    void delete(int key, MyArray* myarray)//删除一个元素
    {int i=index(key,myarray);if(i=-1){printf("没有找到对应数据");}else{//size为元素个数 i为数组下标 要保证i<sizewhile(i<myarray->size){//每个元素都往前覆盖 实际上最后一个元素仍在 认为空了myarray->element[i]=myarray->element[i+1];i++;}myarray->size--;//元素个数减一}
    }
    ​
    //有没有这样一个数据(判断的余地) 这个数据在哪（数据定位）
    //查找操作 返回一个待查找元素的下标
    int index(int key, MyArray* myarray){for(int i=0;i<5;i++){//i为数组下标变量if(myarray->element[i]==key){return i;//返回相对应的下标}else{return -1;}//没有找到 则返回-1}
    }

链表

• 链表特点

  • 在物理内存上不连续，但在逻辑上连续

  • 每个结点需要存放数据（数据域）和（指向下一个结点的）指针（指针域）

• 链表分类

  • 单向链表

  • 单向循环链表

  • 双向链表

  • 双向循环链表

• 单向链表

  • 带头结点

  • 不带头结点

• 链表中的关键概念

  • 头指针：指向第一个节点的指针（不存放元素）

  • 头结点：不存在数据元素的第一个结点（可存放实际存储的个数 依据个人需求）

  • 首元结点：存放元素的第一个结点

• 一个重点：锻炼将抽象逻辑转化为具体代码的能力

• 结点的创建

typedef struct NodeList
{int element;//存放数据的数据域struct NodeList* next//指向一个结点
}Node;

• 链表实现

  Node* InitList()//初始化单向链表
  {//初始化一个头结点Node* node=(Node*)malloc(sizeof(Node));if(node==NULL){printf("内存分配失败");exit(0);}else{node->element=NULL;}return node;
  }
  ​
  void head_insert(int key,Node* node)//向单链表中插入数据（头插法）
  {//建立一个新的结点Node* temp=(Node*)malloc(sizeof(Node));//将待插入的数据放到新结点当中temp->element=key;temp->next=node->next;node->next=temp;
  }
  ​
  void delete(int key,Node* node)
  {//先查找待删除元素的下标（判断有没有这个元素）int index=find(key,node);if(index==-1){printf("没有该元素");exit(0);}else{int i=0;Node* temp=node;//定位到待删除元素的前面while(i<index){temp=temp->next;i++;}//用于释放结点的临时指针Node* free_node=temp->next;//删除中间元素temp->next=temp->next->next;//释放结点free(free_node);}
  }
  ​
  int find(int key,Node* node)
  {Node* temp;//临时指针 用于遍历查找temp=node->next;int i=0;//用于标定链表下标while(temp!=NULL){if(temp->element==key){return i;//找到对应值 则返回结点对应下标}temp=temp->next;//指向下一个结点，i+1i++;}return -1;//找不到，则返回-1
  }

  • 插入操作的实现（否则找不到结点）