}
2. 在单链表上实现线性表的求表长ListLength(L)运算。
2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：
int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L;
while ( p->next!=NULL ) { p=p->next; len++; }
return (len); }
3. 设计将带表头的链表逆置算法。
3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：
void invert(LinkList *head)
{ //逆置head指针所指向的单循环链表 linklist *p, *q, *s; q=head; p=head->next;
while (p!=head) //当表不为空时，逐个结点逆置 { s=q; q=p; p=p->next; q->next=s; } p->next=q; }
4. 假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data, next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。
4．定义类型LinkList如下：
typedef struct node { int data;
struct node *next,*prior;
}LinkList;
此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：
insert (LinkList *head) { LinkList *p,*s,*q;
p=head->next; //p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)
{ s=head; // s指向q结点的前趋结点
q=head->prior; //q指向由prior域构成的链表中待比较的结点
while((q!=NULL) && (p->data>q->data)) //查找插入结点p的合适的插入位置
{ s=q;
q=q->prior; } s->prior=p;
p->prior=q; //结点p插入到结点s和结点q之间 p=p->next;
} }
5. 已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。
5．算法描述如下：
delete(LinkList *head, int max, int min) { linklist *p, *q; if (head!=NULL) { q=head; p=head->next;
while((p!=NULL) && (p->data<=min)) { q=p;
p=p->next; }
while((p!=NULL) && (p->data
} }
6. 已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。
6．算法描述如下：
delete(LinkList *head, int max, int min) { LinkList *p,*q; q=head; p=head->next;
while (p!=NULL)
if((p->data<=min) || (p->data>=max)) { q=p; p=p->next; }
else
{ q->next=p->next;
free(p); p=q->next; } }
7. 假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：
（1）向循环链队列插入一个元素值为x的结点； （2）从循环链队列中删除一个结点。
7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：
（1）插入（即入队）算法：
insert(LinkList *rear, elemtype x)
{ //设循环链队列的队尾指针为rear,x为待插入的元素 LinkList *p;
p=(LinkList *)malloc(sizeof(LinkList));
if(rear= =NULL) //如为空队，建立循环链队列的第一个结点 { rear=p;
rear->next=p; //链接成循环链表 }
else //否则在队尾插入p结点 { p->next=rear->next;
rear->next=p; rear=p; } }
（2）删除（即出队）算法：
delete(LinkList *rear)
{ //设循环链队列的队尾指针为rear if (rear= =NULL) //空队 printf(\
if(rear->next= =rear) //队中只有一个结点 rear=NULL; else
rear->next=rear->next->next; //rear->next指向的结点为循环链队列的队头结点 }
8. 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。 8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：
int InsertDecreaseList( SqList *L, elemtype x ) { int i;
if ( (*L).len>= maxlen) { printf(“overflow\ return(0); }
for ( i=(*L).len ; i>0 && (*L).elem[ i-1 ] < x ; i--) (*L).elem[ i ]=(*L).elem[ i-1 ] ; // 比较并移动元素 (*L).elem[ i ] =x; (*L).len++; return(1); }