（完整版）数据结构（c语⾔版）复习知识点2017
第⼀章绪论
1.1数据、数据元素、数据项、数据结构等基本概念
1.数据（data）：客观事物的符号表⽰，在计算机科学中指所有能输⼊计算机中并被计算机处理的符号总称。整数、浮点数、字符串、声⾳、图像。
2.数据元素（dataelement）：数据的基本单位，在计算机程序中通常作为⼀个整体进⾏考虑和处理。
3.⼀个数据元素可能由若⼲个数据项（dataitem）组成。数据元素是⼀个数据整体中相对独⽴的单位。但它还可以分割成若⼲个具有不同属性的项（字段）。故不是组成数据的最⼩单位。数据项是构成数据的最⼩单位。
4.数据对象（dataobject）：性质相同的数据元素的集合，是数据的⼀个⼦集。
5.数据结构（datastructure）：数据元素以及数据元素之间存在的关系。
6.数据结构主要描述：数据元素之间的逻辑关系、数据在计算机系统中的存储⽅式和数据的运算，即数据的逻辑结构、存储结构和数据的操作集合
1.2数据结构的逻辑结构、存储结构的含义及其相互关系
1.数据的逻辑结构：⽤形式化⽅式描述数据元素间的关系。数据的逻辑结构独⽴于计算机，是数据本⾝所固有的。⽤于算法的设计。
两⼤类逻辑结构：线性结构（线性表、栈、队列、数组和串），⾮线性结构（树和图）。
2.数据的物理结构（也称存储结构）：数据在计算机中的具体表⽰。包括数据元素的表⽰和关系的表⽰。存储结构是逻辑结构在计算机存贮器中的映像，必须依赖于计算机。⽤于算法的实现。
数据的存储⽅式可分为如下两类：顺序存储、链接存储。
1.3算法
1.算法的定义：算法是对特定问题求解步骤的⼀种描述，是指令的有限序列。
2.算法的特性：
有穷性——算法必须在执⾏有穷步之后结束，⽽且每⼀步都可在有穷时间内完成
确定性——每条指令⽆⼆义性。并且，相同的输⼊只能得到相同的输出；
可⾏性——算法中描述的每⼀操作，都可以通过已实现的基本运算来实现。
输⼊——算法有零⾄多个输⼊。输出——算法有⼀个⾄多个输出
3.算法效率的度量：时间复杂度和空间复杂度及计算。
第⼆章线性表
2.1线性表的逻辑结构特征
存在唯⼀的⼀个被称作第⼀个的数据元素；存在唯⼀的⼀个被称作最后⼀个的数据元素；除第⼀个元素之外，集合中的每个数据元素均只有⼀个前驱；除最后⼀个元素之外，集合中的每个数据元素均只有⼀个后继。
2.2线性表的顺序存储结构
1.⽤⼀组连续的存储单元依次存储线性表的数据元素。在线性表的顺序存储表⽰中，只要确定了线性表的起始位置，线性表中任⼀数据元素都可随机存取。线性表的顺序存储结构是⼀种随机存取的存储结构。
LOC(ai+1)=LOC(ai)+1
LOC(ai+1)=LOC(a1)+i*1
LOC(ai)表⽰元素ai的存储位置；LOC(a1)表⽰第⼀个数据元素的存储位置，通常称为线性表的起始位置或基地址每个数据元素占⽤1个存储单元。
2.线性顺序表上的插⼊是指在第i(1≤i≤n+1)个位置插⼊⼀个新的数据元素，需将第i⾄第n共(n-i+1)个元素后移
注意：
顺序表中数据区域有listSize个存储单元，所以在向顺序表中做插⼊时先检查表空间是否满了，在表满的情况下不能再做插⼊，否则产⽣溢出错误。
要检验插⼊位置的有效性，这⾥i的有效范围是：1<=i<=n+1，其中n为原表长。
注意数据的移动⽅向
算法时间复杂度
移动元素个数：n-i+1
平均移动元素个数：n/2
T（n）=O（n）；
3.线性顺序表上的删除是指第i(1≤i≤n)个数据元素删除掉，需将第i+1⾄第n共（n-i)个元素前移注意：
删除第i个元素，i的取值为1<=i<=n，否则第i个元素不存在，因此，要检查删除位置的有效性。
当表空时不能做删除。
删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。
算法时间复杂度：
移动元素个数：n-i
平均移动元素个数：（n-1）/2
T（n）=O（n）；
4.线性表的顺序存储。
优点：逻辑相邻，物理相邻可以实现数据元素的随机存取；
缺点：在作插⼊或是删除操作时，需要移动⼤量数据元素
2.3线性表的链式存储结构
1.线性表链式存储结构的特点：⽤⼀组任意的存储单元存储线性表的数据元素。在线性表的链式存储中，在进⾏插⼊或是删除操作时，不需要进⾏数据元素的移动，但不能实现数据元素的随机存取。
2.线性链表的表⽰：数据元素、数据元素之间的关系；数据域存储数据元素，指针域存储数据元素之间的关系：直接后继的存储位置，线性链表：每个节点只包含⼀个指针域
3.假定指针p指向线性链表中的第i个数据元素，则p->next为指向线性链表中第i+1个数据元素的指针。即p->data为ai，p-
>next->data为ai+1。
(*p)表⽰p所指向的结点
(*p).data p->data表⽰p指向结点的数据域
(*p).next p->next表⽰p指向结点的指针域
4.在单链表中查第i个元素
StatusgetElem_L(LinkListL,inti,ElemType&e){ //获取线性链表中的第i个数据元素p=L->next;j=1;
while(p&&j
{
p=p->next;++j;
}
if(!p‖j>i)returnERROR;
returnp->data;
}//GetElem_L
5.在单链表中插⼊数据元素
S->next=P->next；
P->next=S;
StatuslistInsert_L(LinkList&L,inti,ElemTypee){
p=L;j=0;
while(p&&jnext;++j；
}
if(!p‖j>i-1)returnERROR;
s=(LinkList)malloc(sizeof(LNode));s->data=e;
s->next=p->next;p->next=s;
return OK;
}
6.在单链表中删除数据元素
P-＞next=P-＞next-＞next; 或
q=p->next;
p->next=q->next;free(q);
StatuslistDelete_L(LinkList&L,inti){
p=L;j=0;
while(p->next&&j
p=p->next;++j;
}
if(!(p->next) ‖ j>i-1)
return ERROR;//删除位置不合理q
=p->next;
字符串截取到倒数第二个指定字符p->next=q->next;free(q);//删除并释放结点
return OK;
}//ListDelete_L
7.循环链表：表中最后⼀个结点的指针域指向头结点，整个链表形成⼀个环。
循环链表的操作和单链表基本⼀致，差别仅在于，判别链表中最后⼀个结点的条件不再是"后继是否为空"，⽽是"后继是否为头结点"。
(1)单链表p或p->next==NULL
(2)循环链表p->next==L
8.双向链表有两个指针域，⼀个指向直接前驱，⼀个指向直接后继。
1）向双向链表中插⼊⼀个结点：
s-＞prior=p-＞prior；
p-＞prior-＞next=s；
s-＞next=p；
p-＞prior=s；
2）向双向链表中插⼊⼀个结点：：
s-＞prior=p；
s-＞next=p->next；
p->next-＞prior=s；
p-＞next=s；
3）从双向链表中删除⼀个结点
①p-＞prior-＞next=p-＞next；
②p-＞next-＞prior=p-＞prior；
第三章栈和队列
3.1栈和队列的逻辑结构特征
1.栈（stack）和队列（queue）是两种重要的线性结构，特殊性在于其基本操作是线性表操作的⼦集，是操作受限的线性表（操作限定在两个端点进⾏），为具有限定性的数据结构。栈按“后进先出”的规则进⾏操作，队列按“先进先出”的规则进⾏操作。
2.栈是限定在表尾进⾏插⼊和删除操作的线性表。允许插⼊，删除的⼀端称为栈顶(top)，另⼀端称为栈
底(bottom)。
3.栈的基本运算主要有两个：Push(S,e)，进栈，插⼊（压⼊）元素e为新的栈顶元素，Pop(S)，出栈，删除（弹出）S的栈顶元素。如：若元素⼊栈的顺序为1234，为了得到1342出栈顺序，操作序列为：
Push(S,1)，Pop(S)，Push(S,2)，Push(S,3)，Pop(S)，Push(S,4)，Pop(S)，
Pop(S)。
3.2栈的顺序存储结构
1.顺序栈：利⽤⼀组地址连续的存储单元⼀次存放从栈底到栈顶的数据元素，⽤指针top指⽰栈顶元素在顺序栈中的位置。top指向栈顶元素的下⼀个位置top指向栈顶元素
初始化：S.top=S.p=S.base-1
判栈空：S.base==S.top S.base==S.top-1
⼊栈：*s->top++=e（先压后加）*++s->top=e（先加后压）
栈满：S.top-S.base>=S.p-S.base>=S.stacksize-1
出栈：e=*--S.top（先减后弹）e=*S.top--（先弹后减）
能⼊栈；否则出现空间溢出，引起错误，这种现象称为上溢。
出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产⽣错误。通常栈空时
常作为⼀种控制转移的条件。
2.⽤数组的索引值表⽰栈底和栈顶
top指向栈顶元素的下⼀个位置top指向栈顶元素初始化：top=0 top=-1
判栈空：top==0 top==-1
⼊栈：v[top++]=x（先压后加）v[++top]=x（先加后压）
栈满：top-base>=stacksize; top-base>=stacksize-1;
出栈：y=v[--top])（先减后弹）y=v[top--])（先弹后减）
3.
top[0]表⽰第⼀个栈的栈顶;top[1]表⽰第⼆个栈的栈顶
栈空:top[0]=-1;top[1]=n
⼊栈:a[++top[0]]=e;a[--top[1]]=e
栈满:top[0]+1=top[1]
出栈:e=a[top[0]--];e=a[top[1]++]
4.关于顺序栈的说明:⼊栈时，⾸先判栈是否满了，栈满时，不能⼊栈；否则出现空间溢出，引起错误，这种现象称为上溢。出栈和读栈顶元素操作，先判栈是否为空，为空时不能操作，否则产⽣错误。通常栈空时常作为⼀种控制转移的条件。
3.3栈的顺序链式存储
⼊栈：
p=newLNode;//建新的结点
if(!p)exit(1);//存储分配失败
p->data=e;p->next=S->top;//链接到原来的栈顶
S->top=p;//移动栈顶指针
出栈：
if(!S->top)returnNULL;else
{e=S->top->data;//返回栈顶元素
q=S->top;
S->top=S->top->next;//修改栈顶指针
free(q);//释放被删除的结点空间
return e;
}
3.4栈的应⽤举例
1.数制转换
#defineNUM 10
voidconversion(intN，intr){

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。