文档介绍：特选计算机软件技术基础知识点储备
第一章:概述
1、程序=算法+数据结构
2、算法的几个根本特征:能行性确定性有穷性拥有足够的情报
3、算法的复杂度主要包括:时间复杂度和空间复杂度
第二章:数据结构
1、逻辑结构:数据集合中各数
特选计算机软件技术基础知识点储备
第一章:概述
1、程序=算法+数据结构
2、算法的几个根本特征:能行性确定性有穷性拥有足够的情报
3、算法的复杂度主要包括:时间复杂度和空间复杂度
第二章:数据结构
1、逻辑结构:数据集合中各数据元素之间所固有的逻辑关系〔集合结构、线性结构、树形结构、图状结构〕,可以看作是从具体问题抽象出来的数据模型。
2、物理〔存储〕结构:在对数据进行处理时,各数据元素在计算机中的存储关系,可分为以下四种:顺序存储结构〔存储空间连续〕、链式存储结构、索引结构、散列结构
3、数据结构的运算是指对数据结构中的结点进行操作的集合,包括插入、删除、更新、检索、排序等。
4、数据元素是数据的根本单位
5、有时数据元素可由假设干个数据项〔数据的属性〕组成,在这种情况下,数据项组成的数据元素称为记录,数据项是具有独立含义的最小标识单位,不可分割
6、顺序存储结构:通常定义一维数组来表示线性表的顺序存储空间
7、顺序表的插入
异常处理:〔m为线性表的空间大小,n为线性表的长度<=m,插入的位置为i,i表示在第i个元素之前插入〕
当存储空间已满〔即n=m〕时为上溢错误,不能进行插入,算法结束;
当i>n时,认为在最后一个元素之后〔即第n+1个元素之前〕插入;
当i<1时,认为在第1个元素之前插入
函数的代码实现:
voidinsert〔int*v,intm,intn,inti,intb〕
{
intk;
if(n==m)cout<<〞出现上溢错误!〞<<endl;
if(i>n)i=n+1;
if(i<1)i=1;
for(k=n;k>=i;k--)
{
v[k]=v[k-1];
v[i-1]=b;
n=n+1;
}
}
8、顺序表的删除
异常处理:
当线性表为空〔即n=0〕时为下溢错误,不能进行删除,算法结束;
当i<1或i>n时,认为不存在该元素,不进行删除。
函数的代码实现:
voiddelete(int*v,intm,intn,inti)
{
intk;
if(n==0)cout<<〞出现下溢错误!〞<<endl;
if((i<1)||(i>n))cout<<〞线性表里不存在该元素,不进行删除操作!〞<<endl;
for(k=i;k<=n;k++)
v[k-1]=v[k];
n=n-1;
}
9、栈〔相当于一个井〕的相关概念
先进后出〔后进先出〕
栈顶允许插入与删除
栈底不允许插入与删除
10、队列〔相对于排队买饭〕的相关概念
先进先出
队尾允许插入
对头允许删除
11、链式存储每个结点由两局部组成:数据域和指针域
12、单链表的插入函数实现
在包含元素x的结点前插入新元素b
voidinsert(intx,intb)
{
node*p,*q;
p=newnode;
p->number=b;
if(head==NULL)
{
head=p;
p->next=NULL;
}
if(head->number==x)
{
P->next=head;
Head=p;
}
q=head;
while((q->next!=NULL)&&(((q->next)->number)!=x))
q=q->next;
p->next=q->next;
q->next=p;
}
13、单链表的删除函数实现
删除包换元素x的结点
voiddelete(intx)
{
node*p,*q;
if(head==NULL)cout<<〞没有要删除的元素!〞<<endl;
if((head->number)==x)
{
p=head->next;
deletehead;
head=p;
}
q=head;
while(((q->next)!=NULL)&&(((q->next)->number)!=x))
q=q->next;
if(q->next==NULL)cout<<〞没有要删除的元素!〞<<endl;
p=q->next;
q->next=p->next;
deletep;
}
14、循环链表的插入函数实现
在包含元素x的结点前插入新元素b
voidinsert(intx,intb)
{
node*p,*q;
p=newcode;
p->number=b;
q=head;
while((q->n