计算机软件技术基础

学时安授课34+上机章章1278268图234944串45262 数硬第一 C1.11.1数值计数学模型数学模型→选择计算机语言→编出程序→测试→终解答。数值计算的关键是：如何得出数学模型（方程）？程序设计 比较关注程序设计的技巧。非数值计加以描间的相互关系一般无法用数 1女2男1.21.2研究数据元间的客观联系

逻辑结研究具有某种逻辑关系的数据在计算器内的方式 结算由数据元素的有限集合及所有数据元间的关系Data_Structure={D,所有数据元间的关系的有限集合树形结构图状结构树形结构图状结构集合结构集合结构线性结构线性结构SETK={01,02,03,04,05,06,07,08,09,10}R={}数据结K={01,02,03,04,05,06,07,08,09,10R={<05,01>,<01,03>,<03,08>,<08,02>,<07,04>,<04,06>,<06,09>,<09,10>数据元间的联系数据结TREE=（K,R）K={01,02,03,04,05,06,07,08,09,10R={<03,08>,<03,09>,<04,10>

数据之间的联系Graph=(D,RD={1,2,3,4,5,6,7,8,9R={数据之间的联系 结构（StorageStructure):数据在计算机中的表示(或称映象）称为数据的结构，又称为物理结四种基本 方法 结构索 方散 方同一种逻辑结构可采用不同的方法（以上四种结构:间的逻辑关系链链结构：在每一个数据元素中增存放地址的指针，用此指针来表示数据的逻辑关系间线性结数据的逻辑结

队串及数树形结数据 结

非线性结散

图形结数据的运算查找、排序 、删除、修改1.31.3算法算法是用来解决某个特定问题的指令的集合2程序设计语言形式（如C语言等输入性有0输出性有一个或多个输出(处理结果)确定性有穷性算法应在执行有穷步后结束；整个指令序可行性（有效性）算法中的每一个步骤都应当能55时间复杂度空间复杂度

一个程序在计算机中运行时间的多少与诸多因问题的规模程序中语句的执行次数T(n)/f(n)为一不等于零的实常数，则f(n)为T(n)的称O(f(n))例 /*3n+24nforn2*/ /*10n2+4n+211n2forn5*/ /*6*2n+n27*2nforn4常用的计算规则加T(n)=T1(n)+T2(n)=O(f1(n))+=O(max(f1(n),乘T(n)=T1(n)×T2(n)=O(f1(n))=复杂复杂度复杂度注空间复杂度S(n)按数量级递增顺序也与上表类例2例例例n1/2-例x=91;if(x>100){x=x-10;y--else例inti,j,k,x=0;for(i=1;i<=n;i++)for(j=1;j<=i;j++)for(k=1;k<=j;k++)2100,(3/2)n,(2/3)n,nn,n0.5,n!,2n,lgnnlgn、(3/2)n、2nn(2/3)n<2100<lgn<n0.5<n3/2<nlgn<(3/2)n<2n<n!<1、数据结构是指计算机处理的①的组织形式以及它们相互之间的②。①.数据元B.计算方C.逻辑D.数据映②A.结.关C.运D.算 结构关系、组织形C.数据元素、数据对D.数据复杂性、程序复杂空间复杂3、衡量算法好坏的两个主要空间复杂的时间复杂度 4、下面程序段的时间复杂度是O(n) {}5、算法的时间复杂度仅与问题的规关。*

（）6、下面程序段A[i][j]=0执行次n(n+1)/2,

作业：P251-1，1-2，1－3，复习 C语言的数据类 short;long; float;double;long

int33i

33

指针变量的定intint*i_pointer; *5x5{int

{int

6x6}

voidFunction1(int{}

voidFunction1(int{(*px)++;}数组类int &a[0], a[0], ‘‘\0’为字chara[40]=“Iamastrlen(a为5.定义结构体类型变量定义结构体类型

struct{charname[10];intage;float定义结构体类型变量structstudentstudent1;structstudentstructstudent6.typedefcharelemtype;typedefstructstudent{charname[10];intage;float}stu;elemtypea;stustudent1;数据数据元 数据数据元学 籍 出生年 住 06048002杨 例例民其刘晓男汉…男回…男壮………………女汉…逻辑逻辑结结 …… 链式结… ∧…100元钱买100只鸡，母鸡每只5求解：设母鸡、公鸡、小鸡各为i,j,k只，则有只需要解出本方程就可以得到答案方法1：用三重for(i=0;i<=100;i++)for(j=0;j<=100;j++)for(k=0; if(k%3==0&&(i+j+k)==100&&(5*i+3*j+k/3)==100)printf(“%d,%d,%d\n”,i,j,k);}方法2、3：用两重循因总共买100只鸡，所以小鸡的数目可以由母鸡数和公鸡数得到。for(i=0;i<100;i++)for(j=0;j<100;j++){forfor{k=100-i-jif(k%3==0&&(5*i+3*j+k/3)==100)}方法4：用一重循和 合并为个和 合并为个 ,,j,}Chapter Linear要点回数据结构课程——涉及数学、计算机硬件和计算数据结构定义——指互相有关联的数据元素的集合用D_S=DRS=(D表示数据结构内容——数据的逻辑结构、结构和算算法效率指标——时间效率和空间效数据的结

逻辑结构唯逻辑结构唯结结构数据的运 、删除、修改、查找、排序运算的运算的实现线性表的顺序结线性表的链式结构（单链表线性结构的若结构是非空有限集，则有且仅有一个开始结可表示为：（a0, , an-线性结构的结点和一个尾结点其他结点只有一个直接前驱和一线性结构包括线性表、堆栈、队列、字符串、数组等等，其中，最典型最常用的是------线性表的定义：用数据元素的有限序列表（a0,a1…ai- ai＋1，…,an-线性起（首结点

数据元ai的直接前趋ai的直接后n=0时称为空

线性终（尾点n为元素总数，即表例 分析26个英文字母组成的英文（A,B,C,D, ,数据元素都是字母 元间的关系是线性例 分析学生情况登记学班女微电何仕男微电王女微电男微电：：：：：每个数据元素由5个数据项组成;元间的关系是线性Initia 初始化操作。建立一个空线性表L Insert(L,i,x)前插 ai之 线性表的顺序结构—顺序一、顺序用一组地址连续的单元线性表的各个数据元素，称作线性表的顺序结构，简称 若已知表中首元素在器中的位置，则其他元素存放位置亦可求出（利用数组下标，参见 结构示意图）。线性表的顺序结构示意逻辑地 数据元 地址数据元……1每个元 占K字i…

……… 每个数组元素用相邻的５个字节。器按字节编址，设数组元素Ｍ[０]的第节的地址是113解：地址计算通式为 =LOC(a0)+L因此：LOC(M[3]985#defineMaxlen100typedefstruct{charname[10];charsex;int

/*顺序表最大长度MF}

elemtype

intnum=-

/*当前数据元素下标typedef{typedef{elemtypeList[Maxlen];intnum;}……s-s- s-SeqLista;SeqListSeqLista;SeqList二、顺序表的基本操初始化ListInitiavoidListInitiate(SeqList{L->num=- intintListLength(SeqList{return}intListGet(SeqListL,inti,elemtype{{printf(“ERROR!\n”);return0;} return1;}（在第i个（0<=i<=n）数据元前……an-1…Maxlen-

……an-…n…Maxlen-

…x…an-…n…Maxlen-

是否满足是否满足表长加表长加用c语言描述算intListInsert(SeqList*L,inti,elemtype{intif(i<0||i>L->num+1 printf(“error\n”);return0; if(L->num)>=Maxlen-1) for(j=L->num;j>=i;j--L->list[j+1]＝L-

判断iL-L->num＝L-return}

Eis

nn一个元素所需平均移动次数1一个元素所需平均移动次数1ni0 Eis

n

(ni0

i)

n

ni0

n

i0n

n

n(n1) 因此因此,该算法的时间复杂度为O(n)……an-1 …Maxlen-

……an-…Maxlen-YNYi？NYNYi？N表长减a[j-1]=a[j];用c语言描述删除算intListDelete(SeqList*L,inti,elemtype{intif(L- printf(“\nThelistisreturn

元素,并将其保存在x中elseifi<0||i>L- printf(“\nthepositionisinvalid”);return0; {*x=L-

for(j=i+1;j<=L->num;j++)L->list[j-1]=L-return1;}}

Edl

Edl：删除Edl：删除一个元素所需平均移动次1i0

(ni)

1(ni1ni0（ n（

n1 i0

i0(n

1)

1n(n1)n因此,该算法的时因此,该算法的时间复杂度为O(n)顺序表时间效率分析 T(n)=O(移动元素次数顺序表空间效率分析顺序表的空间复杂度三、顺序结构的特可以方便地随机存取

作业：P552-82-14第二章性逻辑结构

结构：顺序、链缺点 线性表的链式结构—链

单链表的基本概 线性表链式结构的一种。用一组不一定连续的单元来存放数据元数据数据

a1^a1^指针单链表 结typedefstructNode DataTypedata;structNode*next;}SLNode；

单链结点的定义……第2……第2第3第1第1第3……逻辑示意第2第2第1链表结构示意头结头结

首元结

^^^结点的单链表^ 结点的空单链表^^

不结点的单链 head==NULL 不结点的空单链何谓头指针、头结点和首元结点头指 头结点首元结 例：一个线性表的逻辑结构为，其结构用单链表表示如下，请问其地数据指针171地数据指针171777∴头指针的值是 ②H区别：无头结有头结动态内存分设计根据具体问题的具体需要，在程序运行时

##includeMemoryMemory函数原型：void*mallocunsigned用于向系统动态申请size个字节的内存单元空sizeof运算符 功能：

voidfreevoid*函数功能：用于动态分配的内存空间强制类型转typedefstructtypedefstructnodetype intdata;structnodetype}SLNode;SLNode*p;p=(SLNode*)malloc(sizeof(SLNode)p

…一级指一级指 二级二级指

单链表的操作实（1）

{SLNode*

头结

ListInitiate}intListInitiate(SLNode**head{if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}…求当…1p1p

intListLength(SLNode SLNode*p=head;intsize=0; size++;}return}

pp

^an-^an-while(p-{p=p-j++;

*x=p-intListGet(SLNode*head,inti,DataType SLNode*p;intj=0;{p＝p-

if

{printf(“取元素位置参数错！”);return0; return1;}

/*将数据元素值赋给运算（前插，即在ai之 一个数据素

an-an-ai-xx xx步骤:（1）

：1

2、ai-1结点的指针域指向x

…

…

p{

^an-ai-^an-ai-

x}

s=(SLNode*)malloc(sizeof(SLNode));s->next=p-p-用c语言实现的单链表算intListInsert(SLNode*head,inti,DataType{SLNode*p,intj;

{p=p->next;}

{printf(“\n return0;}if((s=(SLNode*

return0;return1;

单链表的删除（删除第i(i>=0)个结点

……sai-p{p=p->next;}

s=p-用c语言实现的单链表删除算ListDelete(SLNode*head,inti,DataTypeSLNodeSLNodeintwhile(p->next!=NULL&&p->next->next!=0&&j<i- if(j!=i- printf(“\n删除位置不合理!”}s=p-p->next=p->next-

将ai除return1;}

#include<stdio.h>#defineMAXLEN100typedefintdatatype;typedefstruct{datatypeList[MAXLEN];intnum;函数void{case1:调用初始化函数;break;case2:调用函数;break;case3:调用删除函数;break;case4:调用输出函数;break;case5:break;｝(6尾接p{if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;链表创建结束链表创建结束YNintCreatL1(SLNode**h,DataTypea[],int inti,j;if(i==0)return0;{if((s=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;p=s;}return (6hh{if((s=(SLNode*return}链表创建结束Y链表创建结束YNintCreatL2(SLNode**h,DataTypea[],int{SLNode*s;inti,j;if(i==0)return0;{if((s=(slnodetype*)malloc(sizeof(slnodetype)))==NULL)return0;(*h)->next=s;}return}2.3.52.3.5

空 >next==head 2.3.6双向循环链

typedefstruct{DataTypestructNode}要点线性表的链式——链问1：线性表的逻辑结构特点是什么？其顺序答性表逻辑结构特点是，只有一个首结点和尾结点；除首尾结点外其他结点只有一个直接前驱和一个直接后继。简言链式时，相邻数据元素可随意存放，但所占空间问2：顺序和链式各有哪些优缺点 链式的优点是或删除元素时很方便，使事实上，链表、删除运算的快捷是以空间问3：在什么情况下用顺序表比链答：顺序表适宜于做查找这样的静态操作；链表于 若线性表的长度变化较大，且其主要操作是、是查找 和删除主要发生应用实例#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum/*最后一个数据元素的下标voidDeleteSeqList(SeqList*la,DataTypex intj,kfor(j=0;j<=la->num;j++ if(la->List for(k=j;k<la-la->List[k]=la->List[k+1];}}}应用实例删除顺序表a中第i(i>=0)个元素起的k。#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum;/*最后一个数据元素的下标intDeleteK(SeqList*a,inti,int{intif(a-

{printf(“顺序表已空！\n”);return0; elseif(i<0||k<0||i+k-1>a->num)return0;{for(j=i;j<=a->num-k;j++)a->num=a->num-k;return1;}}

应用实例在有序顺序表中值为x的数据元素以保持顺序表的有序性。#defineMAX100typedefintDataType;typedefstruct{DataTypeintnum;/*最后一个数据元素的下标intOrderlnsert(SeqList*L,DataTypex{intiif(L->num==Max-{printf顺序表已满”);return0;}{for(i=L->num;i>=0 ;i--)L->List[i+1]=L->List[i];return1; }应用实例实现单链表的就地逆序。设其头结点的指针为，编写一个算法将单链表逆置a2a2q单链表的逆voidreverse(SLNode{SLNode*p,*q;p=head-head->next=NULL;while(p!=NULL){q=p=p-q->next=head->next;head->next=q;}}应用实例LaLa=(3,5,8,11Lb=(2,6,8,9,11,15,20合并结果Lc2,3,5,6,8,8,9,11,11,15,20顺序表结typedef{elemtypeList[maxlen];intnum;}intmergeql(qltypela,qltypelb,qltype{inti,j,k;{printf(“\n数组下界溢出return}{}while(i<=la.num)lc->list[k++]=la.list[i++];while(j<=lb.num)lc->list[k++]=lb.list[j++];return}单链表结typedefstruct{elemtypedata;structslnode*next;}Pa、Pb用于搜索La和Lb，Pc指向新链表当前结358^358^8282996^6…532 …532^intmergesl(slnodetype*la,slnodetype*lb,{slnodetype*pa,if(*lc=(slnodetype{printf(“\n分配内存失败！”);return0;}{if(pc->next=(slnodetype{printf(“\n分配内存失败！”);return0; if(pa->data<=pb-{pc->data=pa->data; {pc->data=pb->data;pb=pb->next;}{ifpc->next=(slnodetype{printf(“\n分配内存失败！”);return0; {ifpc->next=(slnodetype{printf(“\n分配内存失败！”); return0; pc->next=NULL;return思考1、不用1、不用，直接把a表插到b表中；或者把b表插到a表中，如何编程？2、要求不能有重复的数据元素，如何编程了解线性表的定义和线性结构的特点 会用单链表编写、删除等有关算法作业： 2-14(单链表）2- intListInitiate(SLNode**head{if((*head=(SLNode*)malloc(sizeof(SLNode)))==NULL)return0;(*head)->next=NULL;return1;}Chapter Stackand3.1堆栈 3.2队列定逻辑结结运算规实现方

定逻辑结结运算规实现方定堆栈是限定只能在表的一端进行和删除的入和删除的一端叫做顶(top)；表的另一端则叫做栈底(base)。

an-an-…an-

LastLast *堆栈与一般线性表的比较一般线性逻辑结构：逻辑结构：例一个栈的输入序列为123，若在入栈的过程中允答：可以通过穷举所有可能性来求解①1入12入2出，3入3出即②1入12、3入，3、2出即③1、2入，23入3出，1即④1、2入，2、1出，3入3出即⑤1、2、3入，3、2、1出即合计有5种可能性*二、堆栈的操1、初始2、进3、退4、取5、判栈是否非三、栈的顺序表示——顺序堆

maxlen-43210顺序栈的定typedefint#definemaxlen100/*顺序堆栈数组最大单元个数typedefstruct/*顺序栈定义{DataTypestack[maxlen];/*顺序堆栈存放数据元素的数组*/inttop; } 2初始voidinistack(seqstack{s->top=- /*顺序堆栈数组的当前栈顶位置参数：S功能：判断S是否为空，为空返回1，否则返回intempty(seqstack{return1;return}入intpush(seqstack*s,DataType{if(s->top==maxlen-{printf(“\nStackisfull”);return入栈入栈return}

出功能：弹出顺序堆栈s的栈顶数据元素值到参数d，intpop(seqstack*s,DataType{if(s->top==-栈{printf("\nStackisempty!");return0; 栈{*d=s->stack[s->top--return tk[ t tk[ t] 栈顶下标减取栈顶元intgettop(seqstacks,DataType{{printf(“\nStackisempty!”);return0;}{return1;}}顺序栈的C语言描述：typedefint#definemaxlen10typedefstruct{elemtypestack[maxlen];inttop;两个堆栈共享空间目的：节省空 ……… 两个堆栈共享空间的运算：初始出数据结构定义 typedef{intLeftTop;intvoid{s-}intPushDqstack(dqstack*s,charWhichStack,DataTypereturn0;}if(WhichStack!=‘L’&&WhichStackreturn0;}if(WhichStack==‘L’)s->stack[++s->LeftTop]=x;return进栈进栈算共用堆栈的算法练习共用堆栈的算法练习四、栈的链式结^

typedefintDataType;typedefstructsnode{DataTypedata;structsnode*next;} {LSNodeif((p=(LSNode*)if((p=(LSNode*){printf(“\n失败”)returnp-

xhead- xreturn1;∧∧ intPopStack(LSNode*head,DataType链栈的出栈算链栈的出栈算ifif{printf(“underflow\n”);return*d=p- ∧∧return1;}p1：括号匹配问题（参考P66例3-2：数制转换（十转 （Hanoi）4：表达式求N=(Ndivd)×d+Nmod例如：（1348)10=(2504)8 Ndiv8 Nmod8 将余数依次进栈，再出（Hanoi）zyxzyxnn可以使用任一柱子 3321 表达式计后缀表达式：例例：A+B→中缀表达式：AB–CD)栈顶栈顶运算符＋—×／()#＋>><<<>>—>><<<>>×>>>><>>／>>>><>>(<<<<<=)>>>>>>#<<<<<=步中缀表达输1#2#A3#A4#A5#6#7#8#9#步中缀表达输##ABCD/#ABCD/#＋ABCD/##＋ABCD/##ABCD/－E##ABCD/－E×T1←T2←B–T3←T2×T4←A+ABCD/

ABCD/

DCDCBAABCD/EEAT3=T2

BAT2=BBAABCD/AT4=A 作业：p873-6,3-一、队列的基本概定 队列又称先进先出 Out,FIFO)表1、初始化队2、判定队列是否为34、入队列（将新元素队尾5、出队列（队列头元素出队三、队列的顺序结#definemaxlen100typedefintDataType;typedefstruct{DataType, ,}队队列的进队和出队543

FED入队rear指示位置加入，rear=rear+1FED出队front的元素取出，front=front+1。问：如何解决答：在顺序队列中，当

FEDCFEDC 1 10如何实现用求模运算0120123N-0123..队头指针进队头指针进1:frontfront1)队尾指针进1:rearrear1)队列初始化：front=0&&rear队空和队满的判断665 4312

队列队满:front＝＝rear&&tag＝＝1；队空front＝＝rear&&tag＝＝0；队满:count>0&&front＝＝rear； 单元队空voidiniqueue(sequeue*sq){sq->front=0;sq->rear=0;}

intaddqueue(sequeue*sq,DataType{if(sq->front==(sq->rear+1)%maxlen){printf(“\nQueueisfull”);return}sq->queue[sq->rear]=x;sq->rear=(sq->rear+1)%maxlen;return1;}intdelqueue(sequeue*sq,DataType{if(sq->front==sq->rear){printf("\nQueueisempty!");return0;}*d=sq->queue[sq->front];

sq->front=(sq->front+1)%maxlen;return1;}四、队列的链式结

^

队列的链式结队头在链头，队尾在链尾front>next链队列的结构体定typedefstruct{DataTypedata;structslnode*next;}

typedef{LQNode*front;LQNode*rear;}初始intInitiateSLQueue(LQueue{if((q-{printf(“\n申请空间失败！”);return0;return1;}

ifif((p=(LQNode*malloc(sizeof(LQNode)))==NULL)intaddq(LQueue*q,DataType{LQNode{printf(“\intaddq(LQueue*q,DataType{LQNodep-p-p->next=NULL;XpXp∧q->rear=p;∧returnreturn1;ppintdelqueue(LQueue*q,DataType{LQNodeif(q->front->next==NULL)returnpp=q->front- p∧*d=p-∧q->front->next=p->next;free(p);return}1>n可由用户自定义2>3> 1>Panduan(charstr[],int2>EnterStr(charstr[],int*n)3>main() #defineMAXNUM80typedefchartypedef elemtypestack[MAXNUM];inttop;}typedef elemtypequeue[MAXNUM];intfront,rear; {charch,str[MAXNUM];intn;printf("\n是否继续?(y/n): elsebreak;}}voidvoidEnterStr(charstr[],int{}intintPanduan(charstr[],int{qstypemyStack;typemyQueue;charx,y;inti;{}while(QueueNotEmpty(&myQueue)==1while(QueueNotEmpty(&myQueue)==1&&{QueueDelete(&myQueue,&x);{printf(“不是回文 return0;}return1;}StackInitiate(qstypeStackInitiate(qstype{{}intStackPush(qstype*s,elemtype if(s->top>=MAXNUM-1)return0;else{s->stack[++(s- return}}intStackPopintStackPop(qstype*s,elemtype{ (s->top)--;return1;}intintStackNotEmpty(qstype{if(s->top<0)returnreturn}{q->rear=}typeintQueueAppend type*q,elemtype{if(q->rear>=MAXNUM-1)return0;q->queue[(q->rear)++]=x;return}intintQueueDelete{type*q,elemtype*x=q->queue[(q->front)return}intintQueueNotEmpty{typeif(q->rear==q->front)returnreturn}：： 相同点：相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表限的线性表（；栈和队列是两种特殊的线性表，即、删除运算加以限制）①运算规则不同，线性表为随机存取，而栈是只允许在 队列是只允许在一端进行 、另一端进行删除运算，用途不同，线性表比较通用；堆栈用于元素的保存次 作业：p883-2,3-Chapter 数组的结一、数组的定 一维数组随机存取结二维数

a0 a0 a0n-a1 a1 a1n- am-1 am-1 am-1n-Am×n=A=(a0a1…am-其中，ai=(ai0ai1…ain-数组中的数据元素数目固定数组中的数据元素具有相同的数据类型数组是一种随机结构，可随机存取数组int

数组的结通常采用顺序结以二维数组Amn为…a0(n-…a1(n-…a(m-a(m-…

…a(m-…a(m-…a(m-1)…a0(n-a1(n-…对于二维数组floata[5][4解：（1）5×4＝20（2）=2000+(3×4+2)：压缩矩阵中非零元素的个数较少（一般小于 0i,j 则称Aa0a1 a18926302517061389263025170613an-1 an-11an-12…an-1n-对称矩阵的压

1)2

j(j1)

21222212222502220613n阶上（下）三角矩阵是指矩阵的矩阵B的结构，则B中任一元素bij和sb[k]之间ik

i2

当

当i三、稀疏矩阵的压缩 例：写出下图所示稀疏矩阵的压缩形式0129000000000-30000–700方法1：用线性表表示((0,1,12)，(0,2,9)，(2,0,-3)，(3,2,24)，(4,1,18)，(5,0,15)，(5,3,-方法2：用三元组矩阵表示

0129000000000-300067678010292025053–700001200000001200000000-3007601h7601

–700020220-53-2553-25vji方法4：用链表表示vji用途：方法：每个非0元素占用5个域。

00000-300000-3000

–700

①每行非零元素成带表头结点的循环链表②每列非零元素也成带表头结点的循环链表。是列循环链表中的一个结点，即呈链状。9201920100014#definemaxsize10000typedefin typedefstruct{

inti,j;elemtyped;typedefstruct{

/*ijtupletypeint

20 0 30 0

4440003

M

000000-000000000-000000000-00 -(0,1,(0,1,(0,2,9(2,0,-(2,4,(3,2,(4,1,(5,0,(5,3,-

(0,(0,2,-(0,5,(1,0,(1,4,(2,0,(2,3,(3,5,-(4,2,提问答：肯定不正确除了：（1）每个元素的行下标和列下标互换（即三元组中还应该：（2）T的总行数md和总列数nd与M值不同（互换思路：反复扫描a.data中的列序，从小到大依次进行转置(0,1(0,19(2,(2,4,10(5,3,- 组 ④②⑦

(0(0,2,-(0,5,(1,0,(1,4,(2,0,(2,3,(3,5,-(4,2,voidtrantup(tabletypea,tabletype{intif(b-{

//q为b.datafor{

//col为扫描bifa.data[p].j==col)//p为a.data b-b- }}}}

演 23P1295-9，5-Chapter TreeandBinary树5.1adfhijadfhij树是由树是由n(n0)个结点组成的有限集合。如果n=0，称为空树；如果n>0，则有一个特定的称之为除根以外的其它结点划分为m(m0)个互不相交的有限集合T0T1Tm-1，每个集合又是一棵树，并且称之为根的(SubTree)。每棵的根结点有且仅有一个直接前驱，但可以aabcdefghij除根结点之外的所有结点有且只有一个前驱结点，根结点没有前驱结点树结构除根结点之外的所有结点有且只有一个前驱结点，根结点没有前驱结点树结构描述的是层次关abcdefghabfcdegh非树结 AABCDEFGHID:D=;空树 R={<Root,ri>,i=1,2,…m}D;D={Root}DF Root:树的根结DF:树的根结点Root的集DFD1D2D3 并且DiDj(ij;i=1,2,…m;j=1,2,…m主要用于树的屏幕和显示abdefc hddbiejafgcha(b(d,e(i,j),f),c(g,h)ABCDEFGHIABCDEFGHI拥有的的个数。孩子、兄弟、双亲：树中一个结点的的根结有序树和无序树：如果一棵树中结点的各从左到右是有次序的，即若交换某结点各的相对位置A

叶子结：：：：结点A：：：：结点B的

树的

结点M的 ：：结点B的孩：：

结点M的层：：：：结点L的：：：：

树的深331、初始化6、将一棵树到另一树的指定结点为它的子7、删除指定结点的某一delete(t,x,i) 双亲表示孩子表示孩子兄弟表示双亲孩子表示双亲表示（顺 ABCDEFABCDEFGA-B0C0D0E2F2G51234566双亲表示法－－c#defineMAXNODE32typedefstructdatatypedata;int }ptree

孩子表示法（多重链表法 D∧BD∧BA

C∧∧E∧F∧E∧F∧∧∧I∧J∧DCBAJIHGEDCBAJIHGEFFtypedeftypedefstruct{{intstructTreeNdoe}}

孩子结点指针孩子结点指针ABCDEFGHIJABCDEFGHIJAB0C0D0E1∧F1∧G2∧H3∧I3∧J3∧0123∧145∧263789∧456789DFECDFEC4、孩子兄弟表示法（二重链表法兄弟结点指针ABABC兄弟结点指针ABABCDEFGG孩子兄弟表示—C语言描 typedeftypedefstruct{elemtypestructTreeNode*son;structTreeNode*next;}一棵二叉树是结点的一个有限集合该集合或者为空，或者是由一个根结点加上两分别称为 和 的、互不相交的二叉组成

二叉左右左右左右左右 (2)殊二叉ABCDABCDEFGABCDEF行二叉，为i(0≤i≤n-1)的结点与为完全二叉树为i的结点位置相同，则此树 ABCDEF二叉排序树：若为非空二叉树根结点的都小于根结点关键字值，所有结点的关键字结点的关键字值都大于或等于根结所关键字值。一棵二叉排序树和又分别123、 结4、 结56 性质性质1若二叉树的层次从0开始i2i个结点。(i证明：i0时，有2i=20=1，成假定：ik时性质成立；即有2k个结点当ik+1时，第k+1的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k=2k+1故命题性质性质2若规定空树的深度为-1，则深度为k2k+1-1个结点。(k-有2-1+1-1=020+21+22+23+…+2k=2k+1－性质3对任何一棵二叉树n0,度为2n2,为2的结点：n=n0+n1+n22、另一方面，二叉树中一度结点有一个孩子，二度结n=n1+2n213n0=n2+性质性质4具有nlog2（n+1)-(“”表示上取整证明：设完全二叉树的高度为h，则0123456789 2h-10123456789 2h<n+1<=h<log2(n+1)<=性质5如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结 0,1,…,n-1，然后按此结将树中各结点顺序地存放于一个一维数组中0i若i0,i若i0,i的双亲为(i若2*i+1ni的左孩子为2*i+1；否则(2*i+1>没有左孩子，必定是叶子结若2*i+2<n,则i的右孩子为2*i+2；否则，i0

例1：i=5,2*i+1<n=17左兄弟：4，右兄弟：6例2：i=8,2*i+1=n二叉树 结 顺序结 完全二叉 010123456789ABCDEFGHIJAABCDEFGH010123456789ABCDEFGH情况样，可能会浪费很多空间，单支树情况单支 顺序二叉树结点的c#defineMAXNODE elemtype^G^^H^链式结^G^^H^链式结构形象化描述(不结点AA CABCDABCDEFGH ^E^ 链式结构形象化描述 )头结ABCDEFABCDEFGH ^E^ ^E^^G^G^^H^typedef

左孩右孩typedefstruct{elemtypedata;structnode*Lchild；structnode*Rchild;}

intInitiate(bitree

头结点{if((*bt=(bitree*)malloc(sizeof(bitree)))==NULL)return0;return1;}二叉树的创px FCBD^^FCBD^^^E^^^G^G^^H^bitree*Create(elemtypex,bitree*lbt,bitree{bitree*p;returnNULL;return}二叉树的ADADBparentEFGxHBACxEFDHGACBACB^^E^^Fp^E^^Fx^H^ACFB^ ACFB^xx^E^^^D^D^^H^二叉二叉 算bitree*InsertL(elemtypex,bitree{bitree*p;returnreturnNULL;xx

if(parent->Lchild==NULL)}删除二叉树bt中结点parentABABCDFGHABCEFHFFApABB^C^E^E^^^H^bitree (bitree*bt,bitree{bitreeif(parent==NULL||parent->Lchild==NULLprintf(“return}

p=parent->Lchild;

return }二叉排序树的生生成一棵二叉排序树,过程如下①若二叉排序树为空，则令待插结点为根结点②若二叉排序树非空，则比较待插结点(k)和根结点(k)的数据值。若1<k0,则将其到左中；否则，将其到右 中.③结点二叉排序树的左、右过程同上2828二叉排序树生成算法步骤（非递归{k0,k1,k2,…,kn-K0 ；若有ki>=kj且结点 二叉排序树生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}二叉树的遍一、二叉树的遍二叉树的遍历是指按照某种顺序二叉树中的每个结点，使每个结点被一次且只被访组成单元是：根结点D、左L和右R根}{}根}{}Postorder（后序{中序遍中序遍若二叉树为空，则空操作 根结点；（2）前序遍历左 A

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–P->P->BCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AP->AP->CDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AA CDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–AABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–ABABCDEFGH}voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–}

C voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)if(p–>Rchild!=NULL)}D

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– NULLvoidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p–

voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– voidPreorder(bitree{if(p==NULL)return;if(p–>Lchild!=NULL)Preorder(p–>Lchild);if(p–>Rchild!=NULL)Preorder(p– P-> 中序遍历若二叉树为空，则空操作（1）中序遍历左；（2）根结点（3）中序遍历 C

voidinorder(treenode{if(bt==NULL)if(bt->lchild!=NULL)inorder(bt-printf(“%d”,bt-if(bt->rchild!=NULL)inorder(bt-}后序遍历若二叉树为空，则空操作 ；（2）后序遍历右 根结点

后序遍历算法voidpostorder(treenode{if(bt==NULL)if(bt->lchild!=NULL)postorder(bt->lchild);if(bt->rchild!=NULL)postorder(bt->rchild);printf(“%d”,bt->data);}的顺序逐点。 AC

A

ABCGHIDJEKF前序：ABCDEFGHIJK中序：BDEFCAHGJKI后序：FEDCBHKJIGA层序：ABABCGHIDJEKF树

遍历（前序、中序、后序、层序前序遍历算法执行过程AAvoidPreorder(bitree{if(p==NULL)if(p–>Lchild!=NULL)if(p–>Rchild!=NULL)}^B^B^^C^A→B1100-1100- →C1200-1200-END 中序遍 后序遍voidInorder(treenode{if(bt==NULL)return;printf(“%d”,bt->data);}

voidPostorder(treenode{if(bt==NULL)return;printf(“%d”,bt-}{a1，…，am}和{b1，…若中序序列中与后序序列am相同的元素为bjA.j=1时，二叉树无 ，由{a1，…，am-1}{b2，…，bm}可以唯一的确定二叉树的 B.j=m时，二叉树无 ，由{a1，…，am-1}{b1，…，bm-1}可以唯一的确定二叉树的 若am{a1，a2…，ajaj+1 后个数相{b1，，bj-1，bj，bj+1，，bm 中唯一的确定 唯一的确定例1：后序序列{HDFBKGCEAHBDFAEKCG{HDFBKGCEA {HBDFAEKCGAA

E

CA

E {a1，…，am}和{b1，…若中序序列中与前序序列a若中序序列中与前序序列a1相同的元素为bjj=1时，二叉树无 ，由{a2，…，am}{b2，…，bm}可以唯一的确定二叉树的 j=m时，二叉树无 ，由{a2，…，am}{b1，…，bm-1}可以唯一的确定二叉树的 2<=j<=m-1，则子序列{a2，…，aj}和{b1，，bj-1}唯一的确定二叉树的 ；子序列…，am}和{bj+1，…，bm各左、 进行如上操作若a1{a1，a2…，ajaj+1 前{b1，…，{b1，…，bj-，bj+1，，bm 中唯一的确定 唯一的确定例例2：前序序列ABHFDECKGHBDFAEKCG前序序列：1，2，3，4，5，6，7，8，9中序序列中序遍历的结果后序遍历的结果该二叉树并写该二叉树并写遍历结5.5树、森林与二叉树的转对树中不是双亲结点 个 保留新添加的

子结点连线位于左孩子指针位置，使

A 连 抹

整理CE FGABABCDEFGHABDCEGFH 连请做练习将如图所示的森林转换成二叉树ABCDABCDEFGHIJKABCGHIDJEKF

删除原二叉树中所有双亲结点 连线点位于相同层次高度。ABABCDEFG DFGABABDCEGFHABCDEFGHABABCDEFGABCDEFG ABABCDEFGABCDEFG ABCDEFG ABCDEFG练习请给出该树的先根、后根和层序遍历结ABCDEFGH先根：ABECFABCDEFGHEBFCGHD层序：ABCDEFG作业p1957-4，7-10，7-11，补充题1、树:(最优二叉树是一种带权路径最短的于信息检索、判定树、编码等。树（Huffman树（HuffmanTree路径长度：结点的带权路径长度。WPL。WPLwinWPL=7*3+9*3+5*2+6*2+2*=WPL=2*1+6*3+7*4+9*4+5*=WPL=6*2+7*2+5*3+2*3+=WPL=2*1+5*3+7*3+9*3+=WPL的二叉树，其中具有最小WPL的二叉树称为树（或最优棵树。每棵树只有一根结点。将这些树

编另一个字符的编码的前缀，这种编码称为前缀编码CASTCASTSATATA字符集合是{C,A,S,TW＝2,7,4,5A: T: C: S:2+7+4+5*22/18,7/18,4/18,5/18为{2,7,4,5}。2,7,45夫曼树。左分支赋0，右分支赋1，得A: T: C: S:7*1+5*2+(2+4)*3= 5.7.2二叉排序树的生二叉排序树生成算法步骤（非递归{k0,k1,k2,…,kn- ；若有ki>=kj且结点 二叉排序树生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}

先序遍 后序遍

结 遍树

2 结

链式结森 二叉

先序遍树树

中序遍层序遍编 bitree*findnode(bitree*bt,elemtype{bitreeif(bt==NULL)returnNULL;if(bt->data==x)returnbt;if(bt->Lchild!=NULL){p=findnode(bt-if(p!=NULL)returnp; if(bt->Rchild!=NULL){p=findnode(bt->Rchild,x);if(p!=NULL)return returnNULL;

空查找不成typedefstruct{ structnodebnode*b；/*指向根结点的指针intcounter=0；/*记结点个数，全局变量voidcountleaf(bnode/*counter{if(b==NULL)if(b->L==NULL&&b->R=counter=elseprintf(“%d”,b->data);}typedefstruct{ structnodebnode*b；/*指向根结点的指针intcounter=0；/*记结点个数，全局变量voidbitree(bnode{if{if((b->L!=NULL)&&(b- }}}typedefintelemtype;typedefstructbtreenode{elemtypestructbtreenode*Lchild；structbtreenode*Rchild;}intcount=0*计数变量，全局变量作业p195 性质性质1若二叉树的层次从0开始i2i个结点。(i性质性质2若规定空树的深度为-1，则深度为k2k+1-1个结点。(k-性质3对任何一棵二叉树n0,度为2n2,性质性质4具有nlog2（n+1)- (“”表示上取整性质5如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结 0,1,…,n-1，然后按此结将树中各结点顺序地存放于一个一维数组中0i若i0,i若i0,i的双亲为(i若2*i+1ni的左孩子为2*i+1；否则(2*i+1>没有左孩子，必定是叶子结若2*i+2<n,则i的右孩子为2*i+2；否则，i#defineMAXNODE typedefintelemtype;elemtypebt[MAXNODE];typedefin typedefstructnode{elemtypedata;structnode*Lchild；structnode*Rchild;}二叉树的ADADBparentEFGxHBACxEFDHG二叉二叉 算bitree*InsertL(elemtypex,bitree{bitree*p;returnreturnNULL;xx

if(parent->Lchild==NULL)returnp;}删除二叉树bt中结点parentABABCDFGHABCEFHbitree (bitree*bt,bitree{bitreeif(parent==NULL||parent->Lchild==NULLprintf(“return}

p=parent->Lchild;

return }前（先）序遍历若二叉树为空，则空操作 根结点；（2）前序遍历左 ABCDEFGHABCDEFGH ABCDEFGHABCDEFGHvoidpreorder(bitree{if(bt==NULL)printf(“%d”,bt-if(bt->Lchild!=NULL)preorder(bt->Lchild);if(bt->Rchild!=NULL)preorder(bt->Rchild);}中序遍历若二叉树为空，则空操作（1）中序遍历左；（2）根结点（3）中序遍历 C

voidinorder(bitree{if(bt==NULL)if(bt->Lchild!=NULL)inorder(bt-printf(“%d”,bt-if(bt->Rchild!=NULL)inorder(bt-}后序遍历若二叉树为空，则空操作后序遍历 ；（2）后序遍历右 根结点

后序遍历算法voidpostorder(bitree{if(bt==NULL)if(bt->Lchild!=NULL)postorder(bt->Lchild);if(bt->Rchild!=NULL)postorder(bt->Rchild);printf(“%d”,bt->data);}

整 连 抹

C B

A D GWPLWPLwinCASTCASTSATATAC,A,S,TW＝2,7,4,52,7,45树。左分支赋0，右分支赋1，得 A:T:C:S:二叉排序树的生③结点二叉排序树的左、右过程同上2828二叉排序树生成算法描#defineNbitree*creat_bstree(elemtype{intbitree*bt,*s,*p,*q;forif(bt==NULL){p=bt;{

if(s->data<p->data)ifif(s->data<q-q-return}}}第六 Chapter 图的基本概图的结图的遍图的定义图是由一个非空的顶点集合和一描述顶点之间关系——边（或者弧）的