结构体与链表(Week 7)

结构体

• 用一组变量来描述同一个“事物”
• 构造一个新的数据类型——结构体

struct student
{
  int id;
  char name[20];
  char sex;
  int age;
  float score;
  char addr[30];
}; //注意大括号后的;

• 定义结构体类型的变量

  • 定义结构体变量的方式

  1. 直接用已声明的结构体类型定义变量名

     student student1,student2

  2. 在声明类型的同时定义变量，在大括号之后，;之前。

  • 结构体变量的赋值
    • 相当于copy一份给对方
  • 结构体做函数参数
    • 相当于copy一份给函数
  • 结构体变量做函数返回值
    • 现挡雨copy一份给调用者

• 指向结构体的指针

  • -> 指向运算符，访问结构体的成员变量

• 结构体数组

  • 数组名相当于指向数组第一个元素的指针
  • 指向元素的指针++，则跨过一整个结构体

小结

结构体数据类型的特性与普通数据类型的特性是一致的

链表

• 一种非常常用的数据结构

  • 链表头：指向第一个链表结点的指针
  • 链表结点：链表中的每一个元素，包括：
    • 当前节点的数据
    • 下一个节点的地址
  • 链表尾：不再指向其他结点的结点，其地址部分放一个NULL，表示链表到此结束

• 链表可以动态地创建

  • 动态地 申请内存空间
    • int *pint = new int(1024); delete pint;
    • int *pia = new int[4]; delete[] pia;
  • 动态地建立链表节点

struct student
{
  int id;
  student *next;
};

student *head;
head = new student;

• 逐步建立链表

  • Step 1:
    • head = new student;
    • student *temp = head;
  • Step2:
    • Continue?
  • Y:
    • temp->next = new student;
    • temp = temp->next;
    • goto Step2;
  • N:
    • temp->next = NULL;

• 链表元素的遍历

  • 一个pointer

• 链表元素的删除

  • temp = head; head = head->next; delete temp;
  • follow->next = temp->next;delete temp;

• 链表元素的插入

  • unit->next = head; head = unit;
  • unit->next = temp;
  • follow->next = unit

• 双向链表

  • 包含两个指针，一个指向后继，一个指向前驱
  • 删除和插入操作略微麻烦
  • 应用事例：约瑟夫问题