代码1.txt

实用数据结构课后习题解答

using namespace std;
template <typename T> //模板声明，T为类型参数
voidinit_sq_LList(T *v, int m, int *n)
{v=new T\[m\];//动态申请存储空间
*n=0; //线性表长度置0
return;
}



#include <iostream>
using namespace std;
template <typename T>//模板声明，T为类型参数
void ins_sq_LList(T *v, int m, int *n, int i, T b)
{ int k;
if (*n==m)//存储空间已满，上溢错误
{ cout <<"overflow" <<endl;return; }
if (i>*n) i=*n+1;//默认为在最后一个元素之后插入
if (i<1) i=1;//默认为在第一个元素之前插入
for (k=*n; k>=i; k--) 
v\[k\]=v\[k-1\]; //从最后一个元素开始，直到第i个元素均往后移动一个位置
v\[i-1\]=b;//插入新元素
*n=*n+1;//线性表长度增加1
return;
}


#include <iostream>
using namespace std;
template <class T>//模板声明，T为类型参数
void del_sq_LList(T *v, int m, int *n, int i) 
{ int k;
if (*n==0)//线性表为空，下溢错误
{ cout <<"underflow!" <<endl;return; }
if ((i<1)||(i>*n)) //线性表中没有这个元素
{ cout <<"Not this element in the list!" <<endl;
return;
}
for (k=i; k<*n; k++) 
v\[k-1\]=v\[k\]; //从第i个元素开始，直到最后一个元素均往前移动一个位置
*n=*n-1;//线性表长度减1
return;
}


//文件名sq_LList.h
#include <iostream>
using namespace std;
template <class T>//模板声明，数据元素虚拟类型为T
classsq_LList//顺序表类
{ private://数据成员
int mm;//存储空间容量
int nn;//顺序表长度
T *v;//顺序表存储空间首地址
public://成员函数
sq_LList(){ mm=0; nn=0; return;}
sq_LList(int);//建立空顺序表，申请存储空间
void prt_sq_LList();//顺序输出顺序表中的元素与顺序表长度
int flag_sq_LList();//检测顺序表的状态
void ins_sq_LList(int, T);//在表的指定元素前插入新元素
void del_sq_LList(int); //在表中删除指定元素
};

//建立空顺序表
template <class T>
sq_LList<T>∷sq_LList(int m)
{ mm=m;//存储空间容量
v=new T\[mm\];//动态申请存储空间
nn=0;//顺序表长度为0，即建立空顺序表
return; 
}

//顺序输出顺序表中的元素与顺序表长度
template <class T>
void sq_LList<T>∷prt_sq_LList()
{ int i;
cout <<"nn=" <<nn <<endl;
for (i=0; i<nn; i++) cout <<v\[i\] <<endl;
return;
}

//检测顺序表的状态
template <class T>
int sq_LList<T>∷flag_sq_LList()
{ if (nn==mn)return(-1); //存储空间已满，返回-1
if (nn==0)return(0);//顺序表为空，返回0
return(1);//正常返回1
}

//在表的指定元素前插入新元素
template <class T>
void sq_LList<T>∷ins_sq_LList(int i, T b)
{ int k;
if (nn==mm)//存储空间已满，上溢错误
{ cout <<"overflow" <<endl;return; }
if (i>nn) i=nn+1;//默认为在最后一个元素之后插入
if (i<1) i=1;//默认为在第一个元素之前插入
for (k=nn; k>=i; k--) 
v\[k\]=v\[k-1\]; //从最后一个元素直到第i个元素均后移一个位置
v\[i-1\]=b;//插入新元素
nn=nn+1;//顺序表长度加1
return;
}

//在顺序表中删除指定元素
template <class T>
void sq_LList<T>∷del_sq_LList(int i)
{ int k;
if (nn==0)//顺序表为空，下溢错误
{ cout <<"underflow!" <<endl;return; }
if ((i<1)||(i>nn)) //顺序表中没有这个元素
{ cout <<"Not this element in the list!" <<endl;
return;
}
for (k=i; k<nn; k++)
v\[k-1\]=v\[k\];//从第i个元素直到最后一个元素均前移一个位置
nn=nn-1;//顺序表长度减1
return;
}


//文件名L2_3.cpp
#include "sq_LList.h"
int main()
{ sq_LList<double> s1(100);//建立容量为100的空顺序表对象s1
cout <<"第1次输出顺序表对象s1:" <<endl;
s1.prt_sq_LList();
s1.ins_sq_LList(0,1.5);//在第0个元素前插入1.5
s1.ins_sq_LList(1,2.5);//在第1个元素前插入2.5
s1.ins_sq_LList(4,3.5);//在第4个元素前插入3.5
cout <<"第2次输出顺序表对象s1:" <<endl;
s1.prt_sq_LList();
s1.del_sq_LList(0);//删除顺序表s1中的第0个元素
s1.del_sq_LList(2);//删除顺序表s1中的第1个元素
cout <<"第3次输出顺序表对象s1:" <<endl;
s1.prt_sq_LList();
return 0;
}


第1次输出顺序表对象s1:
nn=0
第2次输出顺序表对象s1:
nn=3
2.5
1.5
3.5
Not this element in the list!//指删除顺序表s1中的第0个元素
第3次输出顺序表对象s1:
nn=2
2.5
3.5


if (s.flag_sq_LList()!=-1) s.ins_sq_LList(3, 25);//顺序表非满进行插入操作
else{ 上溢处理 }


if (s.flag_sq_LList()!=0) s.del_sq_LList(3);//顺序表非空进行删除操作
else{ 下溢处理 }


using namespace std;
template <typename T>//模板声明，T为类型参数
void init_Stack (T *s, int m, int *top)
{ s=new T\[m\];//动态申请容量为m的存储空间
*top=0;//栈顶指针置0，即栈空
return;
}


using namespace std;
template <typename T>
voidpush(T *s，int m，int *top，T x)
{if(*top＝＝m){ printf("Stack－overflow\\n")； return； }
*top＝*top＋1；
s\[*top－1\]＝x；
return；
}


using namespace std;
template <typename T>
T pop(T *s，int m，int *top)
{T y;
if(*top＝＝0){ printf("Stack－underflow\\n")； return； }
y＝s\[*top－1\]；
*top＝*top－1；
return(y)；
}


using namespace std;
template <typename T>
Ttop(T *s，int m，int *top)
{T y;
if(*top＝＝0){ printf("Stackempty \\n")； return； }
y＝s\[*top－1\]；
return(y)；
}


//文件名sq_Stack.h
#include <iostream>
using namespace std;
//定义顺序栈类
template <class T>//模板声明，数据元素虚拟类型为T
classsq_Stack//顺序栈类
{ private://数据成员
int mm;//存储空间容量
int top;//栈顶指针
T *s;//顺序栈存储空间首地址
public://成员函数
sq_Stack(int);//构造函数，建立空栈,即栈初始化 
void prt_sq_Stack();//顺序输出栈顶指针与栈中的元素
int flag_sq_Stack();//检测顺序栈的状态
void ins_sq_Stack(T);//入栈
T del_sq_Stack(); //退栈
T read_sq_Stack(); //读栈顶元素
};
//建立容量为mm的空栈
template <class T>
sq_Stack<T>∷sq_Stack(int m)
{ mm=m;//存储空间容量
s=new T\[mm\];//动态申请存储空间
top=0;//栈顶指针为0，即建立空栈
return; 
}
//顺序输出栈顶指针与栈中的元素
template <class T>
void sq_Stack<T>∷prt_sq_Stack()
{ int i;
cout <<"top=" <<top <<endl;
for (i=top; i>0; i--) cout <<s\[i-1\] <<endl;
return;
}
//检测顺序栈的状态
template <class T>
int sq_Stack<T>∷flag_sq_Stack() 
{ if (top==mm) return(-1);//存储空间已满，返回-1
if (top==0) return(0);//栈为空，返回0
return(1);//正常返回1
}
//入栈
template <class T>
void sq_Stack<T>∷ins_sq_Stack(T x) 
{ if (top==mm)//存储空间已满，上溢错误
{ cout <<"Stack overflow!" <<endl;return; }
top=top+1;//栈顶指针进1
s\[top-1\]=x;//新元素入栈
return;
}
//退栈
template <class T>
T sq_Stack<T>∷del_sq_Stack()
{ T y;
if (top==0)//栈为空，下溢错误
{ cout <<"Stack underflow!" <<endl;return(0); }
y=s\[top-1\];//将栈顶元素赋给指定的变量y
top=top-1;//栈顶指针退1
return(y);//返回退出栈的元素
}
//读栈顶元素
template <class T>
T sq_Stack<T>∷read_sq_Stack()
{ if (top==0)//栈为空
{ cout <<"Stack empty!" <<endl;return(0); }
return(s\[top-1\]);//返回栈顶元素
}


if (s.flag_sq_Stack()!=-1) s.ins_sq_Stack(25); //顺序栈非满进行插入操作
else{ 上溢处理 }


if (s.flag_sq_Stack()!=0) y=s.del_sq_Stack(); //顺序栈非空进行退栈操作
else{ 下溢处理 }


if (s.flag_sq_Stack()!=0) y=s.read_sq_Stack();//顺序栈非空读栈顶操作
else{ 下溢处理 }


//文件名L2_4.cpp
#include "sq_Stack.h"
int main()
{ sq_Stack<int> s(10);//建立容量为10的空栈s，元素为整型
s.ins_sq_Stack(50);//将50入栈s
s.ins_sq_Stack(60);//将60入栈s
s.ins_sq_Stack(70);//将70入栈s
s.ins_sq_Stack(80);//将80入栈s
s.ins_sq_Stack(90);//将90入栈s
s.ins_sq_Stack(100);//将100入栈s
cout <<"输出栈顶指针与栈中的元素:" <<endl;
s.prt_sq_Stack();//输出栈顶指针与栈中的元素
cout <<"栈顶元素:" <<s.read_sq_Stack() <<endl;//输出栈顶元素
cout <<"输出退栈元素:" <<endl;
cout <<s.del_sq_Stack() <<endl;//输出从栈退出的元素
cout <<s.del_sq_Stack() <<endl;//输出从栈退出的元素
cout <<s.del_sq_Stack() <<endl;//输出从栈退出的元素
cout <<"再次输出栈顶指针与栈中的元素:" <<endl;
s.prt_sq_Stack();//再次输出栈顶指针与栈中的元素
return 0;
}