线性表
四、已知一个单向链表，试给出复制该链表的算法。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main 函数中进行测试：先构建一个线性表，并定义一个空线性表，然后进行复制。
五、写出从一个带表头的单链表中删除其值等于给定值x 的结点的算法函数：
int delete(LIST &L, int x);如果x 在该链表中，则删除对应结点，并返回其在链表中的位置（逻辑位置，第一个结点的逻辑位置为1），否则返回-1。
要求：1、定义线性表的节点的结构以及节点的型和位置的型。
2、定义线性表的基本操作
3、在1，2的基础上，完成本题。
4、在main 函数中进行测试：先构建一个线性表，然后调用函数删除值等于给定值的节点。
#include
#include
using namespace std;
typedef int elementtype;
struct node{
elementtype element;
node *next;
};
typedef node *LIST;
typedef node *position;
position End(LIST L)//求末尾节点
{
position p=L;
while(p->next!=NULL)
{
p=p->next;
}
return p;
}
void Insert(elementtype x,position p)//插入
{
position q=new node;
q->element=x;
q->next=p->next;
p->next=q;
}
void Delete(position p)//删除
{
if(p->next!=NULL)
{
position q=p->next;
p->next=q->next;
delete q;
}
}
position Locate(elementtype x,LIST L)//定位值为x 的元素
{
position p=L;
while(p->next!=NULL&&p->next->element!=x)
p=p->next;
return p;
}
position MakeNULL(LIST &L)//置空
{
L=new node;
L->next=NULL;
return L;
}
void Print(LIST L)//打印连表中元素
{
position p=L->next;
while(p!=NULL)
{
coutelement
p=p->next;
}
cout
}
void Copy(LIST &L1,LIST L2)
{
position p1=L1;
position p2=L2->next;
while(p2!=NULL)
{
position n =new node;
n->element=p2->element;
n->next=NULL;
p1->next=n;
p2=p2->next;
p1=p1->next;
}
p1=NULL;
}
void Read(LIST &L)
{
position p=L;
cout
int m;
for(;;)
{
position n=new node;
cin>>m;
if(m==-1)
break;
n->element=m;
n->next=NULL;
p->next=n;
p=p->next;
}
}
int deleteElement(LIST &L,int x)
{
position p=L;
int loc=0;
while(p->next)
{
if(p->next->element==x)
{
position q=p->next;
p->next=q->next;
delete q;
return ++loc;
}
++loc;
p=p->next;
}
return -1;
}
int main()
{
LIST L1 = new node;
} L1->next = NULL; LIST L2 = new node; L2->next = NULL; Read(L2); Print(L2); Copy(L1, L2); Print(L1); int n; cout > n; int value = deleteElement(L1, n); if (value == -1){ cerr
树
五、已知非空二叉树T ，写一个算法，求度为2的结点的个数。 要求：
1、定义二叉树的抽象数据类型和型BTREE ，并定义基本操作。
2、编写函数count2(BTREE T)，返回度为2的节点的个数。
3、在主函数中，构建一个二叉树，并验证所编写的算法。
六、用递归方法写一个算法，求二叉树的叶子结点数int leafnum(BTREE T)。 要求：
1、 定义二叉树的抽象数据类型和型BTREE ，并定义基本操作。
2、 编写函数leafnum(BTREE T)，返回树T 的叶子节点的个数。
在主函数中，构建一个二叉树，并验证所编写的算法。
#include
#include
using namespace std;
typedef char datatype;
struct node{
node *lchild;
node *rchild;
datatype data;
};
typedef node*BTREE;
void Empty(BTREE &BT)//置零
{
BT=NULL;
}
bool isEmpty(BTREE BT)//判断是否为空
{
if(BT)
return true;
else
return false;
}
BTREE CreateBT(datatype v,BTREE ltr,BTREE rlr)//左右子树建立二叉树 {
BTREE root;
root->data=v;
root->lchild=ltr;
root->rchild-rlr;
return root;
}
BTREE Lchild(BTREE BT)//返回右子树
{
return BT->lchild;
}
BTREE Rchild(BTREE BT)//返回左子树
{
return BT->rchild;
}
datatype Data(BTREE BT)//返回节点元素
{
return BT->data;
}
void PreOrder(BTREE BT)//先根遍历
{
if(BT)
{
coutdata
PreOrder(BT->lchild);
PreOrder(BT->rchild);
}
}
void InOrder(BTREE BT)//中根遍历
{
if(BT)
{
InOrder(BT->lchild);
coutdata
InOrder(BT->rchild);
}
}
void PostOrder(BTREE BT)//后跟遍历
{
if(BT)
{
PostOrder(BT->lchild);
PostOrder(BT->rchild);
coutdata
}
}
int count2(BTREE BT)//返回度为2的节点的个数 {
if(BT->lchild==NULL&&BT->rchild==NULL) return 0;
if(BT->lchild&&BT->rchild)
return 1+count2(BT->lchild)+count2(BT->rchild); if(BT->lchild&&BT->rchild==NULL)
return count2(BT->lchild);
if(BT->lchild==NULL&&BT->rchild)
return count2(BT->rchild);
}
int leafnum(BTREE BT)//返回叶节点个数
{
static int count=0;
if(BT->lchild==NULL&&BT->rchild==NULL) {
return ++count;
}
else
{
leafnum(Lchild(BT));
leafnum(Rchild(BT));
}
}
void CreateBTREE(BTREE &BT,char *str)//先根输入树 {
char ch;
ch=*str++;
if(ch=='#')
BT=NULL;
else
{
BT=new node; BT->data=ch;
CreateBTREE(BT->lchild,str); CreateBTREE(BT->rchild,str); }
}
int main()
{
BTREE BT=NULL;
char *str="abc##d##ef##g##"; CreateBTREE(BT,str); PreOrder(BT);
cout
InOrder(BT);
cout
PostOrder(BT);
cout
}
cout