计算机软件技术基础知识点储

备

第一章：概述

1 、程序 = 算法 + 数据结构

2 、算法的几个基本特征：能行性确定性有穷性拥有足够的情报

3 、算法的复杂度主要包括：时间复杂度和空间复杂度

第二章：数据结构

、逻辑结构：数据集合中各数据元素之间所固有的逻辑关系(集合结构、线性结构、树形结构、图状结构)，可以看作是从具体问题抽象出来的数据模型。

、物理(存储)结构：在对数据进行处理时，各数据元素在计算机中的存储关系，可分为以下四种：顺序存储结构(存储空间连续)、链式存储结构、索引结构、散列结构

、数据结构的运算是指对数据结构中的结点进行操作的集合，包括插入、删除、更新、检索、排序等。

、数据元素是数据的基本单位

、有时数据元素可由若干个数据项(数据的属性)组成，在这种情况下，数据项组成的数据元素称为记录，数据项是具有独立含义的最小标识单位，不可分割

、顺序存储结构：通常定义一维数组来表示线性表的顺序存储空间

、顺序表的插入

异常处理：( m 为线性表的空间大小， n 为线性表的长度 <=m ，插入的位置为

i ，i 表

示在第 i 个元素之前插入)

⑴

当存储空间已满(即 n=m )时为上溢错误，不能进行插入，算法结束；

⑵

当 i>n

时，认为在最后一个元素之后(即第

n+1 个元素之前)插入；

⑶

当 i<1

时，认为在第 1 个元素之前插入

函数的代码实现：

voidinsert( int*v,intm,intn,int i, int b)

{

int k;

if(n==m)cout<

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;

}

}

、顺序表的删除异常处理：

⑴ 当线性表为空(即 n=0 )时为下溢错误，不能进行删除，算法结束；

⑵当 i<1或 i>n时，认为不存在该元素，不进行删除。

函数的代码实现：

void delete(int *v, int m,int n, int i)

{

intk;

if(n==0)cout<

if((i<1)||(i>n))cout<

for(k=i;k<=n;k++)

v[k-1]=v[k];

n=n-1;

}

、栈(相当于一个井)的相关概念

⑴先进后出(后进先出)

⑵栈顶允许插入与删除

⑶栈底不允许插入与删除

、队列(相对于排队买饭)的相关概念

⑴先进先出

⑵队尾允许插入

⑶对头允许删除

、链式存储每个结点由两部分组成：数据域和指针域

、单链表的插入函数实现

在包含元素x 的结点前插入新元素b

voidinsert(int x,int b)

{

node *p,*q;

p=new node;

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;

}

、单链表的删除函数实现

删除包换元素x 的结点

voiddelete(int x)

{

node *p,*q;

”没有要删除的元素！”<

if((head->number)==x)

{

p=head->next;

delete head;

head=p;

}

q= head;

while(((q->next)!=NULL)&&(((q->next)->number)!=x))

q=q->next;

if(q->next==NULL)

cout<<

”没有要删除的元素！

”<

p=q->next;

q->next=p->next;

delete p;

}

、循环链表的插入函数实现

在包含元素x 的结点前插入新元素b

void insert(int x,int b)

{

node*p,*q;

p=new code;

p->number=b;

q=head;

while((q->next!=NULL)&&(((q->next)->numbe)r!=x))

q=q->next;

p->next=q->next;

q->next=p;

}

、循环链表的删除函数实现

删除包含元素x 的结点

voiddelete(int x)

{

node