1.数据结构研究什么？（计算机加工的对象由数值——>非数值）
将现实生活中大量而复杂的问题（非数值问题）以特定的数据类型（逻辑结构）和特定的存储结构（物理结构）保存到主存储器中，以及在此基础上为实现某个功能（删除、排序）相对应的操作。
2.数据的逻辑结构：
3.存储结构（物理结构）：
1）顺序存储结构（借助元素在存储器中的相对位置）
2）链式存储结构（借助元素存储地址的指针）
4.抽象数据类型ADT：
[cpp]
ADT抽象数据类型名
{
数据对象：<数据对象的定义>
数据关系：<数据对象之间关系的定义>
基本操作：<基本操作的定义>
}
5、时间复杂度：
取决定性作用语句的重复次数
第二章 线性表
1.线性结构的基本特征：
1）集合中必存在唯一的一个“第一个元素”；
2）集合中必存在唯一的一个“最后元素”；
3）除最后元素外，均有唯一的后继；
4）除第一元素之外，均有唯一的前驱；
2.ADT
[cpp]
ADT List
{
数据对象：D={ a1,a2, a3, ... an};
数据关系：R={, , … }；
基本操作：
InitList(&L); //操作结果：构造线性表；
DestroyList(&L)； //操作结果：销毁线性表；
ListEmpty(L)； //操作结果：若L为空表，则返回TRUE,否则FALSE;
ListLength(L)； //操作结果：返回L中元素个数；
PriorElem(L,cur_e,&pre_e)//操作结果：cur_e是L的元素，但不是第一个
//则用pre_e返回它的前驱。若操作失败,pre_e无定义
NextElem(L,cur_e,&next_e)//操作结果：cur_e是L的元素，但不是最后一个，
//则用next_e返回它的后继。若操作失败，next_e无定义
GetElem(L,i,&e) // 1<= i <=LengthList(L) 操作结果：用e返回L中第i个元素的值。
LocateElem(L,e,compare())//compare()是元素判定函数。返回L中第一个与e满足compare()的元素位序。
//若这样的元素不存在，则返回值为0。
ListTraverse(L,visit( )) //依次对L的每个元素调用函数visit( ).一旦visit( )失败，则操作失败
ClearList(&L) //操作结果将L重置为空表。
PutElem(L,i,&e) //1<=i<=LengthList(L) 结果：L中第i个元素赋值为e
ListInsert(&L，i,e) //1<=i <=LengthList(L) +1 结果：在L的第i个元素之前插入新的元素e,L的长度增1
ListDelete(&L，i,&e)//1<=i <=LengthList(L) 结果：删除L的第i个元素，并用e返回其值，,L的长度减1
}ADT List
3.顺序实现
1）存储结构：
[cpp]
#define LIST_INIT_SIZE 10
#define INCREAMENT 2
struct SqList
{
ElemType * elem;
int length;
int listsize;
};
2）基本操作
[cpp]
void InitList(SqList & L )
{
L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType) );
L.length = 0;
L.listsize = LIST_INIT_SIZE;
}
void DestroyList(SqList & L)
{
free(L.elem);
L.elem = NULL;
L.length = 0;
L.listsize = 0;
}
void ClearList( SqList & L)
{
L.length = 0;
}
Status ListEmpty( SqList L)
{
if( L.length != 0 )
return FALSE;
else
return TRUE;
}
int ListLength(SqList L)
{
return L.length;
}
Status GetElem(SqList L, int i , ElemType & e)
{
if( i < 1 || i > L.length )
return ERROR;
e = *(L.elem + i - 1);
return OK;
}
int LocateElem(SqList L,ElemType e, Status(*compare)(ElemType , ElemType))
{
ElemType * p;
p = L.elem;
int i = 1;
while(i < L.length && !(compare(e, *p)))
{
i++;
p++;
}
if( i< L.length)
return i;
else
return 0;
}
Status PriorElem(SqList L, ElemType cur_e, ElemType & pre_e)
{
ElemType * p;
p = L.elem + 1; //p 和 i 之间进行合作
int i = 2;
while(i < L.length && *p!=cur_e)
{
i++;
p++;
}
if( i< L.length)
{
pre_e = *(--p);
return OK;
}
else
return INFEASIBLE;
}
Status NextElem(SqList L,ElemType cur_e,ElemType &next_e)
{ // 初始条件：顺序线性表L已存在
// 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继，
// 否则操作失败，next_e无定义
int i=1;
ElemType *p=L.elem;