数据结构大题

线性表

四、已知一个单向链表，试给出复制该链表的算法。

要求：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