数据结构基本知识点.docx

弟一早
1、什么是数据结构
① 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及 它们之间的尖系和操作等的学科。
②数据结构是相互之间存在一种或多种特定矢系的数据元素的集合。
③4类基本结构：⑴集合；⑵线性(一个前驱、一个后继)结构；⑶树形结
构；⑷图状结构或网状结构。
2、数据结构的二元组表示：Data_Structure= (D,S) 〃 D是数据元素的有限集，S 是D上矢系的有限集。
3、算法的5大特性：⑴有穷性；
4、衡量算法的标准：时间复杂度和空间复杂度
5、数据的逻辑结构分四类
6、数据结构写出逻辑结构，反之。
弟一早
0'线性表的基本概念。
1、线性表的顺序存储的基本操作：Insert, Eis=n/2 Delete. Edi= (n-1) 12
2、线性表的顺序存储的特点：连续地址，随机查找。
3、线性表的链式存储的特点：地址不保证连续，顺序查找。
(1 )重点1 :结构类型P28
Typedef struct LNode{
ElemType data;
Struct LNode *next;
}LNode,*LinkList;
⑵重点2 :基本方法
Status GetElem_L(LinkList L,int i,ElemType &e);
Status Listlnsert_L(LinkList &L,int i,ElemType e);
Status ListDelete_L(LinkList &L,int i,ElemType &e); void CreateList_L(LinkList &L,int n);
void Print(LinkList L) { LinkList p=L->next;(有头结点)
if(!p) printf( "this link is empty!\n "); else{ printf(u %d r ,p->data);
while(p->next)
{p=p->next; printf(u%d r,p->data);} printf( u\rT );
)
)
void CountNodes(LinkList L,int &nd)
{ nd=0;//
LinkList p=L • >next;(有头巨吉点)if(!p) printf( "this link is empty!\nn);
else{ nd++;//
while(p->next)
{p=p->next; nd++;}//
voidCountAve(LinkList L,int &av)
{int n=O,s=O//
av=O;
LinkList p=L - >next;(有头 2 吉点)if(!p) print： "this link is empty!\n ");
else{ s=s+p->data; n++;//
while(p->next)
{p=p->next;s=s+p->data; n++;}// av=s/n;
}
return av;//
)
void PrintMax(LinkList LJ
{int max;
LinkList p=L • >next;(有头巨吉点)if(!p) print，"this link is empty!\n ");
else{ max=p->data;
while(p->next)
{p=p->next; if(p->data>max) max=p->data;}//
printf( umax=%d\rT ,max);
void DeletaMaxNode(LinkList L,) {int max;
LinkList q,t;//q—记录p的前驱结点指针T-保存最大结点的前驱指针
LinkList p=L->next;(有头结点)q=L;〃
if(!p) printf( "this link is empty!\n ");
else{ max=p->data;t=q;// while(p->next)
{q=p; p=p->next; //
if(p->data>max) {max=p->data; t=q;}//
}
q=t->next; t->next=q->next; free(q);
)
}
⑶循环链表的特点：首尾特点
4)链表为空的条件：分有头链表与无头链表
⑸分清头结点，开始结点、尾结点。
第三章栈和队列
1、栈和队列是端点受限操作的线性表。
2、栈的定义及特点：FILO
3、Push(&s,e) Pop(&s,&e)基本操作过程。
4、判定通过栈操作的序列正确否