基本内容线性表的逻辑结构定义和各种存储结构的描述方

1、第二章第二章 线性表线性表基本内容：基本内容：线性表的逻辑结构定义和各种存线性表的逻辑结构定义和各种存储结构的描述方法；在线性表的两类存储结构储结构的描述方法；在线性表的两类存储结构上如何实现基本运算。上如何实现基本运算。重点：重点：掌握顺序表和链表的描述方法、特点掌握顺序表和链表的描述方法、特点及有关概念。及有关概念。难点：难点：掌握顺序表上的插入和删除算法以及掌握顺序表上的插入和删除算法以及动态链表的建立、查找、插入和删除算法。动态链表的建立、查找、插入和删除算法。 第一节第一节 线性表的逻辑结构线性表的逻辑结构 第二节第二节 线性表的顺序存储结构线性表的顺序存储结构 第三节第三节 线性表

2、的链式存储结构线性表的链式存储结构第一节第一节 线性表的逻辑结构线性表的逻辑结构线性表的定义：线性表的定义：含有含有N N个数据元素的线性表是一个数据结构：个数据元素的线性表是一个数据结构：Linear_list=(D,R)其中：其中：D=ai|ai属于属于D0,i=1,2,n,n=0 R=|ai-1,ai属于属于D0,i=2,3,n D0为为某个数据对象。某个数据对象。 线性表中的数据元素可以是各种各样的，但同一线线性表中的数据元素可以是各种各样的，但同一线性表中的元素必是具有相同属性，属于同一数据对象。性表中的元素必是具有相同属性，属于同一数据对象。关系关系R R是一个有序偶对的集合，表示

3、线性表中的数据元素是一个有序偶对的集合，表示线性表中的数据元素之间的相邻关系，即之间的相邻关系，即a ai i-1-1领先于领先于a ai i，a ai i领先于领先于a ai i+1+1，称，称a ai i-1-1为为a ai i的直接前驱，的直接前驱，a ai i+1+1为为a ai i的直接后继，线性表中数据元的直接后继，线性表中数据元素个数为素个数为n n（n=0n=0）定义为线性表的长度，）定义为线性表的长度，n=0n=0时为空表，时为空表，n0n0时，记为：（时，记为：（a a1 1,a,a2 2, ,a,ai i, ,a,an n）. .第二节第二节 线性表的顺序存储结构线性表的

4、顺序存储结构 把线性表的结点按逻辑次序依次存放在把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里，用这种方法存一组地址连续的存储单元里，用这种方法存储的线性表称为顺序表。储的线性表称为顺序表。C C语言中用一维数组来描述：语言中用一维数组来描述：#define MAXLEN 线性表的最大长度线性表的最大长度typedef structelemtype elemMAXLEN; int last; sqlisttp;1 1、查找、查找在顺序表在顺序表v v中查找第中查找第i i个元素。个元素。v.elemi-12 2、求长度、求长度求顺序表求顺序表v v中元素的个数。中元素的个数。v.l

5、ast第二节第二节 线性表的顺序存储结构线性表的顺序存储结构3 3、插入、插入在顺序表在顺序表v v中第中第i i个元素前插入元素个元素前插入元素b b。status insert(sqlisttp &v,int i,elemtype b) if (iv.last+1) return ERROR; else if (v.last=maxlen) return OVERFLOW; else for(j=v.last-1;j=i-1;j-) v.elemj+1=v.elemj; v.elemi-1=b; v.last+; return OK; 第二节第二节 线性表的顺序存储结构线性表的顺序

6、存储结构 4 4、删除、删除 在顺序表在顺序表v v中删除第中删除第i i个元素。个元素。 status delete(sqlisttp &v,int i) if (iv.last) return ERROR; else for (j=i;j=v.last-1;j+) v.elemj-1=v.elemj; v.last-; return OK; 第二节第二节 线性表的顺序存储结构线性表的顺序存储结构5 5、归并、归并 已知线性表已知线性表LALA和和LBLB中的数据元素按值非递减有序排列，中的数据元素按值非递减有序排列，现将现将LALA和和LBLB合成为一个新的线性表合成为一个新的线性

7、表LCLC，且，且LCLC中数据元中数据元素仍按值非递减排列有序。素仍按值非递减排列有序。 status merge(sqlisttp la,sqlisttp lb;sqlisttp &lc) i=1;j=1;k=0; while (i=la.last&j=lb.last) if (la.elemi=lb.elemj) lc.elem+k=la.elemi;+i; else lc.elem+k=lb.elemj;+j while (i=la.last) lc.elem+k=la.elemi;+i; while (jnext=null; for(i=n-1;i=0;i-) p=(

8、Linklist)malloc(sizeof(LNODE); p-data=ai; p-next=la-next; la-next=p; （2）、用尾插法建立单链表（带头结点）、用尾插法建立单链表（带头结点） void creat2(Linklist &la,int an) la=(Linklist)malloc(sizeof(LNODE); la-next=null; r=la; for(i=0;idata=ai; p-next=null; r-next=p; r=p; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 2、 查找查找（1）、按序号查找）、按序号查找(带头结点带

9、头结点)，返回其值。，返回其值。 elemtype loc1(Linklist la,int i) p=la-next; j=1; while (p!=null&jnext; +j; if(p=null|ji) return 0; e=p-data; return e; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 （2）、按值查找（带头结点），返回其在表中的位置。）、按值查找（带头结点），返回其在表中的位置。 int loc2(Linklist la,elemtype x) p=la-next; j=1; while (p!=null&p-data!=x) p=p-

10、next; +j; if (p=null|p-data!=x) return 0; return j; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 3、 插入插入 （1）、后插操作）、后插操作 s=(Linklist)malloc(sizeof(LNODE); s-data=x; s-next=p-next; p-next=s; （2）、前插操作）、前插操作 s=(Linklist)malloc(sizeof(LNODE)； s-data=x; q=la; while(q-next!=p) q=q-next; s-next=p; q-next=s; 第三节第三节 线性表的链式存储结

11、构线性表的链式存储结构 （3）、在单链表）、在单链表LA上实现线性表插入运算上实现线性表插入运算INSERT（LA，I，X） /*在带头结点的单链表在带头结点的单链表LA中第中第I个位置之前插入元素个位置之前插入元素X*/ status list_insert(Linklist &la,int i;elemtype x) p=la; j=0; while(p!=null&jnext; +j; if(p=null|ji-1) return ERROR; s=(Linklist)malloc(sizeof(LNODE); s-data=x; s-next=p-next; p-nex

12、t=s; return OK; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 4、 删除删除 （1）、删除）、删除P的后继元素的后继元素 r=p-next; p-next=r-next; free(r); （2）、删除）、删除P所指元素所指元素 q=la; while(q-next!=p) q=q-next; q-next=p-next; free(p); 第三节第三节 线性表的链式存储结构线性表的链式存储结构 （3）、在单链表）、在单链表LA上实现线性表的删除运算上实现线性表的删除运算DELETE（LA，I）/*在带头结点的单链表在带头结点的单链表LA中，删除第中，删除第I个结点，

13、个结点，并由并由X返回其值返回其值*/ status list_delete(Linklist &la,int i,elemtype &x) p=la;j=0; while(p-next!=null&jnext; +j; if (p-next=null|ji-1) return ERROR; q=p-next; p-next=q-next; x=q-data; free(q); return OK; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 5、 归并归并 （1）、将两个有序单链表合为一个有序单链表（按非递减）、将两个有序单链表合为一个有序单链表（按非递减

14、次序排列）次序排列） void list_merge1(Linklist la,Linklist lb,Linklist &lc) pa=la-next; pb=lb-next; lc=pc=la; while(pa!=null&pb!=null) if(pa-datadata) pc-next=pa;pc=pa;pa=pa-next; else pc-next=pb;pc=pb;pb=pb-next; if(pa!=null) pc-next=pa; else pc-next=pb; free(lb); 第三节第三节 线性表的链式存储结构线性表的链式存储结构 （2）、将两个不

15、同长度的单链表合成一个单链表）、将两个不同长度的单链表合成一个单链表(不带头结不带头结点点) void list_merge2(Linklist la;Linklist lb;Linklist &lc) if (la=null&lb=null) lc=null; if(la=null&lb!=null) lc=lb; if(lb=null&la!=null) lc=la; if(la!=null&lb!=null) p=la; lc=la; while(p-next!=null) p=p-next; p-next=lb; 第三节第三节 线性表的链式存储结

16、构线性表的链式存储结构 二、循环链表二、循环链表 是一种首尾相连的链表。是一种首尾相连的链表。 将单链表中的终端结点的指针域将单链表中的终端结点的指针域NULL改为指向表头改为指向表头结点（带头结点的单链表）或开始结点（不带头结点的单链结点（带头结点的单链表）或开始结点（不带头结点的单链表），得到了单链形式的循环链表，成为单循环链表。表），得到了单链形式的循环链表，成为单循环链表。 在循环链表中常使用尾指针。在循环链表中常使用尾指针。 第三节第三节 线性表的链式存储结构线性表的链式存储结构 1、实现在带头结点的单循环链表的表头插入一个新结点。、实现在带头结点的单循环链表的表头插入一个新结点。

17、为空时插入操作为：为空时插入操作为： p=(Linklist)malloc(sizeof(LNODE); p-data=x； p-next=r; r-next=p; r=p; 不为空时插入操作为：不为空时插入操作为： p=(Linklist)malloc(sizeof(LNODE); p-data=x; p-next=r-next-next; r-next-next=p; 第三节第三节 线性表的链式存储结构线性表的链式存储结构 2、实现在带头结点的单循环链表的表头删除一个结点。、实现在带头结点的单循环链表的表头删除一个结点。 只有一个元素时的删除操作为：只有一个元素时的删除操作为： p=r;

18、r-next-next=r-next; r=p-next； free(p); 有若干个元素时的删除操作为：有若干个元素时的删除操作为： p=r-next-next; r-next-next=p-next; free(p); 第三节第三节 线性表的链式存储结构线性表的链式存储结构 3、实现两个线性表、实现两个线性表LA与线性表与线性表LB的连接。（采用设尾的连接。（采用设尾指针的单循环链表作存储结构）指针的单循环链表作存储结构） void connect(Linklist &ra,Linklist &rb) p=ra-next; q=rb-next; ra-next=rb-next-next; rb-next=p; free(q); 第三节第三节 线性表的链式存储结构线性表的链式存储结构 三、双向链表三