數據結構與演算法分析c版答案

A. 數據結構與演算法題需要回答

《數據結構與演算法》模擬題
一、填空題：（共15分）（每空一分）
按照排序時，存放數據的設備，排序可分為<1> 排序和<2> 排序。內部排序和外部排序
圖的常用的兩種存儲結構是<3> 和<4> 。鄰接矩陣和鄰接表
數據結構中的三種基本的結構形式是<5> 線性結構 和<6> 樹型結構 、圖型結構<7> 。
一個高度為6的二元樹，最多有<8> 63 個結點。
線性查找的時間復雜度為：<9> O(n^2) ，折半查找的時間復雜度為：<10> O(nlogn) 、堆分類的時間復雜度為：<11> O(nlogn) 。
在採用散列法進行查找時，為了減少沖突的機會，散列函數必須具有較好的隨機性，在我們介紹的幾種散列函數構造法中，隨機性最好的是<12> 隨機數 法、最簡單的構造方法是除留余數法<13> 。
線性表的三種存儲結構是：數組、<14> 鏈表 、<15> 靜態鏈表 。
二、回答下列問題：（共30分）
現有如右圖的樹，回答如下問題：看不見圖
根結點有：
葉結點有：
具有最大度的結點：
結點的祖先是：
結點的後代是：
棧存放在數組A[m]中，棧底位置是m-1。試問：
棧空的條件是什麼？top=m-1
棧滿的條件是什麼？top=-1
數據結構和抽象數據型的區別與聯系：
數據結構（data structure)—是相互之間存在一種或多種特定關系的數據元素的集合。數據元素相互之間的關系稱為結構。
抽象數據類型（ADT）：是指一個數學模型（數據結構）以及定義在該模型（數據結構）上的一組操作。

B. 數據結構（c語言版）題目求答案

3.28
void InitCiQueue(CiQueue&Q)//初始化循環鏈表表示的隊列Q
{
Q=(CiLNode*)malloc(sizeof(CiLNode));
Q->next=Q;
}//InitCiQueue
voidEnCiQueue(CiQueue&Q,int x)//把元素x插入循環列表表示的隊列Q,Q指向隊尾元素，Q->next指向頭結點，Q->next->next指向隊尾元素
{
p=(CiLNode*)malloc(sizeof(CiLNode));
p->data=x;
p->next=Q->next;//直接把p加在Q的後面
Q->next=p;
Q=p;//修改尾指針
}
Status DeCiQueue(CiQueue&Q,int x)//從循環鏈表表示的隊列Q頭部刪除元素x
{
if(Q==Q->next)return INFEASIBLE;//隊列已空
p=Q->next->next;
x=p->data;
Q->next->next=p->next;
free(p);
rturn OK;
}//DeCiqueue

3.31

int Palindrome_Test()
{
InitStack(S);InitQueue(Q);
while((c=getchar())!='@')
{
Push(S,c);EnQueue(Q,c);
}
while(!StackEmpty(S))
{
pop(S,a);DeQueue(Q,b);
if(a!=b)return ERROR;
}
return OK;
}

C. 數據結構與演算法分析 C++

你說的是中序線索二叉樹的插入和刪除

#include<stdio.h>
#include"malloc.h"
#include"windows.h"
#definemaxsize20//規定樹中結點的最大數目
typedefstructnode{//定義數據結構
intltag,rtag;//表示child域指示該結點是否孩子
chardata;//記錄結點的數據
structnode*lchild,*rchild;//記錄左右孩子的指針
}Bithptr;

Bithptr*Q[maxsize];//建隊，保存已輸入的結點的地址
Bithptr*CreatTree(){//建樹函數，返回根指針
charch;
intfront,rear;
Bithptr*T,*s;
T=NULL;
front=1;rear=0;//置空二叉樹
printf("建立一棵二叉樹，請輸入結點信息：
");
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();//輸入第一個字元
while(ch!='#')//判斷是否為結束字元
{
s=NULL;
if(ch!='@')//判斷是否為虛結點
{
s=(Bithptr*)malloc(sizeof(Bithptr));
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
s->rtag=0;
s->ltag=0;
}
rear++;
Q[rear]=s;//將結點地址加入隊列中
if(rear==1)T=s;//輸入為第一個結點為根結點
else
{
if(s!=NULL&&Q[front]!=NULL)//孩子和雙親結點均不是虛結點
if(rear%2==0)
Q[front]->lchild=s;
elseQ[front]->rchild=s;
if(rear%2==1)front++;
}getchar()();
printf("請輸入新的結點信息，@為空結點，#為結束標志：");
ch=getchar()();
}
returnT;
}
voidInorder(Bithptr*T)//中序遍歷
{
if(T)
{
if(T->ltag!=1)Inorder(T->lchild);
printf("→%c",T->data);
if(T->rtag!=1)Inorder(T->rchild);
}
}

Bithptr*pre=NULL;
voidPreThread(Bithptr*root)//中序線索化演算法，函數實現
{
Bithptr*p;
p=root;
if(p){
PreThread(p->lchild);//線索化左子樹
if(pre&&pre->rtag==1)pre->rchild=p;//前驅結點後繼線索化
if(p->lchild==NULL)
{
p->ltag=1;
p->lchild=pre;
}
if(p->rchild==NULL)//後繼結點前驅線索化
p->rtag=1;
pre=p;
PreThread(p->rchild);
}
}
voidPrintIndex(Bithptr*t)//輸出線索
{
Bithptr*f;
f=t;
if(f)
{
if(f->ltag==1&&f->lchild==NULL&&f->rtag==1)printf("【%c】",f->data);//如果是第一個結點
if(f->ltag==1&&f->lchild!=NULL)printf("%c→【%c】",f->lchild->data,f->data);//如果此結點有前驅就輸出前驅和此結點
if(f->ltag==1&&f->rtag==1&&f->rchild!=NULL)printf("→%c",f->rchild->data);//如果此結點有前驅也有後繼，就輸出後繼
elseif(f->rtag==1&&f->rchild!=NULL)printf("【%c】→%c",f->data,f->rchild->data);//如果沒有前驅，就輸出此結點和後繼
printf("
");
if(f->ltag!=1)PrintIndex(f->lchild);
if(f->rtag!=1)PrintIndex(f->rchild);
}
}
Bithptr*SearchChild(Bithptr*point,charfindnode)//查找孩子結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if(point->data==findnode)returnpoint;
else
if(point->ltag!=1){point1=SearchChild(point->lchild,findnode);if(point1!=NULL)returnpoint1;}
if(point->rtag!=1){point2=SearchChild(point->rchild,findnode);if(point2!=NULL)returnpoint2;}
returnNULL;
}
else
returnNULL;
}
Bithptr*SearchPre(Bithptr*point,Bithptr*child)//查找父親結點函數
{
Bithptr*point1,*point2;
if(point!=NULL)
{
if((point->ltag!=1&&point->lchild==child)||(point->rtag!=1&&point->rchild==child))returnpoint;//找到則返回
else
if(point->ltag!=1)
{
point1=SearchPre(point->lchild,child);
if(point1!=NULL)
returnpoint1;
}
if(point->rtag!=1)
{
point2=SearchPre(point->rchild,child);
if(point2!=NULL)
returnpoint2;
}
returnNULL;
}
else
returnNULL;
}
voidInsert(Bithptr*root)
{
charch;
charc;
Bithptr*p1,*child,*p2;
printf("請輸入要插入的結點的信息:");
scanf("%c",&c);
scanf("%c",&c);
p1=(Bithptr*)malloc(sizeof(Bithptr));//插入的結點信息
p1->data=c;
p1->lchild=NULL;
p1->rchild=NULL;
p1->rtag=0;
p1->ltag=0;
printf("輸入查找的結點信息:");
scanf("%c",&ch);
scanf("%c",&ch);
child=SearchChild(root,ch);//查孩子結點的地址
if(child==NULL){
printf("沒有找到結點
");
system("pause");
return;
}
elseprintf("發現結點%c
",child->data);
if(child->ltag==0)//當孩子結點有左孩子的時候
{
p2=child;
child=child->lchild;
while(child->rchild&&child->rtag==0)//找到左子樹下，最右結點
child=child->rchild;
printf("發現結點%c
",child->data);
p1->rchild=child->rchild;//後繼化
p1->rtag=1;
child->rtag=0;
child->rchild=p1;//連接
p1->lchild=child;//前驅化
p1->ltag=1;
}
else//當孩子結點沒有左孩子的時候
{
p1->lchild=child->lchild;//前驅化
child->ltag=0;
p1->ltag=1;
child->lchild=p1;
p1->rchild=child;
p1->rtag=1;
}
printf("	插入結點操作已經完成，並同時完成了線索化的恢復
");
}