清华大学《数据结构与算法》(6)

3、设计建立有向图正邻接矩阵的函数（数据输入格式自定）。 Typedef struct

{ int data[ maxsize][maxsize]; int dem,e; }sqgraph;

sqgraph crt (sqgraph g)

{ scanf(n,e);g.dem=n; for (i=1;i<=n;i++) for (j=1;j<=n;j++) g.data[i][j]=0; for (i=1;i<=e;i++) { scanf(beg,end); g.data[beg][end]=1; } return g; }

4、设计函数，将不带表头结点的单链表清除。 lklist clear ( lklist head) { while (head)

{ p=head ;

head=head->next ; free(p); }

return head;

}

5、设计递归函数，求一棵非空的二叉树的深度。 int depth (bitreptr root)

{ if (!root) return 0;

else { dl=depth(root->lc);

dr=depth(root->rc); return 1+(dl>dr?dl:dr); } }

6、设线性表A=(a1,a2,a3,?,an)以带头结点的单链表作为存储结构。编写一个函数，删去A中序号为奇数的结点。

7、试编写一个算法，能由大到小遍历一棵二叉排序树。

void ShowTree ( TreeNode* current ) {

if (current == NULL) {

return; }

ShowTree(current->right);

cout << endl << current->data; ShowTree(current->left); }

8、对于二叉树的链接实现,完成非递归的中序遍历过程。

void InOrder(BiTree bt)

{BiTree s[],p=bt; //s是元素为二叉树结点指针的栈，容量足够大

int top=0;

while(p || top>0)

{while(p) {s[++top]=p; bt=p->lchild;} //中序遍历左子树 if(top>0){p=s[top--]; printf(p->data); p=p->rchild;} //退栈，访问，转右子树

} }

9、利用直接插入排序的方法对一组记录按关键字从小到大的顺序排序。

10、给出一棵表示表达式的二叉树，其中运算符和运算对象都用一个字符表示，求该表达式的值。设二叉树用二叉链表表示，表达式中仅包含二元运算，函数operate(a, b, op)可求任何一种二元运算的值，其中参数op表示运算符，a和b分别表示左右两个运算对象。算法中允许直接引用函数operate (函数operate 不必定义)，如果需要还允许引用栈和队列的基本操作。

11、编写算法，将一单链表逆转。要求逆转在原链表上进行，不允许重新构造一个链表（可以申明临时变量、指针）。

该链表带头节点、头节点和数据节点的结构定义如下 typedef struct LNode {

ElemType data; Struct LNode* next; }List, LNode;

函数定义：void invert(List & L)

12、编写算法计算给定二叉树中叶结点的个数。 其中树节点定义如下 typedef struct BiTNode{

DataType data;

Struct BiTNode *LChild, * RChild;

}BiTNode, *BiTree;

函数定义：CountLeaf (BiTree T, int & LeafNum) void CountLeaf (BiTree T, int & LeafNum) {

if(T) {

if(!T->lchild&&!T->rchild)

LeafNum++; else

{

CountLeaf(T->lchild, LeafNum); CountLeaf(T->rchild, LeafNum);

} }

}

13、写出二叉树前根遍历的递归算法

已知二叉树结点定义为： struct node{

elemtp data;

struct node *lc,*rc; );

Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点); void preorder(bitreptr P) //P指向树根节点

void preorder(bitreptr P) {

If(P!=0) {

printf(P->data); preorder(P->lc); preorder(P->rc);

}

}

14、在邻接矩阵存储结构上实现图的基本操作： InsertVex(G,v)//插入顶点

Status Insert_Vex(MGraph &G, char v)//在邻接矩阵表示的图G上插入顶点v {

if(G.vexnum+1)>MAX_VERTEX_NUM return INFEASIBLE; G.vexs[++G.vexnum]=v;

return OK; }//Insert_Vex

15、已知某哈希表的装载因子小于1，哈希函数H（key）为关键字（标识符）的第一个字母在字母表中的序号，处理冲突的方法为线性探测开放定址法，请编写一个按第一个字母的顺序输出哈希表中所有关键字的算法。

void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,

void Print_Hash(HashTable H)//按第一个字母顺序输出Hash表中的所有关键字,其中处理冲突采用线性探测开放定址法

{

for(i=1;i<=26;i++)

for(j=i;H.elem[j].key;j=(j+1)%hashsize[sizeindex]) //线性探测 if(H(H.elem[j].key)==i) printf(\}//Print_Hash

int H(char *s)//求Hash函数 {

if(s) return s[0]-96; //求关键字第一个字母的字母序号(小写) else return 0; }//H

16、写出二叉树后根遍历的递归算法 已知二叉树结点定义为： struct node{

elemtp data;

struct node *lc,*rc; );

Typedef struct node * bitreptr(指向根),*tpointer(指向一般结点);

void aftorder(bitreptr P) {

If(P!=0) {

aftorder(P->lc); aftorder(P->rc);

printf(P->data); }

}

17、在邻接矩阵存储结构上实现图的基本操作：DeleteArc(G,v.w)//删除边（v,w）

Status Delete_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上删除边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(G.arcs[i][j].adj) {

G.arcs[i][j].adj=0; G.arcnum--; } return OK; }//Delete_Arc

18、编写一个函数或过程判定两棵二叉树是否相似，所谓两棵二叉树s和t相似，即是要么它们都 为空或都只有一个结点，要么它们的左右子树都相似。

[题目分析]两棵空二叉树或仅有根结点的二叉树相似；对非空二叉树，可判左右子树是否相似，采用递归算法。

int Similar(BiTree p,q) //判断二叉树p和q是否相似 {if(p==null && q==null) return (1);

else if(!p && q || p && !q) return (0);

else return(Similar(p->lchild,q->lchild) && Similar(p->rchild,q->rchild)) }//结束Similar

19、在邻接矩阵存储结构上实现图的基本操作：InsertArc(G,v,w)//插入边（v,w）

Status Insert_Arc(MGraph &G,char v,char w)//在邻接矩阵表示的图G上插入边(v,w) {

if((i=LocateVex(G,v))<0) return ERROR; if((j=LocateVex(G,w))<0) return ERROR; if(i==j) return ERROR; if(!G.arcs[i][j].adj) {

G.arcs[i][j].adj=1; G.arcnum++; }

return OK; }//Insert_Arc

20、假设有一个1000*1000的稀疏矩阵，其中1%的元素为非零元素，现要求哈希表作存储 …… 此处隐藏：1653字，全部文档内容请下载后查看。喜欢就下载吧 ……