数据结构教案

1第1章绪论1.2基本概念和术语一、数据、数据元素、数据项1．数据：凡能被计算机存储、加工的对象，通称为数据。2．数据元素：是数据的基本单位，通常具有完整、确定的实际意义。3．数据项：是数据不可分割的最小单位。注意：数据、数据元素、数据项是数据组织的三个层次。如：（80，90，100，110，120）、表格二、数据的逻辑结构1．逻辑结构：数据元素之间的“邻接”关系2．四种逻辑结构线性结构：数据元素之间存在“一对一”的关系树形结构：数据元素之间存在“一对多”的关系图状结构：数据元素之间存在“多对多”的关系集合：数据元素之间没有邻接关系三、数据的存储结构1．存储结构：数据元素在计算机内的存放方式2．两种存储结构顺序存储：将数据元素依次存放到一组连续的存储单元中。链式存储：将数据元素存放到非连续的存储单元中，并利用指针将各个存储单元链接起来。四、数据的基本操作加工型操作：改变数据元素的个数或数据元素的内容引用型操作：数据元素的个数或数据元素的内容均未改变五、数据结构1．含义：包括三方面的内容：逻辑结构：反映数据元素之间的邻接”关系存储结构：反映数据元素在计算机内的存放方式数据的操作2.数据按结构分，可分为4类，每一类对应着一种逻辑结构2数据逻辑结构线性表线性结构树树型结构图图状结构查找表集合1.3算法描述1．算法：解决问题的方法和步骤。2．算法的描述方法框图非形式语言：如中文类C语言程序C语言程序1.4算法分析1．对同一问题，可以设计多种不同的算法，但必有一种算法的时间效率最高。2．估算一个算法的运行时间①确定问题的输入规模n。②根据问题的特点，选择一种操作作为“标准操作”。（通常以条件判断或赋值语句为标准操作）③确定在给定输入下共执行多少次标准操作，从而算出运行时间T。3．算法的时间复杂度对算法的运行时间T(n)，忽略所有的常数、低次项，忽略最高项的系数，称为算法的时间复杂度，以O表示。运行时间时间复杂度T(n)=c常数阶O(1)T(n)=cn线性阶O(n)T(n)=cn2平方阶O(n2)ncnT2)(指数阶O(n2)ncnT2log)(对数阶O(n2log)1.5指针和结构3一、什么是指针1．存储单元的地址每一个存储单元由一个或多个字节组成，存储单元中第一个字节的编号称为存储单元的地址。2．什么叫指针？指针总是指向某个变量。指针的值是所指向变量的地址，指针的类型是所指向变量的类型。二、指针变量1．指针变量的定义类型*指针变量名;例：int*p;解释：定义一个指针p，它只能指向int型变量。2．两个运算符&：取地址运算符，例&i*：指针运算符，例*p例：int*p,i=3;p=&i;printf(%d,%d\n,i,*p);说明：①&和*互为逆运算，即：&*p=p，*&i=i②定义指针变量时，指针变量名前面的“*”不是指针运算符。③指针可以与整数进行加、减运算。指针±n=指针的原值±sizeof(指针的类型)×n④同类型的两个指针可以相互赋值。三、指针与数组1．数组名代表该数组的首地址，例a==&a[0]2．设inta[6]，则a[i]，*(a+i)是等价的&a[i]，a+i是等价的3．表示数组元素的方法下标法：例a[i]指针法：例*(a+i)4．设指针p指向数组a的某一个元素，则p++：使p指向数组的下一个元素；四、结构41．定义结构类型struct结构名{成员定义列表}例：structperson{intno;charname[6];};2．定义结构变量structpersonx;1．引用结构变量的成员结构变量名．成员名2．结构变量的初始化3．结构指针例：已知structpersonx,*p;p=&x;则表示x的no成员有三种形式：x.no，p-no，(*p).no第2章线性表2．1线性表的定义1．线性表的表示形式：L=（a1，a2，a3，…，an）2．线性表的基本操作每种操作都采用一个函数来完成，这些函数是自定义函数，使用之前必须先定义。2．2线性表的顺序存储结构一、顺序表的类型定义顺序表实际是一个结构变量，包括两个域：datas：存放线性表的元素，last：存放线性表的长度。typedefstruct{类型datas[maxsize];intlast;}sequenlist;sequenlistL;二、为线性表L=（'a'，'b'，'c'，'d'，……）创建一个顺序表，要求L的第1个元素存入数组的1号元素中。5typedefstruct{chardatas[20];intlast;}sequenlist;voidmain(){sequenlistL;charch;inti=1;ch=getchar();while(ch!='\n'){L.datas[i]=ch;i++;ch=getchar();}L.last=i-1;for(i=1;i=L.last;i++)printf(%4c,L.datas[i]);printf(\n);}三、基本操作在顺序表上的实现1．insert(a,x,i)：将元素x插入到顺序表a的第i号元素之前2．delete(a,i)：删除顺序表a的第i号元素第3章链式存储结构3．1线性表的链式存储结构一、顺序表的优缺点优点：空间利用率高，可以随机读取表中任一元素。缺点：插入、删除操作要移动大量的数据，时间性能差。二、单链表1．单链表的组成每个单链表由多个结点组成，每个结点包含两个域：数据域data：存放线性表的元素指针域next：存放下一个结点的地址2．单链表的类型定义typedefstructnode6{类型data;structnode*next;}linklist;linklist*head;说明：不带头结点的单链表为空的条件：head==null带头结点的单链表为空的条件：head-next==null3．单链表的建立（尾插入法）例：为L=（'a'，'b'，'c'，'d'，……）创建单链表。#includemalloc.h#includestdio.htypedefstructnode{chardata;structnode*next;}linklist;voidmain(){charch;//定义三根指针，head指向头结点，t指向新产生的结点，last指向最后的结点linklist*head,*t,*last;t=malloc(sizeof(linklist));t-next=NULL;head=t;last=t;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linklist));t-data=ch;t-next=NULL;last-next=t;last=t;ch=getchar();}}4．单链表的插入需设置两支指针：p、t。p：指向待插入结点的前一个结点7t：指向新产生的结点5．单链表的删除需设置两支指针：p、t。p：指向待删除结点的前一个结点t：指向待删除结点三、其它链表单链表单向循环链表（循环链表）双向循环链表（双向链表）1．循环链表最后一个结点的指针域不是NULL，而是指向头结点。2．双链表每个结点包含三个域：一个数据域和两个指针域。双链表的特点是找结点的前趋和后继都很容易。第4章栈和队列4．1栈一、栈的定义1．基本概念栈顶、栈底、进栈、出栈、空栈2．栈的表示形式S=（a1，a2，a3，…，an）按a1，a2，a3，…，an顺序进栈，但按an，…，a3，a2，a1顺序出栈。a1称为栈底元素，an称为栈顶元素。栈又称后进先出线性表（LIFO）表。二、栈的顺序存储结构1．顺序栈的类型定义顺序栈实际上是一个结构变量，包括两个域：data：存放栈中元素，top：存放栈顶元素所在单元的编号。typedefstruct{类型data[maxsize];inttop;}seqstack;seqstacks;栈空条件：s.top=0；8栈满条件：s.top=maxsize-12．为S=（'a'，'b'，'c'，'d'，……）创建一个顺序栈，要求S的第1个元素存入数组的1号元素中。typedefstruct{chardata[20];inttop;}seqstack;voidmain(){seqstacks;charch;inti=1;ch=getchar();while(ch!='\n'){s.data[i]=ch;i++;ch=getchar();}s.top=i-1;for(i=1;i=S.top;i++)printf(%-4c,s.data[i]);printf(\n);}三、栈的链式存储结构1．链栈的类型定义typedefstructnode{类型data;structnode*next;}linkstack;linkstack*top;注意：①链栈总是以栈顶指针top开头，top用于标识整个链栈。②链栈只会出现栈空情况，栈空条件为:top==NULL。2．链栈的建立（头插入法）例：为S=（'a'，'b'，'c'，'d'，……）创建一个链栈。9#includemalloc.h#includestdio.htypedefstructnode{chardata;structnode*next;}linkstack;voidmain(){linkstack*top,*t;charch;top=NULL;ch=getchar();while(ch!='\n'){t=malloc(sizeof(linkstack));t-data=ch;t-next=top;top=t;ch=getchar();}printf(出栈顺序为:\n);while(top-next!=NULL){printf(%-4c,top-data);top=top-next;}printf(\n);}4．2队列一、队列的定义1．基本概念队头、队尾、空队2．队列的表示形式：Q=（a1，a2，a3，…，an）按a1，a2，a3，…，an顺序进队，仍按a1，a2，a3，…，an顺序出队。队列又称先进先出线性表（FIFO表）二、队列的顺序存储结构101．顺序队的类型定义顺序队实际上是一个结构变量，包括三个域：data：存放队列的元素；front：存放队头元素所在单元的前一个单元的编号；rear：存放队尾元素所在单元的编号。typedefstruct{类型data[maxsize];intfront,rear;}seqqueue;seqqueueq;2．顺序队的建立例：为Q=（'a'，'b'，'c'，'d'，……）创建一个顺序队。typedefstruct{chardata[20];intfront,rear;}seqqueue;voidmain(){seqqueueq;charch;inti=0;ch=getchar();while(ch!='\n'){q.data[i]=ch;i++;ch=getchar();}q.front=-1;q.rear=i-1;//输出队列元素for(i=0;i=q.rear;i++)printf(%-4c,q.data[i]);printf(\n);}113．顺序队的队空、队满①队空条件：q.front=q.rear②队满条件：q.rear=maxsize-1队真满：q.front＝-1;q.rear＝maxsize-1队假满：q.front≠-1;q.rear＝maxsize-14．顺序队的插入、删除操作①插入新元素：rear后移而front不变q.rear=q.rear+1;q.data[q.rear]=x;②删除元素：front后移而rear不变q.front=q.front+1;三、循环队1．为充分利用存储空间，克服“假满”，可以把数组看作首尾相接的圆环，形成“循环队”。2．循环队的性质①存储单元的编号从0开始，按顺时针方向，编号逐渐增大，最后一个存储单元的编号为maxsize-1。②在循环队中，当q.rear=maxsize-1时，只要数组有两个以上的存储单元为空，就可以把新元素插入到空单元中。③当队