数据结构课件(c语言).ppt

1、1,第2章 线性表,2.1 线性表的定义及其基本操作 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的存储方式小结,2,线性结构是一种简单的数据结构。这种结构具有以下特点：在数据元素的非空有限集合中，有且只有一个“首”数据元素；有且只有一个 “末”数据元素；除“首”数据元素外，其它数据元素有且只有一个直接前驱；除“末”数据元素外，其它数据元素有且只有一个直接后继。线性表属于线性结构的范畴，是最常用的数据结构。,2.1 线性表的定义及其基本操作,3,线性表（linear list）是具有相同数据类型的n（n0）个数据元素a1，a2，an组成的有限序列。其中n 称为数据元素的个

2、数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1,a2,ai-1,ai,ai+1,an），其中数据元素ai（1in）是线性表中第i个数据元素，它是一个抽象的符号，其数据类型可以根据具体情况而定，i称为数据元素ai在线性表中的位序。,2.1.1 线性表的定义,例2.1 大写英文字母表：（A,B,C,D,Y,Z），其中每个字母为一个数据元素，A是字母序列的“首”数据元素，Z是字母序列的“末”数据元素，其它每个字母有且只有一个直接前驱和一个直接后继，这个序列是一个线性表。 例2.2 教师信息表，其中每位教师的有关信息为一个数据元素，所有教师的信息集合构成一个线性表

3、。,5,2.1.2 线性表的基本操作 (1)InitList(*L): (2)InsItem(*L,i,item): (3)DelItem(*L,i): (4)ClearList(*L): (5)ListEmpty(*L): (6)LenList(*L): (7)LocItem(*L,item): (8)GetItem(*L,i,item): (9)GetPrior(*L,item, char name20; float grade3; float aver; Student; Student t30; 线性表中每个数据元素所占存储单元为10*1+20*1+3*4+1*4=46，假设顺序表中第

4、一个数据元素的存储地址为d，则第i个数据元素的存储地址为d+(i-1)46。,8,由于顺序表的表长通常是可变的，因此可定义一个整型变量来记录表长，且需要定义一个足够大的数组来保存数据。 #define MAXSIZE maxlen typedef int elemtype; typedef struct elemtype dataMAXSIZE; int len; /*顺序表的长度*/ Sequenlist;,9,2.2.2 顺序表的基本操作 (1)初始化顺序表InitList(*L): 算法说明: 创建一个空的顺序表，将该顺序表的表长设为零。 算法实现: Sequenlist *InitLi

5、st(Sequenlist *L) L=( Sequenlist *)malloc(sizeof(Sequenlist); Llen=0; return(L); /*L为指向Sequenlist类型的指针变量*/,10,(2)在顺序表中插入数据元素InsItem(*L,i,item): int InsItem (sequenlist *L, int i, elemtype item) /*(*L).data0中存储表L的第一个数据元素a1*/ int j; if( (*L).len= MAXSIZE) /*表满，插入操作失败*/ printf(“The list is overflow.n”)

6、; return NULL; else if( (i(*L).len+1) ) /*插入位置设定不合适，插入操作失败*/ printf(“Position is not corrent.n”); return NULL; ,else for(j=(*L).len-1;j=i-1;j-) (*L).dataj+1=(*L).dataj; (*L).datai-1= item; (*L). len+; /*顺序表表长增1*/ return 1; ,11,else for(int j=i;j=len-1;j+) (*L).dataj-1=(*L).dataj; /*元素前移*/ (*L).len-;

7、 /*顺序表表长减1*/ return 1; ,(3) 在顺序表中删除数据元素DelItem(*L,i): int DelItem (Sequenlist *L, int i) int j; if(*L).len= =0) /*表空，删除操作失败*/ printf(“List is empty n”); return NULL; else if( (i(*L).len) ) /*删除元素位置设定不合适，删除操作失败*/ printf(“Delete item failn”); return NULL; ,12,(4)定位查找LocItem(*L,item): int LocItem(Seque

8、nlist *L,int item) /*(*L).data0中存储表L的第一个数据元素a1*/ int i,j; j=(*L).len; if(j= =0) /*表空，定位操作失败*/ printf(“The sequenlist is empty”); return 0; for(i=0;i=j;i+) /*匹配item的值*/ if( (*L).datai= =item ) return （i+1）; printf(“The item is not in this sequenlist”); return 0; ,13,2.3 线性表的链式存储 线性表的顺序存储结构的特点是逻辑关系上相邻

9、的两个数据元素在存储器中物理位置上也是相邻的，数据元素之间的邻接关系由存储单元的邻接关系来体现，通过数据元素与顺序表起始地址之间的相对位置，可方便的随机存取表中任一元素，但当插入、删除数据元素时，则需要移动大量数据元素。如何提高插入、删除数据元素的效率，本节将介绍线性表的另一种存储结构线性表的链式存储结构。 链式存储是通过动态分配存储单元来存储线性表中的元素，这些单元在物理上可以是连续的，也可以是不连续的。为了能正确地描述元素之间的逻辑关系，除了存储元素本身的信息外，还需存储表示元素之间逻辑关系的信息。这两部分信息组成数据元素ai的存储映像，称为结点。在链表中，每个结点所占的存储空间分为两部分

10、：存放数值的域称为数据域，存放结点之间相互关系的域称为指针域。跟据结点的连接方式不同，可分为单链表、双向链表、循环链表。,14,2.3.1 单链表 在定义的链表中，若每个结点除了存储数据元素本身信息的数据域外，只含有一个指针域用来存放其直接后继数据元素的存储地址，称这样的链表为单链表或线性链表。其结点结构如图所示:,15,用C语言描述单链表结点结构如下: typedef int elemtype; /*定义新类型，类型名为elemtype*/ typedef struct node elemtype data; /*数据域*/ struct node *next; /*指针域*/ linkli

11、st;,16,在单链表中，第1个结点的指针域记录着第2个结点的地址，第2个结点的指针域记录着第3个结点的地址，以此类推，第n-1个结点的指针域记录着第n个结点的地址，第n个结点后再没有其他结点，则第n个结点的指针域为NULL。因此，单链表中结点之间的逻辑关系，是通过每个结点的指针域存储的该结点的直接后继结点的地址来体现的，即指针是数据元素之间逻辑关系的映像。 例2.4 线性表（A,B,C,D,E,F）的单链表物理存储示意图及逻辑存储示意图如下：,17,例2.4 线性表（A,B,C,D,E,F）的单链表物理存储示意图及逻辑存储示意图如下：,18,单链表的有关操作如下： (1)初始化单链表Init

12、List(*L): linklist *InitList(linklist *L) /*建立一个带头结点的单链表*/ L=( linklist *)malloc(sizeof(linklist); Lnext=NULL; return(L); ,19,(2)建立单链表CreatList(n): linklist *creatlist(int n) int x,i; /*设数据元素的类型为int*/ linklist *L, *r, *p; InitList(L); /*构建头结点空间*/ r=L;,for(i=1;idata=x; pnext=NULL; rnext=p; r=rnext; /

13、*指针r始终指向链表中末数据元素所在位置*/ return(L); ,20,(3) 在单链表中插入数据元素InsItem(*L, item, i): 给定的序号来插入 InsItem ( linklist *L, elemtype item, int i) int j; linklist *p; p=L; j=1; t=(linklist *)malloc(sizeof(linklist); /*生成新结点t*/ tdata=item; if( Lnext= =NULL) if(i= =0) /*若L为空表且要求将新结点插入到第0个位置*/ Lnext=t; tnext=NULL; retur

14、n (1); else return(0); /*若L为空表且要求将新结点插入到第非0个位置，则操作失败*/ ,While(pnext!=NULL) ,21,(3) 在单链表中插入数据元素InsItem(*L, item, i): 按给定的值来插入 InsItem ( linklist *L, elemtype item, elemtype k) linklist *q,*p,*t; t=(linklist *)malloc(sizeof(linklist); /*生成新结点t*/ tdata=item; if( Lnext= =NULL) /*若为空表，则没有值为k的结点，插入操作失败*/

15、printf(“The linklist is emptyn”); return(0); else q=L; p=Lnext; while (p!=NULL) /*查找值为k的结点*/ if (pdata!=k) q=p; p=pnext; ,else break; if( p= =NULL) /*如p= =NULL，则没有值为k的结点，插入操作失败*/ printf(“The node %d is not existn”,k); return(0); else /*若找到值为k的结点，则在值为k的结点前插入新结点*/ qnext=t; tnext=p; return(1); ,22,(4)

16、在单链表中删除数据元素DelItem(*L, i): DelItem ( linklist *L, int i) /*删除给定序号的结点*/ int j; linklist *p; p=L; j=1; if( Lnext= =NULL) /*L为空表，无结点可删除*/ printf(“The linklist is empty.n”); return(0); While(pnext!=NULL) ,if(p= =NULL) /*若没有第i个结点，则删除操作失败*/ printf(“The node %d is not existn”,i); return(0)； else /*若找到第i个结点

17、，则删除并释放第i个结点*/ q=pnext; pnext= pnextnext; free(q); return(1); ,23,删除给定值的结点 DelItem ( linklist *L, elemtype item) linklist *q,*p,*t; if( Lnext= =NULL) /*若为空表，则没有值为item的结点，删除操作失败*/ printf(“The linklist is emptyn”); return(0); else q=L; p=Lnext; while (p!=NULL) /*查找值为item的结点*/ if (pdata!=item) q=p; p=p

18、next; ,else break; if( p= =NULL) /*如p= =NULL，则没有值为item的结点，删除操作失败*/ printf(“The node %d is not existn”,k); return(0); else /*若找到值为item的结点，则删除并释放该结点*/ qnext=pnext; free(p); return(1); ,24,2.3.2 双向链表,在单链表中，我们可以方便的访问其中某个结点的后继结点，这是因为单链表的结点结构中有一个指针域用来记录结点的后继结点地址，但要想访问某个结点的前驱结点时，则要从头结点开始，顺链查找，这样效率太低，可以通过使用

19、双向链表来提高效率。所谓双向，是指其结点结构中包含两个指针域，分别记录相应结点的直接前驱结点地址和其直接后继结点地址，如图所示:,25,用C语言描述单链表结点结构如下: typedef int elemtype; /*定义新类型，类型名为elemtype*/ typedef struct double_node elemtype data; /*数据域*/ struct double_node *prior,*next; /*前驱指针域, 后继指针域*/ double_linklist;,26,例2.5 线性表（A,B,C,D,E,F）的双向链表物理存储示意图及逻辑存储示意图如下：,27,(1

20、)初始化双向链表InitDouList(*L): double_linklist *InitDouList(double_linklist *L) /*建立一个带头结点的双向链表*/ L=( double_linklist *)malloc(sizeof(double_ linklist); Lprior=NULL; Lnext=NULL; return(L); ,28,(2) 在双向链表中插入数据元素InsDouItem(*L, item, i):,29,(3) 在双向链表中删除数据元素DeleDouItem(*L, item, i):,30,2.3.3 循环链表 循环链表是一种首尾相接的链

21、式存储结构。在这种存储结构中，每一个结点的指针域都记录着它的下一个结点的地址，最后一个结点的指针域记录头结点的地址，使链表链接呈环状，这样的链表就称之为单循环链表，如图2.9所示；与单循环链表类似，将双向链表中尾结点的后继指针域记录链表的头结点的地址，头结点的前驱指针域记录尾结点的地址，即构造了双向循环链表，如图2.10所示。在循环链表中，从任意一个结点出发均可访问到表中其他结点。,31,32,例2.6：已知L1和L2分别为两个单循环链表的头指针。试遍写一算法将链表L2连接在链表L1的后面，连接后形成的单循环链表头指针为L1。 linklist *Combination(linklist *L

22、1, linklist *L2) linklist *p, *q; p=L1next; q=L2next; while(pnext!=L1) p=pnext; while(qnext!=L2) q=qnext; p=L2next; qnext=L1; free(L2); return(L1); ,33,2.3.4 静态链表 以上我们提到的线性表的各种链式存储结构，都是根据需要动态分配及释放其结点所占的内存空间，这种链表称为动态链表。还有一种链表叫作静态链表，与动态链表的区别在于静态链表需要预先分配一个较大的空间，以备以后需求。因此，静态链表可用一维数组来实现，其基本结构为: #define MAXSIZE maxlen typedef int elemtype; /*定义新类型，类型名为el