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

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

#define

List_Init_Size

100//初始空间#define

List_Increment

10//分配增量…………L.listsize=List_Init_Size;If(L.length>=L.listsize){…………

L.listsize＋=List_Increment;};P23的malloc()函数与P24的realloc()函数有什么不同？2动态数组如何实现（见教材P22和P24）#defineL附1什么是指针?

指针如何引用?什么是指针?

i20003inti=3;2000pointerint*pointer;Pointer=&i;30013附1什么是指针?指针如何引用?什么是指针?i2000如：用pi,pj,pk来存放i,j,k的地址200020042008358300130053009200020042008pipjpkijk指针的含义：

指针即变量的地址。（如2000、2004、2008等）指针变量：

含义：用于存放指针（地址）的变量。4如：用pi,pj,pk来存放i,j,k的地址2000定义方法：

数据类型*指针变量名例int*p;数据类型*指针变量名=变量地址例int*p=&i;其中1)数据类型：指针变量所指向目标单元的值的类型。

2)*：指针变量的定义符

3)变量名：目标变量在内存中的位置（地址）5定义方法：

数据类型*指针变量名例

与指针相关的运算符(1)&:取地址运算符：作用：用于变量名之前，表示该变量的存储地址。(2)*:指针运算符(间接访问)

作用：用于指针变量名之前，获取该指针所指单元的值。例如，定义和语句如下：

inti=10；int*p,*p1;…p=&i;*p=30;p1=p;p表示指针部分，属于指针类型，其内容为变量i的存储地址；*p表示指针所指的变量部分，属于int类型。p1指向p所指的变量6与指针相关的运算符(1)&:取地址运算符：(2)*:指针运需要注意的是：“*”操作符在指针上的两种用途要区分开：定义或声明时，建立一个指针；执行时间接引用一个指针。定义指针间接引用一个指针例如：intx,*p;p=&x;*p=20;7需要注意的是：“*”操作符在指针上的两种用途要区分开：定义指重要概念：

指针变量也有各种类型，但指针变量的值只能是整型值。point=&x;(√)不允许直接对指针变量赋常量值。如：

int*point;point=1000;（）只能给指针变量一个具有地址属性的值。如：

intx,*point;8重要概念：

指针变量也有各种类型，但指针变量的值只注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有确定的指向。如果此时引用指针指向的变量，将会产生不可预料的后果。例如，int*ptr;*ptr=100;

×一定要注意哦!9注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有结构体类型的认识实体：指客观世界的人、事、物、概念等。属性：实体的特征，用以描述实体。学生是个实体，可以通过以下属性给以描述。附2：结构数据类型的C表示法10结构体类型的认识附2：结构数据类型的C表示法10上海57887.6.13女赵六060411136山东55086.12.1男王五060411135………………………………浙江56286.13.25女李四060411102江苏58487.4.19男张三060411101生源成绩出生日期性别姓名学号这是一个二维表，但却无法用二维数组来描述它，原因是用来描述学生信息的五项数据类型各不相同。能否将一个学生的信息作为一个完整的类型存放呢？为了能方便地处理此类问题，在C语言中，规定了一种新的数据类型“结构体类型”，可有效地表示类型互异又逻辑相关的数据实体。11上海57887.6.13女赵六060411136山东5508对于指向结构类型的指针变量，可说明为：

node*p,*q;

//或用struct

student

*p,*q;//或用pointer

p,q;//注：上面已经定义了node为用户自定义的student类型。类型定义写为：typedefstruct

student

//student是自定义结构类型名称{chardata;//定义数据域的变量名及其类型struct

student*next;//定义指针域的变量名及其类型}node，*pointer;//node是student结构类型的类型替代,

*pointer是指针型的student结构类型的替代，也是数据类型*/12对于指向结构类型的指针变量，可说明为：类型定义写为：12

当把一个结构体变量的起始地址赋值给一个指针变量时，就称该指针指向这个结构体变量，该指针为结构体类型指针。定义形式为:

结构体类型*指针变量名;例如，structstudent{intnum;charname[20];floatscore;}wang,stud[3];structstudent*p,*q;13当把一个结构体变量的起始地址赋值给一

令p=&wang;q=stud;则指针的指向关系如图所示：1003WangWu85wangp1001ZhangSan931002LiSi90.5stud[0]stud[1]q…q+1141003WangWu85wangp1001ZhangSan9附3：介绍C的三个有用的库函数/算符（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度（字节数）；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。15附3：介绍C的三个有用的库函数/算符（都在<stdlib.h动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量Typedefstruct{ElemType*elem;//表基址(用指针*elem表示）intlength;//表长度（表中有多少个元素）intlistsize;//当前分配的表尺寸（以sizeof(ElemType)为单位）}SqList;注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（见教材P22）：16动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素sizeof(x)算符的意思是：计算变量x的长度(字节数)malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。StatusInitList_Sq(

SqList

&L)

//创建一个空线性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem)exit(OVERFLOW);

//分配失败，结束程序

L.length=0;

//暂无元素放入，空表

L.listsize=LIST_INIT_SIZE;

//表尺寸=初始分配量

ReturnOK;}//InitList_Sq动态创建一个空顺序表的算法：(教材p23)17sizeof(x)算符的意思是：计算变量x的长度(字节数)mrealloc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表中第i个位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//检验i值的合法性if(L.length

≥

L.listsize)//若表长超过表尺寸则要增加尺寸

{newbase=(ElemType*)realloc(L.elem,(L.listsize

+

LISTINCREMENT

)*sizeof(ElemType));if(newbase=NULL)exit(OVERFLOW);//分配失败则退出并报错

L.elem=newbase;//重置新基址

L.listsize=

L.listsize

+LISTINCREMENT;}//增加表尺寸18realloc(*p,newsize)函数的意思是：新开q=&L.elem[i-1];//q为插入位置。这是没有头结点的情况for(p=L.elem[L.length-1];p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素统统后移,p为元素位置*q=e;//插入e++L.length;//增加1个数据元素，则表长+1returnOK;}//ListInsert_Sq动态数组的核心是realloc(void*ptr,newsize)函数！19q=&L.elem[i-1];//动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序表L中删除第i个元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被删除元素的位置e=*p;//被删除元素的值赋给e

q=L.elem+L.length-1;//q是表尾的位置for(++p;p<=q;p++)*(p-1)=*p;//待删元素后面的统统前移--L.length;//表长-1returnOK;}//ListDelete_Sq20动态顺序表的删除算法if(i<1ori>L编写调试教材算法的注意事项：（一）要适当修改非C语言的语句，包括：1、算法函数中局部变量的定义；2、可能出现的类C语言的语句，必须改为C语言语句，如成组赋值语句s[5…8]=t[0…3];3、如果采用VC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如InitList(LinkList&L)中的参数&L要改为*L

；（二）算法中出现的函数调用,程序中要把此函数的具体算法实现出来。（三）要书写一个主程序来调用并调试描述算法的函数，主程序的设计要根据算法的功能和调试需要来编写。21编写调试教材算法的注意事项：21链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：22链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相第2章线性表2.1线性表的逻辑结构

2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例23第2章线性表2.1线性表的逻辑结构232.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析242.3线性表的链式表示和实现2.3.1链表的表示24链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率2.3.1链表的表示25链式存储结构特点：如何实现？通过指针来实现！让每个存储结点都例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：a1heada2/\an……讨论1：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)26例：请画出26个英文字母表的链式存储结构。该字母表在内存中1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语：271）结点：数据元素的存储映像。由数据域和指针域两部分组成；a3）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。示意图如下：283）头指针、头结点和首元结点的区别头指针头结点首元结点a1h答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！29答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31（3）举例例1：30一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点头结点不计入链表长度！31上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANL线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,首址=

末址=

。例2：32线性表具有两种存储方式，即顺序方式和链接方式。现有一讨论:

链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。答：以26个字母的链表为例，每个结点都有两个分量：字符型指针型设每个结点用变量node表示，其指针用p表示，两个分量分别用data和*next表示，这两个分量如何赋值？p*nextdatanode方式1：直接表示为

node.data＝'a'；node.next=q方式2：p指向结点首地址，然后p->data='a';p->next=q;方式3：p指向结点首地址，然后(*p).data='a'；(*p).next＝q‘a’‘b’qp33讨论:链表的数据元素有两个域，不再是简单数据类型，编程时该设p为指向链表的第i个元素的指针,则第i个元素的数据域写为

，指针域写为

。练习：p->dataai的值p->nextai+1的地址34设p为指向链表的第i个元素的指针,则第i个元素的练习：p->sizeof(x)——计算x的长度malloc(m)—开m字节空间free(p)——删除一个变量问1：自定义结构类型变量node的长度m是多少？问2：结构变量node的首地址(指针p）是多少？问3：怎样删除结构变量node？*nextdatanode，长度为m字节pm＝sizeof(node)//单位是字节p＝(node*)malloc(m)free(p)//只能借助node的指针删除！P->data=‘a’;p->next=q35sizeof(x)——计算x的长度问1：自定义结构类型变量n单链表的抽象数据类型描述如下（参见教材P28）：TypedefstructLnode{ElemTypedata;//数据域structLnode*next;//指针域}Lnode,*LinkList;//*LinkList为Lnode类型的指针至此应可看懂教材P22关于顺序表动态分配的存储结构。其特点是：用结构类型和指针来表示顺序结构，更灵活。如何具体编程来建立和访问链表？——链表的实现36单链表的抽象数据类型描述如下（参见教材P28）：TypedeTypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;教材P28对于线性表的单链表存储结构描述:教材问题讨论：Q1：第一行的Lnode与最后一行的Lnode是不是一回事？A1：不是。前者Lnode是结构名，后者Lnode是对整个struct类型的一种“缩写”，是一种“新定义名”，它只是对现有类型名的补充，而不是取代。请注意：Typedef不可能创造任何新的数据类型，而仅仅是在原有的数据类型中命名一个新名字，其目的是使你的程序更易阅读和移植。37TypedefstructLnode{教材P28对于线TypedefstructLnode{ElemTypedata;structLnode*next;}Lnode,*LinkList;Q2：那为何两处要同名(Lnode和Lnode）？太不严谨了吧？A2：同名是为了表述起来方便。例如，若结构名为student，其新定义名缩写也最好写成student，因为描述的对象相同，方便阅读和理解。Q3：结构体中间的那个struct

Lnode是何意？A3：在“缩写”Lnode还没出现之前，只能用原始的structLnode来进行变量说明。此处说明了指针分量的数据类型是structLnode。Typedefstructstudent{charname;intage;}student,*pointer;38TypedefstructLnode{Q2：那为何两课堂讨论：顺序表各种操作算法的“通式”该如何书写？———采用抽象数据类型来表示（见教材P19页）顺序表的存储结构是一维数组，如果插入的元素个数超过数组定义的长度怎么办？———采用动态分配的一维数组39课堂讨论：顺序表各种操作算法的“通式”该如何书写？顺序表的动态数组如何实现（见教材P22和P24）

#define

List_Init_Size

100//初始空间#define

List_Increment

10//分配增量…………L.listsize=List_Init_Size;If(L.length>=L.listsize){…………

L.listsize＋=List_Increment;};P23的malloc()函数与P24的realloc()函数有什么不同？40动态数组如何实现（见教材P22和P24）#defineL附1什么是指针?

指针如何引用?什么是指针?

i20003inti=3;2000pointerint*pointer;Pointer=&i;300141附1什么是指针?指针如何引用?什么是指针?i2000如：用pi,pj,pk来存放i,j,k的地址200020042008358300130053009200020042008pipjpkijk指针的含义：

指针即变量的地址。（如2000、2004、2008等）指针变量：

含义：用于存放指针（地址）的变量。42如：用pi,pj,pk来存放i,j,k的地址2000定义方法：

数据类型*指针变量名例int*p;数据类型*指针变量名=变量地址例int*p=&i;其中1)数据类型：指针变量所指向目标单元的值的类型。

2)*：指针变量的定义符

3)变量名：目标变量在内存中的位置（地址）43定义方法：

数据类型*指针变量名例

与指针相关的运算符(1)&:取地址运算符：作用：用于变量名之前，表示该变量的存储地址。(2)*:指针运算符(间接访问)

作用：用于指针变量名之前，获取该指针所指单元的值。例如，定义和语句如下：

inti=10；int*p,*p1;…p=&i;*p=30;p1=p;p表示指针部分，属于指针类型，其内容为变量i的存储地址；*p表示指针所指的变量部分，属于int类型。p1指向p所指的变量44与指针相关的运算符(1)&:取地址运算符：(2)*:指针运需要注意的是：“*”操作符在指针上的两种用途要区分开：定义或声明时，建立一个指针；执行时间接引用一个指针。定义指针间接引用一个指针例如：intx,*p;p=&x;*p=20;45需要注意的是：“*”操作符在指针上的两种用途要区分开：定义指重要概念：

指针变量也有各种类型，但指针变量的值只能是整型值。point=&x;(√)不允许直接对指针变量赋常量值。如：

int*point;point=1000;（）只能给指针变量一个具有地址属性的值。如：

intx,*point;46重要概念：

指针变量也有各种类型，但指针变量的值只注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有确定的指向。如果此时引用指针指向的变量，将会产生不可预料的后果。例如，int*ptr;*ptr=100;

×一定要注意哦!47注意：在没赋初值之前，指针变量的内容将是不确定的，即指针没有结构体类型的认识实体：指客观世界的人、事、物、概念等。属性：实体的特征，用以描述实体。学生是个实体，可以通过以下属性给以描述。附2：结构数据类型的C表示法48结构体类型的认识附2：结构数据类型的C表示法10上海57887.6.13女赵六060411136山东55086.12.1男王五060411135………………………………浙江56286.13.25女李四060411102江苏58487.4.19男张三060411101生源成绩出生日期性别姓名学号这是一个二维表，但却无法用二维数组来描述它，原因是用来描述学生信息的五项数据类型各不相同。能否将一个学生的信息作为一个完整的类型存放呢？为了能方便地处理此类问题，在C语言中，规定了一种新的数据类型“结构体类型”，可有效地表示类型互异又逻辑相关的数据实体。49上海57887.6.13女赵六060411136山东5508对于指向结构类型的指针变量，可说明为：

node*p,*q;

//或用struct

student

*p,*q;//或用pointer

p,q;//注：上面已经定义了node为用户自定义的student类型。类型定义写为：typedefstruct

student

//student是自定义结构类型名称{chardata;//定义数据域的变量名及其类型struct

student*next;//定义指针域的变量名及其类型}node，*pointer;//node是student结构类型的类型替代,

*pointer是指针型的student结构类型的替代，也是数据类型*/50对于指向结构类型的指针变量，可说明为：类型定义写为：12

当把一个结构体变量的起始地址赋值给一个指针变量时，就称该指针指向这个结构体变量，该指针为结构体类型指针。定义形式为:

结构体类型*指针变量名;例如，structstudent{intnum;charname[20];floatscore;}wang,stud[3];structstudent*p,*q;51当把一个结构体变量的起始地址赋值给一

令p=&wang;q=stud;则指针的指向关系如图所示：1003WangWu85wangp1001ZhangSan931002LiSi90.5stud[0]stud[1]q…q+1521003WangWu85wangp1001ZhangSan9附3：介绍C的三个有用的库函数/算符（都在<stdlib.h>中）：sizeof(x)——计算变量x的长度（字节数）；malloc(m)—开辟m字节长度的地址空间，并返回这段空间的首地址；free(p)——释放指针p所指变量的存储空间，即彻底删除一个变量。53附3：介绍C的三个有用的库函数/算符（都在<stdlib.h动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素而空间不足时，可为顺序表增加一个固定长度的空间增量。#defineLIST_INIT_SIZE100//存储空间的初始分配量#defineLISTINCREMENT10//存储空间的分配增量Typedefstruct{ElemType*elem;//表基址(用指针*elem表示）intlength;//表长度（表中有多少个元素）intlistsize;//当前分配的表尺寸（以sizeof(ElemType)为单位）}SqList;注：三个分量可简写为：L.elemL.lengthL.listsize存储结构描述如下（见教材P22）：54动态数组简介先为顺序表空间设定一个初始分配量，一旦因插入元素sizeof(x)算符的意思是：计算变量x的长度(字节数)malloc(m)函数的意思是：新开一片大小为m字节的连续空间，并把该区首址作为函数值。StatusInitList_Sq(

SqList

&L)

//创建一个空线性表{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));

If(!L.elem)exit(OVERFLOW);

//分配失败，结束程序

L.length=0;

//暂无元素放入，空表

L.listsize=LIST_INIT_SIZE;

//表尺寸=初始分配量

ReturnOK;}//InitList_Sq动态创建一个空顺序表的算法：(教材p23)55sizeof(x)算符的意思是：计算变量x的长度(字节数)mrealloc(*p,newsize)函数的意思是：新开一片大小为newsize的连续空间，并把以*p为首址的原空间数据都拷贝进去。动态顺序表的插入算法StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表中第i个位置之前插入新的元素eif(i<1ori>L.length+1)returnERROR;//检验i值的合法性if(L.length

≥

L.listsize)//若表长超过表尺寸则要增加尺寸

{newbase=(ElemType*)realloc(L.elem,(L.listsize

+

LISTINCREMENT

)*sizeof(ElemType));if(newbase=NULL)exit(OVERFLOW);//分配失败则退出并报错

L.elem=newbase;//重置新基址

L.listsize=

L.listsize

+LISTINCREMENT;}//增加表尺寸56realloc(*p,newsize)函数的意思是：新开q=&L.elem[i-1];//q为插入位置。这是没有头结点的情况for(p=L.elem[L.length-1];p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素统统后移,p为元素位置*q=e;//插入e++L.length;//增加1个数据元素，则表长+1returnOK;}//ListInsert_Sq动态数组的核心是realloc(void*ptr,newsize)函数！57q=&L.elem[i-1];//动态顺序表的删除算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序表L中删除第i个元素，用e返回其值if(i<1ori>L.length)returnERROR;//i值不合法，返回p=&L.elem[i-1];//p是被删除元素的位置e=*p;//被删除元素的值赋给e

q=L.elem+L.length-1;//q是表尾的位置for(++p;p<=q;p++)*(p-1)=*p;//待删元素后面的统统前移--L.length;//表长-1returnOK;}//ListDelete_Sq58动态顺序表的删除算法if(i<1ori>L编写调试教材算法的注意事项：（一）要适当修改非C语言的语句，包括：1、算法函数中局部变量的定义；2、可能出现的类C语言的语句，必须改为C语言语句，如成组赋值语句s[5…8]=t[0…3];3、如果采用VC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如InitList(LinkList&L)中的参数&L要改为*L

；（二）算法中出现的函数调用,程序中要把此函数的具体算法实现出来。（三）要书写一个主程序来调用并调试描述算法的函数，主程序的设计要根据算法的功能和调试需要来编写。59编写调试教材算法的注意事项：21链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相邻的两个元素在物理存储位置上也相邻；优点：可以随机存取表中任一元素，方便快捷；缺点：在插入或删除某一元素时，需要移动大量元素。解决问题的思路：改用另一种线性存储方式：60链式存储结构2.2节小结线性表顺序存储结构特点：逻辑关系上相第2章线性表2.1线性表的逻辑结构

2.2线性表的顺序表示和实现2.3线性表的链式表示和实现2.4应用举例61第2章线性表2.1线性表的逻辑结构232.3线性表的链式表示和实现2.3.1链表的表示2.3.2链表的实现2.3.3链表的运算效率分析622.3线性表的链式表示和实现2.3.1链表的表示24链式存储结构特点：其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。如何实现？通过指针来实现！让每个存储结点都包含两部分：数据域和指针域指针数据指针数据指针或样式：数据域：存储元素数值数据指针域：存储直接后继或者直接前驱的存储位置设计思想：牺牲空间效率换取时间效率2.3.1链表的表示63链式存储结构特点：如何实现？通过指针来实现！让每个存储结点都例：请画出26个英文字母表的链式存储结构。该字母表在内存中链式存放的样式举例如下：解：该字母表的逻辑结构为：（a,b,…,y,z）链表存放示意图如下：a1heada2/\an……讨论1：每个存储结点都包含两部分：数据域和

。讨论2：在单链表中，除了首元结点外，任一结点的存储位置由

指示。其直接前驱结点的链域的值指针域(链域)64例：请画出26个英文字母表的链式存储结构。该字母表在内存中1）结点：数据元素的存储映像。由数据域和指针域两部分组成；2）链表：n个结点由指针链组成一个链表。它是线性表的链式存储映像，称为线性表的链式存储结构。3）单链表、双链表、多链表、循环链表：

结点只有一个指针域的链表，称为单链表或线性链表；有两个指针域的链表，称为双链表（但未必是双向链表）；有多个指针域的链表，称为多链表；首尾相接的链表称为循环链表。a1heada2an……循环链表示意图：head(2)与链式存储有关的术语：651）结点：数据元素的存储映像。由数据域和指针域两部分组成；a3）头指针、头结点和首元结点的区别头指针头结点首元结点a1heada2…infoan^头指针是指向链表中第一个结点（或为头结点、或为首元结点）的指针；头结点是在链表的首元结点之前附设的一个结点；数据域内只放空表标志和表长等信息，它不计入表长度。首元结点是指链表中存储线性表第一个数据元素a1的结点。示意图如下：663）头指针、头结点和首元结点的区别头指针头结点首元结点a1h答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表示空表？头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。答：无头结点时，当头指针的值为空时表示空表；^头指针无头结点^头指针头结点有头结点有头结点时，当头结点的指针域为空时表示空表。头结点不计入链表长度！67答：讨论1.在链表中设置头结点有什么好处？讨论2.如何表一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG），其存储结构用单链表表示如下，请问其头指针的值是多少？存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU25答：头指针是指向链表中第一个结点的指针，因此关键是要寻找第一个结点的地址。7ZHAOH31称：头指针H的值是31（3）举例例1：68一个线性表的逻辑结构为：（ZHAO,QIAN,SUN,LI,上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANLISUNZHOUWUZHENG/\WANGH②ZHAOQIANLISUNZHOUWUZHENG/\WANGH区别：①无头结点②有头结点头结点不计入链表长度！69上例链表的逻辑结构示意图有以下两种形式：①ZHAOQIANL线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下图所示。其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？Z47Y31V23X17U05100119104108116112116NULL(0)100108112答：X=

Y=

Z=

,首址=

末址=

。例2：70线性表具有两种存储方式，