数据结构编程题.pdf

1、编程题： 10.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data， next 和 prior，结点 LinkList 类型定义如下： 现在所有结点已经由next 域连接起来， 试编一个算法， 利用 prior 域(此域初值为NULL) 把所有结点按照其值从小到大的顺序链接起来。 typedef struct node int data; struct node *next,*prior; LinkList; /采用插入排序法，设p 指向待插入的结点，用q 搜索已由prior 域链接的有序表找到合 适位置将p 结点链入 void insert (LinkList *he

2、ad) LinkList *p,*s,*q; p=head-next; /p 指向待插入的结点，初始时指向第一个结点 while(p!=NULL) s=head; / s指向 q 结点的前趋结点 q=head-prior; /q 指向由 prior 域构成的链表中待比较的结点 while(q!=NULL) q=q-prior; s-prior=p; p-prior=q; / 结点 p 插入到结点s 和结点 q 之间 p=p-next; 9.已知线性表的元素按递增顺序排列 ，并以带头结点的单链表作为存储结构。试编写一 个删除表中所有值大于min 且小于 max 的元素（若表中存在这样的元素）的算

3、法。 delete(LinkList *head, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head-next; while(p!=NULL) while(p!=NULL) q-next=p; 8.已知线性表的元素是无序的 ，且以带头结点的单链表作为存储结构。设计一个删除表 中所有值小于max 但大于 min 的元素的算法。 delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=NULL) i

4、f(p-datadata=max) q=p; p=p-next; else q-next=p-next; free(p); p=q-next; 7.编写一个算法，求出邻接矩阵表示的无向图 中序号为numb 的顶点的度数。 int degree1(Graph for(j=0; jga.vexnum; j+) if (ga.costnumbj!=0 return (d); 6.编写一个算法，求出邻接矩阵表示的有向图 中序号为numb 的顶点的度数 int degreel(Graph for(i=0;ivexnum; for(i = 1; ivexnum; i+) for(j = 1; jvexnu

5、m; j+) g.edgesij = 0; for(i = 1; ivexnum; i+) m = G-vexpexi.firstarc; while(m) g.edgesim-adjvex = 1; m = m-nextarc; 4.编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。 void BubbleSort(SeqList R,int n) for(int i=1;ii;j-) if(Rj.keyRj-1.key) R0.key = Rj.key; Rj.key = Rj-1.key; Rj-1.key = R0.key; else for(int j=i;jRj+1.key)

6、R0.key = Rj.key; Rj.key = Rj+1.key; Rj+1.key = R0.key; 3.试以单链表为存储结构实现简单选择排序的算法 void LinkList_Select_Sort(LinkList 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

7、-next; q-next=p-next-next; p-next-next=t; /交换 q 和 s-next 两个结点 /for /LinkList_Select_Sort 2.有一种简单的排序算法，叫做计数排序（count sorting） 。这种排序算法对一个待排 序的表 （用数组表示，表中所有待排序的关键字互不相同）进行排序，并将排序结构存 放到另一个新的表中。计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计 表中有多少个记录的关键字比该记录的关键字小。假设对某一个记录，统计出计数值为 C，那么，这个记录在新的有序表中的合适的存放位置即为C。实现计数排序的算法。 Int a300,b300; For(int i=0;in;i+) Num=0; For(int j=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);