《数据结构课件(c语言》由会员分享，可在线阅读，更多相关《数据结构课件(c语言（36页珍藏版）》请在金锄头文库上搜索。
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,&prior): (10)GetNext(*L,item,&next):,6,2.2.1 顺序表的定义 所谓顺序表，就是在内存中开辟一片连续的存储空间，将线性表中数据元素按照数据元素之间的逻辑顺序依次存放其中，需注
4、意的是该连续存储空间所能容纳的数据元素个数不得小于顺序表的长度。 在顺序表中，逻辑关系相邻的两个元素在物理位置上也相邻。线性表的顺序存储结构很容易确定每个数据元素在存储单元中起始地址的相对位置：假设线性表中元素为（a1,a2,ai-1,ai,ai+1,an），设第一个元素a1的内存地址为LOC(a1) ，而每个元素在计算机内占t个存贮单元,则第i个元素ai的首地址LOC(ai)为： LOC(ai)=LOC(a1)+(i-1)t (其中1in),2.2 线性表的顺序存储,7,例2.3 设有顺序表S，其描述如下： typedef struct char no10; char name20; flo
5、at grade3; float aver; Student; Student t30; 线性表中每个数据元素所占存储单元为10*1+20*1+3*4+1*4=46，假设顺序表中第一个数据元素的存储地址为d，则第i个数据元素的存储地址为d+(i-1)46。,8,由于顺序表的表长通常是可变的，因此可定义一个整型变量来记录表长，且需要定义一个足够大的数组来保存数据。 #define MAXSIZE maxlen typedef int elemtype; typedef struct elemtype dataMAXSIZE; int len; /*顺序表的长度*/ Sequenlist;,9,2
6、.2.2 顺序表的基本操作 (1)初始化顺序表InitList(*L): 算法说明: 创建一个空的顺序表，将该顺序表的表长设为零。 算法实现: Sequenlist *InitList(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中存储表
7、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
8、*/ return 1; ,11,else for(int j=i;j=len-1;j+) (*L).dataj-1=(*L).dataj; /*元素前移*/ (*L).len-; /*顺序表表长减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) ) /*删除元素位置设定不合适，删除操作失败*
9、/ printf(“Delete item failn”); return NULL; ,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;i=j;i+) /*匹配item的值*/ if( (*L).datai= =item ) return （i+1）; prin
10、tf(“The item is not in this sequenlist”); return 0; ,13,2.3 线性表的链式存储 线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在存储器中物理位置上也是相邻的，数据元素之间的邻接关系由存储单元的邻接关系来体现，通过数据元素与顺序表起始地址之间的相对位置，可方便的随机存取表中任一元素，但当插入、删除数据元素时，则需要移动大量数据元素。如何提高插入、删除数据元素的效率，本节将介绍线性表的另一种存储结构线性表的链式存储结构。 链式存储是通过动态分配存储单元来存储线性表中的元素，这些单元在物理上可以是连续的，也可以是不连续的。为了能正确
11、地描述元素之间的逻辑关系，除了存储元素本身的信息外，还需存储表示元素之间逻辑关系的信息。这两部分信息组成数据元素ai的存储映像，称为结点。在链表中，每个结点所占的存储空间分为两部分：存放数值的域称为数据域，存放结点之间相互关系的域称为指针域。跟据结点的连接方式不同，可分为单链表、双向链表、循环链表。,14,2.3.1 单链表 在定义的链表中，若每个结点除了存储数据元素本身信息的数据域外，只含有一个指针域用来存放其直接后继数据元素的存储地址，称这样的链表为单链表或线性链表。其结点结构如图所示:,15,用C语言描述单链表结点结构如下: typedef int elemtype; /*定义新类型，类
12、型名为elemtype*/ typedef struct node elemtype data; /*数据域*/ struct node *next; /*指针域*/ linklist;,16,在单链表中，第1个结点的指针域记录着第2个结点的地址，第2个结点的指针域记录着第3个结点的地址，以此类推，第n-1个结点的指针域记录着第n个结点的地址，第n个结点后再没有其他结点，则第n个结点的指针域为NULL。因此，单链表中结点之间的逻辑关系，是通过每个结点的指针域存储的该结点的直接后继结点的地址来体现的，即指针是数据元素之间逻辑关系的映像。 例2.4 线性表（A,B,C,D,E,F）的单链表物理存储
13、示意图及逻辑存储示意图如下：,17,例2.4 线性表（A,B,C,D,E,F）的单链表物理存储示意图及逻辑存储示意图如下：,18,单链表的有关操作如下： (1)初始化单链表InitList(*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
14、*L, *r, *p; InitList(L); /*构建头结点空间*/ r=L;,for(i=1;idata=x; pnext=NULL; rnext=p; r=rnext; /*指针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*/ t
15、data=item; if( Lnext= =NULL) if(i= =0) /*若L为空表且要求将新结点插入到第0个位置*/ Lnext=t; tnext=NULL; return (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的结点，插入操作失败*/ 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(
