s→next=H[i]; H[i]=s; }// else
}//else
}//F2
void Delete_HS(HashTable &H, KeyType key){
//哈希表删除，用链地址法解决冲突
i=H(key); //获得哈希地址 if(H[i]= =Null) exit(1);
p=H[i];q=p; // p为工作指针，q为p前趋 while(p&&p→data!=key) {//查找
q=p; p=p→next; }//while
if(!p) exit(1);
if(q==H[i]){ //key为第一结点 H[i]p→next; free(p); }// if else{
q→next=p→next;
free(p);
}//else }//Delete_HS
12．设关键字是一个由26个小写字母组成的字符串，哈希表的长度为26。试编写算法，建立哈希表，并以第一个
字符的字典顺序输出哈希表中的所有关键字。设哈希函数为hast(x)=x中的第一个字符在字典顺序中的序号，采用线性探测再散列法来解决冲突。（假设函数f(x)能够计算出x中的第一个字符在字典顺序中的序号）。 void create_Hs(RedType &H,key Type key){
i=Hash(key);//创建哈希表 if(H(i)==Null)//插入 H(i)=key;
else{ //解决冲突，再插入
j=(i+1)%m; //m为表长 while (j!=i){
if(H[j]==Null)
H[j]=key; else j=(j+1)%m; }//while
}//create_Hs
void print_Hs(RedType H){
//输出哈希表
for (i=0;i<26;i++){
j=1;
while(H[j])!=Null{
if(f(H[j])==i)
printf(H[j]); j=(j+1)%m; }//while }//for }//print_Hs
13
五、算法设计题
1. 已知f为单链表的表头指针，链表中存储的都是整型数据，试设计算法用直接插入排序使链表非递减有序。
void InsertSort_L(Linklist &La){
//用直接插入排序使链表递增有序 if(La→next){ //链表不空
p=La→next→next; La→next→next→Null; while(p!=Null){
r=p→next;//暂存p的后继。 q=La;
while(q→next&&q→next→data q=q→next;//查找插入位置。 p→next=q→next;//插入 q→next=p; p=r; }//while }//if }//InsertSort_L 2. 设计算法，判断一个以邻接表为存储结构的无向图G是否连通有，若连通，则返回1，否则，返回0。 int connect(ALGraph G){ //判断以邻接表为存储结构的无向图是否连通 flag=1; for(i=0;i if(visited[i]=0){ flag==0; breek; } return flag; }// connect void dfs(ALGraph G,int visited[],int v){ //采用深度优先遍历的算法思想 visited[v]=1; p=G.ver[v].firstarc; while(p){ if(visited[p→adjvex]==0) dfs(G,visited,p→adjvex); p=p→next; }//whike }//dfs 3．设计算法SelectSort的功能是：用单链表实现简单选择排序（设L是带头结点的单链表的头指针，并为已知的LinkList类型）。 void Selectsort(LinkList &L){ //用单链表实现简单选择排序 p=L－>next; //初始化，p为工作指针 while(p){//q为插入指针，min为当前最小指针 min=p;q=p－>next; while(q){ //一趟选择排序 if(q－>data 14 }//while(q) if(min){//交换 temp=p－>data; p－>data=min－>data; min－>data=temp; }//if p=p－>next; }//while(p) }//Selectsort 4．已知深度为h的二叉树采用顺序存储结构存放在数组B[1..2h-1]中，设计一个递归算法，产生该二叉树的二叉链表结构。 void CreateTree(int B[2h],int j,BiTree t){ //创建t树的二叉链表结构，j为数组下标，初值为1 t=( BiTree ) malloc( sizeof(BiTNode)); t－>data=B[j]; //创建根结点 if(2*j>2h) t－>Lchild=null;//无左子树 else //递归创建左子树 t－>Lchild=CreateTree(B,2*j,t－>Lchild)； if(2*j+1>2h) t－>Rchild=null;//无右子树 else //递归创建右子树 t－>Rchild=CreateTree(B,2*j+1,t－>Rchild)； }// CreateTree 5．设用输入广义表表示的字符串来创建二叉链表结构的二叉树，具体规定如下：广义表的表名作为树的根结点； 每个结点的左子树和右子树用逗号分割，若仅有右子树，则逗号不能省略；以特殊符号‘$’表示广义表的结尾。例如：若输入的字符串为A(B(C),D(E(,F),G))。实现用上述方法创建二叉树的算法。 void CreatTree(BiTree &T,char *str){ //根据广义表的嵌套括号表示法，生成二叉链表树 BiTree stack[maxsize],p; int k,j=0,top=-1; //j为str指针，top为栈顶指针 T=null; //初始化栈根指针 Char ch=str[j]; while(ch!=’$’){ switch(ch){ case ‘(’: top ++; stack[top]=p; //入栈 k=1; break; // k=1,为左孩子 case ‘)’: top--;break; //出栈 case ‘,’: k=2; break; //k=2,为右孩子 default: p=(BiTree)malloc(sizeof(BTNode)); p→data=ch; p→lchild=p→rchild=Null; if(T==Null) T=p; //创建根结点 else switch(k){ case ‘1’: stack[top]→lchild=p; break; case ‘2’: stack[top]→rchild=p; break; }//switch }//swith j++; ch=str[j]; 15 }// while }//creatTree 6．设计算法，求以邻接表为存储结构的非连通无向图G的连通分量个数。 int count_graph(ALGraph G){ // 求以邻接表为存储结构的非连通无向图G的连通分量个数 count=0; for(i=0;i count++; for(i=0;i visited[i]=0; dfs(G,visited,0); return count; } void dfs(ALGraph G,int visited[],int v){ //采用深度优先遍历的算法思想 visited[v]=1; p=G.ver[v].firstarc; while(p){ if(visited[p→adjvex]==0) dfs(G,visited,p→adjvex); p=p→next; }//whike }//dfs 7．设有一个正整数序列组成的非递减有序单链表，算法功能：在单链表中将比正整数x小的数按递减次序排列。 void F7 (Linklist L;int,x){ p= L→next; q=p; //p为工作指针 pre=L; L→next=NULL; .//q指最小元素 while(P&&P→data r=p→next; p→next=L→next; L→next=p; p=r; //置逆 }//while q→next=p; pre=q; //重新链接 }//F7 8．Internet的域名系统是一个典型的层次结构，可用树形结构表示。每一个域名服务器提供的区域信息恰好是以 该结点为根的子树中的全部的IP地址。设计算法以孩子-兄弟链表作为树的存储结构,实现搜索所有www域名的IP地址。 void Outpath(CSTree T,Stack &S){//搜索IP地址 while(T){ Push(S,T－>data) if(!T－>firstchild && T－>data==”www”) visitstack(S);//输出一条路径 else Outpath(T－>firstchild ,&S)//递归遍历左子树 Pop(S,e); T=T－>nextsibiling; // 遍历右子树 }//while }//Outpath 9．设计算法实现以逆邻接表为存储结构的有向图的拓扑排序（要求给出逆邻接表的存储结构定义）。 16