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

软件技术基础软件技术基础数据结构一、数据结构的基本概念现实事物如气候、人信息（表征现实事物）如气温、姓名数据（信息的载体）如25ºC、张三数据结构（数据在计算机中的存储形式及相互关系）注意：数据≠数值65706667960131王五585928893960131李四487908891960131张三390968180960131马二284969097960131丁一1C语言电路分析物理数学班级姓名学号学生成绩表数据结构举例每一行为一个数据元素，也称为数据结点或记录每一列为一个数据项或称为字段数据元素的C语言类型可定义如下:typedefstructstudent{intid;charname[20];intclasses;floatscore[4];}elemtype;可以用该类型来定义数据元素变量:elemtypestu1,stu2,stu3;此表中每个数据元素占用40个字节的存储空间。思考：这张二维表格是否可以用一个二维数组来实现？数据结构的三个层次数据的逻辑结构——面向用户(1)线性结构有且仅有一个起点数据元素和一个终点数据元素，每个数据元素最多有一个直接前驱和一个直接后继。马二丁一直接前驱张三直接后继前面提到的学生成绩表就属于线性结构！(2)非线性结构一个数据元素可以有多个直接前驱和多个直接后继，如树结构、图结构。丁一马二张三李四图结构大学英语高等数学大学物理操作系统微机原理选课情况电子科技大学通信学院计算机学院自动化学院专业1专业2专业1专业1专业2专业3树结构机构设置数据的存储结构——面向机器(1)顺序存储将逻辑上相邻的数据元素按顺序存储在物理上相邻的存储单元。马二丁一张三李四……2000H内存地址内存2028H2050H2078H首地址(2)链接存储不要求元素按逻辑顺序存储，每个元素含有指针字段，并指向逻辑上相邻的元素的物理存储位置。李四马二丁一……2000H内存地址内存2028H2050H2078H20a0H张三2000H20c8H20c8H2028H……首地址(3)索引存储需要建立一个索引表，表中有两项：关键字和地址，指明了每个元素的物理存储位置。索引表首地址李四马二丁一……2000H内存地址内存2028H2050H2078H20a0H张三20c8H20f0H……2028H42000H320f0H22078H1地址学号索引表即能够区分每个数据元素、具有唯一性的数据项。(4)散列存储基本思想是：通过一个设计好的散列函数f(x)，将元素的关键字作为自变量代入该函数，得到的结果就作为该元素的物理存储地址，这种方法也称为地址转移法。)(数据元素的关键字数据元素的存储地址＝f数据的操作集合就是对数据进行处理和运算等操作，主要有：（1）遍历（2）插入（3）更新（4）删除（5）查找（6）排序二、线性结构线性表的基本操作主要有：（1）初始化：建立一个空的初始线性表。（2）求表长：求线性表中元素的个数。（3）取元素：获取给定序号的数据元素的值或首地址。（4）定位：查找等于给定值的数据元素的序号。（5）插入：在给定序号的位置上插入一个新的数据元素。（6）删除：删除给定序号的数据元素。1.线性表线性表是n(n≥0)个相同类型的元素构成的有限的线性序列，线性表的长度为n。(1)顺序表即采用顺序存储方式的线性表，数据元素在物理上按逻辑顺序进行存储，整个表占用一组地址连续的存储单元。马二丁一张三李四……2000H内存地址内存2028H2050H2078H首地址数组是计算机中采用顺序存储的一种数据结构，因此，顺序表可采用数组来实现。数组元素[i]的地址＝数组首地址+i×数据元素字节数可见，顺序表是一种随机存取结构。顺序表的C语言实现顺序表的结构类型定义typedefstructlist_type{elemtypedata[MAXNUM];intnum;}listtype;已定义的数据元素类型事先定义的字符常量，表示顺序表的最大长度表示顺序表的当前长度则可以用此类型来定义一个结构体变量：listtypelist;此变量存放的就是一个顺序表顺序表的操作函数定义初始化函数：voidinitiatelist(listtype*l){l-num=0;}将顺序表当前长度置0，表示为空表指向顺序表的首地址，即l=&list数据元素插入函数：（在给定序号位置插入一个新元素）intinsert(listtype*l,inti,elemtypex){intj;if(l-num=MAXNUM){printf(thelistisfull,cannotinsert.);return(0);}if((i0)||(il-num)){printf(iisinvalidvalue!);return(0);}for(j=l-num-1;j=i;j--)l-data[j+1]=l-data[j];l-data[i]=x;l-num++；return(1);}指向顺序表的首地址，即l=&list新的数据元素插入的位置新的数据元素注意：由于顺序表采用数组来实现，因此顺序表的元素序号从0开始。数据元素后移待移动元素的序号判断表是否已满？判断插入序号的有效性放入新元素值线性表长度加1数据元素删除函数：（删除给定序号的元素）intdelete(listtype*l,inti){intj;if((i0)||(il-num-1)){printf(Notexist);return(0);}for(j=i+1;jl-num;j++)l-data[j-1]=l-data[j];l-num--;return(1);}数据元素前移指向顺序表的首地址，即l=&list待删除的元素的序号待移动元素的序号判断删除序号的有效性线性表长度减1顺序表的优点具有随机存取特性，与元素位置无关，对每个数据元素的存和取操作都很快。顺序表的缺点插入和删除操作都比较费时，时间主要花费在移动数据元素上。另外，需要按照顺序表的最大长度预先分配存储空间，降低了存储器的利用率。(2)线性链表即采用链接存储方式的线性表，数据结点无须按逻辑顺序进行存储，而是通过指针链接起来。李四马二丁一……2000H内存地址内存2028H2050H2078H20a0H张三2000H20c8H20c8H2028H……首地址①单向链表是链表中最简单、最基本的，每个结点只有一个指向下一个结点的指针，可以实现从前向后的单向查找。每个数据结点由两部分组成：nextdata数据域（当前结点的内容）指针域（下一个结点的地址）单链表的第一个结点的地址放在一个指针变量（称为头指针）中，可以用头指针的名字来命名单链表。通常在单链表的第一个结点前加一个头结点，以便将空表和非空表的操作统一起来。^datadata^data…a1头结点a2an头指针单链表的C语言实现单链表的结点类型定义structnode{elemtypedata;structnode*next;};已定义的数据结点类型存放下一个数据结点的地址单链表的操作函数定义初始化函数：（创建一个带头结点的空表）voidinitiatelist(structnode**h){*h=(structnode*)malloc(sizeof(structnode));(*h)-next=NULL;}分配指定字节数的存储空间，并返回其首地址指向单链表的头指针变量（指向一级指针变量的为二级指针变量）求某数据类型的字节长度事先定义的字符常量，一般为0。h*h头结点头指针^告知系统该存储空间按照什么类型来使用数据结点插入函数：（在给定序号位置插入一个新的数据结点）voidinsertsl(structnode*h,inti,elemtypex){structnode*p,*t;intj;p=h;j=0;while(p-next!=NULL&&ji-1){p=p-next;j++;}if(j!=i-1){printf(iisinvalid);return};t=(structnode*)malloc(sizeof(structnode));t-data=x;t-next=p-next;p-next=t;}新数据结点插入的序号指向单链表的头结点新数据结点的data成员的值注意：链表的结点序号从1开始。查找到的结点的序号指向查找到的结点的地址指向新结点的地址判断循环结束时j是否不等于i-1创建一个新的结点放入新结点的data成员的值新结点的next成员指向第i个结点第i-1个结点的next成员指向新结点p若指到最后一个结点时就退出循环p指向下一个结点j若加到i-1时就退出循环查找第i-1个结点，即p指到第i-1个结点，j加到i-1从头结点开始查找数据结点删除函数：（删除给定序号的数据结点）voiddeletesl(structnode*h,inti){structnode*p,*s;intj;p=h;j=0;while(p-next!=NULL&&ji-1){p=p-next;j++;}if(p-next==NULL||j!=i-1){printf(iisinvalid);return;}s=p-next;p-next=s-next;free(s);}待删除的数据结点的序号指向单链表的头结点释放指定地址的存储空间指向查找到的结点的地址指向待删除结点的地址查找到的结点的序号查找第i-1个结点，即p指到第i-1个结点，j加到i-1判断循环结束时p是否指到最后一个结点或j是否不等于i-1保存待删除结点的地址第i-1个结点的next成员指向第i+1个结点的地址p若指到最后一个结点时就退出循环p指向下一个结点j若加到i-1时就退出循环从头结点开始查找数据结点访问函数：（取给定序号的数据结点的值）elemtypeaccess(structnode*h,inti){structnode*p;intj;p=h;j=0;while(p-next!=NULL&&ji){p=p-next;j++;}if(j==i)return(p-data);elsereturn(NULL);}待访问的数据结点的序号指向单链表的头结点查找第i个结点，即p指到第i个结点，j加到i指向查找到的结点的地址查找到的结点的序号p若指到最后一个结点时就退出循环p指向下一个结点返回第i个结点的data成员的值判断循环结束时j是否为ij若加到i时就退出循环从头结点开始查找②双向链表即每个结点有两个指针，分别指向前一个和后一个结点，可实现双向查找。每个数据结点由三部分组成：双链表和单链表类似，都有一个头指针和头结点。nextdata数据域（当前结点的内容）后指针域（后一个结点的地址）prior前指针域（前一个结点的地址）^a1头指针dataa2头结点an^……datadata在双链表中，若p是指向表中某一个结点的指针变量，则有p-next-prior=pp-prior-next=pdataai2078H2301Hdataai-1…2012Hdataai+12012H…2012Hp2078H2012H2301H双链表的C语言实现双链表的结点类型定义structnode{elemtypedata;structnode*prior,*next;};已定义的数据结点类型存放后一个数据结点的地址存放前一个数据结点的地址双链表的操作函数定义初始化函数：（创建一个带头结点的空表）voidinitiatelist(structnode**h){*h=(structnode*)malloc(sizeof(structnode));(*h)-prior=NULL;(*h)-next=NULL;}分配指定字节数的存储空间，并返回其首地址指向双链表的头指针变量求某数据类型占用的字节数h*h头指针^头结点^数据结点插入函数：（在给定序号位置插入一个新的数据结点，不适用于空表）voidinsert(structnode*p,elemtypex){structnode*t;t=(structnode*