}
{ }
p=p->next;
}
void fun( LNode *h)//时间复杂度O(n) { }
LNode *p,*q;
p=h->next;
while(p!=NULL && p->next !=NULL ) { }
q=p->next;
if(p->data!=q->data) { p=p->next; } else { }
p->next=q->next; free(q);
2007年真题
试编写一个在带头结点的双向循环链表中值为x的结点之前，插入值为y的结点的算法。（要求：用C语言描述，结点类型定义为DlinkList）
Status InsertPrior-L(DlinkList *L,int x,int y) //x之前插入y结点 { }
5
DNode *s,*p; p=L->next;
while(p!=L && p->data!=x) { }
s=(DNode *)malloc(sizeof(DNode)); s->data=y; s->next=p; s->prior=p->prior; p->prior->next=s; p->prior=s; p=p->next; if(p!=L)
2009年真题
程序填空题：单链表中，无序单链表转化为有序单链表（10分） void sort3(LNode *L)//无序链表排序，利用单链表就地逆置的思想 {
LNode *p,*q,*s;//s保存新摘结点，p保存原有链表，q在新链表中找位置 if(L->next==NULL)
return;
p=L->next->next; //从第二个结点开始 L->next->next=NULL;
while(p!=NULL) { s=p; p=p->next; //p保存原有链表 }
q=L;
while(q->next!=NULL && s->data>q->next->data) //查找插入位置 q=q->next;
s->next=q->next; //插入结点 q->next=s;
}
void sort4(LNode *L)//无序链表排序，利用直接选择排序思想 {
LNode *p,*q,*s;//p控制外层循环，q保存最小结点，s找位置 int x;
if(L->next==NULL) return;
p=L->next; //第一个结点
while(p!=NULL) {
q=p;//假设当前结点值是最小的
s=p->next; //从第二个结点开始
while(s!=NULL) //循环找最小的结点，由q指向 {
if(s->data
//交换两个结点的数据域
}
x=p->data; q->data=x; p=p->next;
p->data=q->data;
//下一个结点
} }
//直接选择排序是每次从n-i+1个结点中选择码值最小者，与第i个结点的码值进行交换，设p指向第i个结点，//min指向无序表中码值最小的结点，算法描述如下： void selesort1(Lnode *h)
6
{ }
模拟二
设n个整数存于数组x中，写一算法将所有偶数移到奇数之前，要求时间复杂度为O(n)。 void change(int a[],int n) { }
模拟三
1．冒泡排序算法是把大的元素向上移（气泡的上浮），也可以把小的元素向下移（气泡的下沉）请给出上浮和下沉过程交替的冒泡排序算法。
void BubbleSort2(int a[],int n) //相邻两趟向相反方向起泡的冒泡排序算法 {
Lnode *p,*q,*min; int x; p=h->next; while(p) { }
min=p; q=p->next; while(q) {
if(q->key
}
if(min!=p) { x=p->key;
p->key=min->key; min->key=x;
}
p=p->next;
int i=1,j=n; while(i<=j) { if(i%2==0) }
i++;
else if(j%2!=0)
j--; else { a[0]=a[i];a[i]=a[j];a[j]=a[0]; i++;j--; }
int i,t,change,low,high;
7
change=1;//有交换
low=0;high=n; //冒泡的上下界 while(low { change=0; //设不发生交换 for(i=low;i if(a[i]>a[i+1]) { t=a[i]; a[i]=a[i+1];a[i+1]=t;change=1; } //有交换，修改标志change high--; //修改上界 for(i=high;i>low;i--) //从下向上起泡 if(a[i] { t=a[i]; a[i]=a[i-1];a[i-1]=t;change=1; } low++; //修改下界 }//while }//BubbleSort2 模拟四 1.设n个元素的线性表顺序存储在一维数组st[1..maxlen]的前n个位置上,试将新元素e插入表中第i-1个和第i个元素之间,写出算法。 void insert(ElemType st[],ElemType e,int i,int n)//插入表元素 { int j; if(n==maxlen) { } { } printf(\数组已满,不能进行插入操作!\\n\return ; if(i<1 || i>n+1) printf(\位置参数不正确,不能进行插入操作!\\n\return ; n++; for(j=n;j>i;j--) { st[j]=st[j-1]; } st[j]=e; /*结点向后移动，腾出一个位置*/ } 2.设Head为带表头结点的单链表的头指针,试写出算法:若为非空表,则输出首结点和尾结点的值(data值)；否则输出:”Empty list！”。 Void disp(LNode *Head) { LNode *p=Head; 8