目录目录 (1)第一章绪论 (5)一、内容提要 (6)二、学习重点 (6)三、例题解析 (6)第二章线性表 (10)一、内容提要 (10)二、学习重点 (11)三、例题解析 (13)第三章栈和队列 (21)一、内容提要 (21)二、学习重点 (22)三、例题解析 (24)第四章串 (36)一、内容提要 (36)二、学习重点 (37)三、例题解析 (37)第五章数组和广义表 (43)一、内容提要 (43)二、学习重点 (44)三、例题解析 (44)第六章树和二叉树 (48)一、内容提要 (49)二、学习重点 (49)三、例题及分析 (51)第七章图 (58)一、内容提要 (58)二、学习重点 (59)三、例题解析 (61)第八章动态存储治理 (70)一、内容提要 (70)二、学习重点 (71)三、例题解析 (71)第九章查找 (77)一、内容提要 (77)二、学习重点 (78)三、例题解析 (79)第十章内部排序 (87)一、内容提要 (87)二、学习要点 (88)二、例题解析 (89)第十一章外部排序 (98)一、内容提要 (98)二、学习要点 (99)三、习题解析 (99)第十二章文件 (105)一、内容提要 (105)二、学习重点 (106)第一章绪论一、内容提要1 数据结构研究的内容。
2 差不多概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。
3 算法的定义及五个特征。
4 算法描述：类PASCAL语言。
5 算法设计要求。
6 算法分析。
二、学习重点1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）。
2 抽象数据类型的定义、表示和实现方法。
3 类PASCAL书写规范，过程（函数）中值参和变参的差不，过程调用规则。
4 用计算语句频度来估算算法的时刻复杂度。
三、例题解析1 写出以下各语句执行次数（左边括号内数字为语句序号）(1) FOR i:=1 TO n DO(2) FOR j:=1 to n DO(3) [ c[I,j] := 0;(4) FOR k:=1 TO n DO(5)c[I,j]:=c[I,j]+a[I,k]*b[k,j] ][答案]：各语句执行次数（频度）分不为n+1，n(n+1), n2 , n2(n+1), n3[分析]：最容易发生的错误，是将第一个语句的执行次数答成n。
2 编写最优算法，从小到大依次输出顺序读入的三个整数PROC asscending;{本算法对读入的三个整数进行排序，然后按从小到大输出} {算法中核心语句如下}read(a,b,c);IF a>bTHEN [t:=a; a:=b; b:=t]; {a,b按正序排序}IF b>cTHEN [t:=c; c:=b; {c为最大}IF a<t THEN b:=t {b为中间值}ELSE [b:=a; a:=t] {a,b正序}WRITELN(a:4,b:4,c:4);ENDP; {assending}[分析]：本题正确算法有多种，但上面是最优算法：最好情况下只通过两次比较且许多据移动，而在最坏情况下，也只是通过三次比较，七个赋值语句就完成了排序。
在本课程教学中，强调“好”的算法, 不仅仅是结果正确, 而且是最优的算法。
这与PASCAL语言教学中的要求有专门大不同。
算法是供人来阅读的，必须牢记这一点。
算法中语句的书写格式采纳缩进规则，保留字用大写，其余标识符小写，提高了算法的易读性。
第二章线性表一、内容提要1．线性表是元素间约束力最强的一类数据结构。
2．线性表的逻辑结构定义，对线性表定义的操作。
3．线性表的存储结构：顺序存储结构和链式存储结构。
4．线性表的操作在两种存储结构中的实现。
5．一元多项式的线性表表示方法，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现。
二、学习重点1．1．线性表的逻辑结构，指线性表的数据元素间存在着线性关系。
在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。
2．2．顺序存储结构用向量（一维数组）表示，给定下标，能够存取相应元素，属于随机存取的存储结构。
3．3．尽管“只要明白某结点的指针就能够存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。
4．4．链表是本章学习的重点和难点。
要理解头结点，首元结点和元素结点的差不。
理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。
掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。
5．5．链表操作中应注意不要使链意外“断开”。
因此，若在某结点前插入一个元素，或删除某元素，必须明白该元素的前驱结点的指针。
6．6．从时刻和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。
7．7．静态链表是又一重点和难点。
应和链表进行比较、理解。
例如，在有头结点的链表情况下，第一元素是p:=la^.next，而在静态链表中则i:=sa[0].next；相对p:=p^.next,有i:=sa[i].next来找到第i个元素的后继。
三、例题解析１．设线性表以顺序存储结构存于a(1..n)中，试编写算法将该线性表就地逆置。
【分析】向量逆置有几种方法，如逆向读入到另一数组中，在正向对应赋值，即：FOR i:=n DOWNTO 1 DO b[n-i+1]:=a[i]; FOR i:=1TO n DO a[i]:=b[i];那个地点要求“就地逆置”，即不能另用一数组空间。
【算法】PROC invert(VAR a:arr; n:integer);{a是存储线性表的一维数组，有n 个元素，本算法将a逆置。
}FOR i:=1TO (n DIV 2) DO a[i]↔a[n-i+1];endp;【讨论】将n个元素的一维数组逆置，什么缘故循环操纵变量用n div 2，而不用n？２．编写在单链表上进行排序的算法【分析】那个地点使用插入排序。
链表中插入元素要明白待插入元素位置的前驱，以pre表示之。
结束的条件是链表为空。
【算法】PROC insertsort(VAR la:linklist);{la是带头结点的单链表的指针，本算法将链表中元素正序排序。
算法的差不多思想是先假定第一个元素有序，然后从第二个元素开始，依次插入到有序的表中，直到全部元素插入完为止}p:=la^.next^.next;{假定链表非空，即至少有一个结点}la^.next^.next:=nil;{设有序链表中当前只有一个结点}found:=false;WHILE (p<>nil)AND NOTfound DO[s:=p^.next;{记住下一个结点}pre:=la;q:=la^.next;found:=false;WHILE(q<>nil)ANDNOT found DOIFq^.data<p^.data THEN[pre:=q; q:=q^.next]ELSE found:=true;p^.next:=q;pre^.next:=p;{p结点插入}p:=s;{取下一个结点}]ENDP; {insertsort} 【讨论】算法中found为一布尔变量，为的是在链表到尾前，如找到p的插入位置，即可退出WHILE循环。
那个地点循环条件未写成：（p<>nil）AND (q^.data<p^.data) 因为若q=nil ，则再引用q^.data是无意义的。
请记住这种退出循环，引入布尔变量的作法。
3．设两个非递减有序的线性表各有m和n个元素（m>0,n>0）,分不存于一维数组a和b中，且a 的存储空间足够大。
试编写算法将两线性表合并成一线性表，结果仍是非递减有序，要求算法的时刻复杂度是o(m+n)。
【分析】两个有序线性表合并成一个有序表，教材中已有讨论，算法特不简单。
本算法要求复杂度为O(m+n)，这是着重点。
题目叙述中有“a的空间足够大”，暗示出若将m+n个元素合并到a中，可不能溢出。
为使数据移动次数最少，应先将两表中最大元素置于m+n的位置上，然后相应指针减1，再比较之，直到两表中有一个指针减到0，则结束，否则，将b中剩余元素传到a中相应位置即可。
【算法】PROC union(VARa:seqlisttp;b:seqlisttp);{a,b是两个非递减有序表，顺序存储结构存储，各有m和n个元素，本算法将两表合并到a中，仍为有序表，算法时刻复杂度为O(m+n)}i:=m; j:=n ;k:=m+n; {i,j,k分不为表a,b和结果表的指针}WHILE (i>0) AND (j>0) DOIF a[i]>b[j] THEN [a[k]:=a[i];i:=i-1; k:=k-1]ELSE [a[k]:=b[j];j:=j-1; k:=k-1];WHILE (j>0) DO [a[k]:=b[j]; j:=j-1;k:=k-1];{若b表中尚有元素，则传至a中相应位置}【讨论】本算法至多比较m+n次，往a中赋值m+n次。
最好情况是比较n次，往a中赋值n次，该种情况是b中最小元素不小于a中最大元素。
问题：什么缘故在退出第一个WHILE循环后，不讨论（即没有）WHILE i>0的情况？第三章栈和队列一、内容提要1．1．从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。
但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。
2．2．栈的定义及操作。
栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。
3．3．栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。
4．4．栈的应用：表达式求值，递归过程及消除递归。
5．5．队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）。
因此在两种存储结构中，都需要队头和队尾两个指针。
6．6．链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。
二、学习重点1．栈和队列操作在两种存储结构下的实现。
2．中缀表达式转成前缀、后缀表达式并求值。
3．用递归解决的问题：定义是递归的，数据结构是递归的，及问题的解法是递归的，掌握典型问题的算法。
4．4．链队列删除时为空的处理（令队尾指针指向队头）。
特不是仅设尾指针的循环链队列的各种操作的实现。
5．5．循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示）及设标记方法（下面例题）。
那个地点特不注意取模运算。
6．6．在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍历等则用到队列。