数据结构上机实验报告 学 院：电子工程学院 专 业：信息对抗技术 姓 名： 学 号： 教 师：饶 鲜 日 期：目 录实验一 线性表 - 2 -一、实验目的 - 2 -二、实验代码 - 2 -三、实验结果 - 8 -四、个人思绪 - 9 -实验二 栈和队列 - 9 -一、实验目的 - 9 -二、实验代码 - 10 -三、实验结果 - 15 -四、个人思绪 - 16 -实验三 数组 - 16 -一、实验目的 - 16 -二、实验代码 - 16 -三、实验结果 - 18 -四、个人思绪 - 18 -实验四 树 - 18 -一、实验目的 - 18 -二、实验代码 - 19 -三、实验结果 - 24 -四、个人思绪 - 25 -实验一 线性表一、实验目的1． 熟悉线性表的顺序和链式存储结构2． 掌握线性表的基本运算3． 可以运用线性表的基本运算完毕线性表应用的运算二、实验代码1． 设有一个线性表E={e1, e2, … , en-1, en}，设计一个算法，将线性表逆置，即使元素排列顺序颠倒过来，成为逆线性表E’={ en, en-1 , … , e2 , e1 }，规定逆线性表占用原线性表空间，并且用顺序表和单链表两种方法表达，分别用两个程序来完毕。
文献夹：习题1）代码：单链表代码：//单链表逆置主文献.cpp#include#include#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<data<<" "; p=p->next; } cout<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#include#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;ilast;i++) cout<data[i]<<" "; cout<last-1; while(idata[i]; L->data[i]=L->data[j]; L->data[j]=mid; i++;j--; }}顺序表实验截图见下方实验结果。
2． 已知由不具有头结点的单链表表达的线性表中，具有三类字符的数据元素（字母、数字和其他字符），试编写算法构造三个以循环链表表达的线性表，使每个表中只具有同一类的字符，且运用原表中的结点空间，头结点可另辟空间文献夹：习题2）代码：//分解单链表主程序文献.cpp#include#include#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<data; p=p->next; } cout<next; while(p!=head) { cout<data; p=p->next; } cout<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;}截图见下方实验结果。
三、 实验结果四、个人思绪 顺序表做逆置操作时将相应的首尾元素位置互换，单链表的指针end指向链表的末尾，指针start指向链表头结点，指针s用来找到指向end节点的节点，将指向链表末尾和头结点的存储内容互换，然后头结点指针指向下一节点，s指针从start节点开始遍历寻找指向end指针的节点，并将end指针赋值为s指针，就完毕了单链表的逆置，可以看出单链表和顺序表都可以完毕线性表的逆置分解单链表的实现思绪是一方面新建3个循环链表，然后顺序遍历单链表，ASCII码判断链表中的元素属于哪一类元素，然后将这个元素添加到相应的循环链表中，从而实现分解单链表的功能实验二 栈和队列一、实验目的1． 熟悉栈和队列的顺序和链式存储结构2． 掌握栈和队列的基本运算3． 可以运用栈和队列的基本运算完毕栈和队列应用的运算二、实验代码1． 假设以数组sequ[m]存放循环队列的元素，同时设变量rear和quelen分别指示循环队列中队尾元素的位置和内含元素的个数编写实现该循环队列的入队和出队操作的算法提醒：队空的条件：sq->quelen==0；队满的条件：sq->quelen==m文献夹：习题3）//循环队列入队出队的主程序文献.cpp#include
