计算机软件技术基础-03 算法和数据结构2

数据结构入学问题住宿组织房间分配班级、专业分配固定不固定数据结构数据结构的研究内容数据的逻辑结构、数据的存储结构、数据的运算数据的逻辑结构：Data-Structure＝(D,R)其中：D是数据元素的集合，R是D上关系的集合一般将数据结构分为两大类：线性数据结构和非线性数据结构。线性数据结构有线性表、栈、队列、串、数组和文件；非线性数据结构有树和图程序中的数据运算是定义在数据的逻辑结构上的，但运算的具体实现要在存储结构(物理结构）上进行。每种逻辑结构都有一个运算集合。常用的运算有检索、插入、删除、更新、排序等研究方法最基本的数据结构为表，其他数据结构都转化为表处理方法：◦研究数据结构的逻辑结构的运算性质◦研究数据结构的物理结构◦根据物理结构和运算性质写算法（集合）逻辑结构和物理结构是相对的线性表线性表的逻辑结构是n个数据元素的有限序列:(a1,a2,a3,…an)n为线性表的长度(n≥0)，n=0的表称为空表数据元素呈线性关系.必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素；除第一个元素外，每个元素都有且只有一个前驱元素；除最后一个元素外，每个元素都有且只有一个后继元素。所有数据元素ai在同一个线性表中必须是相同的数据类型线性表线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表；用链式存储结构存储的线性表称为链表线性表的基本运算主要有：①在两个确定的元素之间插入一个新的元素；②删除线性表中某个元素；③按某种要求查找线性表中的一个元素，需要时，还可找到元素进行值的更新顺序表和一维数组将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表，其下标可看成元素的相对地址。顺序表的运算：①插入②删除③查找\访问顺序表和一维数组顺序表的运算enumBook{ComputerBasic,Math};voidmain(){Bookbooks[6];intnum=0;Booka=ComputerBasic；Insert(books,&num,a,0);Insert(books,&num,a,1);Insert(books,&num,a,2);Insert(books,&num,a,3);Insert(books,&num,a,4);Insert(books,&num,Math,1);Delete(books,&num,5);Delete(books,&num,4);Delete(books,&num,2);}顺序表和一维数组插入boolInsert(Bookbooks[],int*n,Booknbook,intpos){if(pos0||pos*n)returnfalse;for(inti=pos;i*n;++i)books[i+1]=books[i];books[pos]=nbook;*n+=1;returntrue;}顺序表和一维数组删除boolDelet(Bookbooks[],int*n,intpos){if(pos0||pos=*n)returnfalse;*n-=1;for(inti=pos;i*n;++i)books[i]=books[i+1];returntrue;}链表老王老徐大洪小刚单链表enumCode{LaoWang,LaoXu,DaHong,XiaoGang};structSpy{Codec;//信息域Spy*next;//指针域};structStation{Spy*head;intnum;};voidmain(){Stationstation;Spy*wa=Insert(LaoWang,NULL,&station);Spy*xu=Insert(LaoXu,wa,&station);Spy*ho=Insert(DaHong,xu,&station);Spy*ga=Insert(XiaoGang,ho,&station);Delete(wa,&station);//删除LauXu}单链表插入Spy*Insert(Codecd,Spy*prev,Station*st){}代号地址代号地址prev代号地址单链表插入boolDelete(Spy*prev,Station*st){}代号地址代号地址prev代号地址双向链表老王老钟大洪小刚双向链表enumCode{LaoWang,LaoZhong,DaHong,XiaoGang};structSpy{Codec;//信息域Spy*next;//指针域Spy*prev;};structStation{Spy*head;intnum;};voidmain(){Stationstation={NULL,0};Spy*wa=Insert(LaoWang,NULL,&station);Spy*zh=Insert(LaoZhong,wa,&station);Spy*ho=Insert(DaHong,xu,&station);Spy*ga=Insert(XiaoGang,ho,&station);Delete(ho,&station);//删除DaHong}双向链表插入Spy*Insert(Codecd,Spy*pre,Station*st){}prev代号地址地址代号地址地址代号地址地址双向链表删除boolDelete(Spy*cur,Station*st){}prev代号地址地址代号地址地址代号地址地址循环链表老王老钟小刚小吴小李小郑石头链表最后的工作voidFree(Station*st){}代号地址地址代号地址地址代号地址地址head栈栈(STACK)也是一种特殊的线性表，是一种“后进先出”的结构，它的运算规则受到一些约束和限定，故又称限定性数据结构。(1）栈的结构特点栈是限定仅在表尾进行插入和删除运算的线性表，表尾称为栈顶(top)，表头称为栈底(bottom)栈的物理存储可以用顺序存储结构，也可以用链式存储结构(2）栈的运算◦设置一个空栈◦判定栈是否为空◦进栈、退栈◦读取栈顶元素等队列队列也是一种特殊的线性表。在实际生活中经常要靠排队来维护正常的社会秩序，在计算机程序设计中也有类似的问题。数据结构中的队列与生活中的“排队”极为相似，也是按“先来到先解决”的原则行事的，既不允许“加塞儿”，也不允许“中途离队”。“先入先出”队列(Queue)是限定所有的插入只能在表的一端进行，而所有的删除都在表的另一端进行的线性表表中允许插入的一端称为队尾(Rear)，允许删除的一端称为队头(Front)队列的操作是按先进先出的原则进行的队列的物理存储可以用顺序存储结构，也可以用链式存储结构。队列的实现队尾（Rear）队头（Rear）队尾（Rear）队头（Rear）循环队列将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。采用循环队列结构后，有效地解决了“假溢出”的问题，避免了数据元素的移动。插入一个新元素rear=mod(rear,m)+1删除一个元素front=mod(front,m)+1front=rear队列空或满增加一个标志变量S循环队列front=rear队列空或满，增加一个标志变量S假设标志为S，其状态定义为设初始状态F=R，S＝0插入一个元素后置S＝1插入操作If(F=R)and(S=1)ThenERROR(“队满！”)；Return;ElseR=mod(R,m)+1;Q(R)=x;S=1;Endif删除操作IfS=0ThenERROR(“队空！”)；Return;ElseF＝mod(F,m)+1;IfF=RThenS=0;Endif