DBS第02章结构与联合、数组、链表.ppt

《DBS第02章结构与联合、数组、链表.ppt》由会员分享，可在线阅读，更多相关《DBS第02章结构与联合、数组、链表.ppt（56页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章第二章 两种基本数据结构两种基本数据结构内容提要内容提要 1 1、结构与联合；、结构与联合；2 2、数组；、数组；3 3、链表。、链表。2.1 2.1 结构与联合结构与联合结构结构是是C C语言提供的语言提供的聚合数据聚合数据的机制。使用结构可以将的机制。使用结构可以将不同类型的数据组合成一个整体。不同类型的数据组合成一个整体。例如：例如：struct studentstruct student char name20;char name20;char sex;char sex;int age;int age;数据项数据项：每个数据每个数据每个数据每个数据项称为一个结构体项称为一个结构体

2、项称为一个结构体项称为一个结构体的成员的成员的成员的成员如：如：struct student struct student strcpy(studentA.name,Wang);strcpy(studentA.name,Wang);studentA.age=19;studentA.age=19;studentA.sex=M;studentA.sex=M;studentA;studentA;成员运算符成员运算符“.”“.”studentA.age+studentA.age+；struct student student2;struct student student2;student2=stud

3、entA;student2=studentA;ANSI CANSI C允许将一个结构变量整体赋值给另一个具有允许将一个结构变量整体赋值给另一个具有相同结构的结构变量。相同结构的结构变量。不能将一个结构变量作为一个整体进行输入和输出，不能将一个结构变量作为一个整体进行输入和输出，也不能直接判定两个结构是否相同。也不能直接判定两个结构是否相同。printf(“%dn”,studentA);printf(“%dn”,studentA);printf(“studentA:%s,%d,%cn”,studentA.name,studenprintf(“studentA:%s,%d,%cn”,student

4、A.name,studentA.age,studentA.sex);tA.age,studentA.sex);可逐个全部或部分输入输出。可逐个全部或部分输入输出。定义变量的语句：定义变量的语句：struct student student1 struct student student1；用用typedeftypedef创建结构类型创建结构类型StudentStudent：typedef struct studenttypedef struct student char name20;char name20;char sex;char sex;int age;int age;Student S

5、tudent；结构名结构名结构类型名结构类型名Student student1;Student student1;结构名称与结构名称与结构类型的结构类型的名称可以相名称可以相同同2.1.2 2.1.2 联合联合 联合联合(union)(union)是一个变量，它可以存放不同类型是一个变量，它可以存放不同类型的数据对象。的数据对象。联合的目的是联合的目的是使用单一变量，存放多个类型的使用单一变量，存放多个类型的值值。显然任何时候只能存放其中之一。显然任何时候只能存放其中之一。union tag union tag int ival;int ival;float fval;float fval;c

6、har chval;char chval;；union tag aunion tag a，b b；联合可以放在结构或数组中，反之亦然。联合可以放在结构或数组中，反之亦然。访问一个结构中的联合的成员等同于访问嵌套的结访问一个结构中的联合的成员等同于访问嵌套的结构变量。构变量。引用联合的成员引用联合的成员ivalival的方式是：的方式是：symtabi.u.ival symtabi.u.ivalstruct struct char name20;char name20;int flags;int flags;int utype;int utype;union union int ival;int

7、 ival;float fval;float fval;char chval;char chval;u;u;symtab maxsize;symtab maxsize;用用typedeftypedef创建自己的联合类型。创建自己的联合类型。typedef union tag typedef union tag int ival;int ival;float fval;float fval;char chval;char chval;Constval Constval；2.2 2.2 数组数组数组与结构相同之处：数组与结构相同之处：一一旦旦定定义义，便便不不能能再再增增加加和和删删除除元元素素，

8、只只能能访访问问和和修修改改数数组元素的值，因此被称为组元素的值，因此被称为静态数据结构静态数据结构。静态数据结构的特点：静态数据结构的特点：一个静态数据结构一旦建立，它包含的元素个数将不变。一个静态数据结构一旦建立，它包含的元素个数将不变。动态数据结构：动态数据结构：数据元素个数可变的数据结构，可以在动态数据结构中数据元素个数可变的数据结构，可以在动态数据结构中插入或删除数据元素。插入或删除数据元素。数组与结构不同之处：数组与结构不同之处：数组的元素具有相同的数据类型，而结构的元数组的元素具有相同的数据类型，而结构的元素素(域域)可以是不同类型。可以是不同类型。数组元素用下标标识，而结构的域

9、由域名引用。数组元素用下标标识，而结构的域由域名引用。2.2.1 2.2.1 一维数组一维数组C C语言中的一维数组：语言中的一维数组：int one5;int one5;数组元素可以在定义时赋值：数组元素可以在定义时赋值：int one5=0,1,2,3,4;int one5=0,1,2,3,4;也可以通过引用数组元素对元素赋值。也可以通过引用数组元素对元素赋值。for(i=0;i5;i+)onei=i;for(i=0;i5;i+)onei=i;下标从下标从0 0到到4 4例如例如 int a5 int a5；a aa 4 a 4 a 3 a 3 a 2 a 2 a 1 a 1 a 0 a

10、0 数组通常采用数组通常采用顺序表示顺序表示，即数组中的元素按一定，即数组中的元素按一定顺序存放在一个顺序存放在一个连续的存储区域连续的存储区域。Loc(ai)=Loc(a0)+i*kLoc(ai)=Loc(a0)+i*k起始地址起始地址前前i i个元素占用个元素占用的存储单元的的存储单元的数量数量2.2.2 2.2.2 二维数组二维数组二维数组二维数组(two-dimensional array)(two-dimensional array)的下标是二维的。的下标是二维的。int a34;int a34;aa0a1a2a10a10 a11a11 a12a12 a13a13a00a00 a01

11、a01 a02a02 a03a03 a20a20a21a21a22a22a23a23可以认为二维数组是每个元素都是一维数组的一维可以认为二维数组是每个元素都是一维数组的一维数组数组将一个二维数组映射到一维的存储空间将一个二维数组映射到一维的存储空间一般有两种顺序：一般有两种顺序：行优先顺序行优先顺序(row major order)(row major order)列优先顺序列优先顺序(column major order)(column major order)行优先顺序的地址计算：行优先顺序的地址计算：若若已已知知每每个个数数组组元元素素占占k k个个存存储储单单元元，第第一一个个数数组组

12、元元素素a00a00的的存存储储地地址址是是loc(a00),loc(a00),则则数数组组元元素素aijaij的的存存储储地地址址loc(aij)loc(aij)为为loc(aij)=loc(a00)+(i*n+j)*kloc(aij)=loc(a00)+(i*n+j)*k (0(0 im;0im;0 j j n)n)a00 a01a0n-1 a10 a11a1n-1 am-10 am-11am-1n-1a00 a01a0n-1 a10 a11a1n-1 am-10 am-11am-1n-1 -下标为下标为0 0的行的行-下标为下标为1 1的行的行-下标为下标为m-1m-1的行的行-行优先顺

13、序行优先顺序列优先顺序存储：列优先顺序存储：loc(aij)=loc(a00)+(j*m+i)*k (0loc(aij)=loc(a00)+(j*m+i)*k (0 im;0im;0 j j n)n)a00 a10am-10 a01 a11am-11 a0n-1 a1n-1am-1n-1 a00 a10am-10 a01 a11am-11 a0n-1 a1n-1am-1n-1-下标为下标为0 0的列的列-下标为下标为1 1的列的列-下标为下标为n-1n-1的列的列-列优先顺序列优先顺序随机存取的存储结构随机存取的存储结构 存取数组中任何一个元素所需的时间是相同的存取数组中任何一个元素所需的时间

14、是相同的维数和各维的长度维数和各维的长度分配存储空间分配存储空间数组元素下标数组元素下标根据相应的地址计算公式求根据相应的地址计算公式求得数组元素的存储位置来存得数组元素的存储位置来存取元素取元素 static int a34=1,0,6,0,0,11;static int a34=1,0,6,0,0,11;静态存储变量存放在静态存储变量存放在静态存储区静态存储区中。中。二维数组的初始化二维数组的初始化0110000600001采用采用typedeftypedef定义二维数组类型：定义二维数组类型：typedef int atype34;typedef int atype34;atype a=

15、1atype a=1，00，66，00，0 0，11;11;或或typedef int atype14;typedef int atype14;typedef atype1 atype23;typedef atype1 atype23;atype2 a=1atype2 a=1，00，66，00，0 0，11;11;推广到多维数组推广到多维数组amam1 1mm2 2 m mn n，数组元素数组元素aiai1 1ii2 2 i in n 的存储地址为的存储地址为 ：loc(ailoc(ai1 1ii2 2 i in n)=loc(a00)=loc(a00)+(i +(i1 1*m*m2 2*m*

16、m3 3*m*mn n +i+i2 2*m*m3 3*m*m4 4*m*mn n +i +in-1n-1*m*mn n +i+in n )*k)*k(0(0 i ij jmmj j,1,1 j j n)n)2.2.3 2.2.3 多维数组的顺序表示多维数组的顺序表示数组元素的存储位置是其下标的数组元素的存储位置是其下标的线性函数线性函数。通过。通过计算地址便可实现对数组元素的计算地址便可实现对数组元素的随机存取随机存取。C C语言中数组是语言中数组是不允许整体赋值不允许整体赋值的。的。C C语言中对数组下标超出正常范围的访问语言中对数组下标超出正常范围的访问并不限制并不限制 例如：例如：int

17、int a5 a5 a a3=03=0；a7=1;a7=1;数组是静态数据结构，其存储空间的大小需具体数组是静态数据结构，其存储空间的大小需具体确定，并确定，并预先分配预先分配，一旦分配则难以扩充。，一旦分配则难以扩充。顺序存储表示是实现数据结构的重要存储方式，顺序存储表示是实现数据结构的重要存储方式，一般借助数组来描述。一般借助数组来描述。2.3 2.3 链表链表课堂提要课堂提要课堂提要课堂提要第第第第2 2 2 2章章章章两种基本数据结构两种基本数据结构 2.1 2.1 结构与联合结构与联合2.2 2.2 数组数组2.3 2.3 链表链表2.3.1 2.3.1 指针指针 单链表单链表2.3

18、.3 2.3.3 双向双向链表链表2.3.4 2.3.4 循环循环链表链表2.3.1 2.3.1 指针指针C C语言中，指针语言中，指针(pointer)(pointer)也称为链也称为链(link)(link)。对任意类型对任意类型T T，都可定义指向该类型的指针类型。，都可定义指向该类型的指针类型。指针类型变量的值：是一个指针类型变量的值：是一个存储地址存储地址。int i,*pi;int i,*pi;与与指针类型相关的运算符：指针类型相关的运算符：取地址运算符取地址运算符&间接引用运算符间接引用运算符 *用来对指针变量所指示的变量进行操作。用来对指针变量所指示的变量进行操作。int i,

19、*pi;int i,*pi;pi=&i;pi=&i;i=5;i=5;printf(%d printf(%d，i);i);*pi=10;*pi=10;printf(%d printf(%d，*pi);*pi);变量变量i i 变量变量pi pi 254=254=5=102 2指针和数组指针和数组 C C语言中，任何在数组上执行的运算都可以使用指针实语言中，任何在数组上执行的运算都可以使用指针实现。现。C C语言规定语言规定数组名数组名代表数组的代表数组的首地址首地址(起始地址起始地址)。int*pint*pa;a;int*p=&a0;int*p=&a0;例如：例如：int a5;int a5;等

20、价等价【程序【程序2 21 1】数组和指针。数组和指针。int one5=0,1,2,3,4;int one5=0,1,2,3,4;void f(int*p,int n)void f(int*p,int n)int i;int i;printf(n*(p+i)printf(n*(p+i)：););for(i=0;in;i+)for(i=0;in;i+)printf(“%d ”,*(p+i);printf(“%d ”,*(p+i);*(p+i)+=2;*(p+i)+=2;void main()void main()int i;int i;f(one,5);f(one,5);printf(n*(o

21、ne+i):);printf(n*(one+i):);for(i=0;i5;i+)for(i=0;i NULL=NULL指针变量的指针变量的存储单元存储单元 firstfirst1.1.单链表的结点结构单链表的结点结构typedef struct nodetypedef struct node T Element;T Element;struct node*Link;struct node*Link;Node;Node;单链表的结点类型单链表的结点类型NodeNode用户自定义用户自定义的元素类型的元素类型typedef int Ttypedef int T；在在C C语言环境中，语言环境中，

22、元素类型元素类型T T必须由用户在应用时，必须由用户在应用时，用用typedeftypedef语句定义为具体的类型。语句定义为具体的类型。typedef struct entrytypedef struct entry int Key;int Key;char Data;char Data;Entry;Entry;typedef Entry T;typedef Entry T;（1 1）T*InputElement();T*InputElement();后置条件：已构造一个类型为后置条件：已构造一个类型为T T的新元素对象，并的新元素对象，并赋以所需的元素值，返回新元素对象的地址。赋以所需的元

23、素值，返回新元素对象的地址。（2 2）void PrintElement(T e)void PrintElement(T e)后置条件：输出元素后置条件：输出元素e e。两个重要运算两个重要运算【程序程序2 23 3】创建和显示元素。创建和显示元素。typedef int T;typedef int T;T*InputElement()T*InputElement()static T a;static T a;scanf(%d,&a);scanf(%d,&a);return&a;return&a;void PrintElement(T x)void PrintElement(T x)print

24、f(%d ,x);printf(%d ,x);返回返回a a的地址的地址【程序【程序2 24 4】构造新结点。构造新结点。#define IS_FULL(ptr)(!(ptr)#define IS_FULL(ptr)(!(ptr)Node*Node*NewNodeNewNode()()Node*p=(Node*)malloc(sizeof(Node);Node*p=(Node*)malloc(sizeof(Node);if(IS_FULL(p)if(IS_FULL(p)fprintf(stderr,The memory is fulln);fprintf(stderr,The memory i

25、s fulln);exit(1);exit(1);p-Link=NULL;p-Link=NULL;return p;return p;pNode*Node*NewNode1NewNode1()()Node*p=(Node*)malloc(sizeof(Node);Node*p=(Node*)malloc(sizeof(Node);if(IS_FULL(p)if(IS_FULL(p)fprintf(stderr,The memory is fulln);fprintf(stderr,The memory is fulln);exit(1);exit(1);p-Element=*InputElem

26、ent();p-Element=*InputElement();p-Link=NULL;p-Link=NULL;return p;return p;p1 1Node*Node*NewNode2NewNode2(T x)(T x)Node*p=(Node*)malloc(sizeof(Node);Node*p=(Node*)malloc(sizeof(Node);if(IS_FULL(p)if(IS_FULL(p)fprintf(stderr,The memery is fulln);fprintf(stderr,The memery is fulln);exit(1);exit(1);p-El

27、ement=x;p-Element=x;p-Link=NULL;p-Link=NULL;return p;return p;px x2.2.单链表类型单链表类型单链表类型单链表类型List:List:typedef Node*List;typedef Node*List;a a0 0a a1 1a a2 2a an-1n-1firstfirst非空单链表非空单链表List first;List first;类型类型ListList是指向是指向NodeNode类型变量的指针类型类型变量的指针类型q q插入时只要修改二个指针：插入时只要修改二个指针：q-link=p-link q-link=p-l

28、ink p-link=q p-link=q能否对调上述语句执行顺序？能否对调上述语句执行顺序？不能，会不能，会“断链断链”现象现象a ai-1i-1a ai ix xP Pa ai ia ai+1i+1x xq qp p“断链断链”现象现象将将q q插入插入P P之后之后:3.3.单链表的插入和删除单链表的插入和删除firstfirsta a0 0a a1 1a a2 2a an-1n-1x xq3.3.单链表的插入和删除单链表的插入和删除q-link=firstq-link=first；first=q;first=q;a ai ia ai+1i+1q qp pa ai-1i-1删除时只要修改

29、一个指针：删除时只要修改一个指针：q-link=p-link q-link=p-link删除删除p p：a a1 1a a2 2a an-1n-1firstfirsta a0 0p pfree(p)结点结点*q*q是结点是结点*p*p的前驱结点的前驱结点(predecessor)(predecessor)。在单链表中，。在单链表中，为了删除一个结点，我们必须知道它的前驱结点。为了删除一个结点，我们必须知道它的前驱结点。4.4.建立单链表建立单链表 【程序【程序2 25 5】建立单链表。】建立单链表。List BuildList()List BuildList()Node*p,*r=NULL,*

30、Node*p,*r=NULL,*first=NULLfirst=NULL;char c;char c;printf(Another element?y/n);printf(Another element?y/n);while(c=getchar()=n);while(c=getchar()=n);while(tolower(c)!=n)while(tolower(c)!=n)p=p=NewNode1NewNode1();();if(first!=NULL)r-Link=p;if(first!=NULL)r-Link=p;else first=p;else first=p;r=p;r=p;pri

31、ntf(Another element?y/n);printf(Another element?y/n);while(c=getchar()=n);while(c=getchar()=n);return first;return first;a0a0pfirstfirstr ra1a1firstfirst 5 5输出单链表输出单链表 【程序【程序2 26 6】输出单链表。输出单链表。void PrintList(List first)void PrintList(List first)printf(nThe list contains:n);printf(nThe list contains:

32、n);for(;first;first=first-Link)for(;first;first=first-Link)PrintElement(first-Element);PrintElement(first-Element);printf(nn);printf(nn);对于不同的元素类型用户可以设计对于不同的元素类型用户可以设计不同不同的的PrintElementPrintElement函函数，实现元素输出。数，实现元素输出。6.6.清空单链表清空单链表 【程序【程序2 27 7】清空单链表。清空单链表。List*List*是指向指针类型的指针类型是指向指针类型的指针类型a a1 1a a

33、2 2a a0 0p pvoid Clear(void Clear(List*List*first)first)Node*p=*first;Node*p=*first;while(*first)while(*first)p=(*first)-Link;p=(*first)-Link;free(*first);free(*first);*first=p;*first=p;typedef Node*List;typedef Node*List;q qfirstfirstList q;List q;List*first;List*first;2.3.3 2.3.3 带表头结点的单链表带表头结点的单链

34、表firstfirstfirstfirsta a0 0a a1 1a an-1n-1在单链表前增加一个结点，称为在单链表前增加一个结点，称为表头结点表头结点。表头结点的数据域表头结点的数据域EntryEntry不存放单链表的元素，它或者为空，不存放单链表的元素，它或者为空，或者用于存放实现算法所需的辅助数据。或者用于存放实现算法所需的辅助数据。头结点头结点:是单链表的起始结点是单链表的起始结点表头结点是添加的额外结点表头结点是添加的额外结点.注意：区分注意：区分“表头结点表头结点”和和“头结点头结点”，表头结点表头结点2.3.4 2.3.4 循环链表循环链表firstfirsta a0 0fi

35、rstfirsta a1 1a an-1n-1单循环链表是将单链表单循环链表是将单链表尾结点尾结点的指针域置为第一个的指针域置为第一个结点的地址，而不再是结点的地址，而不再是NULLNULL，这样从表中任一结点，这样从表中任一结点出发，均可访问到表中所有结点。出发，均可访问到表中所有结点。带带“表头结点表头结点”的单循环链表的单循环链表firstfirst a a0 0a a1 1a an-1n-1firstfirst从表中任一结点出发，均可访问到表中所有结点。从表中任一结点出发，均可访问到表中所有结点。2.3.5 2.3.5 双向链表双向链表 (1)(1)双向链表的结点结构双向链表的结点结构

36、lLink element rLinklLink element rLink双向链表的双向链表的每个结点的结构每个结点的结构具有如下定义的结构类具有如下定义的结构类型：型：typedef struct dnode typedef struct dnode T Element;T Element;struct dnode*RLink struct dnode*RLink，*LLink;*LLink;DNode;DNode;a a1 1a an-1n-12.3.5 2.3.5 双向链表双向链表 (2)(2)带表头结点的双向循环链表带表头结点的双向循环链表firstfirstfirstfirst空表

37、空表非空表非空表（3 3）双向链表的插入）双向链表的插入插入操作的核心步骤是：插入操作的核心步骤是：(1)DNode*q=NewNode2(x)(1)DNode*q=NewNode2(x)(2)q-llink=p-llink;q-rlink=p;(2)q-llink=p-llink;q-rlink=p;p-llink-rlink=qp-llink-rlink=q;p-llink=qp-llink=q a a1 1a an-1n-1 a a0 0 x xp pq q（4 4）双向链表的删除）双向链表的删除删除操作的核心步骤是：删除操作的核心步骤是：(1)p-llink-rlink=p-rlink

38、;(1)p-llink-rlink=p-rlink;p-rlink-llink=p-llink;p-rlink-llink=p-llink;=能否颠倒顺序？能否颠倒顺序？(2)free(p);(2)free(p);a a1 1a a2 2 a a0 0p p作作 业业P33 2-4 2-9 2-12void Invert(T elements,int length)/length数组长度 /elements为需要逆序的数组 T e;for(int i=1;i=length/2;i+)e=elementsi-1;elementsi-1=elementslength-i;elementslength-i=e;