淮海工学院计算机科学系实验报告书课程名：《数据结构》题目：线性数据结构试验班级：软嵌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 OK 1#define ERROR 0#define TURE 1#define FALSE 0#define ElemType int#define MAXSIZE 25typedef struct{ElemType elem[MAXSIZE];int last;}SeqList;int GetData(SeqList *L,int i){return L->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; //线性表的长度int t; //插入的元素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 application. //#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,ElemType e); void Get(LinkList L,int i);void InitList(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);elseprintf("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");elseprintf("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;}int DelList(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++;}return j;}4测试数据与实验结果（可以抓图粘贴）5结果分析与实验体会此次试验所使用的基本概念为上学期的链表的内容，而链表主要是通过结点等跳来跳去，充分利用空间，而且链表，指针通常搭配使用，这增加了理解上的难度，只要有一错错误，整个程序便会出现错误，所以此次试验尽管题目不难，但写起代码非常麻烦，尤其是c语言学得不好的，更会吃力。