数据结构是相互之间存在一种或多种特定关系的数据元素的集合，表示为：
data_structure=（d, s）
d：元素有限集还分成数值类型和非数值类型。
s：关系有限集。
数据(data)——所有能被计算机识别、存储和处理的符号的集合（包括数字、字符、声音、图像等信息 ）。
数据元素(data element)——是数据的基本单位，具有完整确定的实际意义(又称元素、结点，顶点、记录等）。
数据项(data item)——构成数据元素的项目。是具有独立含义的最小标识单位（又称字段、域、属性等）。
数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。逻辑结构可细分为4类：
集合结构： 仅同属一个集合。
线性结构： 一对一（1:1) 线性。
树结构： 一对多（1:n) 非线性。
图结构： 多对多 (m:n) 非线性。
物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。
存储结构可分为4大类：
顺序存储结构。
链式存储结构。
索引存储结构。
散列存储结构。
数据的运算是在数据的逻辑结构上定义的操作算法。它在数据的存储结构上实现。
最常用的数据运算有5种：
插入、删除、修改、查找、排序。
抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的操作。
算法是解决某一特定类型问题的有限运算序列。是一系列输入转换为输出的计算步骤。
算法有5个基本特性：有穷性、确定性、可行性、输入和输出。
算法评价有4个指标：运行时间、占用空间、正确性和简单性。
评价指标中的运行时间，就是用时间复杂度来衡量的。
表现形式：o(f(n))
渐进符号（o）的定义：当且仅当存在一个正的常数 c，使得对所有的 n n0 ，有 f(n) cg(n)，则。
f(n) =o(g(n))
3n+2=o(n3n+24n for n2 */
3n+3=o(n3n+34n for n3 */
100n+6=o(n100n+6101n for n10 */
10n2+4n+2=o(n2) /10n2+4n+211n2 for n5 */
6*2n+n2=o(2n6*2n+n2 7*2n for n4 */
常见的时间复杂度，按数量级递增排列依次为：常数阶o(1)、对数阶o(log2n)、线性阶o(n)、
线性对数阶o(nlog2n)、平方阶o(n^2)、立方阶o(n^3)、k次方阶o(n^k)、指数阶o(2^n)。
下面我们通过例子加以说明，让大家碰到问题时知道如何去解决。
1、设三个函数f,g,h分别为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn
请判断下列关系是否成立：
1） f(n)=o(g(n))
2） g(n)=o(f(n))
3） h(n)=o(n^1.5)
4） h(n)=o(nlgn)
(1)成立。题中由于两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。
（2）成立。与上同理。
（3）成立。与上同理。
（4）不成立。由于当n→∞时n^1.5比nlgn递增的快，所以h(n)与nlgn的比值不是常数，故不成立。
2、设n为正整数，利用大"o"记号，将下列程序段的执行时间表示为n的函数。
1) i=1; k=0
while(i1
while (x>=(y+1)*(y+1))
y++;解答：t(n)=n1/2 ，t(n)=o(n1/2)，最坏的情况是y=0，那么循环的次数是n1/2次，这是一个按平方根阶递增的函数。
3) x=91; y=100;
while(y>0)
if(x>100)
x=x-10;y--;
else x++;
解答： t(n)=o(1)， 这个程序看起来有点吓人，总共循环运行了1000次，但是我们看到n没有？ 没。
这段程序的运行是和n无关的，就算它再循环一万年，我们也不管他，只是一个常数阶的函数。
逻辑结构：1.描述：
线性表是由n (n>=0)个数据元素(结点)a1,a2,….ai,….an组成的有限序列。
其中，数据元素的个数n定义为表长。当n=0时称为空表，非空的线性表(n>0)记为：
a1,a2,….ai,….an)
注意： 1.数据元素ai是一个抽象的符号。
2. ai可取各种数据类型。
3. 一般情况下，同一线性表中的元素具有相同的数据类型。
4. i是元素的序号 (1<=i<=n)
2.逻辑特征：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表的运算：
线性表的常见基本运算包括：
置空表setnull(l)
建表creatlist(l)
求表长length(l)
取结点get(l,i)
定位locate(l,x)
插入insert(l,x,i)
删除delete(l,i)
顺序存储：将线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里。
顺序表：采用顺序存储方法存储的线性表称顺序表。
由n个数据元素a1、a2、..an组成的有限序列，称为顺序表。
存储地址的计算：
由于顺序表采用的是顺序存储方法，因此表中的任一结点的存储地址可按下式计算：
loc(ai)=loc(a1)+(i-1)*c 1<=i<=n
这里：loc(a1)为结点a1的存储起址，c为每个结点所占存储单元数。
顺序表是一种随机存取结构。
在c语言中，顺序表用一维数组描述：
typedef int datetype;
#define maxsize 1024;
typedef struct
datatype data[maxsize];
int last;
} sequenlist;
顺序表上的基本运算（实现）
setnull（l）： l).last = 1
length(l): l).last+1
get(l,i): l).data[i-1]
1. locate(l,x)
算法思想：将x和线性表中的每一个数据元素比较，若相等，返回比较结点的序号，比较至表尾，没有等于x的节点，则返回0.
int locate(sequenlist *l,datatype x)
int i=0;
while(i<=(l).last)
return(0);
最好情况下： t(n)=1
最坏情况下： t(n)=n
2.插入 insert(l,x,i)
所做工作： 判断是否可插入，从表空间上考虑。
判断插入位置是否合法。
结点后移。将x插入第i个位置。
终端结点下标加1
3. 删除 delete(l,i)
所作工作： 判断删除位置是否合法：
i<1)||i>((l).last+1)
结点前移。for(j=i;j<=(l).last; j++)
(*l).data[j-1]=(l).data[j];
终端结点下标减1 (*l).last--;
删除除算法分析。
删除一个结点时结点的平均移动次数为(n-1)/2
平均时间复杂度o(n)
顺序表的优点：
（1）各结点存储单元物理位置上的邻接关系表示了结点间的逻辑关系，因此，无须增加额外的存储空间表示结点间的逻辑关系。
（2）因其为随机存储结构，故可以随机存储表中任一结点。
顺序表的缺点：
（1）插入和删除运算不方便，通常须移动大量结点，效率较低。
2）难以进行连续的存储空间的预分配，尤其是当表变化较大时。
1、 链式存储：用一组任意的存储单元存储线性表， 逻辑上相邻的结点在物理位置上不一定相邻，结点间的逻辑关系由存储结点时附加的指针字段表示。
2、链表：采用链式存储方法的线性表称为链表。
3、链表的特点：其结点的存储单元可以不连续，每个结点中除存储原表结点中的数据外，还须存储指示其直接后继或前趋结点的地址，以反映结点之间的逻辑关系。因此，链表中每个结点由两部分构成：
数据域和链域。
1、单链表的特点：每个结点只有一个链域，指向其直接后继。
（尾结点除外）。
2、结点结构：
3、图示法表示单链表。
4、单链表的存储结构描述如下：
typedef int dataype;
typedef struct node
linklist;
linklist *head, *p;
区分指针变量和结点变量 :p ,*p
结点的动态分配和释放。
申请一个结点 p=(linklist *)malloc(sizeof(linklist));
释放一个结点 free(p);
尾插法建表：将新结点插入到当前链表的表尾。
linklist *creatlistr( )
char ch;
linklist *head,*s,*r;
head=null;
r=null;
ch=getchar( )
while (ch!=‘
s=malloc(sizeof(linklist))
s->data=ch;
if(head=null) head=s
else r->next=s;
r=s; ch=getchar( )
数据结构期末复习讲解
计算机1405杨程皓。版权所有，翻版必究。附录是最小生成树和拓扑排序的 及讲解，还有一些主要算法的演示。一 基本概念及基本结构。1 数据结构及其逻辑结构 存储 物理 结构的基本概念。答 数据结构是相互之间存在一种或多种特定关系的数据元素的集合，在任何问题中，数据元素都不是孤立存在的，而是在他们之间存...
数据结构实验内容安排
数据结构 实验内容安排。1.实验一简单程序设计实验 2学时 最迟提交时间 2016年9月18日。2.实验二线性表实验 3学时 最迟提交时间 2016年9月25日。3.实验三栈和队列实验 4学时 最迟提交时间 2016年10月9日。4.实验四树和二叉树实验 3学时 最迟提交时间 2016年10月16日...
数据结构复习题1 和答案讲解
说明 此复习题为复习专用，其给定了期末考试的主要范围，并非给定考试原题，考试时相关的题目基本都要进行改动。因此同学们请注意，不要去背答案，要将题理解并做会。请注意这决不是原题，只有弄会才可能通过 1 数据结构主要研究的三个内容为以及定义在该结构上的。2 数据结构从逻辑结构上可分为线性结构与非线性结构...