淮海工学院计算机科学系实验报告书课程名:《数据结构》题目: 线性数据结构试验班级:软嵌151学号:2015123352姓名: 韩吉线性表实验报告要求1目得与要求:1)掌握线性表数据结构得基本概念与抽象数据类型描述;2)熟练掌握线性表数据结构得顺序与链式存储存表示;3)熟练掌握线性表顺序存储结构得基本操作算法实现;4)熟练掌握线性表得链式存储结构得基本操作算法实现;5)掌握线性表在实际问题中得应用与基本编程技巧;6)按照实验题目要求独立正确地完成实验内容(提交程序清单及相关实验数据与运行结果);7)按照报告格式与内容要求,认真书写实验报告,并于下周周二前统一提交实验报告电子版文档(每次实验全体同学必须提交实验报告电子版,实验报告文档文件命名方式:姓名+学号+数据结构第X次实验报告)提交给学委,而后由学委以班为单位统一打包(包文件名为:软件14X班-数据结构第X次实验报告)用邮件发给老师;提交纸质报告(每班每次收5份,学委安排,保证每学期每个同学至少提交一次)一起提交给老师。
每次提交电子文档时,学委务必统计与上报未交报告人数与具体姓名;凡逾期不交报告者,不再推迟提交,一律按照旷交处理。
8)积极开展实验组组内交流与辅导,严禁直接复制与剽窃她人实验成果,一旦发现严肃处理;9)上实验课前,要求每个同学基本写好程序,并存储在自己得U盘上,用于实验课堂操作时调试与运行.2实验内容或题目(在一个主程序中实现全部题目内容)一、顺序表得基本操作实现实验要求:数据元素类型ElemType取整型int.按照顺序存储结构实现如下算法:1)创建任意整数线性表(即线性表得元素值随机在键盘上输入)得顺序存储结构(即顺序表),长度限定在25之内;2)打印/显示(遍历)该线性表(依次打印/显示出表中元素值);3)在顺序表中查找第i个元素,并返回其值;4)在顺序表第i个元素之前插入一已知元素;5)在顺序表中删除第i个元素;6)求顺序表中所有元素值(整数)之与;二、链表(带头结点)基本操作实验要求:数据元素类型ElemType取字符型char。
按照动态单链表结构实现如下算法:1)按照头插法或尾插法创建一个带头结点得字符型单链表(链表得字符元素从键盘输入),长度限定在10之内;2)打印(遍历)该链表(依次打印出表中元素值,注意字符得输入顺序与链表得结点顺序);3)在链表中查找第i个元素,i合法返回元素值,否则,返回FALSE;4)在链表中查找与一已知字符相同得第一个结点,有则返回TRUE,否则,返回FALSE;5)在链表中第i个结点之前插入一个新结点;6)在线性表中删除第i个结点;7)计算链表得长度。
3实验步骤与源程序#include”stdio、h”#include"stdlib、h”#include"malloc、h"#define OK1#define ERROR 0#define TURE 1#define FALSE 0#defineElemType int#define MAXSIZE 25typedef struct{ﻩElemType elem[MAXSIZE];ﻩintlast;}SeqList;int GetData(SeqList*L,int i){returnL-〉elem[i—1];}int InsList(SeqList *L,int i,ElemType e){int k;if((i〈1)||(i〉L-〉last+2))ﻩ{ﻩprintf("插入位置i值不合法!");ﻩﻩreturn(ERROR);ﻩ}ﻩif(L->last〉=MAXSIZE-1)ﻩ{ﻩprintf(”超出了链表得最大范围,无法插入无法插入!”); ﻩreturn(ERROR);ﻩ}for(k=L—〉last;k〉=i—1;k——)L—〉elem[k+1]=L-〉elem[k];ﻩL-〉elem[i—1]=e;ﻩL->last++;return(OK);}int DelList(SeqList *L,int i,ElemType *e) {int k;ﻩif((i<1)||(i〉L-〉last+1)){ﻩprintf("删除位置不在表中,不合法!”);ﻩreturn(ERROR);ﻩ}*e=L->elem[i—1];ﻩfor(k=i;k〈=L—>last;k++)ﻩﻩL-〉elem[k-1]=L—〉elem[k];L—〉last--;return(OK);}int SumList(SeqList *L){ﻩint sum=0;ﻩfor(int i=0;i〈=L->last;i++)ﻩ{ﻩsum+=L—>elem[i];}ﻩreturn(sum);}void main(){SeqList *l;int p; //要查找得位置ﻩint *q;int r;//线性表得长度ﻩintt;ﻩ//插入得元素ﻩint s;ﻩ//删除得位置ﻩint w;//要插入得位置int i;ﻩl=(SeqList*)malloc(sizeof(SeqList));ﻩq=(int*)malloc(sizeof(int));printf(”请输入线性表得长度:");ﻩscanf(”%d”,&r);l—〉last=r-1;printf("请输入线性表中得各元素值:\n");for(i=0;i〈=l-〉last;i++)ﻩ{ﻩﻩscanf(”%d",&l->elem[i]);}ﻩprintf("线性表中所有元素之与就是:%d\n”,SumList(l));ﻩprintf("请输入要查找得位置:ﻩ");ﻩscanf("%d”,&p);printf("查找得元素就是:%d\n",GetData(l,p));printf(”请输入要插入得位置:");ﻩscanf("%d",&w);printf("插入得元素就是: ”);ﻩscanf(”%d”,&t);ﻩInsList(l,p,t);ﻩprintf(”插入后得线性表:\n”);for(i=0;i<=l-〉last;i++)ﻩ{printf("%d ",l->elem[i]);ﻩ}printf(”\n");ﻩprintf(”请输入要删除得位置:”);scanf("%d”,&s);ﻩDelList(l,s,q);printf("删除得元素值就是:%d\n”,*q);printf("删除后得线性表:\n”);for(i=0;i<=l—〉last;i++){ﻩprintf(”%d ",l-〉elem[i]);ﻩ}}// 数据结构第二题、cpp: Defines the entry point for the console applicati on、//#include 〈stdio、h〉#include <stdlib、h〉#include <malloc、h>#define OK 1#define ERROR 0#define TURE 1#define FALSE 0typedef char ElemType;typedef struct Node{ﻩElemType data;struct Node*next;}Node,*LinkList;void CreateTail(LinkList L);int DelList(LinkList L,int i,ElemTypee);void Get(LinkList L,int i);voidInitList(LinkList *l);int InsList(LinkList L,int i,ElemType e);int ListLength(LinkList L);void Locate(LinkList L,ElemType e);void main(){LinkList k;ﻩint m;ﻩ//要查找得序号ﻩint n;ﻩ//要插入得位置ﻩint t;// 要删除得位置ﻩchar a; //要查找得元素InitList(&k);Node *p;p=k-〉next;printf("用尾插法建立单链表,请输入链表数据,以$结束!\n”);CreateTail(k);while(p!=NULL){ﻩﻩprintf("%c\n”,p—〉data);ﻩp=p—>next;ﻩ}printf("请输入要查找得序号:”);scanf("%d",&m);ﻩprintf("查找到得元素就是:ﻩ");Get(k,m);printf(”\n请输入要查找得元素:");scanf("%c”,&a);Locate(k,a);ﻩprintf("\n请输入要插入得位置: ");ﻩscanf("%d",&n);printf(”插入得元素就是:”);ﻩscanf("%c",&a);ﻩInsList(k,n,a);ﻩprintf("插入后得链表就是: ");p=k—>next;ﻩwhile(p!=NULL){ﻩprintf(”%c ",p—>data);ﻩp=p-〉next;ﻩ}printf("\n请输入要删除得位置:");ﻩscanf(”%d",&t);DelList(k,t,a);printf("删除得元素就是:%c\n",a);ﻩscanf("%c",&a);printf("删除后得链表就是:ﻩ”);ﻩp=k—>next;ﻩwhile(p!=NULL)ﻩ{ﻩprintf(”%c ",p—>data);p=p->next;}ﻩprintf(”\n链表得长度就是:%d\n",ListLength(k)); }void InitList(LinkList *k){ﻩ*k=(LinkList)malloc(sizeof(Node));(*k)->next=NULL;}void CreateTail(LinkList L){ﻩchar c;ﻩNode *r,*s;int flag=1;ﻩr=L;ﻩwhile(flag)ﻩ{ﻩc=getchar();if(c!='$')ﻩﻩ{ﻩﻩs=(Node*)malloc(sizeof(Node));ﻩs—>data=c;ﻩﻩr-〉next=s;ﻩﻩr=s;ﻩ}ﻩelse{ﻩflag=0;ﻩﻩﻩr->next=NULL;ﻩﻩ}ﻩ}}void Get(LinkList L,int i){ﻩint j;ﻩNode *p;p=L;j=0;ﻩwhile(p-〉next!=NULL&&j〈i)ﻩ{ﻩp=p—>next;j++;}if(i==j)ﻩprintf("%c”,p—〉data);ﻩelseﻩprintf("FALSE”);}void Locate(LinkList L,ElemType e){Node *p;ﻩp=L—〉next;ﻩwhile(p!=NULL)ﻩif(p-〉data!=e)ﻩp=p—>next;else break;ﻩif(p->data==e)ﻩﻩﻩprintf("TURE");elseﻩprintf("FALSE");}int InsList(LinkList L,int i,ElemType e){Node *pre,*s;ﻩint k;ﻩpre=L;k=0;while(pre!=NULL&&k〈i-1){ﻩﻩpre=pre->next;ﻩk=k+1;ﻩ}if(k!=i—1){ﻩprintf(”插入位置不合法!");return ERROR;ﻩ}ﻩs=(Node*)malloc(sizeof(Node));s->data=e;s-〉next=pre->next;pre—〉next=s;ﻩreturn OK;}intDelList(LinkList L,int i,ElemType e){Node *p,*r;ﻩint k;ﻩp=L;k=0;ﻩwhile(p!=NULL&&k〈i-1){ﻩp=p->next;k=k+1;ﻩ}ﻩif(k!=i-1)ﻩ{ﻩﻩprintf("删除结点得位置不合法!");ﻩreturn ERROR;ﻩ}ﻩr=p—>next;ﻩp—〉next=p-〉next->next;ﻩe=r->data;ﻩfree(r);ﻩreturn OK;}int ListLength(LinkList L){ﻩNode *p;p=L—〉next;int j=0;ﻩwhile(p!=NULL){ﻩﻩp=p->next;ﻩﻩj++;ﻩ}returnj;}4测试数据与实验结果(可以抓图粘贴)5结果分析与实验体会此次试验所使用得基本概念为上学期得链表得内容,而链表主要就是通过结点等跳来跳去,充分利用空间,而且链表,指针通常搭配使用,这增加了理解上得难度,只要有一错错误,整个程序便会出现错误,所以此次试验尽管题目不难,但写起代码非常麻烦,尤其就是c语言学得不好得,更会吃力。