数据结构上机实验报告-单链表的实现.doc

华东交通大学 软件学院上机/实验报告册专 业_班 级_姓 名_课程名称_教 师_学 期_软件学院上机实验报告备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。实验题目： 单链表的实现实验目的： 1.掌握单链表的逻辑结构 2.掌握单链表的存储结构和结构特点 3.掌握单链表基本操作的实现和指针的操作 4.了解单链表基本操作的效率和特点实验要求： 1.线性表的抽象数据类型 2. 单链表存储结构的c+语言定义 3. 单链表基本操作的实现：初始化销毁创建获取元素插入删除 4.单链表的使用 5.实验结果实验内容：1. 线性表的抽象数据类型adt 线性表（list）data 线性表的数据对象集合为a1，a2,an，每个元素的类型均为datatype。其中，除第一个元素a1外，每一个元素有且只有一个直接前驱元素，除了最后一个元素外，每一个元素有且只有一个直接后继元素。数据元素之间的关系是一对一的关系。operation initlist（*l）： 初始化操作，建立一个空的线性表l。 listempty（l）： 若线性表为空，返回ture，否则返回false。 clearlist（*l）： 将线性表清空。 getelem（l,i,*e）: 将线性表l中的第i个元素值返回给e。 locateelem（l,e）： 在线性表l中查找与给定值e相等的元素，如果查找成功，返回该元素在表中序号表示成功；否则，返回0表示失败。2. 单链表存储结构的c+定义： /*线性表的单链表存储结构*/ typedef struct node elemtype data; struct node *next; node; node *linklist; /*定义linklist*/ 3.单链表基本操作的实现：1 初始化：initlist(*l)l=(linklist)malloc(sizeof(linklist)l-next=nullreturn l;2 销毁：/*初始条件：线性表l已存在；操作结果：将l重置为空表*/status clearlist (linklist *l) linklist p,q; p=(*l)-next; while (p) q=p-next; free(p); p=q; (*l)-next=null; return ok;3 创建：/*随机产生n个元素的值，建立带头结点的单链表l（头插法）*/void createlisthead (linklist *l,int n)linklist p; int i; srand(time(0); *l=(linklist)malloc(sizeof(node); (*l)-next=null; for(i=0,idata=rand( )%100+1; p-next=(*l)-next; (*l)-next=p; 4 获取元素：/*初始条件：顺序线性表l已存在，1ilistlength(l)*/*操作结果：用e返回l中第i个数据元素的值*/status getelem(linklist l,int i,elemtype *e)int j; linklist p; p=l-next; j=1; while(!p=null&jnext; +j; if (!p |ji) return error; *e=p-data; return ok;5 插入：/*初始条件:线性表l已存在，1ilistlength(l)*/*操作结果：在l中第i个位置之前插入新的数据元素e，l长度加1*/status listinsert(linklist *l,int i,elemtype e)int j; linklist p,s; p=*l j=1; while(p&jnext; +j; if (!p |ji) return error; s=(linklist)malloc(sizeof(node); s-data=e; s-next=p-next; p-next=s; return ok;6 删除：/*初始条件：线性表l已存在，1ilistlength(l)*/*操作结果：删除l的第i个数据元素，并用e返回其值，l长度减1*/status listdelete (linklist *l,int i,elemtype *e)int j; linklist p, q; p=*l; j=1; while (p-next|ji ) p=p-next; +j; if (! (p-next) |ji ) return error; q=p-next; p-next=q-next; *e=q-data; free(q); return ok; 4.单链表的应用本应用为设计了一个学生成绩管理系统源代码如下：/简单成绩管理系统。#include#include#includeusing namespace std;struct studentstrint stuno;char name20;int score; /这里假设为整型，其实为实数比较妥当。;typedef struct linkstruct studentstr data;struct link * next;linklist;int linklistlen(linklist * head) /返回链表长度，这样可以很容易计算学生编号。int len =0;linklist * p =null;p = head-next;while(p)len+;p=p-next;return len;linklist * createlinklist(linklist *head)head = new linklist;head-data.stuno = -1;head-next = null;return head;int calcstuno(linklist *head)return 1001+linklistlen(head); /设置学号的一个起始值。void insertlinklist(linklist *head,char * name,int score)linklist *p = null;linklist *q = null;p= new linklist;p-data.stuno = calcstuno(head);strcpy(p-d,name);p-data.score = score;p-next = null;q=head;while(q-next)q = q-next;q-next = p;int menu()cout*endl;cout学生成绩管理系统endl;cout*endl;cout*endl;cout*1-输入数据*endl;cout*2-查询成绩*endl;cout*3-修改成绩*endl;cout*4-输出所有学生成绩*endl;cout*5-删除某个学生成绩*endl;cout*6-统计及格和优秀人数*endl;cout*7-平均成绩*endl;cout*8-退出系统*endl;cout*endl;int innum;while(1)cout请输入你的选择：innum;cin.get();if(innum = 1 & innum = 8)break;elsecout输入有误！endl; return innum;void inputdata(linklist *head) /输入成绩 int score; char name20; cout请输入姓名：name; cout请输入成绩：score; insertlinklist(head,name,score);void searchscore(linklist *head) /查询成绩。 int stuno; cout请输入编号：stuno; linklist * p =null; p =head-next; while(p & p-data.stuno != stuno) p = p-next; if(!p) coutno result!data.stuno = stuno) coutstuno name score endl; coutdata.stuno d data.scoreendl; void modifyscore(linklist *head) /修改成绩。 int stuno; cout请输入编号：stuno; cin.get(); linklist * p =null; p =head-next; while(p & p-data.stuno != stuno) p = p-next; if(!p) coutno result!data.stuno = stuno) int score; cout请输入成绩：score; cin.get(); p-data.score = score; cout改后的信息：endl; coutstuno name score endl; coutdata.stuno d data.scorenext; coutstuno name score endl; while(p) coutdata.stuno d data.scorenext; void remove(linklist *head) /删除某个学生成绩。int stuno; cout请输入编号：stuno; cin.get(); linklist *p = null; linklist *q = null; p=head-next; while(p & p-data.stuno != stuno) q=p; p = p-next; if(!p) coutno finding!data.stuno = stuno) /q-next=p-next;delete p; void count(linklist *head) /统计及格和优秀成绩人数。 linklist *p = null; p=head-next; int jige = 0; int youxiu = 0; while(p) if(p-data.score = 60) jige+; if(p-data.score =90) /假设大于等于90为优秀。 youxiu+; p = p-next; cout及格人数为：jigeendl; cout优秀人数为：youxiunext;int sum=0; while(p) sum+=p-data.score; p = p-next; float aver=sum/linklistlen(head); cout平均成绩为：averendl;void exitsys() /退出系统。char temp; couttemp; cin.get(); if(temp = y | temp =y) coutexit success!n; couttop=maxsize-1) /*栈满*/ return error; s-top+; /*栈顶指针增加一*/ s-datas-top=e; /*将新插入元素赋值给栈顶空间*/ return ok;2) 对于出栈操作pop，代码如下：/*若栈不空，则删除s的栈顶元素，用e返回其值，并返回ok；否则返回error*/status pop （sqstack *s，selemtype *e）if(s-top=-1) return erroe;*e=s-datas-top;s-top-;return ok;5. 栈的应用#include#include#define stack_init_size 500/栈的存储结构#define stackincrement 100typedef struct stackchar *base;char *top;int stacksize;stack;void push(stack &s,char e);void init(stack &s);void destroy(stack &s);char gettop(stack s,char &e);char pop(stack &s, char &e);char operation(stack s1,stack s2);int suanfu(char c);char precede(char x,char y);char operate(char x,char z,char y);void init(stack &s)s.base=new char500;if(!s.base) abort();s.top=s.base;s.stacksize=stack_init_size;void destroy(stack &s)int i;i=s.top-s.base;for(;i=s.stacksize)/ the stack is full filleds.base=(char *)realloc(s.base,(s.stacksize+stackincrement)*sizeof(char);if(!s.base) abort();s.top=s.stacksize+s.base;s.stacksize=s.stacksize+stackincrement;*s.top+=e;int suanfu(char c)if(c=*)return 1;else if(c=/)return 1;else if(c=-)return 1;else if(c=+)return 1;else if(c=()return 1;else if(c=)return 1;else if(c=#)return 1;else return 0;char precede(char x,char y) int i,j; int form77=1,1,-1,-1,-1,1,1,1,1,-1,-1,-1,1,1,1,1,1,1,-1,1,1,1,1,1,1,-1,1,1,-1,-1,-1,-1,-1,0,2,1,1,1,1,2,1,1,-1,-1,-1,-1,-1,2,0; switch(x) case +:i=0;break; case -:i=1;break; case *:i=2;break; case /:i=3;break; case (:i=4;break; case ):i=5;break; case #:i=6;break; switch(y) case +:j=0;break; case -:j=1;break; case *:j=2;break; case /:j=3;break; case (:j=4;break; case ):j=5;break; case #:j=6;break; if(formij=1) return ; else if(formij=-1) return ; else return =;char operate(char x,char z,char y)int a=x-0,b=y-0; switch(z) case +:return a+b; case -:return a-b; case *:return a*b; case /:return a/b;char operation(stack s1,stack s2)/s1 为运算符 栈；s2为 运算数栈；init(s1); push(s1,#);init(s2);cout请输入算式：c;char e;char l;char q;char u1;while(c!=#|gettop(s1,e)!=#)if(!suanfu(c)/判断是否为运算符push(s2,c); cinc;elseu1=precede(gettop(s1,l),c);switch(precede(gettop(s1,l),c)case c;break;case=:pop(s1,q);cinc;break;case:char v;char y,d;pop(s1,v);pop(s2,y);pop(s2,d);int a1=operate(d,v,y);/知道了是在这里出现的错误。第一次计算出的值在存到s2里时，类型出了问题/存储的时候在后面加了一个，让出来的数字变了大小push(s2,a1+0x30);/整形变字符型 在整形数上加0x30就可以了break;char r;return gettop(s2,r);void main()stack s1,s2;int u;u=operation(s1,s2);cout(char)u0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i 维下标，aj1j2jnelemset, ji=0, ,bi-1, i=1,2, ,n数据关系：r=r1,r2, ,rnri=|0jkbk-1,1kn且ki, 0jibi-2,aj1.ji.jn,aj1ji+1jnd, i=2, ,n 基本操作： initarray( &a, n, bound1, , boundn ) 操作结果：若维数n和各维长度合法，则构造相应的数组a，并返回ok。 destroyarray( &a ) 操作结果：销毁数组a。 value( a, &e, index1, , indexn ) 初始条件：a是n维数组，e为元素变量，随后是n个下标值。 操作结果：若各下标不越界，则e赋值为所指定的a的元素值，并返回ok。 assign( &a, e, index1, , indexn ) 初始条件：a是n维数组，e为元素变量，随后是n个下标值。 操作结果：若下标不越界，则将e的值赋给所指定的a的元素，并返回ok。adt array 2.稀疏矩阵的抽象数据类型:adt sparsematrix 数据对象：d=aij | i=1,2,m; j=1,2,.,n;aijelemset, m和n分别称为矩阵的行数和列数。 数据关系：r=row,col row= | 1=i=m, 1=j=n-1 col= | 1=i=m-1, 1=j=n 基本操作： createsmatrix(&m)； 操作结果：创建稀疏矩阵m。 destroysmatrix(&m)； 初始条件：稀疏矩阵m存在。 操作结果：销毁稀疏矩阵m。 printsmatrix(m)； 初始条件：稀疏矩阵m存在。 操作结果：输出稀疏矩阵m。 copysmatrix(m，t)； 初始条件：稀疏矩阵m存在。 操作结果：由稀疏矩阵m复制得到t。 addsmatrix(m，n，&q)； 初始条件：稀疏矩阵m与n的行数和列数对应相等 操作结果：求稀疏矩阵的和q=m+n。 subtmatrix(m，n，&q)； 初始条件：稀疏矩阵m与n的行数和列数对应相等 操作结果：求稀疏矩阵的差q=m-n。 multsmatrix(m，n，q)； 初始条件：稀疏矩阵m的列数等于n的行数。 操作结果：求稀疏矩阵乘积q=m*n。 transposesmatrix(m，t)； 初始条件：稀疏矩阵m存在。 操作结果：求稀疏矩阵m的转置矩阵t。 adt sparsematrix稀疏矩阵的应用:编写程序实现矩阵的基本的加法、减法、成法运算，代码如下：#includeusing namespace std;class matrixprivate: int row,col; double *mx;public: matrix() matrix(); matrix(matrix &m); matrix(int n,int m); friend matrix operator*(matrix &,matrix &); friend istream & operator (istream &,matrix &); friend ostream & operator (ostream &,matrix &); friend matrix operator+(matrix &,matrix &); friend matrix operator-(matrix &,matrix &); friend matrix operator!(matrix &);matrix:matrix(matrix &m)int i,j;row=m.row;col=m.col;mx=new double *row;for(i=0;irow;i+) mxi=new doublecol; for(i=0;im.row;i+) for(j=0;jm.col;j+) mxij=m.mxij;matrix:matrix()int i; for(i=0;irow;i+) delete mxi; delete mx;matrix:matrix(int n,int m) int i,j; row=n; col=m; mx=new double *row;for(i=0;irow;i+) mxi=new doublecol;for(i=0;irow;i+) for(j=0;j(istream &input,matrix &m) int i,j;for(i=0;im.row;i+) for(j=0;jm.mxij;return input;matrix operator+(matrix &m1,matrix &m2) matrix m(m1.row,m1.col); int i,j; for(i=0;im1.row;i+) for(j=0;jm1.col;j+) m.mxij=m1.mxij+m2.mxij; return m;matrix operator*(matrix &m1,matrix &m2)if(m1.col!=m2.row)throw 1;matrix m(m1.row,m2.col);int i,j,t=0,s,l=0; for(i=0;im.col*m.row;i+) for(j=0,s=0;jm2.row,sm1.col;j+,s+) m.mxtl+=m1.mxtj*m2.mxsl; if(i+1)%m.col=0) t+;l=0; else l+; return m;ostream& operator(ostream &output,matrix &m) int i,j; for(i=0;im.row;i+) for(j=0;jm.col;j+) outputm.mxijt; if(j=m.col-1) coutendl; return output;matrix operator-(matrix &m1,matrix &m2) matrix m(m1.row,m1.col); int i,j; for(i=0;im1.row;i+) for(j=0;jm1.col;j+) m.mxij=m1.mxij-m2.mxij; return m;matrix operator!(matrix &m1)int i,j;matrix m(m1.col,m1.row); for(i=0;im1.row;i+) for(j=0;jm1.col;j+) m.mxji=m1.mxij;return m; int main() int n,m; int n1,n2;cout*加法与减法*endl; coutnm; matrix m1(n,m); cout输入第一个矩阵：m1; matrix m2(n,m); cout输入第二个矩阵：m2; matrix m3(m1+m2); cout两矩阵相加后：endl; coutm3endl; cout两矩阵相减后：endl; matrix m31(m1-m2); coutm31endl; cout*乘法*endl;coutnm;matrix m4(n,m);cout输入第一个矩阵：m4;coutn1n2;matrix m5(n1,n2);cout输入第二个矩阵：m5;try matrix m6(m4*m5); cout两矩阵相乘后：endl; coutm6endl; catch(int) cout第一个矩阵的列数不等于第二个矩阵的行数，所以不能相乘！endl; cout*转置*endl;coutnm;matrix m7(n,m);cout输入一个矩阵：m7;matrix m8(!m7);cout转置后：endl;coutm8;return 0;稀疏矩阵的快速转置:#includeusing namespace std;class matrixpublic: int data100100; int m,n;typedef int spmatrix1003;voi