数据结构-线性结构非线性结构线性表

数据结构-线性结构非线性结构线性表本课程内容结构数据结构线性结构非线性结构线性表栈队列串数组和广义表顺序表链表循环链表两种存储结构顺序存储链式存储树图二叉树的遍历树和森林哈夫曼树及哈夫曼编码图的存储图的遍历最小生成树拓扑排序和关键路径最短路径排序静态动态内部外部数据结构-线性结构非线性结构线性表全文共63页，当前为第1页。数据结构-线性结构非线性结构线性表2一、问题引入程序实际问题数学模型计算机实际问题中元素的数学抽象建立和解决数学模型的方法算法数据结构+数据结构-线性结构非线性结构线性表全文共63页，当前为第2页。数据结构-线性结构非线性结构线性表定义含义inti;int*p;inta[n];int*p[n];int(*p)[n];intf();int*p();int(*p)();int**p;定义整型变量ip为指向整型数据的指针变量定义含n个元素的整型数组an个指向整型数据的指针变量组成的指针数组pp为指向含n个元素的一维整型数组的指针变量f为返回整型数的函数p为返回指针的函数，该指针指向一个整型数据p为指向函数的指针变量，该函数返回整型数p为指针变量，它指向一个指向整型数据的指针变量指针的数据类型数据结构-线性结构非线性结构线性表全文共63页，当前为第3页。数据结构-线性结构非线性结构线性表C语言+“数据结构”“数据库”=“会武会功”第1章C语言概述：了解该语言程序的格式、构成及基本要求；编程的基本思路和方法；上机调试的基本步骤和方法；注意在书写或输入程序时采用缩进格式。第2章C语言程序设计的初步知识：标识符，基本数据类型及不同之间赋值规律，算术运算符；编辑、编译、链接和运行的过程。第3章顺序结构程序设计：各种类型数据的输入输出方法，格式转换字符；顺序结构；程序设计的一般思路。第4章选择结构程序设计：关系和逻辑运算符及表达式值；if和switch语句；简单的算法。第5章循环结构程序设计：循环含义；while和for和do-while语句；break和continue的作用；算法：如穷举、迭代、递推；自顶向下、逐步求精。第6章数组：一二维的应用；字符数组；数组算法（排序）第7章函数：定义；形参，实参，值传递；调用自定义函数条件及嵌套和递归调用；变量的作用域和存储类别；多文件程序；模块化程序设计。第8章编译的预处理：宏定义；文件包含处理；条件编译。第9章指针：指针变量；数组（字符串）的指针和指向数组（字符串或函数）的指针变量；指向指针的用法。第10章构造数据类型：结构体类型变量、数组、链表的操作，共用体类型；typedef。第11章文件：缓冲文件，文件指针；打开、关闭、读、写文件操作。第12章位运算：使用位运算、某些位的操作。数据结构-线性结构非线性结构线性表全文共63页，当前为第4页。数据结构-线性结构非线性结构线性表上机题P44第9题讲解指导老师：许晓飞数据结构-线性结构非线性结构线性表全文共63页，当前为第5页。数据结构-线性结构非线性结构线性表题面

设有多项式：A(x)=7+3x+9x8+3x15B(x)=5x+6x7-9x8(1)用单链表给出A(x)的存储表示；（2）用单链表给出B(x)的存储表示；（3）以上述两个单链表为基础，通过插入和删除等运算给出A(x)+B(x)的存储表示，其存储空间覆盖A(x)和B(x)的存储空间数据结构-线性结构非线性结构线性表全文共63页，当前为第6页。数据结构-线性结构非线性结构线性表首先，我们自己会做一元多项式的相加：

不失一般性，设有两个一元多项式：P(x)=p0+p1x+p2x2+…+pnxn，Q(x)=q0+q1x+q2x2+…+qmxm(m<n)R(x)=P(x)+Q(x)R(x)由线性表R((p0+q0)，(p1+q1)，(p2+q2)，…，(pm+qm)，…，pn)唯一表示。分步走：第一步，寻找和比较相加项的幂指数（操作条件）；第二步，幂指数相同，系数相加（操作内容）；数据结构-线性结构非线性结构线性表全文共63页，当前为第7页。数据结构-线性结构非线性结构线性表解：首先要解决多项式的表征问题，即在程序中如何表征多项式，如写成：f(x)=p1xe1+p2xe2+p3xe3+…+pnxen

很明显，我们可以把多项式看作是一个线性表，线性表中的数据元素是一个二元组（系数，指数）。用线性表（（p1,e1）,(p2,e2),…(pn,en)）唯一代表一个多项式。其次，是选取顺序表还是链表来存储多项式？如果用户输入的多项式的项数事先无法知道，最好采用链表来存储多项式。再次，程序的主要操作是多项式相加，相加结果存储到新的链表中还是占用原来的链表？

为了操作方便，先采用将相加结果存放到一个新链表中。最后，方便相加，表征多项式的链表应该按照指数降序排列。想一想，降低程序的空间复杂度，两个多项式相加的结果被存放到了一个新的链表中。可以设计一个程序，利用第二个链表存放相加后的结果。减少主函数代码，分项建子函数，“模拟计算机运行”：先主函数，调用子函数。数据结构-线性结构非线性结构线性表全文共63页，当前为第8页。数据结构-线性结构非线性结构线性表一元多项式相加的实质是：

指数不同：是链表的合并。

指数相同：系数相加，和为0，去掉结点，和不为0，修改结点的系数域。算法之一：就在原来两个多项式链表的基础上进行相加，相加后原来两个多项式链表就不在存在。当然再要对原来两个多项式进行其它操作就不允许了。算法之二：对两个多项式链表进行相加，生成一个新的相加后的结果多项式链表，原来两个多项式链表依然存在，不发生任何改变，如果要再对原来两个多项式进行其它操作也不影响。数据结构-线性结构非线性结构线性表全文共63页，当前为第9页。数据结构-线性结构非线性结构线性表怎么表征（（p1,e1）,(p2,e2),…(pn,en)）？

为了正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其直接后继结点的地址(或位置)，称为指针(pointer)或链(link)，这两部分组成了链表中的结点结构，如图2-2所示。链表是通过每个结点的指针域将线性表的n个结点按其逻辑次序链接在一起的。每一个结只包含一个指针域的链表，称为单链表。为操作方便，总是在链表的第一个结点之前附设一个头结点(头指针)head指向第一个结点。头结点的数据域可以不存储任何信息(或链表长度等信息)。datanext图2-2链表结点结构data：数据域，存放结点的值。next：指针域，存放结点的直接后继的地址。数据结构-线性结构非线性结构线性表全文共63页，当前为第10页。数据结构-线性结构非线性结构线性表1

结点的描述与实现

C语言中用带指针的结构体类型来描述typedefstructLnode{ElemTypedata;/*数据域，保存结点的值*/structLnode*next;/*指针域*/}LNode;/*结点的类型*/2结点的实现

结点是通过动态分配和释放来的实现，即需要时分配，不需要时释放。实现时是分别使用C语言提供的标准函数：malloc()，realloc()，sizeof()，free()。数据结构-线性结构非线性结构线性表全文共63页，当前为第11页。数据结构-线性结构非线性结构线性表顺序表还应该有表示线性表的长度属性，所以用结构类型来定义顺序表类型。#defineOK1#defineERROR-1#defineMAX_SIZE100typedefintStatus;typedefintElemType;typedefstructsqlist{ElemTypeElem_array[MAX_SIZE];intlength;}SqList;数据结构-线性结构非线性结构线性表全文共63页，当前为第12页。数据结构-线性结构非线性结构线性表动态分配p=(LNode*)malloc(sizeof(LNode));函数malloc分配了一个类型为LNode的结点变量的空间，并将其首地址放入指针变量p中。动态释放free(p);系统回收由指针变量p所指向的内存区。P必须是最近一次调用malloc函数时的返回值。3最常用的基本操作及其示意图⑴结点的赋值

LNode*p;p=(LNode*)malloc(sizeof(LNode));p->data=20;p->next=NULL;p20NULL数据结构-线性结构非线性结构线性表全文共63页，当前为第13页。数据结构-线性结构非线性结构线性表⑵常见的指针操作①

q=p;pa……操作前pa……q操作后②

q=p->next;bpa……操作前操作后qbpa……③

p=p->next;bpa……操作前操作后pba……④

q->next=p;c…pbqa……操作前操作后qb……ac…p(a)数据结构-线性结构非线性结构线性表全文共63页，当前为第14页。数据结构-线性结构非线性结构线性表⑤

q->next=p->next;(a)xy…pbqa……操作前操作后qb……axy…p操作前ypx……bqa…操作后ypx……bqa…(b)操作前ypx……bqa…操作后ypx……bqa…(b)数据结构-线性结构非线性结构线性表全文共63页，当前为第15页。数据结构-线性结构非线性结构线性表

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat⋀head

图2-3

带头结点的单链表的逻辑状态、物理存储方式单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。例1、线性表L=(bat，cat，eat，fat，hat)其带头结点的单链表的逻辑状态和物理存储方式如图2-3所示。数据结构-线性结构非线性结构线性表全文共63页，当前为第16页。数据结构-线性结构非线性结构线性表正反向建立链表，教材P22页//反向建立链表NODE***(int*a,int*b,intiMax){ NODE*head,*s; inti;//教材原来有一个malloc，是错误的（head=(NODE*)malloc(sizeof(NODE));）

for(***)//循环

{ s=(NODE*)malloc(sizeof(NODE)); s->Ai=a[i]; s->Xp=b[i]; if(i==iMax-1) s->next=NULL; else s->next=head; head=s; } returnhead;}数据结构-线性结构非线性结构线性表全文共63页，当前为第17页。数据结构-线性结构非线性结构线性表数据结构-线性结构非线性结构线性表全文共63页，当前为第18页。数据结构-线性结构非线性结构线性表链表的逻辑结构：对于单链表，无论是哪种操作，只要涉及到钩链(或重新钩链)，如果没有明确给出直接后继，钩链(或重新钩链)的次序必须是“先右后左”。对于单链表，不能象顺序表中那样直接按序号i访问结点，而只能从链表的头结点出发，沿链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。按值查找是在链表中，查找是否有结点值等于给定值key的结点?若有，则返回首次找到的值为key的结点的存储位置；否则返回NULL。查找时从开始结点出发，沿链表逐个将结点的值和给定值key作比较。⑴顺序存储表示的相加线性表的定义typedefstruct{ElemTypea[MAX_SIZE];intlength;}Sqlist;

用顺序表示的相加非常简单。访问第5项可直接访问：L.a[4].coef，

L.a[4].expn(2)

链式存储表示的相加

当采用链式存储表示时，根据结点类型定义，凡是系数为0的项不在链表中出现，从而可以大大减少链表的长度。数据结构-线性结构非线性结构线性表全文共63页，当前为第19页。数据结构-线性结构非线性结构线性表算法1描述Ploy*add_ploy(ploy*La，ploy*Lb)

/*将以La，Lb为头指针表示的一元多项式相加*/{ploy*Lc,*pc,*pa,*pb,*ptr;floatx;Lc=pc=La;pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){pc->next=pa;pc=pa;pa=pa->next;}/*将pa所指的结点合并，pa指向下一个结点*/if(pa->expn>pb->expn){pc->next=pb;pc=pb;pb=pb->next;}/*将pb所指的结点合并，pb指向下一个结点*/数据结构-线性结构非线性结构线性表全文共63页，当前为第20页。数据结构-线性结构非线性结构线性表else{x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)

/*如果系数和为0，删除两个结点*/{ptr=pa;pa=pa->next;free(ptr);ptr=pb;pb=pb->next;free(ptr);}else/*如果系数和不为0，修改其中一个结点的系数域，删除另一个结点*/

{pc->next=pa;pa->coef=x;pc=pa;pa=pa->next;ptr=pb;pb=pb->next;free(pb);}数据结构-线性结构非线性结构线性表全文共63页，当前为第21页。数据结构-线性结构非线性结构线性表}}/*endofwhile*/if(pa==NULL)pc->next=pb;elsepc->next=pa;return(Lc);}数据结构-线性结构非线性结构线性表全文共63页，当前为第22页。数据结构-线性结构非线性结构线性表数据结构-线性结构非线性结构线性表全文共63页，当前为第23页。数据结构-线性结构非线性结构线性表算法2描述Ploy*add_ploy(ploy*La，ploy*Lb)

/*将以La，Lb为头指针表示的一元多项式相加，生成一个新的结果多项式*/{ploy*Lc,*pc,*pa,*pb,*p;floatx;Lc=pc=(ploy*)malloc(sizeof(ploy));pa=La->next;pb=Lb->next;while(pa!=NULL&&pb!=NULL){if(pa->expn<pb->expn){p=(ploy*)malloc(sizeof(ploy));p->coef=pa->coef;p->expn=pa->expn;p->next=NULL;数据结构-线性结构非线性结构线性表全文共63页，当前为第24页。数据结构-线性结构非线性结构线性表

/*生成一个新的结果结点并赋值*/pc->next=p;pc=p;pa=pa->next;}/*生成的结点插入到结果链表的最后，pa指向下一个结点*/if(pa->expn>pb->expn){p=(ploy*)malloc(sizeof(ploy));p->coef=pb->coef;p->expn=pb->expn;p->next=NULL;/*生成一个新的结果结点并赋值*/pc->next=p;pc=p;pb=pb->next;}/*生成的结点插入到结果链表的最后，pb指向下一个结点*/数据结构-线性结构非线性结构线性表全文共63页，当前为第25页。数据结构-线性结构非线性结构线性表if(pa->expn==pb->expn){x=pa->coef+pb->coef;if(abs(x)<=1.0e-6)

/*系数和为0，pa,pb分别直接后继结点*/{pa=pa->next;pb=pb->next;}else/*若系数和不为0，生成的结点插入到结果链表的最后，pa,pb分别直接后继结点*/{p=(ploy*)malloc(sizeof(ploy));p->coef=x;p->expn=pb->expn;p->next=NULL;/*生成一个新的结果结点并赋值*/pc->next=p;pc=p;pa=pa->next;pb=pb->next;数据结构-线性结构非线性结构线性表全文共63页，当前为第26页。数据结构-线性结构非线性结构线性表

}}}/*endofwhile*/if(pb!=NULL)while(pb!=NULL){p=(ploy*)malloc(sizeof(ploy));p->coef=pb->coef;p->expn=pb->expn;p->next=NULL;/*生成一个新的结果结点并赋值*/pc->next=p;pc=p;pb=pb->next;}数据结构-线性结构非线性结构线性表全文共63页，当前为第27页。数据结构-线性结构非线性结构线性表if(pa!=NULL)while(pa!=NULL){p=(ploy*)malloc(sizeof(ploy));p->coef=pb->coef;p->expn=pa->expn;p->next=NULL;/*生成一个新的结果结点并赋值*/pc->next=p;pc=p;pa=pa->next;}return(Lc);}数据结构-线性结构非线性结构线性表全文共63页，当前为第28页。数据结构-线性结构非线性结构线性表数据结构-线性结构非线性结构线性表全文共63页，当前为第29页。数据结构-线性结构非线性结构线性表编程思想准备工作：c语言基础，安装VC6.0,会建立工程文件；具体程序：包括定义变量，设计算法流程，用好软件三大武器：顺序、循环、判断关键技术：创建链表查资料：

数据结构-线性结构非线性结构线性表全文共63页，当前为第30页。数据结构-线性结构非线性结构线性表2.2.2

顺序表的基本操作

顺序存储结构中，很容易实现线性表的一些操作：初始化、赋值、查找、修改、插入、删除、求长度等。以下将对几种主要的操作进行讨论。1顺序线性表初始化

StatusInit_SqList(SqList*L){L->elem_array=(ElemType*)malloc(MAX_SIZE*sizeof(ElemType));if(!L->elem_array)returnERROR;else{L->length=0;returnOK;}}数据结构-线性结构非线性结构线性表全文共63页，当前为第31页。数据结构-线性结构非线性结构线性表2

顺序线性表的插入

在线性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)个位置上插入一个新结点e，使其成为线性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

实现步骤(1)

将线性表L中的第i个至第n个结点后移一个位置。(2)将结点e插入到结点ai-1之后。(3)线性表长度加1。数据结构-线性结构非线性结构线性表全文共63页，当前为第32页。数据结构-线性结构非线性结构线性表准备工作：（1）定义全局变量//nodelink.cpp:Definestheentrypointfortheconsoleapplication.//标准库函数，头文件#include“***.h”#include<***.h>#include“***.h"#defineNA4#defineNB3

structnode{ intAi; //多项式系数

intXp; //多项式幂指数

structnode*next;};typedefstructnodeNODE;数据结构-线性结构非线性结构线性表全文共63页，当前为第33页。数据结构-线性结构非线性结构线性表（2）多项式的单项定义：幂指数和系数//获得幂指数为Xp的节点的系数AiintgetAi(NODE*head,intXp){ NODE*p; boolbFound; intiAi; iAi=0; bFound=false; p=head; while(***==false)//循环

{ if(p->next==NULL)//判断

bFound=true; if(p->Xp==Xp)//判断

{ bFound=true; iAi=p->Ai; } else p=p->next; } returniAi;}数据结构-线性结构非线性结构线性表全文共63页，当前为第34页。数据结构-线性结构非线性结构线性表（3）获取多项式的最大幂指数intgetMaxXp(NODE*head)//获得链表最大的幂指数{ NODE*p; intiMax; iMax=0; if(head!=***)//判断

{ p=head; iMax=p->Xp; while(p->next!=NULL)//循环

{ p=p->next; if(iMax<p->Xp) iMax=p->Xp; } } returniMax;}数据结构-线性结构非线性结构线性表全文共63页，当前为第35页。数据结构-线性结构非线性结构线性表（4）反向建立链表//反向建立链表NODE***(int*a,int*b,intiMax){ NODE*head,*s; inti;//教材原来有一个malloc，是错误的（head=(NODE*)malloc(sizeof(NODE));）

for(***)//循环

{ s=(NODE*)malloc(sizeof(NODE)); s->Ai=a[i]; s->Xp=b[i]; if(i==iMax-1) s->next=NULL; else s->next=head; head=s; } returnhead;}数据结构-线性结构非线性结构线性表全文共63页，当前为第36页。数据结构-线性结构非线性结构线性表（5）删除链表的最后一个节点//删除链表的最后一个节点voiddeleteLastNode(NODE*head){ NODE*p,*s; s=NULL; p=NULL; if(head!=NULL)//判断

{ p=head; while(p->next!=NULL)//循环

{ s=p; p=p->next; } free(p); if(***!=NULL) s->next=NULL; else head=NULL; }}数据结构-线性结构非线性结构线性表全文共63页，当前为第37页。数据结构-线性结构非线性结构线性表（6）显示链表的系数和幂指数//显示链表的系数和幂指数voiddisplayNode(NODE*head){ NODE*p; inti; i=0; if(head!=NULL)//判断

{ p=head; while(p->next!=NULL)//循环

{ printf("Ai(%d)=%dXp=%d\n",i,p->Ai,p->Xp); p=p->next; i=i+1; } //displaylastonenode printf("Ai(%d)=%dXp=%d\n",i,p->Ai,p->Xp); }}数据结构-线性结构非线性结构线性表全文共63页，当前为第38页。数据结构-线性结构非线性结构线性表主函数：（1）顺序+创建函数intmain(intargc,char*argv[]){ intA_Ai[NA]; intA_Xp[NA]; intB_Ai[NB]; intB_Xp[NB]; intC_Ai[NB+NA];//合并后的多项式最多有NA+NB项

intC_Xp[NB+NA]; intc_Max;//记录合并后的多项式的有效项的最大数目

inti; intiMaxXp; inti_ai; inti_bi;

NODE*A_Link; NODE*B_Link; NODE*C_Link; 数据结构-线性结构非线性结构线性表全文共63页，当前为第39页。数据结构-线性结构非线性结构线性表//初始化变量

iMaxXp=0; A_Link=NULL; B_Link=NULL; C_Link=NULL; A_Ai[0]=7; A_Ai[1]=3; A_Ai[2]=-9; A_Ai[3]=3; A_Xp[0]=0; A_Xp[1]=1; A_Xp[2]=8; A_Xp[3]=16;

B_Ai[0]=5; B_Ai[1]=9; B_Ai[2]=-12; B_Xp[0]=1; B_Xp[1]=8; B_Xp[2]=12;

//建立链表A并显示

A_Link=***(A_Ai,A_Xp,NA); printf("displayLinkAinformation!\n"); displayNode(A_Link); printf("\n"); printf("\n");//建立链表B并显示

B_Link=***(B_Ai,B_Xp,NB); printf("displayLinkBinformation!\n"); displayNode(B_Link);数据结构-线性结构非线性结构线性表全文共63页，当前为第40页。数据结构-线性结构非线性结构线性表（2）开始计算两个多项式的和

//开始计算两个多项式的和

//初始化C_Ai和C_Xp for(i=0;i<NA+NB;i++) { C_Ai[i]=0; C_Xp[i]=0; } //找出两个多项式最大的幂指数

printf("\n"); printf("\n"); iMaxXp=getMaxXp(A_Link); i=getMaxXp(B_Link); 数据结构-线性结构非线性结构线性表全文共63页，当前为第41页。数据结构-线性结构非线性结构线性表接上个程序段if(iMaxXp<i) iMaxXp=i; printf("\n"); printf("\n"); printf("MaxXp=%d\n",iMaxXp); c_Max=0; for(i=0;i<=iMaxXp;i++)//循环

{ i_ai=getAi(A_Link,i); i_bi=getAi(B_Link,i); if((i_ai+i_bi)!=0) { C_Ai[c_Max]=i_ai+i_bi; C_Xp[c_Max]=i; c_Max=c_Max+1; i_ai=0; i_bi=0; }}数据结构-线性结构非线性结构线性表全文共63页，当前为第42页。数据结构-线性结构非线性结构线性表（3）显示多项式求和的结果 //建立链表C并显示

C_Link=***(C_Ai,C_Xp,c_Max); printf("\n"); printf("\n"); printf("displayLinkCinformation!\n"); displayNode(C_Link);//退出前清理好已经分配的内存，不然程序运行几次后，电脑内存被占满，有可能直接死机！

i=0; while(A_Link!=NULL&&i<NA)//循环

{ deleteLastNode(A_Link); i=i+1; } i=0; while(B_Link!=NULL&&i<NB)//循环

{ deleteLastNode(B_Link); i=i+1; } i=0;

数据结构-线性结构非线性结构线性表全文共63页，当前为第43页。数据结构-线性结构非线性结构线性表接上个程序段while(C_Link!=NULL&&i<c_Max)//循环

{ deleteLastNode(C_Link); i=i+1; } printf("\n"); printf("\n"); printf("OK,GameisOver!\n"); return0;}数据结构-线性结构非线性结构线性表全文共63页，当前为第44页。数据结构-线性结构非线性结构线性表程序运行结果：数据结构-线性结构非线性结构线性表全文共63页，当前为第45页。数据结构-线性结构非线性结构线性表作业：1.画出上述程序算法的流程图；2.补充完整程序代码；3.编译运行出正确结果；4.请改动程序，使得最后输出结果形式有所变化；5.另写出创新的算法，加分。6.编写和运行程序过程，有错误需记录下来，改好了的方法和找到原因需记录，越多越有价值的，加分；7.另外，下学期有两门选修课，面向对象和数据库，咱们选的同学可以考虑做一个计软程序调试故障诊断系统。数据结构-线性结构非线性结构线性表全文共63页，当前为第46页。数据结构-线性结构非线性结构线性表如这样的错误提示：--------------------Configuration:

yanghui

-

Win32

Debug--------------------

Compiling...

yanghui.cpp

Linking...

yanghui.obj

:

error

LNK2005:

_main

already

defined

in

y2.obj

Debug/yanghui.exe

:

fatal

error

LNK1169:

one

or

more

multiply

defined

symbols

found

执行

link.exe

时出错.

yanghui.exe

-

1

error(s),

0

warning(s)数据结构-线性结构非线性结构线性表全文共63页，当前为第47页。数据结构-线性结构非线性结构线性表程序运行出现的错误集序号错误原文错误分类错误原因错误改法

备注数据结构-线性结构非线性结构线性表全文共63页，当前为第48页。数据结构-线性结构非线性结构线性表

数据结构(DataStructure)：是指相互之间具有(存在)一定联系(关系)的数据元素的集合。元素之间的相互联系(关系)称为逻辑结构。数据元素之间的逻辑结构有四种基本类型，如下所示。①集合：结构中的数据元素除了“同属于一个集合”外，没有其它关系。②线性结构：结构中的数据元素之间存在一对一的关系。③树型结构：结构中的数据元素之间存在一对多的关系。④图状结构或网状结构：结构中的数据元素之间存在多对多的关系。数据结构-线性结构非线性结构线性表全文共63页，当前为第49页。数据结构-线性结构非线性结构线性表

数据结构的形式定义是一个二元组：

Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集。例2：设数据逻辑结构B=（K，R）

K={k1,k2,…,k9}R={<k1,k3>，<k1,k8>，<k2,k3>，<k2,k4>，<k2,k5>，<k3,k9>，<k5,k6>，<k8,k9>，<k9,k7>，<k4,k7>，<k4,k6>}

画出这逻辑结构的图示，并确定那些是起点，那些是终点四类基本结构图数据结构-线性结构非线性结构线性表全文共63页，当前为第50页。数据结构-线性结构非线性结构线性表数据结构的存储方式

数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。

数据结构在计算机内存中的存储包括数据元素的存储和元素之间的关系的表示。元素之间的关系在计算机中有两种不同的表示方法：顺序表示和非顺序表示。由此得出两种不同的存储结构：顺序存储结构和链式存储结构。顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。数据结构-线性结构非线性结构线性表全文共63页，当前为第51页。数据结构-线性结构非线性结构线性表

链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer)，用该指针来表示数据元素之间的逻辑结构(关系)。例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0}，两种不同的存储结构。顺序结构：数据元素存放的地址是连续的；

链式结构：数据元素存放的地址是否连续没有要求。

数据的逻辑结构和物理结构是密不可分的两个方面，一个算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采用的存储结构。在C语言中，用一维数组表示顺序存储结构；用结构体类型表示链式存储结构。数据结构-线性结构非线性结构线性表全文共63页，当前为第52页。数据结构-线性结构非线性结构线性表数据结构的三个组成部分：逻辑结构：数据元素之间逻辑关系的描述

D_S=（D，S）存储结构：数据元素在计算机中的存储及其逻辑关系的表现称为数据的存储结构或物理结构。数据操作：对数据要进行的运算。本课程中将要讨论的三种逻辑结构及其采用的存储结构。数据结构-线性结构非线性结构线性表全文共63页，当前为第53页。数据结构-线性结构非线性结构线性表数据的逻辑结构非线性结构集合图状结构有向图无向图树形结构一般树二叉树线性结构一般线性表线性表推广广义表数组串受限线性表栈和队列图1-5

数据逻辑结构层次关系图图1-4

逻辑结构与所采用的存储结构线性表树图顺序存储结构链式存储结构复合存储结构逻辑结构物理结构数据结构-线性结构非线性结构线性表全文共63页，当前为第54页。数据结构-线性结构非线性结构线性表

数据结构的主要运算包括：⑴建立(Create)一个数据结构；⑵消除(Destroy)一个数据结构；⑶从一个数据结构中删除(Delete)一个数据元素；⑷把一个数据元素插入(Insert)到一个数据结构中；⑸对一个数据结构进行访问(Access)；⑹对一个数据结构(中的数据元素)进行修改(Modify)；⑺对一个数据结构进行排序(Sort)；⑻对一个数据结构进行查找(Search)。1.1.6

数据结构的运算数据结构-线性结构非线性结构线性表全文共63页，当前为第55页。数据结构-线性结构非线性结构线性表5.数据结构结构是数据元素之间的关系。数据结构是带结构的数据元素的集合。一、基本概念

例如一个12位的十进制数可以用三个4位十进制数表示：3214，6587，9345——a1(3214),a2(6587),a3(9345)在a1,a2,a3之间存在“次序”关系<a1,a2>,<a2,a3>3214,6587,9345≠6587,3214,9345a1a2a3a2a1a3又例二行三列的二维数组{a1,a2,a3,a4,a5,a6}a1a3a5a2a4a6行的次序关系：row={<a1,a2>,<a2,a3>,<a4,a5>,<a5,a6>}列的次序关系：Col={<a1,a4>,<a2,a5>,<a3,a6>}≠a1a2a3a4a5a61.2数据结构的基本概念数据结构-线性结构非线性结构线性表全文共63页，当前为第56页。数据结构-线性结构非线性结构线性表

线性结构是最常用、最简单的一种数据结构。而线性表是一种典型的线性结构。其基本特点是线性表中的数据元素是有序且是有限的。在这种结构中：①存在一个唯一的被称为“第一个”的数据元素；②存在一个唯一的被称为“最后一个”的数据元素；③除第一个元素外，每个元素均有唯一一个直接前驱；④除最后一个元素外，每个元素均有唯一一个直接后