编程线性结构概要.ppt

首结点之前插新结点函数定义 void lq_ins2(hpt,x) LinkNode *hpt; /*链表头指针*/ int x; /*新结点的键盘值*/ {LinkNode *u; u= new LinkNode; u-data=x; u-link=hpt; hpt=u; } 分情况讨论（3） 3、在链式存储的线性表的末尾接上一个键值为x的新结点 线性表末尾接上新结点函数定义 void lq_ins3(hpt,x) LinkNode *hpt; /*链表头指针*/ int x; /*新结点的键盘值*/ {LinkNode *u,*p; u=new LinkNode; u-data=x; u-link=null; if (hpt==null) /*如链表为空链表*/ {hpt=u;return; } /*x以链表首结点开始顺序走向末尾结点*/ for( p=hpt; p-link!=null;p= p-link); p-link=u; } 分情况讨论（4） 4、在有序链式存储线性表中插入一键值为X的新结点(假设x=8) 有序链式线性表中插入新结点函数 voikd lq_ins4 (hpt,x) /*设链表从小到大有序*/ LinkNode *hpt; /*链表头指针*/ int x; /*新结点的键值*/ {LinkNode *u,*q,*p; u=new LinkNode; u-data=x; /*从链表首结点开始顺序寻找*/ for(p=htp;pp-datax;q=p,p=p-link); if(p= =hpt) hpt=u; else q-link=u; u-link=p } （三）线性链表的删除操作 完成删除算法可有以下几个步骤组成： 1、如链表为空链表，则不执行删除操作 2、若链表的首结点的值为指定值，更改链表的头指针为指向首结点的后继结点； 3、在链表中找到指定值的结点； 4、将找到的结点删除 删除操作示意图 链表中删除指定值的结点的函数定义 int lq_delete(hpt,a) LinkNode *hpt; /*链表头指针的指针*/ int a; /*要删除的结点键值*/ {LinkNode *p, *q; if((q=hpt)==NULL) return 1; /*链表已为空链表*/ if(q-data==a) /*要删除链表的首结点*/ { hpt=q-link; /*更改链表头指针*/ delete(q); /*释放被删除结点的空间*/ return 0; /*删除成功*/ }for( ; q-data!=aq-link!=NULL;p=q,q=q-link); /*寻找*/ if(q-data==a) /*找到*/ { p-link=q-link; /被删除的结点从链表脱钩**/ delete(q); /*释放被删除结点的空间*/ return 0; /*删除成功*/ }return 1; /*没有指定值勤的结点，未执行删除操作*/ } 2.3.3 循环链表 1.单循环链表 将单向链表中最后一个结点的指针域指向头结点，整个链表头尾结点相连形成了一个环,就构成了单向循环链表。如图2-26所示。这种结构从表中任一结点出发均可找到其它结点。 单向循环链表的基本操作类似于普通链表，差别在于算法中循环条件不在是p或p-link是否为空，而是它们是否等于头指针,即: p-link =head。 2.关于存储密度 (1)存储密度是指结点数据本身所占的存储空间和整个结点结构所占的 存储空间之比。所以，顺序表的存储密度等于1，而链表的存储密度 小于1。 （2）采用链式存储比采用顺序存储占用更多的存储空间，因为链式存储 结构增加了存储其后继结点的地址的指针域。 （3）存储空间完全被结点值占用的存储方式称为紧凑存储，否则称为非 紧凑存储。显然，顺序存储是紧凑存储，而链式存储是非紧凑存 储。存储密度的值越大，表示数据所占用的存储空间越小。 2.3.4 双向链表 在单向链表中，从任何一个结点能通过指针域找到它的后继结点，但要找它的前驱结点，则需从表头出发顺链查找。双向链表克服了这个缺点。 双向链表的每一个结点除数据域外，还包括两个指针域，一个指向该结点的后继结点，另一个指向它的前驱结点，结点结构如图2-27所示。双向链表也可以是循环链表，其结构如图2-28所示 front rear 双向链表的结点类型可描述如下 struct cdlist {datatype data; struct cdlist *front; struct