嵌入式团队结构体&链表培训

结构体

从基本数据类型到抽象数据类型

由前面我们学习的知识可知，C语言规定了一些基本数据类型，比如int、long、float、char等,但是这些基本数据类型在描述一些比较复杂的事务的时候就显得有些不足了，这就引出了我们今天学习的结构体，它允许用户自定义数据，把一些不同类型的数据看成一个整体。这也蕴含着面向对象的思想。

结构体的定义

在C语言里我们怎样描述一个学生的信息呢？这个学生包含了姓名，年龄，性别，学号这些属性。

我们可以抽象出这样的一个结构体

struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};

由此可见，结构体就是把一些基本类型的数据组合在一起，把他们当作一个整体，赋予其新的意义。

结构体的三种定义方式

1、先声明结构体，再定义

struct 结构体名
{数据类型 变量名1；数据类型 变量名2；...数据类型 变量n；
};//注意大括号外面有一个分号

eg：

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};//先声明int main(){struct student st1;//再定义st1.id = 1001;//结构体中变量的访问printf("%d",st1.id);return 0;
}

1、在声明结构体的同时定义结构体变量

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
}st1;//声明同时定义int main(){
//	struct student st1;st1.id = 1001;printf("%d",st1.id);return 0;
}

3、使用typedef定义数据类型

关键字typedef用于为系统固有的或者程序员自定义的数据类型定义一个别名。数据类型的别名通常使用大写字母。

eg：

typedef int INTEGER;

这样就为int定义了一个新的名字INTEGER,int与INTEGER是一个意思，是完全等价的。

所以，我们当然也可以使用typedef来为结构体定义一个别名，让我们使用更加方便。

eg：

#include <stdio.h>typedef struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
}STUDENT;//声明结构体的同时起一个别名，STUDENT就相当于struct studentint main(){STUDENT st1;int i;st1.id = 1001;printf("%d",st1.id);return 0;
}
/******或者*******/
#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};//先声明
typedef struct student STUDENT;//再起别名int main(){STUDENT st1;int i;st1.id = 1001;printf("%d",st1.id);return 0;
}

结构体的访问及初始化

结构体的访问

直接看例子：

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT st1;st1.id = 1001;//对st1中id的访问printf("%d",st1.id);return 0;
}

访问格式：结构体变量名+.+数据变量名

知道了如何访问我们就可以对结构体变量进行赋值,赋值方式仍然与之前的基本数据类型一样。

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT st1;st1.id = 1001;scanf("%s",st1.name);scanf("%d",&st1.age);st1.gender = 'w';printf("%s%d岁了",st1.name,st1.age);return 0;
}

但是！当我们用一个指针指向结构体时

eg：

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT *st1;
//	st1.id = 1001;
//	scanf("%s",st1.name);
//	scanf("%d",&st1.age);
//	st1.gender = 'w';
//	printf("%s%d岁了",st1.name,st1.age);return 0;
}

例如这里的st1指针，我们该如何通过指针去访问结构体的数据呢？

前面我们是用.，这里我们用->这样的箭头符号。

eg：

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT *st1;//定义一个STUDENT类型的指针STUDENT stu;//定义一个STUDNET结构体st1 = &stu;//将是st1指针指向stu
//	st1.id = 1001;
//	scanf("%s",st1.name);
//	scanf("%d",&st1.age);
//	st1.gender = 'w';
//	printf("%s%d岁了",st1.name,st1.age);st1->id = 1001;//注意用的是->scanf("%s",st1->name);scanf("%d",&st1->age);st1->gender = 'w';printf("%s%d岁了\n",st1->name,st1->age);printf("%s%d岁了",(*st1).name,(*st1).age);//st1指针解引用之后就与普通结构体变量一样用.return 0;
}

结构体指针相比结构体更加轻量化，常常被用于函数传递一个结构体。

结构体的初始化

除了常规的初始化之外，结构体可以直接全部赋值进行初始化

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT stu= {"张三",18,'w',1001};return 0;
}

结构体数组

如何表示一些 相同结构的学生记录呢？与前面的基本数据类型一样，结构体也有数组。

#include <stdio.h>struct student{char name[32];//姓名int age;//年龄char gender;//性别long long id;//学号
};
typedef struct student STUDENT;int main(){STUDENT stu[3] = {{"张三",18,'w',1001},{"李四",19,'m',1002},{"王五",20,'w',1003}};return 0;
}

结构体所占字节

大家自己动手实践一下，运行如下代码。你会发现什么？

（内存对齐）

#include <stdio.h>struct test{char ch;int a;short b;
};int main(){printf("%d",sizeof(test));return 0;
}

链表

当需要储存一系列具有同样意义的数据时，根据前面的知识我们会用到数组，但是数组必须先定义数组元素的个数。有没有一种结构可以用于在我们不知道数据元素有多少个的时候，实现数据动态的增长？这就是我们今天要学习的链表。

链表的结构

顾名思义，链表就像一条链子一样把数据连接起来。

由图可知，链表是由一个一个的节点组成的。每一个节点分为两个部分

• 数据域：用于储存节点数据
• 指针域：用于指向下一个节点

所以需要用到结构体，一个简单的链表结构体定义如下：

struct link {int data;//数据域struct link *next;//指针域，next意为指向下一个link结构体的指针
};

链表特殊的储存结构决定了对链表数据特殊的访问方式，即单链表只能顺序访问，不能随机访问。那么想要访问单链表，首先要找到链表的头。

链表的头，我们用头指针来表示它，所以一个完整的链表结构示意图如下：

关于头节点：

头指针：

1. 头指针是指向第一个结点的指针，若链表有头结点，则是指向头结点的指针
2. 头指针具有标识作用，所以常用的头指针冠以链表的名字（指针变量的名字）
3. 无论链表是否为空，头指针均不为空
4. 头指针是链表的必要元素

头节点：

1. 头结点是为了操作的统一和方便而设立的（比如使用头插法的时候），放在第一个元素的结点之前，其数据域一般无意义（但也可以存放链表的长度）
2. 可以没有头节点

带头节点的单链表：

不带头节点的单链表：

单链表的头插法建立（不带头节点）

链表结构如下：

struct Node {int data;//数据域struct Node *next;//指针域，next意为指向下一个link结构体的指针
};
typedef struct Node node;

1. 定义一个指向Node结构体的指针，这个指针就是头指针。

   node *head;
   head = NULL;//指向NULL就是指向空的意思
   

2. 定义并初始化一个节点pnew，将head指向节点

   node *pnew;//新节点
   pnew = (node *)malloc(sizeof(node));//为节点分配内存
   pnew->next = NULL;//先将新节点的next置为NULL；
   if(pnew == NULL){printf("内存不足");exit(0);
   }
   

   因为我们建立的单链表不带头节点，所以进行头插的时候需要分两种情况，一种是插入第一个节点时，其他节点的插入为第二种情况。

   if(head == NULL){head = pnew;//将头指针head指向新节点
   }
   

   第二个节点插入链表，图解：

   

   大家想一想在第二个节点插入链表的过程中，是a操作在前还是b操作在前？

   pnew->next = head;//pnew指向head指向的节点
   head = pnew;//head头指针指向pnew
   

   之后节点的插入过程与第二个插入过程一样。

   节点的插入与这个过程也是一样的。

总结几点建立单链表需要注意的过程：

1. 需要定义头指针，初始化节点时需要为节点分配内存。
2. 注意每个节点还有头指针的指向，建议画图理解。
3. 将最后一个节点指向NULL。

节点的删除

假设有如图所示的链表

cur节点就是我们要删除的节点，我们怎么删除它呢？

只需这样一行代码就搞定，但是由于建立链表的时候，我们为每一个节点都分配了内存，所以我们在删除节点的时候也应该释放其内存，用free()函数来释放内存。

pre->next = cur->next;//让前一节点的指针域指向待删节点的下一节点
free(cur);//释放删除节点的内存

拓展：循环链表和双向链表

循环链表

将单链表中最后结点的指针端由指向NULL改为指向头结点（或第一个节点），就使整个单链表形成一个环，这种头尾相接的单链表称为循环单链表，简称循环链表（circular linked list）。和单向链表一样，循环链表不一定必须有头结点，但是带有头结点循环链表使得空链表和非空链表的处理一致。

双向链表

双向链表(double linked list)是在单链表的每个结点中，在设置一个指向其前驱结点的指针域。双向链表有两个指针域，一个指向前驱一个指向后继。其结构可以设计成：

typedef struct DulNode
{int data;struct DulNode * prev;struct DulNode * next;
}DulNode,typedef DulNode * pDuLinkList;

双向链表能够反向遍历。