计算机软件基础作业

1、软件技术基础结课大作业姓名 王家毅 学号 120611325 日期 1利用减半递推技术，写出求长度为n的数组中最大元素的递归算法#include using namespace std;int maxa(int a, int m, int n) int d,d1,d2; if ( m=n ) return( am-1 ); else d1 = maxa( a,m,(m+n)/2 ); /求数组中前半部分的最大值 d2 = maxa( a,(m+n)/2+1,n ); /求数组中后半部分的最大值 if (d1d2) d=d1; else d=d2; return(d);2编写用回溯法求解n皇后的

2、算法#include #include bool place(int k, int *X)int i;i=1;while(i0)Xk=Xk+1; /不断的在解空间里从小到大的试探while(Xk=n)&(!place(k, X)Xk=Xk+1;/不符合条件的马上再取解空间的下一个值来试探。if(Xk=n)/找到了一个位置，而且是合法的if(k=n)/是不是最后一个皇后，若是则得出一个完整解for(int i=1;i=n;i+)coutXi ;cout du + w(u,v) dv := du + w(u,v) previousv := u /总共合起来是O（E+n2）;所有步骤合起来就是O(n

3、)+O(1)+O(n)+O(E+n2),即O(n2)。4将单链表看做二叉树，编写递归程序打印单链表#include#include#include#includetypedef struct nodechar 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) / 检查是否存在相同结点

4、result=(int)(r-c)-(int)(ch);if(!result)r-count+=1;return r;elsep=r;r=resultright: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(result0) p-left=r;else p-right=r;return r;leaflink(bnode *root)if(!root)retu

5、rn;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);doif(!root)root=creatree(root,*s);else creatree(root,*

6、s);s+=1;while(*s);leaflink(root); / 将叶结点链成链表while(k)printf(%c,k-c);k=k-right; / 输出该链表5编写二叉树的层次遍历算法main() BitTree t; printf(Input data to create bittree and ); printf( SHUJU,END); printf( will make null tree.n); /*输入根结点 */ CreateBitTree(&t);/*初始化二叉树*/printf(Layer order travel the tree:n); LayerTravel

7、BitTree(t); /*层次遍历二叉树*/ /*层次遍历二叉树*/T = (BitTree )malloc(sizeof(BTnode); printf(Enter Data:); fflush(stdin); scanf(SHUJU,&inputdata); /*输入数据*/ if ( inputdata = END) *T = NULL; return FALSE; else (*T)-data = inputdata; /*将输入的数据存入结点*/ printf(Create left sub treelchild); printf(Create right sub treerchi

8、ld); return TRUE; /*递归循环输入右子树*/ /*递归循环输入左子树*/while ( DeQueue(&tq,&res) = TRUE) if (res) VisitData(res-data); EnQueue(&tq,res-lchild); EnQueue(&tq,res-rchild); /*当队头元素不空时执行 while 循环*/int EnQueue(queue *q, QueueElemtype c) /*将元素 c 插入队尾*/ q-rear+; /*尾指针加 1*/ /*若尾指针超出队列长度则提示错误*/ if (q-rear = QUEUESIZE)

9、printf(Queue overflow!n); exit(0); q-dataq-rear = c; return 1; 4.10 队头元素出队 Statu DeQueue(queue *q, QueueElemtype *ret) 返回其值*/ if (q-front = q-rear) return FALSE; q-front+; *ret = /*头指针加 1*/ /*若队列为空，则返回错误提示*/ /*队头元素出队并用 ret q-dataq-front; return TRUE;6自底向上实现归并排序算法/*函数名称：Merge*参数说明：pDataArray 无序数组* in

10、t* pTempArray 临时储存合并后的序列* bIndex 需要合并的序列1的起始位置* mIndex 需要合并的序列1的结束位置 并且作为序列2的起始位置* eIndex 需要合并的序列2的结束位置*说明： 将数组中连续的两个子序列合并为一个有序序列*/Void Merge(int* pDataArray, int* pTempArray, int bIndex, int mIndex, int eIndex)Int mlength = eIndex bIndex; /合并后的序列长度Int I =; /记录合并后序列插入数据的偏移Int j = bIndex; /记录子序列1插入数据

11、偏移Int k = mindex； /记录子序列2插入数据偏移While( j mIndex & k eIndex) If (pDataArrayj = pDataArrayk) pTempArrayi+ = pDataArrayj; j+; else pTempArrayi+ = pDataArrayk; k+; If (j = mIndex) /说明序列1已经插入完毕 while (k eIndex) pTempArrayi+ = pDataArrayk+; else /说明序列2已经插入完毕 while (j mIndex) pTempArrayi+ = pDataArrayj+; fo

12、r (I =; i mlength; i+) /将合并后序列重新放入pDataArray pDataArraybIndex + i = pTempArrayi;/*函数名称：BottomUpMergeSort*参数说明：pDataArray 无序数组；* iDataNum为无序数据个数*说明： 自底向上的归并排序*/Void BottomUpMergeSort(int* pDataArray, int iDataNum); Int* pTempArray = (int*)malloc(sizeof(int)* iDataNum); /临时存放合并后的序列Int length = 1; /初始有

13、序子序列长度为1While (length iDataNum) Int i = ; For (i + 2*length iDataNum; I += 2*length) Merge(pDataArray,pTempArray, I , I + length, I + 2*length); If (I + length iDataNum) Merge(pDataArray, pTempArray, I , I + length, iDataNum); Length *= 2; /有序子序列长度*2Free(pTempArray); 7实现堆排序算法#include#include#include

14、#defineMAX50/数据输入子函数voidInputData(intlist)intI = 1;printf(请输入要排序的数据（以-1结束）:n);/用-1表示数据输入结束，-1不包括在排序数据中 scanf(%d,&listi);while(listi! = -1)i+;scanf(%d,&listi);list0=i-1;/list0用来放list数组的长度voidpanduan(intlist,intn)intI = 1;for(I = 1;I n; i+)if(isdigit(listi) = 0) printf(序列为非完全数字序列，无法排序。n); exit(0); /数据

15、输出子函数voidOutputData(intlist,intn) inti=1; printf(排序后的数列是:n);for(i=1;i=n;i+) if(i%4=0) printf(n); printf(%dt,listi); printf(n);/创建大顶堆子函数voidHeapAdjust(intlist,ints,intm)intj,rc;rc=lists;for(j=2*s;jm;j*=2)if(j=m&(listj=listj)break; lists=listj; s=j;lists=rc;/堆排序子函数voidHeapSort(intlist,intn)inti,t;for(

16、i=n/2;i0;i-) HeapAdjust(list,i,n); for(i=n;i1;i-)t=list1;list1=listi;listi=t; HeapAdjust(list,1,i-1); /界面子函数voidUI() printf(*内部堆排序程序*n);printf(程序操作如下n);printf(*n);/主函数voidmain() UI();intn;intlistMAX;InputData(list);n=list0;panduan(list,n); HeapSort(list,n);OutputData(list,n);8实现迪杰斯特拉最短路径算法#includeus

17、ingnamespacestd;constintmaxnum=100;constintmaxint=999999;voidDijkstra(intn,intv,int*dist,int*prev,intcmaxnummaxnum)boolsmaxnum;/判断是否已存入该点到S集合中for(inti=1;i=n;+i)disti=cvi;si=0;/初始都未用过该点if(disti=maxint)previ=0;elseprevi=v;distv=0;sv=1;/依次将未放入S集合的结点中，取dist最小值的结点，放入结合S中/一旦S包含了所有V中顶点，dist就记录了从源点到所有其他顶点之间

18、的最短路径长度for(inti=2;i=n;+i)inttmp=maxint;intu=v;/找出当前未使用的点j的distj最小值for(intj=1;j=n;+j)if(!sj)&distjtmp)u=j;/u保存当前邻接点中距离最小的点的号码tmp=distj;su=1;/表示u点已存入S集合中/更新distfor(intj=1;j=n;+j)if(!sj)&cujmaxint)intnewdist=distu+cuj;if(newdist=1;-i)if(i!=1)coutquei;elsecoutquein;/输入路径数cinline;intp,q,len;/输入p,q两点及其路径长度/初始化c为maxintfor(inti=1;i=n;+i)for(intj=