数据结构教程.docx

第十一课： 第十二课： 第十三课： 第十四课： 第十五课： 第十六课： 第十七课： 第十八课： 第十九课： 第二十课： 第二十一课 第二十二课 第二十三课 第二十四课 第二十五课 第二十六课 第二十七课 第二十八课 第二十九课
数据结构教程
第一课：数据结构的基本概念和术语
第二课：抽象数据类型的表示与实现
第三课：算法及算法设计要求
第四课：算法效率的度量和存储空间需求
第五课：线性表的类型定义
第六课：线性表的顺序表示和实现
第七课：实验一线性表的顺序存储实验
第八课：线性表的链式表示与实现
第九课：循环链表与双向链表
第十课：栈的表示与实现 栈的应用实验二循环链表实验
队列串的定义
串的表示和实现串操作应用举例
实验三：栈的表示与实现及栈的应用数组的顺序表示与实现
实验四串的实现实验广义表
:树、二叉树定义及术语:实验五数组实验
:二叉树的存储结构:遍历二叉树
:单元测验:图的定义与术语
:实验六二叉树实验:图的存储结构
:静态查找表（一）顺序表的查找
第三十课：静态查找表（二）有序表的查找
第三H^一课：动态查找表
第三十二课：哈希表（一）
第三十三课：哈希表（二）
第三十四课：插入排序，快速排序
第三十五课：实验七查找第三十六课：选择排序，归并排序 第三十七课：实验八排序实验 第三十八课：文件概念，顺序文件
#define ERROR 0#define OK 1
struct STU{ char name[20];
char stuno[10];int age; int score;
}stu[50];struct LIST
{ struct STU stu[50];int length;
}L；int printlist(struct LIST L)
{int i;printf("name stuno age score\n");
for(i=0;i<L.length;i++)printf("%s %s\t%d\t%d\n", L.stu[i].name, L.stu[i].stuno,
L.stu[i].age, L.stu[i].score);printf("\n");
}int listinsert(struct LIST *L,int i,struct STU e)
{struct STU *p,*q;if (i<1||i>L->length+1)
return ERROR;q=&(L->stu[i-1]);
for(p=&L->stu[L->length-1 ] ;p>=q ;-p)*(p+1)=*p； *q=e; ++L->length;
return OK;表结构本身是在查找过程中动态生成的，即对于给定值key,假设表中存在其关键 字等于key的记录，那么查找成功返回，否那么插入关键字等于key的记录。以政是 动态查找表的定义：
ADT DymanicSearchTable{数据对象D： D是具有相同特性的数据元素的集合。各个数据元素均含有类型相 同，可唯一标识数据元素的关键字。
数据关系R：数据元素同属一个集合。
基本操作P ：
InitDSTable(&DT);DestroyDSTable(&DT);
SearchDSTable(DT, key);InsertDSTable(&DT, e);
DeleteDSTable(&DT, key);TraverseDSTable(DT, Visit());
}ADT DynamicSearchTable二、二叉排序树及其查找过程
二叉排序树或者是一棵空树；或者是具有以下性质的二叉树：
1、假设它的左子树不空，那么左子树上所有结点的值均小于它的根结点的值；
2、假设它的右子树不空，那么右子树上所有结点的值均大于它的根结点的值；
3、它的左、右子树了分别为二叉排序树。
如果取二叉链表作为二叉排序树的存储结构，那么上述查找过程如下：
BiTree SearchBST(BiTree T,KeyType key){if (!T) | | EQ (key, T->data. key)) return (T);
else if LT (key, T->data. key) return (SearchBST(T->lchiId, key));else return (SearchBST(T->rchiId. key));
}//SearchBST三、二叉排序树的插入和删除
二叉排序树是一种动态树表，其特点是，树的结构通常不是一资生成的，面是在 查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结 点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一 个结点的左孩子或右孩子结点。
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){if (IT) {p=f;return FALSE;}
else if EQ (key, T->data. key){ p=T;return TRUE;}else if LT(key, T->data. key) SearchBsT (T->lchiId, key, T, p);
else SearchBST(T->rchild, key, T, p);}//SearchBST
插入算法：
Status InsertBST(BiTree &T, ElemType e) { if (!SearchBST(T, e. key, NULL, p) { s二(BiTree)malloc(sizeof (BiTNode));s->data=e;s->lchild=s->rchild=NULL;
if(!p) T=s;else if (LT(e. key, p->data. key) p->lchild=s;
else p->rchild=s;return TRUE;
}else return FALSE;
}//InsertBST在二叉排序树中删除一个节点的算法：
Status DeleteBST(BiTree &T, KeyType key){if(!T) return FALSE;
else {if EQ(key, T->data. key) Delete(T);
else if LT(key, T->data. key) DeleteBST(T->lchild, key);else DeleteBST(T->rchild, key);
return TRUE;void Delete(BiTree &p) { if (!p->rchild) {
q=p; p=p->lchild; free(q);else if (!p->lchild) {
q=p;p=p->rchild; free(q);else {
〃方法一：如图示
L，的左孩子接至p的右孩子删除后
q=p;s=p->lchild;
while (s->rchild) {q=s; s=s->rchild} 〃转左，然后向右到尽头p->data=s->data; //s指向被删结点的“前驱〃
if (q!=p)q->rchild=s->lchild; 〃重接*q 的右子树else q->lchild=s-〉lchild;〃重接*q的左子树(方法一结束)
〃或可用方法二：
〃q=s=(*p)->l;//while(s->r) s=s->r;
//s->r=(*p)->r;//free(*p);
〃(*p)=q；
删除前
删除后
请看一个例如源程序。
四、总结回目录上一课下一课
第三十二课
本课主题:哈希表（一）教学目的:掌握哈希表的概念作用及意义，哈希表的构造方法
教学重点:哈希表的构造方法教学难点:哈希表的构造方法
授课内容:
一、哈希表的概念及作用一般的线性表，树中，记录在结构中的相对位置是随机的，即和记录的关键字之 间不存在确定的关系，因此，在结构中查找记录时需进行一系列和关键字的比拟。 这一类查找方法建立在“比拟”的基础上，查找的效率依赖于查找过程中所进行 的比拟次数。
理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字 之间建立一个确定的对应关系f,使每个关键字和结构中一个唯一的存储位置相 对应。
哈希表最常见的例子是以学生学号为关键字的成绩表，1号学生的记录位置在第 一条，10号学生的记录位置在第10条...
如果我们以学生姓名为关键字，如何建立查找表，使得根据姓名可以直接找到相 应记录呢？
a
b
c
d
e
f
g
h
*
1
•
J
k
1
m
n
0
P
q
r
s
t
u
V
w
X
y
z
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

刘丽
刘宏英
吴军
吴小
艳
李秋梅
陈伟

姓名中各字拼音首字
母
11
Ihy
WJ
wxy
Iqm
CW
• • •
用所有首字母编号值
相加求和
24
46
33
72
42
26
• • •
最小值可能为3最大值可能为78可放75个学生
再壬述得到的数值作为对应记录在表中的位置，得到下委上面这张表即哈希表。

成绩一
成绩二...
3
• • •

24
刘丽
82
95
25
• • •

26
陈伟

• • •
• • •

33
吴军

• • •
• • ♦

42
李秋梅

• • •
• • ♦

46
刘宏英

• • •
• • •

72
吴小艳

• • •
• • ♦

78
• • •

如果将来要查李秋梅的成绩，可以用上述方法求出该记录所在位置：
李秋梅：lqm 12+17+13=42取表中第42条记录即可。
问题：如果两个同学分别叫刘丽 刘兰 该如何处理这两条记录？
这个问题是哈希表不可防止的，即冲突现象：对不同的关键字可能得到同一哈希 地址。
二、哈希表的构造方法
1、直接定址法例如：有一个从1到100岁的人口数字统计表，其中，年龄作为关键字，哈希函 数取关键字自身。
地址
01
02
• • •
25
26
27
• • •
100
年龄
1
2
• • •
25
26
27
• • •
• • •
人数
3000
2000
• • •
1050
• • •
• • •
• • •
• • •
• • •

2、数字分析法有学生的生日数据如下:
年•月.日
75. 10. 0375. 11.23
76. 03. 0207. 12
75. 04.2102. 15
经分析，第一位，第二位，第三位重复的可能性大，取这三位造成冲突的机会增 加，所以尽量不取前三位，取后三位比拟好。
3、平方取中法取关键字平方后的中间几位为哈希地址。
4、折叠法将关键字分割成位数相同的几局部（最后一局部的位数可以不同），然后取这儿 局部的叠加和（舍去进位）作为哈希地址，这方法称为折叠法。
例如：每一种西文图书都有一个国际标准图书编号，它是一个10位的十进制数 字，假设要以它作关键字建立一个哈希表，当馆藏书种类不到10, 000时，可采用 此法构造一个四位数的哈希函数。如果一本书的编号为0-442-20586-4,那么：
5864586442200224
+)
04
十）
04
6092

6092
10088H (key)=0088H(key)=6092
(a)移位叠加(b)间界叠加5、除留余数法
取关键字被某个不大于哈希表表长m的数P除后所得余数为哈希地址。
H (key)=key MOD p (p<=m)6、随机数法
选择一个随机函数，取关键字的随机函数值为它的哈希地址，即H (key)=random (key),其中random为随机函数。通常用于关键字长度不等时采 用此法。
三、总结哈希表的优缺点
四、作业预习如何处理冲突及哈希表的查找。
回目录上一课下一课第三十三课
本课主题:哈希表(二)教学目的:掌握哈希表处理冲突的方法及哈希表的查找算法
教学重点:哈希表处理冲突的方法教学难点:开放定址法
授课内容:
一、复习上次课内容什么是哈希表？如何构造哈希表？
提出问题：如何处理冲突？
二、处理冲突的方法

成绩一
成绩二...
3
• • •

24
刘丽
82
95
25
• • •

26
陈伟

♦ • •
・ ♦ ♦

33
吴军

• • •
• • •

42
李秋梅

• • •
♦ ・ ♦

46
刘宏英

• • •
• • •

72
吴小艳

• • •
• • •

78
• • •

如果两个同学分别叫刘丽刘兰，当加入刘兰时，地址24发生了冲突，我们可以 以某种规律使用其它的存储位置，如果选择的一个其它位置仍有冲突，那么再选下 一个，直到找到没有冲突的位置。选择其它位置的方法有：
1、开放定址法Hi=(H (key)+di) MOD m i=l, 2,..., k(k<=m-l)
其中m为表长，di为增量序列如果di值可能为1,2,称线性探测再散列。
如果 di 取值可能为 1,-1, 2, -2, 4, -4, 9, -9, 16,-16,... k*k, -k*k (k<=m/2) 称二次探测再散列。
如果di取值可能为伪随机数列。称伪随机探测再散列。
例：在长度为11的哈希表中已填有关键字分别为17,60,29的记录，现有第四个 记录，其关键字为38,由哈希函数得到地址为5,假设用线性探测再散列，如下:
}/*Listlnsert Before i */ main(){ struct STU e;
L.length=0;strcpy(e.name5ffzmofunM);
strcpy(e.stuno5M100001 ");e.age=80;
e.score=1000;listinsert(&L,19e);
printlist(L);printf("List length now is %d.\n\n",L.length);
strcpy(e.name5MbobjinM);strcpy(e.stuno5M100002M);
e.age=80;e.score=1000;
listinsert(&LJ,e);printlist(L);
printf("List length now is %d.\n\n",L.length);}
60172938
0
1
2
3
4
5
6
7
8
9
10
11
12
01
55
68 A
| 19 | -H- 68 | 人
I 20 I Al
| 10 | 4-> 1231A
I 11 I 人I

0
1
2
3
4
5
6
7
8
9
10

60
17
29
38

(d)伪随机探测再散列
0
1
2
3
4
5
6
7
8
9
10

38

60
17
29

伪随机数列为9, 5, 3,8,1...
2、再哈希法当发生冲突时，使用第二个、第三个、哈希函数计算地址，直到无冲突时。缺点: 计算时间增加。
3、链地址法将所有关键字为同义词的记录存储在同一线性链表中。
链地址法处理冲突时的哈希表
(同一链表中关键字有序)
4、建立一个公共溢出区 假设哈希函数的值域为那么设向量HashTable[O..m-1]为基本表，另外设立存储空间向量OverTable[0.. v]用以存储发生冲突的记录。
三、哈希表的查找〃开放定址哈希表的存储结构
int hashsize[] = {997,. . . );typedef struct{
ElemType *elem;int count;
int sizeindex;}HashTable;
ftdefine SUCCESS 1ftdefine UNSUCCESS 0
^define DUPLICATE -1Status SearchHash(HashTable H, KeyType K, int &p, int &c) {
p=Hash (K);while(H. elem[p]. key!=NULLKEY && !EQ(K, H. elem[p]. key)) collision (p, ++c);
if (EQ (K, H. elem[p]. key)return SUCCESS;
else return UNSUCCESS;)
Status InsertHash(HashTable &H, EleType e){c=0;
if (SearchHash (H, e. key, p, c))return DUPLICATE;
else if (c<hashsize[H. sizeindex]/2){H. elem[p]=e; ++H.count; return OK;
else RecreateHashTable(H);四、总结
处理冲突的要求是什么？
回目录上一课下一课第三十四课
本课主题:插入排序，快速排序教学目的:掌握排序的基本概念，插入排序、快速排序的算法
教学重点:插入排序、快速排序的算法教学难点:快速排序算法
授课内容:
一、排序概述排序：将一个数据元素的无序序列重新排列成一个按关键字有序的序列。
姓名
年龄
体重
1李由
57
62
2王天
54
76
3七大
24
75
4张强
24
72
5陈华
24
53
上表按年龄无序，如果按关键字年龄用某方法排序后得到下表:

姓名
年龄
体重
3七大
24
75
4张强
24
72
5陈华
24
53
2王天
54
76
1李由
57
62
注意反色的三条记录保持原有排列顺序，那么称该排序方法是稳定的! 如果另一方法排序后得到下表：

姓名
年龄
体重
原3, 4, 5记录顺序改变，那么称该排序方法是不稳定的！
4张强
24
72
，一■一.一
3七大
24
75
5陈华
24
53
2王天
54
76
1李由
57
62
内部排序：待排序记录存放在计算机随机存储器中进行的排序过程；
外部排序：待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。
二、插入排序1、直接插入排序
基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数
在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找 速度，可以采用折半查找，这种排序称折半插入排序。
3、2一路插入排序为减少排序过程中移动记录的次数，在折半插入排序的基础上加以改进：
i=l49
first
i=249
final
i=34965
final
i=44965
i=54965
i =64965
i=74965
i=84949
三、快速排序
97
final
7697
final
7697
final
7697
final
657697
38
first
38
first
38
first
38
first
1338
first
132738
first
132738
final first

49
38
65
97
78
13
27
49
• • •

1、起泡排序 首先将第一个记录的关键字和第二个记录的关键字进行比拟，假设为逆序，那么将两 个记录交换之，然后比拟第二个记录和第三个记录的关键字。直至第nT个记录 和第n个记录的关键字进行过比拟为止。
然后进行第二趟起泡排序，对前n-l个记录进行同样操作。
...直到在某趟排序过程中没有进行过交换记录的操作为止。
49
38
38
38
38
13
13
38
49
49
49
13
27
27
65
65
65
13
27
38
38
4997
977613
27
49
49
761327
49
49

132749
65

274978

初始第一趟第二趟第三趟第四趟第五趟第六趟2、快速排序
通过一趟排序将待排记录分割成独立的两局部，其中一局部记录的关键字均比另 一局部记录的关键字小，那么可分别对这两局部记录继续进行排序，以到达整个序 列有序。
初始关键字
1次交换之后
2次交换之后
3次交换之后
4次交换之后
49
完成一趟排序27381349769765
初始状态
49
38
65
一次划分
27
38
13
分别进行
13
27
38

结束

结束

初始状态
49
38
65
一次划分
27
38
13
分别进行
13
27
38

结束

结束

97
76
13
27
49
49
76
97
65
49

49
65
76
97

49
65

结束

结束

有序序列
132738
494965
76
97
四、总结
儿种排序的简单分析与比拟。（时间、空间复杂度）五、作业
实现直接插入排序、起泡排序、快速排序算法。
回目录上一课下一课第三十五课
本课主题:实验七查找教学目的:练习顺序查找、折半查找及二叉排序树的实现
教学重点:
教学难点:
授课内容:
顺序查找折半查找
顺序查找及折半查找例如二叉排序树
例如回目录上一课下一课
第三十六课本课主题:选择排序，归并排序
教学目的:掌握选择排序，归并排序算法教学重点:选择排序之堆排序，归并排序算法
教学难点:堆排序算法授课内容:
一、选择排序每一趟在n-i+l(i=l, 2,. .. n-1)个记录中选取关键字最小的记录作为有序序列 中第i个记录。
二、简单项选择择排序算法：
Smp_Selecpass(ListType &r,int i)k=i;
for(j=i+l;j<n;i++)if (r[j]. key<r[k]. key)
k=j;if (k!=i) { t=r[i] ;r[i]=r[k] ;r[k]=t;}
Smp_Sort(ListType &r) for(i=l;i<n-l;i++)Smp_Selecpass(r, i);
｝三、树形选择排序
又称锦标赛排序，首先对n个记录的关键字进行两两比拟，然后在其中一半较小 者之间再进行两两比拟，如此重复，直到选出最小关键字的记录为止。
四、堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。
什么是堆？ n个元素的序列｛kl,k2,...,kn｝当且仅当满足以下关系时，称之为堆。
关系一:ki<=k2i 关系二：ki<=k2i+l (i=l, 2,..., n/2)堆排序要解决两个问题：1、如何由一个无序序列建成一个堆？ 2、如何在输出堆 顶元素之后，调整剩余元素成为一个新的堆？ 问题2的解决方法:
(d) 27和97交换后调整的新堆

sift(ListType &r, int k, int m){
i=k;j=2*i;x=r[k]. key;finished=FALSE;t=r[k];
while ((j<=m)&&(!finished)){
if ((j<m)&&(r[jL key>r[j+l]. key)) j-tif (x<=r [j]. key)
finished:=TRUE;else {r[i]=r[j] ;i=j; j=2*i;}
E:\ZM\Zmdoc\datastru\class02>listdemo name stuno age score zmofun 100001 80 1000List length now is 1. name stuno age score bobjin 100002 80 1000 zmofun 100001 80 1000

抽象数据类型定义;抽象数据类型实现方法：一、类c语言实现 二、C语言实现
回目录上一课下一课
第三课
r i =t;}
HeapSort (ListType &r){
for (i=n/2; i>0; i--) sift (r, i, n);for(i=n;i>l;i--) {
r[1]<->r [i];sift (r, i, i-l)
}}
五、归并排序将两个或两个以上的有序表组合成一个新的有序表的方法叫归并。
假设初始序列含有n个记录，那么可看成是n个有序的子序列，每个子序列的长度 为1,然后两两归并，得到n/2个长度为2或1的有序子序列；再两两归并，如 此重复。

2一路归并排序例如•merge (ListType r, int Lint m, int n, ListType &r2)
{i=l;j=m+l;k=l-l;
while(i<=m) and(j<n) do{
k=k+1;if (r[i]. key<=r[j]. key) {r2[k]=r[i];i++;}
else {r2[i]=r[j];j++}}
if (i<=m) r2[k+l. . n]=r[i. . m];if (j<=n) r2[k+l.. n]=r[j.. n];
mergesort (ListType &r, ListType &rl, int s, int t)if (s==t) rl [s]=r [s];
else{
mergesort (r, r2, s, s+t/2);mergesort (r, r2, s+t/2+1, t);
merge (r2, s, s+t/2, t, rl);}
]六、总结
回目录上一课下一课第三十七课
本课主题:实验八排序实验教学目的:掌握简单插入排序、快速排序、堆排序的算法并加以应用。
教学重点:
教学难点:
授课内容:
实现下述三种算法，并用以下无序序列加以验证： 49, 38, 65, 97, 76, 13, 27, 49一、简单插入排序 二、快速排序
三、堆排序以上算法的C源程序。
回目录上一课下一课第三十八课
本课主题:文件概念，顺序文件教学目的:掌握文件基本概念，顺序文件的概念。
教学重点:文件基本概念教学难点:逻辑结构与物理结构的关系。
授课内容:
一、表与文件和表类似，文件是大量记录的集合。习惯上称存储在主存储器（内存储器）中的 记录集合为表，称存储在二级存储器（外存储器）中的记录集合为文件。
二、文件基本概念文件：是由大量性质相同的记录组成的集合。
文件按记 录类型不 同分类
操作系统的文
件
一维的连续的字符序列
数据库文件
带有结构的记录的集合,每条记录是由一个 或多个数据项组成的集合。
姓名
准考证号
政治
语文
数学
外语
刘青
1501
78
90
100
95
张朋
1502
64
88
90
74
1
崔永
1503
90
100
85
89
郑琳
1504
85
73
90
91

文件按记录定长记录文件 文件中每个记录含有信息长度相同。
长度是否相不定长记录文「八.文件中每个记录含有信息长度不等。
同分类 件 记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。
姓名
准考证号
政治
语文
数学
外语
刘青
1501
78
90
100
95
张朋
1502
64
88
90
74
崔永
1503
90
100
85
89
郑琳
1504
85
73
90
91
• • •

这张成绩表呈现的结构即是逻辑结构。
记录的物理结构是数据在物理存储器上存储的方式。一条物理记录指的是计算机 用一条I/O命令进行读写的基本数据单位。
三、顺序文件顺序文件中的物理记录的顺序和逻辑记录的顺序是一致的。
四、总结 回目录上一课下一课第三十九课
本课主题:索引文件教学目的:掌握索引文件的有关概念
教学重点:索引文件的基本概念，索引文件的重要意义教学难点:索引文件的建立
授课内容:
一、索引文件的基本概念除了文件本身（称作数据区）之外，别建立一张指示逻辑记录和物理记录之间一 一对应关系的表一索引表。
索引表中的每一项称作索引项。不管主文件是否按关键字有序，索引表中的索引 项总是按关键字（或逻辑记录号）顺序排列。
假设数据区中的记录也按关键字顺序排列，那么称索引顺序文件。反之，假设数据区中 记录不按关键字顺序排列，那么称非顺序文件。
数据区：
物理记录号
姓名
年龄
体重（关 键字）
1
李由
57
62
2
王天
54
76
3
七大
24
75
4
张强
24
72
5
陈华
24
53

索引表:
体重（关键字）
物理记录号
53
5
62
1
72
4
75
3
76
2
有了按体重索引的索引表后，按体重查找学生可先在索引表中查找（因索引表中 按体重有序，所以可用效率高的查找算法）然后得到对应的物理记录号后到数据 区取出对应物理记录。
索引文件可以大大提高表查找的速度。因为索引表容量小，且索引表按关键字有 序。
二、索引文件的建立在记录输入建立数据区的同时建立一个索引表，表中的索引项按记录输入的先后 次序排列，待全部记录输入完毕后再对索引表进行排序。
回目录上一课下一课第四十课
本课主题:总复习教学目的:数据结构综述
教学重点:数据结构课程的核心教学难点:理解概念
授课内容:
一、学习数据结构的意义设想一下，你决定向一个公司投资，而你对某个公司的了解只限于该公司的一条 生产线每分钟可生产2000件产品，你会作出投资的决定吗？如果你是一个公司 的管理者，这个公司日常的每笔交易的详细情况对你来讲确实重要，但如果你把 时间花在这些数据上面，你就无法站在宏观的高度上把握公司的经营方向。
不管是经营一个公司，还是管理一个国家，对描述事物特征的数据必须加以分析 与加工，现实事物是普遍联系的，描述这些事物属性及特征的数据之间也是普遍 联系的，把这些数据之间的关系进行总结，得到集合、线性、树、图这四种基本 关系，由此得到四类基本数据结构。而每种结构类型的数据，相同的操作（如遍 历、查找等）需要采用不同的方法（算法），不同结构类型可进行的操作也有区 别。通过应用这些算法，可得到事物的总体抽象特征。如：一个公司的年产值, 年利润总额，利润率等。
反过来，为了描述一个复杂的事物，必须分析它的组成局部，既要描述每个局部 的特征，又要描述各个局部之间的关系，如此细分下去，便于最终用计算机进行 处理，而计算机的基本数据类型不适合描述复杂的结构，且仅用基本数据类型也 不便于人的理解与记忆，所以使用介于两者之间的抽象数据类型成了计算机语言 描述现实事物的纽带。人可以方便的把事物用抽象数据类型描述，也可以方便的 把抽象数据类型用基本数据类型来实现，为用计算机处理现实问题提供了解决方 法。
二、数据结构的学习重点如何描述一种新的抽象数据类型？
如何分析算法的优劣？
线性表的主要特征。
线性表的存储表示（顺序表示、单向链表、循环链表、双向链表）特殊的线性表：栈、队列、串
二叉树的定义、性质、存储结构、遍历算法图的定义、术语、存储结构
静态查找表、二叉排序树、哈希函数的构造及冲突处理方法。
插入排序、快速排序、选择排序回目录上一课
附录资料:不需要的可以自行删除 libxml2应用实例
Libxml2是一个xml的c语言版的解析器，本来是为Gnome工程开 发的工具，是一个基于MIT License的免费开源软件。它除了支持c 语言版以外，还支持C++、PHP、Pascal. Ruby、Tel等语言的绑定, 能在Windows、Linux> Solaris、MacOsX等平台上运行。功能还是相 当强大的，相信满足一般用户需求没有任何问题。
二、Libxml2 安装：
一般如果在安装系统的时候选中了所有开发库和开发工具的话 (Fedora Core系列下)，应该不用安装，下面介绍一下手动安装：
1) 从 xmlsoft 站点或 ftp (ftp. xmlsoft. org)站点下载 libxml 压 缩包(libxml2-xxxx. tar. gz)2)对压缩包进行解压缩tar xvzf libxml2-xxxx. tar. gz
3)进入解压缩后的文件夹中运行
./configure —prefix /home/usei7 myxml/xmlinst(止匕处为 待安装的路径)或者直接使用./configure
make make install
4) 添加路径export PATH=/home/user/myxml/xmlinst/bin:$PATH
说明：为了结构清晰，最好将libxml2不安装在解压目录中。
安装完成后就可以使用简单的代码解析XML文件，包括本地和远程 的文件，但是在编码上有一些问题。Libxml默认只支持UTF-8的编 码，无论输入输出都是UTF-8,所以如果你解析完一个XML得到的结 果都是UTF—8的，如果需要输出GB2312或者其它编码，需要ICONV 来做转码（生成UTF-8编码的文件也可以用它做），如果系统中没有 安装iconv的话，需要安装libiconv。
1）下载 libiconv 压缩包（例如 libiconv-1. 11. tar. gz）
2）对压缩包进行解压缩 tar xvzf libiconv-1. 11. tar. gz
3）进入解压缩后的文件夹中运行./configure
makemake install
三、关于XML：
在开始研究Libxml2库之前，先了解一下XML的相关基础。XML是 一种基于文本的格式，它可用来创立能够通过各种语言和平台访问的 结构化数据。它包括一系列类似HTML的标记，并以树型结构来对这 些标记进行排列。
本课主题:算法及算法设计要求教学目的:掌握算法的定义及特性，算法设计的要求
教学重点:算法的特性，算法设计要求教学难点:算法设计的要求
授课内容:
一、算法的定义及特性1、定义：
ispass(int num[4][4]){ int i, j ;
for(i=0;i<4;i++)for(j=0;j<4;j++)
if (num[i] [j] !=i*4+j+l)/*一条指令，多个操作*/return 0;
return 1;}/*上面是一个类似华容道避戏中判断游戏是否结束的算法*