当前位置:文库下载 > 所有分类 > 外语学习 > 韩语学习 > 2014年新疆维吾尔自治区数据库入门基础
侵权投诉

2014年新疆维吾尔自治区数据库入门基础

2014年新疆维吾尔自治区数据库入门基础

1、本题要求建立有序的循环链表。从头到尾扫描数组A,取出A[i](0<=i<n),然后到链表中去查找值为A[i]的结点,若查找失败,则插入。
LinkedList creat(ElemType A[],int n)
//由含n个数据的数组A生成循环链表,要求链表有序并且无值重复结点
{LinkedList h;
h=(LinkedList)malloc(sizeof(LNode));//申请结点
h->next=h; //形成空循环链表
for(i=0;i<n;i++)
{pre=h;
p=h->next;
while(p!=h && p->data<A[i])
{pre=p; p=p->next;} //查找A[i]的插入位置
if(p==h || p->data!=A[i]) //重复数据不再输入
{s=(LinkedList)malloc(sizeof(LNode));
s->data=A[i]; pre->next=s; s->next=p;//将结点s链入链表中
}
}//for
return(h);
}算法结束

2、冒泡排序算法是把大的元素向上移(气泡的上浮),也可以把小的元素向下移(气泡的下沉)请给出上浮和下沉过程交替的冒泡排序算法。
48.有n个记录存储在带头结点的双向链表中,现用双向起泡排序法对其按上升序进行排序,请写出这种排序的算法。(注:双向起泡排序即相邻两趟排序向相反方向起泡)

3、约瑟夫环问题(Josephus问题)是指编号为1、2、…,n的n(n>0)个人按顺时针方向围坐成一圈,现从第s个人开始按顺时针方向报数,数到第m个人出列,然后从出列的下一个人重新开始报数,数到第m的人又出列,…,如此重复直到所有的人全部出列为止。现要求采用循环链表结构设计一个算法,模拟此过程。
#include<stdlib.h>
typedef int datatype;
typedef struct node
{datatype data;
struct node *next;
}listnode;
typedef listnode *linklist;
void jose(linklist head,int s,int m)
{linklist k1,pre,p;
int count=1;
pre=NULL;
k1=head; /*k1为报数的起点*/
while (count!=s) /*找初始报数起点*/
{pre=k1;
k1=k1->next;
count++;
}
while(k1->next!=k1) /*当循环链表中的结点个数大于1时*/
{ p=k1; /*从k1开始报数*/
count=1;
while (count!=m) /*连续数m个结点*/
{ pre=p;
p=p->next;
count++;
}
pre->next=p->next; /*输出该结点,并删除该结点*/
printf("%4d",p->data);
free(p);
k1=pre->next; /*新的报数起点*/
}
printf("%4d",k1->data); /*输出最后一个结点*/
free(k1);
}
main()
{linklist head,p,r;
int n,s,m,i;
printf("n=");
scanf("%d",&n);
printf("s=");
scanf("%d",&s);
printf("m=",&m);
scanf("%d",&m);
if (n<1) printf("n<0");
else
{/*建表*/
head=(linklist)malloc(sizeof(listnode)); /*建第一个结点*/
head->data=n;
r=head;
for (i=n-1;i>0;i--) /*建立剩余n-1个结点*/
{ p=(lin


klist)malloc(sizeof(listnode));
p->data=i;
p->next=head;
head=p;
}
r->next=head; /*生成循环链表*/
jose(head,s,m); /*调用函数*/
}
}

第1页

猜你喜欢

返回顶部