理学数据结构线性表.pptx

《理学数据结构线性表.pptx》由会员分享，可在线阅读，更多相关《理学数据结构线性表.pptx（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、附附1 1 什么是指针什么是指针?指针如何引用指针如何引用?什么是指针什么是指针?i20003int i=3;int i=3;2000pointerint*pointer;int*pointer;Pointer=&i;Pointer=&i;3001第第1页页/共共37页页如如：用：用pi,pj,pkpi,pj,pk来存放来存放i,j,ki,j,k的地址的地址200020042008 35 8300130053009200020042008pipjpkijk指针的含义：指针即变量的地址。（如2000、2004、2008等）指针变量：含义：用于存放指针（地址）的变量。第第2页页/共共37页页定义方

2、法：数据类型 *指针变量名 例 int*p;数据类型 *指针变量名=变量地址 例 int*p=&i;其中 1)数据类型：指针变量所指向目标单元的值的类型。2)*：指针变量的定义符 3)变量名 ：目标变量在内存中的位置（地 址）第第3页页/共共37页页 与指针相关的运算符与指针相关的运算符(1)&:(1)&:取地址运算符：取地址运算符：作用：用于变量名之前，表示该变量的存储地址。作用：用于变量名之前，表示该变量的存储地址。(2)*:(2)*:指针运算符指针运算符(间接访问间接访问)作用：用于指针变量名之前，获取该指针所指单元的值。作用：用于指针变量名之前，获取该指针所指单元的值。例如，定义和语句

3、如下：例如，定义和语句如下：int i=10；int*p,*p1;p=&i;*p=30;p1=p;p表示指针表示指针部分，属于指部分，属于指针类型，其内容为变针类型，其内容为变量量i的存储地址；的存储地址；*p表示指针所指的变量表示指针所指的变量部分，部分，属于属于int类型。类型。p1指向指向p所所指的变量指的变量第第4页页/共共37页页需要注意的是：需要注意的是：“*”操作符在指针上的两种用途要区分开：操作符在指针上的两种用途要区分开：定义或声明时，建立一个指针；定义或声明时，建立一个指针；执行时间接引用一个指针。执行时间接引用一个指针。定义指针定义指针间接引用一个指针间接引用一个指针例如

4、：例如：int x,*p;p=&x;*p=20;第第5页页/共共37页页重要概念：重要概念：指针变量也有各种类型，但指针变量的值只能指针变量也有各种类型，但指针变量的值只能是整型值。是整型值。point=&x;()不允许直接对指针变量赋常量值。不允许直接对指针变量赋常量值。如：如：int*point;point=1000;（）只能给指针变量一个具有地址属性的值。只能给指针变量一个具有地址属性的值。如：如：int x,*point;第第6页页/共共37页页注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有确定的指向。如果此时引用指针指向的变量，将会产生不可预料的后果。例如，int*pt

5、r;*ptr=100;一定要注意哦一定要注意哦!第第7页页/共共37页页 结构体类型的认识实体：实体：指客观世界的人、事、物、概念等。指客观世界的人、事、物、概念等。属性：属性：实体的特征，用以描述实体。实体的特征，用以描述实体。学生是个实体，可以通过以下属性给以描述。学生是个实体，可以通过以下属性给以描述。附附2：结构数据类型的结构数据类型的C表示法表示法第第8页页/共共37页页上海上海57857887.6.1387.6.13女女赵六赵六060411136060411136山东山东55055086.12.186.12.1男男王五王五060411135060411135浙江浙江56256286

6、.13.2586.13.25女女李四李四060411102060411102江苏江苏58458487.4.1987.4.19男男张三张三060411101060411101生生 源源成成 绩绩出生日期出生日期性性 别别姓姓 名名学学 号号 这是一个二维表，但却无法用二维数组来描述它，这是一个二维表，但却无法用二维数组来描述它，原因是用来描述学生信息的五项数据类型各不相同。原因是用来描述学生信息的五项数据类型各不相同。能否能否将一个学生的信息作为一个完整的类型存放呢？将一个学生的信息作为一个完整的类型存放呢？为了能方为了能方便地处理此类问题，在便地处理此类问题，在C C语言中，规定了一种新的数据

7、类语言中，规定了一种新的数据类型型“结构体类型结构体类型”，可有效地表示类型互异又逻辑相关的，可有效地表示类型互异又逻辑相关的数据实体。数据实体。第第9页页/共共37页页对于指向结构类型的指针变量，可说明为对于指向结构类型的指针变量，可说明为：nodenodenodenode *p,*q;/或用或用 struct studentstudent*p,*q;/或用或用 pointerpointer p,q;p,q;/注：上面已经定义了注：上面已经定义了node为用户自定义的为用户自定义的studentstudent类型。类型。类型定义写为：类型定义写为：typedef structtypedef

8、struct student /studentstudent是自定义结构类型名称是自定义结构类型名称 char data;/定义数据域的变量名及其类型定义数据域的变量名及其类型 structstruct studentstudent*next;/定义指针域的变量名及其类型定义指针域的变量名及其类型node，*pointer;/nodenode是是studentstudent结结构构类类型型的的类类型型替替代代,*pointer*pointer是是指指针针型型的的studentstudent结结构构类类型型的的替替代代，也也是是数数据类型据类型*/第第10页页/共共37页页 当把一个结构体变量的

9、起始地址赋值给一个指针变量时，就称该指针指向这个结构体变量，该指针为结构体类型指针。定义形式为:结构体类型 *指针变量名;例如，struct student int num;char name20;float score;wang,stud3;struct student*p,*q;第第11页页/共共37页页 令令p=&wang;q=stud;p=&wang;q=stud;则指针的指向关系如图所示：则指针的指向关系如图所示：1003WangWu85wangp1001ZhangSan931002LiSi90.5stud0stud1qq+1第第12页页/共共37页页附附3：介绍介绍C的三个有用的库

10、函数的三个有用的库函数/算符（都在算符（都在 中）：中）：sizeof(x)计算变量计算变量x x的长度（字节数）；的长度（字节数）；malloc(m)开辟开辟m m字节长度的地址空间，并返回这段空间字节长度的地址空间，并返回这段空间的首地址；的首地址；free(p)释放指针释放指针p p所指变量的存储空间，即彻底删除所指变量的存储空间，即彻底删除一个变量。一个变量。第第13页页/共共37页页动态数组简介动态数组简介先为顺序表空间设定一个初始分配量，一旦因先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长插入元素而空间不足时，可为顺序表增加一个固定长度的空间

11、增量。度的空间增量。#define LIST_INIT_SIZE 100/存储空间的初始分配量存储空间的初始分配量#define LISTINCREMENT 10/存储空间的分配增量存储空间的分配增量Typedef struct ElemType*elem;/表基址表基址(用指针用指针*elemelem表示表示）int length;/表长度（表长度（表中有多少个元素表中有多少个元素）int listsize;/当前分配的表尺寸（当前分配的表尺寸（以以sizeof(ElemType)sizeof(ElemType)为单位为单位）SqList;注：三个分量可简写为：注：三个分量可简写为：L.el

12、em L.length L.listsize存储结构描述如下（存储结构描述如下（见教材见教材P22P22）：）：第第14页页/共共37页页sizeof(x)sizeof(x)算符的意思是：算符的意思是：计算变量计算变量x x的长度的长度(字节数字节数)malloc(m)函数的意思是：新开函数的意思是：新开一片大小为一片大小为m字节字节的连续空间，的连续空间，并把该区首址作为函数值。并把该区首址作为函数值。Status InitList_Sq(SqList&L)/创建一个空线性表创建一个空线性表 L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(Ele

13、mType);If(!L.elem)exit(OVERFLOW);/分配失败，结束程序分配失败，结束程序 L.length=0;/暂无元素放入，空表暂无元素放入，空表 L.listsize=LIST_INIT_SIZE;/表尺寸表尺寸=初始分配量初始分配量 Return OK;/InitList_Sq/InitList_Sq动态创建一个动态创建一个动态创建一个动态创建一个空空空空顺序表的算法：顺序表的算法：顺序表的算法：顺序表的算法：(教材教材教材教材p23)p23)第第15页页/共共37页页realloc(*p,newsize)函数的意思是：新开一函数的意思是：新开一片大小为片大小为news

14、ize的连续空间，并把以的连续空间，并把以*p为为首址的原空间数据都拷贝进去。首址的原空间数据都拷贝进去。动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法动态顺序表的插入算法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=(ElemTy

15、pe*)realloc(L.elem,(L.listsize+LISTLISTINCREMENTINCREMENT)*sizeof(ElemType);if(newbase=NULL)exit(OVERFLOW);/分配失败则退出并报错分配失败则退出并报错 L.elem=newbase;/重置新基址重置新基址 L.listsize=L.listsize+LISTINCREMENT LISTINCREMENT;/增加表尺寸增加表尺寸第第16页页/共共37页页 q=&L.elemi-1;/q为插入位置。这是没有头结点的情况为插入位置。这是没有头结点的情况 for(p=L.elemL.length-

16、1;p=q;-p)*(p+1)=*p;/插入位置及之后的元素统统后移插入位置及之后的元素统统后移,p为元素位置为元素位置*q=e;/插入插入e+L.length;/增加增加1个数据元素，则表长个数据元素，则表长+1 return OK;/ListInsert_Sq动态数组的核心是动态数组的核心是reallocrealloc(void*ptr,newsize)(void*ptr,newsize)函数！函数！第第17页页/共共37页页动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法动态顺序表的删除算法Status ListDelete_Sq(SqList&L,int i,ElemTyp

17、e&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=aa;p-next=q q;方式方式3：p指向结点首地址，然后指向结点首地址，然后(*p).data=aa；(*p).nextq qaabq qp p第第31页页/共共37页页设设p p为指向链

18、表的第为指向链表的第i i个元素的指针个元素的指针,则第则第i i个元素的个元素的数据域写为数据域写为 ，指针域写为，指针域写为 。练习：练习：p-dataai的值的值p-nextai+1的地址的地址第第32页页/共共37页页sizeof(x)计算计算x x的长度的长度malloc(m)开开m m字节字节空间空间free(p)删除一个变量删除一个变量问问1：自定义结构类型变量自定义结构类型变量node的长度的长度m是多少？是多少？问问2：结构变量结构变量node的首地址的首地址(指针指针p）是多少？）是多少？问问3：怎样删除结构变量怎样删除结构变量node？*nextdatanode，长度为长

19、度为m字节字节pmsizeof(node)/单位是字节单位是字节p(node*)malloc(m)free(p)/只能借助只能借助node的指针删除！的指针删除！P-data=P-data=a a;p-;p-next=qnext=q第第33页页/共共37页页单链表的抽象数据类型描述如下单链表的抽象数据类型描述如下（参见教材参见教材P28P28）：）：Typedef struct Lnode ElemType data;/数据域数据域 struct Lnode *next;/指针域指针域Lnode,*LinkList;/*LinkList为为Lnode类型的指针类型的指针至此应可看懂教材至此应可

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

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

22、f 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;第第36页页/共共37页页37感谢观看！感谢观看！第第37页页/共共37页页