数据结构

《数据结构》实验报告

学号：

姓名：

班级：

}

cout<1．#include } 实验一 链表

using namespace std; struct node{ int data ; node* next; }; class list{ public: list(); void create_R(); void print(); node *locate(const int x)const; private: int count ; node *head; }; list::list(){ head=new node; head->next=NULL; count=0; } void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; } } void list::print(){ node *p; p=head->next; while(p!=NULL) { cout<data<<\" \"; p=p->next; node *list::locate(const int x)const{ node *p; int i=1; p=head->next; if(x>count) return NULL; else while(inext;} return p; cout<data<>i; cout<<\"查询位置指针地址为\"< using namespace std; struct node{ int data ; node* next; }; class list{ public: list(); void create_R(); void print(); void insert(const int i,const int x); private: int count ; node *head; };

list::list(){ head=new node; head->next=NULL; count=0; } void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; } } void list::insert(const int i,const int x){ node *p=NULL; p=head->next; int j=1; while(p!=NULL&&j<(i-1)){ p=p->next; j++;} node *s=new node; s->data=x; s->next=p->next; p->next=s; count++; } void list::print(){ node *p; p=head->next; while(p!=NULL) { cout<data<<\" \"; p=p->next; } cout< using namespace std; struct node{ int data ; node* next; }; class list{ public: list(); void create_R(); void print(); void delete_element(const int i); private: int count ; node *head; }; list::list(){ head=new node; head->next=NULL; count=0; } void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x;

} }

void list::delete_element(const int i){ };

class list{ public: node *p=NULL,*u=NULL; int j; p=head;j=0; while (j!=(i-1)&&p!=NULL){ p=p->next; j++; } if(i<1||i>count) cout<<\"删除位置错误\"<next; p->next=u->next; delete u; count--; }

void list::print(){ node *p; p=head->next; while(p!=NULL) {

cout<data<<\" \"; p=p->next; }

cout<int main(){ list A;

A.create_R(); A.print(); cout<4. #include using namespace std; struct node{ int data ; node* next; list(); void create_R(); void print(); void insert(const int x); private: int count ; node *head; };

list::list(){ head=new node; head->next=NULL; count=0; }

void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; } }

void list::insert(const int x){ node *p,*s; p=head;

while((p->next!=NULL)&&p->next ->datanext;

//if(p->next ==NULL||p->next ->data>x)

s=new node; s->data=x;

s->next=p->next; p->next=s; count++;

}

void list::print(){ node *p; p=head->next; while(p!=NULL) {

cout<data<<\" \"; p=p->next; }

cout<int main(){ list A;

A.create_R(); A.insert(55); cout<5. #include using namespace std; struct node{ int data ; node* next; };

class list{ public: list(); void create_R(); void print(); node*get_head(){return head;}; void copy1(list A,list B); void copy2(list A,list C); private: int count ; node *head; };

list::list(){ head=new node; head->next=NULL;

count=0; }

void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; } }

void list::copy1(list A,list B){ node *s,*PA,*PB; PA=A.get_head()->next; PB=B.get_head(); while(PA!=NULL){ s=new node; s->data=PA->data; PB->next=s; PB=s; count++; PB->next=NULL;

if(PA->next==NULL) break; PA=PA->next->next; } }

void list::copy2(list A,list C){ node* s,*PA,*PC; PA=A.get_head()->next->next; PC=C.get_head(); while(PA!=NULL){ s=new node; s->data=PA->data; PC->next=s;

PC=s; count++; PC->next=NULL; if((PA->next)==NULL) break; PA=PA->next->next; } }

void list::print(){ node *p; p=head->next; while(p!=NULL) {

cout<data<<\" \"; p=p->next; }

cout<int main(){ list A; list B;list C; A.create_R(); A.copy1(A,B); A.copy2(A,C); A.print(); cout<6. #include using namespace std; struct node{ int data ; node* next; };

class list{ public: list(); void create_R(); void print(); node *get_head(){return head;}; void merge_list(list A,list B,list C); private: int count ; node *head; };

list::list(){ head=new node; head->next=NULL; count=0; }

void list::create_R(){ int x; cin>>x; node *rear=head; while(x!=-1) { count++; node *s=new node; s->data=x; rear->next=s; rear=s; rear->next=NULL; cin>>x; } }

void list::merge_list(list A,list B,list C) { node *pa,*pb,*rc,*u; rc=C.get_head();

pa=A.get_head()->next; pb=B.get_head()->next; while(pa!=NULL&&pb!=NULL) { if(pa->data data) pa=pa->next; else if(pa->data >pb->data ) pb=pb->next; else {u=new node; u->data=pa->data; rc->next=u; rc=u; rc->next=NULL; C.count++;

pa=pa->next;pb=pb->next; } } }

void list::print(){ node *p; p=head->next; while(p!=NULL) {

cout<data<<\" \"; p=p->next; }

cout<int main(){ list A; list B;list C;

cout<<\"input A:\"<实验二 二叉树

1. #include using namespace std;

typedef struct bnode {char data;

struct bnode *lchild,*rchild; };

typedef bnode *bitre; void create_pre_bitre_(bitre { char ch; cin>>ch; if(ch=='.') T=NULL;

else{ T=new bnode; T->data =ch; create_pre_bitre_(T->lchild ); create_pre_bitre_(T->rchild ); } }

int high(bnode *T) { if(T==NULL) return 0; else return

((high(T->lchild )>high(T->rchild ))?high(T->lchild ):high(T->rchild ))+1; }

int main() {

bitre t;

cout<<\"输入该二叉树的先序序列\"<cout<<\"高度= \"<2. #include #include using namespace std; typedef struct bnode {char data;

struct bnode *lchild,*rchild; };

typedef bnode *bitre; int n=0; void create_pre_bitre_(bitre &T) { char ch; cin>>ch; if(ch=='.') T=NULL; else{ T=new bnode;

&T) T->data =ch;

create_pre_bitre_(T->lchild ); create_pre_bitre_(T->rchild ); } }

void inorder(bnode *T) { if(T!=NULL) { n++; inorder(T->lchild ); cout<data<<\"(\"<inorder(T->rchild ); n--; } }

int main() {

bitre t;

cout<<\"输入该二叉树的先序序列\"<cout<<\"该二叉树的中序序列为\"; inorder(t); cout<3. #include using namespace std; const int max=5; int i=1;char A[max]; typedef struct bnode {char data;

struct bnode *lchild,*rchild; };

typedef bnode *bitre;

void create(bitre &T,int i) { if(i>max) T=NULL; else{ if(A[i]=='.') T=NULL; else{ T=new bnode; T->data=A[i]; create(T->lchild ,2*i); create(T->rchild ,2*i+1);} } }

void create_A() { cout<<\"请输入数组：\"<for(int n=1;n第\"<>A[n];} }

void preorder(bnode *T) { if(T!=NULL) {cout<data<<\" \"; preorder(T->lchild ); preorder(T->rchild ); } }

void inorder(bnode *T){ if(T!=NULL) { inorder(T->lchild); cout<data<<\" \"; inorder(T->rchild); } }

void postorder(bnode *T) { if(T!=NULL) { postorder(T->lchild); postorder(T->rchild); cout<data<<\" \"; } }

int main() {

bitre t;

create_A();

create(t,i); cout<<\"该二叉树的先序序列为\";

preorder(t); cout<cout<<\"该二叉树的后序序列为\"; postorder(t); cout<cout<data; return 0; } 4. #include #include using namespace std; typedef struct bnode {char data; struct bnode *lchild,*rchild; }; typedef bnode *bitre; void create_pre_bitre_(bitre &T) { char ch; cin>>ch; if(ch=='.') T=NULL; else{ T=new bnode; T->data =ch; create_pre_bitre_(T->lchild ); create_pre_bitre_(T->rchild ); } } void copy_T(bitre &T,bitre &T1) { if(T==NULL) T1=NULL; else { T1=new bnode; T1->data =T->data ; copy_T(T->lchild,T1->lchild); copy_T(T->rchild,T1->rchild); } //cout<<\"拷贝成功\"<} void preorder(bnode *T) { if(T!=NULL) {cout<data<<\" \"; preorder(T->lchild ); preorder(T->rchild ); } } void inorder(bnode *T) { if(T!=NULL) { inorder(T->lchild ); cout<data<<\" \"; inorder(T->rchild ); } } void postorder(bnode *T) { if(T!=NULL) { postorder(T->lchild ); postorder(T->rchild ); cout<data<<\" \"; } } int main() { bitre t,t1; cout<<\"输入该二叉树的先序序列\"<data<postorder(t1); cout< using namespace std; typedef struct bnode {char data; struct bnode *lchild,*rchild; }; typedef bnode *bitre; void create_pre_bitre_(bitre &T)

{ char ch; cin>>ch; if(ch=='.') T=NULL; else{ T=new bnode; T->data =ch; create_pre_bitre_(T->lchild ); create_pre_bitre_(T->rchild ); } }

void exchange_child(bitre &T) { bitre temp; if(T!=NULL) { temp=T->lchild ; T->lchild =T->rchild ; T->rchild =temp; exchange_child(T->lchild); exchange_child(T->rchild); } }

void preorder(bnode *T) { if(T!=NULL) {cout<data<<\" \"; preorder(T->lchild ); preorder(T->rchild ); } }

void inorder(bnode *T) { if(T!=NULL) { inorder(T->lchild ); cout<data<<\" \"; inorder(T->rchild ); } }

void postorder(bnode *T) { if(T!=NULL) { postorder(T->lchild ); postorder(T->rchild ); cout<data<<\" \";

} }

int main() {

bitre t;

cout<<\"输入该二叉树的先序序列\"<cout<<\"调整后该二叉树的先序序列为\"; preorder(t); cout<cout<<\"调整后该二叉树的中序序列为\"; inorder(t); cout<cout<<\"调整后该二叉树的后序序列为\"; postorder(t); cout<6. #include using namespace std; typedef struct bnode {char data;

struct bnode *lchild,*rchild; };

typedef bnode *bitre;

void create_pre_bitre_(bitre &T) { char ch; cin>>ch; if(ch=='.') T=NULL; else{

T=new bnode; T->data =ch; create_pre_bitre_(T->lchild ); create_pre_bitre_(T->rchild ); } }

void preorder(bnode *T) { if(T!=NULL) {cout<data<<\" \"; preorder(T->lchild ); preorder(T->rchild ); } }

void inorder(bnode *T) { if(T!=NULL) { inorder(T->lchild ); cout<data<<\" \"; inorder(T->rchild ); } }

void postorder(bnode *T) { if(T!=NULL) { postorder(T->lchild ); postorder(T->rchild ); cout<data<<\" \"; } }

int main() {

bitre t;

cout<<\"输入该二叉树的先序序列\"<postorder(t); cout<实验三 排序

#include using namespace std; int main() { int m;

cout<<\"请输入数据长度\"<>m; int A[30]; cout<<\"请输入数据\"<>A[i]; int p,n=0; for(int k=0;k