文档介绍：--------------------------校验:_____________-----------------------日期:_____________计算机软件技术基础知识点储备第一章:概述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的结点前插入新元素bvoidinsert(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的结点前插入新元素bvoidinsert(intx,intb){node*p,*q;p=newcode;p->number=b;q=head;while((q->next!=NULL)&&(((q->next)->numbe)r!=x))q=q->next;p->next=q->next;q->next=p;}15、循环链表的删除函数实现删除包含元素x的结点voiddelete(intx){node*p,*q;q=head;while((q->next!=NULL)&&(((q->next)->number)!=x))q=q->next;if(q->next==head)cout<<”没有要删除的元素”<<endl;p=q->next;q->next=p->nex