《数据结构编程题.doc》由会员分享，可在线阅读，更多相关《数据结构编程题.doc（8页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编程题： 10.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data，next与prior，结点LinkList类型定义如下： 现在所有结点已经由next域连接起来，试编一个算法，利用prior域(此域初值为NULL)把所有结点按照其值从小到大的顺序链接起来。 typedefstructnodeintdata;structnode*next,*prior;LinkList;/采用插入排序法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到适宜位置将p结点链入voidinsert(LinkList*head)LinkList*p,*s,*q; p=head-n
2、ext;/p指向待插入的结点，初始时指向第一个结点 while(p!=NULL)s=head;/s指向q结点的前趋结点q=head-prior;/q指向由prior域构成的链表中待比拟的结点while(q!=NULL)&(p-dataq-data)/查找插入结点p的适宜的插入位置s=q;q=q-prior;s-prior=p;p-prior=q;/结点p插入到结点s与结点q之间p=p-next; 9.线性表的元素按递增顺序排列，并以带头结点的单链表作为存储构造。试编写一个删除表中所有值大于min且小于max的元素假设表中存在这样的元素的算法。delete(LinkList*head,intma
3、x,intmin)linklist*p,*q;if(head!=NULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;while(p!=NULL)&(p-datanext;q-next=p; 8.线性表的元素是无序的，且以带头结点的单链表作为存储构造。设计一个删除表中所有值小于max但大于min的元素的算法。 delete(LinkList*head,intmax,intmin)LinkList*p,*q;q=head;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;elseq-n
4、ext=p-next;free(p);p=q-next; 7.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 intdegree1(Graph&ga,intnumb) intj,d=0; for(j=0;jga.vexnum;j+) if(ga.costnumbj!=0&ga.costnumbj!=MAXINT) d+; return(d);6. 编写一个算法，求出邻接矩阵表示的有向图中序号为numb的顶点的度数int degreel(Graph &ga,int numb)int i,j,num=0;for(i=0;ivexnum;for(i=1;ivexnum;i+)f
5、or(j=1;jvexnum;j+)g.edgesij=0;for(i=1;ivexnum;i+)m=G-vexpexi.firstarc;while(m)g.edgesim-adjvex=1;m=m-nextarc; 4.编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。 voidBubbleSort(SeqListR,intn)for(inti=1;ii;j-)if(Rj.keyRj-1.key)R0.key=Rj.key;Rj.key=Rj-1.key;Rj-1.key=R0.key;elsefor(intj=i;jRj+1.key)R0.key=Rj.key;Rj.key=Rj+1
6、.key;Rj+1.key=R0.key; 3.试以单链表为存储构造实现简单项选择择排序的算法void LinkList_Select_Sort(LinkList &L) /单链表上的简单项选择择排序算法 for (p=L;p-next-next;p=p-next) q=p-next; x=q-data; for (r=q,s=q;r-next;r=r-next) /在q后面寻找元素值最小的结点 if (r-next-datanext-data; s=r; if (s!=q) /找到了值比q-data更小的最小结点s-next p-next=s-next; s-next=q; t=q-next
7、; q-next=p-next-next; p-next-next=t; /交换q与s-next两个结点 /for /LinkList_Select_Sort 2.有一种简单的排序算法，叫做计数排序count sorting。这种排序算法对一个待排序的表用数组表示，表中所有待排序的关键字互不一样进展排序，并将排序构造存放到另一个新的表中。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为C，那么，这个记录在新的有序表中的适宜的存放位置即为C。实现计数排序的算法。 Inta300,b300; For(inti=0;in;i+)Num=0;For(intj=0;jn;j+) If(ajdata; while(p!=NULL)/找到数据域值最小的结点 If(data1data) p1=p; data1=p-data; p=p-next; P=head;While(pnext!=p1)p=p-next;/找到据域值最小的结点前的结点 p-next=p-next-next;/删除数据域值最小的结点。free(p1);第 8 页