《《C语言和Java语言描述》02 线性表》由会员分享，可在线阅读，更多相关《《C语言和Java语言描述》02 线性表（46页珍藏版）》请在金锄头文库上搜索。
1、,数据结构与算法,第二章线性表,目录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,目录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,线性表的定义,定义,由n(n)个相同类型数据元素(结点)a1，a2，an组成的有限序列。(a1，a2，an)其中：n：数据元素的个数，也称表的长度。空表：n=0，记为（）,举例,由26个英文字母构成的表（a,b,c,z）是一个线性表；由全体职工的基本工资构成的表（1236.60,1669.80,
2、900.00,890.00,1842.00）是线性表。我们常常玩的扑克牌，其数据元素牌，是由牌点、花色两项组成的，是复合数据类型，这种类型的线性表称为复合线性表。,数据结构与算法,线性表的定义,数据结构与算法,在非空的线性表，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1。,线性表的特征,线性表的定义,求表长求线性表中元素的个数。遍历从左到右（或从右到左）扫描（或读取）表中的各元素。按编号查找找出表中第i个元素。按特征查找
3、按某个特定值查找线性表。插入在第i个位置上（即原第i个元素前）插入一新元素。删除删除原表中的第i个元素。排序按元素某特征值的递增（或递减）排序，重排表中各元素。,线性表的基本运算,数据结构与算法,目录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,顺序表的定义,数据结构与算法,顺序表：把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。特点：逻辑上相邻的数据元素，其物理（存储）位置也是相邻的。,LOC(ai)=LOC(ai-1)+k,LOC(ai)=b+(i-1)k,顺
4、序表的定义,数据结构与算法,由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。,顺序表的定义,MaxSize-1,备用空间,有效结点,顺序表的定义,数据结构与算法,GetLength()：求顺序表中元素的个数PrintList()：遍历一个顺序表GetElem(inti)：按编号查找Locate(objecte)：按特征查找InsertList(inti,objecte)：在顺序表中插入一个元素DeleteList(inti)：从顺序表中删除一个元素,基于顺序表的运算的实现,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,intLocate(SeqListl，El
5、emTypee)/*在顺序表l中查找元素e，若l.elemi=e，则找到该元素，并返回i，若找不到，返回-1*/i=0;while(i=l.listlength-1)/*Locate*/,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,/*在顺序表l中第i（i应视作数组的下标）个数据元素之前插入元素e*/voidInsList(SeqList*l,inti,ElemTypee)if(i=l-listlength)/*判断插入位置是否合法*/printf(“Error”)；if(l-listlength=MaxSize-1)/*判断表是
6、否已满*/printf(“Overflow”)；return;for(k=l-listlength-1;k=i;k-)/*将元素elemlistlength-1.i依次向后移动一个单元*/l-elemk+1=l-elemk;l-elemi=e;l-listlength+;,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,删除l中的第i个数据元素（DelList(l,i)），使得线性表(a1,ai-1,ai,an)改变为(a1,，ai-1,ai+1,an)。即：改变了线性表中元素之间的关系，使和改变为，同时表长减1。,顺序表的定义,数据结构与算法,基于顺序表的运算的实现,/*在顺序表l中删
7、除第i（i应视作数组的下标）个数据元素*/voidDelList(SeqList*l,inti)if(il-listlength-1)/*判断删除位置是否合法*/printf(Error)；return;for(k=i+1;ilistlength-1;k+)l-elemk-1=l-elemk;/*将第i个数据元素后面的元素依次前移*/l-listlength-;,目录,线性表的定义,顺序线性表,线性表的链式存储,第一节,第二节,第三节,CONTENTS,循环单链表和双向链表,第四节,实训,第五节,线性表的链式表示和实现,数据结构与算法,1.单链表的结构,线性表的链式表示和实现,数据结构与算法,
8、2.基本操作在带头结点单链表第一个数据元素前插入结点,线性表的链式表示和实现,数据结构与算法,2.基本操作删除带头结点单链表第一个数据元素结点,线性表的链式表示和实现,数据结构与算法,2.基本操作在不带头结点单链表第一个数据元素前插入结点,线性表的链式表示和实现,数据结构与算法,2.基本操作在不带头结点单链表其他数据元素前插入结点,线性表的链式表示和实现,数据结构与算法,2.基本操作删除不带头结点单链表第一个数据元素结点,线性表的链式表示和实现,数据结构与算法,2.基本操作删除不带头结点单链表其他数据元素结点,线性表的链式表示和实现,数据结构与算法,2.基本操作结论,（1）带头结点单链表无论在
9、第一个数据元素结点前插入，还是在其他结点前插入，操作方法一样；而不带头结点单链表在第一个数据元素结点前插入，和在其他结点前插入，操作方法不一样（2）删除操作和插入操作类似（3）设计带头结点单链表的算法时，头指针参数可设计成输入型参数；设计不带头结点单链表的算法时，头指针参数必须设计成输出型参数（4）带头结点单链表的算法设计简单,线性表的链式表示和实现,数据结构与算法,3.结点结构代码描述,/*线性表的单链表存储结构*/typedefintElemType;/ElemType根据实际情况确定/这里为了简单，假设为inttypedefstructNodeElemTypedata;structNod
10、e*next;Node;typedefstructNode*LinkList;/定义单链表LinkList,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算求单链表中元素的个数,/*初始条件：以head表示单链表，假设单链表head已存在*/*操作结果：返回head中数据元素个数*/intLength(LinkListhead)inti=0;LinkListp=head-next;/*p指向第一个结点*/while(p)i+;p=p-next;returni;,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算求遍历单链表,/*初始条件：单链表head已存在*/*操作结果
11、：输出head中的数据元素*/voidPrint(LinkListhead)LinkListp=head-next;/*p指向第一个结点*/while(p)printf(“%d”,p-data);/输出单链表中的数据元素p=p-next;printf(”n”);,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算按编号查找,要找到第i个元素，必须从表头一步步查找/初始条件：单链表head已存在，1iLength(head)/操作结果：用e返回head中第i个数据元素的值voidGetElem(LinkListhead,inti,ElemType*e)intj;LinkListp;/*
12、声明一结点p*/p=head-next;/*让p指向链表head的第一个结点*/j=1;/*j为计数器*/while(p,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算按特征查找,/*初始条件：顺序线性表L已存在*/*操作结果：返回L中第1个与e满足关系的数据元素的位序。*/*若这样的数据元素不存在，则返回值为0*/intLocateElem(LinkListL,ElemTypee)inti=0;LinkListp=L-next;while(p)i+;if(p-data=e)/*找到这样的数据元素*/returni;p=p-next;return0;,线性表的链式表示和实现,数据
13、结构与算法,4.单链表的基本运算在单链表中插入一个结点,单链表的插入可以直接修改指针域，不用移动其它元素，比线性表的顺序存储的插入简单很多。单链表在第i个数据插入结点的算法思路如下：声明一个指针pre指向链表头结点，初始化j从1开始；当jdata；结点s插入单链表第i个位置如图2.10所示，单链表的插入语句s-next=pre-next;pre-next=s;程序结束。,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算单链表插入元素的实现,/*初始条件：顺序线性表head已存在,1iListLength(head)，*/*操作结果：在head中第i个位置之前插入新的数据元素x，链表
14、长度加1*/voidInsert(LinkList*head,inti,ElemTypex)intj;LinkListpre,s;pre=*head;j=0;while(pre/*第i个元素不存在*/,s=(LinkList)malloc(sizeof(Node);/*生成新结点(C语言标准函数)*/s-data=x;s-next=pre-next;/*将p的后继结点赋值给s的后继*/pre-next=s;/*将s赋值给p的后继*/return;,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算从单链表中删除一个结点,从单链表中删除第i个结点的算法思路：1.声明工作指针pre指向链
15、表的头指针，初始化j从0开始；2.当jnext=p-next;6.将p结点的数据赋值给e;7.释放p结点，程序结束。,线性表的链式表示和实现,数据结构与算法,4.单链表的基本运算单链表删除结点的实现,/*初始条件：顺序线性表head已存在，1iListLength(head)*/*操作结果：删除head的第i个数据元素，并用e返回其值，head的长度减1*/voidDelete(LinkList*head,inti,ElemType*e)intj;LinkListpre,p;pre=*head;j=0;while(pre-next/*让系统回收此结点，释放内存*/,线性表的链式表示和实现,数据
16、结构与算法,5.单链表的创建,单链表的基本操作都是建立在单链表已经存在于内存的基础上，但事实上在程序开始，如果自己不创建，这个单链表是不存在的。我们需要先创建单链表。创建单链表的过程就是一个动态生成链表的过程。即从“空表”的初始状态开始，依次建立各元素结点，并逐个插入链表。这种方法创建链表，就是在建立头结点之后，反复地调用插入算法。单链表创建的算法思路如下：(1)声明一个指针和循环变量i；(2)初始化一个空链表head;(3)让head的头结点的指针指向NULL，即建立一个带头结点的单链表；(4)循环：生成一新结点赋值给s；随机生成1-100之间的数字赋值给s的数据域s-data;将s插入到头结点与前一新结点之间,线性表的链式表示和实现,数据结构与算法,5.单链表的创建头插法的实现代码,/*随机产生n个元素的值，建立带表头结点的单链线性表head（头插法）*/voidCreateHead(LinkList*head,intn)LinkLists
