第2章 线性表.doc

第二章 线性表一、线性表的基本概念1、定义线性表（Linear List）：是由n(n0)个性质相同的数据元素组成的有限序列，记为(a1,a2,a3,an)。 表中数据元素的个数n定义为线性表的长度。n=0的表称为空表，即该线性表不包含任何数据元素。这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。例1、26个英文字母组成的字母表（A，B，C、Z）是一个线性表。例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况表也是一个线性表。（6，17，28，50，92，188） 2、线性表的逻辑特征从以上的定义及例子可以看出，线性表具有以下逻辑特征：1）在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；2）有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋a n-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋a i-1和一个直接后继ai+1。线性表是一种典型的线性结构。二、线性表的存储结构（一）顺序存储结构1、概念及特点顺序表：即用一组连续的存储单元依次存放线性表的数据元素。若每个数据元素占用k个存储单元，并以所占的第一个存储单元地址作为这个数据元素的存储位置，则表中任一元素ai的存储地址为：LOC(ai)=LOC(a1)+(i-1)*k(n为结点总数，1in)Loc(a1)Loc(a2)=Loc(a1)+kLoc(ai)=Loc(a1)+(i-1)*kLoc(an)=Loc(a1)+(n-1)*ka1a2aian顺序表的特点：表中相邻的元素ai和ai+1有相邻的存储位置LOC(ai)和LOC(ai+1)。即顺序表中各数据元素在存储空间中是按逻辑顺序依次存放的，如下图：2、顺序表的结构类型定义/*顺序表的定义：*/#define ListSize 100/*表空间大小可根据实际需要而定，这里假设为100*/typedef int DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef structDataType dataListSize;/*向量data用于存放表结点*/int length;/*当前的表长度*/SeqList;3、顺序表的基本运算主要包括：顺序表的查找、插入及删除。1）顺序表的建立及打印算法/*顺序表的建立：*/void CreateList(SeqList *L,int n)int i; for (i=0;idatai);L-length=n;/*顺序表的打印：*/void PrintList(SeqList L,int n)int i;for (i=0;in;i+)printf(%d ,L.datai);printf(n);2）、顺序表的查找算法/*顺序表的查找：*/int LocateList(SeqList L,DataType x)int i=0;while (iL.length & L.datai!=x) +i;if (iL.length) return i+1;/*找到返回该值的位置*/else return 0;/*找不到返回0*/查找过程可以参看“线性表的查找.swf” 动画文件。3）、顺序表的插入算法顺序表的插入运算是指在表的第i(1in+1个位置上，插入一个新结点x，使长度为n的线性表 (a1，a i-1，ai，an)变成长度为n+1的线性表 (a1，a i-1，x，ai，an)算法如下：/*顺序表的插入：*/void InsertList(SeqList *L,DataType x,int i)/*将新结点x插入L所指的顺序表的第i个结点的位置上*/int j;if (iL-length+1)printf(插入位置非法n);exit(0);if (L-length=ListSize)printf(表空间溢出，退出运行n);exit(0);for (j=L-length-1;j=i-1;j-)L-dataj+1=L-dataj;/*从表尾元素到第i个元素逐个后移*/L-datai-1=x;/*新元素插入*/L-length+;/*修正表长*/插入过程可以参看“线性表的插入.swf” 动画文件。4）顺序表的删除算法线性表的删除运算是指将表的第i(1in)结点删除，使长度为n的线性表： (a1，a i-1，ai，a i+1，an)变成长度为n-1的线性表 (a1，a i-1，a i+1，an)算法如下：/*顺序表的删除：*/void DeleteList(SeqList *L,int i)/*从L所指的顺序表中删除第i个结点*/int j;if (L-length=0)printf(线性表为空，退出运行n);exit(0);if (iL-length)printf(删除位置非法n);exit(0);for (j=i;jlength-1;j+)L-dataj-1=L-dataj;/*将第i+1个元素之后的所有元素向前移动*/L-length-;/*修正表长*/删除过程可以参看“线性表的删除.swf”动画文件。4、顺序表基本算法的效率分析插入运算效率分析：该算法的时间主要花费在循环的结点后移语句上。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。最好情况是：当在结点最后插入时，结点不用后移，其时间复杂度O（1）；最坏情况是：在第一个前面插入，结点后移语句将循环执行n次，需移动表中所有结点，时间复杂度为O（n）。在顺序表上做插入运算，平均要移动表中一半结点。当表长 n较大时，算法的效率相当低。删除运算效率分析：同插入运算相同，即最好情况是：删除最后一个结点时，结点不用移动，其时间复杂度O（1）；最坏情况是：删除第一个结点时，结点后移语句将循环执行n次，需移动表中所有结点，时间复杂度为O（n）。算法的平均时间复杂度为O(n)（二）链式存储结构线性链表线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点，下面介绍的链式存储结构可以避免大量结点的移动。1、链式存储结构每个结点由两部分组成：数据域和指针域。如下图：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称为指针（pointer）或链（link）。链表(Linked List)：线性表的链式存储结构称为链表。它是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序通过链表中的指针链接次序实现的。链表的第一个结点被称为头结点（front）或表头。 指向头结点的指针被称为头指针（head）。链表的最后一个结点被称为尾结点（rear）。2、单链表（Single Linked）若链表中每个结点只包含一个指针域，则称此链表为单链表。单链表的特点：第一个结点无前驱，最后一个结点无后继，若表为空，则head=NULL。例如：下面是线性表:(bat，cat，eat，fat，hat，jat，lat，mat)用单链表存储时的结构示意图：headbat cateatmat 165130205200170160135110160lat205jat110fat130batNullmat170eat135cat200hatHead=1651）单链表的逻辑结构单链表的逻辑结构如下图：heada1 a2an 带头结点结构：heada1 a2an 此时，在头结点的数据域中不存储任何信息。2）单链表的类型定义/*单链表的定义：*/typedef char DataType;/*DataType可以是任何相应的数据类型如int, float或char*/typedef struct node/*结点类型定义*/DataType data;/*结点的数据域*/struct node *next;/*结点的指针域*/ListNode;typedef ListNode *LinkList;在C中，链结点变量的动态生成方法：S=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/它表示，通过函数malloc分配一个类型为ListNode的结点变量的空间，并将其始地址放入指针变量S中。3）单链表的基本运算算法单链表的建立头插法：基本思想：从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。算法如下：/*单链表的建立（无头结点）：*/LinkList CreateListF_Nohead(void)char ch;LinkList head;/*头指针*/ListNode *s;/*工作指针*/head=NULL;/*链表开始为空*/ch=getchar();while (ch!=n)s=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/s-data=ch;s-next=head;head=s;ch=getchar();return head;/*返回头指针*/*单链表的建立(有头结点)：*/LinkList CreateListF_head(void)char ch;LinkList head,s;/*生成头结点*/s=(ListNode *)malloc(sizeof(ListNode);head=s;s-next=NULL;printf(请连续输入字符，按*号结束：);printf(n);while (ch=getchar()!=*)s=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/s-data=ch;s-next=head-next;head-next=s;return head;/*返回头指针*/尾插法：/*单链表的建立（无头结点）：*/LinkList CreateListR_Nohead(void)char ch;LinkList head;/*头指针*/ListNode *s,*r;/*工作指针*/head=NULL;/*链表开始为空*/r=NULL;/*链表尾指针开始为空*/while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/s-data=ch;if (head=NULL)head=s;/*新结点插入空表*/else r-next=s;r=s;if (r!=NULL)r-next=NULL;/*对于非空表，将尾结点指针域置空*/return head;/*返回头指针*/*单链表的建立(有头结点)：*/LinkList CreateListR_head(void)char ch;LinkList head=(ListNode *)malloc(sizeof(ListNode);ListNode *s,*r;r=head;/*尾指针初值指向头结点*/while (ch=getchar()!=n)s=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/s-data=ch;r-next=s;r=s;r-next=NULL;return head;/*返回头指针*/单链表的打印带头结点的打印算法：void PrintList_head(LinkList head)ListNode *p;for(p=head-next;p;p=p-next)printf(%c,p-data);printf(n);不带头结点的打印算法：void PrintList_Nohead(LinkList head) ListNode *p;for(p=head;p;p=p-next) printf(“%c”,p-data); printf(“n”);单链表的查找按序号查找：在链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点，则返回该结点的地址，否则，返回NULL。链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1in时，i的值是合法的。算法如下：LinkList GetNode(LinkList head,int i)/*在带头结点的单链表head中查找第i个结点*/int j;ListNode *p;p=head;j=0;/*从头结点开始扫描*/while (p-next & jnext;j+;if (i=j)return p;/*找到了第i个结点*/elsereturn NULL;按值查找：按值查找是在链表中，查找是否有结点值等于给定值key的结点，若有的话，则返回首次找到的其值为key的结点的存储位置；否则返回NULL。查找过程从开始结点出发，顺着链表逐个将结点的值和给定值key作比较。算法如下：LinkList LocateNode(LinkList head,DataType key)/*在带头结点的单链表head中查找其值为key的结点*/ListNode *p=head-next;/*从开始结点比较*/while (p&p-data!=key)/*直到p为NULL或p-data是key为止*/p=p-next;/*扫描下一结点*/return p;单链表的插入插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入到ai-1与ai之间。因此，我们必须首先找到ai-1的存储位置p，然后生成一个数据域为x的新结点*p，并令结点*p的指针域指向新结点，新结点的指针域指向结点ai。从而实现三个结点ai-1，x和ai之间的逻辑关系的变化。算法如下：void InsertList(LinkList head,DataType x,int i)/*将值为x的新结点插入到带头结点的单链表head的第i个结点的位置上*/ListNode *p,*s;p=GetNode(head,i-1);/*寻找第i-1个结点*/if(p=NULL)printf(插入位置非法n);exit(0);s=(ListNode *)malloc(sizeof(ListNode);/*生成新结点*/s-data=x;s-next=p-next;p-next=s;单链表的删除删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点a i-1的指针域next中，所以我们必须首先找到a i-1的存储位置p。然后令pnext指向ai的直接后继结点，即把ai从链上摘下。最后释放结点ai的空间。算法如下：void DeleteList(LinkList head,int i)/*删除带头结点的单链表中的第i个结点*/ListNode *p,*r;p=GetNode(head,i-1);/*寻找第i-1个结点*/if(p=NULL|p-next=NULL)printf(删除位置非法n);exit(0);r=p-next;p-next=r-next;free(r);/*释放第i个结点*/4）单链表算法的效率分析单链表的插入、删除、查找算法的平均时间复杂度均为O(n)。3、循环链表（Circular Linked List）就是将单向链表中的最后一个结点的指针指向链表中第一个结点，使整个链表构成一个环形。循环链表是一种头尾相接的链表。其特点是无须增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向表头结点的或开始结点，就得到了单链形式的循环链表，并简单称为单循环链表。heada1 a2an 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：非空循环链表head空循环链表循环链表的运算和单链表基本一致，差别在于：当需要从头到尾扫描整个链表时，是否到表尾的条件不同。对循环链表来说，只要将条件“p-next!=NULL”（或p-next）改为“p-next!=head”即可。4、双链表(Double linked list)双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样就形成的链表中有两个方向不同的链，故称为双向链表。双链表特点：双链表的每一个结点除含数据域外，还有两个指针域，一个指针指向其前驱结点