求高手给出部分详解，数据结构的题目，谢谢大家了~~~~~~~
1.用线性表了管理一个商品的库存表（用顺序表和链表分别实现）2。设计一个搜索系统：当输入一个数据时，可以自动排列成二叉搜索树T，输出该二叉搜索树的广义表表示形式，输出中序遍历；
输入任意元素值x，在T中查找，若存在x则显示存在，并提示：“选择是否删除或者更新或者不变”，若选择删除或者更新，操作结束后要求T仍然是一棵二叉搜索树；
将每一组数据所形成的二叉搜索树用文件形式保留，程序可以读取加载。
2.#include<iostream.h>
#include<stdlib.h>
typedef int ElemType;
struct BTreeNode {
ElemType data;
BTreeNode*left;
BTreeNode*right;
};
void InitBTree(BTreeNode*& bst)
{
bst=NULL;
}
void Insert(BTreeNode*& bst, const ElemType&item)
{
if(bst==NULL)
{
BTreeNode*p=new BTreeNode;
p->data=item;
p->left=p->right=NULL;
bst=p;
}
else if(item<bst->data)
Insert(bst->left, item);
else
Insert(bst->right, item);
}
void CreateBSTree(BTreeNode*& bst, ElemType a[], int n)
{
bst=NULL;
for(int i=0; i<n; i++)
Insert(bst, a[i]);
}
void PrintBTree(BTreeNode*bst)
{
if(bst!=NULL) {
cout<<bst->data;
if(bst->left!=NULL || bst->right!=NULL) {
cout<<'(';
PrintBTree(bst->left);
if(bst->right!=NULL)
cout<<',';
PrintBTree(bst->right);
cout<<')';
}
}
}
void InOrder(BTreeNode* bst)
{
if(bst!=NULL) {
InOrder(bst->left);
cout<<bst->data<<' ';
InOrder(bst->right);
}
}
bool Find(BTreeNode*bst, ElemType&item)
{
if(bst==NULL) return 0;
else {
if(item==bst->data) {
item=bst->data;
return 1;
}
else if(item<bst->data)
return Find(bst->left, item);
else
return Find(bst->right, item);
}
}
bool Delete(BTreeNode*& bst, const ElemType&item)
{
if(bst==NULL) return 0;
if(item<bst->data) return Delete(bst->left, item);
if(item>bst->data) return Delete(bst->right, item);
BTreeNode*temp=bst;
if(bst->left==NULL) {
bst=bst->right; delete temp; return 1;
}
else if(bst->right==NULL) {
bst=bst->left; delete temp; return 1;
}
else {
if(bst->left->right==NULL) {
bst->data=bst->left->data;
return Delete(bst->left, bst->left->data);
}
else {
BTreeNode*p1=bst,*p2=bst->left;
while(p2->right!=NULL) {p1=p2; p2=p2->right;}
bst->data=p2->data;
return Delete(p1->right, p2->data);
}
}
}
bool Updata(BTreeNode*bst,ElemType& item,ElemType& z)
{
if(bst==NULL) return 0;
else {
if(item==bst->data) {
bst->data=z;
return 1;
}
else if(item<bst->data)
return Updata(bst->left, item,z);
else
return Updata(bst->right, item,z);
}
}
void main()
{
int *a;
int i,length;
cout<<"请输入数据的个数:";
cin>>length;
a=new int[length];
if(a)
{
cout<<"请输入所有数据:"<<endl;
for(i=0; i<length; i++) {
cin>>a[i];
}
}
else
cout<<"内存分配失败!"<<endl;
ElemType x,m,b;
BTreeNode*bst;
InitBTree(bst);
CreateBSTree(bst,a,length);
PrintBTree(bst); cout<<endl;
cout<<"中序:"; InOrder(bst); cout<<endl;
cout<<"输入一个待查找的整数值:";
cin>>x;
if(Find (bst,x)) cout<<"查找元素"<<x<<"成功!"<<endl;
else {
cout<<"查找元素"<<x<<"失败!"<<endl;
exit(1);
}
cout<<"将要对该数值"<<x<<"做什么处理?"<<endl;
cout<<"1=删除;2=更新;3=不变"<<endl;
cin>>m;
{
if(m==1) {
if(Delete (bst,x)) cout<<"删除元素"<<x<<"成功!"<<endl;
PrintBTree(bst); cout<<endl;
}
else if(m==2) {
cout<<"输入更新后的整数值:";
cin>>b;
if(Updata (bst,x,b)) cout<<"更新元素"<<x<<"成功!"<<endl;
else cout<<"更新元素"<<x<<"失败!"<<endl;
for(int i=0; i<10; i++) {
if(a[i]==x) {
a[i]=b;
CreateBSTree(bst,a,length);
}
}
PrintBTree(bst); cout<<endl;
}
else if(m==3) { PrintBTree(bst); cout<<endl; }
else { cout<<"输入无效!"<<endl; }
}
}
这是我做的第二题的前两问，求求求第三问怎么做？！！！
1.#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include<string.h>
#include<fstream.h>
struct goods
{
char code[5];
char name[15];
int minq;
int curq;
};
typedef goods ElemType;
struct List {
ElemType *list;
int size;
int MaxSize;
};
bool operator ==(const ElemType& e1, const ElemType& e2)
{
return (strcmp(e1.code,e2.code)==0);
}
bool operator <(const ElemType& e1, const ElemType& e2)
{
return (strcmp(e1.code,e2.code)==-1);
}
ostream& operator <<(ostream& ostr, const ElemType& x)
{
ostr.setf(ios::left);
ostr<<setw(6)<<x.code<<setw(12)<<x.name;
ostr<<setw(4)<<x.minq<<setw(4)<<x.curq<<endl;
return ostr;
}
#include"3.h"
void SetupGoodsList(List& L, char* fname)
{
ifstream ifstr(fname,ios::in|ios::nocreate);
if(!ifstr) {
cerr<<"File 'goods' not found!"<<endl;
exit(1);
}
goods g;
int i=1;
while(ifstr>>g.code) {
ifstr>>g.name>>g.minq>>g.curq;
InsertList(L,g,i++);
}
ifstr.close();
}
void WriteGoodsFile(char* fname, List& L)
{
ofstream ofstr(fname);
if(!ofstr) {
cerr<<"File 'goods' no create!"<<endl;
exit(1);
}
goods g;
int n=LengthList(L);
for(int i=1; i<=n; i++) {
g=GetList(L,i);
ofstr<<g.code<<" "<<g.name<<" "<<g.minq<<" "<<g.curq<<endl;
}
ofstr.close();
}
void main()
{
List L2;
InitList(L2);
SetupGoodsList(L2,"d:goods.txt");
TraverseList(L2);
int i,flag=1;
while(flag)
{
cout<<"1 打印整个库存表"<<endl;
cout<<"2 修改库存表中的记录"<<endl;
cout<<"3 删除库存表中的记录"<<endl;
cout<<"4 对库存表排序"<<endl;
cout<<"5 结束处理过程"<<endl;
cout<<"输入你的选择:";
cin>>i;
while(i<1 || i>5) {
cout<<"请重新输入选择(1-5):";
cin>>i;
}
cout<<endl;
switch(i) {
case 1:
TraverseList(L2);
break;
case 2:
goods g;
int x;
cout<<"输入待修改的商品代号:";
cin>>g.code;
if(FindList(L2,g)) {
cout<<"输入该商品的修正量:";
cin>>x;
g.curq+=x;
if(UpdataList(L2,g)) cout<<"完成更新!"<<endl;
}
else {
cout<<"输入新商品记录的其余字段的内容:"<<endl;
cin>>g.name>>g.minq>>g.curq;
InsertList(L2,g,LengthList(L2)+1);
cout<<"新记录已被插入到表尾!"<<endl;
}
break;
case 3:
cout<<"输入待删除商品的商品代号:";
cin>>g.code;
if(DeleteList(L2,g,0))
cout<<"代号为"<<g.code<<"的记录被删除!"<<endl;
else cout<<"代号为"<<g.code<<"的记录不存在!"<<endl;
break;
case 4:
SortList(L2);
cout<<"商品表中的记录已按商品代号排序!"<<endl;
break;
case 5:
cout<<"本次处理结束，再见!"<<endl;
flag=0;
}
}
WriteGoodsFile("d:goods.txt",L2);
}
int LengthList(List &L)
{
return L.size;
}
ElemType GetList(List &L, int pos)
{
if(pos<1 || pos>L.size)
{
cerr<<"pos is out range!"<<endl;
exit(1);
}
return L.list[pos-1];
}
void InitList(List &L)
{
L.MaxSize=10;
L.list=new ElemType[L.MaxSize];
if(L.list==NULL) {
cout<<"动态可分配的存储空间用完，退出运行!"<<endl;
exit(1);
}
L.size=0;
}
void TraverseList(List &L)
{
for(int i=0;i<L.size;i++)
cout<<L.list[i]<<' ';
cout<<endl;
}
bool FindList(List &L,ElemType& item)
{
for(int i=0;i<L.size;i++)
if(L.list[i]==item) {
item=L.list[i];
return true;
}
return false;
}
bool UpdataList(List &L, const ElemType& item)
{
for(int i=0;i<L.size;i++)
if(L.list[i]==item) {
L.list[i]=item;
return true;
}
return false;
}
bool InsertList(List &L, ElemType item, int pos)
{
if(pos<-1 || pos>L.size+1) {
cout<<"pos值无效!"<<endl; return false;
}
int i;
if(pos==0) {
for(i=0;i<L.size;i++)
if(item<L.list[i]) break;
pos=i+1;
}
else if(pos==-1) pos=L.size+1;
if(L.size==L.MaxSize) {
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list ,2*L.MaxSize*k);
if(L.list==NULL) {
cout<<"动态可分配的存储空间用完，退出运行!"<<endl;
exit(1);
}
L.MaxSize=2*L.MaxSize;
}
for(i=L.size-1; i>=pos-1; i--)
L.list[i+1]=L.list[i];
L.list[pos-1]=item;
L.size++;
return true;
}
bool DeleteList(List &L, ElemType& item, int pos)
{
if(L.size==0) {
cout<<"线性表为空，删除无效!"<<endl;
return false;
}
if(pos<-1 || pos>L.size) {
cout<<"pos值无效!"<<endl; return false;
}
int i;
if(pos==0) {
for(i=0;i<L.size;i++)
if(item==L.list[i]) break;
if(i==L.size) return false;
pos=i+1;
}
else if(pos==-1) pos=L.size;
item=L.list[pos-1];
for(i=pos;i<L.size;i++)
L.list[i-1]=L.list[i];
L.size--;
if(float(L.size)/L.MaxSize,0.4 && L.MaxSize>10) {
int k=sizeof(ElemType);
L.list=(ElemType*)realloc(L.list, L.MaxSize*k/2);
L.MaxSize=L.MaxSize/2;
}
return true;
}
void SortList(List &L)
{
int i,j;
ElemType x;
for(i=1;i<L.size;i++)
{
x=L.list[i];
for(j=i-1;j>=0;j--)
if(x<L.list[j]) L.list[j+1]=L.list[j];
else break;
L.list[j+1]=x;
}
}
这是第一题顺序表形式，问链表形式怎么做？？？？
[ 本帖最后由 ornateblue 于 2012-1-4 11:24 编辑 ]
.
