数据结构上机实验报告学院：电子工程学院专业：信息对抗技术姓名：学号：教师：饶鲜日期：目录实验一线性表................................................. - 4 -一、实验目的................................................ - 4 -二、实验代码................................................ - 4 -三、实验结果............................................... - 14 -四、个人思路............................................... - 15 -实验二栈和队列.............................................. - 15 -一、实验目的............................................... - 15 -二、实验代码............................................... - 16 -三、实验结果............................................... - 24 -四、个人思路............................................... - 25 -实验三数组.................................................. - 26 -一、实验目的............................................... - 26 -二、实验代码............................................... - 26 -三、实验结果............................................... - 28 -四、个人思路............................................... - 28 -实验四树.................................................... - 29 -一、实验目的............................................... - 29 -二、实验代码............................................... - 29 -三、实验结果............................................... - 39 -四、个人思路............................................... - 39 -实验一线性表一、实验目的1．熟悉线性表的顺序和链式存储结构2．掌握线性表的基本运算3．能够利用线性表的基本运算完成线性表应用的运算二、实验代码1．设有一个线性表E={e1, e2, … , e n-1, e n}，设计一个算法，将线性表逆置，即使元素排列次序颠倒过来，成为逆线性表E’={ e n, e n-1 , … , e2 , e1 }，要求逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表示，分别用两个程序来完成。

（文件夹：习题1）代码：单链表代码：//单链表逆置主文件.cpp#include<iostream.h>#include<stdio.h>#include"单链表结构类型定义.h"#include"建立单链表.h"#include"输出单链表.h"#include"单链表逆置.h"void main(){linklist*head;creat(head);print(head);invert(head);//调用单链表逆置的函数 print(head);}//单链表结构类型定义.htypedef char datatype;typedef struct node{datatype data;struct node *next;}linklist;//建立单链表.hvoid creat(linklist*&head)//采用尾插法建立具有结点的单链表{char ch;linklist *s,*r;head=new linklist;r=head;while((ch=getchar())!='*'){s=new linklist;s->data=ch;r->next=s;r=s;}r->next=NULL;}//输出单链表.hvoid print(linklist *head) {linklist*p=head->next;while(p!=NULL){cout<<p->data<<" ";p=p->next;}cout<<endl;}//单链表逆置.hvoid invert(linklist*head) {linklist*p,*q,*r;p=head->next;q=p->next;while(q!=NULL){r=q->next;q->next=p;p=q;q=r;}head->next->next=NULL;head->next=p;}单链表结果截图见下方实验结果。

顺序表代码：//顺序表逆置主文件.cpp#include<iostream.h>#include<stdio.h>#include"顺序表结构类型定义.h" #include"建立顺序表.h"#include"输出顺序表.h"#include"顺序表逆置.h"void main(){sequenlist*L;creat(L);print(L);invert(L);//调用顺序表逆值的函数 print(L);}//顺序表的结构类型定义.htypedef char datatype;const int maxsize=1024;typedef struct{ datatype data[maxsize];int last;}sequenlist;//建立顺序表.hvoid creat(sequenlist*&L){L=new sequenlist;L->last=0;char ch;while((ch=getchar())!='*') {L->data[L->last]=ch;L->last++;}}//输出顺序表.hvoid print(sequenlist*L){for(int i=0;i<L->last;i++)cout<<L->data[i]<<" ";cout<<endl;}//顺序表逆置.hvoid invert(sequenlist*L){char mid;int i,j;i=0;j=L->last-1;while(i<j){mid=L->data[i];L->data[i]=L->data[j];L->data[j]=mid;i++;j--;}}顺序表实验截图见下方实验结果。

2．已知由不具有头结点的单链表表示的线性表中，含有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表示的线性表，使每个表中只含有同一类的字符，且利用原表中的结点空间，头结点可另辟空间。

（文件夹：习题2）代码：//分解单链表主程序文件.cpp#include<iostream.h>#include<stdio.h>#include"单链表结构类型定义.h"#include"建立单链表.h"#include"输出单链表.h"#include"输出循环链表.h"#include"在循环链表中插入.h"#include"分解单链表.h"void main(){ linklist *head,*letter,*digit,*other;creat(head);print1(head);letter=new linklist;letter->next=letter;digit=new linklist;digit->next=digit;other=new linklist;other->next=other;resolve(head,letter,digit,other);//调用分解单链表的函数 print2(letter);print2(digit);print2(other);}//单链表结构类型定义typedef char datatype; typedef struct node{ datatype data;struct node *next;}linklist;void creat(linklist*&head) //建立单链表{ datatype x;linklist *s,*r;head=new linklist;r=head;cin>>x;while(x!='$'){s=new linklist;s->data=x;r->next=s;r=s;cin>>x;}r->next=NULL;}void print1(linklist*head)//输出单链表{ linklist *p=head->next;while(p!=NULL){ cout<<p->data;p=p->next;}cout<<endl;}void print2(linklist*head)//输出循环链表{ linklist *p=head->next;while(p!=head){ cout<<p->data;p=p->next;}cout<<endl;}//在循环链表中插入.hvoid insert(linklist*h,linklist*p) { linklist *q=h;while(q->next!=h) q=q->next;q->next=p;p->next=h;}//分解单链表.hvoid resolve(linklist* head,linklist* letter,linklist* digit,linklist* other) {linklist* p = head->next,*t;head->next =NULL;while (p!=NULL){t = p; p=p->next;if (t->data >='0' && t->data <='9')insert(digit,t);else if ((t->data >='a' && t->data <='z') ||(t->data >='A' && t->data <='Z'))insert(letter,t);else insert(other,t);}return;}截图见下方实验结果。