p->n = p->n ? count;
if (p->element[i] == x) p?>n? ?; }
代价分析
该算法访问顺序表中每个元素各一次，时间代价为O (n)。
? 讨论
这个算法使用了一点技巧使得在中间删除元素时，避免了最后一串元素的移动。但
是，它破坏了原来线性表中元素之间的顺序关系。
如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表，
如果元素不是x，则继续向后；如果元素是x，则寻找其后第一个不是x的元素，将这两个元素互换。具体算法请读者自己实现。
6.写一算法，在带头结点的单链表llist中，p所指结点前面插入值为ｘ的新结点，并返回插入成功与否的标志。
【答】
数据结构
采用2.1.3节中单链表定义。
思想：
由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插入。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locate_link 类似的方式进行搜索。 算法：
int insertPre_link(LinkList llist,PNode p,DataType x){
/* 在llist带头结点的单链表中，p所指结点前面插入值为x的新结点 */ PNode p1;
if(llist==NULL) return 0; p1=llist;
while(p1!=NULL&&p1->link!=p)p1=p1->link; /*寻找p所指结点的前驱结点*/ if(p1=NULL) return 0;
PNode q=(PNode)malloc(sizeof(struct Node));/*申请新结点*/ if(q=NULL) {printf(“Out of space!!!\\n”);return 0;} q->info=x; q->link=p1->link; p1->link=q; return 1; }
7.写一算法，在带头结点的单链表llist中,删除p所指的结点，并返回删除成功与否的标志。
【答】
数据结构
采用2.1.3节中单链表定义。
思想：
由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成删除。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与
locate_link 类似的方式进行搜索。
int deleteP_link(LinkList llist,PNode p){
/* 在llist带头结点的单链表中，删除p所指的结点 */ PNode p1;
if(llist==NULL)return Null; p1=llist;
while(p1!=NULL&&p1->link!=p)p1=p1->link; /*寻找p所指结点的前驱结点*/ if(p1=NULL)return 0; p1->link=p->link; free(p); /* 删除结点p */ return 1; }
8. 已知list是指向无头结点的单链表的指针变量，写出删除该链表下标为i的（第i+1个）结点的算法。 【答】 数据结构
采用2.1.3节中单链表定义。 思路
依次遍历表中的每一个结点并计数，到第i+1个结点时实行删除。由于链表是无头结
点的，所以在删除第一个结点时要特别注意。
算法
int deleteindex_link_nohead(LinkList * pllist, int i) {
/*删除单链表中下标为i的结点。删除成功返回TRUE，否则返回FALSE。*/
int j; PNode p, q;
if ((*pllist) == NULL || i < 0) return FALSE; if ( i = = 0) { q = (*pllist);
(*pllist) = (*pllist)->link; free(q); return TRUE; }
p = (*pllist); j = 0;
while (p->link != NULL && j < i ? 1) { p = p->link; j++; }
if (p->link == NULL) return FALSE; q = p->link; p->link = q->link; free(q); return TRUE; }
/*此元素不存在*/
/*寻找下标为i?1的结点的地址*/
/*如果需要删除第一个结点*/
代价分析
该算法访问单链表中前面i个结点，时间代价为O(i)，最大不超过O(n)。
? 讨论
如果函数参数不是LinkList *类型而是LinkList类型，在删除i=0的结点时，程序不
能正确实现，其原因请读者思考（考虑C语言的参数传递方式）。
如果单链表带表头结点，重写本题的算法。比较这两个算法，是否能体会到表头结
点的作用。
9. 已知list是指向无头结点的单链表的指针变量，写出删除该链表中从下标为i的（第i+1个）结点开始的连续k个结点的算法。 【答】 数据结构
采用2.1.3节单链表定义。 思路
这道题与上题相似，只需要增加计数即可。要注意的是应该判断给出的i和k是否合
理，是不是会超出链表长度。
算法
int del_link_nohead(LinkList * pllist, int i, int k) {
/*删除单链表中从下标i开始的k个结点。删除成功返回TRUE，否则返回FALSE。*/
int j; PNode p, q;
if ((*pllist) == NULL || i < 0 || k <= 0) return FALSE; if ( i = = 0) {
/*如果需要删除从第一个结点开始的k个结点*/
for ( j = 0; j < k && (*pllist) != NULL; j++) {
q = (*pllist);
(*pllist) = (*pllist)->link; free(q); }
return TRUE; }
p = (*pllist); j = 0;
while ( p->link != NULL && j < i ? 1) {
p = p->link; j++;
}
if (p->link == NULL) return FALSE;
q = p->link; p->link = q->link; free(q); }
return TRUE; }
/*第i个结点不存在*/
for ( j = 0; j < k && p->link != NULL; j++) {
/*寻找下标为i?1的结点的地址*/
代价分析
该算法访问单链表中前面i+k个结点，时间代价为O(i+k)，最大不超过O(n)。
13. 请设计一个算法，求出循环表中结点的个数。 【答】
数据结构
采用不带头结点的循环链表。
struct Node;
typedef struct Node * PNode; struct Node{
DataType info; PNode link; };
typedef struct Node * LinkList;
思路
遍历整个循环链表，同时计数即可。 ? 错误算法
int count(LinkList clist){
int count; PNode p, q; p = clist; q = p->link;
if (clist == NULL) return 0; count = 1; while ( q != p){
}
return count; }
q = q->link; count++;
/*如果是空表*/
错误：如果clist是一个空表，那么第5行的语句“q = p->link;”是非法的。
分析：应把第6行语句（用下划线表示）提前1行或2行。一定要放在语句“q = p->link;”之前。
缺点：增加局部变量p。
分析：这样做没有必要，因为p的初值置为clist，在程序中并没有对p做其他修改，所以程序中不需要引入p而直接使用clist即可。
算法
int count(LinkList clist){
int count; PNode q;
if (clist == NULL) return 0; q = clist->link; count = 1; while ( q != clist){
q = q->link; count++;
/*如果是空表*/
}
return count; }
代价分析
该算法访问循环链表中每个结点各一次，时间代价为O(n)。