数据： 数据是信息的载体，所有能输入到计算机中并被计算机程序识别和处理的符号的集合。
数据元素： 数据元素是数据的基本单位，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。
e.g. 若学生记录是一个数据元素，那么其由学号、姓名、性别等数据项组成。
数据对象： 数据对象是由具有相同性质的数据元素的集合，是数据的一个子集。
e.g. 整数是一个数据对象。
数据类型： 数据类型是一个值的集合和定义在此集合上的一组操作的总称。
1）原子类型：其值不可再分的数据类型。
2）结构类型：其值可以再分为若干成分的数据类型。
3）抽象数据类型：抽象数据组织及与之相关的操作。
1、数据的逻辑结构
逻辑结构是指数据元素之间的逻辑关系，与数据的存储无关，是独立于计算机的。
数据的逻辑结构分为 线性结构 和 非线性结构。
2、数据的存储结构
存储结构是指数据结构在计算机中的表示，所以又称为物理结构。
数据的存储结构主要有：顺序存储、链式存储、索引存储和散列存储。
顺序存储： 逻辑上相邻的元素存储在物理位置上也相邻。
链式存储： 不要求逻辑相邻元素物理位置相邻，借助指针来表示元素之间的逻辑关系。
索引存储： 在存储元素信息的同时，建立附加的索引表，索引表没项称为索引项。
散列存储： 根据元素的关键字直接计算出该元素的存储地址。
3、数据的运算
数据的运算包含运算的定义和实现。
有穷性： 一个算法必须在执行有穷步骤之后结束，且每一步都可在有穷时间内完成。
确定性： 算法中每条指令都必须有确切的含义，对于相同的输入只能得出相同的输出。
可行性： 算法中描述的操作都可以通过有限次基本运算完成。
输入： 算法有零个或多个输入。
输出： 算法中有一个或多个输出。
正确性： 算法应能正确地解决求解问题。
可读性： 算法应具有良好的可读性。
健壮性： 输入非法数据时，算法能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。
效率和低存储量需求： 效率指的是算法执行的时间，存储量指的是算法执行过程中所需的最大存储空间。
一个语句的频度是指在算法中被重复执行的次数。算法中所有语句的频度之和为T(n)。
算法中基本运算（最深层循环内的语句）的频度与T(n)同数量级，因此：T(n)=O(f(n))
加法规则： T(n) = T1(n)+T2(n) = O(f(n))+O(g(n)) = O(max(f(n),g(n)))
乘法规则： T(n) = T1(n)*T2(n) = O(f(n))*O(g(n)) = O(f(n)*g(n))
算法的空间复杂度S(n)定义为该算法所耗费的存储空间。
一个程序在执行时除需要存储空间来存放本身所用的指令、常数、变量和输入数据外，还需要存储一些对数据进行操作的工作单元和存储一些为实现计算所需信息的辅助空间。
线性表是具有相同数据类型的n个数据元素的有限序列，n为表长，n=0时为空表。
L=(a1,a2,a3,…,an)
a1为 “表头元素” ，an为 “表尾元素” 。除“表头元素”，线性表中每个元素有且仅有一个 “直接前驱” ，除“表尾元素”，线性表每个元素有且只有一个 “直接后继” 。
InitList(&L) 初始化表。构造一个空的线性表。
Length(L) 求表长
LocateElem(L,e) 按值查找操作，在表L中查找值为e的元素
GetElem(L,i) 按位查找操作，获取表L中第i个元素
ListInsert(&L,i,e) 插入操作，在表L中第i个位置插入指定元素e
ListDelete(&L,i,&e) 删除操作，删除表L中第i个位置的元素，用e返回其值
PrintList(L) 输出操作，按前后顺序输出线性表L的所有元素值
Empty(L) 判空操作，若L为空表，返回true，否则返回false
DestoryList(&L) 销毁操作，销毁线性表，释放线性表L所占存储空间
线性表的顺序存储称为顺序表（物理结构）。用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。
根据上述特质，顺序表可以随意存取，且时间复杂度为O(1)。
顺序表在静态分配时，数组的大小和存储空间事先固定，所以若空间占满仍加入新数据会产生溢出，导致崩溃。
#define MaxSize 50 // 定义线性表的最大程度
typedef struct{
ElemType data[MaxSize]; // 顺序表的元素
int length; // 顺序表的当前长度
}SqList; // 顺序表的类型定义
顺序表为动态分配时，一旦数据空间占满，就另外开辟一块更大的存储空间替换之前的存储空间。
#define InitSize 100 // 表长度的初始定义
typedef struct{
ElemType *data; // 指出动态分配数组的指针
int MaxSize,length; // 数组的最大容量和当前个数
}SeqList; // 动态分配数组顺序表的类型定义
特点一：随机访问 通过首地址和元素序号可在时间O(1)内找到指定的元素。
特点二：存储密度高 每个结点只存储数据元素。
特点三：逻辑上相邻的元素物理上也相邻 所以插入和删除操作需要移动大量元素。
插入操作
bool ListInsert(SqList &L,int i,ElemType e){
if(i<1||i>L.length+1)
return false;
if(L.length>=MaxSize)
return false;
for(int j=L.length;j>=i;j--)
L.data[j]=L.data[j-1];
L.data[i-1]=e;
L.length++;
return true;
}
消耗时间复杂度O(n)
删除操作
bool ListDelete(SqList &L,int i,ElemType &e){
if(i<1||i>L.length)
return false;
e=L.data[i-1];
for(int j=i;j<L.length;j++)
L.data[j-1]=L.data[j];
L.length--;
return true;
}
消耗时间复杂度O(n)
按值查找
int LocateElem(SqList L,ElemType e){
int i;
for(i=0;i<L.length;i++)
if(L.data[i]==e)
return i+1;
return 0;
}
消耗时间复杂度O(n)
通过一组任意的存储单元来存储线性表中的数据元素。
对每个链表结点，除存放元素自身的信息外，还需存放一个指向后继结点的指针。
其中data为数据域，存放数据元素；next为后继指针域，存放后继结点的地址。
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode, *LinkList;
单链表可以解决顺序表需要大量连续存储空间的缺点，但是存放指针域也需要额外的存储空间。且由于单链表的元素离散地分布在存储空间中，所以单链表是非随机存取的存储结构。
按序号查找结点值
LNode *GetElem(LinkList L,int i){
int j=i;
LNode *p=l->next;
if(i==0)
return L;
if(i<1)
return NULL;
while(p&&j<i){
p=p->next;
j++;
}
return p;
}
按值查找表结点
LNode *LocateElem(LinkList L,ElemType e){
LNode *p=L->next;
while(p!=NULL&&p->data!=e)
p=p->next;
return p;
}
插入结点操作
p=GetElem(L,i-1); 查找插入位置的前驱结点
s->next=p->next; 新插入的指针指向后继结点
p->next=s; 前驱结点指向新插入结点
删除结点操作
p=GetElem(L,i-1); 查找删除位置的前驱结点
q=p->next; 令q指向被删除结点
p->next=q->next; 将*q结点从链中断开
free(q); 释放结点的存储空间
单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。要访问某个结点的前驱结点时，只能从头开始遍历，即访问后继结点的时间复杂度为O(1)，访问前驱结点的时间复杂度为O(n)。
引入双链表，包含两个指针分别指向前驱结点prior和指向后继结点next。
typedef struct DNode{
ElemType data;
struct DNode *prior, *next;
}DNode, *DLinkList;
插入操作
s->next=p->next; 将结点*s插入到结点*p之后
p->next->prior=s;
s->prior=p;
p->next=s;
删除操作
p->next=q->next; 删除结点*p的后继结点*q
q->next->prior=p;
free(q);
循环单链表和单链表的区别在于最后一个结点的指针不是NULL，而改为指向头结点。
----20220905 P48