Linux-数据结构-线性表-顺序表

一.数据结构的基本概念

【1】数据结构：

相互之间存在一种或多种特定关系的数据元素的集合。
（1）逻辑结构
       集合，所有数据在同一个集合中，关系平等。
       线性，数据和数据之间是一对一的关系
       树，一对多
       图，多对多

（2）物理结构(在内存当中的存储关系)
       顺序存储，数据存放在连续的存储单位中。逻辑关系和物理关系一致
       链式，数据存放的存储单位是随机或任意的，可以连续也可以不连续。

【2】数据的类型，ADT abstruct datatype

       是指一组性质相同的值的集合及定义在此集合上的一些操作的总称。
       原子类型，int，char，float
       结构类型，sturct， union，

       抽象数据类型，数学模型 + 操作。

       程序 = 数据 + 算法

【3】算法

   是解决特定问题求解步骤的描述，计算机中表现为指令的有限序列，每条指令表示一个或多个操作。


（1）算法的特征，
   1，输入，输出特性，输入时可选的，输出时必须的。
   2，有穷性，执行的步骤会自动结束，不能是死循环，并且每一步是在可以接受的时间内完成。
   3，确定性，同一个输入，会得到唯一的输出。
   4，可行性，每一个步骤都是可以实现的。


（2）算法的设计，
   1，正确性，
       语法正确
       合法的输入能得到合理的结果。
       对非法的输入，给出满足要求的规格说明
       对精心选择，甚至刁难的测试都能正常运行，结果正确
   2，可读性，便于交流，阅读，理解
   3，健壮性，输入非法数据，能进行相应的处理，而不是产生异常
   4，高效，存储低，效率高

【4】算法时间复杂度

也就是执行这个算法所花时间的度量
n 1 = O(n) O(1)
推到时间复杂度
       1，用常数1 取代运行时间中的所有加法常数
       2，在修改后的运行函数中，只保留最高阶项。
       3，如果最高阶存在且不是1，则取除这个项相乘的常数。

二.线性表-顺序表

【1】线性表的概念

线性表
   零个或多个数据元素的有限序列
   元素之间是有顺序了。如果存在多个元素，第一个元素无前驱，最有一个没有后继，其他的元素只有一个前驱和一个后继。
   当线性表元素的个数n（n>=0）定义为线性表的长度，当n=0时，为空表。在非空的表中每个元素都有一个确定的位置，如果a1是第一个元素，那么an就是第n个元素。

【2】线性表的常规操作 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;

SeqList *CreateSeqList(int len);
int DestroySeqList(SeqList *list);
int ShowSeqList(SeqList *list);
int InsertTailSeqList(SeqList *list, DATATYPE data);
int IsFullSeqList(SeqList *list);
int IsEmptySeqList(SeqList *list);
int InsertPosSeqList(SeqList *list, DATATYPE data, int pos);
int FindSeqList(SeqList *list, char *name);
int ModifySeqList(SeqList *list, char *old, DATATYPE new);
int DeleteSeqList(SeqList *list, char *name);
int ClearSeqList(SeqList *list);
内存泄露检测工具
sudo apt-get install valgrind
valgrind ./all