第五章机械CAD中常用的数据结构

第五章机械CAD中常用的数据结构学习内容：CAD中数据结构线性表栈树二叉树5.1基本概念在数据处理中，现实世界－－－－→信息世界－－－→数据世界。包含几个层次概念：个体特征总体事物及其联系现实世界实体属性实体集实体及其联系信息世界记录数据项文件数据组织（数据文件、数据库）计算机世界5.1基本概念1.数据的逻辑结构定义：数据的逻辑结构描述的是数据之间的逻辑关系、它从客观的角度组织和表达数据。2.数据的物理结构定义:是指数据在计算机内部的存储方式，它从物理存储的角度来描述数据以及数据间的关系。5.2线性表•线性表是一个由n（n≥0）个数据元素a1,a2,a3...an组成的有限序列，表中的每一个数据元素，除了第一个和最后一个，仅有一个直接前驱和直接后继。线性表中数据元素的个数定义为线性表的长度。当n=0，称为空表。•例如：光轴轴径系列值表示成线性表形式：（3，6，10，14，18，...）5.2线性表1.线性表的逻辑结构5.2线性表•2.线性表的物理结构•（1）顺序存储•（2）链式存储•1）单向链•2）双向链•3）多向链5.2线性表（1）线性表的顺序存储结构定义:利用一组地址连续的存储单元依次存放各数据元素。特点：1）有序性2）均匀性5.2线性表•线性表顺序存储结构的运算：•（1）建表•staticcharlistc[6]={‘A’,’B’,’C’,’D’,’E’};•（2）访问•charc;•C=listc[2];•（3）修改•listc[2]=‘T’;•（4）删除•（5）插入5.2线性表特点：1）存储单元少，简单易行，结构紧凑。2）数据结构缺乏柔性，若要增删数据，必须重新分配存储单元。应用：查询频繁，修改、补充、删除数据量小的场合。5.2线性表•（2）线性表的链式存储结构用一组任意的存储单元存储数据元素(这组存储单元可以是连续的，也可以是不连续的)。信息字段结构形式：一个数据元素项由两个字段组成信息字段（INFO）和指针字段(POINT)指针字段信息字段存放数据元素本身的域指针字段存放直接后继或直接前驱的域称为指针域(point)。指针域中存储的信息称作指针。5.2线性表存储结构可独立于逻辑结构。存储的物理顺序不必与逻辑顺序一致而仍能按逻辑要求存取数据。特点：链式存储结构在不改变原来存储结构的条件下，增删记录十分方便，只要控制指针即可。根据指针的数目，链式存储结构有三种类型：单向链结构双向链结构多向链结构5.2线性表正向链：连接方向与逻辑顺序相同反向链：连接方向与逻辑顺序相反R1R2R3R4R5反向链单向链结构各个数据元素由一个指针域和一个数据域组成，通过指针构成一个链状结构，且链接方向单一。R1R2R3R4R5-个简单的单向链表的图示datanext头指针headdatanext尾指针NULL5.2线性表1）．链表是结构、指针相结合的-种应用,它是由头、中间、尾多个链环组成的单方向可伸缩的链表,链表上的链环我们称之为结点。2）．每个结点的数据可用-个结构体表示,该结构体由两部分成员组成：数据成员与结构指针变量成员。3）．数据成员存放用户所需数据,而结构指针变量成员则用来连接(指向)下-个结点,由于每-个结构指针变量成员都指向相同的结构体,所以该指针变量称为结构指针变量。5.2线性表4）．链表的长度是动态的,当需要建立-个结点,就向系统申请动态分配-个存储空间,如此不断地有新结点产生,直到结构指针变量指向为空(NULL)。申请动态分配-个存储空间的表示形式为：(structnode*)malloc(sizeof(structnode))5.2线性表在链表建立过程中,首先要建立第-个结点,然后不断地在其尾部增加新结点,直到不需再有新结点,即尾指针指向NULL为止。设有结构指针变量structnode*p,*p1,*head;head:用来标志链表头；p:在链表建立过程中,p总是不断先接受系统动态分配的新结点地址。p1-next：存储新结点的地址。链表的建立链表建立的步骤：第-步：建立第-个结点structnode{intdata;structnode*next;};structnode*p,*p1,*head;head=p1=p=(structnode*)malloc(sizeof(structnode);datanextheadp,p1第-结点第二步：给第-个结点成员data赋值并产生第二个结点scanf(“%d”,&p-data);/*输入10*/p=(structnode*)malloc(sizeof(structnode);datanextnext10第-结点第二结点headp1p链表建立的步骤：第三步：将第-个结点与第二个结点连接起来p1-＞next=p;10nextnextdata第-结点第二结点headp1p链表建立的步骤：第四步：产生第三个结点p1=p;scanf(“%d”,&p-data);/*输入8*/p=(structnode*)malloc(sizeof(structnode);以后步骤都是重复第三、四步,直到给出-个结束条件,不再建新的结点时,要有p-next＝NULL；它表示尾结点。链表建立的步骤：[例1]建立链表#includestdio.h#includemalloc.h#defineLENsizeof(structnode)structnode{intdata；structnode*next；}；main(){structnode*p,*p1,*head；head＝p＝(structnode*)malloc(LEN)；scanf(“％d”,&p-data)；/*头结点的数据成员*/while(p-data!＝0)/*给出0结束条件,退出循环*/{p1＝p；p＝(structnode*)malloc(LEN)；scanf(”％d”,&p-data)；/*中间结点数据成员*/p1-next=p；/*中间结点的指针成员值*/}p-next＝NULL；/*尾结点的指针成员值*/……}为了证实已建链表是所需要的，应在上程序的省略处加入下列程序段：p＝head；／*链表显示*／printf(”链表数据成员是：”)；while(p-next!=NULL){printf(”％d”，p-data)；p＝p-next；}printf(”％d＼n”，p-data)；【结果】1086420／*建链表时输入的数据*／链表数据成员是：1086420／*显示所建的链表*／ai-1//插入数据元素ListInsert(&L,i,e),第i个节点前插入数据e在单链表中的实现：有序对ai-1,ai改变为ai-1,e和e,aieaiai-1链表插入因此，在单链表中第i个结点之前进行插入的基本操作为:找到线性表中第i-1个结点，然后修改其指向后继的指针。可见，在链表中插入结点只需要修改指针。但同时，若要在第i个结点之前插入元素，修改的是第i-1个结点的指针。链表插入intListInsert_L(NODE*head,inti,inte){}//LinstInsert_Lelse{……}NODE*p,*s;intj;p=head;j=0;while(p&&ji-1){p=p-next;j++;}if(!p||ji-1)return0;p=head-next,如何修改程序？j=1时，如何修改程序链表插入s=(NODE*malloc(sizeof(NODE));//生成新结点if(s==NULL)return0;s-data=e;s-next=p-next;p-next=s;//插入return1;eai-1aiai-1sp链表插入链表结点的插入意味着要在某结点前或后插入-个或多个结点，所插入的结点必须(1)动态分配地址p2＝(structnode*)malloc(LEN)；(指针变量p2指向该地址);(2)将原链表插入处,后结点p-next取出,存放在指针变量p3中即p3＝p-next;(3)将新结点的地址赋给而原插入处前结点的p-next即p-next＝p2(4)而原插入处后结点的地址值(p3)赋给新结点的p2-next即p2-next＝p3注意(1)本节仅描述在某结点前插入，若想在某结点之后插入，怎么做？？。(2)在插入操作中，多增加了两个结构指针变量p2、p3。链表结点的插入[例2]在链表中插入新结点的程序段。p＝head；while(p!=NULL){if(p-data==8){p3＝p-next；p2＝(structnode*)malloc(LEN)；scanf(”％d”，&p2-data)；p2-next＝p3；p-next=p2；}}链表插入//删除数据元素ListDelete(&L,i,&e)在链表中的实现:有序对ai-1,ai和ai,ai+1改变为ai-1,ai+1ai-1aiai+1ai-1链表结点删除在单链表中删除第i个结点的基本操作为:找到线性表中第i-1个结点，修改其指向后继的指针。ai-1aiai+1ai-1q=p-next;p-next=q-next;e=q-data;delete(q);pq链表结点删除intListDelete_L(NODE*head,inti,int*e){//删除以head为头指针(带头结点)的单链表中第i个结点}//ListDelete_LNODE*p=head;intj=0;while(p-next&&ji-1){p=p-next;j++;}//寻找第i-1个结点，q=p-next;p-next=q-next；e=q-data;free（q）;//删除并释放结点return1;if(!(p-next)||ji-1)return0;//删除位置不合理双向链结构5.2线性表单链表的每个结点再增加一个指向其前趋的指针域prior，这样形成的链表有两条不同方向的链，称之为双（向）链表。特点：双链表一般也由头指针head唯一确定。每一结点均有：数据域（data)左链域（prior)指向前趋结点.右链域（next)指向后继。是一种对称结构（既有前趋，又有后继）。L•双链表的结点类型描述Typedefstruct{ElemTypedata;//数据域structDuLNode*prior;//前向指针域structDuLNode*next;//后向指针域}DuLNode,*DuLinkList;DuLinkListL,p;L空双向链表Initlist(intn){inti;DuLNode*p,*q;head=(DuLNode*)malloc(sizeof(DuLNode));q=head;//q指向头节点q-prior=NULLfor(i=1;i=n;i++){p=(NODE*)malloc(sizeof(NODE));//p指向新生成的新结点scanf(%d,&p-data);q-next=p;p-prior=q;q=p;//将p指向的结点连在链表的尾端}q-next=NULL;//链表的尾端}•双向链建立双向链表的插入•在结点p后面插入一个新结点s头结点^psq•引入一个指针q•q=p-next•s-next=q•q-prior=s•p-next=s•s-prior=p不引入指针s-next=p-nextp-next-prior=s;p-next=s;s-prior=p双向链表的删除L•双向链表中删除第i个数据元素StatusDuListDelete_L(DuLinkList&L,inti,ElemType&e){if(!(p=GetElemP_Dul(L,i)))returnERROR;//寻找第i-1个结点，确定第i个结点的指针e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);//释放空间returnOK;}第i个结点p双