数据结构第2章+线性表B课件.ppt

1、课堂讨论：课堂讨论：顺序表各种操作算法的顺序表各种操作算法的“通式通式”该如何书写？该如何书写？采用采用抽象数据类型抽象数据类型来表示来表示（见教材（见教材P19页）页）顺序表的存储结构是一维数组，如果插入的元顺序表的存储结构是一维数组，如果插入的元素个数素个数超过超过数组定义的数组定义的长度长度怎么办？怎么办？采用采用动态分配动态分配的一维数组的一维数组动态数组如何实现动态数组如何实现（见教材见教材P22和和P24）#define#define List_Init_SizeList_Init_Size 100 /100 /初始空间初始空间#define#define List_Increme

2、ntList_Increment 10 /10 /分配增量分配增量 L.listsizeL.listsize=List_Init_Size;=List_Init_Size;If(L.length=If(L.length=L.listsizeL.listsize)L.listsizeL.listsize=List_IncrementList_Increment;P23P23的的mallocmalloc()()函数与函数与P24P24的的reallocrealloc()()函数函数有什么不同？有什么不同？附附1 1 什么是指针什么是指针?指针如何引用指针如何引用?什么是指针什么是指针?i20003

3、intint i=3;i=3;2000pointerintint *pointer;pointer;Pointer=&i;Pointer=&i;3001如如：用：用pi,pj,pkpi,pj,pk来存放来存放i,j,ki,j,k的地址的地址200020042008 35 8300130053009200020042008pipjpkijk指针的含义：指针即变量的地址。（如2000、2004、2008等）指针变量：含义：用于存放指针（地址）的变量。定义方法：数据类型 *指针变量名 例 int*p;数据类型 *指针变量名=变量地址 例 int*p=&i;其中 1)数据类型：指针变量所指向目标单元的

4、值的类型。2)*：指针变量的定义符 3)变量名 ：目标变量在内存中的位置（地 址）与指针相关的运算符与指针相关的运算符(1)&:(1)&:取地址运算符：取地址运算符：作用：用于变量名之前，表示该变量的存储地址。作用：用于变量名之前，表示该变量的存储地址。(2)(2)*:指针运算符指针运算符(间接访问间接访问)作用：用于指针变量名之前，获取该指针所指单元的值。作用：用于指针变量名之前，获取该指针所指单元的值。例如，定义和语句如下：例如，定义和语句如下：int i=10；int*p,*p1;p=&i;*p=30;p1=p;p表示指针表示指针部分，属于指部分，属于指针类型，其内容为变针类型，其内容为

5、变量量i的存储地址；的存储地址；*p表示指针所指的变量表示指针所指的变量部分，部分，属于属于int类型。类型。p1指向指向p所所指的变量指的变量需要注意的是：需要注意的是：“*”操作符在指针上的两种用途要区分开：操作符在指针上的两种用途要区分开：定义或声明时，建立一个指针；定义或声明时，建立一个指针；执行时间接引用一个指针。执行时间接引用一个指针。定义指针定义指针间接引用一个指针间接引用一个指针例如：例如：int x,*p;p=&x;*p=20;重要概念：重要概念：指针变量也有各种类型，但指针变量的值只能指针变量也有各种类型，但指针变量的值只能是整型值。是整型值。point=&x;()不允许直

6、接对指针变量赋常量值。不允许直接对指针变量赋常量值。如：如：int*point;point=1000;（）只能给指针变量一个具有地址属性的值。只能给指针变量一个具有地址属性的值。如：如：int x,*point;注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有确定的指向。如果此时引用指针指向的变量，将会产生不可预料的后果。例如，int*ptr;*ptr=100;一定要注意哦一定要注意哦!结构体类型的认识实体：实体：指客观世界的人、事、物、概念等。指客观世界的人、事、物、概念等。属性：属性：实体的特征，用以描述实体。实体的特征，用以描述实体。学生是个实体，可以通过以下属性给以描述。学

7、生是个实体，可以通过以下属性给以描述。实体NameScoreAgeSexNumAddr实体实体：属性属性：附附2 2：结构数据类型的结构数据类型的C C表示法表示法上海上海57857887.6.1387.6.13女女赵六赵六060411136060411136山东山东55055086.12.186.12.1男男王五王五060411135060411135浙江浙江56256286.13.2586.13.25女女李四李四060411102060411102江苏江苏58458487.4.1987.4.19男男张三张三060411101060411101生生 源源成成 绩绩出生日期出生日期性性 别别姓

8、姓 名名学学 号号 这是一个二维表，但却无法用二维数组来描述它，这是一个二维表，但却无法用二维数组来描述它，原因是用来描述学生信息的五项数据类型各不相同。原因是用来描述学生信息的五项数据类型各不相同。能否能否将一个学生的信息作为一个完整的类型存放呢？将一个学生的信息作为一个完整的类型存放呢？为了能方为了能方便地处理此类问题，在便地处理此类问题，在C C语言中，规定了一种新的数据类语言中，规定了一种新的数据类型型“结构体类型结构体类型”，可有效地表示类型互异又逻辑相关的，可有效地表示类型互异又逻辑相关的数据实体。数据实体。对于指向结构类型的指针变量，可说明为对于指向结构类型的指针变量，可说明为：

9、*p,*q;/或用或用 struct studentstudent*p,*q;/或用或用 pointerpointer p,q;p,q;/注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的studentstudent类型。类型。类型定义写为：类型定义写为：student /studentstudent是自定义结构类型名称是自定义结构类型名称 char data;/定义数据域的变量名及其类型定义数据域的变量名及其类型 studentstudent*next;/定义指针域的变量名及其类型定义指针域的变量名及其类型node，*pointer;/nodenode是是student

10、student结构类型的类型替代结构类型的类型替代,*pointerpointer是指针型的是指针型的studentstudent结构类型的替代，也是数据类结构类型的替代，也是数据类型型*/当把一个结构体变量的起始地址赋值给一个指针变量时，就称该指针指向这个结构体变量，该指针为结构体类型指针。定义形式为:结构体类型 *指针变量名;例如，struct student int num;char name20;float score;wang,stud3;struct student*p,*q;令令p=&wangp=&wang;q=stud;q=stud;则指针的指向关系如图所示：则指针的指向关系如

11、图所示：1003WangWu85wangp1001ZhangSan931002LiSi90.5stud0stud1qq+1附附3：介绍介绍C的三个有用的库函数的三个有用的库函数/算符（都在算符（都在 中）：中）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m)开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p)释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一

12、旦因插入元素而空间不足时，可为顺序表增加一个固定插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。长度的空间增量。#define LIST_INIT_SIZE 100/存储空间的初始分配量存储空间的初始分配量#define LISTINCREMENT 10/存储空间的分配增量存储空间的分配增量Typedef struct ElemType*elem;/表基址表基址(用指针用指针*elemelem表示表示）int length;/表长度（表长度（表中有多少个元素表中有多少个元素）int listsize;/当前分配的表尺寸（当前分配的表尺寸（以以sizeof(ElemTypesizeo

13、f(ElemType)为单位为单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L.elem L.length L.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：sizeof(xsizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开函数的意思是：新开一片大小为一片大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。Status InitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表 L.elem=(ElemT

14、ype*)malloc(LIST_INIT_SIZE*sizeof(ElemType);If(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序 L.length=0;/暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量 Return OK;/InitList_Sq/InitList_Sqrealloc(*p,newsize)函数的意思是：新开一函数的意思是：新开一片大小为片大小为newsize的连续空间，并把以的连续空间，并把以*p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷

15、贝进去。Status ListInsert_Sq(SqList&L,int i,ElemType e)/在顺序线性表中第在顺序线性表中第i i个位置之前插入新的元素个位置之前插入新的元素e eif(i L.length+1)return ERROR;/检验检验i 值的合法性值的合法性 if(L.length L.listsize)/若表长超过表尺寸则要增加尺寸若表长超过表尺寸则要增加尺寸 newbase=(ElemType*)realloc(L.elem,(L.listsize )*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出

16、并报错分配失败则退出并报错 L.elem=newbase;/重置新基址重置新基址 L.listsize=L.listsize ;/增加表尺寸增加表尺寸 q=&L.elemi-1;/q为插入位置。这是没有头结点的情况为插入位置。这是没有头结点的情况 for(p=L.elemL.length-1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位置为元素位置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1 return OK;/ListInsert_Sq动态数组的核心是动态数组的核心是realloc

17、realloc(void(void*ptr,newsizeptr,newsize)函数！函数！Status ListDelete_Sq(SqList&L,int i,ElemType&e)/在顺序表在顺序表L中删除第中删除第 i 个元素，用个元素，用 e 返回其值返回其值 if(i L.length)return ERROR;/i 值不合法，返回值不合法，返回 p=&L.elemi-1;/p 是被删除元素的位置是被删除元素的位置 e=*p;/被删除元素的值赋给被删除元素的值赋给 e q=L.elem+L.length-1;/q 是表尾的位置是表尾的位置 for(+p;pdata=;p-next

18、=;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=；(*p).nextb设设p p为指向链表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址sizeof(x)计算计算x x的长度的长度malloc(m)开开m m字节字节空间空间free(p)删除一个变量删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少？）是

19、多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长度为m字节字节pmsizeof(node)/单位是字节单位是字节p(node*)malloc(m)free(p)/只能借助只能借助node的指针删除！的指针删除！P-data=a;p-P-data=a;p-next=qnext=q单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材参见教材P28P28）：）：Typedef struct Lnode ElemType data;/数据域数据域 struct Lnode *next;/指针域指针域Lnode,*LinkList;/*LinkL

20、ist为为Lnode类型的指针类型的指针至此应可看懂教材至此应可看懂教材P22P22关于顺序表关于顺序表动态分配动态分配的存储结构的存储结构。其特点是：用结构类型和指针来表示顺序结构，更灵活。其特点是：用结构类型和指针来表示顺序结构，更灵活。如何具体编程来建立如何具体编程来建立和访问链表？和访问链表？链表的实现链表的实现Typedef struct Lnode ElemType data;struct Lnode *next;Lnode,*LinkList;教材P28P28对于线性表的单链表存储结构描述:教材问题讨论：教材问题讨论：Q1Q1：第一行的第一行的LnodeLnode 与最后一行的与

21、最后一行的LnodeLnode是不是一回事？是不是一回事？A1A1：不是。前者不是。前者LnodeLnode是结构名，后者是结构名，后者LnodeLnode是对整个是对整个structstruct类型的一种类型的一种“缩写缩写”，是一种，是一种“新定义名新定义名”，它只，它只是对现有类型名的补充，而不是取代。是对现有类型名的补充，而不是取代。请注意：请注意：TypedefTypedef不可能创造不可能创造任何新的数据类型，而仅仅是任何新的数据类型，而仅仅是在原有的数据类型中命名一个在原有的数据类型中命名一个新名字，其目的是使你的程序新名字，其目的是使你的程序更易阅读和移植。更易阅读和移植。Ty

22、pedef struct Lnode ElemType data;struct Lnode *next;Lnode,*LinkList;Q2Q2：那为何两处要同名那为何两处要同名(Lnode和和Lnode）？太不严谨了吧？）？太不严谨了吧？A2A2：同名是为了表述起来方便。例如，若结构名为同名是为了表述起来方便。例如，若结构名为studentstudent，其新定义名缩写也最好写成其新定义名缩写也最好写成studentstudent，因为描述的对象相同，因为描述的对象相同，方便阅读和理解。方便阅读和理解。Q3Q3：结构体中间的那个：结构体中间的那个structstruct LnodeLnode是何意？是何意？A3A3：在：在“缩写缩写”LnodeLnode还没出现之前，只能用原始的还没出现之前，只能用原始的struct Lnodestruct Lnode来进行变量说明。此处说明了指针分量的数来进行变量说明。此处说明了指针分量的数据类型是据类型是struct Lnodestruct Lnode。Typedef struct student char name;int age;student,*pointer;