数据结构课件(c语言)(2)

第2章线性表1第2章线性表2.1线性表的定义及其基本操作2.2线性表的顺序存储2.3线性表的链式存储2.4线性表的存储方式小结第2章线性表2线性结构是一种简单的数据结构。这种结构具有以下特点：在数据元素的非空有限集合中，有且只有一个“首”数据元素；有且只有一个“末”数据元素；除“首”数据元素外，其它数据元素有且只有一个直接前驱；除“末”数据元素外，其它数据元素有且只有一个直接后继。线性表属于线性结构的范畴，是最常用的数据结构。2.1线性表的定义及其基本操作第2章线性表3线性表（linearlist）是具有相同数据类型的n（n≥0）个数据元素a1，a2，…an组成的有限序列。其中n称为数据元素的个数或线性表的长度，当n=0时称为空表，n0时称为非空表。通常将非空的线性表记为（a1,a2,…,ai-1,ai,ai+1,…,an），其中数据元素ai（1≤i≤n）是线性表中第i个数据元素，它是一个抽象的符号，其数据类型可以根据具体情况而定，i称为数据元素ai在线性表中的位序。2.1.1线性表的定义第2章线性表•例2.1大写英文字母表：（A,B,C,D……,Y,Z），其中每个字母为一个数据元素，A是字母序列的“首”数据元素，Z是字母序列的“末”数据元素，其它每个字母有且只有一个直接前驱和一个直接后继，这个序列是一个线性表。•例2.2教师信息表，其中每位教师的有关信息为一个数据元素，所有教师的信息集合构成一个线性表。第2章线性表52.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):第2章线性表62.2.1顺序表的定义所谓顺序表，就是在内存中开辟一片连续的存储空间，将线性表中数据元素按照数据元素之间的逻辑顺序依次存放其中，需注意的是该连续存储空间所能容纳的数据元素个数不得小于顺序表的长度。在顺序表中，逻辑关系相邻的两个元素在物理位置上也相邻。线性表的顺序存储结构很容易确定每个数据元素在存储单元中起始地址的相对位置：假设线性表中元素为（a1,a2,…,ai-1,ai,ai+1,…,an），设第一个元素a1的内存地址为LOC(a1)，而每个元素在计算机内占t个存贮单元,则第i个元素ai的首地址LOC(ai)为：LOC(ai)=LOC(a1)+(i-1)×t(其中1≤i≤n)2.2线性表的顺序存储第2章线性表7•例2.3设有顺序表S，其描述如下：•typedefstruct•{•charno[10];•charname[20];•floatgrade[3];•floataver;•}Student;•Studentt[30];•线性表中每个数据元素所占存储单元为10*1+20*1+3*4+1*4=46，假设顺序表中第一个数据元素的存储地址为d，则第i个数据元素的存储地址为d+(i-1)×46。第2章线性表8•由于顺序表的表长通常是可变的，因此可定义一个整型变量来记录表长，且需要定义一个足够大的数组来保存数据。•#defineMAXSIZEmaxlen•typedefintelemtype;•typedefstruct•{•elemtypedata[MAXSIZE];•intlen;/*顺序表的长度*/•}Sequenlist;第2章线性表92.2.2顺序表的基本操作•(1)初始化顺序表InitList(*L):•算法说明:•创建一个空的顺序表，将该顺序表的表长设为零。•算法实现:•Sequenlist*InitList(Sequenlist*L)•{•L=(Sequenlist*)malloc(sizeof(Sequenlist));•L–len=0;•return(L);•}/*L为指向Sequenlist类型的指针变量*/第2章线性表10•(2)在顺序表中插入数据元素InsItem(*L,i,item):•intInsItem(sequenlist*L,inti,elemtypeitem)•/*(*L).data[0]中存储表L的第一个数据元素a1*/•{•intj;•if((*L).len=MAXSIZE)•/*表满，插入操作失败*/•{printf(“Thelistisoverflow.\n”);•returnNULL;•}•elseif((i1)||(i(*L).len+1))•/*插入位置设定不合适，插入操作失败*/•{printf(“Positionisnotcorrent.\n”);•returnNULL;•}•else•{for(j=(*L).len-1;j=i-1;j--)•(*L).data[j+1]=(*L).data[j];•(*L).data[i-1]=item;•(*L).len++;•/*顺序表表长增1*/•return1;•}•}第2章线性表11•else•{for(intj=i;j=len-1;j++)•(*L).data[j-1]=(*L).data[j];•/*元素前移*/•(*L).len--;•/*顺序表表长减1*/•return1;•}•}(3)在顺序表中删除数据元素DelItem(*L,i):•intDelItem(Sequenlist*L,inti)•{•intj;•if((*L).len==0)•/*表空，删除操作失败*/•{printf(“Listisempty\n”);•returnNULL;•}•elseif((i1)||(i(*L).len))•/*删除元素位置设定不合适，删除操作失败*/•{printf(“Deleteitemfail\n”);•returnNULL;•}第2章线性表12(4)定位查找LocItem(*L,item):•intLocItem(Sequenlist*L,intitem)•/*(*L).data[0]中存储表L的第一个数据元素a1*/•{•inti,j;•j=(*L).len;•if(j==0)/*表空，定位操作失败*/•{printf(“Thesequenlistisempty”);•return0;•}•for(i=0;i=j;i++)/*匹配item的值*/•if((*L).data[i]==item)•return（i+1）;•printf(“Theitemisnotinthissequenlist”);•return0;•}第2章线性表132.3线性表的链式存储•线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在存储器中物理位置上也是相邻的，数据元素之间的邻接关系由存储单元的邻接关系来体现，通过数据元素与顺序表起始地址之间的相对位置，可方便的随机存取表中任一元素，但当插入、删除数据元素时，则需要移动大量数据元素。如何提高插入、删除数据元素的效率，本节将介绍线性表的另一种存储结构——线性表的链式存储结构。•链式存储是通过动态分配存储单元来存储线性表中的元素，这些单元在物理上可以是连续的，也可以是不连续的。为了能正确地描述元素之间的逻辑关系，除了存储元素本身的信息外，还需存储表示元素之间逻辑关系的信息。这两部分信息组成数据元素ai的存储映像，称为结点。在链表中，每个结点所占的存储空间分为两部分：存放数值的域称为数据域，存放结点之间相互关系的域称为指针域。跟据结点的连接方式不同，可分为单链表、双向链表、循环链表。第2章线性表142.3.1单链表在定义的链表中，若每个结点除了存储数据元素本身信息的数据域外，只含有一个指针域用来存放其直接后继数据元素的存储地址，称这样的链表为单链表或线性链表。其结点结构如图所示:第2章线性表15•用C语言描述单链表结点结构如下:•typedefintelemtype;•/*定义新类型，类型名为elemtype*/•typedefstructnode•{•elemtypedata;/*数据域*/•structnode*next;/*指针域*/•}linklist;第2章线性表16在单链表中，第1个结点的指针域记录着第2个结点的地址，第2个结点的指针域记录着第3个结点的地址，以此类推，第n-1个结点的指针域记录着第n个结点的地址，第n个结点后再没有其他结点，则第n个结点的指针域为NULL。因此，单链表中结点之间的逻辑关系，是通过每个结点的指针域存储的该结点的直接后继结点的地址来体现的，即指针是数据元素之间逻辑关系的映像。例2.4线性表（A,B,C,D,E,F）的单链表物理存储示意图及逻辑存储示意图如下：第2章线性表17例2.4线性表（A,B,C,D,E,F）的单链表物理存储示意图及逻辑存储示意图如下：...BLAF^head第2章线性表18单链表的有关操作如下：•(1)初始化单链表InitList(*L):•linklist*InitList(linklist*L)•/*建立一个带头结点的单链表*/•{•L=(linklist*)malloc(sizeof(linklist));•L–next=NULL;•return(L);•}第2章线性表19•(2)建立单链表CreatList(n):•linklist*creatlist(intn)•{•intx,i;•/*设数据元素的类型为int*/•linklist*L,*r,*p;•InitList(L);•/*构建头结点空间*/•r=L;••for(i=1;i=n;i++)•/*循环构建n个结点*/•{printf(inputvalue:\n);•scanf(%d,&x);•p=(linklist*)malloc(sizeof(linklist));•p–data=x;•p–next=NULL;•r–next=p;•r=r–next;•/*指针r始终指向链表中末数据元素所在位置*/•}•return(L);•}第2章线性表20(3)在单链表中插入数据元素InsItem(*L,item,i):给定的序号来插入•InsItem(linklist*L,elemtypeitem,inti)•{•intj;•linklist*p;•p=L;•j=1;•t=(linklist*)malloc(sizeof(linklist));•/*生成新结点t*/•t–data=item;•if(L–next==NULL)•{if(i==0)•/*若L为空表且要求将新结点插入到第0个位置*/•{L–next=t;•t–next=NULL;•return(1);•}•elsereturn(0);•/*若L为空表且要求将新结点插入到第非0个位置，则操作失败*/•}•While((p–next!=NULL)&&(ji))•/*查找第i个结点*/•{p=p–next;•j++;}•if(p==NULL)•/*若没有第i个结点，则插入操作失败*/•{printf(“Thenode%disnotexist\n”,i);•return(0)；•}•else•/*若找到第i个结点，则在第i个结点前插入新结点*/•{t–next=p–next;•p–next=t;•return(1);•}}第2章线性表21(3)在单链表中插入数据元素InsItem(*L,item,i):按给定的值来插入•InsItem(linklist*L,elemtypeitem,elemtypek)•{•linklist*q,*p,*t;•t=(linklist*)malloc(sizeof(linklist));•/*生成新结点t*/•t–data=item;•if(L–next==NULL)•/*若为空表，则没有值为k的结点，插入操作失败*/•{printf(“Thelinkli