现在学的《数据结构》是我在大学期间所学的最难的课程，暂时没有之一。
现把前两章所学基础的知识做一下总结：
第一章
1.1数据结构：是研究非数值计算的程序设计中计算机操作的对象以及它们之间的关系和运算的一门学科。
1.2数据(Data)：是对客观事物的符号表示(信息的描述)，一切能够由计算机接受和处理的对象。
数据元素(Data element)：是数据的基本单位，在程序中作为一个整体加以考虑和处理。
数据项(Data item)：是数据的不可分割的最小单位，在有些场合下，数据项又称为字段或域。
根据数据之前的不同关系可以分为：集合、线性结构、树形结构、网状结构或者分为线性结构和非线性结构。
Data_Structure=(D，S)
D：数据元素的有限集
S：D上关系的有限集
1.3数据元素之间的逻辑结构分为：一对一、一对多、多对多三种。
物理结构：描述数据元素在计算机存储器中的存储方式。
顺序：逻辑相邻的元素物理存储上相邻；
链式：逻辑相邻的元素物理存储无关。
抽象数据类型的定义与表示：
（D，S，P）
D是数据对象，S是D上的关系集，P是对D的基本操作集。
ADT 抽象数据类型名 {
数据对象：D=〈数据对象的定义〉
数据关系：R=〈数据关系的定义〉
基本操作：〈基本操作的定义〉
} ADT 抽象数据类型名
1.4算法效率的度量
性能指标：时间复杂度、空间复杂度、其他（正确性、可读性、易调性、健壮性）
度量方法：事后统计法、事前估算法
时间复杂度：与问题的规模有关
T(n)=O(f(n))
例题1
for (i=0; i
return ERROR;
else e=L.elem[i-1];
return OK;
}//GetElem_Sq
插入(前插法):
(1).前提；表不满
(2).插入范围：1~L.length+1
注；位序i在C/C++中对应于下标i-1
(3).步骤：第i至最后所有元素后移一个元素
在第i个位置插入元素X
表长增加1
(4).算法：
Status ListInsert_L(LinkList &L, int i, ElemType e)
{ LinkList p,s;
p=L;
int j=0;
while(p&&j
}
if(!p||j>i-1) return ERROR;
s=(LinkList)malloc(sizeof(Lnode));
s->data=e;s->next=p->next;
p->next=s;
return OK;
}
Status ListInsert_Sq(SqList &L,int i, ElemType e)
{ //（1）合法性判断
//（2）n-i+1个元素的后移
//（3）插入元素e
//（4）表长加1
return OK;
}
删除
(1).前提：表非空
(2).合理的删除范围：1~L.length+1
(3).步骤：
取出第i个元素
第i个元素之后的元素向前移动一个位置
表长减1
(4).算法
Status ListDelete_L(LinkList L, int i, ElemType &e)
{ LinkList p,q;
p=L;
int j=0;
while(p->next&&j
}
if(!(p->next)||j>i-1) return ERROR;
q=p->next;p->next=q->next;
e=q->data;free(q);
eturn OK;
}
Status ListDelete_Sq(SqList &L,int i, ElemType &e)
{ //（1）合法性判断
//（2）n-i个元素的前移
//（3）表长减1
return OK;
}
2.3 线性表的链式表示和实现
date|next
数据域：存储数据元素信息的域。
指针域：存储直接后继存储位置的域。
指针(链)：指针域中存储的地址。
链表：n个结点链结成一个链表，即为线性表的链式存储结构。
线性链表(单链表)：链表的每个结点中只包含一个指针域。
结点和单链表的结构描述
typedef struct LNode{
ElemType data;
struct LNode next;
}LNode, LinkList;
单链表的操作与实现
初始化单链表//建立带附加头结点的空表
Status InitList_L(LinkList &L)
{ L=(LNode)malloc(sizeof(LNode));
if(!L) //L==NULL
exit(OVERFLOW);
L->next=NULL;
return OK;
} //InitList_L
单链表的操作与实现
获取单链表的长度//针对带附加头结点的链表
int ListLength_L(LinkList L)
{ p=L->next;
num=0;
while(p!=NULL)
{ num++; p=p->next; }
return num;
} //ListLength_L
单链表的操作与实现
获取单链表中的第i个元素
Status GetElem_L(LinkList L,int i, ElemType &e)
{ //i在1到ListLength(L)之间
p=L->next; j=1; //p指向第一个元素，j是计数器
while(p&&j
if(!p||j>i) return ERROR;
e=p->data;
return OK;
} //GetElem_L
插入时的操作代码：
q->next = p->next;
p->next = q;
单链表的操作与实现 插入
Status ListInsert_L(LinkList &L,int i, ElemType e)
{ p=L; j=0;
//获得第i-1个元素的地址
while(p&&j
if(!p||j>i-1) return ERROR;
//在第i个元素前插入元素e
s=(LNode
s->data=e; s->next=p->next;
p->next=s;
return OK;
} //ListInsert_L
删除时的操作代码：
p->next = p->next->next;
单链表的操作与实现 删除
Status ListDelete_L(LinkList &L,int i, ElemType &e)
{ p=L; j=0;
//查找第i-1个元素
while(p->next&&j
if(!(p->next)||j>i-1) return ERROR;
//删除第i个元素
q=p->next;
p->next=q->next; e=q->data;
free(q);
return OK;
} //ListDelete_L
单链表的操作与实现
清空单链表
Status ClearList_L(LinkList &L)
{ //将单链表重新置为空表
while (L->next)
{
p=L->next; L->next=p->next;
free(p);
}
return OK;
} //ClearList_L
顺序存储与链式存储的比较
void MergeList(List La, List Lb, List &Lc)
{ InitList(Lc); i = j = 1; k = 0;
La_len = ListLength(La); Lb_len = ListLength(Lb);
while ((i <= La_len) && (j <= Lb_len))
{ GetElem(La, i, ai); GetElem(Lb, j, bj);
if (ai <= bj) { ListInsert(Lc, ++k, ai); ++i; }
else { ListInsert(Lc, ++k, bj); ++j; }
}
… …
}
循环链表
表中最后一个结点的指针域指向头结点。
循环链表为空的判定条件：L->next == L
双向链表
每个结点中包含指向直接前驱和直接后继的两个指针域。
d->next->prev=d->prev->next=d
例题：
设已知结点指针p指向双向链表上的某结点，结点指针q指向一个待插入结点，设计操作，将q所指向的结点插入到p所指向的结点的后面。
操作代码：
p->next->prev = q;
q->next = p->next;
p->next = q;
q->prev = p;
例题：
设已知结点指针p指向双向链表上的某结点，将p所指向的结点删除。
操作代码：
p->prev->next = p->next;
p->next->prev = p->prev;
顺序结构与链式结构选用对比：
顺序结构实现的线性表的特点：
空间结构简单，易于管理
便于随机访问
占用整块儿存储单元
增删元素不方便
链式结构实现的线性表的特点
空间结构复杂，不易管理
不能进行随机访问
有效利用存储空间
便于增删元素
例题：
1.在长度为n的顺序存储的线性表中,向第i个元素(1≤i ≤ n+1)位置插入一个新元素时，需要从后向前依次后移（ n-i+1 ）个元素
2.在一个长度为n的 顺序存储的线性表中，删除第i个元素（1≤i ≤ n）时，需要从前向后依次移动（ n-i ）个元素
3.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ B ）。
A.HL=p；p->next=HL; B.p->next=HL;HL=p;
C.p->next=HL;p=HL; D.p->next=HL->next; HL->=p;
4.在一个单链表HL中，若要在指针q指向的结点后面插入一个由指针p所指向的结点，则执行( D )。
A.q->next=p->next；p->next=q;
B.p->next=q->next; q=p;
C.q->next=p->next; p->next=q;
D.p->next=q->next; q->next=p;
5.在一个单链表HL中，若要删除由指针q指向的结点的后继结点，则执行( C )。
A.p=q->next；p->next=q->next;
B.p=q->next; q->next=p;
C.p=q->next; q->next=p->next;
D.q->next=q->next->next; q->next=q;
6.在已HL为表头指针的带表头结点的单链表和循环链表中，链表为空的条件分别为( HL->next=NULL )和( HL->next=HL ) 。