数据结构编程题.doc

《数据结构编程题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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 (Lin

2、kList *head){   LinkList *p,*s,*q;    p=head->next;  //p指向待插入的结点，初始时指向第一个结点    while(p!=NULL)    { s=head;  // s指向q结点的前趋结点q=head->prior;  //q指向由prior域构成的链表中待比较的结点while((q!=NULL) && (p->data>q->data))  //查找插入结点p的合适的插入位置{ s=q;q=q->prior;}s->prior=p;p->prior=q;  //结点p插入到结点s和

3、结点q之间p=p->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->data<=min)){ q=p;p=p->next;}while((p!=NULL) && (p->data

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

5、

6、 (p->data>=max)){ q=p;p=p->next;}else{  q->next=p->next;free(p);p=q->next

7、;}}Ø7.编写一个算法，求出邻接矩阵表示的无向图中序号为numb的顶点的度数。int degree1(Graph & ga, int numb){     int j,d=0;   for(j=0; j

8、=0;ivexnum;for(i = 1; i<=G->vexnum; i

9、++)                             for(j = 1; j<=G->vexnum; j++)g.edges[i][j] = 0;for(i = 1; i<=G->vexnum; i++){m = G->vexpex[i].firstarc;while(m){g.edges[i][m->adjvex] = 1;m = m->nextarc;}}}Ø4.编写一个双向起泡的排序算法，即相邻两趟向相反方向起泡。 void BubbleSort(SeqList R,int n){for(int i=1;i<=n;i++

10、){if(i%2==1)        {for(int j=n-i+1;j>i;j--){if(R[j].key