软件技术基础-数据结构课件

软件技术基础20.序论软件技术基础的主要内容数据结构：讨论和研究计算机系统中数据的组织形式及相互关系操作系统：Operatingsystem(OS),例如(DOS,Windows,Unix,MAC,Linux,etc.)软件工程：“软件危机”，其它工程类知识(机械工程、电子工程、化工工程的思想引入软件开发)、程序→软件…Database：数据库（xbase、Access、Sybase、Oracle…）网络基础：Internet/Intranet,拓扑结构、网络协议等教学的展开理论介绍（抽象）上机学习课程性质与重要性专业基础课的定位承上启下的作用（每一章都是一门独立的学科）软

件

技

术

基

础第一章数据结构41.1数据结构的基本概念什么是数据结构数据结构中的基本概念C语言的数据类型抽象数据类型－数

据

结

构软件技术基础5什么是数据结构什么是数据结构数据结构的定义：讨论和研究计算机系统中数据的组织形式及相互关系。数据：用计算机对客观事物进行识别、存储和加工所进行的描述，统称为数据，其基本单位是数据元素（数据节点）,ie,十进制，二进制常数、字母、字符、程序段、图形图像、语音文件等。SP：数据不仅仅指数值。结构：指事物间的相互关系和约束。－数

据

结

构软件技术基础一般用下列二元组来描述：

DS=（D，R）其中：

D：是数据元素的有限集合；

R：是数据元素之间关系的集合。6什么是数据结构举例课题组由1名教师、1~3名研究生、1~6名本科生组成；成员关系是：教师指导研究生、研究生指导1~2名本科生。定义DS如下：

Group=（D，R）其中：

D={T,G1,…,Gn,S11,…,Snm}

1n3,1m2R={R1,R2}R1={〈T,Gi〉|1≤i≤n,1≤n≤3}R2={〈Gi,Sij〉|1≤i≤n,1≤j≤m,1≤n≤3,1≤m≤2}－数

据

结

构软件技术基础7什么是数据结构数据结构研究的属畴数据元素间的逻辑关系。采用什么样的存储结构。采用什么样的操作实现算法效率更高。－数

据

结

构软件技术基础8Exp:线性表结构－数

据

结

构软件技术基础IDNameClassesMathPhysicCircuitCLanguage1丁一960131879086842马二960131808186903张三960131918890874李四960131938892855王五96013167667065┆┆┆┆┆┆┆typedefstructstudent{intid;charname[20];intclasses;floatscore[4];}elemtype;elemtype｛…｝表示了数据元素的类型。9数据结构中的基本概念数据结构的三层次概念数据的逻辑结构从解决问题的需要出发，为实现必要的功能所建立的数据结构，它属于用户的视图，是面向对象的。反映的是数据元素间的逻辑关系。数据的存储结构（物理结构）指数据该如何在计算机中存放，是数据逻辑结构的物理存储方式，是属于具体实现的视图，是面向计算机的。数据操作集合－数

据

结

构软件技术基础10数据结构中的基本概念数据的逻辑结构分类线性结构有且仅有一个开始数据元素和一个终点数据元素，并且所有数据元素都最多只有一个直接前趋和一个直接后继。非线性结构非线性结构的逻辑特征是该结构中一个数据元家可能有多个直接前趋和直接后继。－数

据

结

构软件技术基础157324图结构6abcdefhgi树结构11a2a1a312345数据结构中的基本概念数据的存储方法顺序存储：把逻辑上相邻的数据元素存储在物理位置上相邻的存储单元里，元素间的逻辑关系由存储单元的邻接关系体现。链接存储：该方法不要求逻辑上相邻的元素其物理位置上亦相邻，元素间的逻辑关系是由附加的指针字段表示的。－数

据

结

构软件技术基础Exp：对于线性结构B1=（a1,a2,a3,a4,a5）B1的顺序存储a2a3a4a512345a1B1的链式存储12数据结构中的基本概念数据的存储方法索引存储：该方法通常是在存储元素信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。－数

据

结

构软件技术基础……王2王1……张2张1……李2李1地址姓名王……张李地址姓13数据结构中的基本概念数据的存储方法散列存储：该方法的基本思想是根据元素的关键字直接计算出该元素的存储地址。即在数据元素的字段中有一个或几个字段的值，通过某一散列函数唯一地确定该元素的存储地址。－数

据

结

构软件技术基础14数据结构中的基本概念数据的处理与运算遍历：在数据结构的各个元素中移动，或查看所有数据元素。插入：往数据结构中添加新的元素。更新：修改或替代数据结构中指定元素的一个或多个数据项(字段值)。删除：把指定的数据元素从数据结构中去掉。查找：在数据结构中查找满足一定条件的数据元素。排序：在保持数据结构中数据元素个数不变的前提下，把元素按指定的顺序重新排列。－数

据

结

构软件技术基础15C语言的数据类型基本数据类型intshort；long；unsigned

floatfloat；double；longdoublechar指针类型

inta,b,*pa;pa=&a;b=*pa;//b=a－数

据

结

构软件技术基础voidmain(){voidswap();inta,b;a=10;b=20;printf(“beforecallingswap()a=%db=%d\n”,a,b);swap(&a,&b);printf(“aftercallingswap()a=%db=%d”,a,b);}voidswap(int*x,int*y){inttemp;temp=*x;*x=*y;*y=temp;}beforecallingswap()a=10b=20aftercallingswap()a=20b=1016C语言的数据类型数组类型与字符串

inta[100];floatb[10][10];chars[20]=“Thisisastring”;－数

据

结

构软件技术基础s[0]Ts[1]h……s[15]gs[16]‘\0’……17C语言的数据类型结构类型－数

据

结

构软件技术基础typedefstructdate{intyear;charmonth[5];intday;}date;dated1,d2;d1.year=2003;d1.month=“Feb”;d1.day=1;18抽象数据类型(AbstructDataType-ADT)数据类型

定义：一个数据的集合,以及定义于这个数据集合上的一组操作的总称。抽象数据类型由用户定义，用以表示应用问题的数据模型由基本的数据类型组成,并包括一组相关的服务（或称操作）信息隐蔽和数据封装，使用与实现相分离（物理实现封装）－数

据

结

构软件技术基础19抽象数据类型(AbstructDataType-ADT)抽象数据类型的定义

ADT抽象数据类型名{

数据对象：数据对象的定义

数据关系：数据逻辑关系的定义

基本操作：基本操作的定义}ADT抽象数据类型名基本操作的定义基本操作名（参数表）

初始条件：初始条件描述

操作结果：操作结果描述－数

据

结

构软件技术基础20抽象数据类型(AbstructDataType-ADT)Exp:一个圆柱体抽象类型可以定义如下：

ADTCYLinder{数据：

floatr,h;

操作：

Initcyld(r,h);[初始化圆柱，r底面半径，h圆柱高]Basearea(r);[计算底面积，r底面半径]Sidearea(r,h);[计算侧面积，r底面半径,h圆柱高]Volume(r,h);[计算体积，r底面半径,h圆柱高]}－数

据

结

构软件技术基础21抽象数据类型(AbstructDataType-ADT)结合C语言，抽象数据类型的数据部分可用struct来定义，其操作部分可用函数来实现。对于上述圆柱类型，其数据部分可定义如下：

typedefstructCylinder{floatr,h;}Cylinder;初始化圆柱函数可以定义如下：

CylinderInitcyld(floatr0,floath0){Cylindercyl;//定义一个圆柱型变量cylcyl.r=r0;cyl.h=h0;return(cyl);}－数

据

结

构软件技术基础22抽象数据类型(AbstructDataType-ADT)求圆柱体积函数可以定义如下：

floatVolume(Cylindercyl){floatv;//V为体积

v=3.14159*cyl.r*cyl.r*cyl.h;return(v);}－数

据

结

构软件技术基础231.2线性结构线性表栈与队列数组串－数

据

结

构软件技术基础线性结构的特点：数据元素有序并有限。线性结构的逻辑特征：有且仅有一个无直接前趋而仅有一个直接后继的数据元素为起始元素；有且仅有一个无直接后继而仅有一个直接的前趋的数据元素为终点元素；其余均为内部元素，它们各有一个直接前趋和直接后继。线性结构可以排列成一个线性序列：

a1,a2,a3,…,an线性结构分类：24线性表线性表是n(n≥0)个相同类型数据元素a1,a2,…，an构成的有限序列。线性表通常表示为：(a1,a2,…,an)其中n为线性表的长度，ai(1≤i≤n)是线性表中第i个序号的数据元素。Exp：英文字母表（A,B,C,…..Z)是一个线性表－数

据

结

构软件技术基础学号姓名年龄001张三18002李四19………数据元素25线性表线性表的基本操作INITIATE(L)｛初始化｝：设定一个空的线性表L。

LENGTH(L)｛求表长｝：对给定的线性表L，函数返回值为其数据元素的个数。

GET(L,i)｛取元素｝:若给定的数据元素序号i满足1≤i≤LENGTH(L)，则函数返回值为给定线性表L的第i个数据元素ai；否则返回空元素。LOCATE(L,x)｛定位｝:若线性表L中存在某个ai等于x，则函数返回索引号i；若L中存在多个等于x的数据元素，则函数返回索引号最小的i值；若L中不存在等于x的数据元素，则函数返回一个特殊值(比如－1)，以说明不存在的位置。

INSERT(L,i,x)｛插入｝:若1≤i≤LENGTH(L)，则在线性表的第i位置上插入一个新的数据元素x，使表长度由n变为n＋1，并使函数返回值为true，否则函数返回值为false。DELETE(L,i)｛删除｝：若1≤i≤LENGTH(L)，则把线性表L中第i个元素ai删除，使表长度由n变为n－1，并使函数返回值为true，否则函数返回值为false。－数

据

结

构软件技术基础26线性表Exp：利用线性表的基本运算实现清除L中多余的重复节点。

PURGE(Linear_list*L) {inti=1,j,x,y; while(i<LENGTH(L)) {x=GET(L,i); j=i+1; while(j<=LENGTH(L)) {y=GET(L,j); if(x==y)DELETE(L,j);elsej++;}i++;}}－数

据

结

构软件技术基础27顺序表顺序表的存储结构在顺序表的存储结构中，数据元素按其逻辑次序依次存放在一组地址连续的存储单元里。顺序表的元素地址计算方法

Loc(ai)=Loc(a1)+(i-1)*kk—每个数据元素占用存贮单元的个数显然，顺序表中每个元素的存储地址是该元素在表中索引号的线性函数。特点实现逻辑上相邻—物理地址相邻实现随机存取线性表－数

据

结

构软件技术基础28线性表顺序表的存储结构示意图

－数

据

结

构软件技术基础存储地址内存状态元素索引号Loc(a1)a11Loc(a1)+ka22………Loc(a1)+(i-1)*kaii………Loc(a1)+(n-1)*kann29线性表顺序表的结构类型typedefstruct{elemtypedata[MAXNUM];intnum;}listtype;listtypelist;elemtype—顺序表中元素的类型MAXNUM—顺序表最大元素个数初始化listvoidinitiatelist(listtype*l){l->num=0;}－数

据

结

构软件技术基础30线性表顺序表的插入算法〖算法1〗a1a2…aiai+1…an…12…ii+1…na1a2…xai…an-1an…12…ii+1…nn+131－数

据

结

构软件技术基础 #definetrue1 #definefalse0 intinsertl(listtype*l,inti,elemtypex)

｛intj; if(l->num>=MAXNUM)

｛printf(”thelistisfull,cannotinsert.”);return(false);

｝

if(i<0)||(i>l->num)

｛printf(”iisinvalidvalue”);return(false);

｝

for(j=l->num-1;j>=i;j--)

l->data[j+1]=l->data[j];l->data[i]=x;l->num++;return(true);

｝32线性表顺序表的删除算法〖算法2〗－数

据

结

构软件技术基础a1a2…aiai+1…an…12…ii+1…na1a2…ai+1ai+2…an…12…ii+1…n-133－数

据

结

构软件技术基础

#definetrue1 #definefalse0 intdelete_l(listtype*l,inti)

｛intj; if(i<0)‖(i>l->num-1)

｛printf(”notexist”);return(false);

｝

for(j=i+1;j<l->num;j++)

l->data[j-1]=l->data[j];l->num--;return(true);

｝34顺序表顺序存储结构的优缺点优点逻辑相邻，物理相邻可随机存取任一元素存储空间使用紧凑缺点插入、删除操作需要移动大量的元素预先分配空间需按最大空间分配，利用不充分表容量难以扩充线性表－数

据

结

构软件技术基础35线性链表

存储特征：用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零散分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。线性表－数

据

结

构软件技术基础结点36线性链表单链表结点中只含一个指针域的链表线性表－数

据

结

构软件技术基础datanextC语言表示：typedefstructnode{elemtypedata;structnode*next;}node;node*h,*p;datanextp结点（*p）(*p)表示p所指向的结点(*p).datap->data表示p指向结点的数据域(*p).nextp->next表示p指向结点的指针域生成一个node型新结点：p=(node*)malloc(sizeof(node));系统回收p结点：free(p)37单链表线性表－数

据

结

构软件技术基础a1线性表：a1,a2,a3,…,ana2a3an^…ha1a2an^…h带头结点的单链表^h带头结点的空表38单链表线性表－数

据

结

构软件技术基础初始化单链Voidinitatesl(node**h){*h=(node*)malloc(sizeof(node));(*h)->next=NULL;}39访问单链表的算法〖算法3〗线性表－数

据

结

构软件技术基础elemtypeaccess(node*h,inti){node*p;intj;p=h;j=0;WHILE(p->next!=NULL&&j<i){p=p->next;j++;}if(p!=NULL&&j=i)return(p->data);elsereturn(NIL);}40单链表的插入算法〖算法4〗线性表－数

据

结

构软件技术基础a1hai－1…ai…an^xp41软件技术基础－数

据

结

构a1hai－1…ai…an^xpvoidinsertsl(node*h,inti){node*p,*t;intj;p=h;j=0;WHILE(p->next!=NULL&&j<i-1){p=p->next;j++;}//寻找第i－1个结点

if(j!=i-1){printf(“iisinvalid”);return;}//插入位置i不合理

t=(node*)malloc(sizeof(node));t->data=x;t->next=p->next;p->next=t;//链的重新连接}t42单链表的删除算法〖算法5〗线性表－数

据

结

构软件技术基础a1hai－1…ai…an^pai+1sai43软件技术基础－数

据

结

构voiddeletesl(node*h,inti){node*p,*s;intj;p=h;j=0;WHILE(p->next!=NULL&&j<i-1){p=p->next;j++;}//寻找第i－1个结点

if(j!=i-1){printf(“iisinvalid”);return;}//判定i是否是有效结点

s＝p->next;p->next=s->next;//链的重新连接

free(s);//释放被删除结点存储空间}a1hai－1…ai…an^pai+1sai44单链表生成的算法〖算法6〗线性表－数

据

结

构软件技术基础a1hai－1…ai…an^s45软件技术基础－数

据

结

构voidcreatesl(node**h){node*p,*s;intj;elemtypex;*h=(node*)malloc(sizeof(node));(*h)->next=NIL;//初始化空表

pread(x);WHILE(x!=-1)//’-1’为线性表结束标志

{s=(node*)malloc(sizeof(node));s->data=x;if((*h)->next==NIL)(*h)->next=s;elsep->next=s;//判定是否建立第一个结点

p=s;//p始终指向最后一个结点

pread(x);}p->next=NIL;}a1hai－1…ai…an^s^^pps46单链表特点它是一种动态结构，整个存储空间为多个链表共用不需预先分配空间指针占用额外存储空间不能随机存取，查找速度慢线性表－数

据

结

构软件技术基础47prior线性链表双链表结点结构线性表－数

据

结

构软件技术基础datanextC语言表示：typedefstructnode{elemtypedata;structnode*prior,*next;}node;h…a1a2…an^abcpp->prior->next=p=p->next->proir48双链表的结点插入〖算法7〗线性表－数

据

结

构软件技术基础ai-1aipvoidinsertdl(node*p,elemtypex){node*t;t=(node*)malloc(sizeof(node));t->data=x;t->prior=p->prior;//确定新结点的前趋

p->prior->next=t;//确定i-1结点的后继

t->next=p;//确定新结点的后继

p->prior=t;//重新定义i结点的前趋}xt49双链表的结点删除〖算法8〗线性表－数

据

结

构软件技术基础ai-1ai+1voiddeletedl(node*p){p->prior->next=p->next;p->next->prior=p->prior;free(p);}aipai50线性链表循环链表

循环链表是表中最后一个结点的指针指向头结点，使链表构成环状特点：从表中任一结点出发均可找到表中其他结点，提高查找效率操作与单链表基本一致,循环条件不同单链表p：p->next=NULL循环链表p：p->next=H线性表－数

据

结

构软件技术基础51循环链表

线性表－数

据

结

构软件技术基础循环单链空表h循环双链空表h循环单链表a1hai－1…ai…an循环双链表…a1a2…anhr尾指针h52链表的合并

线性表－数

据

结

构软件技术基础voidconnect_a(node**ha,node*hb){node*p;p=*ha;while(p->next!=NIL){p=p->next;}//遍历第一链表，找到anp->next=hb->next;//将链表hb的第一结点与链表ha的尾结点链接

free(hb);//释放链表hb的头结点}b1hbbi－1…bi…bn^a1haai－1…ai…an^^hb单链表53链表的合并

线性表－数

据

结

构软件技术基础voidconnect_b(node*ra,node**rb){node*p;p=(*rb)->next;//保存rb的头结点地址

(*rb)->next=ra->next;//rb尾结点与ra的头结点链接

ra->next=p->next;//链表rb的第一结点与链表ra的尾结点链接

free(p);//释放链表rb的头结点}

循环单链表a1ai－1…ai…anrab1bi－1…bi…bnrbp54栈与队列栈与队列是两种特殊的线性表，是操作受限的线性表，它们的逻辑结构与线性表相同，只是其插入、删除运算只允许在表的端点进行，栈与队列是程序设计中常用的2种数据结构。－数

据

结

构软件技术基础55栈（Stack）定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈。特点：先进后出（FILO）或后进先出（LIFO）栈与队列－数

据

结

构软件技术基础出栈进栈a2…an-1an栈底栈顶a156栈（Stack）栈的五种基本操作SETNULL(s)｛置空栈｝:将栈S置成空栈。EMPTY(s)｛判空栈｝:这是一个布尔函数。若栈S为空栈,则返回值“真”，否则返回值“假”。PUSH(s,x)｛进栈｝:在栈S的顶部插入(亦称压入)元素x。POP(s)｛出栈｝:若栈S不空,则删除(亦称弹出)顶部元素。TOP(s)｛出栈顶｝:取栈顶元素，并不改变栈中内容。栈与队列－数

据

结

构软件技术基础57栈（Stack）顺序栈用一组连续的存贮空间存放栈元素，可用一维数组来实现。typedefstruct{elemtypestack[MAXNUM];inttop;}stacktype;//顺序栈结构定义stacktypes;//定义一个堆栈voidinitiatest(stacktype*s)//对栈s初始化

{s->top=-1;}栈与队列－数

据

结

构软件技术基础58顺序栈的元素插入算法〖算法9〗

栈与队列－数

据

结

构软件技术基础#definetrue1#definefalse0intpushs(stacktype*s,elemtypex){if(s->top>=MAXNUM-1)return(false);//栈满，不能再插入

else{s->top++;s->stack[s->top]=x;//进栈

return(ture);}}toptoptoptoptoptop012345top-1abcdefgoverflow59顺序栈的元素删除〖算法10〗

栈与队列－数

据

结

构软件技术基础elemtypepops(stacktype*s){if(s->top<0)return(NIL);//栈空

else{s->top--;return(s->stack[s->top+1];}//栈顶元素出栈}toptoptoptoptoptoptop-1toptoptoptoptoptop012345abcdefunderflow60栈（Stack）链栈

链栈是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行。链栈中每个数据元素用一个结点表示，栈顶指针作为链栈的头指针，常用来命名一个链栈，不再增设头结点。typedefstructnode{elemtypedata;structnode*next;}node;//链栈结构定义栈与队列－数

据

结

构软件技术基础aiai－1a2a1^top…61链栈的进栈算法〖算法11〗

栈与队列－数

据

结

构软件技术基础voidpushs(node**top,elemtypex){node*p;p=(node*)malloc(sizeof(node));p->data=x;p->next=(*top);(*top)=p;}aiai－1a2a1^top…xptoptop62链栈的元素删除（出栈）算法〖算法12〗

栈与队列－数

据

结

构软件技术基础elemtypepops(node**top){node*p;elemtypex;if((*top)==NIL){printf(“stackisunderflow”);return(NIL);}x=(*top)->data;p=(*top);(*top)＝(*top)->next;free(p);return(x);}aiai－1a2a1^top…topxptop63队列（Queue）定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)栈与队列－数

据

结

构软件技术基础a2…ai-1aia1队尾入队…rear队头front012i-1in出队64队列（Queue）队列的五种基本操作SETNULL(Q)｛置空队列｝:将队列Q初始化为空。EMPTY(Q)｛判队列空｝:若队列Q为空队列,函数返回true，否则返回false。ENTER(Q,x)｛入队列｝:若队列Q未满，在原队尾后加入数据元素x，使x成为新的队尾元素。DELETE(Q)｛出队列｝:若队列Q未空,则将队列的队头元素删除。GETHEAD(Q)｛取队头元素｝:若队列Q未空,则函数返回对头数据元素，但不改变队列中内容。栈与队列－数

据

结

构软件技术基础65队列（Queue）队列的顺序存储结构

用一组连续的存贮空间存放队列元素。typedefstruct{elemtypequeue[MAXNUM+1];intfront;intrear;}queuetype;//队列结构定义queuetypeq;//定义一个队列q栈与队列－数

据

结

构软件技术基础66入队列操作〖算法13〗

栈与队列－数

据

结

构软件技术基础#definetrue1#definefalse0intenter(queuetype*q,elemtypex){if(q->rear>=MAXNUM)return(false);else{q->rear++;q->queue[q->rear]=x;return(true);}}frontrearrearrearrearrearrearrear012345abc67出队列操作〖算法14〗

栈与队列－数

据

结

构软件技术基础elemtypedelete(queuetype*q){if(q->front==q->rear)return(NIL);else{q->front++;return（q->queue[q->front]);}}frontrearfrontfrontfrontfrontfrontfront012345abc

存在问题假溢出rearerearrearrearf当front=0,rear=M时，再有元素入队发生溢出——真溢出当front0,rear=M时，再有元素入队发生溢出——假溢出

解决方案循环队列68循环队列

队列的结构空间首尾相连。把队列设想成环形。栈与队列－数

据

结

构软件技术基础队头指针进1:front=(front+1)%MAXNUM队尾指针进1:rear=(rear+1)

%MAXNUM队列初始化：front=rear=0队空条件：front==rear队满条件：(rear+1)%MAXNUM==front01234567frontrearrearrearrearrearrearrearrearrear为了区别队空、队满两种状态，在循环队列中约定，队列仅还有一个空位时，队列就为满状态.69循环队列的入队操作〖算法15〗

栈与队列－数

据

结

构软件技术基础#definetrue1#definefalse0intenter(queuetype*q,elemtypex){if((q->rear+1)%MAXNUM==q->front)return(false);//队列已满

else{q->rear=(q->rear+1)%MAXNUM;q->queue[q->rear]=x;return(true);}}01234567frontrearrearrearrearrearrearrearrear70循环队列的出队操作〖算法16〗

栈与队列－数

据

结

构软件技术基础elemtypedelete(queuetype*q){if(q->front==q->rear)return(NIL);else{q->front=(q->front+1)%MAXNUM;return（q->queue[q->front]);}}frontfrontfrontfrontfrontfrontfront01234567rearfront71队列（Queue）队列的链式存储结构

可以用带头指针的单链表作为队列的链式存储结构，将队头指针指向单链表的头结点，将队尾指针指向单链表的最后一个结点。typedefstructnode{elemtypedata;structnode*next;}node;

typedefstructqtype{node*front;node*rear;}qtype;栈与队列－数

据

结

构软件技术基础reara1a2an^…front头结点72进链队列操作算法〖算法17〗

栈与队列－数

据

结

构软件技术基础voidenter(qtype*q,elemtypex){node*p;p=(node*)malloc(sizeof(node));p->data=x;p->next=NULL;//新的队尾结点

q->rear->next=p;//链入队列中

q->rear=p;//修改队尾指针}reara1a2an^…front头结点xprear^rear73出链队列操作算法〖算法18〗

栈与队列－数

据

结

构软件技术基础elemtypedelete(qtype*q){node*p;elemtypex;if(q->front->next==NIL)return(NIL);//队列空

else{p=q->front->next;x=p->data;if(p->next==NULL)q->rear=q->front;//若队长为1,修改队尾指针

elseq->front->next=p->next;//修改队头指针

free(p);return(x);}}reara1a2an^…front头结点px74栈和队列的应用栈子程序调用的断点与现场保护(FIFO,FILO)递归算法（调用自己）编译系统中的表达式计算队列任务的排队（多任务系统）缓冲区设计等栈与队列－数

据

结

构软件技术基础75从逻辑结构上看，二维数组的每一行都是一个线性表，同行元素间的关系满足线性表的关系，即a11是a12的“行前趋”，而a12是a11的“行后继”。同理每一列也是一个线性表，元素间也满足线性表的关系。整个数组Amn可以看成是由m个行向量组成的线性表，也可以看成由n个列向量组成的线性表。前者称为数组的行主序，后者称为数组的列主序。线性表中的数据元素本身也是一个线性表，从这种意义上讲，数组可以看成是线性表的扩展。数组－数

据

结

构软件技术基础二维数组76数组数组特点数组结构固定数据元素同构数组运算给定一组下标，找到与之相应的数据元素。

给定一组下标，存取或修改与其相应的数据元素中某个数据项的值。

－数

据

结

构软件技术基础77数组数组的顺序存储结构行优先顺序存储=mn2n2221aaaK1n1211aaaKALoc(aij)=Loc(a11)+[(i-1)*n+(j-1)]*sa11a12…a1n01n-1…a21a22…a2nn2n-1…am1am2…amn……m*n-1…mnm2m1aaaKKKKK－数

据

结

构软件技术基础78数组数组的顺序存储结构列优先顺序存储=mn2n2221aaaK1n1211aaaKALoc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*sa11a21…am101m-1…a12a22…am2m2m-1…a1na2n…amn……m*n-1…mnm2m1aaaKKKKK－数

据

结

构软件技术基础79数组数组的顺序存储结构推广到多维数组行优先的顺序存放：以左下标为主序，即先排右下标，最后排左下标；列优先顺序的存放：则以右下标为主序，即先排左下标，最后排右下标。－数

据

结

构软件技术基础80数组矩阵的压缩存储结构对称矩阵

a11a12

….

……..a1n

a21

a22

……..…….a2n

an1

an2

……..ann

….k=012345n(n-1)/2n(n+1)/2-1按行序为主序：a11a21a22a31a32a33an1…ann…－数

据

结

构软件技术基础81数组矩阵的压缩存储结构对角矩阵k=0123453(n-1)

按行序为主序：a11a12a21a22a23a32ann-1ann…a11a120………a21a22a230……0a32a33a340…………………0……0an-1,n-2an-1,n-10………0an,n-1000…an-1,nann－数

据

结

构软件技术基础Loc(aij)=Loc(a11)+[2(i-1)+(j-1)]*S

82数组矩阵的压缩存储结构稀疏矩阵非零元素较零元素少，且分布没有一定规律的矩阵压缩存储原则：只存矩阵的行列维数和每个非零元的行列下标及其值。（三元存储法）－数

据

结

构软件技术基础设A是一个m×n的稀疏矩阵，其中非零元素的个数为I，三元存储法可采用一个(I+1)×3的T来存储A。矩阵T的第一行是m，n，I；后面的每一行对应A矩阵中的一个非零元素，如某一行为i，j，x；对应的是矩阵A中第i行，第j列的那个值为x的非零元素。矩阵A中各非零元素对应的三元组可按其行的递增次序(相同行按列的递增次序)排序，这称为行优先的三元组存储方式。83数组矩阵的压缩存储结构稀疏矩阵－数

据

结

构软件技术基础#defineM20typedefstructnode{inti,j;intx;}node;nodema[M];ijx565111157231231352-3ma[0].i,ma[0].j,ma[0].x分别存放矩阵行列维数和非零元个数三元组表所需存储单元个数为3(I+1)其中I为非零元个数84串串（字符串），是由零到多个字符组成的连续有限序列，一般记为：

S=‘a1a2a3…an’

其中，S为串名，引号中为串值，ai为串元素，n（n≥0）是串的长度。－数

据

结

构软件技术基础

一个串中任意多个连续的字符组成的子序列称为该串的子串，包含该子串的串称为主串，一个字符在串中的序号称为该字符在串的位置。当一个字符在串中多次出现时，该字符在串中的位置指的是该字符在串中第一次出现的位置。子串的主串中的位置指的是该子串的第一个字符在主串中的位置。称两个串是相等的即是指两个串中的字符序列一一对应相等。例如有如下一些串：

S1=‘Iamastudent’;

S2=‘teacher’;

S3=‘a’;

S4=‘student’;

S5=‘student□’;85串对比串的定义和线性表的定义可知，串是一种其数据元素固定为字符的线性表。因此，仅就数据结构而言，串归属于线性表这种数据结构。串的基本操作和线性表上的基本操作相比却有很大的不同。线性表上的操作主要针对线性表中的某个数据元素进行，而串上的操作主要是针对串的整体或串的某一部分子串进行。－数

据

结

构软件技术基础86串串的基本操作：ASSIGN(S,T)｛赋值｝：把串T的值赋给串S。EQUAL(S,T)｛判相等｝：S，T为串名或串值，若S和T相等，则函数返回true，否则函数返回false。LENGTH(S)｛求串长｝：求串S的长度，返回值为串S中字符的个数。SUBSTR(S,start,len)｛取子串｝：从串S中的第start个字符开始，抽取len个字符构成一个新的串。其中，参数应满足：1≤start≤LENGTH(S)且1≤len≤LENGTH(S)－start＋1。CONCAT(S1,S2)｛连接｝：将S2的串值紧接着放在S2串值的末尾而组成一个新的串，新的串值名为S1。INDEX(S1,S2)｛定位｝：若在主串S1中存在与S2相等的子串，则函数返回S1中第一个与S2相等的子串在主串S1中的位置，否则函数值返回为0。REPLACE(S1,S2,S3)｛替换｝：该函数完成一个置换操作，操作结构是用串S3替换S1中所有与串S2相等且不重叠的子串。－数

据

结

构软件技术基础87串串的存储结构顺序结构顺序存储结构是用一块地址连续的存储单元存储串的字符序列。为节省存储空间，顺序存储结构存储串值时允许采用紧缩格式，即一个字节存放一个字符，把一个字存储单元中放一个字符称为非紧缩格式。显然，非紧缩格式浪费存储空间，但操作方便；紧缩格式节省存储空间，但若要分离某一部分字符时，操作比较麻烦。通常系统在存储串值时自动在串值的末尾处添加一特殊符号作为当前串值的结束标记。在c语言中串值结束标记采用转义字符‘\0’。－数

据

结

构软件技术基础#defineMAXNUM80typedefstruct{charstr[MAXNUM];intlen;}strtype;

88串串的存储结构链式存储结构－数

据

结

构软件技术基础typedefstructnode{chardata;structnode*next;}node;

S=‘student’;student\0^s89串串的存储结构顺序结构链式存储结构－数

据

结

构软件技术基础901.3非线性结构树结构图结构－数

据

结

构软件技术基础非线性结构的逻辑特征是一个结点元素可能有多个直接前趋和多个直接后继。最主要的非线性结构91

树结构是结点元素之间有分支、层次关系的结构。定义定义：树(tree)是n(n>0)个结点的有限集T，其中：有且仅有一个特定的结点，称为树的根(root)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)特点：树中至少有一个结点——根树中各子树是互不相交的集合树结构及其基本概念－数

据

结

构软件技术基础ACDBEFGHIJ92基本术语树结构及其基本概念－数

据

结

构软件技术基础EACDBFGHIJ父结点(parents)相对于某结点子树的根，称该结点为子树根的父结点。子结点(child)某结点子树的根称为该结点的子结点。树的度树中各结点的度的最大值称为该树的度。结点的度(degree)一个结点的子树数目就称为该结点的度。分支结点非叶子结点称为分支结点(或非终端结点)。叶子(leaf)没有后继的结点称为叶子（或终端结点）。degree=2degree=3degree=093基本术语－数

据

结

构软件技术基础EACDBFGHIJ森林(forest)森林是n棵树的集合(n≥0)。任何一棵树，删去根结点，树就变成了森林。有序树和无序树如果一棵树中结点的各子树从左到右是有序的，即若交换了某结点各子树的相对位置，则构成了不同的树，称这棵树为有序树，反之，则为无序树。树的深度(depth)一棵树中，结点的最大层次值就是树的深度。结点的层次(level)根结点的层次为1，其他任何的层数等于它的父结点的层数加1。兄弟(sibling)具有同一父结点的子结点称为兄弟。第一层第二层第三层第四层94二叉树结构二叉树的基本概念定义：二叉树是n个结点的有限集合(n≥0)；这个集合可以是空(即n＝0)，此时称为空二叉树；或者由一个根结点和两棵互不相交的被称为根的左子树和右子树组成。左子树和右子树分别又是一棵二叉树。特点每个结点至多有二棵子树(即不存在度大于2的结点)二叉树的子树有左、右之分，且其次序不能任意颠倒树至少应有一个节点，而二叉树可以是空－数

据

结

构软件技术基础95二叉树结构二叉树的基本概念基本形态－数

据

结

构软件技术基础A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空96二叉树结构几种特殊形式的二叉树满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称为满二叉树。－数

据

结

构软件技术基础ABCDEFGHIJKLMNO12345678910111213141597二叉树结构几种特殊形式的二叉树完全二叉树若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。－数

据

结

构软件技术基础ABCDEFGHIJKL98二叉树结构几种特殊形式的二叉树二叉排序树它或者是空二叉树，或者是具有如下性质的二叉树：左子树上所有结点的关键字均小于根结点的关键字；右子树上所有结点的关键字均大于等于根结点的关键字。左子树和右子树本身又各是一棵二叉排序树。－数

据

结

构软件技术基础84101491761299二叉树结构二叉树的存储结构顺序存储结构

对于满二叉树和完全二叉树，其节点的逻辑关系符合如下特征：对于有n个结点的满二叉树和完全二叉树，如果从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号，则对于任意序号i的结点有：（1）如果i＞1，则序号为i的结点的父结点的序号为i/2（取整）；如果i＝1，则结点是根结点，无父结点。（2）如果2i≤n，则序号为i的结点的左子结点的序号为2i。（3）如果2i＋1≤n，则序号为i的结点的右子结点的序号为2i＋1。

显然，满二叉树和完全二叉树中结点的序号可以唯一地反应出结点之间的逻辑关系。所以可以用顺序存储方式按从上到下，从左到右的顺序存储树中所有结点的数据信息。实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素－数

据

结

构软件技术基础100二叉树结构二叉树的存储结构顺序存储结构特点：结点间关系蕴含在其存储位置中浪费空间，适于存满二叉树和完全二叉树－数

据

结

构软件技术基础abcde0000fg012345678910abcdefg101二叉树结构二叉树的存储结构链式存储结构－数

据

结

构软件技术基础

数据域右指针域：指向结点的右子树根左指针域：指向结点的左子树根LCDataRC

二叉链表

三叉链表LCDataRCParenttypedefstructbtreenode{elemtypedata;structbtreenode*LC,*RC;}bnode;typedefstructtnode{elemtypedata;structtnode*LC,*RC,*parent;}tnode;102二叉树结构二叉树的存储结构链式存储结构－数

据

结

构软件技术基础ABCDEFG^^^^^^^^

二叉链表ABCDEFG103二叉树结构二叉树的遍历树遍历的含义是指用一定的规律走遍树的每一个结点，使每个结点被访问一次而且只被访问一次。访问该结点时，可对该结点进行操作。方法先序遍历（DLR）：先访问根结点，然后分别先序遍历左子树、右子树中序遍历（LDR）：先中序遍历左子树，然后访问根结点，最后中序遍历右子树后序遍历（LRD）：先后序遍历左、右子树，然后访问根结点－数

据

结

构软件技术基础104二叉树结构二叉树的遍历先序遍历－数

据

结

构软件技术基础ADBCDLRADLRDLR>B>>D>>CDLR先序遍历序列：ABDC105二叉树结构二叉树的遍历中序遍历－数

据

结

构软件技术基础ADBCLDRBLDRLDR>A>>D>>CLDR中序遍历序列：BDAC106二叉树结构二叉树的遍历后序遍历－数

据

结

构软件技术基础ADBCLRDLRDLRD>A>>D>>CLRD后序遍历序列：DBCAB107二叉树结构二叉树先序遍历算法〖算法19〗

－数

据

结

构软件技术基础voidpreorder(bnode*BT){if(BT==NULL)return;else{visite(BT);//访问BT指向的根结点

if(BT->LC!=NULL)preorder(BT->LC);if(BT->RC!=NULL)preorder(BT->RC);}}108二叉树结构二叉树中序遍历算法〖算法20〗

－数

据

结

构软件技术基础voidinorder(bnode*BT){if(BT==NULL)return;else{if(BT->LC!=NULL)inorder(BT->LC);visite(BT);//访问BT指向的根结点

if(BT->RC!=NULL)inorder(BT->RC);}}109二叉树结构二叉树后序遍历算