南昌大学数据结构实验报告

1、数据结构实验指导书计算机系数据结构实验报告（1）姓名： 学号： 专业班级： 实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。问题描述：1、 构造一个空的线性表l。2、 在线性表l的第i个元素之前插入新的元素e；3、 在线性表l中删除第i个元素，并用e返回其值。实验要求：1、 分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。2、 在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。文法是一个四元 算法分析：#include#include#includeusing nam

2、espace std;#define list_init_size 100#define listincrement 10typedef structint *elem;int length;int listsize;sqlist;int initlist_sq(sqlist &l)l.elem=(int *)malloc(list_init_size*sizeof(int);if(!l.elem)return(0);l.length=0;l.listsize=list_init_size;return(1);int listcreat_sq(sqlist &l,int n,int a)int

3、 i;for(i=0;in;i+)l.elemi=ai;l.length=n;return (1);int listinsert_sq(sqlist &l,int i,int e)int *p;int *q;int *newbase;void listprint_sq(sqlist &l);if(il.length+1)coutdata error!=l.listsize)newbase=(int *)malloc(l.listsize+listincrement)*sizeof(int);if(!newbase)couterror!=q;-p)*(p+1)=*p;*q=e;+l.length

4、;cout insert order:endl;listprint_sq(l);return(2);int listdelete_sq(sqlist &l,int i,int e)int *p;int *q;int j;void listprint_sq(sqlist &l);if(il.length)coutdata error!endl;return(0);p=&(l.elemi-1);e=*p;q=l.elem+l.length-1;for(+p;p=q;+p)*(p-1)=*p;l.length-;cout deleted order:endl;listprint_sq(l);retu

5、rn(1);void listprint_sq(sqlist &l)int i;for(i=0;il.length;i+)coutsetw(5)l.elemi;coutendl;int main()sqlist l;int e=0,i;int a8;int insert_position=0;int insert_number=0;int delete_position=0;if(initlist_sq(l)=1)coutyes!endl;elsecoutsorry!endl;coutinput 8 numbers initialize the lianbiao:endl;for(i=0;ia

6、i;listcreat_sq(l,8,a);coutthe original order:endl;listprint_sq(l);coutinput the insert number insert_number;coutinput the insert position insert_position;listinsert_sq(l,insert_position,insert_number);coutinput the delete positiondelete_position;listdelete_sq(l,delete_position,e);(2).链表实现线性表的建立、插入和删

7、除操作程序：#include#include#includeusing namespace std;typedef struct lnodeint data;struct lnode *next;lnode, *linklist;int listcreate_l(linklist &l,int n)void listprint_l(linklist &l);int i; linklist p;l=(linklist)malloc(sizeof(lnode);l-next=null;for(i=n;i0;-i)p=(linklist)malloc(sizeof(lnode);cinp-data;

8、p-next=l-next;l-next=p;coutthe original order:endl;listprint_l(l);return(1);int listinsert_l(linklist &l,int i,int e)linklist p=l;linklist s;int j=0;void listprint_l(linklist &l);while(p&jnext;+j;if(!p|ji-1)coutdata error!data=e;s-next=p-next;p-next=s;cout inserted order:next&jnext;+j;if(!(p-next)|j

9、i-1)coutdata error!next;p-next=q-next;e=q-data;coutdeleted order:next;while(p)coutsetw(5)data;p=p-next;coutendl;int main()linklist l;int number;int e;int insert_position=0;int insert_number=0;int delete_position=0;coutinput the number of node that you want to create:number;coutinput the reversed dat

10、a to inliliaze the lianbiao:(按逆序输入数据初始化链表)endl;listcreate_l(l,number);coutinput the insert numberinsert_number;coutinput the insert position.insert_position;listinsert_l(l,insert_position,insert_number);coutinput the delete positiondelete_position;listdelete_l(l,delete_position,e);实验内容和过程：实验结果：总结和感想

11、：阅读完删除本文本框要求：根据本格式填写实验报告，标题用黑小四，正文字体用五号字体，word文本以“数据结构实验(1)_学号_姓名”命名。实验目的：深入了解栈和队列的特性，学会在实际问题下灵活运用它们。问题描述：表达式求值运算是实现程序设计语言的基本问题之一，也是栈应用的一个典型例子。设计并演示用算符优先级对算术表达式的求解过程。实验要求：1、算法优先级别如下：+, -, *, /, (, ), #+ , , , , , ,- , , , , , ,* , , , , , ,/ , , , , , ,( , , , , , , , , , , ,# , , , , , , =2、以字符序列的形

12、式从终端输入语法正确、不含变量的算术表达式，利用给出的算符优先级关系，实现对算术四则混合运算的求解过程。文法是一个四元算法分析：实验内容和过程：#include#include#includeusing namespace std;char a7=+,-,*,/,(,),#;char b77=, , , , ,=s.stacksize)s.base=(char *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(char);if(!s.base)return 0; s.top=s.base+s.stacksize;s.stacksize+=

13、stackincrement;*s.top+ =e;return 1;char pop(sqstack &s)char e;if(s.top=s.base)return 0;e= * -s.top;return e;int in(char c)int i;for(i=0;i=6;i+)if(ai=c)return 1;return 0;char precede(char c1,char c2)int i=0;int j=0;while(ai!=c1)i+;while(aj!=c2)j+;return bij;char operate(char x,char c,char y)int i=0;i

14、nt m,n;char d;m=x-0;n=y-0;while(c!=ai)i+;switch(ai)case +:d=(m+n)+0;break;case -:d=(m-n)+0;break;case *:d=m*n+0;break;case /:d=m/n+0;break;return d;int main()sqstack optr,opnd;char c;char theta;char x1,x2;initstack(optr);push(optr,#);initstack(opnd);c=cin.get();while(c!=#|gettop(optr)!=#)if(!in(c)pu

15、sh(opnd,c);c=cin.get();elseswitch(precede(gettop(optr),c)case :theta=pop(optr);x2=pop(opnd);x1=pop(opnd);push(opnd,operate(x1,theta,x2);break;cout(int(gettop(opnd)-0)endl;实验结果：总结和感想：虽然书上有算法，但是自己真正去编写的时候才发现其实还是有难度的，关键有一个ascii码的转换问题，什么时候变整型，什么时候变字符型符合条件。实验目的：深入研究数组的存储表示和实现技术，着重掌握对稀疏矩阵的表示方法及其运算的实现。问题描述

16、：稀疏矩阵是指那些多数元素为零的矩阵。利用稀疏特点进行存储和计算可以大大节省存储空间，提高效率。通过对稀疏矩阵的存储表示，实现矩阵的基本操作。实验要求：1、 要求矩阵的输入形式采用三元组表示，以“带行逻辑链接信息”的三元组顺序表表示稀疏矩阵。2、 设计矩阵的逆置算法，实现矩阵的逆置。3、 实现两个稀疏矩阵的相加、相减和相乘等运算。4、 要求运算结果的矩阵则以通常的阵列形式出现。文法是一个四元实验内容和过程：输入数据：2 1 00 0 00 0 32 0 01 0 00 0 3-12 1 00 0 00 0 30 0 00 0 00 0 2+=2 1 00 0 00 0 52 1 00 0 30

17、 00 00 2+=0 00 6源代码：#include #include using namespace std; const int maxsize=12500; const int maxrc=10; typedef struct int i,j; int e; triple; typedef struct triple datamaxsize+1; int mu,nu,tu; tsmatrix; typedef struct triple datamaxsize+2; int rposmaxrc+1; int mu,nu,tu; rlsmatrix; template bool inp

18、uttsmatrix(p & t,int y) cout输?入?矩?阵的?行d列d非?零?元a个?数y:t.mut.nut.tu; cout输?入?非?零?元a的?位?置?和值:endl; int k=1; for(;kt.datak.it.datak.jt.datak.e; return true; template bool outputsmatrix(p t) int m,n,k=1; for(m=0;mt.mu;m+) for(n=0;nt.nu;n+) if(t.datak.i-1)=m&(t.datak.j-1)=n) cout.width(4); coutt.datak+.e;

19、else cout.width(4); cout0; coutendl; return true; bool transposesmatrix( ) tsmatrix m,t; /定义?预转aa置?的?矩?阵 inputtsmatrix(m, 0); /输?入?矩?阵 int nummaxrc+1; int cpotmaxrc+1; / 构11建辅助数yy组 int q,p,t; t.tu=m.tu; t.mu=m.nu; t.nu=m.mu; if(t.tu) for(int col=1;col=m.nu;col+) numcol=0; for(t=1;t=m.tu;t+) +numm.da

20、tat.j; cpot1=1; for(int i=2;i=m.nu;i+) cpoti=cpoti-1+numi-1; / 求出?每?一?列dd中dd非?零?元aa素?在三yy元aa组中dd出?现?的?位?置? for(p=1;p=m.tu;p+) int col=m.datap.j; q=cpotcol; t.dataq.i=col; t.dataq.j=m.datap.i; t.dataq.e=m.datap.e; +cpotcol; cout输?入?矩?阵的?转a置?矩?阵为aendl; outputsmatrix(t); return true; bool count(rlsmatr

21、ix &t) int nummaxrc+1; int col;for(int col=1;col=t.mu;col+) numcol=0; for(col=1;col=t.tu;col+) +numt.datacol.i; t.rpos1=1; for(int i=2;i=t.mu;i+) t.rposi=t.rposi-1+numi-1; return true; bool multsmatrix ( ) rlsmatrix m,n,q; inputtsmatrix(m,1); inputtsmatrix(n,1); count(m); count(n); if(m.nu!=n.mu) re

22、turn false; q.mu=m.mu; q.nu=n.nu; q.tu=0; / q初?始?化 int ctempmaxrc+1; int arow,tp,p,brow,t,q,ccol; if(m.tu*n.tu) for( arow=1;arow=m.mu;arow+) /memset(ctemp,0,n.nu); for(int x=1;x=n.nu;x+) ctempx=0; q.rposarow=q.tu+1; if(arowm.mu) tp=m.rposarow+1; else tp=m.tu+1; for(p=m.rposarow;ptp;p+) brow=m.datap.

23、j; if(brown.mu) t=n.rposbrow+1; else t=n.tu+1; for(q=n.rposbrow;qt;q+) ccol=n.dataq.j; ctempccol += m.datap.e*n.dataq.e; for(ccol=1;ccolmaxsize) return false; q.dataq.tu.e=ctempccol; q.dataq.tu.i=arow; q.dataq.tu.j=ccol; outputsmatrix(q); return true; bool addsmatrix() tsmatrix m,n,q;inputtsmatrix(m

24、, 2);inputtsmatrix(n, 2);if(m.mu=0)|(m.nu=0)|(m.tu=0)|(n.mu=0)|(n.nu=0)|(n.tu=0) return 0; if(m.mu!=n.mu|m.nu!=n.nu) return 0; q.mu=m.mu; q.nu=m.nu; q.tu=0; int x=0,y=0; for(int i=1;i=q.mu;i+) for(int j=1;j=q.nu;j+) for(int p=1;p=m.tu;p+) if(i=m.datap.i)&(j=m.datap.j) x=m.datap.e; break; else x=0; /

25、for p for(int q=1;q=n.tu;q+) if(i=n.dataq.i)&(j=n.dataq.j) y=n.dataq.e; break; else y=0; /for q if(x+y)!=0) q.dataq.tu+1.i=i; q.dataq.tu+1.j=j; q.dataq.tu+1.e=x+y; q.tu+; /if /for j /for i outputsmatrix(q); return 1;int main() cout请?选?择?要a进?行d的?操作endl; cout1:矩?阵的?转a置?endl; cout2:矩?阵的?加法endl; cout3:矩

26、?阵的?乘?法endl; cout4:退?出?程序endl; char c=getchar(); if(c=1) transposesmatrix( ); else if(c=2) addsmatrix(); else if(c=3) multsmatrix (); else exit(0); /退?出? return 0;实验结果：总结和感想：蛮大难度的，代码量比较长，感觉还有许多都不怎么懂，照书上的码下来的，还是要多练习才行。实验目的：树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。问题描述：首先，掌握二叉树的各种存储结构

27、和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。-+/a*b-efcd如算术表达式：a+b*(c-d)-e/f实验要求：1、 如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算a) 统计叶子结点的个数。b) 求二叉树的深度。2、 十进制的四则运算的计算器可以接收用户来自键盘的输入。3、 由输入的表达式字符串动态生成算术表达式所对应的二叉树。4、 自动完成求值运算和输出结果。算法分析：#include#include#include#includeusing namespace std;#define stack_init_size

28、100#define stackincrease 10typedef char telemtype; /表示?处|理的?数y据y类型，?这a里?是?字?符?typedef struct bitnode /二t叉?树中d节点?的?数y据y结构1，?左右孩子用?指?针?表示?telemtype data;struct bitnode * lchild,* rchild;binode,* bitree;typedef bitree selemtype;typedef bitree qelemtype;typedef struct sqstack /栈?的?定义?，?是?一?个?二t叉?树组成的?栈?

29、，?每?个?成员是?一?个?指?向二t叉?树中d结点?的?指?针? selemtype *base;selemtype *top;int stacksize;sqstack;/*=栈?-adt栈?的?实现?，?包括初?始?化，?push，?pop其?实这a部?分?代码?可以?不?需要a看，?无t非?是?实现?了?栈?的?基本?操作=*/void initstack(sqstack &s)s.base=(selemtype *)malloc(stack_init_size*sizeof(selemtype);s.top=s.base;s.stacksize=stack_init_size;/in

30、itstackvoid push(sqstack &s,selemtype e)if(s.top-s.base=s.stacksize)s.base=(selemtype *)realloc(s.base,(s.stacksize+stackincrease)*sizeof(selemtype);if(!s.base)exit(1);s.top=s.base+s.stacksize;/?貌2似?多余?s.stacksize+=stackincrease;*s.top+=e;int pop(sqstack &s,selemtype &e)if(s.base=s.top)return -1;e=*

31、-s.top;return 0;bitree precreatebitree()bitree p;char ch;ch=getchar();ch=getchar(); /此?处|读两?次?的?原-因是?，?每?隔?一?个?输?入?符?号?之?间?，?有d一?个?空?格?，?需要a多读一?次?把?空?格?跳?过y去if(ch=#) return null;p=(bitree)malloc(sizeof(binode);p-data=ch;p-lchild=precreatebitree();p-rchild=precreatebitree();return p;/precreatebitreev

32、oid visit(telemtype ch)printf(%c,ch);/visit/用?来打印?data。int preread(bitree bt)if(!bt)return 0;visit(bt-data);preread(bt-lchild);preread(bt-rchild);return 0;/preread/先序遍历，?先将?data打印?，?再递y归调用?。int inread(bitree bt)if(!bt)return 0;inread(bt-lchild);visit(bt-data);inread(bt-rchild);return 0;/inread/中d序遍历

33、，?先递y归调用?左孩子，?再打印?data，?再调用?右孩子。int postread(bitree bt)if(!bt)return 0;postread(bt-lchild);postread(bt-rchild);visit(bt-data);return 0;/postread/后序遍历，?先将?左右孩子递y归调用?，?再打印?data。int number(bitree bt)int n1,n2;if(!bt) return 0;n1=number(bt-lchild);n2=number(bt-rchild);return 1+n1+n2;/number/求二t叉?树结点?数y，

34、?递y归调用?，?当头指?针?为a空?时，?返回?0，?否?则返回?1+左孩子结点?数y+右孩子结点?数y。int leaf(bitree bt)int l1,l2;if(!bt) return 0;if(!bt-lchild&!bt-rchild) return 1;l1=leaf(bt-lchild);l2=leaf(bt-rchild);return l1+l2;/leaf/求二t叉?树叶?子数y，?递y归调用?，?若?头指?针?为a空?时，?返回?0，?若?头指?针?左右孩子为a空?，?则返回?1，?否?则返回?左孩子叶?子数y+右孩子叶?子数y。int height(bitree b

35、t)int h1,h2;if(!bt) return 0;h1=height(bt-lchild);h2=height(bt-rchild);return 1+(h1h2?h1:h2);/height/求二t叉?树的?高?度，?递y归调用?，?当头指?针?为a空?时，?返回?0，?否?则返回?1+（左右孩子中d高?度最?大的?）?。int wide(bitree bt,int *w,int x)if(!bt)return 0;if(bt)wx=wx+1;if(bt-lchild)wide(bt-lchild,w,x+1);if(bt-rchild)wide(bt-rchild,w,x+1);r

36、eturn 0;/wide/求二t叉?树的?宽度，?递y归调用?，?先求得?其?高?度，?创建一?个?数y组输?入?，?并输?入?其?层?数y。若?双?亲非?空?wx+。调用?其?左右孩子。这a样就可以?得?到?每?层?的?宽度，?找到?最?大值就是?二t叉?树的?宽度。void copybitree(bitree &p,bitree q)bitree lp,rp;if(!q)p=null;elsecopybitree(lp,q-lchild);copybitree(rp,q-rchild);p=(bitree)malloc(sizeof(binode);p-data=q-data;p-lch

37、ild=lp;p-rchild=rp;/copybitree/复制?二t叉?树，?仍?是?递y归调用?。从下?向上?、从左到?右创建，?当头指?针?为a空?时，?赋3值空?指?针?。int destroybitree(bitree &bt)if(!bt)return 0;if(bt-lchild)destroybitree(bt-lchild);if(bt-rchild)destroybitree(bt-rchild);if(!bt-lchild&!bt-rchild)free(bt);bt=null;return 0;return 0;/destroybitree/销毁二t叉?树，?递y归调

38、用?。如?果?头指?针?为a空?，?返回?。调用?左右孩子，?如?果?左右孩子为a空?，?释放?双?亲。开a始?先判d断?左右孩子是?否?非?空?，?程序很长。经-过y调整?，?最?后判d断?，?使1函数y大大缩?减?了?。int calculate(bitree bt)int l,r;if(!bt-lchild&!bt-rchild)return bt-data-48;l=calculate(bt-lchild);r=calculate(bt-rchild);switch(bt-data)case +: return l+r;case -: return l-r;case *: return

39、 l*r;case /: return l/r;return 0;/calculate/计?算?二t叉?树的?值，?递y归调用?。如?果?左右孩子为a空?，?返回?其?ascii码?-48，?即其?实数y值int restore(bitree bt)if(!bt)return 0;if(bt-data=*|bt-data=/)&(bt-lchild-data=+|bt-lchild-data=-)printf();restore(bt-lchild);printf();elserestore(bt-lchild);visit(bt-data);if(bt-data=*|bt-data=/)&(bt-rchild-data=+|bt-rchild-data=-)printf();restore(bt-rchild);printf();elserestore(bt-rchild);return 0;/restoreint main()int i;bitree s10;for(i=0;ii;printf( (1)请?输?入?扩?展1先序序