❶ 求RSA密码的c语言实现算法的源程序（可通过运行）（1024位的）
加密的时候，输入Y，然后输入要加密的文本（大写字母）
解密的时候，输入N，然后输入一个整数n表示密文的个数，然后n个整数表示加密时候得到的密文。
/*RSA algorithm */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MM 7081
#define KK 1789
#define PHIM 6912
#define PP 85
typedef char strtype[10000];
int len;
long nume[10000];
int change[126];
char antichange[37];
void initialize()
{ int i;
char c;
for (i = 11, c = 'A'; c <= 'Z'; c ++, i ++)
{ change[c] = i;
antichange[i] = c;
}
}
void changetonum(strtype str)
{ int l = strlen(str), i;
len = 0;
memset(nume, 0, sizeof(nume));
for (i = 0; i < l; i ++)
{ nume[len] = nume[len] * 100 + change[str[i]];
if (i % 2 == 1) len ++;
}
if (i % 2 != 0) len ++;
}
long binamod(long numb, long k)
{ if (k == 0) return 1;
long curr = binamod (numb, k / 2);
if (k % 2 == 0)
return curr * curr % MM;
else return (curr * curr) % MM * numb % MM;
}
long encode(long numb)
{ return binamod(numb, KK);
}
long decode(long numb)
{ return binamod(numb, PP);
}
main()
{ strtype str;
int i, a1, a2;
long curr;
initialize();
puts("Input 'Y' if encoding, otherwise input 'N':");
gets(str);
if (str[0] == 'Y')
{ gets(str);
changetonum(str);
printf("encoded: ");
for (i = 0; i < len; i ++)
{ if (i) putchar('-');
printf(" %ld ", encode(nume[i]));
}
putchar('\n');
}
else
{ scanf("%d", &len);
for (i = 0; i < len; i ++)
{ scanf("%ld", &curr);
curr = decode(curr);
a1 = curr / 100;
a2 = curr % 100;
printf("decoded: ");
if (a1 != 0) putchar(antichange[a1]);
if (a2 != 0) putchar(antichange[a2]);
}
putchar('\n');
}
putchar('\n');
system("PAUSE");
return 0;
}
测试：
输入：
Y
FERMAT
输出：
encoded: 5192 - 2604 - 4222
输入
N
3 5192 2604 4222
输出
decoded: FERMAT
❷ 急！那位大侠有用C语言实现的互相关算法的源代码，谢谢啦
#include <math.h>
#define M_PI 3.14159265358979323846
#define FALSE 0
#define TRUE 1
#define BIG 1e10
#define SMALL 1e-10
typedef struct {
float r, i;
} complex;
/* FAST CORRELATION OF X(0:L) AND Y(0:L). FINDS RXY(0) THRU RXY(NMAX). */
/* L=LAST INDEX IN BOTH X AND Y. MUST BE (POWER OF 2)+1 AND AT LEAST 5. */
/* ITYPE=TYPE OF CORRELATION=0 IF X AND Y ARE THE SAME VECTOR (AUTO- */
/* CORRELATION), OR NOT 0 IF X AND Y ARE DIFFERENT VECTORS. */
/* NMAX=MAXIMUM LAG OF INTEREST IN THE CORRELATION FUNCTION. */
/* FFT LENGTH ,N, USED INTERNALLY, IS L-1. */
/* LET K=INDEX OF FIRST NONZERO SAMPLE IN Y(0)---Y(N-1). THEN X(0) */
/* 到 X(N-1) MUST INCLUDE PADDING OF AT LEAST NMAX-K ZEROS. */
/* CORRELATION FUNCTION, RXY, REPLACES X(0) THRU X(NMAX). */
/* Y(0) THRU Y(L) IS REPLACED BY ITS FFT, COMPUTED USING SPFFTR. */
/* IERROR=0 NO ERROR DETECTED */
/* 1 L-1 NOT A POWER OF 2 */
/* 2 NMAX OUT OF RANGE */
/* 3 INADEQUATE ZERO */
void spcorr(float *x, float *y, long *l, long *type, long *nmax, long *error)
/*
x:序列X；
y：序列Y；
l:序列X与序列Y的长度，不小5，且要为2的幂次方；
type:相关的类型，0：表示X与Y序列相同，其它值：X与Y序列不相同
nmax:相关的最大时延；
error:运行出错提示；0：无错；1：数据长度不是2的幂次方；2：时延超界；3：无足够零填充出错
*/
{
long j, k, m, n;//n:FFT长度；k:序列Y中的首个非零样本的位置序号；在序列Y中必须最少包含有(nmax-k)零填充。
complex cx;
float test;
n = *l - 1;
if (*nmax < 0 || *nmax >= n)
{
*error = 2;
return;
}
test = (float) n;
test /= 2.0;
while ((test - 2.0) > 0.0)
{
test /= 2.0;
}
if ((test - 2.0) == 0)
{
for (k = 0 ; k < n && y[k] == 0.0 ; ++k) ;
for (j = n - 1 ; j >= 0 && x[j] == 0.0 ; --j) ;
if ((n - 1 - j) < (*nmax - k))
{
*error = 3;
return;
}
spfftr(x, &n);//对X序列FFT变换
if (*type != 0)
{
spfftr(y, &n);//如果X、Y是相同序列，则对Y序列也进行FFT
}
for (m = 0 ; m <= (n / 2) ; ++m)
{
cx.r = x[m * 2] * y[m * 2] - -x[(m * 2) + 1] * y[(m * 2) + 1];
cx.i = x[m * 2] * y[(m * 2) + 1] + -x[(m * 2) + 1] * y[m * 2];
x[m * 2] = cx.r / n;
x[(m * 2) + 1] = cx.i / n;
}
spiftr(x, &n);
*error = 0;
}
else if ((test - 2.0) < 0.0)
{
*error = 1;
}
return;
} /* spcorr */
/* SPFFTR 11/12/85 */
/* FFT ROUTINE FOR REAL TIME SERIES (X) WITH N=2**K SAMPLES. */
/* COMPUTATION IS IN PLACE, OUTPUT REPLACES INPUT. */
/* INPUT: REAL VECTOR X(0:N+1) WITH REAL DATA SEQUENCE IN FIRST N */
/* ELEMENTS; ANYTHING IN LAST 2. NOTE: X MAY BE DECLARED */
/* REAL IN MAIN PROGRAM PROVIDED THIS ROUTINE IS COMPILED */
/* SEPARATELY ... COMPLEX OUTPUT REPLACES REAL INPUT HERE. */
/* OUTPUT: COMPLEX VECTOR XX(O:N/2), SUCH THAT X(0)=REAL(XX(0)),X(1)= */
/* IMAG(XX(0)), X(2)=REAL(XX(1)), ..., X(N+1)=IMAG(XX(N/2). */
/* IMPORTANT: N MUST BE AT LEAST 4 AND MUST BE A POWER OF 2. */
//FFT计算函数
void spfftr(complex *x, long *n)
{
/* Builtin functions */
void r_cnjg();
/* Local variables */
void spfftc();
long m, tmp_int;
complex u, tmp, tmp_complex;
float tpn, tmp_float;
tpn = (float) (2.0 * M_PI / (double) *n);
tmp_int = *n / 2;
spfftc(x, &tmp_int, &neg_i1);
x[*n / 2].r = x[0].r;
x[*n / 2].i = x[0].i;
for (m = 0 ; m <= (*n / 4) ; ++m)
{
u.r = (float) sin((double) m * tpn);
u.i = (float) cos((double) m * tpn);
r_cnjg(&tmp_complex, &x[*n / 2 - m]);
tmp.r = (((1.0 + u.r) * x[m].r - u.i * x[m].i)
+ (1.0 - u.r) * tmp_complex.r - -u.i * tmp_complex.i) / 2.0;
tmp.i = (((1.0 + u.r) * x[m].i + u.i * x[m].r)
+ (1.0 - u.r) * tmp_complex.i + -u.i * tmp_complex.r) / 2.0;
tmp_float = ((1.0 - u.r) * x[m].r - -u.i * x[m].i
+ (1.0 + u.r) * tmp_complex.r - u.i * tmp_complex.i) / 2.0;
x[m].i = ((1.0 - u.r) * x[m].i + -u.i * x[m].r
+ (1.0 + u.r) * tmp_complex.i + u.i * tmp_complex.r) / 2.0;
x[m].r = tmp_float;
r_cnjg(&x[*n / 2 - m], &tmp);
}
return;
} /* spfftr */
/* SPIFTR 02/20/87 */
/* INVERSE FFT OF THE COMPLEX SPECTRUM OF A REAL TIME SERIES. */
/* X AND N ARE THE SAME AS IN SPFFTR. IMPORTANT: N MUST BE A POWER */
/* OF 2 AND X MUST BE DIMENSIONED X(0:N+1) (REAL ARRAY, NOT COMPLEX). */
/* THIS ROUTINE TRANSFORMS THE OUTPUT OF SPFFTR BACK INTO THE INPUT, */
/* SCALED BY N. COMPUTATION IS IN PLACE, AS IN SPFFTR. */
//逆FFT变换函数
void spiftr(complex *x, long *n)
{
long m, tmp_int;
complex u, tmp_complex, tmp;
float tpn, tmp_float;
tpn = (float) (2.0 * M_PI / (double) *n);
for (m = 0 ; m <= (*n / 4) ; ++m)
{
u.r = (float) sin((double) m * tpn);
u.i = (float) -cos((double) m * tpn);
r_cnjg(&tmp_complex, &x[*n / 2 - m]);
tmp.r = ((1.0 + u.r) * x[m].r - u.i * x[m].i)
+ ((1.0 - u.r) * tmp_complex.r - -u.i * tmp_complex.i);
tmp.i = ((1.0 + u.r) * x[m].i + u.i * x[m].r)
+ ((1.0 - u.r) * tmp_complex.i + -u.i * tmp_complex.r);
r_cnjg(&tmp_complex, &x[*n / 2 - m]);
tmp_float = ((1.0 - u.r) * x[m].r - -u.i * x[m].i)
+ ((1.0 + u.r) * tmp_complex.r - u.i * tmp_complex.i);
x[m].i = ((1.0 - u.r) * x[m].i + -u.i * x[m].r)
+ ((1.0 + u.r) * tmp_complex.i + u.i * tmp_complex.r);
x[m].r = tmp_float;
r_cnjg(&x[*n / 2 - m], &tmp);
}
tmp_int = *n / 2;
spfftc(x, &tmp_int, &pos_i1);
return;
} /* spiftr *
void r_cnjg(complex *r, complex *z)
{
r->r = z->r;
r->i = -z->i;
}
❸ 地杰斯特拉算法求最短路径C语言实现。求源代码！！！！！
没有用数据测试，你可以测一下，如果不对把不对的数据发上来再改
#include<stdio.h>
#define N 100
#define MaxDist 10000
int mapdist[N][N];
int mindist[N];
void Dijkstra(int n,int c)
{
int i,tag[N],minc,t,j;
for(i=1;i<=n;++i)
{
if(mapdist[c][i]>=0)
mindist[i]=mapdist[c][i];
else
mindist[i]=MaxDist;
tag[i]=0;
}
for(j=1;j<=n;++j)
{
minc=MaxDist;
for(i=1;i<=n;++i)
{
if(minc>mindist[i]&&(!tag[i]))
{
minc=mindist[i];
t=i;
}
}
tag[t]=1;
for(i=1;i<=n;++i)
{
if((mindist[i]>mindist[t]+mapdist[t][i])&&(!tag[i]))
mindist[i]=mindist[t]+mapdist[t][i];
}
}
}
int main()
{
int i,j,n,c;
scanf("%d%d",&n,&c);//c为源点
for(i=1;i<=n;++i)
{
for(j=1;j<=n;++j)
scanf("%d",&mapdist[i][j]);//-1表示不直接连通
}
Dijkstra(n,c);
for(i=1;i<=n;++i)
printf("%d",mindist[i]);
return 0;
}
❹ 怎么用c语言实现单源最短路径问题要求是用Dijkstra算法，最好写出所有的代码 ，包括结构定义等等，对一
C语言代码：//清华大学出版社光盘的代码
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D)
{ // 算法7.15
// 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]
// 及其带权长度D[v]。
// 若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。
// final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。
int i=0,j, v,w,min;
bool final[MAX_VERTEX_NUM];
for (v=0; v<G.vexnum; ++v) {
final[v] = FALSE;
D[v] = G.arcs[v0][v].adj;
for (w=0; w<G.vexnum; ++w) P[v][w] = FALSE; // 设空路径
if (D[v] < INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; }
}
D[v0] = 0; final[v0] = TRUE; // 初始化，v0顶点属于S集
//--- 开始主循环，每次求得v0到某个v顶点的最短路径，并加v到S集 ---
for (i=1; i<G.vexnum; ++i) { // 其余G.vexnum-1个顶点
min = INFINITY; // 当前所知离v0顶点的最近距离
for (w=0; w<G.vexnum; ++w)
if (!final[w]) // w顶点在V-S中
if (D[w]<min) { v = w; min = D[w]; } // w顶点离v0顶点更近
final[v] = TRUE; // 离v0顶点最近的v加入S集
for (w=0; w<G.vexnum; ++w) // 更新当前最短路径及距离
if (!final[w] && (min+G.arcs[v][w].adj<D[w])) {
// 修改D[w]和P[w], w∈V-S
D[w] = min + G.arcs[v][w].adj;
for(j=0;j<G.vexnum;j++) P[w][j] = P[v][j]; //第v行赋值于第w行
P[w][w] = TRUE; // P[w] = P[v]+[w]
}//if
}//for
} // ShortestPath_DIJ
❺ 谁有KMP算法的C语言实现啊
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<assert.h>
#include<stdlib.h>
void getNext(const char * t,int * Next)//get the Next array
{
int k=-1;
int j=0;
int size=strlen(t);
Next[0]=-1;
while(j<size)
{
if(k==-1||t[j]==t[k])//if k==-1 there are two conditions
//one is this is the first time entering the loop
{ //if t[j]==t[k] get the next[j+1] directly
k++;//the other is the end of the iteration cos k==-1;
j++;
Next[j]=k;//whatever Next[j]=k
}
else
k=Next[k];
}
}
int myStrstr(const char * Dest,const char *subStr)//find the starting position of the sub
{ //in the Dest through KMP
int destSize=strlen(Dest);
int subSize=strlen(subStr);
int i,j;
int * Next=(int *)(malloc(sizeof(int)*subSize));
i=j=0;
assert((Dest!=NULL)&&(subStr!=NULL));
getNext(subStr,Next);
while(i<destSize&&j<subSize)
{
if(j==-1||Dest[i]==subStr[j])//if j==-1 the main string need match the next elements
{ //and the subString begin from the beginning
i++; //if Dest[i]==subStr[j] both string need shift to the
j++; // next elements
}
else
j=Next[j]; //if match fail,glide back to Next[j]
}
if(j==subSize)return i-j;
return -1;
}
int main()
{
char *temp,*sub,* Dest;//to store the substring to be matched
int ch;
unsigned int templen,length=20*sizeof(char);
unsigned int mlength=20*sizeof(char);//the original length of the memory
sub=(char*)malloc(length);
Dest=(char*)malloc(length);
if(sub==NULL||Dest==NULL)//allocation failure
{
printf("memory allocate failure\n");
exit(0);
}
temp=sub;
printf("please input the substring:\n");
while((ch=getchar())!=10)//read the sub String
{
if((temp-sub)/sizeof(char)==length)//if running out of the memory
{
templen=length;
sub=realloc(sub,length+=20*sizeof(char));
if(sub==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=sub+templen*sizeof(char);//reset the temp cos the sub may change its value
}
*temp++=ch;
}
*temp='\0';
temp=Dest;
printf("please input the mainstring:\n");
while((ch=getchar())!=10)//read the main String
{
if((temp-Dest)/sizeof(char)==mlength)
{
templen=mlength;
Dest=realloc(Dest,mlength+=20*sizeof(char));//if running out of the memory
if(Dest==NULL)
{
printf("sub memory allocate failure\n");
exit(0);
}
temp=Dest+templen*sizeof(char);//reset the temp cos the Dest may change its value
}
*temp++=ch;
}
*temp='\0';
printf("the starting position is :%d\n",myStrstr(Dest,sub));//get the starting position
free(Dest);
free(sub);
return 0;
}
❻ 求C语言源代码，实现如下功能：从屏幕上输入7个数字，程序输出由这7个数字中抽出的 3 个数字的组合
要源码的话需要一定时间才能出来，不过算法倒是可以给你
设3个变量xyz，xyz循环取1~7且设置循环条件为x<y<z，当3者全不等时输出（共3层嵌套，xyz各一层）
主要代码：（数组a[6]为输入的7个数字）
#include "stdio.h"
int main(){
int a[6];
for(int i=0;i<=6;i++)
scanf("%d",&a[i]);
for(int x=0;x<=4;x++)
for(int y=x+1;y<=5;y++)
for(int z=y+1;z<=6;z++)
printf("%d ",a[x]*100+a[y]*10+a[z]);
return 0;
}
❼ C语言。编程实现简单的四则运算。比如输入3+5=8，输入3*5=15。要有算法分析图和完整的源代码
#include <stdio.h>
int main()
{int a,b,c;
char op;
scanf("%d%c%d",&a,&op,&b);
while(op!='+'&&op!='-'&&op!='*'&&op!='/')
{printf("只能计算加减乘除，请重新输入： ");
scanf("%d%c%d",&a,&op,&b);
}
if(op=='/'&&b==0)
{printf("divided by zero. ");
return (1);
}
switch(op)
{case '+':c=a+b;break;
case '-':c=a-b;break;
case '*':c=a*b;break;
case '/':c=a/b;break;
}
printf("%d%c%d=%d ",a,op,b,c);
return 0;
}
❽ 急求lzw算法的英文文本压缩C语言源代码！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>//用来计算压缩的时间
using namespace std;
//定义常数
const int MAX = 1000003;//最大code数，是一个素数，求模是速度比较快
const int ascii = 256; //ascii代码的数量
const int ByteSize = 8; //8个字节
struct Element//hash表中的元素
{
int key;
int code;
Element *next;
}*table[MAX];//hash表
int hashfunction(int key)//hash函数
{
return key%MAX;
}
void hashinit(void)//hash表初始化
{
memset(table,0,sizeof(table));
}
void hashinsert(Element element)//hash表的插入
{
int k = hashfunction(element.key);
if(table[k]!=NULL)
{
Element *e=table[k];
while(e->next!=NULL)
{
e=e->next;
}
e->next=new Element;
e=e->next;
e->key = element.key;
e->code = element.code;
e->next = NULL;
}
else
{
table[k]=new Element;
table[k]->key = element.key;
table[k]->code = element.code;
table[k]->next = NULL;
}
}
bool hashfind(int key,Element &element)//hash表的查找
{
int k = hashfunction(key);
if(table[k]!=NULL)
{
Element *e=table[k];
while(e!=NULL)
{
if(e->key == key)
{
element.key = e->key;
element.code = e->code;
return true;
}
e=e->next;
}
return false;
}
else
{
return false;
}
}
void compress(void)//压缩程序
{
//打开一个流供写入
FILE *fp;
fp = fopen("result.dat", "wb");
Element element;
int used;
char c;
int pcode, k;
for(int i=0;i<ascii;i++)
{
element.key = i;
element.code = i;
hashinsert(element);
}
used = ascii;
c = getchar();
pcode = c;
while((c = getchar()) != EOF)
{
k = (pcode << ByteSize) + c;
if(hashfind(k, element))
pcode = element.code;
else
{
//cout<<pcode<<' ';
fwrite(&pcode, sizeof(pcode), 1, fp);
element.code = used++;
element.key = (pcode << ByteSize) | c;
hashinsert(element);
pcode = c;
}
}
//cout<<pcode<<endl;
fwrite(&pcode, sizeof(pcode), 1, fp);
}
int main(void)
{
int t1,t2;
//欲压缩的文本文件
//freopen("input.txt","r",stdin);
freopen("book5.txt","r",stdin);
t1=time(NULL);
hashinit();
compress();
t2=time(NULL);
cout<<"Compress complete! See result.dat."<<endl;
cout<<endl<<"Total use "<<t2-t1<<" seconds."<<endl;
❾ 求RSA算法的源代码（c语言）
这个是我帮个朋友写的，写的时候发现其实这个没那么复杂，不过，时间复杂度要高于那些成型了的，为人所熟知的rsa算法的其他语言实现．
#include
int
candp(int
a,int
b,int
c)
{
int
r=1;
b=b+1;
while(b!=1)
{
r=r*a;
r=r%c;
b--;
}
printf("%d",r);
return
r;
}
void
main()
{
int
p,q,e,d,m,n,t,c,r;
char
s;
{printf("input
the
p:\n");
scanf("%d\n",&p);
printf("input
the
q:\n");
scanf("%d%d\n",&p);
n=p*q;
printf("so,the
n
is
%3d\n",n);
t=(p-1)*(q-1);
printf("so,the
t
is
%3d\n",t);
printf("please
intput
the
e:\n");
scanf("%d",&e);
if(e<1||e>t)
{printf("e
is
error,please
input
again;");
scanf("%d",&e);}
d=1;
while
(((e*d)%t)!=1)
d++;
printf("then
caculate
out
that
the
d
is
%5d",d);
printf("if
you
want
to
konw
the
cipher
please
input
1;\n
if
you
want
to
konw
the
plain
please
input
2;\n");
scanf("%d",&r);
if(r==1)
{
printf("input
the
m
:"
);/*输入要加密的明文数字*/
scanf("%d\n",&m);
c=candp(m,e,n);
printf("so
,the
cipher
is
%4d",c);}
if(r==2)
{
printf("input
the
c
:"
);/*输入要解密的密文数字*/
scanf("%d\n",&c);
m=candp(c,d,n);
printf("so
,the
cipher
is
%4d\n",m);
printf("do
you
want
to
use
this
programe:yes
or
no");
scanf("%s",&s);
}while(s=='y');
}
}
❿ c语言数据结构（考题，测试你的能力）－－编写源代码
P88 稀疏矩阵十字链表相加算法如下：
/*假设ha为A稀疏矩阵十字链表的头指针，hb为B稀疏矩阵十字链表的头指针*/
#include<stdio.h>
#define maxsize 100
struct linknode
{ int i,j;
struct linknode *cptr,*rptr;
union vnext
{ int v;
struct linknode *next;} k;
};
struct linknode creatlindmat( ) /*建立十字链表*/
{ int x, m, n, t, s, i, j, k;
struct linknode *p , *q, *cp[maxsize],*hm;
printf("请输入稀疏矩阵的行、列数及非零元个数\n");
scanf("%d%d%d",&m,&n,&t);
if (m>n) s=m; else s=n;
hm=(struct linknode*)malloc(sizeof(struct linknode)) ;
hm->i=m; hm->j=n;
cp[0]=hm;
for (i=1; i<=s;i++)
{ p=(struct linknode*)malloc(sizeof(struct linknode)) ;
p->i=0; p->j=0;
p->rptr=p; p->cptr=p;
cp[i]=p;
cp[i-1]->k.next=p;
}
cp[s]->k.next=hm;
for( x=1;x<=t;x++)
{ printf("请输入一个三元组(i,j,v)\n");
scanf("%d%d%d",&i,&j,&k);
p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=i; p->j=j; p->k.v=k;
/*以下是将p插入到第i行链表中 */
q=cp[i];
while ((q->rptr!=cp[i]) &&( q->rptr->j<j))
q=q->rptr;
p->rptr=q->rptr;
q->rptr=p;
/*以下是将P插入到第j列链表中*/
q=cp[j];
while((q->cptr!=cp[j]) &&( q->cptr->i<i))
q=q->cptr;
p->cptr=q->cptr;
q->cptr=p;
}
return hm;
}
/* ha和hb表示的两个稀疏矩阵相加，相加的结果放入ha中*/
struct linknode *matadd(struct linknode *ha, struct linknode *hb)
{ struct linknode *pa, *pb, *qa, *ca,*cb,*p,*q;
struct linknode *hl[maxsize];
int i , j, n;
if((ha->i!=hb->i)||(ha->j!=hb->j))
printf("矩阵不匹配,不能相加\n");
else
{ p=ha->k.next; n=ha->j;
for (i=1;i<=n; i++)
{ hl[i]=p;
p=p->k.next;
}
ca=ha->k.next; cb=hb->k.next;
while(ca->i==0)
{pa=ca->rptr; pb=cb->rptr;
qa=ca;
while(pb->j!=0)
{ if((pa->j<pb->j)&&(pa->j!=0))
{ qa=pa; pa=pa->rptr;}
else if ((pa->j>pb->j)||(pa->j==0)) /*插入一个结点*/
{ p=(struct linknode*)malloc(sizeof(struct linknode));
p->i=pb->i; p->j=pb->j;
p->k.v=pb->k.v;
qa->rptr=p; p->rptr=pa;
qa=p; pb=pb->rptr;
j=p->j; q=hl[j]->cptr;
while((q->i<p->i)&&(q->i!=0))
{ hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=p; p->cptr=q;
hl[j]=p;
}
else
{pa->k.v=pa->k.v+pb->k.v;
if(pa->k.v==0) /*删除一个结点*/
{ qa->rptr=pa->rptr;
j=pa->j; q=hl[j]->cptr;
while (q->i<pa->i)
{hl[j]=q; q=hl[j]->cptr;}
hl[j]->cptr=q->cptr;
pa=pa->rptr; pb=pb->rptr;
free(q);
}
else
{ qa=pa; pa=pa->rptr;
pb=pb->rptr;
}
}
}
ca=ca->k.next; cb=cb->k.next;
}
}
return ha;
}
void print(struct linknode *ha) /*输出十字链表*/
{ struct linknode *p,*q;
p=ha->k.next;
while(p->k.next!=ha)
{ q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
p=p->k.next;
}
q=p->rptr;
while(q->rptr!=p)
{ printf("%3d%3d%3d\t",q->i,q->j,q->k.v);
q=q->rptr;
}
if(p!=q)
printf("%3d%3d%3d",q->i,q->j,q->k.v);
printf("\n");
}
void main()
{
struct linknode *ha=NULL,*hb=NULL,*hc=NULL;
ha=creatlindmat( ); /*生成一个十字链表ha*/
hb=creatlindmat( ); /*生成另一个十字链表hb*/
printf("A:\n"); /*输出十字链表ha*/
print(ha);printf("\n");
printf("B:\n"); /*输出十字链表hb*/
print(hb);printf("\n");
hc=matadd(ha,hb); /*十字链表相加*/
printf("A+B:\n"); /*输出相加后的结果*/
print(hc);printf("\n");
}
P94 数据类型描述如下：
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
}
P95 数据类型描述如下：
struct node2
{ elemtype data;
struct node2 *link1,*link2;
}
P96 求广义表的深度depth(LS)
int depth(struct node1 *LS)
{
int max=0,dep;
while(LS!=NULL)
{ if(LS->atom==0) //有子表
{ dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
P96 广义表的建立creat(LS)
void creat(struct node1 *LS)
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node*)malloc(sizeof(struct node));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node*)malloc(sizeof(struct node));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
P97 输出广义表print(LS)
void print(struct node1 *LS)
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c ",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
P98 该算法的时间复杂度为O(n)。整个完整程序如下：
#include<stdio.h>
#define elemtype char
struct node1
{ int atom;
struct node1 *link;
union
{
struct node1 *slink;
elemtype data;
} ds;
};
void creat(struct node1 LS) /*建立广义表的单链表*/
{
char ch;
scanf("%c",&ch);
if(ch=='#')
LS=NULL;
else if(ch=='(')
{LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=0;
creat(LS->ds.slink);
}
else
{ LS=(struct node1*)malloc(sizeof(struct node1));
LS->atom=1;
LS->ds.data=ch;
}
scanf("%c",&ch);
if(LS==NULL);
else if(ch==',')
creat(LS->link);
else if((ch==')')||(ch==';'))
LS->link=NULL;
}
void print(struct node1 LS) /*输出广义单链表*/
{
if(LS->atom==0)
{
printf("(");
if(LS->ds.slink==NULL)
printf("#");
else
print(LS->ds.slink);
}
else
printf("%c",LS->ds.data);
if(LS->atom==0)
printf(")");
if(LS->link!=NULL)
{
printf(";");
print(LS->link);
}
}
int depth(struct node1 LS) /*求广义表的深度*/
{
int max=0;
while(LS!=NULL)
{ if(LS->atom==0)
{ int dep=depth(LS->ds.slink);
if(dep>max) max=dep;
}
LS=LS->link;
}
return max+1;
}
main()
{ int dep;
struct node1 *p=NULL;
creat(p); /*建立广义表的单链表*/
print(p); /*输出广义单链表*/
dep=depth(p); /*求广义表的深度*/
printf("%d\n",dep);
}
第六章 树
P109 二叉链表的结点类型定义如下：
typedef struct btnode
{ anytype data;
struct btnode *Lch,*Rch;
}tnodetype;
P109 三叉链表的结点类型定义如下：
typedef struct btnode3
{ anytype data;
struct btnode *Lch,*Rch，*Parent ;
}tnodetype3;
P112 C语言的先序遍历算法：
void preorder (tnodetype *t)
/*先序遍历二叉树算法，t为指向根结点的指针*/
{ if (t!=NULL)
{printf("%d ",t->data);
preorder(t->lch);
preorder(t->rch);
}
}
P113 C语言的中序遍历算法：
void inorder(tnodetype *t)
/*中序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{inorder(t->lch);
printf("%d ",t->data);
inorder(t->rch);
}
}
P113 C语言的后序遍历算法：
void postorder(tnodetype *t)
/*后序遍历二叉树算法，t为指向根结点的指针*/
{
if(t!=NULL)
{ postorder(t->lch);
postorder(t->rch);
printf("%d ",t->data);
}
}
P114 如果引入队列作为辅助存储工具，按层次遍历二叉树的算法可描述如下：
void levelorder(tnodetype *t)
/*按层次遍历二叉树算法，t为指向根结点的指针*/
{tnodetype q[20]; /*辅助队列*/
front=0;
rear=0; /*置空队列*/
if (t!=NULL)
{ rear++;
q[rear]=t; /*根结点入队*/
}
while (front!=rear)
{ front++;
t=q [front];
printf ("%c\n",t->data);
if (t->lch!=NULL) /*t的左孩子不空，则入队*/
{ rear++;
q [rear]=t->lch;
}
if (t->rch!=NULL) /*t的右孩子不空，则入队*/
{ rear++;
q [rear]=t->rch;
}
}
}
P115 以中序遍历的方法统计二叉树中的结点数和叶子结点数，算法描述为：
void inordercount (tnodetype *t)
/*中序遍历二叉树，统计树中的结点数和叶子结点数*/
{ if (t!=NULL)
{ inordercount (t->lch); /*中序遍历左子树*/
printf ("%c\n",t->data); /*访问根结点*/
countnode++; /*结点计数*/
if ((t->lch==NULL)&&(t->rch==NULL))
countleaf++; /*叶子结点计数*/
inordercount (t->rch); /*中序遍历右子树*/
}
}
P115 可按如下方法计算一棵二叉树的深度：
void preorderdeep (tnodetype *t,int j)
/*先序遍历二叉树，并计算二叉树的深度*/
{ if (t!=NULL)
{ printf ("%c\n",t->data); /*访问根结点*/
j++;
if (k<j) k=j;
preorderdeep (t->lch,j); /*先序遍历左子树*/
preorderdeep (t->rch,j); /*先序遍历右子树*/
}
}
P117 线索二叉树的结点类型定义如下：
struct nodexs
{anytype data;
struct nodexs *lch, *rch;
int ltag,rtag; /*左、右标志域*/
}
P117 中序次序线索化算法
void inorderxs (struct nodexs *t)
/*中序遍历t所指向的二叉树，并为结点建立线索*/
{ if (t!=NULL)
{ inorderxs (t->lch);
printf ("%c\n",t->data);
if (t->lch!=NULL)
t->ltag=0;
else { t->ltag=1;
t->lch=pr;
} /*建立t所指向结点的左线索，令其指向前驱结点pr*/
if (pr!=NULL)
{ if (pr->rch!=NULL)
pr->rtag=0;
else { pr->rtag=1;
pr->rch=p;
}
} /*建立pr所指向结点的右线索，令其指向后继结点p*/
pr=p;
inorderxs (t->rch);
}
}
P118 在中根线索树上检索某结点的前驱结点的算法描述如下：
struct nodexs * inpre (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的前驱结点*/
{ if (q->ltag==1)
p=q->lch;
else { r=q->lch;
while (r->rtag!=1)
r=r->rch;
p=r;
}
return (p);
}
P119 在中根线索树上检索某结点的后继结点的算法描述如下：
struct nodexs * insucc (struct nodexs *q)
/*在中根线索树上检索q所指向的结点的后继结点*/
{ if (q->rtag==1)
p=q->rch;
else { r=q->rch;
while (r->ltag!=1)
r=r->lch;
p=r;
}
return (p);
}
P120 算法程序用C语言描述如下：
void sortBT(BT *t,BT *s) /*将指针s所指的结点插入到以t为根指针的二叉树中*/
{ if (t==NULL) t=s; /*若t所指为空树，s所指结点为根*/
else if (s->data < t->data)
sortBT(t->lch,s); /*s结点插入到t的左子树上去*/
else
sortBT(t->rch,s); /*s结点插入到t的右子树上去*/
}
P121 二叉排序树结点删除算法的C语言描述如下：
void delnode(bt,f,p)
/*bt为一棵二叉排序树的根指针，p指向被删除结点，f指向其双亲*/
/*当p=bt时f为NULL*/
{ fag=0; /*fag=0时需修改f指针信息，fag=1时不需修改*/
if (p->lch==NULL)
s=p->rch; /*被删除结点为叶子或其左子树为空*/
else if (p->rch==NULL)
s=p->lch;
else { q=p; /*被删除结点的左、右子树均非空*/
s=p->lch;
while (s->rch!=NULL)
{ q=s;
s=s->rch;
} /*寻找s结点*/
if (q=p)
q->lch=s->lch;
else q->rch=s->lch;
p->data=s->data; /*s所指向的结点代替被删除结点*/
DISPOSE(s);
Fag=1;
}
if (fag=0) /*需要修改双亲指针*/
{ if (f=NULL)
bt=s; /*被删除结点为根结点*/
else if (f->lch=p)
f->lch=s;
else f->rch=s;
DISPOSE(p); /*释放被删除结点*/
}
}
第七章 图
P134 用邻接矩阵表示法表示图，除了存储用于表示顶点间相邻关系的邻接矩阵外，通常还需要用一个顺序表来存储顶点信息。其形式说明如下：
# define n 6 /*图的顶点数*/
# define e 8 /*图的边(弧)数*/
typedef char vextype; /*顶点的数据类型*/
typedef float adjtype; /*权值类型*/
typedef struct
{vextype vexs[n];
adjtype arcs[n][n];
}graph;
P135 建立一个无向网络的算法。
CREATGRAPH(ga) /*建立无向网络*/
Graph * ga;
{
int i,j,k;
float w;
for(i＝0;i<n;i++ )
ga ->vexs[i]＝getchar(); /*读入顶点信息，建立顶点表*/
for(i＝0;i<n;i++ )
for(j＝0;j<n;j++)
ga ->arcs[i][j]＝0; /*邻接矩阵初始化*/
for(k＝0;k<e;k++) /*读入e条边*/
(scanf("％d％d％f",&I,&j,&w); /*读入边(vi,vj)上的权w */
ga ->arcs[i][j]＝w;
ga - >arcs[j][i]＝w;
}
} /*CREATGRAPH*/
P136 邻接表的形式说明及其建立算法：
typedef struct node
{int adjvex; /*邻接点域*/
struct node * next; /*链域*/
}edgenode; /*边表结点*/
typedef struct
{vextype vertex; /*顶点信息*/
edgenode link; /*边表头指针*/
}vexnode; /*顶点表结点*/
vexnode ga[n];
CREATADJLIST(ga) /*建立无向图的邻接表*/
Vexnode ga[ ];
{int i,j,k;
edgenode * s;
for(i=o;i<n;i++＝ /*读入顶点信息*/
(ga[i].vertex＝getchar();
ga[i].1ink＝NULL; /*边表头指针初始化*/
}
for(k＝0;k<e;k++＝ /*建立边表*/
{scanf("％d％d",&i,&j); /*读入边(vi , vj)的顶点对序号*/
s＝malloc(sizeof(edgenode)); /*生成邻接点序号为j的表结点*s */
s-> adjvex＝j;
s- - >next：＝ga[i].Link;
ga[i].1ink＝s; /*将*s插入顶点vi的边表头部*/
s＝malloc(size0f(edgende)); /*生成邻接点序号为i的边表结点*s */
s ->adjvex＝i;
s ->next＝ga[j].1ink;
ga[j].1ink＝s; /*将*s插入顶点vj的边表头部*/
}
} /* CREATADJLIST */
P139 分别以邻接矩阵和邻接表作为图的存储结构给出具体算法，算法中g、g1和visited为全程量，visited的各分量初始值均为FALSE。
int visited[n] /*定义布尔向量visitd为全程量*/
Graph g; /*图g为全程量*/
DFS(i) /*从Vi+1出发深度优先搜索图g，g用邻接矩阵表示*/
int i;
{ int j;
printf("node：％c＼n" , g.vexs[i]); /*访问出发点vi+1 */
Visited[i]＝TRUE; /*标记vi+l已访问过*/
for (j＝0;j<n;j++) /*依次搜索vi+1的邻接点*/
if((g.arcs[i][j]＝＝1) ＆＆(! visited[j]))
DFS(j); /*若Vi+l的邻接点vj+l未曾访问过，则从vj+l出发进行深度优先搜索*/
} /*DFS*/
vexnode gl[n] /*邻接表全程量*/
DFSL(i) /*从vi+l出发深度优先搜索图g1，g1用邻接表表示*/
int i;
{ int j;
edgenode * p;
printf("node：％C\n" ,g1[i].vertex);
vistited[i]＝TRUE;
p＝g1[i].1ink; /*取vi+1的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{
if(! Vistited[p ->adjvex])
DFSL(p - >adjvex); /*从vi+1的未曾访问过的邻接点出发进行深度优先搜索*/
p＝p - >next; /*找vi+l的下一个邻接点*/
}
} /* DFSL */
P142 以邻接矩阵和邻接表作为图的存储结构，分别给出宽度优先搜索算法。
BFS(k) /＊从vk+l出发宽度优先搜索图g，g用邻接矩阵表示，visited为访问标志向量*/
int k;
{ int i,j;
SETNULL(Q); /*置空队Q */
printf("％c＼n"，g.vexs[k]); /*访问出发点vk+l*x/
visited[k]＝TRUE; /*标记vk+l已访问过*/
ENQUEUE(Q，K); /*已访问过的顶点(序号)入队列*/
While(!EMPTY(Q)) /*队非空时执行*/
{i＝DEQUEUE(Q); /*队头元素序号出队列*/
for(j＝0;j<n;j++)
if((g.arcs[i][j]＝＝1)＆＆(! visited[j]))
{printf("％c＼n" , g.vexs[j]); /*访问vi+l的未曾访问的邻接点vj+l */
visited[j]＝TRUE;
ENQUEUE(Q,j); /*访问过的顶点入队*/
}
}
} /* BFS */
BFSL(k) /*从vk+l出发宽度优先搜索图g1，g1用邻接表表示*/
int k
{ int i;
edgenode * p;
SETNULL(Q);
printf("％c＼n" , g1[k].vertex);
visited[k]＝TRUE;
ENQUEUE(Q,k);
while(! EMPTY(Q));
{ i＝DEQUEUE(Q);
p＝g1[i].1ink /*取vi+l的边表头指针*/
while(p !＝NULL) /*依次搜索vi+l的邻接点*/
{ if( ! visited[p - >adjvex]) /*访问vi+l的未访问的邻接点*/
{ printf{"％c＼n" , g1[p - >adjvex].vertex};
visited[p - >adjvex]＝TRUE;
ENQUEUE(Q,p - >adjvex); /*访问过的顶点入队*/
}
p＝p - >next; /*找vi+l的下一个邻接点*/
}
}
} /*BFSL*/
P148 在对算法Prim求精之前，先确定有关的存储结构如下：
typdef struct
{Int fromvex，endvex; /*边的起点和终点*/
float length; /*边的权值*/
} edge;
float dist[n][n]; /*连通网络的带权邻接矩阵*/
edgeT[n-1]; /*生成树*/
P149 抽象语句(1)可求精为：
for(j=1;j<n;j++) /*对n-1个蓝点构造候选紫边集*/
{T[j-1].fromvex＝1}; /*紫边的起点为红点*/
T[j-1].endvex＝j+1; /*紫边的终点为蓝点*/
T[j-1].1ength＝dist[0][j]; /*紫边长度*/
}
P149 抽象语句(3)所求的第k条最短紫边可求精为：
min＝max; /*znax大于任何边上的权值*/
for (j＝k;j<n-1;j++) /*扫描当前候选紫边集T[k]到T[n-2]，找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;m＝j; /*记录当前最短紫边的位置*/
}
P149 抽象语句(4)的求精：
e＝T[m];T[m]＝T[k];T[k]＝e， /* T[k]和T[m]交换*/
v＝T[kl.Endvex]; /* v是刚被涂红色的顶点*/
P149 抽象语句(5)可求精为：
for(j＝k+1;j<n-1;j++) /*调整候选紫边集T[k+1]到T[n-2]*/
{d＝dist[v-1][T[j].endvex-1]; /*新紫边的长度*/
if(d<T[j].1ength) /*新紫边的长度小于原最短紫边*/
{T[j].1ength＝d;
T[j].fromvex＝v; /*新紫边取代原最短紫边*/
}
}
P150 完整的算法：
PRIM() /*从第一个顶点出发构造连通网络dist的最小生成树，结果放在T中*/
{int j , k , m , v , min , max＝l0000;
float d;
edge e;
for(j=1;j<n;j++) /*构造初始候选紫边集*/
{T[j-1].formvex＝1; /*顶点1是第一个加入树中的红点*/
T[j-1].endvex＝j+1;
T[j-1].length＝dist[o][j];
}
for(k＝0;k<n-1;k++) /*求第k条边*/
{min＝max;
for(j＝k;j<n-1;j++) /*在候选紫边集中找最短紫边*/
if(T[j].1ength<min)
{min＝T[j].1ength;
m＝j;
} /*T[m]是当前最短紫边*/
}
e＝T[m];T[m]＝T[k];T[k]＝e; /*T[k]和T[m]交换后，T[k]是第k条红色树边*/
v＝T[k].endvex ; /* v是新红点*/
for(j＝k+1;j<n-1;j++) /*调整候选紫边集*/
{d＝dist[v-1][T[j].endvex-1];
if(d<T[j].1ength);
{T[j].1ength＝d;
T[j].fromvex＝v;
}
}
} /* PRIM */
P151 Kruskl算法的粗略描述：
T＝(V,φ);
While(T中所含边数<n-1)
{从E中选取当前最短边(u,v);
从E中删去边(u,v);
if((u,v)并入T之后不产生回路，将边(u,v)并入T中;
}
P153 迪杰斯特拉算法实现。算法描述如下：
#define max 32767 /*max代表一个很大的数*/
void dijkstra (float cost[][n],int v)
/*求源点v到其余顶点的最短路径及其长度*/
{ v1=v-1;
for (i=0;i<n;i++)
{ dist[i]=cost[v1][i]; /*初始化dist*/
if (dist[i]<max)
pre[i]=v;
else pre[i]=0;
}
pre[v1]=0;
for (i=0;i<n;i++)
s[i]=0; /*s数组初始化为空*/
s[v1]=1; /*将源点v归入s集合*/
for (i=0;i<n;i++)
{ min=max;
for (j=0;j<n;j++)
if (!s[j] && (dist[j]<min))
{ min=dist[j];
k=j;
} /*选择dist值最小的顶点k+1*/
s[k]=1; /*将顶点k+1归入s集合中*/
for (j=0;j<n;j++)
if (!s[j]&&(dist[j]>dist[k]+cost[k][j]))
{ dist[j]=dist[k]+cost[k][j]; /*修改 V-S集合中各顶点的dist值*/
pre[j]=k+1; /*k+1顶点是j+1顶点的前驱*/
}
} /*所有顶点均已加入到S集合中*/
for (j=0;j<n;j++) /*打印结果*/
{ printf("%f\n%d",dist[j],j+1;);
p=pre[j];
while (p!=0)
{ printf("%d",p);
p=pre[p-1];
}
}
}
P155 弗洛伊德算法可以描述为：
A(0)[i][j]=cost[i][j]; //cost为图的邻接矩阵
A(k)[i][j]=min{A(k-1) [i][j],A(k-1) [i][k]+A(k-1) [k][j]}
其中 k=1,2,…,n
P155 弗洛伊德算法实现。算法描述如下：
int path[n][n]; /*路径矩阵*/
void floyd (float A[][n],cost[][n])
{ for (i=0;i<n;i++) /*设置A和path的初值*/
for (j=0;j<n;j++)
{ if (cost[i][j]<max)
path[i][j]=j;
else { path[i][j]=0;
A[i][j]=cost[i][j];
}
}
for (k=0;k<n;k++)
/*做n次迭代，每次均试图将顶点k扩充到当前求得的从i到j的最短路径上*/
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (A[i][j]>(A[i][k]+A[k]