陈正宁-2015123349-数据结构第1次实验报告

1、淮海工学院计算机科学系实验报告书课程名： 数据结构 题 目： 线性数据结构试验 班 级： 软嵌151 学 号： 2015123349 姓 名： 陈正宁 评语：成绩： 指导教师： 批阅时间： 年 月 日 数据结构 实验报告 - 12 -线性表实验报告要求1目的与要求:1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现； 4）熟练掌握线性表的链式存储结构的基本操作算法实现;5）掌握线性表在实际问题中的应用和基本编程技巧;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果

2、）；8）积极开展实验组组内交流和辅导，严禁直接复制和剽窃他人实验成果，一旦发现严肃处理；9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操作时调试和运行。2实验内容或题目（在一个主程序中实现全部题目内容）一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印/显示出表中元素值）；3）在顺序表中查找第i个元素，并返回其值；4）在顺序表第i个元素之前插入一已知元素；5）在顺序

3、表中删除第i个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型char。按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中第i个结点之前插入一个新结点；6）在线性表中删除第i个结点；7）计算链表的

4、长度。3实验步骤与源程序第一题：顺序表/顺序结构#include <stdio.h>#include <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 25 typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList

5、;/顺序表查找操作int GetData(SeqList *L,int i)return L->elemi-1;/ 插入运算/*在顺序表L中第i个数据元素之前插入一个元素e。 插入前表长n=L->last+1，i的合法取值范围是 1iL->last+2 */int InsList(SeqList *L,int i,ElemType e) int k;if(i<1) | (i>L->last+2) /*首先判断插入位置是否合法*/printf("插入位置i值不合法");return(ERROR);if(L->last>= MAX

6、SIZE-1)printf("表已满无法插入");return(ERROR);for(k=L->last;k>=i-1;k-) /*为插入元素而移动位置*/L->elemk+1=L->elemk;L->elemi-1=e; /*在C语言数组中，第i个元素的下标为i-1*/L->last+;return (OK);/删除运算int DelList(SeqList *L,int i,ElemType *e)/*在顺序表L中删除第i个数据元素，并用指针参数e返回其值。i的合法取值为1iL.last+1 */ int k;if(i<1)|(

7、i>L->last+1) printf("删除位置不合法!");return(ERROR);*e = L->elemi-1; /* 将删除的元素存放到e所指向的变量中*/for(k=i; i<=L->last; k+)L->elemk-1 = L->elemk; /*将后面的元素依次前移*/L->last-;return(OK);void main()SeqList *l;int p,r,t,sum=0;int *q;int i;l = (SeqList*)malloc(sizeof(SeqList);q = (int*)ma

8、lloc(sizeof(int);printf("请输入线性表的长度:");scanf("%d",&r);l->last = r-1;printf("请输入线性表的各元素值:n");for(i=0; i<=l->last; i+)scanf("%d",&l->elemi);printf("该结果如下所示:n");for(i=0;i<=l->last;i+)sum=sum+l->elemi;printf("n以上元素之和是:&qu

9、ot;);printf("%dn",sum);for(i=0; i<=l->last; i+)printf("%dt",l->elemi);printf("n请输入要查找的位置：n");scanf("%d",&p);printf("查找的元素是：%dn",GetData(l,p);printf("n请输入要插入的元素所在位置:n");scanf("%d",&t);printf("n请输入要插入的元素:n"

10、;);scanf("%d",&p);InsList(l,t,p);printf("n插入后所有元素是:n");for(i=0; i<=l->last; i+)printf("%dt",l->elemi);printf("n请输入要删除的元素位置:n");scanf("%d",&p);DelList(l,p,q);printf("删除的元素值为:%dn",*q);第二题：链表/链表结构#include <stdio.h>#inclu

11、de <stdlib.h>#include <malloc.h>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;typedef struct Node /结点类型定义 ElemType data;struct Node *next;Node, *LinkList; #include "common.h"#include "SeqList.h"/ 链表创建（头插法）void CreateFromHead(LinkList L)

12、 Node *s;char c;int flag=1; while(flag) /* flag初值为1，当输入"$"时，置flag为0，建表结束*/c=getchar(); if(c!='$')s=(Node*)malloc(sizeof(Node); /*建立新结点s*/s->data=c;s->next=L->next;/*将s结点插入表头*/L->next=s;elseflag=0;void Show(LinkList l)Node *p;p=l->next;printf("链表的结构为:n");whi

13、le(p!=NULL)printf("%c ",p->data);p=p->next;/ 链表插入int InsList(LinkList L,int i,ElemType e)/*在带头结点的单链表L中第i个位置插入值为e的新结点s*/ Node *pre,*s;int k;pre=L; k=0; /*从"头"开始，查找第i-1个结点*/while(pre!=NULL&&k<i-1) /*表未查完且未查到第i-1个时重复，找到pre指向第i-1个*/ pre=pre->next;k=k+1; /*查找第i-1结点

14、*/if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ printf("插入位置不合理!");return ERROR;s=(Node*)malloc(sizeof(Node); /*申请一个新的结点S */s->data=e; /*值e置入s的数据域*/s->next=pre->next;/*修改指针，完成插入操作*/pre->next=s;return OK;/链表删除int DelList(LinkList L,int i)/在带头结点的单链表L中删除第i个元素，并将删除的元素保存到变量*e中Node *p

15、;int j=0;p=L;if(i<1)printf("对不起，删除的位置不合法！");return ERROR;elsewhile(p->next!=NULL&&j<i)p=p->next;j+;if(p->next=NULL)printf("对不起，删除的位置不合法！");return ERROR;p->next=p->next->next;/链表查找char Find(LinkList l,int i)/*在带头结点的单链表L中查找第i个结点,若找到（1<=i<=n),则返

16、回元素值，否则返回FALSE*/Node *p;char s;int j=1; /从头结点开始扫描p=l->next;while(p!=NULL&&j<i)p=p->next;j+;if(p!=NULL)s=p->data; /找到了下一个结点,并输出该元素return (s);elsereturn ERROR;/没找到该结点/ 求链表长度int ListLength(LinkList L)/*本算法是用来求带头结点的单链表的长度*/Node *p;p=L->next;int j=0; /用于存放单链表的长度while(p!=NULL)j+;p=p

17、->next;return j;void main()LinkList l;int n,a;Node *p;ElemType r;l=(Node*)malloc(sizeof(Node);l->next=NULL;printf("用头插法建立单链表,请输入链表数据,以$结束!n");CreateFromHead(l);Show(l);printf("n请输入要查找元素的位置:");scanf("%d",&a);printf("n该元素是:");printf("%c",Find(l,a);printf("n请输入要插入的元素:");scanf(" %c",&r);printf("请输入要插入元素的位置:");scanf("%d",&a);InsList(l,a,r);Show(l);printf("n请输入要删除元素的位置:");scanf("%d",&a);DelList(l,a-1);Show(l);printf("n链表长度为:");printf("