顺序表
注意：
构建顺序表的时候，只能用malloc分配内存而不能用new，
因为new分配的内存空间不一定是连续的，而malloc是连续的，
顺序存储要求逻辑上相邻的元素在物理上的存储单元也是相邻的。
如果使用new也能得到相同的结果但是在存储结构上并不符合
代码部分：
参考了顺序表的基本操作（C语言详解版）
#include<iostream>//cout等输入输出流头文件
#include<stdio.h>//scanf(), printf()，gets() 等函数的的头文件
using namespace std;//保证在程序中可以直接使用std命名空间中的成员,原本用法是std::xxxx的，现在就可以直接输xxxx了.
//顺序表的定义
#define Size 5 //对Size进行宏定义，表示顺序表申请空间的大小
typedef struct Table {
int *head; //定义一个指向int类型地址的指针、声明了一个名为head的长度不确定的数组，也叫“动态数组”
//注意，head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。
int length; //表的长度
int size; //记录顺序表分配的存储容量
}table; //将Table类型重新定义为table
//初始化顺序表
table initTable() {
table t;
t.head = (int*)malloc(Size * sizeof(int));//构造一个空的顺序表，动态申请存储空间
/*t.head = new int[5];*/
if (!t.head) //如果申请失败，作出提示并直接退出程序
{
printf("初始化失败");
exit(0);
}
t.length = 0;//空表的长度初始化为0
t.size = Size;//空表的初始存储空间为Size
return t;
}
//输出顺序表中元素的函数
void displayTable(table t) {
for (int i = 0; i < t.length; i++) {
printf("%d ", t.head[i]);
}
printf("\n");
}
int main() {
table t = initTable();
//向顺序表中添加元素
for (int i = 1; i <= Size; i++) {
t.head[i - 1] = i;
t.length++;
}
printf("顺序表中存储的元素分别是：\n");
displayTable(t);
return 0;
}
输出结果如下：
顺序表的插入、删除
顺序表的插入算法：
注意insertTable里面不能直接使用insertTable(table t, int i,int data)
需要加上&，声明引用，否则修改之后的成员值不能返回到主调函数
//顺序表的插入算法
void insertTable(table &t, int i,int data)
{
//判断i的范围是否有效，否则非法
if (i > t.length) {
printf("插入位置无效，请重新选择有效位置插入");
}
else {
if (t.length == t.size) {
//判断当前存储空间是否已满，否则不能插入
printf("当前顺序表已满，无法插入");
}
else {
//进行数据的插入
for (int m = t.size; m >= i; m--) { //将第i个位置以及其后的元素往后移动
t.head[m] = t.head[m - 1];
}
t.head[i - 1] = data; //在第i个位置插入数据
t.length++; //表的长度+1
}
}
}
顺序表的删除算法(另一种传参方式）:
table *p = &t;
delteTable(p, 2);
//顺序表的删除算法
void delteTable(table *t, int i) {
//判断i的范围是否有效，否则非法
if (i > t->length) {
printf("插入位置无效，请重新选择有效位置插入");
}
else {
for (int m = i; m < t->length; m++) {
t->head[m - 1] = t->head[m];
}
t->length--;
}
}
单链表
学习资料：C语言实现链表（链式存储结构）
史上最全单链表的增删改查反转等操作汇总以及5种排序算法(C语言)
链表的数据位置不要求连续，
请求分配内存的时候可以使用new，如果是C++的话，
C语言只能用malloc，因为C语言没有new这个操作符
链表中每个数据的存储都由以下两部分组成： 1. 数据元素本身，其所在的区域称为数据域； 2. 指向直接后继元素的指针，所在的区域称为指针域；
即链表中存储各数据元素的结构如下图 所示：
上图 所示的结构在链表中称为节点。也就是说，链表实际存储的是一个一个的节点，真正的数据元素包含在这些节点中，如下图 所示：
定义单链表：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 10 /*宏定义SIZE为10*/
//定义单链表
typedef struct single_Linked_Lists {
int data; /*data为数据域*/
struct list *next; /*指针域，指针指向直接后继元素*/
}list; /*定义single_Linked_Lists为link*/
/*定义全局头尾节点*/
list *head = NULL;
list *end = NULL;
由于指针域中的指针要指向的也是一个节点，因此要声明为 list类型（这里要写成 struct list*的形式）
另外，可以看到除了结构体的定义外，还声明了头结点和尾结点
头结点的数据域可以不设任何信息，也可以记录表长等相关信息。
头结点的指针域指向线性表的第一个元素结点。
头结点和头指针的区分：
不管带不带头结点，头指针始终指向链表的第一个结点，而头结点是带头指针的链表中的第一个结点，其内通常不设置任何信息
所以链表中有头节点时，头指针指向头节点；反之，若链表中没有头节点，则头指针指向首元节点。
头结点带来的优点：
- 由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作和在表的其他位置上的操作并无区别，无需进行特殊处理
- 无论链表是否为空，它的头指针都是指向头结点的非空指针（空表中的头结点的指针域为空），因此空表和非空表的处理也就统一了
链表的建立:
参考博客：数据结构-头插法和尾插法
头插法：
核心思路：
- 新插入的结点的指针指向原来的首元结点
- 头结点的指针指向新插入的结点
//头插法建立单链表{1,2,3,4,5}
void ListInitHead(list *l) {
l->next = NULL;
for (int i = 1; i<=5; i++) {
list *s = (list*)malloc(sizeof(list));
if (s == NULL) {
printf("malloc error!");
exit(0);
}
else
{
/*给要插入的结点赋值*/
s->data = i;
s->next = l->next;
l->next = s;
}
}
}
打印输出结果：
尾插法：
头插法虽然简单，但是读入数据的顺序与生成链表中元素的顺序是相反的，若我们希望读入数据的顺序和生成链表中的元素顺序保持一致，就可以使用尾插法
为此增加一个尾指针r，使其始终指向当前链表的尾结点
核心思路：
- 原链表中的尾结点（r原本指向）指向要插入的结点
- r指向新的表尾结点
//尾插法建立链表{1,2,3,4,5}
void ListInitEnd(list *l) {
list *s, *r;//s用来指向新生成的节点。r始终指向L的尾结点。
r = l; //因为这里是创建链表，头结点也即尾结点
for (int i = 1; i <= 5; i++) {
s = (list*)malloc(sizeof(list));
if (s == NULL) {
printf("malloc error!");
exit(0);
}
else
{
/*给要插入的结点赋值*/
s->data = i;
r->next = s;
r = s;//r指向终端节点
}
}
r->next = NULL;//元素已经全部装入链表L中
//L的终端节点指针域为NULL，L建立完成
}
上面的是头插法，
下面是尾插法。
链表的插入、查找、删除
链表的查找
所有元素打印：
void Display(list *l) {
list *p = l;//p指针指向头结点
p = p->next; //头结点为空，移到首元结点
while (p)
{
printf("%d", p->data);
p = p->next;
printf(" ");
}
printf("\n");
}
按照序号查找结点值
//按照序号查找结点值
list* GetElem(list *l, int i) {
int j = 1;
list *p = l->next; //首元结点指针赋值给p
if (i == 0) {
return l;//i=0的时候返回头结点
}
else {
if (i < 1) {
printf("查询位置无效，请重新选择有效位置");
return NULL;
}
else
{
while (p&&j < i) {
p = p->next;
j++;
}
}
}
return p;
}
按照值查找表结点
//按照值查找结点
list* LocateElem(list *l, int data) {
list *p = l->next; //首元结点指针赋值给p
while (p&&p->data!=data)
{
p = p->next;
}
return p;
}
链表的插入
在插入函数中，先检查插入位置的合法性，
新建一个结点，把要插入位置的前驱结点的指针域指向s，s的指针域指向原本的数据
//链表插入数据
void InsertData(list *l, int data, int i) { //data为数据，i为位置
list *p = l->next;
if (i <= 0){ //差错控制,判断输入位置是否合法,不可在头结点之前插入
printf("输入位置不合法，请重新输入");
exit(0);
}
else
{
list *s = (list*)malloc(sizeof(list)); //分配新的内存空间给要插入的结点
p = GetElem(l, i-1); //通过GetElem获取结点的前驱结点
s->data = data; //给要插入的结点赋值
s->next = p->next; //s的指针指向p的下一个结点
p->next = s; //p的指针指向s
}
}
链表的删除
//链表删除数据(按照位置)
void DeleteData(list *l,int i) {
int j = 1;
list *before, *Delete;
if (i < 0) {
printf("输入位置不合法，请重新输入");
exit(0);
}
else
{
before = GetElem(l, i - 1);//before指向要删除结点的前驱结点
Delete = before->next; //Delete指向被删除结点
before->next = Delete->next;//被删除结点的前驱结点指向被删除结点的后驱结点
free(Delete); //释放内存空间
}
Display(l);
}
附：
求链表表长
//求链表表长
int GetLength(list *l) {
list *p=l->next;
int length=0;
if (p == NULL) {
return 0;
}
else
{
while (p)
{
p = p->next;
length++;
}
}
return length;
}
循环单链表
双向链表
C语言笔记小结
用到sizeof（int），顺便补充一下各个类型变量所占字节数加强一下记忆
exit（0）
exit()通常是用在子程序中用来终结程序用的，使用后程序自动结束，跳回操作系统。
在c语言中：
exit(0)：表示正常退出；
exit(1):表示异常退出，这个1是返回给操作系统；
值是返回操作系统的：0是正常退出，而其他值都是异常退出，
所以我们在设计程序时，可以在推出前给一些小的提示信息，或者在调试程序的过程中查看出错原因。
使用exit()时，可以不论main()的返回值类型，它的头文件是 stdlib.h。
结构体定义
以这段代码为例
typedef struct Table {
int *head; //定义一个指向int类型地址的指针、声明了一个名为head的长度不确定的数组，也叫“动态数组”
//注意，head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。
int length; //表的长度
int size; //记录顺序表分配的存储容量
}table; //将Table类型重新定义为table
如果没有typedef ：
struct Table {
int *head; //定义一个指向int类型地址的指针、声明了一个名为head的长度不确定的数组，也叫“动态数组”
//注意，head 是我们声明的一个未初始化的动态数组，不要只把它看做是普通的指针。
int length; //表的长度
int size; //记录顺序表分配的存储容量
}table;
最后的table就是定义了一个名为table的Table类型的变量；
但是加上typedef 就等同于
typedef Table table；
将Table类型重新定义为table
malloc函数:
资料来源：【c语言】malloc函数详解
malloc是分配一块连续的内存,与free一起使用
如果分配成功：则返回指向被分配内存空间的指针
不然，返回空指针NULL。 同时，当内存不再使用的时候，应使用free（）函数将内存块释放掉。
malloc和new的区别：
- new/delete是C++关键字，需要编译器支持。malloc/free是库函数，需要头文件支持
- 使用new操作符申请内存分配时无须指定内存块的大小，编译器会根据类型信息自行计算。而malloc则需要显式地指出所需内存的尺寸。
- new操作符内存分配成功时，返回的是对象类型的指针，类型严格与对象匹配，无须进行类型转换，故new是符合类型安全性的操作符。而malloc内存分配成功则是返回void * ，需要通过强制类型转换将void*指针转换成我们需要的类型。
- new内存分配失败时，会抛出bac_alloc异常。malloc分配内存失败时返回NULL。
- new会先调用operator new函数，申请足够的内存（通常底层使用malloc实现）。然后调用类型的构造函数，初始化成员变量，最后返回自定义类型指针。delete先调用析构函数，然后调用operator
delete函数释放内存（通常底层使用free实现）- malloc/free是库函数，只能动态的申请和释放内存，无法强制要求其做自定义类型对象构造和析构工作。
- new操作符从自由存储区（free store）上为对象动态分配内存空间，而malloc函数从堆上动态分配内存。自由存储区是C++基于new操作符的一个抽象概念，凡是通过new操作符进行内存申请，该内存即为自由存储区。而堆是操作系统中的术语，是操作系统所维护的一块特殊内存，用于程序的内存动态分配，C语言使用malloc从堆上分配内存，使用free释放已分配的对应内存。自由存储区不等于堆，如上所述，布局new就可以不位于堆中。
new返回指定类型的指针，并且可以自动计算所需要的大小
int *p;
p = new int;//返回类型为int* ，分配的大小是sizeof(int)
p = new int[100];//返回类型是int*类型，分配的大小为sizeof(int)*100
而malloc需要我们自己计算字节数，并且返回的时候要强转成指定类型的指针。
int *p;
p = (int *)malloc(sizeof(int));
当我们需要一个5元素的int数组时
int *p;
p = (int *)malloc(5*sizeof(int)); //使用malloc
p = new int[5]; //使用new
释放内存：
delete pi ;// 释放单个对象
delete [ ]pi;//释放数组