数据结构上机实验报告单链表的实现.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.单链表基本操作的实现： 初始化：InitList(*L)L=(LinkList)malloc(sizeof(LinkList)L->next=NULLreturn L; 销毁：/*初始条件：线性表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; 创建：/*随机产生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,i<n,i+) p=(LinkList)malloc(sizeof(Node); p->data=rand( )%100+1; p->next=(*L)->next; (*L)->next=p; 获取元素：/*初始条件：顺序线性表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&&j<i) p=p->next; +j; if (!p |j>i) return ERROR; *e=p->data; return OK; 插入：/*初始条件:线性表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&&j<i) p=p->next; +j; If (!p |j>i) return ERROR; s=(LinkList)malloc(sizeof(Node); s->data=e; s->next=p->next; p->next=s; return OK; 删除：/*初始条件：线性表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|j>i ) p=p->next; +j; If (! (p->next) |j>i ) return ERROR; q=p->next; p->next=q->next; *e=q->data; Free(q); return OK; 4.单链表的应用本应用为设计了一个学生成绩管理系统源代码如下：/简单成绩管理系统。#include<iostream>#include<string.h>#include<stdlib.h>using 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->Data.name,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<<"请输入你的选择："<<endl;cin>>innum;cin.get();if(innum >= 1 && innum <= 8)break;elsecout<<"输入有误！"<<endl; return innum;void inputData(LinkList *head) /输入成绩 int score; char name20; cout<<"请输入姓名："<<endl; cin>>name; cout<<"请输入成绩："<<endl; cin>>score; insertLinkList(head,name,score);void searchScore(LinkList *head) /查询成绩。 int stuNo; cout<<"请输入编号："<<endl; cin>>stuNo; LinkList * p =NULL; p =head->next; while(p && p->Data.stuNo != stuNo) p = p->next; if(!p) cout<<"NO RESULT!"<<endl; else if(p->Data.stuNo = stuNo) cout<<"stuNO "<<"name "<<"score "<<endl; cout<<p->Data.stuNo<<" "<<p->Data.name<<" "<<p->Data.score<<endl; void modifyScore(LinkList *head) /修改成绩。 int stuNo; cout<<"请输入编号："<<endl; cin>>stuNo; cin.get(); LinkList * p =NULL; p =head->next; while(p && p->Data.stuNo != stuNo) p = p->next; if(!p) cout<<"NO RESULT!"<<endl; else if(p->Data.stuNo = stuNo) int score; cout<<"请输入成绩："<<endl; cin>>score; cin.get(); p->Data.score = score; cout<<"改后的信息："<<endl; cout<<"stuNO "<<"name "<<"score "<<endl; cout<<p->Data.stuNo<<" "<<p->Data.name<<" "<<p->Data.score<<endl; void outputData(LinkList *head) /打印成绩。 LinkList * p = NULL; p=head->next; cout<<"stuNO "<<"name "<<"score "<<endl; while(p) cout<<p->Data.stuNo<<" "<<p->Data.name<<" "<<p->Data.score<<endl; p = p->next; void remove(LinkList *head) /删除某个学生成绩。int stuNo; cout<<"请输入编号："<<endl; cin>>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) cout<<"NO finding!"<<endl; else if(p->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<<"及格人数为："<<jige<<endl; cout<<"优秀人数为："<<youxiu<<endl;void average(LinkList *head) /计算平均成绩LinkList *p = NULL; p=head->next;int sum=0; while(p) sum+=p->Data.score; p = p->next; float aver=sum/linkListLen(head); cout<<"平均成绩为："<<aver<<endl;void exitSys() /退出系统。char temp; cout<<"If you want to exit?(y/n)n" cin>>temp; cin.get(); if(temp = 'y' | temp ='Y') cout<<"exit success!n" cout<<"BYE BYEn" exit(0); else return; int main()int selectnum;LinkList *head = NULL;head = createLinkList(head);while(1)selectnum = menu();switch(selectnum)case 1:inputData(head);break;case 2:searchScore(head);break;case 3:modifyScore(head);break;case 4:outputData(head);break;case 5:remove(head);break;case 6:count(head);break;case 7:average(head);break;case 8:exitSys();break;5.实验结果：实验总结： 单链表相对于顺序链表，插入和删除更加方便，而且不需要考虑存储空间的大小问题，但是频繁的读取和数据的查找不甚便捷。软件学院上机实验报告备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。实验题目： 栈的应用实验目的： 1.了解栈的性质2.掌握栈的顺存储结构3.掌握栈的实际应用 4.学会使用递归方式编程实验要求： 1.栈的抽象数据类型 2.举一个栈的后进先出的例子 3.顺序栈的定义 4.顺序栈基本操作的实现 5.栈的应用 6.递归的使用 7.实验结果实验内容：1. 栈的抽象数据类型ADT 栈（stack）Data 同线性表，元素具有相同的类型，是相邻元素具有前驱和后继关系。OperationInitStack（*S）：初始化操作，建立一个空栈S。DestroyStack（*S）：若栈存在，则销毁它。ClearStack（*S）：将栈清空。StackEmpty（S）：若栈为空，返回ture，否则返回false。GetTop（S,*e）：若栈存在且非空，用e返回S的栈顶元素。Push（*S，e）：若栈S存在，插入新元素e到栈S中并成为栈顶元素。Pop（*S，*e）：删除栈S中栈顶元素，并用e返回其值。StackLength（S）：返回栈S的元素个数。endADT2. 举一个栈的后进先出的例子例如弹夹式手枪，子弹先填装，后出来；后填装，先出来。3. 顺序栈的定义Typedef int SElemType; /*SElemType 类型根据实际情况而定，这里假设为int*/ SElemType dataMAXSIZE; Int top; /*用于栈顶指针*/SqStack;4. 顺序栈基本操作的实现1) 对于进展操作Push，其代码如下： /*插入元素e为新的栈顶元素*/Status Push（SqStack *S, SElemType e） If(S->top=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<iostream.h>#include<stdlib.h>#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<0;i-)delete -S.top;/删除的必须是指针delete S.top;delete S.base;char GetTop(Stack S,char &e)if(S.top=S.base) abort();e=*-S.top;return e;char Pop(Stack &S, char &e)if(S.top=S.base) abort();e=*-S.top;return e;void Push(Stack &S,char e)if(S.top-S.base>=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<<"请输入算式："<<endl;char c; cin>>c;char e;char l;char q;char u1;while(c!='#'|GetTop(s1,e)!='#')if(!suanfu(c)/判断是否为运算符Push(s2,c); cin>>c;elseu1=Precede(GetTop(s1,l),c);switch(Precede(GetTop(s1,l),c)case '<':Push(s1,c);cin>>c;break;case'=':Pop(s1,q);cin>>c;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)u<<endl;system("pause");6. 实验结果实验总结: 通过实验明白了栈的“后进先出”的特点，栈强调在栈顶的操作，而不是元素的位序。栈的优点就是读取速度快，而且数据可以共享；缺点就是存在于栈中的数据大小及周期必须是确定的，缺乏灵活性。而通过对递归算法的应用，体会到了递归的便利，递归使算法的描述简洁而且易于理解，十分有效的解决了一大类问题，但是在使用递归算法的同时还要注意必须有一个明确的递归出口。软件学院上机实验报告备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。实验题目：矩阵的存储压缩实验要求：1.特殊矩阵的压缩存储2.稀疏矩阵的压缩存储3.稀疏矩阵的快速转质实验内容：1.数组的抽象数据类型ADT Array数据对象：D=aj1j2jn|n(>0)称为数组的维数，bi是数组第i维的长度，ji是数组元素的第i 维下标，aj1j2jnElemSet, ji=0, ,bi-1, i=1,2, ,n数据关系：R=R1,R2, ,RnRi=<aj1.ji.jn,aj1ji+1jn>|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=<ai,j , ai,j+1> | 1<=i<=m, 1<=j<=n-1 Col= <ai,j , ai+1,j> | 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稀疏矩阵的应用:编写程序实现矩阵的基本的加法、减法、成法运算，代码如下：#include<iostream>using 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