数据结构教案 - 安徽新华学院
数据结构教案
作者：admin&&文章来源：信息工程学院&&点击数：12298&&更新时间：&&字体大小：
&&&&&&&& 1
&&&&&&&& 2
&&&&&&&& 3
1.1基本概念和术语
数据(data)：是对客观事物的符号表示，在计算机科学中是指所有能输入计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的对象是字符串。因此，对计算机而言，数据的含义极为广泛，如图象， 声音等都可以通过编码而归数据的范畴
数据元素(data element)：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。有时，一个数据元素可由若干个数据项组成。数据项是不可分割的最小单位。
数据对象(data object)：是性质相同的数据元素的集合，是数据的一个子集。
数据结构(data structure)：是相互之间存在一种或多种特定关系的数据元素的集合。数据元素都不是孤立存在 的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构(structure)。包括三方面内容：
(1)数据元素之间的逻辑关系，也称为数据的逻辑结构；
(2)数据元素及其关系在计算机存储器内的表示，称为数据的存储结构；
(3)数据的运算，即对数据施加的操作。
数据的逻辑结构：
数据的存储结构
1.2抽象数据类型的表示与实现
数据类型可分为：
抽象数据类型:&
&&&&&&&&&&&&&& :
&&&&&&&&&&&&&& :
&&&&&&&&&&&&&& :
&&&&&&& D SD PD
存在的数据类型
精选了C 的一个子集，扩充修改，增强了语言的描述功能。
l&&&&&& 预定义常量和类型
l&&&&&& 数据结构的表示：存储结构用类型（typedef）定义来描述。
数据元素类型约定为ElemType.
l&&&&&& 基本操作的算法用函数描述：
函数类型 函数名（函数参数表）
{/*算法说明*/
1.3 算法的描述和算法的分析
1、算法（Algorithm）
是对特定问题求解步骤的一种描述，它是指令的有限序列。
算法具有五个重要特性：有穷性、确定性、可行性、输入、输出
2、算法设计的要求
正确性、可读性、健壮性和效率与低存储量要求
3、算法效率的度量
算法时间是由控制结构和原操作的决定的。做法：选取一种是基本操作的原操作，以该基本操作重复的次数作为算法的时间量度。
时间复杂度：算法中基本操作重复执行的次数是问题规模n的某个函数f（n），
T（n）=O（f（n））
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长绿相同。
&&& 语句的频度：是该语句重复执行的次数。
例：求两个n阶方阵的乘积C=A×B，其算法如下：
#define n 100
void MatrixMultiply(int A[n][n],int B[n][n],int C[n][n])
&&& int i,j,k
&&& &for (i=1;i&=n;++i)&&&&&&&&&&&&&&&&&&&&&&&&&& n+1
&&&&&&& for (j=1;j&=n;++j)&&&&&&&&&&&&&&&&&&&&&&&& n*(n+1)
&&&&&&&&&&& C[i][j]=0;&&&&&&& &&&&&&&&&&&&&&&&&&&&&&n2
&&&&&&&&&&& for (k=1;k&=n,k++)&&&&&&&&&&&&&&&&&&&&& n2(n+1)
&&&&&&&&&&&&&&& C[i][j]=C[i][j]+a[i][k]*b[k][j];&&&& n3
T(n)=2n3+3n2+2n+1
limT(n)/ n3=2&&&&
T(n)=O(n3)
（a）{++x;s=0;}
（b）for (i=1;i&=n;++i) {++x;s+=x;}
（c）for (j=1;j&=n;++j)
for (k=1;k&=n;k++){++x;s+=x;}
含基本操作“x增1”的语句的频度分别为1,n和n2
时间复杂度是O(1),O(n)和O(n2)。
时间复杂度有时与输入有关。
4、算法的存储空间需求
空间复杂度：S（n）=O（f（n））
p1.1& p1.3& p1.5&
&&&&&&&& 1
&&&&&&&& 3
&&&&&&&& 4
L=a1,…,ai-1,ai,ai+1,…an
void unin(List &La &List Lb)
La_len=(ListLength(La));& Lb_len=(ListLength(Lb));
for (i=1;i&=Lb_i++){
GetElem(Lb,i,e);
&&&&&&&& if (!LocateElem(La,e,equal)) ListInsert(La,++La_len,e);
&&&&&&&& /*La e */
&&&&&&&& }
OListLength(LA) ListLength(LB)
2 LALBLCLC
void MergeList(List La, List Lb, List &Lc)
InitList(Lc);
i=j=k=1; k=0;
La_len=(ListLength(La));& Lb_len=(ListLength(Lb));
while (i&=La_len)&&(j&=Lb_len)
&&&&&&&&&&&&&&&&&&&& GetElem(La,i,ai); GetElem(Lb,j,bj);
if(ai&=bj){ListInsert(Lc,++k,ai);++i;}
else {ListInsert(Lc,++k,bj);++j;}
while (i&=La_len)
&&&&&&&&&&&&& GetElem(La,i++,ai); ListInsert(Lc,++k,ai);
while (j&=Lb_len)
&&&&&& & GetElem(Lb,j++,bj); ListInsert(Lc,++k,bj);
&&&&&& OListLength(LA) +ListLength(LB)
LOC(ai+1)=LOC(ai)+l
LOC(ai)=LOC(a1)+(i-1)*l
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
type struct{
&&&&&&&&&&&&& ElemType *
&&&&&&&&&&&&&
&&&&&&&&&&&&& int&
Status InitList_Sq(SqList &L)
&&&&&& L.elem=(ElemType )malloc(LIST_INIT_SIZE*sizeof(ElemType));
&&&&&& If (!L.elem)exit(OVERFLOW);
&&&&&& L.length=0;
&&&&&& L.listsize= LIST_INIT_SIZE;
&&&&&& Return OK;
Status ListInsert_Sq(SqList &L, int i, ElemType e )
if (i&1||i&L.length+1) return ERROR;
if (L.length&=L.listsize)
newbase=(ElemType )realloc(L.elem,(L.listsize+LISTINCREMENT)sizeof(ElemType));
&&&&&& if(!newbase)exit(OVERFLOW);
&&&&&& L.elem=
&&&&&& L.listsize+= LISTINCREMENT;
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]);p&=q;--p)*(P+1)=*p;
return OK;
OListLength(LA) ListLength(LB)
OListLength(LA) +ListLength(LB)
typedef struc LNode{
&&&&&& ElemType&&&&&& &&&&&
&& struct& LNode&& *next&&
}LNode, *LinkList
Status GetElem_L(LinkList L, int i, ElemType){
& /*ieOKERROR*/
& p=L j=1;
& while(p && j&i){
& p=p ++j;
& return OK;
aba xa x x baxb
snext=pnextpnext=s
Status ListInsert_L(ListLInk &L,& int i, ElemType e){
& p=L;& j=0;
& while(p && j&i-1){p=p ++j;}
& if (!p || j&i-1) return ERROR;
& s=(LinkList)malloc(sizeof(LNode));
& sdata=e; snext=p-
& pnext=s;
& return OK;
pnext=pnextnext
#define& MAXSIZE& 1000
typedef& struct{
&&&&&& ElemType&
&&&&&& Int&&&&&&&
}component, SLinklist[MAXSIZE];
S[i].cur i+1
int& LocateElem_SL(SLinkList L, ElemType){
& while(i &&S[i].data!=e) i=S[i].
typedef struct DuLNode {
ElemType&&&&&&
struct DuLNode& *
struct DuLNode& *
} DuLNode, *DuL
NextElemPriorElemO1
p2.1& p2.3& p2.5&& p2.8
&&&&&&&& 1
&&&&&&&& 2
stack):TOPbottom).
&&&&&&&&&&&&& 1
&&&&&&&&&&&&& 2
&&&&&&&&&&&&& 3
&&&&&&&&&&&&& 4
&&&&&&&&&&&&& 5
&typedef struct {
&&&&&&&& SElemType&& *
&&&&&& &&SElemType&& *
&&&&&&&& int&&
&&&&&&&& } SqS
&SqStack&& s
&&&&&&&&&&&&& base = NULL
&&&&&&&&&& a. toptop=base
&&&&&&&&&& b. top=base
&&&&&&&&&& c. top
&&&&&&&&&&&&&&
stacksize ——
ls. top =s. base&
l&s.top-s.base&=s.stacksize
l&*s.top++=e;& *s.top=e; s.top++;
l&e=*--s.top s.top-- e=*s.top
Status InitStack (SqStack &S) {
&& S.base = (SElemType )malloc(STACK_INIT_SIZE * sizeof(ElemType));
if (!S.base) return (OVERFLOW);
S.stacksize = STACK_INIT_SIZE;
return OK;
Status& GetTop(SqStack S, SElemType& &e)
if (S.top == S.base) return ERROR;
e = *(S.top-1);
return OK;
Status& Push(SqStack& &S, SElemType& e)
& if (S.top-S.base&=S.stacksize)
&&& { S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)
&&&&&&&&&&&&&&&&&&&&& *sizeof(ElemType));
&&&&&& if (!S.base) return (OVERFLOW);
&&&&&& S.top = S.base +S.
&&&&&& S.stacksize += STACKINCREMENT;
&*S.top++ = /*&& *S.top = S.top = S.top+1;
&return OK;
Status Pop(SqStack &S, SElemType& &e)
if (S.top == S.base) return ERROR;
&e=*--S.&& /*&& S.top= S.-1; e=*S.
&return OK;
&&&&&& &typedef struct SNode{
&&&&&& &&&&&&& SElemType&
&&&&&& &&&&&&& struct SNode& *
&&&&&& &&&&&&& }SNode, *LinkS
&&&&&& LinkS
l& & / Free Memory
Status& Push_L (LinkStack &sSElemType e)
&&& {& p=(LinkStack)malloc(sizeof(SNode));
&&&&&& if (!p) exit(Overflow);
&&&&&& p-&data =&& p-&next =& s=p;
&&&&&& return OK;
Status& Pop_L (LinkStack &s, SElemType &e)
&&& {& if (!s) return& ERROR;
&&&&&& e=s-&& p=s;& s=s-&
&&&&&& free(p);
&&&&&& return OK;
N=(N div d)*d + N mod d
void conversion(seqstack *s)
{SETNULL(s);
&scanf(“%d%d”,N,d);
{PUSH(s,N%d);& N=N/d; }
&while(!EMPTY(s))
{e=pop(s);& printf(“%d”,e);}
void EDIT(seqstack *s)
&SETNULL(s);
&c=getchar();
&while(c!=’*’)
&& {if(c==’#’) POP(s);
else if (c==’@’) SETNULL(s);
&&& else PUSH(s,c);
c=getchar( );
3& 表达式求值
&& 概念：前缀表达式，中缀表达式，后缀表达式
&&&&&&&&&& +a b,& a+b,& a b+
&& 算符：运算符和界符。
算符的优先关系。&、=、&
&& 算法的思想：设置两个工作栈：运算符栈OPTR和操作数栈OPND。操作数栈也放表达式的运算结果。首先置操作数栈为空栈，置运算符栈的栈底为表达式的起始符#。依次读入表达式中的每个字符，若是操作数则进OPND栈；若是运算符，则和OPTR中的栈顶元素做比较再操作，直至表达式求置完毕。
这里重点介绍中缀表达式转为后缀表达式，并对后缀表达式求值。
&（1）& 中缀表达式转为后缀表达式
& 设中缀表达式和后缀表达式分别在向量IFX和PFX申，用栈S实现中缀式转为后缀式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下。
&&& &1)栈初始化。
&&& &2)从左到右扫描向量IFX，重复下述两步操作，直到表达式尾。
&&&&& ① 从IPX中取出下个TOKEN(数字、运算符、左括号、右括号)；
&&&&& ② CASE& TOKEN& OF
&&&&&&&&&&&&& \'(\'：将TOKEN压入栈S;
&&&&&&&&& 操作数：将操作数直接送入PFX;
&&&&&&&&& 操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否则，退栈并将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之;
&&&&&&&&&&&&& ‘）’：退栈并将退栈元素送PFX，直到碰到左括号，左括号退栈不送PFX。
&& &3)当遇到中缀表达式结束符号，连续退栈并送退栈元素到PFX，直至栈空。
（2）& 对后缀表达式求值
& 用实型数栈S存放计算后缀式的中间及最终结果，求值算法可描述如下。
& &1)栈初始化。
& &2)从左到右扫描向量PFX，重复下述两步操作，直到表达式尾。
&&&&& ① 从PFX中取出下个TOKEN(操作数、运算符)
&&&&& ② CASE TOKEN OF
&&&&&&&&& 操作数：将操作数直接送入栈S1;
操作符：出栈两个操作数，对其进行TOKEN操作，结果压人栈S1
& &3)当遇到后缀表达式结束符号，栈顶的值就是结果(应是栈中唯一元素)。
4、栈与递归的实现
递归：在函数执行中，直接或间接调用自己的函数称为递归函数。
“递归工作栈”——栈顶为“工作记录”，包括参数、局部变量以及上一层的返回地址。
递归过程的应用：
问题的定义是递归的：f(n)=n*f(n-1)
数据结构是递归的：链表
问题的解法是递归的：Hanoi 塔问题
用栈实现递归函数
int FACT(n)
{if(n==1) return(1);
&else return(n*FACT(n-1));
1 Enqueue(&Q, e) Qe
2Dequeue(&Q, &e) Q
3Gethead(&Q, &e) Qe
4Queueempty(Q) Qtruefalse
typedef& struct QNode{
&&&&&&&&&&&&& QelemType&&&& &
&&&&&&&&&&&&& struct QNode&& *&
}QNode,& *QueueP
typedef&& struct{
QueuePtr&&&&&&& *&&&&&&&&&
QueuePtr&&&&&&& *
1Enqueue(&Q, e)
&&&&&&&& p=(QueuePtr) malloc(sizeof(node));& /**/
&&&&&&&& p-&data=e;
p-&next=NU
Q.rear-&next=p;&
2 Dequeue(&Q, &e)
if& (Q.front==Q.rear) return E
&&&&&&&& p=Q.front-&
&&&&&&&&&&&&&&&&&&&& e=p-&
Q.front-&next=p-&
if(Q.rear==p) Q.rear=Q.
Q.front = Q.rear=0
#define MAXSIZE 100
typedef struct {
&& QElemType& *
SqQueue& Q;
nQ.rear 1 Q.rear = Q.rear + 1
nQ.front 1 Q.front = Q.front + 1
l1maxSize -10()
l1:& Q.front = (Q.front + 1)% MAXSIZE
&& 1:& Q.rear = (Q.rear + 1)% MAXSIZE;
lQ.front = Q.rear = 0;
lQ.front == Q.rear;
l(Q.rear + 1) % MAXSIZE == Q.front
l(Q.rear-Q.front+MAXSIZE)%MAXSIZE
l& ----p63& “”
l Q.front=Q.rear“”“”
Status InitQueue (SqQueue &Q)
Q.base=(QElemTye *)malloc(MAXQSIZE*sizeof(QElemType));
& if (!Q.base) exit(OVERFLOW);
& Q.front=Q.rear=0;
& return OK;
int QueueLength(SqQueue Q)
&&&& return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
Status EnQueue (SqQueue &Q, QElemType e)
&&&&& if ((Q.rear+1) % MAXQSIZE ==Q.front) return ERROR;
&&&&& Q.base[Q.rear]=e;
&&&&& Q.rear = (Q.rear+1)%MAXQSIZE;
&&&&& return OK;
Status DeQueue(SqQueue &Q, QElemType &e)
&&&&& if (Q.rear==Q.front) return ERROR;
&&&&& e=Q.base[Q.front];
&&&&& Q.front=(Q.front+1)%MAXQSIZE;
&&&&& return OK;
Status QueueEmpty(SqQueue Q)
&&&&&& if (Q.front==Q.rear) return TRUE;
&&&&&& return FALSE;
Status GetHead(SqQueue Q,QElemType &e)
&&&&& if QueueEmpty(Q) return ERROR;
&&&&& e=Q.base[Q.front];
&&&&& return OK;
l/&& Q.rear = Q.rear + 1; Q.front = Q.front+1;
l%MAXQSIZE
l Q.front = Q.rear
l Q.rear&= MAXQSIZE
l& Q.rear - Q.front
p3.1& p3.2& p3.4&& p3.7&& p3.9
&&&&&&&& 1
&&&&&&&& 2
、S=’a1 a2an’ n&0
&& #define& MAXSTRLEN 255
typedef& unsigned& char Sstring[MAXSTRLEN +1];
typedef& struct{
&&&&&&&&&&&&&
&&&&&&&&&&&&&
&&&&&&&&&&&&&
#DEFINE&&&&&&&&&&&&& CHUNKSIZE& 80
typedef&&&&&&&&&&&&&&&&& struct Chunk{
&&&&&& char&&&&&&& ch[CHUNKSIZE];
&&&&&& struct&&&&& Chunk&&&&&&&&&&& *
typedef&&&&&&&&&& struct{
&&&&&& Chunk&&&&&&&&&&& *head, *
&&&&&& int&&&&&&&&&&&&&&&&&
、 Index(S, T, pos)
int index(SString S, SString T, int pos ){
&&&&&&&&&& i=&&& j=1;
&&&&&&&&&& while(i&=S[0]&&j&=T[0]){
&&&&&&&& & &&&&&&&&&& if (S[i]==T[j]{++i; ++j; }
&&&&&&&& & &&&&&&&&&& else{i=i-j+2;&&& j=1;}
(sipj)kinext[j]=knext
&&&&&&&&& 0&&&&& j=1
next[j]=&& Max{k | 1&k&j p1pk-1’=’pj-k+1pj-1}
&&&&&&&&&&&&&&&& &&&&&&&&&
&&&&&&&&&&&&& KMP
&&&&&& int& Index_KMP(SString S, SString T, int pos ){
&&&&&&&&&& i=&&& j=1;
&&&&&&&&&& while(i&=S[0]&&j&=T[0]){
&&&&&&&& & &&&&&&&&&& if (j==0 || S[i]==T[j]{++i; ++j; }
&&&&&&&& & &&&&&&&&&& else& j=next[j];
&&&&&&&&&& if (j&T[0]) return& i-T[0];
&&&&&&&&&& else return 0;
&&&&&&&&&&&&& next
&&&&&&&&&&&&& void get_next(SString T, int &next[] )
&&&&&&&&&&&&&&&&&&&& i=1;& next[1]=0;&&& j=0;
&&&&&&&&&&&&&&&&&&&& while(i&T[0]){
if(j==0 ||T[i]==T[j]){++i; ++j; next[i]=j;}
&&&&&& else j=next[j];
&&&&&&&&&&&&& }
p4.1& p4.3 &p4.4&& p4.5&&
、nbinaj1j2jn0jibi-2n j1,j2,jn
&& & &&&&& &&&&&&&&&
&&&&&&&& & Array1
LOCi , j= LOC0 , 0+(b2 * i + j) L
LOCj1j2jn= LOC0 , 0,0+ciji
cn=Lci-1=bi*ci
#include& &stdarg.h&
#define&& MAX_ARRAY_DIM& 8
typedef& struct{
&&&&&& ElemType&&&&&&&&&&&&& *
&&&&&& int&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&& int&&&&&&&&&&&&&&&&&&&&&&&& *
&&&&&& int &&&&&&&&&&&&&&& *
、sa[n(n+1)/2]n A sa[k]aij
&&&&& i(i-1)/2+j-1&&&&& i&=j
&&&&& j(j-1)/2+i-1&&&&& i&j
LS = α1α2 αn
&&&&&&&&&&&&& & α1
&&&&&&&&&&&&& & α2 αn
typedef&&&&&&&&&& enum{ATOM, LIST}ElemT
typedef& struct&&&&& GLNode{
&&&&&& ElemTag&&&&&&&&
&&&&&& union{
struct {struct& GLNode&&&&&& *hp , *}ptr
&&&&&& }*GL
p5.1& p5.2& p5.3&& p5.5& p5.7&& p5.8
&&&&&&&& Tree=(D,R)
3r0rRr0,r1,,rs,&ri-1,ri&H(1&=i&=s),r
&&& RF={&root,ri&|i=1,2,…,m,m&0}
3 Tn01n12n2n0= n2+1
(k0&=n&=2k-1-1)
4 nlog2n+1
5 1i(1&=i&=n)
2i+1&ni2i+1
#define& MAX_TREE_SIZE& 100
typedef& TElemType& SqBiTree[MAX_TREE_SIZE];
typedef& struct& BiTNode
TElemType&
struct& BiTNode& *lchild, *
}BiTNode ,*B
typedef& struct& BiTNode
{TElemType&
struct& BiTNode& *lchild, *rchild,*
}BiTNode ,*B
DLRDLR6DLRDRLLDRLRDRDLRLDDLRLDRLRD
typedef struct treenode
struct treenode *lchild,*
}treenode ,*
void preorder(r)
&& { visit(r-&data);&&&&&&&& /* */
&&&& preorder(r-&lchild);&&& /* */
&&&& preorder(r-&rchild);&&& /* */
void& create(pre,in,l,h,r)
/* preinn,lhr& */
int pre[n],in[n],l,h;
{ int i=l;
& while& (in[i]!=pre[l])& i++&&&& /*
& p=(struct treenode *)malloc(sizeof(treenode))
& p-&data=pre[l];
if (i=l)& p-&lchild=&&&&&&&&&& /*
else create(pre,in,l,i-1,p-&lchild)&&& /*
if (i=h)& p-&rchild=&&&&&&&&&& /*
&&& else create(pre,in,i+1,h,p-&lchild)& /*
.& int depth (tree BT)
&& {if (BT= =null)return0);
&&&&&& else {l=hepth (BT-&lchild);
&&& &&&&&&&&r=hepth(BT-&rchild);
&&&&&&&&&&& return((l&r?l:r)+1);
void exchg_tree(bitreptr BT)
&{if (BT!=null)&&&&&&&&&&& /**/
& {exchg_tree(BT-&lchild); /**/
&& exchg_tree(BT-&rchild); /**/
&& p=BT-&&&&&&&&&&& /**/
&& BT-&lchild=BT-&& BT-&rchild =p;
void preorder(tree T)
&& {if (T!=NULL)
&&&&& { printf(“%f”, T-&data);
preorder(T-&rchild);
preorder(T-&lchild);
void layorder (tree T)
&{initqueue (q)&&&&&&&&&&&&&&&&&&&&&& /**/
& if(T!=NULL)
&&& { enqueue (q, T);&&&&&&&&&&&&&&&&& /**/
&&&& while (not emptyqueue (q) )&&&&& /**/
&&&&&& {outqueue (q, p) ;&&&&&&&&&&&& /**/
&&&&&&& printf(“%f”, p-&data);
&&&&&&& if (p-&lchild!=NULL)
&&&&&&&&&& enqueue (q, p-&lchild);&&&&& /**/
&&&&&&& if (p-&rchild!=NULL)
&&&&&&&&&& enqueue (q, p-&rchild);&&&&&& /**/
&&&&&&& }&& /* end of while (not emptyqueue (q) )& */
tree create(r,A)
char A[n];
static i=0;
c=A[i]; i++;
if (c==’ ’) r=
&& else { r=(tree *)malloc(sizeof(treenode))
&&&&&&&& if (!r)& exit(0);
&&&&&&&& r-&data=c;
&&&&&&&&& r-&lchild=create(r-&lchild,A); /* */
&&&&&&&&& r-&rchild=create(r-&rchild,A); /* */
&&&&&&&& }
&return( r );
int countleaf(r);
{static& i=0;
&& { if ((r-&lchild==null) && (r-&rchild==null))& i++; /* */
countleaf(r-&lchild);&&&& /* */
countleaf(r-&rchild);&&&& /* */
&return(i);
1ltag=1lchildrtag=1rchild
Status& InOrderTraverse_Tri(BiThrTree T, Status(*Visit)(TElemType e))
&while(p!=T)
&& {while(p-&ltag==0)& p=p-&
if(!Visit(p-&data))& return& ERROR;
while(p-&rtag==1 && p-&rchild!=T)
& {p=p-& Visit(p-&data);
return& OK;
Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)
{if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))) exit(OVERFLOW);
Thrt-&ltag=0; Thrt-&rtag=1;Thrt-&rchild=T
if(!T) Thrt-&lchild=T
else {Thrt-&lchild=T; pre=T
&&&&& InThreading(T);
&&&&& pre-&rchild=T pre-&rtag=1; Thrt-&rchild=
return OK;
void InThreading(BiThrtTree p)
&& {InThreading(p-&lchild);
if(!p-&lchild){p-&ltag=1; p-&lchild= }
if(!pre-&rchild){pre-&rtag=1; pre-&rchild=p; }
InThreading(p-&rchild)
typrdef struct tnode
& { datatype&
& }tree[n]
typrdef struct tagnode&&&&&&&& /*
&&& struct tagnode *
& }node, *
typedef struct&&&&&&&&&&&&& /*
typedef headnode childlink[maxnode];&&& /*
typedef struct&&&&&&&&&&&&& /*
& }headnode1;
typedef struct treenode
struct treenode *fch,*
}treenode ,*
WPL=WiLi(i=1n)
1 n{w1,w2,…,wn}nF={T1,T2,…,Tn}Ti
typedef struct
& unsigned int parent,lchild,
} HTNode,*HT
typedef struct
{ unsigned int bits[n];
& m && ht[j].parent==0)&&&& /*
{ n=ht[j].w; y=j; }
} /* end of& for(i=1;i&=n;i++) */
c=i; f=ht[c].
{ if (ht[f].lchild=c cd.bits[cd.start]=0; /*
else cd.bits[cd.start]=1;&&&&&&&&&&&&&& /*
cd.start--; c=f; f=ht[f].
hcd[i]=&&&&&& /*
p6.1& p6.2& p5.3&& p6.6& p6.7&& p6.21
&&&&&&&& AOV
&&&&&&&&&&& &&&&Graph( V, E )&&&
&&&&&&&& &&&&&&&&E (edge)
2,(vi , vj ) (vi,vj )vivj;
3,& vi , vj && vi ,vj &vivj,vivj
&&& G=(V, E)(vi , vj)Evivj(Adjacent)(vi& , vj)vivj
&&& G=(V, A)& vi , vj &Avivjvjvi& vi , vj&vivj
n(n-1)/2 ,
n n(n-1) ,
G’(V’, E’), V’ V
&viTD(vi),
vi&& viID(vi)
vi(OutDegree) viOD(vi)
&G(V, E),vi ,()vp1, vp2, …, vpm vj (vi , vp1 , vp2 , ... , vpm , vj )vi vj
v1,v2,...,vm
&& vivjijvivj
&& , v1v2, v1v2,
&&& , vivj, vivjvjvi,
7& WeightNetwork
(Adjacency Matrix)
1 G= (V, E) n
G.arcs[n][n]:
2、无向图邻接矩阵的性质
（2）&&&& viii(1)
3、有向图邻接矩阵的性质
2&&&& viii
4、网的邻接矩阵
5、邻接矩阵的优缺点
typedef struct{
&datatype vexs[MAX_VERTEX_NUM];
int arcs[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];
7、建立邻接矩阵的算法
#define MAX& N&& /*N */
typedef struct
{ datatype& vaxs[MAX+1];& /*
& int arcs[MAX+1][MAX+1]; /*
& int vexnum,&&&&& /*
void creatgraph(g)
{ int i,j,k,vl,v2;
int LocateVex( );&&& /* 具体内容见下面算法 */
scanf("%d,%d",&g-&vexnum,&g-&arcnum);/* 输入图g的顶点数和边数*/
for (i=1;i&=g-&i++)
scanf(“%d”,&g-&vexs[i]);&& /* 输入各顶点值，设为int型 */
for (i=1;i&=g-&i++)
for(j=l;j&=g-&j++) g-&arcs[i][j]=0; /*初始化邻接矩阵 */
for(k=l;k&=g-&k++)
{ scanf("%d,%d",&vl,&v2);
/* 依次输入每条边关联的两个顶点的值:若顶点值不是int型，*/
/* 则应设置成其他的格式字串 */
i=LocateVex(g,v1);j=LocateVex(g,v2);
/ *确定两个顶点在图中的位置序号分别为i,j */
if (i!=0 && j!=0)&&& /* 如果输入的顶点在图中，则对邻接矩阵中 */
&&&&&&& { g-&arcs[i][j]=l; /* 的相应位置及其对称位置的元素赋值为l*/
g-arcs[i][j]=1;
&&&&&&&& }
int LocateVex(g,v)
mgraph *g;
&for (i=1;g-&vexs[i]!=v && i&=g-& i++); /* 查顶点v的下标i */
&if (i&g-&vexnum) return(0);
&else return(i);
二、图的邻接表表示法
邻接矩阵在稀疏图时空间浪费较大，为了克服这一缺点，可采用邻接表表示法。
1、邻接表的结点结构
（1）顶点结点结构
（2）边（弧）结点结构
其中，vexdata是顶点数据，firstarc是指向该顶点第一个邻接点的指针，adjvex是邻接点在向量中的下标，info是邻接点的信息，next是指向下一邻接点的指针。
2、邻接表是顶点的向量结构和边（弧）的单链表结构
每个顶点结点包括两个域，将n个顶点放在一个向量中（称为顺序存储的结点表）；一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。
3、邻接表的优缺点
容易实现图的前4个操作；
空间较省；
无向图容易求各顶点的度；边表中结点个数是边的两倍；
有向图容易求顶点的出度；若求顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）
4、建立邻接表的算法
#define MAX n&& /*定义最大顶点个数n为某一正整数 */
typedef struct EdgeNode
{&&&&&&&&&&&&&& /* 邻接点域，存储位置序号，为int型 */
& struct EdgeNode *& /* 链域，指向下一条边(弧)的指针 */
typedef struct VNode&&&&&&&& /* 头结点的类型 Vnode */
{ DataT&&&&&&&&& /*& 头结点的数据域 */
struct& EdgeNode *&&& /* 头结点的指针域 */
typedef VNode AdGraph [MAX+l];/* 定义图的类型AdGraph，为一个一维数组*/
void creatgraph(g)
{ int i,n,e,*p=g,v1,v2;&&&&& /* 假设顶点数据为int型 */
scanf("%d,%d",&n,&e);/* 输入图g的顶点数n和边数e*/
for (i=1;i&=n;i++)
{scanf(“%d”,p[i].vexdata);&& /* 输入各顶点值，设为int型 */
&p[i].link=
for (i=1;i&=e;i++)&&&&&&& /* 输入e条边 */
&{ scanf("%d,%d",&v1,&v2);/* 输入图g的顶点v1和v2 */
i=LocateVex(g,v1);j=LocateVex(g,v2);
/ *确定两个顶点在图中的位置序号分别为i,j */
if (i!=0 && j!=0)&&& /* 如果输入的顶点在图中 */
{ r=(Vnode *)malloc(sizeof(Vnode))
& r-&adjnum=j; r-&nextarc=p[i]-& /*链入i链表中*/
& p[i]-&link=r;
r=(Vnode *)malloc(sizeof(Vnode))
& r-&adjnum=i; r-&nextarc=p[j]-& /*链入j链表中*/
& p[j]-&link=r;
&&&&&&&& }
7．3 &图的遍历
图的遍历指，从图的某顶点出发，访问图的各顶点，使每个顶点被访问一次，且只被访问一次。访问的含义可以是输出个顶点的值，查询顶点，修改顶点等等。
本节介绍图的遍历的两种方法：深度优先遍历和宽度优先遍历，还介绍生成树的概念。为了遍历方便，设辅助数组visited，初始时，数组元素的值均为0或false，表示未被遍历，一旦遍历，就置为1或true。
一、深度优先遍历
1、深度优先遍历的思想
在图中从任意一个顶点（设为v0）开始，进行遍历,接着找v0的第一邻接点，若该邻接点未被遍历，则遍历之，再找该邻接点的第一邻接点，若该第一邻接点已被遍历，则找其下一邻接点。若下一邻接点未被遍历，则遍历，再找它的第一邻接点，就这样递归向下进行。若遇到第一邻接点不存在，或下一邻接点也不存在时，则退回到调用的上一层。如此下去，若不能遍历完所有顶点（说明不是连通图），则再选一个未遍历的顶点，重新开始以上过程，直至所有顶点遍历完毕。
2、深度优先遍历的实例模拟
书上有一例子。必须说明，若不给定存储结构，深度优先遍历的结果不唯一。因为哪个顶点是第一邻接点未确定。给定存储结构后，深度优先遍历的结果是唯一的。
3、深度优先遍历的算法
int visited[MAX+1]& /*辅助数组，是算法中需用到的全局变量 */
void dfs(g,v)&&&&&& /* 从图g的第v号顶点出发深度优先遍历 */
AdGraph& g[MAX+1]
{ EdgeNode *p;
& printf(“6d”,g[v].vexdata)&&&& /* 首先访问该顶点，假设其数据为整数 */
& visited[vl=1;
&&& { if(visited[p-&adjnum]!=l) dfs(g,p-&adjnum);
&&&&&&&&&&&&&&&&&& /* 若该顶点末被访问过，则递归调用 */
&&&&& p=p-&&& /* p指向下一个与第v个顶点链接的表结点 */
void dfstravel(g,n)&&&&& /* 深度优先遍历顶点个数为n的图g */
AdGraph g[MAXX+l];
for (v=1;v&=n;v++) visited[v]=0;
/*初始化辅助数组，表示所有顶点均末被访问过 */
for (v=1;v&=n;v++)&& /*对图中所有未被访问过的顶点进行深度优先搜索*/
if (visited[v]!=1) dfs(g,v)
4、深度优先遍历生成树
图的所有顶点加上遍历中经过的边所构成的子图叫图的生成树。
5、深度优先遍历算法分析
对于连通图，在dfstravel函数中只要调用一次dfs，即可遍历图中所有顶点。对于非连通图，有几个连通分量，则调用几次。由此，也知道了如何求连通分量的个数。
&& 当用二维数组表示邻接矩阵作图的存储结构时，查找每个顶点的邻接点所需时间为O(n2)，其中n为图中顶点数。而当以邻接表作图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图的边数或有向图的弧数。由此，当以邻接表作存储结构时，深度优先遍历图的时间复杂度为0(n+e)。
二、宽度优先遍历
1、宽度优先遍历的基本思想
宽度优先遍历又称广度优先遍历，和树的层次遍历类似。从图中任意一个顶点（设为v0）开始遍历,接着依次遍历v0的所有邻接点（每个邻接点被遍历一次且只一次），再遍历这些邻接点的邻接点，……。如此下去，若不能遍历完所有顶点（说明不是连通图），则再选一个未遍历的顶点，重新开始以上过程，直至所有顶点遍历完毕。
2、宽度优先遍历的实例模拟
必须说明，若不给定存储结构，宽度优先遍历的结果不唯一。因为哪个顶点是第一邻接点未确定。给定存储结构后，宽度优先遍历的结果是唯一的。
3、宽度优先遍历的算法
使用队列。
4、宽度优先遍历生成树
图的所有顶点加上遍历中经过的边所构成的子图叫图的生成树。
5、宽度优先遍历算法分析
&& 宽度优先遍历时间复杂度和深度优先遍历相同，二者不同仅在于对顶点访问的顺序不同。
7·4& 图的连通性问题
一、无向图的连通分量和生成树
1、无向图的连通分量
& 对于连通图，一次调用DFS或BFS即可遍历图的全部顶点；对于非连通图，多次调用DFS或BFS才能遍历完图的全部顶点。每次调用所得的顶点访问序列就是各连通分量的顶点集。
& 对于连通图，调用DFS或BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵生成树。
3、生成森林
对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。
4、生成森林的算法
void& DFSForest(Graph G,CSTree &T)
&for (v=0;v&G.++v)
visited[v]=
for (v=0;v&G.++v)
if (!visited[v])
& {p=(CSTree)malloc(sizeof(CSNode));
&& *p={GetVex(G,v),NULL,NULL};
&& if (!T) T=p;
&& else q-&nextsibling =
&& DFSTree(G,v,p);
void DFSTree(Graph G,int v, CSTree &T){
visited[v]=TRUE; first=TRUE;
for(v=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))
& if(!visited[v])
{ p=(CSTree)malloc(sizeof(CSNode));
&& *p={GetVex(G,v),NULL,NULL};
&& if (first) { T-&lchild=p;first=FALSE;}
&& else {q-&nextsibling=p;
&& DFSTree(G,w,q);
二、最小生成树
1、问题的提出
假设n个城市间建立通信联络网，连通n个城市需要n-1条线路，而n个城市间最多有n(n-1)/2条线路，如何从n(n-1)/2条中选取n-1条线路，使总的耗费最少。
2、由无向连通图构造最小生成树的方法
（1）从图中任意顶点开始，将其包括在最小生成树中；
（2）再选取权值最小的边，使其一个顶点已在生成树中，而另一个顶点尚不在生成树中，将该顶点加入生成树。若这样的边有多个，任选一个。
（3）重复（2），直至所有顶点都包括在生成树中。这就是最小生成树。
具体说，构造最小生成树有两种方法：普里母（prim）和克鲁斯卡尔（kruskal）方法。
3、生成最小生成树的算法
}closedge[MAX_VERTEX_NUM];
void MiniSpanTree_PRIM(Mgraph G,VertexType u){
& k=LocateVex(G,u);
& for(j=0;j&G.j++)
if(j!=k)closedge[j]={u,G.arcs[k][j].adj};
& closedge[k].lowcost=0;
& for(i=0;i&G.i++)
&& {k=minimum(closedge);
printf(closedge[k].adjvex,G.vexs[k]);
closedge[k].lowcost=0;
&&& for(j=0;j&G.j++)
& if(G.arcs[k][j].adj&closedge[j].lowcost)
&&&&& closedge[j]={G.vexs[k],G.arcs[k][j].
4、生成最小生成树算法的分析
求具有n个顶点e条边的连通图的最小生成树，使用普里母算法时间复杂度为O(n2),和图的边数无关，适合边稠密的情况。克鲁斯卡尔算法时间复杂度为(eloge)，适合边稀疏的情况。
一、拓扑排序
1、拓扑排序的基本概念
（1）AOV网
顶点表示活动，弧表示活动间的优先关系的有向图，叫顶点表示活动的网（Activity On Vertex Network）。
（2）拓扑序列
将AOV网上的所以顶点排成一个线性序列，且该序列满足若在AOV网中，顶点vi到vj有一条路径，则在该线性序列中vi必在vj的前面。这样的序列称为拓扑序列。
（3）拓扑排序
对AOV网构造拓扑序列的操作叫拓扑排序。
（4）在AOV网中不应有环，否则就会自己以自己为先决条件；若AOV网代表一个工程，则AOV网的一个拓扑序列就是一个工程顺利完成的可行方案。
2、拓扑排序的方法
（1）&&&&&&&& 从图中选择一个入度为0的顶点输出；
（2）&&&&&&&& 从图中删除该顶点及源自该顶点的所有弧；
（3） &重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行。
3、&拓扑排序算法
在邻接表的顶点向量中，向量的每个元素再增加一个入度域，存放各顶点的入度值。输出该顶点，删除源自该顶点的弧就是将该顶点的邻接点的入度减1。实际实现时，可设一个栈，存放入度为0的顶点，退栈就是输出顶点，当邻接点的入度域减1减到0时，就将其入栈，拓扑排序完成时，栈应为空。
Status ToplogicalSort(ALGraph G){
& FindInDegree(G,indegree);
& InitStack(S);
& for(i=0;i&G.++i)
&&&& if(!indegree[i]) Push(S,i);
& count=0;
& while(!StackEmpty(S))
&& { Pop(S,i);printf(I,G.vertices[i].data); ++
&&&& for(p=G.vertices[i].p;p=p-&nextarc)
&&&&&&& {k=p&
&&&&&&&& if(!(--indegree[k])) Push(S,k);
&& if(count&G.vexnum) return ERROR;
&& else return OK;
4、拓扑排序算法的分析
二、关键路径
用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网 。AOE网常用于估算工程完成时间。
、AOE网研究的问题
（1）&&&& 完成整个工程至少需要多少时间；
）&&&& 哪些活动是影响工程的关键。
1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。
、关键路径的几个术
2&&&& e(i)
3&&&& l(i)& e(i)=l(i)
4&&&& ve(i)
5&&&& vl(i)
ai&j,k&(jk)dut(&j,k&),
&&&&&&&& e(i)=ve(j)
&&&&&&&& l(i)=vl(k)-dut(&j,k&)&&&&&&&&&&&&&&&&&&&&&&& (6_6_1)
ve(i)vl(j)
ve(j)=Max{ ve(i)+dut(&i,j&) }&&&&&&&&&&&&&&&&&& (6_6_2)
&&&&& &i,j&T,& 2&=j&=n
vl(n)=ve(n)
vl(i)=Min{ vl(j)-dut(&i,j&) }&&&&&&&&&&&&&&&&&&&& (6_6_3)
&&&&& &i,j&S,& 1&=i&=n-1
、求关键路径的算法
(1)&&&&&&&& 输入e条弧&j,k&，建立AOE网的存储结构。
&&&&&&&& 从源点v1出发，令ve(1)=0,求 ve(j)&&& 2&=j&=n。
&&&&&&&& 从汇点vn出发，令vl(n)=ve(n),求 vl(i)&&& 1&=i&=n-1。
&&&&&&&& 根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。
求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。
Status ToplogicalSort(ALGraph G,stack &T){
& FindInDegree(G,indegree);
& InitStack(S);count=0; ve[0..G.vexnum-1]=0;
& while(!StackEmpty(S))
&& { Pop(S,j);Push(T,j); ++
&&&& for(p=G.vertices[j].p;p=p-&nextarc)
&&&&&&& {k=p&
&&&&&&&& if(--indegree[k]==0) Push(S,k);
&&&&&&&& if(ve[j]+*(p-&info)&ve[k]) ve[k]=ve[j]+*(p-&info);
&& if(count&G.vexnum) return ERROR;
&& else return OK;
status CriticalPath(ALGraph G){
if(!ToplogicalOrder(G,T)) return ERROR;
vl[0..G.vexnum-1]=ve[0..G.vexnum-1];
while(!StackEmpty(T))
for(Pop(T,j),p=G.vertices[j].p;p=p-&nextarc)
&&& {k=p& dut=*(p-&info);
&&&& if(vl[k]-dut&vl[j])& vl[j]=vl[k]-
& for(j=0;j&G.++j)
&&& for(p=G.vertices[j].p;p=p-&nextarc)
&&&&& {k=p& dut=*(p-&info);
&&&&&& ee=ve[j];& el=vl[k];
&&&&&& tag=(ee==el)?’*’:’’;
printf(j,kdut,ee,el,tag);
&&&&&&&&&&&
5求关键路径的算法分析
、Dijkstra
、Dijkstra
1&&&&&&&&&&& sv1,tdistv1v1dist
2&&&& 选dist中最小的权值js
&&&&&&&&& s=s{j}
3&&&& v1t(t=V-s),
&&&&&&&&&& dist[j]+arcs[j][k]&dist[k]
&&&&&&&&&& dist[k]=dist[j]+arcs[j][k]
(4) 23n-1v1
nDijkstraO(n3)floydO(n3)
1、弗洛伊德（floyd）算法的基本思想
vivjvivjn-1v1(vi,v1),(v1,vj)(vi,vj)vivj1v2vivj2vnvivjn
2、弗洛伊德（floyd）算法
void& ShortestPath_FLOYD(MGraph G,PathMatrix &P[],DistanceMatrix &D)
{for (v=0;v&G,++v)
for (w=0;w&G,++w)
&&& {D[v][w]=G.arcs[v][w];
for (u=0;u&G,++u) P[v][w][u]=FALSE;
if(D[v][w]&INFINITY){p[v][w][v]=TRUE;P[v][w][w]=TRUE;}
& for (u=0;u&G.u++)&&&&& /* 将顶点u从0到n-1逐个加入测试 */
&& for (v=0;v&G.v++)&&&&& &&&&&&&&/* 求v到w间的最短路径 */
for (w=0;w&G.w++)
& if (D[v][u]+D[u][w]&D[v][w]) /*从v经u到w的一条路径更短 */
&&& { D[v][w]=D[v][u]+D[u][w];
for (i=0;i&G,++i)
&& P[v][w][i]=P[v][u][i]||P[u][w][i];
p7.1& p7.2& p7.3&&& p7.5&&& p7.7&& p7.10
在排序中结点（数据元素）称为“记录”，记录的集合称为“文件”，内存中的文件也常称为“线性表”。
设n个记录的序列为
{K1K2Kn}&&&&&&&&&&&&&&&&&&&
Kp1&=Kp2&=&=Kpn&&&&&&&&&&&&&&&&&& 82
{Rp1 Rp2Rpn}
内部排序和外部排序。内部排序指待排序文件不大，一次可以在内存中完成的排序，外部排序指待排序文件较大，文件存放在外存上，不能一次调入内存的排序。
若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生变化，这种排序称为“稳定”排序，否则是“不稳定”排序。稳定排序与不稳定排序表示所用的排序方法，并不说明哪种方法好与差。
#define& n&
typedef struct
rectype& r[n+1];&& /* r */
&&&&&& [7]&& 2&& 5&& 1&& 9& &6&& 8&& 3
&&&& i=2:& (2)& [2&& 7]&& 5&& 1&& 9&& 6&& 8&& 3
&&&& i=3:& (5)& [2&& 5&& 7]&& 1&& 9&& 6&& 8&& 3
&&&& i=4:& (1)& [1&& 2&& 5&& 7]&& 9&& 6&& 8&& 3
&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&&&&&&&&
&&&& i=4:& (3)& [1&& 2&& 3&& 4&& 5&& 6&& 7&& 8&& 9]
void& straitsort(r,n)
int& n,r[];&
{ int i,j;
& for(i=2,i&=n;i++)&&&&&& /*
{ r[0]=r[i]; j=i-1;&&&& /*
& while (r[0].key&r[j].key)
&&& { r[j+1]=r[j]; j--;&& /*
& r[j+1]=r[0];&&&&&&&& /* */
1 =n-1 =2(n-1)
2i2&=i&=ni-1 =(n+2)*(n-1)/2= =(n+4)*(n-1)/2
（1）Shell
（2）Knuth
72285117966287334524
shellsort(r,n)
/*rnShell */
rectype& r[n+1]
{ int& k, i,
& rectype& x;
& k=n/2;&&&&&&&&&&&&&&&&&& /*
& while& (k&=1)&&&&&&&&&&& /* 1 */
{ for& (i=k+1;i&=n;i++)& /* k */
&& { x=r[i]; j=i-k;
&&&& while& (j&0& &&& x.key&r[j].key)
&&&&&& { r[j+k]=r[j]; j=j-k;
&&&& r[j+k]=x;&&&&&&&&&&& /* i */
5、Shell 排序的算法复杂度
KnuthShelln1.3
R1R2RnK1K2K n
（1）K1K2 K1&K2,K2K3Kn-1Knnn-1
&& 72519683
2517683[9]
215673[89]
12563[789]
1253[6789]
123[56789]
123[56789]
void& bubblesort(r,n)
rectype& r[n+1]
{ register& i=1, j, k,flag=1;
&while (flag& &&& i&n )
{ flag=0;&&&&&&&&&&&&&&&&&&&&&&& /*
for& (j=1;j&=n-i;j++)&
&& { if& (r[j+1].key&r[j].key)
&&& {& r[j]&—&r[j+1]; flag=1&&&&& /*&
i++;&&&&&&&&&&&&&&& /*
，交换次数为0；逆序时，比较次数和交换次数均为：
&& [7&& 2&& 5&& 1&& 9&& 6&& 8&& 3]
1&&&& [3&& 2&& 5&& 1&& 6]& 7& [8&& 9]
&& [1&& 2] &3&& [5& 6]
&&&&&&&& &&&&& [8&& 9]
&&&&&&&&&&&&&&&&&&&&&&&&
&&&&&&&&&&&& 1&& 2&& 3&& 5&& 6&& 7&& 8&& 9
int Patition(r,l,h)
{ int i=l; j=h;
& rp=r[i]; x=r[i].& /* , */
& while (i&j)
&& { while (i&j && r[j].key&=x.key )& j--;
if (i&j)& r[i++]=r[j];
while (i&j && r[i].key&=x.key )& i--;
if (i&j)& r[j--]=r[i]
& r[i]=rp&&& /* i
&return(i);
quicksort(r,s,t)
rectype& r[]
& { k=patotion(r,s,t)
&&& quicksort(r,s,k-1)
quicksort(r,k+1,t)
nlog2n,nlog2n/6nlog2n = n-1n2/2log2n
8．4& 选择排序
nn-1n-2n-1
& 72519683
71[1]2579683
2&&& [12]579683
53[123]79685
75[1235]9687
96[12356]987
71[123567]89
8[12356789]
selectsort(r,n)
rectype& r[n+1]
{ register& i, j,
& rectype& x;
{ for& (i=1;i&=n-1;i++)&
&& {k=i;&&&&&&&&&&&&&&&& /* i */
&&&& for& (j=i+1;j&=n;j++)&& /*
&&&&& if& (r[j].key&r[k].key)& k=j;
&&& if& (k!=i)& r[k]&&r[i]; /* i */
直接选择排序的比较次数和记录的初始顺序无关。其比较次数为：
(n-1)n-13(n-1)
二、 堆排序
1、堆的定义
堆是一个含有n{k1,k2,…,kn}
&&&&&&& ki&=k2i
&&&&& ki&=k2i+1&&&&&&&&&&&&& &&(1&=i&=n/2)&&& (1)
&&&&&&& ki&=k2i
&&&&& ki&=k2i+1&&&&&&&&&&& (1&=i&=n/2)&& (2)
&&&&&&& ki&=k2i
2、堆排序的基本问题
3、如何调堆
Sift(R，i，m)
/* 假设R[i+1..m]中各元素满足堆的定义，本算法调整R[i]使序列R[i..ml中各元素满足堆的性质*/
RecTypeR[];&&&&&& 。
&{ int j=2*i;
&& RecType temp=R[i];&&&&&&&&&&&&&&&&& /* 暂存“根”记录R[i] */
&& while(j&=m)&&&&&&&&&&&&&&&&&&&&&&&& /* j&=m时，R[2i]是R[i]的左孩子 */
&&&& { if((j&m) && (R[j].key&R[j+l].key))j++; /* j指向R[i]的右孩子 */
&&&&&& if(temp.key&R[j].key)&&&&&&&&&&& /* 孩子结点关键字最大 */
& { R[i]=R[j];&&&&&&&&&&&&&&&&&&& /* 将R[j]换到双亲位置上 */
&&&&&&&&&&& i=j; j=2*i;&&&&&&&&&&&&&&&&&& /* 修改当前被调整结点 */
/* 调整完毕，退出循环*/
R[i]=&&&&&&& /* 最初被调整结点放入正确位置 */
4、如何建堆
5、堆排序算法
Heapsort(R)
/* R[1]R[n] */
RecType R[];
& RecType&
& for (i=n/2;i&=1;i--) Sift(R,i,n);&& /*
& for (i=n;i&1;i--)
{ R[1]& -- &R[i]&& /*
Sift(R,1,i-1);&& /*
6、堆排序算法分析
8．5归并排序
1、归并排序的基本思想
& &设待排序文件有n个记录，开始首先假定这n个记录都是有序的（这是自然的，一个记录当然自己有序）。然后进行归并，将相邻的有序子文件合并成一个较大子文件，如此下去，直至整个文件有序。对于二路归并来说，第一次长1的有序子文件两两归并得到长为2的é ù个有序子文件，再两两归并得到长为4的é ù个有序子文件，如此下去，直至得到长为n的有序文件。
2、二路归并排序的算法
（1）两个有序子文件归并成一个有序子文件
&merge(r,r1,low,mid,high)
&/*r[low]到r[mid]与r[mid+1]到r[high]是两个有序子文件* /
/* 本算法将其归并成一个有序子文件从r1[low]到r1[high]*/
rectype r[],r1[];
int low,mid,
{ int i= j=mid+1; k=
& while& ((i&=mid) && (j&=high))
&&& if (r[i].key&=r[j].key r1[k++]=r[i++]; /*取小者复制*/
&&& else r1[k+=]=r[j++];
while& (i&=mid)& r1[k++]=r[i++];/*复制第一个文件剩余记录*/
while (j&=high)& r1[k++]=r[j++];/*复制第二个文件剩余记录*/
（2）一趟归并的算法
mergepass(r,r1,length)
/*对r进行一趟归并，结果放在r1中 */
rectype r[],r1[];
&&&&&&&&& /* length是本趟归并的有序子文件的长度*/
{int i=0,j;&&&&&&&&& /*指向第一对子文件起始点 */
&while (i+2*length&=n)
& {merge(r,r1,i,i+length-1,i+2*length-1)
&& i=i+2*length&&& /*指向下一对子文件起始点 */
&if (i+leng-1&n-1)& /* 剩下两个子文件，其中一个长度小于length*/
&&& merge(r,r1,i,i+length-1,n-1);
&else&&&&& /* 子文件个数为奇数，将最后一个子文件复制到r1中*/
&&& for (j=i;j&n;j++) r1[j]=r[j];
（3）二路归并排序的算法
mergesort( r )
rectype r[];
{ int length=1;
& while (length&n)
&& { mergepass(r,r1,length)&& /* 一趟归并，结果在r1中 */;
mergepass(r1,r,length)&& /* 再次归并，结果在r中 */;
3、二路归并排序的时间复杂度
&& 第i趟排序后，有序子文件长度为2i，具有n个记录的文件排序，必须做「log2nù趟归并，每趟所花时间为O（n），故二路归并排序的时间复杂度为O（nlog2n），所需空间为O（n）。
8．6分配排序
一、分配排序概述
1、分配排序的实例
（1）扑克牌的排序
扑克牌有花色和面值（点数）。规定花色高于面值。在花色中规定梅花&方块&红心&黑桃；在面值中2&3&4&…&10&J&Q&K&A。其排序有两种方法：
方法1：先按花色分成4堆，每堆内按面值从小到大排序，最后按花色顺序收集起来。这种方法叫最高位（MSD）优先法。
方法2：先按面值分成13堆，将13堆从小到大排序，再按花色分成4堆，最后按花色顺序收集起来。这种方法叫最低位（LSD）优先法。
（2）卡片的排序
卡片按日期（年月日）建立，然后以建立日期为关键字进行排序。
方法1：先按年份分堆，同年的卡片按月份分堆，同月的卡片按日分堆，最后顺序收集这些卡片。这种方法叫最高位（MSD）优先法。
方法2：先按日分堆并收集，再按月份分堆并收集，最后按年分堆并收集。这种方法叫最低位（LSD）优先法。
2、分配排序的方法
最高位（MSD）优先法是按最高位分成若干子集，子集再分成子集，在各子集中排序，最后收集；最低位（LSD）优先法是从最低位开始到最高位结束，进行若干次分配和收集。
&&& 当关键字为一个字段时，亦可使用分配排序方法。如000---999。
二、基数排序
&&& 将最低位优先法用于单关键字的情况。
1、基数排序的基本思想
n个记录的关键字进行排序，每个关键字看成是一个d元组：
ki=(ki1, ki2,..., kid)
c0&=kij &=cr-1& &( 1&=i&=n,& 1&=j&=d )
排序时先按kid 的值，从小到大将记录分到r（称为基数）个盒子中，再依次收集；然后按kid-1的值再这样作。直至按ki1分配和收集序列为止，排序结束。
在关键字为数字时，r=10,& 0&=ci&=9， 1&=i&=d；
在关键字为字母时& r=26,& ’A’&=ci&=’Z’,& 1&=i&=d。
2、基数排序的实例模拟
&& 设待排序文件各记录的关键字为288，371，260，531，287，235，56，299，18，23。这时 r=10, d=3。进行3趟分配和3趟收集。
基数排序可以采用顺序存储方式。使用R数组存放待排序记录，用r个数组存放分配时的r个队列。分配一次和收集一次都需要n次移动，d遍分配和收集，共需2dn移动。每个队列最大为n，共需rn个结点。
若采用链式存储方式，在R数组中，每个记录设一个next字段，存放下一结点的下标（静态链表）。记录的移动次数降为0，辅助空间为O(n+r)，分配时间O(n)，收集时间O(n)，时间复杂度O(d(n+r))。
3、基数排序的算法
& 首先定义新的数据类型：
& chtype=c1..
& struct node{
&& chtype& key[1..d];
&& }R[n+1]
(1)[初始化]
for (i=0;i&n;i++)& R[i].next=i+1;
R[n].next=0;
(2)[准备] p=1;& /* 指向静态链表中第一个元素 */
while (i=d;i&0;i--)
{ ① [给Q初始化]
循环 j=c0,c1,…,cn-1,执行
& Q[j].f=0; Q[j].e=0& /* 队头、队尾指针为0 */
② [分配] 循环反复执行下列语句，直至p=0
(a)k=R[p].key[i]& /* 取关键字的第i个字符 */
& (b) IF Q[k].f=0 THEN Q[k].f=p ELSE R[Q[k].e].next=p
& (c) Q[k].e=p&&&&&& /* 修改队头队尾指针 */
& (d) p=Q[p].&& /* 取关键字的下一个字符 */
(b)循环 当Q[j].f=0时，反复执行
(c)p=Q[j].f;& t=Q[j].e&
(d)循环 k=succ(j),…,cr-1,执行
若Q[k].f&&0,则R[t].next=Q[k].f; t=Q[k].e
&&&&&&&& (e) R[t].next=0&&&&&& /* 静态链表尾 */
(4)[算法结束]
8·7& 各种排序方法的比较
一、 外存信息的存取
二、外部排序的方法
1、外部排序的两个阶段
生成顺串（有序归并段）
2、外部排序效率分析
s=「logkm」
s—归并趟数
k—归并路数
m—归并段个数&&&&
三、 多路平衡归并的实现
四、 置换-选择排序
五、最佳归并树
p8.1&& p8.2&& p8.5&&&& p8.11
9·1& 基本概念
1、查找的定义
查找其关键字等于给定值的操作。
2、关键字的概念
3、查找的结果
4、查找算法效率的度量
（2）所需的辅助存储空间
本章假定关键字为整数，其类型定义如下：
#define n&
typedef struct
table& R[n+1];
9·2& 线性表的查找
一、 顺序查找
1、顺序查找的定义
2、顺序查找的算法
int seqsearch(R,k)
table R[];
{& int i=0;
R[n].key=k;&&&&&&&&&&&& / *R[n] */
while (R[i].key !=k)& i++;
if (i==n) return(-1);&&&&&& /*
else return(i);
3、顺序查找算法的时间复杂度
p,q=(1-p),
E(n)=p. +q.(n+1)= p. +(1-p).(n+1)=(n+1).(1- );
二、二分查找
1、二分法查找的基本概念
2、二分法查找的算法
int binsearch(R,k)
table R[];
{& int l=0; h=n-1;
while (l&=h)
& { i=(l+h)/2&&&&&&&&&&&&&&&&&&&& /*
if (R[i].key=k)& return(i);&&&&&& /*
else if (R[i].key&k)& h=i-1);&&&& /*
else l=i+1;&&&&&&&&&&&&&&&&&& /*
3、二分法查找的时间复杂度
二分法查找的过程可用二叉树来描述，中间结点是二叉树的根，左子表相当于左子树，右子表相当于右子树，由此得到的二叉树便为描述二分法查找的判定树。二分法查找的过程是走了一条从根结点到叶子结点的过程，不论查找成功与失败，查找长度均不超过树的高度，其平均性能为h= log2(n+1)
4、二分法查找的优缺点
优点：查找速度快； 但表必须有序。
缺点：频繁插入和删除不方便。
三、分块查找
分块查找综合了顺序查找和二分法查找的优点，既有动态结构，又适于快速查找。
1、分块查找的基本思想
2、分块查找的平均长度
设待查找文件有nbs
E(n)=Eb+Ew= + =(s2+2s+n)/(2s)
&&&&&& E(n)=Eb+Ew=log2(b+1) +
3、几种查找方法的比较
9·3& 动态查找表
&&& 适应元素结点的动态插入与删除。
二叉排序树
1、什么叫二叉排序树
（1）二叉排序树的定义
（2）二叉排序树的建立实例
k=(k1,k2,,km) (m&0)
k1&k2k2k1k1
k=(45,12,53,3,37,100,24,61,90,78)
（3）中序（对称序）遍历二叉排序树所的结点序列是有序序列
（4）二叉排序树中结点的插入
BSTNode *lnsertBST(t,s)
/*将新结点*s插入到t所指的二叉排序树中*/
/*返回插入*s后二叉排序树的根指针*/
BSTNode *s,*t;
{ BSTNode *f,*p=t;
& while(p!=NULL)
&& { f=p;&&&&&&&&&&&&&&&&&&&&&&&& /*查找过程中，f指向*P的双亲*/
&&&& if(s-&key==p-&key)return(t);& /*树中己有结点*s，无须插入*/
&&&& if(s-&key&p-&key) p=p-&/*在左子树中查找插入位置*/
elsep=p-&&&&&&&&&&&&&& /*在右子树中查找插入位置*/
if(t==NULL) return(s);&&&&&&&&&&&& /*原树为空，返回S作为根指针*/
if(s-&key&f-&key)& f-&lchild=s;&&& /*将*s插入为*f的左孩子*/
else f-&rchild=s;&&&&&&&&&&&&&&& /*将*s插入为*f的左孩子*/
（5）二叉排序树中结点的删除
BSTNode *CreatBST()
{BSTNode *s,*t==NULL;&&&&&&&&& /*置二叉排序树的初态为空树*/
& KeyType key,endflag=0;
& scanf(“%d”,&key);&&&&&&&&&&&&& /*读入一个结点的关键字*/
& while(key !=endflag)&&&&&&&&&& /*输入未到结束标志时，循环*/
&&& { s=malloc(sizeof(BSTNode)) ;/* 申请新结点*/
&&&&& s-&lchild=s-&rchild=
scanf(“%d”,&data);&&&&&&&& /*读入结点的其他数据项*/
t=lnserBST(t,s);&&&&&&&&&& /*将新结点*s插入到树t中*/
scanf("%d",&key);&&&&&&&&& /*读入下一个结点的关键字*/
& return(t);
2、最佳二叉排序树
（1）最佳二叉排序树的定义
（2）扩充的二叉排序树
&&&&&&& N=n+1
&&&&&&& E=I+2n
&&&&& En= In+2n&&&&&&&&&&&&&& 1
In=In+1-K&&&&&&&&&&&&&&&& (2)
& En=En+1-2(K+1)+K&&&&&&&&& (3)
&&& En+1= En+2(K+1)-K
&&&&&& =(In+2n)+K+2
&&&&&& =((In+1-K)+2n)+K+2
&&&&&& =In+1+2(n+1)
（3）二叉排序树的检索效率
En&=1+4logn
（4）如何构造最佳二叉排序树
3、平衡二叉树(AVL树)
（1）key1&&key2f(key1)=f(key2)1939 davenport
h(key)=key& mod& p
key=(215874)10,1321587413=783579102,3,4,5h(57
H(key)=random(key)
1 283,255,377,407,384,801,803,203,659,491,775,519,611,990—18h(key)=key mod 19
Hi=(H(key)+di) mod m&&&&& (i=1,2,…,m-1)
di=1,2,…,m-1, d+1,d+2,…,m-1,0,…,d-1
di=12,- 12,22,- 22,32,…,+(-)k2,(k&=m/2),
h1(key)=key mod m
h2(key)=key mod (m-2)+1
h2(key)=[key/m] mod (m-2)+1
(d+h2(key)) mod m, (d+2h2(key)) mod m, (d+3h2(key)) mod m
p9.1&& p9.4&&&& p9.8&&& p9.9&&&&& p9.12
10.1&& 基本概念
102&& 顺序文件
10.3&& 索引文件
10.4&& 索引顺序文件
10.4.1&& ISAM文件
10.4.2&& VSAM文件
10.6&& 多关键字文件
10.6.1& 多重表文件
10.6.2&& 倒排文件
p10.1&& p10.3&&&& p10.4
安徽新华学院
版权所有　
联系电话：(校办) 5872019(人事) 5872888(招生) 传真：5872323
地址：安徽省合肥市望江西路555号