200分求高人解决数据结构试题(C语言版),先付100分,解决以后本人还有100分送

本来很简单，我也没时间这是我们的一次实验报告，希望对你的树形结构提高能有帮助
模拟因特网域名查找
一、问题描述
1、 实验内容
利用属性结构的搜索算法模拟因特网域名查找
2、 基本要求
首先要实现一个反映域名结构的树，叶子节点另有一个数据与存放站点的IP地址。
3、 测试数据
去常用到的著名站点的域名和IP地址为例构建域名结构的树，一般要有几十个左右站点域名。当输入域名时，输出其域名；输入找不到的域名时，输出应为“找不到服务器或发生DNS错误”。
二、需求分析
1、程序能达到的基本功能：
本程序能根据内存中存储的树形结构，当输入域名时，输出IP地址或者找不到的信息。
2、输入的形式和输入值的范围：
程序运行后显示提示信息，由用户输入一个域名，程序自动建树，程序将提示是否继续输入,用户可以继续输入域名和IP地址,知道输入“N”，接着程序将在内存中建立一棵二叉树，接着用户就可以输入要查找的域名，系统输出IP地址或者输出出错信息。
输入的域名可以是任意形式，IP地址也可以是任意形式
域名字符数目应不大于30，每一层域名应不大于10，输入的域名数目可以为任意个。
3、用户输入查找的域名后，系统将自动输出IP地址或者输出出错信息。
4、测试数据
域名字符数目应不大于30，每一层域名应不大于10，输入的域名数目可以为任意个。
三、概要设计
为实现上述功能，需要栈、二叉树两个抽象数据类型
1、 栈的抽象数据类型定义为：
ADT Stack
{ 数据对象：typedef struct{
char *elem;
int top;
}Stack;
数据关系：栈中元素先进后出
数据操作：InitStack(Stack&S)
初始条件：栈S不存在。
操作结果：建立一个空栈。
Pop(Stack&S,char &e)
初始条件：栈S非空
操作结果：用e返回栈顶元素
Push(Stack&S,char e)
初始条件：存在栈
操作结果：将元素e压入S栈
StackEmpty(Stack &S)
初始条件：存在栈S
操作结果：返回栈是否为空
}ADT Stack
ADT CSTree{
数据对象：typedef struct CSNode{
char y[10];
char *d;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;
数据关系：结点关系为父子关系或兄弟关系
基本操作：Insert(CSTree &T,char *w)
初始条件：树T存在或不存在，w为一字符串。
操作结果：将表示域名的w插入树T
Found(CSTree T,char *w)
初始条件：树T存在，w唯一输入要查找的域名字符串
操作结果：返回w对应的域名或出错信息
}ADT CSTree
2、 本程序包括四个模块
主程序模块；
二叉树操作模块；
域名操作模块；
之间的调用关系为：

核心算法为void main()
{
char c='Y';
char w[30];
CSTree T;
T=NULL;
while(c=='Y'){
printf("输入域名:\n");
scanf("%s",w);
Insert(T,w);
printf("继续输入域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//whi8le
c='Y';
while(c=='Y'){
printf("输入要查询的域名:\n");
scanf("%s",w);
Found(T,w);
printf("继续查询域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//while
}//main
四、详细设计：
1、元素类型、结点类型和指针类型。
typedef struct{
char *elem; //
int top;
}Stack;
typedef struct CSNode{
char y[10]; //域名的一层
char *d; //IP地址
struct CSNode *firstchild,*nextsibling;//指向树节点
}CSNode,*CSTree;
3、 各操作的伪码算法
void InitStack(Stack&S){
S.top=-1;
S.elem=new char[10];
}

void Push(Stack&S,char e)
{
S.elem[++S.top]=e;
}
bool Pop(Stack&S,char &e){
if(S.top==-1)return FALSE;
e=S.elem[S.top--];
return TRUE;
}
bool StackEmpty(Stack &S){
if(S.top==-1)return TRUE;
return FALSE;
}
void Divide(char *w,char *a)
{ //用a返回w的最后一个'.'后的字符串
int n,i=0;
char e;
Stack S;
InitStack(S);
n=strlen(w);
i=n-1;
for(;w[i]!='.'&&i>=0;i--){
Push(S,w[i]);
w[i]='\0';
}//for
if(i>0)
w[i]='\0';//w[i]将最后一个'.'变为'\0'
i=0;
while(!StackEmpty(S)){
Pop(S,e);
a[i]=e;
i++;
}//while
a[i]='\0';
}//Divide

void Insert(CSTree &T,char *w)
{ // insert string w to tree T
CSNode *p;
char a[10];
if(!T){
Divide(w,a);
T=new CSNode;
p=T;
p->firstchild=p->nextsibling=NULL;
p->d=NULL;
strcpy(p->y,a);
while(*w!='\0'){
p->firstchild=new CSNode;
p=p->firstchild;
Divide(w,a);
strcpy(p->y,a);
p->nextsibling=p->firstchild=NULL;
p->d=NULL; ;
}//WHILE
printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d);
//for(p=T;p->firstchild!=NULL;p=p->firstchild)
//printf("%s\n",p->y);
}//if
else {
p=T;
Divide(w,a);
if(*w=='\0'){
while(p->nextsibling!=NULL)
p=p->nextsibling;
p->nextsibling=new CSNode;
p=p->nextsibling;
p->firstchild=p->nextsibling=NULL;
p->d=NULL;
strcpy(p->y,a);

printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d);
}//if
else{
while((strcmp(p->y,a)!=0)&&(p->nextsibling!=NULL))
p=p->nextsibling;
if(strcmp(p->y,a)==0){
p=p->firstchild;
Insert(p,w);
}//if
else{
p->nextsibling=new CSNode;
p=p->nextsibling;
strcpy(p->y,a);
p->nextsibling=p->firstchild=NULL;
p->d=NULL;
while(*w!='\0'){
p->firstchild=new CSNode;
p=p->firstchild;
Divide(w,a);
strcpy(p->y,a);
p->nextsibling=p->firstchild=NULL;
p->d=NULL;
}//WHILE
printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d);
}//else
}//else
//for(p=T;p->firstchild!=NULL;p=p->firstchild)
//printf("%s\n",p->y);

}//else
}//Insert

void Found(CSTree T,char *w)
{ //查找w是否在树中,并输出信息
char a[10];
Divide(w,a);
CSNode *p;
p=T;
while((strcmp(p->y,a)!=0)&&(p->nextsibling!=NULL))
p=p->nextsibling;
if(strcmp(p->y,a)!=0)
printf("找不到服务器或发生DNS错误。\n");
else{
if(*w=='\0')
printf("该域名地址为:%s\n",p->d);
else{
p=p->firstchild;
Found(p,w);
}//else
}//else
}//Found
主函数算法：
void main()
{
char c='Y';
char w[30];
CSTree T;
T=NULL;
while(c=='Y'){
printf("输入域名:\n");
scanf("%s",w);
Insert(T,w);
printf("继续输入域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//whi8le
c='Y';
while(c=='Y'){
printf("输入要查询的域名:\n");
scanf("%s",w);
Found(T,w);
printf("继续查询域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//while
}//main
五、调试分析
1、通过这个程序的设计，我更加深了对链表和二叉树的理解
调试程序时，起初我忘了将树的节点的左右指针付初值NULL，所以程序老运行错误，调试好这一错误后，程序才得以顺利运行。
调试的时候我还用了很多printf语句用以调试程序这样确实很有效，调试好之后只需加“//”，或者删除。
2、算法的时空分析
每输入一个域名时，都要查找四次，所以时间复杂度为O(n),空间复杂度为O（n）。
六、使用说明
程序运行后用户根据提示输入域名和IP地址，域名字符数目应不大于30，每一层域名应不大于10，输入的域名数目可以为任意个。程序将自动建立树
查找域名，当输入域名时，程序将自动查找域名。
七、测试结果：
输入域名:
www.ustc.edu.cn
Input the address:
23/23.4.234.
继续输入域名?(Y/N)
Y
输入域名:
www.tsinghua.edu.cn
Input the address:
23.23.34.4
继续输入域名?(Y/N)
Y
输入域名:
ftp.ustc.edu.cn
Input the address:
23.4.65.78
继续输入域名?(Y/N)
Y
输入域名:
34234
Input the address:
alskdfj
继续输入域名?(Y/N)
N
输入要查询的域名:
34234
该域名地址为:alskdfj
继续查询域名?(Y/N)
Y
输入要查询的域名:
www.ustc.edu.cn
该域名地址为:23/23.4.234.
继续查询域名?(Y/N)
Y
输入要查询的域名:
www.usct.edu.cn
找不到服务器或发生DNS错误。
继续查询域名?(Y/N)
N
Press any key to continue
八、附录：
程序清单：
#include
#include
#include
#include

const TRUE=1;
const FALSE=0;

typedef struct{
char *elem;
int top;
}Stack;
typedef struct CSNode{
char y[10];
char *d;
struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

void InitStack(Stack&S){
S.top=-1;
S.elem=new char[10];
}

void Push(Stack&S,char e)
{
S.elem[++S.top]=e;
}
bool Pop(Stack&S,char &e){
if(S.top==-1)return FALSE;
e=S.elem[S.top--];
return TRUE;
}
bool StackEmpty(Stack &S){
if(S.top==-1)return TRUE;
return FALSE;
}

void Divide(char *w,char *a)
{ //用a返回w的最后一个'.'后的字符串
int n,i=0;
char e;
Stack S;
InitStack(S);
n=strlen(w);
i=n-1;
for(;w[i]!='.'&&i>=0;i--){
Push(S,w[i]);
w[i]='\0';
}//for
if(i>0)
w[i]='\0';//w[i]将最后一个'.'变为'\0'
i=0;
while(!StackEmpty(S)){
Pop(S,e);
a[i]=e;
i++;
}//while
a[i]='\0';
}//Divide

void Insert(CSTree &T,char *w)
{ // insert string w to tree T
CSNode *p;
char a[10];
if(!T){
Divide(w,a); //printf("w 是 %s,a 是 %s\n",w,a);
T=new CSNode;
p=T;
p->firstchild=p->nextsibling=NULL;
p->d=NULL;
strcpy(p->y,a); //printf("p->y 是 %s,a 是 %s\n",p->y,a);
while(*w!='\0'){
p->firstchild=new CSNode;
p=p->firstchild;
Divide(w,a);
strcpy(p->y,a); //printf("p->y 是 %s,w是 %s\n",p->y,w);
p->nextsibling=p->firstchild=NULL;
p->d=NULL; //printf("p->y 是 %s,a 是 %s\n",p->y,a);
}//WHILE
printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d);
//for(p=T;p->firstchild!=NULL;p=p->firstchild)
//printf("%s\n",p->y);
}//if(没有错的一段)
else {
p=T;
Divide(w,a); //printf("w 是 %s,a 是 %s\n",w,a);
if(*w=='\0'){
while(p->nextsibling!=NULL)
p=p->nextsibling;
p->nextsibling=new CSNode;
p=p->nextsibling;
p->firstchild=p->nextsibling=NULL;
p->d=NULL;
strcpy(p->y,a);
//printf("w 是 %s,a 是 %s\n",w,a);
printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d); //printf("p->y 是 %s,w是 %s\n",p->y,w);
}//if
else{
while((strcmp(p->y,a)!=0)&&(p->nextsibling!=NULL))
p=p->nextsibling;
if(strcmp(p->y,a)==0){ //printf("p->y 是 %s,w 是 %s\n",p->y,w);
p=p->firstchild;
Insert(p,w);
}//if(以上无错)
else{
p->nextsibling=new CSNode;
p=p->nextsibling;
strcpy(p->y,a);
p->nextsibling=p->firstchild=NULL;
p->d=NULL;
while(*w!='\0'){
p->firstchild=new CSNode;
p=p->firstchild;
Divide(w,a);
strcpy(p->y,a);
p->nextsibling=p->firstchild=NULL;
p->d=NULL;
}//WHILE
printf("Input the address:\n");
p->d=new char[20];
scanf("%s",p->d);
}//else
}//else
//for(p=T;p->firstchild!=NULL;p=p->firstchild)
//printf("%s\n",p->y);

}//else
}//Insert

void Found(CSTree T,char *w)
{ //查找w是否在树中,并输出信息
char a[10];
Divide(w,a); //printf("w 是 %s,a 是 %s\n",w,a);
CSNode *p;
p=T;
while((strcmp(p->y,a)!=0)&&(p->nextsibling!=NULL))
p=p->nextsibling; //printf("p->y 是 %s,w 是 %s\n",p->y,w);
if(strcmp(p->y,a)!=0)
printf("找不到服务器或发生DNS错误。\n");
else{
if(*w=='\0')
printf("该域名地址为:%s\n",p->d);
else{ // printf("p->y:%s\n",p->y);
p=p->firstchild; //printf("p->y:%s\n",p->y);
Found(p,w);
}//else
}//else
}//Found

/******************************************************
******
*****************************/

void main()
{
char c='Y';
char w[30];
CSTree T;
T=NULL;
while(c=='Y'){
printf("输入域名:\n");
scanf("%s",w);
Insert(T,w);
printf("继续输入域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//whi8le
c='Y';
while(c=='Y'){
printf("输入要查询的域名:\n");
scanf("%s",w);
Found(T,w);
printf("继续查询域名?(Y/N)\n");
scanf("%c",&c);
scanf("%c",&c);
}//while
}//main

1.//存储结构：deque
//多项式相加的基本过程：(1)、两个多项式的最高次幂较高的那个，存入endPower；
// (2)、从ix=0开始，对多项式的对应项做运算；
// (3)、递增，如果ix>=endPower，结束；否则，重复2和3。

#include
#include
using namespace std;

class Expression {
public:
Expression() { int highestPower=0; factors=deque(0.0); }
~Expression() { factors.clear(); }

bool create();
void display();
Expression &add( Expression &another );
Expression &subtract( Expression &another );

int HighestPower() const;
double Factor( int index ) const;
private:
int highestPower; //最高次幂
deque factors; //系数（从最高次幂~0的系数都保存，如果某次幂不存在，则系数为0）
};

bool
Expression::
create() {
cout<<"Enter the highest power: ";
cin>>highestPower;

double dTemp;
for( int ix=highestPower; ix>=0; --ix ) {
cout<<"Enter the factor of x^"< cin>>dTemp;
factors.push_front( dTemp );
}

return true;
}

void
Expression::
display() {
for( int ix=highestPower; ix>=0; --ix ) {
if( ix0 )
cout<<"+";
if( factors.at(ix)!=0 ) {
cout< if( ix>0 )
cout<<"x"<<"^"< }
}
cout<}

Expression &
Expression::
add( Expression &another ) {
int endPower = (highestPower>another.HighestPower()) ? highestPower : another.HighestPower();
for( int ix=0; ix<=endPower; ++ix ) {
if( ix>highestPower ) {
factors.push_back( another.Factor(ix) );
highestPower=ix;
} else if( ix<=another.HighestPower() ){
factors.at(ix) += another.Factor(ix);
}
}

return *this;
}

Expression &
Expression::
subtract( Expression &another ) {
int endPower = (highestPower>another.HighestPower()) ? highestPower : another.HighestPower();
for( int ix=0; ix<=endPower; ++ix ) {
if( ix>highestPower ) {
factors.push_back( (-1)*another.Factor(ix) );
highestPower=ix;
} else if( ix<=another.HighestPower() ){
factors.at(ix) -= another.Factor(ix);
}
}

return *this;
}

int
Expression::
HighestPower() const {
return highestPower;
}

double
Expression::
Factor( int index ) const {
return factors.at(index);
}

int main() {
Expression aExpression, bExpression;
if( aExpression.create() )
aExpression.display();
if( bExpression.create() )
bExpression.display();

cout<<"aExpression.add( bExpression ): "< aExpression.add( bExpression );
aExpression.display();

cout<<"aExpression.subtract( bExpression ): "< aExpression.subtract( bExpression );
aExpression.display();
}
2.char *a;
int m;
cout<<"输入猴子个数:"<cin>>m;
a=new char[m];
cout<<"输入N:"<int n;
cin>>n;
if(n>m)
{
cout<<"输入错误,必须小于M="<cin>>n;
}
for(int i=0;i{
a[i]=1;
}
bool c=true;
for (int j=0;;j++)
{
for(int k=0;k{
if(a[k]!=0)
{
c=false;
break;
}
else c=true;
}
if(c!=true)//判断退出
break;
if(j%n==0)
a[j%m]=0;

}
int result=j%m;
cout<<"最后猴子的序号是:"<
---------------2-----------------
insert(int arry[],int address,int data)
{
int l=arry.length();
for(int i=l-1;i>address;i--)
{
arry[i]=arry[i-1];
}
arry[i]=data;
}

sort01(int a[])
{
int temp;
int l=a.length();
temp=a[0];
for(int i=1;i{
if(a[i]insert(a,i-1,temp);
temp=a[i];
}
}

------------------------------------
swap(int *x,int *y)
{
int temp;
temp=*x;
*y=temp
*x=*y;
}

l=a.length;
temp1=a[0];temp2=a[1];
for(int k=0;kfor(int i=k;i{
if(a[i]>a[i+1])
swap(a[i],a[i+1);
}

3.//二叉树

struct node {

int key;

node* left;

node* right;

};

//链表

struct list {

node* data;

list* next;

};

//队列

struct queue {

list* front;

int count;

list* rear;

};

//Enqueue for Breadth-First Traversal

queue* BST::_enqueue (queue* Q, node* n) //进队

{

list* pNew = new list;

pNew->data = n;

pNew->next = NULL;

if (Q->count == 0)

Q->front = pNew;

else

Q->rear->next = pNew;

Q->rear = pNew;

Q->count++;

return Q;

}

//Dequeue for Breadth-First Traversal

node* BST::_dequeue (queue* &Q) //出队

{

if (Q->count == 1)

Q->rear = NULL;

list* pDel = Q->front;

node* temp = pDel->data;

Q->front = Q->front->next;

Q->count--;

delete pDel;

pDel = NULL;

return temp;

}

//Breadth-First Traversal (层序遍历）

void BST::_traverse (const node* T)

{

queue* Q = new queue;

Q->front = Q->rear = NULL;

Q->count = 0;

while (T != NULL)

{

cout << T->key << " ";

if (T->left != NULL)

Q = _enqueue (Q, T->left); //左孩子进队

if (T->right != NULL)

Q = _enqueue (Q, T->right); //右孩子进队

if (Q->count != 0) //排队输出下一个将要处理的节点

T = _dequeue (Q);

else //队列为空，跳出

T = NULL;

}

return ;

}

靠来，这么多代码怎么给你写，暂时没时间
你不是来找人给你做作业吧？
其实这几个问题都很简单
告诉我你的邮箱，我抽时间发给你吧~！

哇好厉害吖
羡慕死啦^_^

去你邮箱看看