目录
数据结构
基础知识
1.数据结构的定义
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
具体来说，它包括以下两个方面：
1. 数据元素：是数据的基本单位，可以是数字、字符、记录等。
2. 特定关系：数据元素之间的关系可以是逻辑关系，如线性关系、树状关系、图状关系等；也可以是物理关系，即数据在计算机内存中的存储方式。
数据结构的选择对于算法的效率和程序的性能至关重要。不同的数据结构适用于不同的应用场景，例如，数组适合随机访问但插入和删除操作效率较低；链表适合频繁的插入和删除操作但随机访问效率不高；栈和队列在特定的场景下（如表达式求值、任务调度等）有着独特的作用；树和图则在表示层次关系和复杂网络关系方面表现出色。
逻辑结构
集合，所有数据在同一个集合中，关系平等。
线性，数据和数据之间是一对一的关系
树， 一对多
图，多对多
物理结构(在内存当中的存储关系)
顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续。
struct Per 数据元素
{
char name;//数据项
int age;
char phone;
}
struct Per list[100]; //数据对象
数据的类型，ADT abstruct datatype
是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
原子类型，int，char，float
结构类型，sturct， union，
抽象数据类型， 数学模型 + 操作。
2.为什么需要数据结构
数据结构在计算机科学中具有至关重要的作用，主要原因如下：
一、高效的数据组织和管理
1. 不同的数据结构可以适应不同类型的数据和操作需求。例如，数组适合存储和访问一组具有相同类型的数据，而链表则更适合频繁进行插入和删除操作的场景。
2. 合理选择数据结构可以提高数据存储的效率。例如，哈希表可以快速地根据键值查找对应的数据，大大减少查找时间。
二、优化算法性能
1. 许多算法的效率取决于所使用的数据结构。例如，在排序算法中，不同的数据结构（如数组、链表、二叉树等）会影响排序的时间复杂度和空间复杂度。
2. 数据结构可以提供特定的操作，使得算法能够更高效地执行。例如，栈和队列可以方便地实现深度优先搜索和广度优先搜索算法。
三、便于程序设计和维护
1. 使用合适的数据结构可以使程序的逻辑更加清晰。例如，使用树结构可以直观地表示层次关系，使程序更容易理解和维护。
2. 数据结构的封装性可以提高程序的可扩展性和可维护性。当需要修改数据的存储方式或操作方法时，只需要修改相应的数据结构部分，而不会影响整个程序的其他部分。
综上所述，数据结构是计算机科学中不可或缺的一部分，它能够帮助我们更高效地组织、管理和操作数据，优化算法性能，提高程序的设计质量和可维护性。
3.算法
程序 = 数据 + 算法
算法是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。
算法的特征：
1，输入，输出特性，输入时可选的，输出时必须的。
2，有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
3，确定性，同一个输入，会得到唯一的输出。
4，可行性，每一个步骤都是可以实现的。
算法的设计：
1，正确性，
语法正确
合法的输入能得到合理的结果。
对非法的输入，给出满足要求的规格说明
对精心选择，甚至刁难的测试都能正常运行，结果正确
2，可读性，便于交流，阅读，理解
3，健壮性，输入非法数据，能进行相应的处理，而不是产生异常
4，高效，存储低，效率高
算术时间复杂度
算术时间复杂度是用来衡量算法运行时间与输入规模之间关系的一个指标。
一、定义及表示方法
算术时间复杂度通常用大 O 符号表示，它给出了算法运行时间的一个上界。例如，O(n)表示算法的运行时间与输入规模 n 呈线性关系；O(log n)表示运行时间与输入规模的对数呈线性关系。
二、影响因素
1. 基本操作的执行次数：算法中基本操作（如赋值、比较、算术运算等）的执行次数决定了算法的时间复杂度。通常，执行次数越多，时间复杂度越高。
2. 输入规模：一般来说，输入规模越大，算法的运行时间也会相应增加。不同的数据结构和算法对于不同规模的输入可能会有不同的表现。
3. 算法的结构：算法的控制结构（如循环、递归等）也会影响时间复杂度。例如，嵌套循环通常会导致更高的时间复杂度。
三、重要性
1. 评估算法效率：通过分析算法的算术时间复杂度，可以比较不同算法在处理相同问题时的效率。这有助于选择最适合特定问题的算法。
2. 预测性能：在实际应用中，可以根据问题的规模和算法的时间复杂度来预测算法的运行时间，从而为系统设计和优化提供参考。
3. 算法设计：在设计算法时，考虑时间复杂度可以帮助我们选择更高效的算法结构和数据结构，以提高算法的性能。
推导时间复杂度：
1，用常数1 取代运行时间中的所有加法常数
2，在修改后的运行函数中，只保留最高阶项。
3，如果最高阶存在且不是1，则取除这个项相乘的常数。
算术空间复杂度
算术空间复杂度是衡量一个算法在运行过程中所占用的额外存储空间大小与输入规模之间关系的指标。
一、定义及表示方法
和算术时间复杂度类似，算术空间复杂度也通常用大 O 符号表示。例如，O(1)表示算法所占用的额外空间大小是一个常量，与输入规模无关；O(n)表示额外空间大小与输入规模 n 呈线性关系。
二、影响因素
1. 数据结构的选择：不同的数据结构占用的存储空间不同。例如，数组通常需要连续的内存空间，而链表可以分散存储，在某些情况下链表可能占用更少的连续空间。
2. 算法的实现方式：算法的具体实现方式会影响空间复杂度。例如，某些算法可能需要额外的栈空间来进行递归调用，而通过迭代实现可能会减少空间占用。
3. 输入规模：一般来说，输入规模越大，可能需要的额外存储空间也会相应增加。
三、重要性
1. 资源限制考虑：在一些资源受限的环境中，如嵌入式系统或移动设备，空间复杂度是一个重要的考虑因素。了解算法的空间需求可以确保算法能够在有限的存储空间内运行。
2. 算法效率评估：空间复杂度和时间复杂度一起可以全面评估一个算法的效率。在某些情况下，可能需要在时间和空间之间进行权衡，选择一个最适合特定应用场景的算法。
3. 系统设计优化：通过分析算法的空间复杂度，可以对系统进行优化，减少存储空间的占用，提高系统的性能和可扩展性。
顺序表
在数据结构中，顺序表是一种非常基础且常用的数据结构。
一、存储结构
顺序表采用连续的存储单元来存储数据元素。就像在一个长长的柜子里，一格一格地依次存放物品一样。这种存储方式使得顺序表可以通过下标快速地访问特定位置的元素。
二、特点
1. 随机访问性强：由于元素的存储位置是连续的，可以在常量时间内访问任意位置的元素。例如，如果你想获取顺序表中第 10 个元素，只需要根据起始地址和元素大小，直接计算出该元素的存储位置并访问，时间复杂度为 O(1)。
2. 存储密度高：顺序表中每个元素只存储数据本身，没有额外的指针等空间开销，因此存储密度高。
3. 不利于动态变化：当需要在顺序表中插入或删除元素时，可能需要移动大量的元素以保持存储的连续性。例如，在中间位置插入一个元素，需要将插入位置后面的元素依次向后移动一位，时间复杂度为 O(n)。
三、应用场景
1. 适合数据量相对稳定，且需要频繁随机访问的情况。比如存储一组学生的成绩，需要经常查询特定学生的成绩时，顺序表是一个不错的选择。
2. 在一些算法中，需要快速访问连续的数据，顺序表也能发挥很大的作用。例如，在某些排序算法中，顺序表可以方便地进行元素的比较和交换。
线性表的常规操作
1.创建ADT
typedef struct person {
char name[32];
char sex;
int age;
int score;
}DATATYPE;
typedef int Datatype;
typedef struct list {
DATATYPE *head;
int tlen;
int clen;
}SeqList;
2.创建
SeqList *CreateSeqList(int len);
SeqList *CreateSeqList(int len)
{
SeqList* sl = malloc(sizeof(SeqList));
if(NULL == sl)
{
perror("CreateSeqList malloc");
return NULL;
}
sl->head = malloc(sizeof(DATATYPE)*len);
if(NULL == sl->head)
{
perror("CreateSeqList malloc2");
return NULL;
}
sl->clen = 0;
sl->tlen = len;
return sl;
}3.删除表
int DestroySeqList(SeqList *list);
int DestroySeqList(SeqList *list)
{
free(list->head);
free(list);
return 0;
}4.打印
int ShowSeqList(SeqList *list);
int ShowSeqList(SeqList *list)
{
int i = 0 ;
int len = GetSizeSeqList(list);
for(i=0;i<len;i++)
{
printf("name:%s gender:%c age:%d score:%d\n",list->head[i].name
,list->head[i].gender,list->head[i].age,list->head[i].score);
}
return 0;
}5.尾插
int InsertTailSeqList(SeqList *list, DATATYPE data);
int InsertTailSeqList(SeqList *list, DATATYPE *data)
{
if(IsFullSeqList(list))
{
printf("list is full\n");
return 1;
}
memcpy(&list->head[list->clen],data,sizeof(DATATYPE));
list->clen++;
return 0;
}6.判断是否满
int IsFullSeqList(SeqList *list);
int IsFullSeqList(SeqList *list)
{
return list->clen == list->tlen;
}7.判断是否空
int IsEmptySeqList(SeqList *list);
int IsEmptySeqList(SeqList *list)
{
return 0 == list->clen;
}
8.按位置插
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
int InsertPosSeqList(SeqList *list, DATATYPE *data, int pos)
{
int len = GetSizeSeqList(list);
if(pos<0||pos>len)
{
return 1;
}
for(int i=list->clen;i!=pos ;i--)
{
list->head[i]= list->head[i-1];
}
memcpy(&list->head[pos],data,sizeof(DATATYPE));
list->clen++;
return 0;
}
9.查找
int FindSeqList(SeqList *list, char *name);
int FindSeqList(SeqList *list, char *name)
{
int i = 0 ;
int len = GetSizeSeqList(list);
for(i =0 ;i<len;i++)
{
if(0==strcmp(list->head[i].name,name))
{
return i;
}
}
return -1;
}
DATATYPE *GetItemSeqList(SeqList *list, int pos)
{
int len = GetSizeSeqList(list);
if(pos<0||pos>=len)
{
return NULL;
}
return &list->head[pos];
}10.更改
int ModifySeqList(SeqList *list, char *old, DATATYPE new);
int ModifySeqList(SeqList *list, char *old, DATATYPE *newdata)
{
int ret = FindSeqList(list,old);
if(-1 == ret)
{
return 1;
}
memcpy(&list->head[ret],newdata,sizeof(DATATYPE));
return 0;
}11.删除
int DeleteSeqList(SeqList *list, char *name);
int DeleteSeqList(SeqList *list, char *name)
{
int i = FindSeqList(list,name);
for(i;i<list->clen;i++)
{
list->head[i]=list->head[i+1];
}
list->clen--;
return 0;
}
12.清空
int ClearSeqList(SeqList *list);
int ClearSeqList(SeqList *list)
{
list->clen=0;
return 0;
}