O(n)。
6 q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q; 7线性表为：（78，50，40，60，34，90）
四、算法设计题
1．算法思想为：
（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作； （2）当i=0时，删除第一个结点：
（3）当０ delete(LinkList *q,int i) { //在无头结点的单链表中删除第i个结点 LinkList *p,*s; int j; if(i<0) printf(\ else if(i= =0) { s=q; q=q->next; free(s); } else { j=0; s=q; while((j j++; } if (s= =NULL) printf(\ delete\ else { p->next=s->next; free(s); } } } 2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下： int ListLength ( LinkList *L ) { //求带头结点的单链表的表长 int len=0; ListList *p; p=L; while ( p->next!=NULL ) { p=p->next; len++; } return (len); } 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．定义类型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．算法描述如下： 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．算法描述如下： 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; } } 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); } 9. int CountX(LNode* HL,ElemType x) { int i=0; LNode* p=HL;//i为计数器 while(p!=NULL) { if (P->data==x) i++; p=p->next; }//while, 出循环时i中的值即为x结点个数 return i; }//CountX 11 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构 表示。 typedef struct node {int data; struct node *next;}lklist; void intersection(lklist *ha,lklist *hb,lklist *&hc) { lklist *p,*q,*t; for(p=ha,hc=0;p!=0;p=p->next) { for(q=hb;q!=0;q=q->next) if (q->data==p->data) break; if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;} } } 12设计在单链表中删除值相同的多余结点的算法。 typedef int datatype; typedef struct node {datatype data; struct node *next;}lklist; void delredundant(lklist *&head) { lklist *p,*q,*s; for(p=head;p!=0;p=p->next) { for(q=p->next,s=q;q!=0; ) if (q->data==p->data) {s->next=q->next; free(q);q=s->next;} else {s=q,q=q->next;} } } 13设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。 typedef char datatype; typedef struct node {datatype data; struct node *next;}lklist; void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc) { lklist *p; ha=0,hb=0,hc=0; for(p=head;p!=0;p=head) { head=p->next; p->next=0; if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;} else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;} } } 14 设计两个有序单链表的合并排序算法。 void mergelklist(lklist *ha,lklist *hb,lklist *&hc) { lklist *s=hc=0; while(ha!=0 && hb!=0) if(ha->data 15设计判断单链表中元素是否是递增的算法。 int isriselk(lklist *head) { if(head==0||head->next==0) return(1);else for(q=head,p=head->next; p!=0; q=p,p=p->next)if(q->data>p->data) return(0); return(1); } 五、算法阅读 （1）该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为 新的开始结点，返回新链表的头指针。 （2）查询链表的尾结点 （3）将第一个结点链接到链表的尾部，作为新的尾结点 （4）返回的线性表为（a2,a3,?,an,a1）