【精品数据结构】线性表及其顺序存储结构.pptVIP

数 据 结 构 主讲：陈光喜 博士 课号:032844 课时:40(讲课)+16(实验) 上课地点:6312 (周一) 3314 (周五) 第一章 绪 论 1.1 例子 1.2 数据结构、基本概念和术语 1.3 算法和算法分 1.3.1 算法 1.3.2 算法设计的要求 1.3.3 算法的复杂度 1.3.4 算法的描述 第一章 绪 论 计算机是一门研究用计算机进行信息表示和处理的科学。这里面涉及到两个问题： 信息的表示 信息的处理 信息的表示和组又直接关系到处理信息的程序的效率。随着计算机的普及，信息量的增加，信息范围的拓宽，系统程序和应用程序的规模越来越大，结构愈加复杂。要有“好”的程序，必须分析待处理的对象的特征及各对象之间存在的关系，这就是数据结构这门课所要研究的问题。 本章学习要点 熟悉各名词术语的含义,掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。分清哪些是逻辑结构的性质，哪些是存储结构的性质。 理解算法各要素的确切含义:①动态有穷性(能执行结束);②确定性(对于相同的输入执行相同的路径);③有输入;④有输出;⑤可行性(用以描述算法的操作都是足够基本的).　 掌握估算算法时间复杂度的方法。 了解算法描述语言。 第二章 线性表及其顺序存储结构 2.1 线性表的基本概念 2.2 栈及其应用 2.3 队列及其应用 2.4 字符串 例2 学生健康情况登记表如下： 2.3.3 队列的应用 2.3.1 工作调度和分配 模型分析(P39) 2.3.2 输入输出缓冲区结构(略) 2.3.3 汽车加油站工作模拟(重点讲解) 模型分析与详细设计(P40-44) 2.4 串 2.4.1 串类型的定义 2.4.2 串的表示和实现 2.4.2.1 定长顺序存储表示 2.4.2.2 堆分配存储表示 2.4.2.3 串的块链存储表示 （2）入队列操作 void append(qqueue *q,datatype x) {if (( q-s==1)(q-front==q-rear)) return FALSE; /*队列满*/ q-rear++; if (q-rear= =MAXNUM) q-rear=0; q-queue[q-rear]=x; q-s=1; /*置队列非空*/ } （3）出队列操作 datatype delete(qqueue *q) {datatype x; if (q-s= =0) retrun NULL; /*队列为空*/ q-front++; if (q-front= =MAXNUM) q-front=0; x=q-queue[q-front]; if (q-front = =q-rear) q-s=0; /*置队列空*/ return x; } 也可以用一个计数器记录队列中元素的总数(队列长度).下面给出循环队列的类型定义。 #define queuesize 100 typedef char datatype; typedef Struct{ int front; int rear; int count; datatype data[queuesize] }cirqueue; （1）置空队 void initqueue(cirqueue *q){ if ((q=(cirqueue *)malloc(sizeof(cirqueue)))==NULL) error(“内存错误”); q–front=q–rear=0; q–count=0; } （2）判断队空 int queueempty(cirqueue *q) { return q–count==0; } （3）判断队满 int queuefull(cirqueue *q){ return q–count==queuesize; } （4）入队 void enqueue(cirqueue *q,datatype x) { if(queuefull(q)) error(“queue overflow”); q–count++;