数据结构本课程主要内容第一章：绪论第二章：线性表第三章：栈和队列第四章：串第五章：数组和广义表第六章：树和二叉树第七章：图第八章：查找第九章：内部排序第一章绪论高等数学例2:计算机和人的对弈问题例3:多叉路口交通灯的管理问题数据结构的地位数据（Data)客观事物的符号表示，能输入到计算机中并被计算机中程序处理的符号的总称。数据元素(Dataelement)数据的基本单位，可由数据项组成。数据类型(DataType)是和数据结构密切相关的一个概念，在高级语言中，用以刻画（程序）操作对象的特性。是一个值的集合和定义在这个值集上的一组操作的总称。数据对象(DataObject)性质相同的数据元素的集合，是数据的子集。数据结构(DataStructure)相互之间存在一种或多种特定关系的数据元素的集合。数据元素之间的相互关系称为结构。有下列四种基本结构：（1）集合（2）线形结构（3）树形结构（4）图状结构(网状结构）。集合数据类型综述拆除：去掉数据结构中某个指定的数据元素。更新：改变数据结构中某个数据元素的值。查找：在数据结构中寻找某个满足特定要求的数据元素。排序：重新安排数据元素的逻辑顺序关系，使之值按从小到大或从大到小的顺序排列。从操作的特性分，所有的操作可以归结为两类：加工型操作——操作改变了（操作之前的）结构的值。引用型操作——不改变值，只是查询或求得结构的值。例：欧几里德算法：给定两个正整数ｍ和ｎ，求它们的最大公因子？输入整数ｍ和ｎ，R存放M除N的余数解：其算法过程如下：1、求余数：R=M／N余数；2、判断余数：R＝0吗？不是，则转到第4步；3、余数R＝0，输出最大公因子N，运算结束。4、M，N互换数据，返回1，继续循环。一个算法就是一个有穷规则的集合，规则规定了解决某特定问题的运算序列。语言的描述C语言中操作的描述二、循环语句：for语句：for（赋初值表达式序列；条件；修改表达式序列）语句；while语句：while（条件）语句；三、选择语句：条件语句1：if（表达式）语句；条件语句2：if（表达式）语句；else语句；开关语句1：switch（表达式）{case值1：语句序列1；break；：：case值n：语句序列；break；default：语句序列n+1；｝开关语句2：switch｛case条件1：语句系列1；break；…case条件n：语句序列n；break；default：语句序列n+1；}五、结束语句：函数结束语句：return表达式；return；case结束语句：break；异常结束语句：exit（异常代码）；八、逻辑运算约定：与运算&&：对于A&&B，当A的值为0时，不再对B求值。或运算||：对于A||B，当A的值为非0时，不再对B求值。算法的设计要求：时间复杂度：从算法中选取一个对于所研究的问题来说是基本操作的愿操作，以该基本操作重复执行的次数作为算法的时间量度。计作：T（n）=O（f（n））。空间复杂度：一个上机执行的程序除了需要存储空间来积存本身所用指令，常数，变量和输入数据外，也需要一些对数据进行操作的工作单元和存储一些实现计算所需信息的辅助空间。该辅助空间的大小及反映了该算法的空间复杂性。计作：S（n）=O（f（n））。频度：某语句重复执行的次数。程序段一：for(j=1;j<=n;++j)for(k=1;k<=n;++k){++x;s+=x;}程序段二：{++x;s=0;}程序段三：for(i=1;i<=n;++i){++x;s+=x;}第二章线性表线性表可以进行如下运算：Initiate(L)：初始化操作，设定一个线性表。Length(L)：长度的函数，返回元素的个数。Get(L.i)：取第个i数据元素。Insert(L,i,b)：在第个i元素之前，插入元素b。Delete(L,b)：删除第i个元素。Prior(L,elm)：求元素elm的前驱。Next(L,elm)：求元素elm的后继。Locate(L,x)：定位函数。Empty(L)：判空表函数。Clear(L)：表置空操作。二、顺序存储结构的插入和删除运算程序段：voidinsetsqlist(v,n,i,x){if(i<=n){y=v[i];for(j=i;j<=n-1;j++)v[j]=v[j+1];}elseexit(“noelem”);n=n-1;return;}一、单链表指针表示3、使结点q的next域指向含有HAT的结点；4、使包含CAT的结点的next域指向q。单链表的删除操作：链