数据结构算法求大神

Question

1 写一算法，统计出单链表L中结点的值等于给定值x的结点数。
2 已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表 中所有大于K1且小于K2的元素（若表中存在这样的元素,且K1<K2），并分析你的算法的时间复杂度。
3假设两个按元素值递增有序排列的线性表A和B，均以单链表作为存储结构，请编写算法，将A表和B表 归并成一个按元素值递减有序的排列的线性表C，并要求利用原表（即A表和B表的）结点空间存放表C 。

Answer 1

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<iostream.h>

#define elem int
#define M 10

typedef struct node
{
elem data;
struct node *next;
}no;

//以下单链表均带头节点
//1.
int f1(no *L,elem x)
{
int i=0;
L=L->next;
while(L)
{
if(L->data==x)
i++;
L=L->next;
}
return i;
}
//2.算法复杂度为O(N)
void f2(no *L,int k1,int k2)
{
if(k1>=k2)
{
cout<<"arguements error"<<endl;
return;
}
no *p=L,*q;
L=L->next;
while(L)
{
if(L->data>k1)
break;
p=L;//记住删除第一个结点的父节点
L=L->next;
}
while(L && L->data<k2)
{
q=L;
p->next=L->next;
free(q);
L=p->next;
}
}
//3.算法采用的是头插法
node *f3(no *a,no *b)
{
if(!a || !b)
return 0;
node *c=new node,*p;
if(!c)
exit(1);
c->next=0;
while(a->next || b->next)
{
if(!a->next || b->next && b->next->data < a->next->data)
{//当链表a为空时，或b链表存在且b链表的第一个值小于a链表
p=b->next;
b->next=p->next;
}
else
{
p=a->next;
a->next=p->next;
}
p->next=c->next;
c->next=p;
}
return c;
}