数据结构PPT教学课件-第2章 线性表.ppt

２.２ 线性表的顺序存储结构（向量） ２.３ 线性表的链表存储结构 ２.４ 循环链表和双向链表 ２.5 多项式相加问题 ２.6 线性表的算法实现举例 if (i1||iv.len+1) printf(i 位置不存在。 ); else { for (j=v.len; j=i; j--) v.elem［j+1］=v.elem［j］; v.elem［i］=x; v.len++; } } /* insert end */  void delete(struct sequnce *p, int i) { int j; if(i1||iv.len) printf(i 位置不存在。 ); 算法 2.4 ”void delete(struct node *head) { q=head; p=q-next; while((p!=NULL)(p-data!=x){ q=p; p=p-next; } if (p==NULL) printf(NO!); else { q-next= p-next; free(p); printf(YES!); } }  3. 单链表的逆置 单链表的逆置方法不唯一, 在此介绍的是: 利用在附加头结点和第一个存放数据元素的结点之间不断插入后边元素结点的方法, 如图2.9所示。 算法2.5 ” Void nizhi(struct node *head)  { p=head-next; head-next=NULL; while (p!=NULL) {q=p-next; p-next=head-next; head-next=p; p=q; } } 图2.9是针对算法的一个简单图示。上述算法不仅适用于多结点链表, 也适用于空表。 4. 单链表的建立 所谓建立链表是指从无到有地建立一个链表, 即将线性表的数据元素一一输入, 不断产生各结点并建立起前后相链的关系。 根据原始数据输入的顺序不同, 算法细节也有所不同。 一种是按照原始数据的先后顺序一一输入, 新结点在表尾插入; 另一种是按照原始数据的倒序输入, 新结点在附加头结点后第一个有效数据元素结点前插入。 这里介绍的算法是第一种方法。具体算法如下: 算法2.6 ”void creat ( ) { head = (NODE*) malloc (sizeof(NODE)) ; /* head应为全局变量 */ head-next=NULL ; p=head; /* head为附加头结点 */ printf(x=?);scanf(%d,x); /* 输入第一个数据元素*/ while (x!=-999) { ptr= (NODE *) malloc (sizeof(NODE)) ; ptr-data=x; ptr-next=NULL; p-next=ptr;  p=ptr; printf(x=?);scanf(%d,x);/* 输入下一个数据元素 */ } } 在这个算法中从第一个数据元素开始输入, 然后按顺序逐一输入, 最后以-999为结束标志。 ２.４.１ 循环链表 　　循环链表是另一种形式的链式存储结构, 将单链表的形式稍加改动, 让表中最后一个结点的指针指向单链表的表头结点, 这样就形成了一个循环链表, 如图2.10所示。 使用循环链表的主要优点是, 　　从表中任一结点出发均可找到表中其它结点。  在循环链表中, 除了头指针ｈ外, 还加了一个尾指针ｒ, 尾指针ｒ指向最后一个结点, 从最后一个结点的指针又可立即找到链表的第一个结点, 这样, 尾指针就起到了又指头又指尾的功能, 所以在实际应用中, 往往使用尾指针代替头指针来进行某些操作