|
【题目】设一单向链表的头指针为head,链表的记录中包含着整数类型的key域,试设计算法,
将此链表的记录按照key递增的次序进行就地排序.（不答应使用数组做辅助存储）
【来源】中科院计算机技术研究所1999年第五（1）题 （10’）
华中理工大学2000年第八（2）题 （13’）
【解答】
typedef struct CircleList{ // 定义循环链表
int key;
struct CircleList *next;
}*listnode;
ListSort(listnode head)
{
int k,min,i,j;
listnode p,q,t;
p=head->next;
while(p->next!=head->next){p=p->next;k+=1;} // 统计链表中元素个数，保存在 K 中
p=head;j=1;
for(i=1;i<k;i++){
while(j<=i){p=p->next;j++;} // 找应填入当前最小元素的位置，该位置保存在 q 中
min=p->key;q=p; // 将当前位置元素的值设为初始最小值
while(p->next!=head->next){
if(min>p->key){min=p->key;t=p;} // 找当前最小元素，并保存在 t 所指位置中
p=p->next;
}
t->key=q->key;q->key=min;j=1; // 交换 q 位置元素和最小元素的值
}
}
【分析】本题不需要修改链表中的各个指针。
--------------------------------------------------------------------------
前几天根据快速排序 Quick Sort算法的基本思想，编写了如下分治策略的算法，供大家讨论：
思路：
设输入的序列L[p..r]，确定支点元素l[p]和l[r],并使l[p].key<=l[r].key
分解(Divide)：将序列L[p..r]划分成三个子序列L[p..k-1]、L[k+1..m-1]和L[m+1..r]，使L[p..q]中关系为L[p..k-1]、l[k]、L[k+1..m-1]、l[m]、L[m+1..r]任一区间元素的值不大于其后区间元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..k-1]、L[k+1..m-1]和L[m+1..r]进行排序。
算法的实现（用C语言实现）
QSort(Sqlist &L,int low,int high){
c=high-low; /*循环次数*/
if(c<10)直接调用插入排序法; /*小数时直接调用插入排序法*/
if(L.r[low].key>L.r[high].key)L.r[low]<->L.r[high]; /*确保区间内第一个元素的值不大于区间内最后一个元素的值*/
ilow=low; /*小于区间内第一个元素的值数组边界下标*/
ihigh=high; /*大于区间内最后一个元素的值数组边界下标*/
for(i=low+1;i<c;i++){
if(L.r[i].key<L.r[low].key)L.r[i]<->L.r[++ilow]; /*小于区间内第一个元素的值放置ilow区间内*/
else
if(L.r[i].key>L.r[high].key){
L.r[i]<->L.r[--ihigh]; /*大于区间内最后一个元素的值放置ihigh区间内*/
i--; /*下一个比较位置不变*/
c--; /*循环次数减一*/
}
}
L.r[ilow]<->L.r[low]; /*将小于区间内第一个元素的边界下标元素与第一个元素互换*/
L.r[ihigh]<->L.r[high]; /*将大于区间内最后一个元素的边界下标元素与最后一个元素互换*/
QSort(L,low,ilow-1);
QSort(L,ilow+1,ihigh-1);
QSort(L,ihigh+1,high);
}
void QuickSort(Sqlist &L)
{
QSort(L,1,L.length);
}
优点：
1、每次快速排序将确定二个元素位置
2、每次快速排序将划分三个区间，优化后续平均时间和空间复杂度
缺点：
1、存在较多的元素交换（每次需要三步），不及改进快速排序法利用空穴赋值方便
--------------------------------------------------------------------------------------
四阶Runge-Kutta法
一阶常微分方程：
u'=f(t,u) a<t<b
u(t(0))=u(0)
Runge-Kutta非线性高阶单步法，p阶R-K法的整体阶段误差为O(h^p)
R-K四阶算法：
u(i+1)=u(i)+h*(k1+3*k2+3*k3+k4)/8
k1=f(t(i),u(i))
k2=f(t(i+h/3),u(i+h*k1/3))
k3=f(t(i+h/3),u(i+h*k2/3))
k4=f(t(i+h),u(i+h*k3))
四阶程序如下：
class RK{
private:
double k1,k2,k3,k4;
double h,b,u,a;
public:
void seth(double l=0){h=l;} //设步长
void setf(double xa=0,double xb=0,double y=0) //设初值和范围（xa,xb）
{
b=xb;
a=xa;
u=y;
}
double f(double t,double u) //函数值，修改它以适应各自需要
{
//函数设定
double f=u-2*t/u;
return f;
}
void dork() //R-K 主函数
{
for(int count=0;count<(b-a)/h;count++)
{
k1=f(a+count*h,u);
k2=f(a+count*h+h/3,u+h*k1/3);
k3=f(a+count*h+2*h/3,u-h*k1/3+h*k2);
k4=f(a+count*h+h,u+h*k1-h*k2+h*k3);
u=u+h*(k1+3*k2+3*k3+k4)/8;
count<<u<<endl;
}
}
};
void main()
{
RK my;
my.seth(0.1);
my.setf(0,1,1);
my.dork();
}
--------------------------------------------------------------------------------------
快速排序
算法的基本思想：
快速排序的基本思想是基于分治策略的。对于输入的子序列ap..ar，假如规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列ap..ar划分成两个非空子序列ap..aq和aq+1..ar，使ap..aq中任一元素的值不大于aq+1..ar中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对ap..aq和aq+1..ar进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在ap..aq和aq+1..ar都排好序后不需要执行任何计算ap..ar就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
算法Quick_Sort的实现：
Pascal实现：
Procedure Quick_Sort(p,r:TPosition;var L:TList); {快速排序}
var
q:TPosition;
begin
if L[p..r]足够小 then Sort(p,r,L) {若L[p..r]足够小则直接对L[p..r]排序}
else
begin
q:=Partition(p,r,L); {将L[p..r]分解为L[p..q]和L[q+1..r]两部分}
Quick_Sort(p,q,L); {递归排序L[p..q]}
Quick_Sort(q+1,r,L); {递归排序L[q+1..r]}
end;
end;
--------------------------------------------------------------------------------------
【题目】设中序线索二叉树的结点结构为：|left|ltag|data|rtag|right|. 现已知中序线索
二叉树的根结点地址root。设计一程序，打印出该线索二叉树的中序遍历结果.不得
再使用O(n)级的辅存空间。
【来源】上海交通大学96年第十题（15')
【解答】intravers(root:bitree)
finished:=false;t:=root;
while not finished do
【
while t↑.ltag=0 do t:=t↑.lch // 左孩子不空
write(t↑.data); // 访问左孩子
if t↑.rtag=1 then
【t:=t↑.rch;{后继结点}
write(t↑.data);{访问当前根结点}
t:=t↑.rch{访问当前根结点的右孩子}
】
else
t:=t↑.rch; // 右孩子不空
if t↑.rch=nil then finished:=true
】
--------------------------------------------------------------------
【题目】请设计一个算法，把二叉树的叶子结点按从左到右的顺序连成一个单链表。二叉树
按lchild - rchild 的方式存储，链接时用叶子结点的rchild 域存放指针。
【来源】长沙铁道学院99年第四（3）题（8’）
【解答】
#include <stdio.h>
#include <alloc.h>
#include <string.h>
#include <ctype.h>
typedef struct node{
char c;
int count;
struct node *left,*right;
}bnode;
bnode *k,*m; // 分别记录叶子链表的第一及当前结点的前驱
bnode *creatree(bnode *ptr,char ch) // 建二叉树
{ int result;bnode *p,*r; // p 指向当前结点的最近的父结点
p=NULL;r=ptr;
while(r){ // 检查是否存在相同结点
result=(int)(r->c)-(int)(ch);
if(!result){r->count+=1;return r;}
else
{p=r;
r=result<0?r->right:r->left;
}
}
r=(struct node *)malloc(sizeof(bnode));// 建新结点
r->left=r->right=NULL;
r->c=(char)malloc(sizeof(char));
r->c=ch;r->count=1;
if(!ptr)return r;
else if(result>0) p->left=r;
else p->right=r;
return r;
}
leaflink(bnode *root)
{
if(!root)return;
if(root->left==NULL&&root->right==NULL){
if(k==NULL)k=m=root; // 保存找到的第一个叶子结点（k指针）
else {m->right=root;m=m->right;}}
if(root->left)leaflink(root->left);
if(root->right)leaflink(root->right);
return;
}
main()
{
char *s;
bnode *root=NULL;
printf("Input a string:");
scanf("%s",s);
do{
if(!root)root=creatree(root,*s);
else creatree(root,*s);
s+=1;
}while(*s);
leaflink(root); // 将叶结点链成链表
while(k){printf("%c",k->c);k=k->right;} // 输出该链表
}
【分析】建一个一般的二叉树假如采用递归的话，将对调用该二叉树造成不便；相反，采用
非递归建一个二叉排序树既简单又实用。
----------------------------------------------------------------------------------
【题目】在二叉树中查找值为x的结点，试编写算法打印值为x的结点的所有祖先，假设值为x
的结点不多于一个。分析算法的时间复杂度(不加分析直接写出结果得零分）。
【来源】上海交通大学98年第五题（15')
【解答】proc searchx(p:bitree)
setnull(s);found:=false;
count:=0;
lflag[1..n]:=0;{lflag、rflag分别保存结点p的左右孩子是否已访问}
rflag[1..n]:=0;{初始状态为未被访问}
while not found and count<=n do
【if p↑.data=x then found:=true;{退出}
if lflag[p]=0 and p↑.left<>nil then
【push(s,p);count:=count+1;lflag[p]=1;p:=p↑.left;】
else
【if rflag[p]=0 and p↑.right<>nil then
【push(s,p);count:=count+1;rflag[p]=1;p:=p↑.right;】
else pop(s,p)
】
】
if found then
【while not empty(s) do【pop(s,p);write(p↑.data)】{打印祖先结点}】
else
write("error")
endp;
【时间复杂度分析】本题实际上是先序遍历的一个应用，因此算法的复杂度和先序遍历相同，
为O(n).
| -----------------------------------------------------------------------------------
用栈和递归求解两顶点的所有简单路径
栈和递归在程序设计中的应用是非常广的，比如对于迷宫的求解、表达式的求解，等都可以用栈来解决，典型的hanoi塔问题，树和图的遍历等都可以用递归来解决，在数据结构等很多书中都有介绍，假如对此不了解，可去参考。递归算法的设计实际上就是对问题的抽象的过程，假如抽象到每个小问题都有相同特征时，那就形成了递归，递归算法简明易懂，下面我就介绍一种利用到栈与递归求解两顶点所有简单路径的问题。
先说明一下什么叫“两顶点的所有简单路径”的概念，“两顶点的所有简单路径”的意思通熟的讲就是在图中有若干点，点与点之间可有边相连（在数据结构中叫“图”），任意设个起点和终点，现在要求的是从起点到终点所有可能通过的边序列的集合。（注：是简单有序边，也就是说简单路径，所谓简单路径就是序列中顶点不重复出现的路径。）举个例子：从上海到北京，我可以直接到达，也可以先到四川，再到北京，或者先到广东，再到北京，等等。如：上海->四川->上海->北京，这就不是简单路径了，显然，不是简单的路径有无数条。
为了描述方便，我用了简单的二维数组来做存储结构。（当然，完全可以用邻接矩阵、邻接表、十字链表、邻接多重表等来表示）* * *
* * *
* * *
如上图左上角的坐标为(1,1)，右上角的坐标为(3,1)，左下角的坐标为(1,3)，右下角的坐标为(3,3)，点与点之间都可相通，假设从点(1,1)要到(3,3)，有多少种走法？
对这个问题的求解先要熟悉到它的本质，其本质是一个点有四个方向（各边非凡处理），依次探索四个方向上的点，判定是不是最后的目的地，假如是，则进栈并返回，假如不是则进栈，将此点同样上述处理。显然这个过程是一个递归的过程，直到是最后的目的地，才层层返回。
当然，解决此问题不是只有栈与递归才能解决，经我自己摸索，用生成树的方法访问其双亲结点，也可解决，假如有更好的方法，请多多指教。
注重:当运行程序时,输入的maxx,maxy的数最好小等于3,不然效率很低!
作者：张钧卿
本程序本站没有测试!
//用栈和递归求解两顶点的所有简单路径
//borland c++ 3.1下编译通过
#include <stdlib.h>
#include <iostream.h>
#define SIZE 100
#define STACK_INIT_SIZE 1
#define STACKINCREMENT 1
typedef struct pos{
int x,y;
}pos;
typedef struct{
pos *base,*top;
int stacksize;
}sqstack;
sqstack s;
pos pstack[SIZE][SIZE];
int m=0,maxx,maxy;
int initstack(sqstack &s){
s.base=(pos *)malloc(STACK_INIT_SIZE*sizeof(pos));
s.top=s.base;
s.stacksize=STACK_INIT_SIZE;
return 1;
}
int push(sqstack &s,pos e){
if(s.top-s.base>=s.stacksize){
s.base=(pos *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(pos));
s.top=s.base+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return 1;
}
int pop(sqstack &s,pos &e){
if(s.top==s.base) return 0;
e=*--s.top;
return 1;
}
int stacktraverse(sqstack s,pos e){
int i;
for(i=0;(s.base+i)<=(s.top-1);i++)
if(((s.base+i)->x==e.x) && ((s.base+i)->y==e.y)) return 0;
return 1;
}
void list(int maxx,int maxy,pos a,pos b)
{
int fx,n;pos c;
push(s,a);
if(a.x==b.x && a.y==b.y)
{
for(n=0;(s.base+n)<=(s.top-1);n++) pstack[m][n]=*(s.base+n);m++;
pop(s,c);
return;
}
for(fx=1;fx<=4;fx++)
{
switch(fx)
{
case 1:
{if(a.x<maxx) {c.x=a.x+1;c.y=a.y;break;} else continue;}
case 2:
{if(a.y<maxy) {c.x=a.x;c.y=a.y+1;break;} else continue;}
case 3:
{if(a.x>1) {c.x=a.x-1;c.y=a.y;break;} else continue;}
case 4:
{if(a.y>1) {c.x=a.x;c.y=a.y-1;break;} else continue;}
}
if(stacktraverse(s,c)) list(maxx,maxy,c,b);
}
pop(s,c);
}
main()
{
int i,j;
pos a,b;
cout<<"max x=";
cin>>maxx;
cout<<"max y=";
cin>>maxy;
cout<<"start x=";
cin>>a.x;
cout<<"start y=";
cin>>a.y;
cout<<"end x=";
cin>>b.x;
cout<<"end y=";
cin>>b.y;
initstack(s);
list(maxx,maxy,a,b);
for(i=0;i<=m-1;i++){
for(j=0;j<=SIZE;j++)
{cout<<'('<<pstack[i][j].x<<','<<pstack[i][j].y<<')'<<" ";
if(pstack[i][j].x==b.x && pstack[i][j].y==b.y) break;}
cout<<"\n";}
return 1;
}
-------------------------------------------------------------------------------
Bubble Sort(冒泡法)
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注重两个相邻的元素的顺序是否正确。假如发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。
Bubble Sort程序：
STL C++程序：(VC++6.0通过)
#include "stdafx.h"
#include "iostream.h"
template<class T>
class doit{
private:
int x,y;
T temp;
public:
doit(T* in,int count)
{
for(y=0;y<count-1;y++)
{
for(x=1;x<count-y;x++)
{
if((*(in+x))>(*(in+x-1)))
{
temp=(*(in+x-1));
(*(in+x-1))=(*(in+x));
(*(in+x))=temp;
}
}
}
}
};
int main()
{
double a[4]={1.1,1.3,1.9,2.2};
doit<double> d(a,4);
for(int i=0;i<4;i++)
{
cout<<a[i]<<endl;
}
return 0;
}
C语言程序：(TC 2.0通过)
void doit(float* in,int count)
{
int x;
int y;
float temp;
for(y=0;y<count-1;y++)
{
for(x=1;x<count-y;x++)
{
if((*(in+x))>(*(in+x-1)))
{
temp=(*(in+x-1));
(*(in+x-1))=(*(in+x));
(*(in+x))=temp;
}
}
}
}
| ------------------------------------------------------------
选择排序(Selection Sort)
选择排序的基本思想是对待排序的记录序列进行n-1遍的处理，第i遍处理是将ai,…,an中最小者与ai交换位置。这样，经过i遍处理之后，前i个记录的位置已经是正确的了。
直接选择排序:
void docr(float *in,int count)
{
int i;
int j;
int x=0;
float temp;
for(i=0;i<count;i++)
{
temp=*(in+i);
x=i;
for(j=i;j<count;j++)
{
if(*(in+j)<temp)
{
temp=*(in+j);
x=j;
}
}
*(in+x)=*(in+i);
*(in+i)=temp;
}
}
总移动次数：3(n-1)
比较次数：n(n-1)/2
-------------------------------------------------------
如何产生素数
Solovag-Strasson
Robert Solovag和Volker Strasson开发了一种概率的基本测试算法。这个算法使用了雅可比函数来测试p是否为素数：
（1） 选择一个小于p的随机数a。
（2） 假如GCD（a,p）<>1，那么p通不过测试，它是合数。
（3） 计算j=a^(p-1)/2 mod p。
（4） 计算雅可比符号J（a,p）。
（5） 假如j<>J（a,p），那么p肯定不是素数。
（6） 假如j=J(a,p),那麽p不是素数的可能性值多是50%
数a被称为一个证据，假如a不能确定p，p肯定不是素数。假如p是合数。随机数a是证据的概率不小于50%。对a选择t个不同的随机值，重复t次这种测试。p通过所有t次测试后，它是合数的可能性不超过1/2^t。
Lehmann
另一种更简单的测试是由Lehmann独自研究的。下面是它的测试算法：
（1） 选择一个小于p的随机数a。
（2） 计算a^(p-1)/2 mod p
（3） 假如a^(p-1)/2<>1或-1（mod p），那么p肯定不是素数。
（4） 假如a^(p-1)/2=1或-1（mod p），那麽p不是素数的可能性值多是50%
同样，重复t次，那麽p可能是素数所冒的错误风险不超过1/2^t。
Rabin-Miller
这是个很轻易且广泛使用的简单算法，它基于Gary Miller的部分象法，有Michael Rabin发展。事实上，这是在NIST的DSS建议中推荐的算法的一个简化版。
首先选择一个代测的随机数p，计算b，b是2整除p-1的次数。然后计算m，使得n=1+(2^b)m。
（1） 选择一个小于p的随机数a。
（2） 设j=0且z=a^m mod p
（3） 假如z=1或z=p-1，那麽p通过测试，可能使素数
（4） 假如j>0且z=1, 那麽p不是素数
（5） 设j=j+1。假如j<b且z<>p-1,设z=z^2 mod p，然后回到(4)。假如z=p-1，那麽p通过测试，可能为素数。
（6） 假如j=b 且z<>p-1，不是素数
这个测试较前一个速度快。数a被当成证据的概率为75%。这意味着当迭代次数为t时，它产生一个假的素数所花费的时间不超过1/4^t。实际上，对大多数随机数，几乎99.99%肯定a是证据。
实际考虑：
在实际算法，产生素数是很快的。
（1） 产生一个n-位的随机数p
（2） 设高位和低位为1（设高位是为了保证位数，设低位是为了保证位奇数）
（3） 检查以确保p不能被任何小素数整除：如3，5，7，11等等。有效的方法是测试小于2000的素数。使用字轮方法更快
（4） 对某随机数a运行Rabin-Miller检测，假如p通过，则另外产生一个随机数a,在测试。选取较小的a值，以保证速度。做5次 Rabin-Miller测试假如p在其中失败，从新产生p，再测试。
在Sparc II上实现： 2 .8秒产生一个256位的素数
24.0秒产生一个512位的素数
2分钟产生一个768位的素数
5.1分钟产生一个1024位的素数
视频教程列表
文章教程搜索
C语言程序设计推荐教程
C语言程序设计热门教程
|
QQ：2693987339(点击联系)购买教程光盘
:
