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

《数据结构上机实验报告单链表的实现.doc》由会员分享，可在线阅读，更多相关《数据结构上机实验报告单链表的实现.doc（52页珍藏版）》请在三一办公上搜索。

1、华东交通大学 软件学院上机/实验报告册专 业_班 级_姓 名_课程名称_教 师_学 期_软件学院上机实验报告备注：学生应根据实验的要求，设计一个实验过程（包括程序代码、各种定义说明），并根据实验的结论及实验过程中出现的情况（错误、异常等）得出的体会。要求学生每人一台计算机，独立完成实验的全过程。实验题目： 单链表的实现实验目的： 1.掌握单链表的逻辑结构 2.掌握单链表的存储结构和结构特点 3.掌握单链表基本操作的实现和指针的操作 4.了解单链表基本操作的效率和特点实验要求： 1.线性表的抽象数据类型 2. 单链表存储结构的C+语言定义 3. 单链表基本操作的实现：初始化销毁创建获取元素插入删

2、除 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个元素

3、值返回给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

4、已存在；操作结果：将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=

5、0,idata=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&jnext; +j; if (!p |ji) return ERROR; *e=p-data; return OK; 插入：/*初始条件:线性表L已存在，1iListLength(L)

6、*/*操作结果：在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; 删除：/*初始条件：线性表L已存在，1iListLength(L)*/*操作结果：删除L的第i个数据元素，并用e返回其值，L长

7、度减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;stru

8、ct 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(LinkLi

9、st *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(

10、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

11、;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; cou

12、t请输入编号：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 Data.name Data.scoreendl; void modifyScore(LinkList *head) /修改成绩。 int stuNo; cout请输入编号：stuNo; cin.get(); LinkList * p =NULL;

13、 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 Data.name Data.scorenext; coutstuNO name score endl; while(p) coutData.stuNo Dat

14、a.name 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) /统计

15、及格和优秀成绩人数。 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平均

16、成绩为：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，SElemT

17、ype *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,c

18、har &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

19、=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

20、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;

21、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,c

22、har 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);

23、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 Ge

24、tTop(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。 Des

25、troyArray( &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;aijEl

26、emset, 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的行数

27、和列数对应相等 操作结果：求稀疏矩阵的和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