数据结构教程精品资料.docx

《数据结构教程精品资料.docx》由会员分享，可在线阅读，更多相关《数据结构教程精品资料.docx（153页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构教程 第一课：数据结构的基本概念和术语第二课：抽象数据类型的表示与实现第三课：算法及算法设计要求第四课：算法效率的度量和存储空间需求第五课：线性表的类型定义第六课：线性表的顺序表示和实现第七课：实验一 线性表的顺序存储实验第八课：线性表的链式表示与实现第九课：循环链表与双向链表第十课：栈的表示与实现第十一课：栈的应用第十二课：实验二 循环链表实验第十三课：队列第十四课：串的定义第十五课：串的表示和实现第十六课：串操作应用举例第十七课：实验三：栈的表示与实现及栈的应用第十八课：数组的顺序表示与实现第十九课：实验四 串的实现实验第二十课：广义表第二十一课：树、二叉树定义及术语第二十二课：实

2、验五 数组实验第二十三课：二叉树的存储结构第二十四课：遍历二叉树第二十五课：单元测验第二十六课：图的定义与术语第二十七课：实验六 二叉树实验第二十八课：图的存储结构第二十九课：静态查找表（一）顺序表的查找第三十课：静态查找表（二）有序表的查找第三十一课：动态查找表第三十二课：哈希表（一）第三十三课：哈希表（二）第三十四课：插入排序，快速排序第三十五课：实验七 查找第三十六课：选择排序，归并排序第三十七课：实验八 排序实验第三十八课：文件概念，顺序文件第三十九课：索引文件第四十课：总复习第一课本课主题：数据结构的基本概念和术语教学目的：了解数据结构的基本概念，理解常用术语教学重点：基本概念：数据

3、与数据元素教学难点：数据元素间的四种结构关系。授课内容：一、数据、数据元素、数据对象、数据结构的定义1、数据的定义定义一：数据是客观事物的符号表示。学号姓名语文数学C语言6201001张三8554926201002李四9284646201003王五8774736201004.例：张三的C语言考试成绩为92分，92就是该同学的成绩数据。定义二：能输入到计算机中并被计算机程序处理的符号的总称。例：图像、声音等。总结：现实世界信息的分析、复制、传播首先要符号化，这样才便于处理，尤其是便于计算机的处理。家长、社会要了解一个学生的学习成绩和能力，要看他的学习档案，而学习档案即是说明该学生学习情况的数据。

4、2、数据元素、数据项数据元素是数据的基本单位，它也可以再由不可分割的数据项组成。如图示：3、数据对象是性质相同的数据元素的集合。如上例：一个班级的成绩表可以看作一个数据对象。4、数据结构定义一、数据元素集合（也可称数据对象）中各元素的关系。定义二、相互之间存在特定关系的数据元素集合。数据结构的种类：特征示例集合元素间为松散的关系线性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格的一对多关系图状结构（或网状结构）元素间为多对多关系数据结构的形式定义：数据结构名称=（D，S）其中D为数据元素的有限集，S是D上关系的有限集逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系

5、，故也称数据结构为逻辑结构。存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。顺序存储结构链式存储结构存储结构详解：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(Data Field)。例：上述成绩表数据用C语言的结构体数组classonestu50来存储：struct stu int stuno;/*数据项，也称stu位串中的一个子位串，或叫做数据域*/ char name20;int maths;int language;

6、int c_language; classonestu50;二、数据类型1、定义：数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例：C语言中的整型，其内涵为一定范围的自然数集合，及定义在该集合上的加减乘除及取模、比较大小操作。而实型则无取模操作。当然整型也不需四舍五入。2、数据类型的种类：特征例原子类型值在逻辑上不可分解int float结构类型值由若干成分按某种结构组成struct stu数据类型封装了数据存储与操作的具体细节。三、总结数据-数据元素具有特定关系的数据元素集合-数据结构数据结构的逻辑表示与物理存储-逻辑结构与存储结构人们不仅关心数据的逻辑结构、存储结构，还关心数据

7、的处理方法（算法）与处理结果-数据类型数据类型-分类第二课本课主题： 抽象数据类型的表示与实现教学目的： 了解抽象数据类型的定义、表示和实现方法教学重点： 抽象数据类型表示法、类C语言语法教学难点： 抽象数据类型表示法授课内容：一、抽象数据类型定义（ADT）作用：抽象数据类型可以使我们更容易描述现实世界。例：用线性表描述学生成绩表，用树或图描述遗传关系。定义：一个数学模型以及定义在该模型上的一组操作。关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。例：线性表这样的抽象数据类型，其数学模型是：数据元素的集合，该集合内的元素有这样的关系：除第一个

8、和最后一个外，每个元素有唯一的前趋和唯一的后继。可以有这样一些操作：插入一个元素、删除一个元素等。抽象数据类型分类原子类型值不可分解，如int固定聚合类型值由确定数目的成分按某种结构组成，如复数可变聚合类型值的成分数目不确定如学生基本情况抽象数据类型表示法：一、三元组表示：（D，S，P）其中D是数据对象，S是D上的关系集，P是对D的基本操作集。二、书中的定义格式：ADT 抽象数据类型名数据对象：数据关系：基本操作：ADT 抽象数据类型名例：线性表的表示名称线性表数据对象D=ai| ai(-ElemSet,i=1,2,.,n,n=0任意数据元素的集合数据关系R1=| ai-1,ai(- D,i=

9、2,.,n除第一个和最后一个外，每个元素有唯一的直接前趋和唯一的直接后继基本操作ListInsert(&L,i,e)L为线性表，i为位置，e为数据元素。ListDelete(&L,i,e).二、类C语言语法类C语言语法示例1、预定义常量和类型#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef in Status; /Status是函数的类型，其值是函数结果状态代码。2、数据结构的存储结构typedef ElemType first;3、基本

10、操作的算法函数类型 函数名（函数参数表）/算法说明语句序列/函数名 4、赋值语句简单赋值：变量名=表达式；串联赋值：变量名1=变量名2=.=变量名k=表达式；成组赋值:（变量名1，.,变量名k）=（表达式1，.,表达式k);结构名=结构名；结构名=（值1，.，值k);变量名=表达式；变量名起始下标.终止下标=变量名起始下标.终止下标； 交换赋值：变量名变量名；条件赋值：变量名=条件表达式？表达式？表达式T：表达式F5、选择语句1、if（表达式） 语句；2、if（表达式） 语句；else 语句；3、switch(表达式）case 值1：语句序列1；break;.case 值n：语句序列n；bre

11、ak; default:语句序列n+1；break; 4、switchcase 条件1：语句序列1；break;.case 条件n：语句序列n；break; default:语句序列n+1；break; 6、循环语句for（赋初值表达式；条件；修改表达式序列）语句；while（条件）语句；do 语句序列while（条件）；7、结束语句return 表达式；return; /函数结束语句break; /case结束语句exit(异常代码); /异常结束语句8、输入和输出语句scanf（格式串，变量1，.,变量n）；9、注释/文字序列10、基本函数max（表达式1，.，表达式n）min,abs,f

12、loor,ceil,eof,eoln11、逻辑运算&与运算；|或运算例：线性表的实现：ADT List数据对象: D=ai| ai(-ElemSet,i=1,2,.,n,n=0 数据关系: R1=| ai-1,ai(- D,i=2,.,n 基本操作：InitList(&L)DestroyList(&L)ListInsert(&L,i,e)ListDelete(&L,i,&e)ADT ListListInsert(List &L,int i,ElemType e)if(iL.length+) return ERROR;q=&(L.elemi-1);for(p=&(L.elemL.length-1

13、);p=q;-p) *(p+1)=*p;*q=e;+L.length;return OK;下面是C语言编译通过的示例： #define ERROR 0 #define OK 1 struct STU char name20;char stuno10; int age; int score; stu50; struct LIST struct STU stu50; int length; L; int printlist(struct LIST L) int i;printf(name stuno age scoren); for(i=0;iL.length;i+) printf(%s %st%

14、dt%dn, L.stui.name, L.stui.stuno, L.stui.age, L.stui.score); printf(n); int listinsert(struct LIST *L,int i,struct STU e) struct STU *p,*q; if (iL-length+1) return ERROR; q=&(L-stui-1); for(p=&L-stuL-length-1;p=q;-p) *(p+1)=*p; *q=e; +L-length; return OK; /*ListInsert Before i */main() struct STU e;

15、 L.length=0; strcpy(e.name,zmofun); strcpy(e.stuno,100001); e.age=80; e.score=1000; listinsert(&L,1,e); printlist(L); printf(List length now is %d.nn,L.length); strcpy(e.name,bobjin); strcpy(e.stuno,100002); e.age=80; e.score=1000; listinsert(&L,1,e); printlist(L); printf(List length now is %d.nn,L.

16、length); E:ZMZmdocdatastruclass02listdemo name stuno age score zmofun 100001 80 1000 List length now is 1. name stuno age score bobjin 100002 80 1000 zmofun 100001 80 1000 List length now is 2. 三、总结抽象数据类型定义；抽象数据类型实现方法：一、类C语言实现 二、C语言实现回目录 上一课 下一课第三课本课主题： 算法及算法设计要求教学目的： 掌握算法的定义及特性，算法设计的要求教学重点： 算法的特性，算

17、法设计要求教学难点： 算法设计的要求授课内容：一、算法的定义及特性1、定义：ispass(int num44) int i,j; for(i=0;i4;i+)for(j=0;j4;j+) if(numij!=i*4+j+1)/*一条指令，多个操作*/return 0; return 1; /*上面是一个类似华容道游戏中判断游戏是否结束的算法*/算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列五个重要特性：2、算法的五个特性：有穷性一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；确定性算法

18、中每一条指令必须有确切的含义，读者理解时不会产生二义性。有任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。可行性一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。输入一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合。输出一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。例：有穷性haha()/*only a joke,do nothing.*/ main()printf(请稍等.您将知道世界的未日.);while(1)haha(); 确定性float average(int *a,int num)in

19、t i;long sum=0;for(i=0;inum;i+)sum+=*(a+);return sum/num;main()int score10=1,2,3,4,5,6,7,8,9,0;printf(%f,average(score,10); 可行性输入输出getsum(int num)int i,sum=0;for(i=1;ib)if(ac) return c;else return a; 程序对于几组输入数据能够得出满足规格说明要求的结果。max(int a,int b,int c)if (ab)if(ac) return a;else return c; /* 8,6,7 */ /*

20、 9,3,2 */程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果。max(int a,int b,int c)if (ab)if(ac) return a;else return c; elseif(bc) return b;else return c; 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。2、可读性3、健壮性4、效率与低存储量需求效率指的是算法执行时间。对于解决同一问题的多个算法，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。两者都与问题的规模有关。算法一算法二在三个整数中求最大者max(int a,int

21、 b,int c)if (ab)if(ac) return a;else return c; elseif(bc) return b;else return c; /*无需额外存储空间，只需两次比较*/max(int a3)int c,int i;c=a0; for(i=1;ic) c=ai;return c; /*需要两个额外的存储空间，两次比较，至少一次赋值*/*共需5个整型数空间*/ 求100个整数中最大者同上的算法难写，难读max(int a100)int c,int i;c=a0; for(i=1;ic) c=ai;return c;/*共需102个整型数空间*/ 三、总结1、算法的

22、特性2、算法设计要求：正确性、可读性、健壮性、效率与低存储量需求。回目录 上一课 下一课第四课本课主题： 算法效率的度量和存储空间需求教学目的： 掌握算法的渐近时间复杂度和空间复杂度的意义与作用教学重点： 渐近时间复杂度的意义与作用及计算方法教学难点： 渐近时间复杂度的意义授课内容：一、算法效率的度量算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣，可以在相同的规模下，考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：1、事后统计的方法。缺点：不利于较大范围内的算法比较。（异地，异时，异境） 2、事前分析估算的方法。程序在计算机上运行所需时间的影响因素算法本身选

23、用的策略问题的规模规模越大，消耗时间越多书写程序的语言语言越高级，消耗时间越多编译产生的机器代码质量机器执行指令的速度综上所述，为便于比较算法本身的优劣，应排除其它影响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作重复执行的次数作为算法的时间量度。（原操作在所有该问题的算法中都相同）T(n)=O(f(n)上示表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度。求4*4矩阵元素和，T(4)=O(f(4)f=n*n;sum(int num44) int i,j,r=0; for(i=0;i4;i+)fo

24、r(j=0;j4;j+) r+=numij; /*原操作*/return r; 最好情况：T（4）=O（0）最坏情况：T（4）=O（n*n）ispass(int num44) int i,j; for(i=0;i4;i+)for(j=0;j4;j+) if(numij!=i*4+j+1)return 0; return 1; 原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。语句频度时间复杂度+x;s=0;1O(1)for(i=1;i=n;+i)+x;s+=x;nO(n)for(j=1;j=n;+j)for(k=1;k=0 数据关系: R1=| ai-1,ai(-

25、D,i=2,.,n 基本操作：InitList(&L)DestroyList(&L)ClearList(&L)ListEmpty(L)ListLength(L)GetElem(L,i,&e)LocateElem(L,e,compare()PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e) ListInsert(&L,i,e)ListDelete(&L,i,&e)ListTraverse(L,visit() union(List &La,List &Lb)ADT List2、部分操作的类C实现：InitList(&L)L.elem=(ElemTy

26、pe *)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem)exit(OVERFLOW);L.length=0;L.listsize=LIST_INIT_SIZE;return OK;/InitListGetElem(L,i,&e)*e=L.lemi/GetElemListInsert(List &L,int i,ElemType e)if(iL.length+) return ERROR;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p) *(p+1)=*p;*q=e;+L.length;retu

27、rn OK;/ListInsertvoid union(List &La,List &Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if(!LocateElem(La,e,equal)ListInsert(La,+La_len,e);/unionvoid MergeList(List La,List Lb,List &Lc)InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);while(i=La

28、_len)&(jLb_len)GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;elseListInsert(Lc,+k,bj);+j;while(k=La_len)GetElem(La,i+,ai);ListInsert(Lc,+k,ai);while(j=Lb_len)GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);/MergeList3、部分操作的C语言实现,下面是程序运行的结果：-List Demo is running.- First is InsertList func

29、tion. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 List A length now is 2. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 List A length now is 3. name stuno age score zmofun 100001 80 1000 bobjin 100002 80 1000 stu1 100001 80 1000 List B length now i

30、s 3. Second is UnionList function. Now union List A and List B. name stuno age score stu1 100001 80 1000 stu2 100002 80 1000 stu3 100003 80 1000 zmofun 100001 80 1000 bobjin 100002 80 1000 List A length now is 5. Welcome to visit ! 三、总结线性表的定义线性表的类型定义回目录 上一课 下一课第六课本课主题： 线性表的顺序表示和实现教学目的： 掌握线性表的顺序表示和实现

31、方法教学重点： 线性表的顺序表示和实现方法教学难点： 线性表的顺序存储的实现方法授课内容：复习1、存储结构逻辑结构“数据结构”定义中的“关系”指数据间的逻辑关系，故也称数据结构为逻辑结构。存储结构数据结构在计算机中的表示称为物理结构。又称存储结构。顺序存储结构链式存储结构2、线性表的类型定义一、线性表的顺序表示用一组地址连续的存储单元依次存储线性表的数据元素。C语言中的数组即采用顺序存储方式。2000:00012000:00032000:00052000:00072000:00092000:00112000:00132000:00152000:0017.2000:10012000:100300

32、0000000000000100000000000000100000000000000011000000000000010000000000000001010000000000000110000000000000011100000000000010000000000000001001a9123456789假设线性表的每个元素需占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则存在如下关系：LOC(ai+1)=LOC(ai)+lLOC(ai)=LOC(a1)+(i-1)*l式中LOC(a1)是线性表的第一个数据元素的存储位置，通常称做线性表的起始位置或基地址。常用b表示。

33、线性表的这种机内表示称做线性表的顺序存储结构或顺序映象。称顺序存储结构的线性表为顺序表。顺序表的特点是以元素在计算机内物理位置相邻来表示线性表中数据元素之间的逻辑关系。二、顺序存储结构的线性表类C语言表示：线性表的动态分配顺序存储结构#define LIST_INIT_SIZE 100 #define LISTINCREMENT 10 typedef structElemType *elem; /存储空间基址int length; /当前长度int listsize; /当前分配的存储容量以一数据元素存储长度为单位SqList; 三、顺序存储结构的线性表操作及C语言实现：顺序表的插入与删除操作

34、：序号数据元素序号数据元素序号数据元素序号数据元素12345678912132124283042772412345678912132128304277插入前n=8;插入后n=9;删除前n=8;删除后n=7;顺序表的插入算法status ListInsert(List *L,int i,ElemType e) struct STU *p,*q; if (iL-length+1) return ERROR; q=&(L-elemi-1); for(p=&L-elemL-length-1;p=q;-p) *(p+1)=*p; *q=e; +L-length; return OK; /*ListIns

35、ert Before i */ 顺序表的合并算法void MergeList(List *La,List *Lb,List *Lc) ElemType *pa,*pb,*pc,*pa_last,*pb_last; pa=La-elem;pb=Lb-elem; Lc-listsize = Lc-length = La-length + Lb-length; pc = Lc-elem = (ElemType *)malloc(Lc-listsize * sizeof(ElemType); if(!Lc-elem) exit(OVERFLOW); pa_last = La-elem + La-length - 1; pb_last = Lb-elem + Lb-length - 1; while(pa=pa_last & pb=pb_last) if(Less_EqualList(pa,pb) *pc+=*pa+; else *pc+=*pb+; while(pa=pa_last) *pc+=*pa+; while(pb=pb_last) *pc+=*pb+; 顺序表的查找算法int LocateElem(List *La,ElemTyp