《数据结构编程题 (1).docx》由会员分享，可在线阅读，更多相关《数据结构编程题 (1).docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、编程题： 10.假设有一个带表头结点的链表，表头指针为head,每个结点含三个域：data, next 和prior,结点LinkList类型定义如下：typedef struct nodenext; /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-
2、next; 9.已知线性表的元素按递增顺序排列，并以带头结点的单链表作为存储结构。试编写一个删除表中所有值大于min且小于max的元素(若表中存在这样的元素)的算法。delete(LinkList *head, int max, int min) (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
3、的元素的算法。delete(LinkList *head, int max, int min)(LinkList *p,*q;q=head;p=head-next;while (p!=NULL)if(p-datadata=max)(q=p；p=p-next;)else(q-next=p-next;free(p);p=q-next; 7.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。 int degree 1 (Graph & ga, int numb) (int j,d=O;for(j=0; jga.vexnum; j+)if (ga.costnumbj! =0 & ga
4、.costnumb j! =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+)for(j = 1; jvexnum; j+) g.edgesi|j = 0;for(i = 1; ivexnum; i+)(m = G-vexpexi .firstarc;while(m)(g.edgesi m-adj vex = 1;m = m-nextarc;)4,编写一个双向起泡
5、的排序算法，即相邻两趟向相反方向起泡。 void BubbleSort(SeqList R,int n)(for(int i=l;ii;j-)(if(Rj.keyRj+l.key)RO.key = Rj.key;Rj.key = Rj+l.key;Rj+l.key = RO.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)
6、在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; q-next=p-next-next; p-next-next=t; 交换q和s-next两个结点/for /LinkList_Select_Sort2.有一种简单的排序算法，叫做计数排序(count sorting)o这种排序算法对一个待排 序的表(用数组表示，表中所有待排序的关键字互不相同)进行排序，并将排序结构存 放到另一个新的表中。计数排序算法针对表中的每个记录
7、，扫描待排序的表一趟，统计 表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为 C,那么，这个记录在新的有序表中的合适的存放位置即为C。实现计数排序的算法。Int a300,b300;For(int i=0;in;i+)Num=O;For(int j=O;jn;j+)If(a|jdata;while(p!=NULL)/找到数据域值最小的结点(If(dataldata)(P1=P；datal=p-data;)p=p-next;)P 二 head;While(pnext!=pl)p=p-next;找到据域值最小的结点前的结点p-next=p-next-next;/删除数据域值最小的结点。free(pl);