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

第2章 线性表 1 第2章 线性表 2.1 线性表的定义及其基本操作 2.2 线性表的顺序存储 2.3 线性表的链式存储 2.4 线性表的存储方式小结 第2章 线性表 2 线性结构是一种简单的数据结构。这种结构具有以 下特点：在数据元素的非空有限集合中，有且只有 一个“首”数据元素；有且只有一个 “末”数据元素； 除“首”数据元素外，其它数据元素有且只有一个直 接前驱；除“末”数据元素外，其它数据元素有且只 有一个直接后继。线性表属于线性结构的范畴，是 最常用的数据结构。 2.1 线性表的定义及其基本操作 第2章 线性表 3 线性表（linear list）是具有相同数据类型的n（n0）个数 据元素a1，a2，an组成的有限序列。其中n 称为数据元 素的个数或线性表的长度，当n=0时称为空表，n0时称为 非空表。通常将非空的线性表记为（a1,a2,ai- 1,ai,ai+1,an），其中数据元素ai（1in）是线性表中第 i个数据元素，它是一个抽象的符号，其数据类型可以根据 具体情况而定，i称为数据元素ai在线性表中的位序。 2.1.1 线性表的定义 第2章 线性表 例2.1 大写英文字母表：（A,B,C,D,Y,Z），其中 每个字母为一个数据元素，A是字母序列的“首”数据元 素，Z是字母序列的“末”数据元素，其它每个字母有且 只有一个直接前驱和一个直接后继，这个序列是一个 线性表。 例2.2 教师信息表，其中每位教师的有关信息为一个数 据元素，所有教师的信息集合构成一个线性表。 第2章 线性表 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，假设顺序表中第一个数据元素的 存储地址为d，则第i个数据元素的存储地址为d+(i-1)46。 第2章 线性表 8 由于顺序表的表长通常是可变的，因此可定义 一个整型变量来记录表长，且需要定义一个足 够大的数组来保存数据。 #define MAXSIZE maxlen typedef int elemtype; typedef struct elemtype dataMAXSIZE; int len; /*顺序表的长度*/ Sequenlist; 第2章 线性表 9 2.2.2 顺序表的基本操作 (1)初始化顺序表InitList(*L): 算法说明: 创建一个空的顺序表，将该顺序表的表长设为零。 算法实现: Sequenlist *InitList(Sequenlist *L) L=( Sequenlist *)malloc(sizeof(Sequenlist); Llen=0; return(L); /*L为指向Sequenlist类型的指针变量*/ 第2章 线性表 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”); 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; 第2章 线性表 11 else for(int j=i;j(*L).len) ) /*删除元素位置设定不合适，删除操作失败*/ printf(“Delete item failn”); return NULL; 第2章 线性表 12 (4)定位查找LocItem(*L,item): int LocItem(Sequenlist *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;inext=NULL; return(L); 第2章 线性表 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; /*指针r始终指向链表中末数据元素所在位 置*/ return(L); 第2章 线性表 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; return (1); else return(0); /*若L为空表且要求将新结点插入到第非0个位置， 则操作失败*/ While(pnext!=NULL) j+; if(p= =NULL) /*若没有第i个结点，则插入操作失败*/ printf(“The node %d is not existn”,i); return(0)； else /*若找到第i个结点，则在第i个结点前插入新结点*/ tnext=pnext; pnext= t; return(1); 第2章 线性表 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的结点，插入操作失败 */ 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); 第2章 线性表 22 (4) 在单链表中删除数据元素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) j+; if(p= =NULL) /*若没有第i个结点，则删除操作失败*/ printf(“The node %d is not existn”,i); return(0)； else /*若找到第i个结点，则删除并释放第i个结 点*/ q=pnext; pnext= pnextnext; free(q); return(1); 第2章 线性表 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=pnext; 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); 第2章 线性表 24 2.3.2 双向链表 在单链表中，我们可以方便的访问其中某个结点的后继结点，这是因为 单链表的结点结构中有一个指针域用来记录结点的后继结点地址，但要 想访问某个结点的前驱结点时，则要从头结点开始，顺链查找，这样效 率太低，可以通过使用双向链表来提高效率。所谓双向，是指其结点结 构中包含两个指针域，分别记录相应结点的直接前驱结点地址和其直接 后继结点地址，如图所示: 前驱指针 域 数据域后继指针 域 第2章 线性表 25 用C语言描述单链表结点结构如下: typedef int elemtype; /*定义新类型，类型名为elemtype*/ typedef struct double_node elemtype data; /*数据域*/ struct double_node *prior,*next; /*前驱指针域, 后继指针域*/ double_linklist; 第2章 线性表 26 例2.5 线性表（A,B,C,D,E,F）的双向链表物理存储示意图及逻辑存储示意 图如下： 第2章 线性表 27 (1)初始化双向链表InitDouList(*L): double_linklist *InitDouList(double_linklist *L) /*建立一个带头结点的双向链表*/ L=( double_linklist *)malloc(sizeof(double_ linklist); Lprior=NULL; Lnext=NULL; return(L); 第2章 线性表 28 (2) 在双向链表中插入数据元素InsDouItem(*L, item, i): 第2章 线性表 29 (3) 在双向链表中删除数据元素DeleDouItem(*L, item, i): 第2章 线性表 30 2.3.3 循环链表 循环链表是一种首尾相接的链式存储结构。在这种存储结构中 ，每一个结点的指针域都记录着它的下一个结点的地址，最 后一个结点的指针域记录头结点的地址，使链表链接呈环状 ，这样的链表就称之为单循环链表，如图2.9所示；与单循 环链表类似，将双向链表中尾结点的后继指针域记录链表的 头结点的地址，头结点的前驱指针域记录尾结点的地址，即 构造了双向循环链表，如图2.10所示。在循环链表中，从任 意一个结点出发均可访问到表中其他结点。 第2章 线性表 31 第2章 线性表 32 例2.6：已知L1和L2分别为两个单循环链表的头指针。试遍写一算法将链表L2连接在链表 L1的后面，连接后形成的单循环链表头指针为L1。 linklist *Combination(linklist *L1, 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); 第2章 线性表 33 2.3.4 静态链表 以上我们提到的线性表的各种链式存储结构，都是根据需要动态分配及释 放其结点所占的内存空间，这种链表称为动态链表。还有一种链表叫作静 态链表，与动态链表的区别在于静态链表需要预先分配一个较大的空间， 以备以后需求。因此，静态链表可用一维数组来实现，其基本结构为: #define MAXSIZE maxlen typedef int elemtype; /*定义新类型，类型名为elemtype*/ typedef struct SeqLinkList elemtype data; /*数据域*/ int next; /*下标指针域*/ SLListMAXSIZE; 第2章 线性表 34 例2.6线性表（A,B,C,D,E,F）的静态链表存储示意图如