线性表数据结构试验.doc

淮海工学院计算机科学系
实验报告书

课程名： 《数据结构》
题 目： 线性表数据结构试验

班 级：
学 号：
姓 名：

评语：

成绩： 指导教师：

批阅时间： 年 月 日

《 数据结构 》实验报告 - 13 -
线性表实验报告要求
1目的与要求:
1）掌握线性表数据结构的基本概念和抽象数据类型描述；
2）熟练掌握线性表数据结构的顺序和链式存储存表示；
3）熟练掌握线性表顺序存储结构的基本操作算法实现；
4）熟练掌握线性表的链式存储结构的基本操作算法实现;
5）掌握线性表在实际问题中的应用和基本编程技巧;
6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；
7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电子（全班同学提交到学委，再统一打包提交给老师）和纸质（每班每次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实验步骤与源程序
一、 顺序表的基本操作实现实验
Common.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

Seqlist.h
#define ElemType int
#define MAXSIZE 25
typedef struct
{
ElemType elem[MAXSIZE];
int last;
}SeqList;
#include "common.h"
#include "seqlist.h"

int Locate(SeqList L, int n)
{
int i=0;
while ((i<L.last&&i!=n))
i++;
if (i<=L.last)
return L.elem[i];
else
return(-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 AddList(SeqList *L)
{
int k,s=0;
for(k=0;k<=L->last;k++)
s=s+L->elem[k];
return s;
}

void main()
{
SeqList l;
int p,q,r,*q1;
int i;
q1=(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("请输入要查找的元素的位置:\n");
scanf("%d",&q);
p=Locate(l,q);
if(p == -1)
printf("在此线性表中没有这样的元素!\n");
else
printf("该位置的元素为:%d\n",p);

printf("请输入要插入的位置:\n");
scanf("%d",&p);
printf("请输入要插入的元素值:\n");
scanf("%d",&q);
InsList(&l,p,q);
for(i=0; i<=l.last; i++)
{
printf("%d ",l.elem[i]);
}
printf("\n");

printf("请输入要删除的元素位置:\n");
scanf("%d",&p);
DelList(&l,p,&q);
printf("删除的元素值为:%d\n",q);
printf("删除后的元素序列:\n");
for(i=0; i<=l.last; i++)
printf(" %d ",l.elem[i]);
printf("\n");
printf("剩余数字之和为：");
printf(" \n %d \n",AddList(&l));
}

二、链表（带头结点）基本操作实验
Common.h
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE

Linklist.h
typedef char ElemType;
typedef struct Node
{
ElemType data;
struct Node * next;
}Node, *LinkList;

#include <stdio.h>
#include <stdlib.h>

#define ElemType char
typedef struct Node
{
ElemType data;
struct Node * next;
}Node, *LinkList;

LinkList CreateFromHead()
{
LinkList L;
Node *s;
char c;
int flag=1,i=1;
L=(LinkList)malloc(sizeof(Node));
L->next=NULL;
while(flag&&i<=10)
{
c=getchar();
if(c!='$')
{
s=(Node*)malloc(sizeof(Node));
s->data=c;
s->next=L->next;
L->next=s;
}
else
flag=0;
i++;

}
return L;
}

Node *search(LinkList L,int i)
{
int j=0;
Node *p;
p=L;
while(p->next!=NULL&&j<i)
{
p=p->next;
j++;
}
if(i==j) return p;
else return NULL;
}

Node *locate(LinkList L,ElemType key)
{
Node *p;
p=L->next;

while(p!=NULL)
{
if(p->data!=key)
p=p->next;
else break;
}
return p;
}
void InsList(LinkList L,int i,ElemType e)
{
Node *p,*s;
int k;
p=L;
k=0;
while(p!=NULL&&k<i-1)
{
p=p->next;
k=k+1;
}
if(k!=i-1)
{
printf("error!");

}
s=(Node *)malloc(sizeof(Node));
s->data=e;
s->next=p->next;
p->next=s;

}

void delLink(LinkList L,int i,ElemType *e)
{
Node *p,*r;
int k;
p=L;
k=0;
while(p->next!=NULL&&k<i-1)
{
p=p->next;
k=k+1;
}
if(k!=i-1)
{
printf("位置不合理");

}
r=p->next;
p->next=p->next->next;
*e=r->data;
free(r);

}

int Listlength(LinkList L)
{
Node *p;
p=L->next;
int j=0;
while(p!=NULL)
{
p=p->next;
j++;
}
return j;
}

void main()
{
LinkList l;
Node *p;
char e;
char a;
int i,n;
printf("用头插法建立单链表,请输入链表数据,以$结束!\n");
l = CreateFromHead();
p = l->next;
printf("输入的字符依次为:");
while(p!=NULL)
{

printf("%c ",p->data);
p=p->next;
}
printf("%c\n");

Node *p1;
printf("请输入要查找的字符的序号:");
scanf("%d",&n);
printf("要查找的字符:\n");
p1=search(l,n);
printf("%c ",p1->data);
printf("%c\n");

printf("插入后的字符:\n");
scanf("%c",&a);
InsList(l,3,'a');
p1=l->next;
while(p1!=NULL)
{
printf("%c ",p1->data);
p1=p1->next;
}
printf("%c\n");

delLink(l,2,&e);
p1=l->next;
printf("删除后的字符为:\n");
while(p1!=NULL)
{
printf("%c ",p1->data);
p1=p1->next;
}
printf("%c\n");

printf("该字符串的长度为:\n");
i=Listlength(l);
printf("%d\n",i);

printf("输入要查找的字符:\n");
scanf("%c",&a);
p1=locate(l,a);
if(p1!=NULL)
{
printf("true");
printf("%c\n");
}
else
{
printf("flase!");
printf("%c\n");
}
}

4测试数据与实验结果（可以抓图粘贴）
一． 顺序表的基本操作实现实验

二、链表（带头结点）基本操作实验

5结果分析与实验体会
这是第一次数据结构实验，我感觉基础还是很重要的，C语言的基础很重要。这次的数据结构试验不是很难，主要是根据书本上的例子改编而成，只要理解书本上的习题和思想，就可以解决这些问题。可是由于一个暑假没有复习C语言，导致做实验时还是有点吃力的。我发现数据结构这门功课对思维能力以及数学能力的要求还是很高的，所以今后还要好好学习数学，不断的提高自己的思维能力以及数学能力。希望老师今后可以严格要求我，使我在这门功课上可以学到更多的知识，真正掌握技术。