自考数据结构导论--02142第二章-线性表

1第二章线性表2第2章线性表2.1线性表的基本概念2.2线性表的顺序存储2.3线性表的链接存储2.4其它运算在单链表上的实现2.5其它链表2.6顺序实现与连接实现的比较2.7小结34本章总述本章主要讨论了线性表及它的两种存储实现：顺序实现和链接实现；另外，简单介绍了串这种特殊的线性表的运算和存储实现。线性表是一种最简单最常见的数据结构5本章重点线性结构的定义和特点；线性表的运算；顺序表和单链表的组织方法和算法设计。本章难点单链表上的算法设计。6字母表(A,B,C,D….Z)数字表(0,1,2,3,4,5,6,7,8,9)1001张三08信管1班1985.1.12008.9.1xxxxxxxxx1002李四08信管1班1986.2.12008.9.1xxxxxxxxx1003王五08信管1班1986.3.12008.9.1xxxxxxxxx学生名单7问题：线性结构的特点？82.1线性表的基本概念线性表是由n（n≥0）个数据元素（结点）a1，a2，…，an组成的有限序列。①数据元素的个数n定义为表的长度,n=0时称为空表，记作（）或②将非空的线性表（n＞0）记作：L=（a1，a2，…，an）③数据元素ai（1≤i≤n）只是个抽象符号，其具体含义在不同情况下可以不同。9线性表的基本术语：起始结点、终端结点、直接前驱、直接后继线性表长度，空表L=（a1，a2，…，an）注意：线性表中只有一个起始结点，一个终端结点，起始结点没有直接前驱，有一个直接后继。终端结点有一个直接前驱，没有直接后继。除此二结点外，每个结点都有且只有一个直接前驱和一个直接后继。10线性表的逻辑结构特征对于非空的线性表:①有且仅有一个起始结点a1，没有直接前驱，有且仅有一个直接后继a2；②有且仅有一个终端结点an，没有直接后继，有且仅有一个直接前驱an-1；③其余的内部结点ai（2≤i≤n-1）都有且仅有一个直接前驱ai-1和一个直接后继ai+1。11线性表的基本运算1，初始化Initiate(L)2，求表长度Length(L)3，取表元Get(L,i)4，定位Locate(L,x)5，插入Insert(L,x,i)6，删除Delete(L,i)区分引用型和加工型操作122.2线性表的顺序实现定义顺序表是线性表的顺序存储存储结构，即以一段连续内存存放的线性表此时，内存的顺序性体现了数据间的逻辑关系线性表中相邻的结点在存储结构中仍相邻13假定有一组数据，数据间有顺序：1210578564532887111此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表01234567891112105785645328871线性表的顺序存储结构1401234567891112105785645328871假设已知a1地址为Loc(a1)，每个数据占c个单元则计算ai地址Loc(ai)=Loc(a1)+c*(i-1)a1a2a3a4a5a6a7a8a9a1015此处数据间的顺序即表示数据间的逻辑关系即线性关系，这一组数据为线性表0123456789顺序存储线性表时，需要存储：存储单元大小、数据个数线性表大小：10线性表长度：7所存放数据的类型:MaxSizeLengthDataType121057856453216a1a2an01length-112n内存data数组下标元素序号maxsize-1备用空间顺序表的结构体定义#definemaxsize100typedefstruct{datatypedata[maxsize];intlength;}Seqlist;SeqlistL；问题：L有什么成员？17附讲：结构体结构体是一种构造数据类型用途：把不同类型的数据组合成一个整体-------自定义数据类型引入结构体的好处：加强数据项之间的联系如学生的基本信息，包括学号、姓名、性别、年龄、班级、成绩等数据项。这些数据项描述了一个学生的几个不同侧面。nonamesexageclassnograde独立的变量表示：数据项之间无关联nonamesexageclassnograde结构体变量表示：数据项为一个整体charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩181、结构体类型的定义struct结构体类型名{数据类型名1成员名1；数据类型名2成员名2；……数据类型名n成员名n；}；struct是关键字,不能省略合法标识符可省:无名结构体成员类型可以是基本型或构造型以分号;结尾例1：structStudent_Info{charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩};例2：structDate{intyear;//年intmonth;//月intday;//日};19在结构体中数据类型相同的成员，既可逐个、逐行分别定义，也可合并成一行定义，就象一次定义多个变量一样。structStudent_Info{charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩};structStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;};structDate{intyear;//年intmonth;//月intday;//日};structDate{intyear,month,day;};注意：结构类型只是用户自定义的一种数据类型，用来定义描述结构的组织形式,不分配内存，只有用它来定义某个变量时，才会为该变量分配结构类型所需要大小的内存单元。所占内存的大小是它所包含的成员所占内存大小之和。20structStudent_Info{charno[9],name[20],sex;unsignedintage,classno;floatgrade;};structStudent_Infostudent;例：2、结构体变量的定义和引用struct结构体类型名{数据类型名1成员名1；……数据类型名n成员名n；}；struct结构体类型名变量名列表；结构体变量的定义间接定义法：先定义结构类型，再定义结构变量……9字节20字节1字节2字节2字节4字节nonamesexageclassnograde内存映像(BC下)212、结构体变量的定义和引用struct[结构体类型名]{数据类型名1成员名1；……数据类型名n成员名n；}变量名列表；结构体变量的定义直接定义法：定义结构体类型的同时定义结构体变量structStudent_Info{charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩}student1,student2;struct{charno[9];//学号charname[20];//姓名charsex;//性别unsignedintage;//年龄unsignedintclassno;//班级floatgrade;//成绩}student1,student2;或无名结构体定义，变量只能一次定义22例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;if(stu1==stu2)……..()例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu,*pstu=&stu;strcpy(stu.name,zhangMing);stu.score=80;pstu-score+=10;printf(%s%f,stu.name,(*pstu).score);结构体变量的引用引用规则结构体变量不能整体引用,只能引用变量成员引用方式：结构体变量名.成员名//非指针型结构体变量的引用可以将一个结构体变量赋值给另一个结构体变量结构体嵌套时逐级引用结构体指针-成员名或（*结构体指针）.成员名//指针型结构体变量的引用成员(分量)运算符结合性:从左向右成员(分量)运算符结合性:从左向右例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;stu1.num=10;stu1.score=85.5;stu1.score+=stu2.score;stu1.age++;例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;printf(“%d,%s,%c,%d,%f,%s\n”,stu1);()stu1={101,“WanLin”,‘M’,19,87.5,“DaLian”};()结构体变量名.成员名.子成员名……最低级子成员名例structstudent{intnum;charname[20];charsex;intage;floatscore;charaddr[30];}stu1,stu2;Stu2=stu1;(√)例structstudent{intnum;charname[20];structdate{intmonth;intday;intyear;}birthday;}stu1,stu2,*pstu=&stu1;numnamebirthdaymonthdayyearstu1.birthday.month=12;pstu1-birthday.year=2008;233、结构体变量的赋值结构体变量初始化赋值先定义结构体类型，再定义结构体变量时赋初值struct结构体类型名初值表{……}；struct结构体类型名变量名={成员1的值，…，成员n的值}；注意：赋初值时，{}中间的数据顺序必须与结构体成员的定义顺序一致，否则就会出现混乱。structStudent_Infostu={20020306,ZhangMing,'M',18,1,90};nonamesexageclassnograde√structStudent_Infostu={18,ZhangMing,'M',20020306,1,90};×structDate{intyear;//年intmonth;//月intday;//日};structStu_Info{charno[9];//学号charname[20];//姓名charsex;//性别structDatebirthday;//生日unsignedintclassno;//班级floatgrade;//成绩};structStu_Infostu={20020306,ZhangMing,'M',{1986,12,10},1,90};243、结构体变量的赋值结构体变量初始化赋值定义结构体类型的同时，定义结构体变量并赋初值struct[结构体类型名]{初值表……}变量名={成员1的值，成员2的值，…，成员n的值}；structDate{intyear,month,day;}birthday={1986,12,10};struct{intyear,month,day;}birthday={1986,12,10};或structStudent_Info{charno[9];//学号charname[20];//姓名charsex;//性别uns