HUNAN UNIVERSITY
课程实验报告
题目：自组织线性表
学生姓名：
学生学号：
专业班级：
指导老师：
完成日期：
一． 需求分析
输入形式
本程序可从文件中读入一个或多个汉字句子，并用自组织线性表保存，然后从另外一个文件中依次读入要查找的汉字。不对非法输入做处理，假定输入的数据都合法汉字。
输出形式
输出要查找的汉字和查找结果及比较次数，并将输出保存到文件中。
具体格式如下：
要查找的汉字为：
查找成功，比较次数为——。
查找失败，比较次数为——。
程序功能
本程序可读入保存在文件中的汉语句子和要查找的汉字，并用需查找的汉字与汉字句子中的汉字进行查找比较，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。
测试数据
①输入：
一二三四五六七八
需要查找的汉字为：
七九三四
输出：
七 查找成功！查找次数为：8
九 查找失败！查找次数为：9
三 查找成功！查找次数为：3
四 查找成功！查找次数为：4
②输入：
一二三四五六七八
需要查找的汉字为：
五七四二
输出：
五 查找成功！查找次数为：5
七 查找失败！查找次数为：7
四 查找成功！查找次数为：4
二 查找成功！查找次数为：2
③输入：
一二三四五六七八
需要查找的汉字为：
六六二二
输出：
六 查找成功！查找次数为：6
六 查找失败！查找次数为：7
二 查找成功！查找次数为：2
二 查找成功！查找次数为：3
④输入：
一一二二三三四四
需要查找的汉字为：
一二三四
输出：
一 查找成功！查找次数为：1
二 查找失败！查找次数为：3
三 查找成功！查找次数为：5
四 查找成功！查找次数为：7
⑤输入：￥%￥……
二． 概要设计
抽象数据类型
从文件中读入一组汉字集合，用自组织线性表保存。集合中必存在唯一一个第一元素和最后元素。除最后元素在外，元素间均有唯一的后继，除第一元素之外，元素间均有唯一的前驱，所以为数据元素建立一个线性数据关系，因此选用线性表来存储汉语句子。
线性表ADT
数据对象：D＝{ ai | ai ∈字符型, i=1,2,...,n, n≥0 }
数据关系：R1＝{ <ai-1 ,ai >|ai-1 ,ai∈D, i=2,...,n }
基本操作：
void clear(); //初始化变量
bool insert(); //从文件中读入汉字
int getLength(); //获得汉字集合的长度
void print(); //输出读入的记录到屏幕
算法基本思想
根据用户的输入构建相应的线性表，遍历线性表，依次用需查找的汉字与保存了读入汉字的自组织线性表中的每一个汉字作比较，如果相等那么查找到汉字，输出该汉字查找成功，把查找到的汉字在顺序表中用转置法排序，输出查找结果与比较次数。没有查找到则输出查找失败，输出查找的次数。
程序基本流程
该程序主要分为输入模块，转置查找模块和输出模块
（1） 读入模块：从文件中读入一组汉字集合，并保存在自组织线性表中，读入要查找的汉字。
（2） 转置查找模块：依次根据需查找的汉字对汉字线性表遍历一次进行查找，若查找到该汉字，调用转置函数，将该汉字与前一个位置的汉字转置，然后继续查找下一个汉字。
（3） 输出模块：若查找到汉字，则输出到屏幕和文件中查找成功并显示查找次数；若没有查找到该汉字，输出到屏幕和文件中查找不成功并显示查找的次数。
三． 详细设计
物理数据类型
查找函数：汉字占两个字节，所以在查找时要比较该两个字节是否都相同
int search(char a[][2],int size,char c[2])
{ //查找函数
int flag=0，i;
for( i=0;i<size;i++)
if(a[i][0]==c[0] && a[i][1]==c[1])
{ //汉字所占的两位是否同
flag=1;
break;
}
if(flag)
{
if(i>0)
Inverse(a,i,i-1);
return i+1;
}
else
return size; //如果找不到则查找次数为以保存汉字的数
}
倒置函数
void Inverse(char a[][2],int i,int j)
{
char temp=a[i][0];
a[i][0]=a[j][0];
a[j][0]=temp;
temp=a[i][1];
a[i][1]=a[j][1];
a[j][1]=temp;
}
线性表设计：
class Alist
{
private:
int maxsize;
int fence;
Elem *listArray;
public:
Alist(int max)
{maxsize=max;
listArray=new Elem[maxsize];
}
void clear()
{delete[]ListArray;}; //初始化变量
bool insert(const Elem&); //从文件中读入汉字
int getLength(){return fence;}; //获得汉字集合的长度
void print()
{for(int i=0;i<maxsize;i++)
cout<<listArray[i];}; //输出读入的记录到屏幕
算法具体步骤
int i,n,num;
AList L;
fstream file; //声明一个文件file，用于保存查找的结果
L.clear(); //初始化
L.insert(); //读入汉字
L.print(); //输出汉字到屏幕
file.open("查找结果.txt",ios::out);
for(i=0;i<L.getLengthk();i++)
{
num=search(L,i); //返回查找的次数
if(flag)
cout<<”查找成功，查找次数为”<<num;
//查找成功，输出查找的次数
else
cout<<”查找失败，比较次数为：”<<num;
//查找不成功，输出查找的次数
}
算法时空分析
该对于n个汉字，需要插入n次，查找n次，所以算法的时间复杂度为?（n）
输入输出格式
输入：
1. 从文件读入汉字集合到数组中
outfile1.open("test.txt",ios::in); //打开文本文件，打开方式：读入
while(!outfile1.eof()){ //当没有访问到文件末尾，向数组读入汉字
outfile1>>chinese[i];
}
2. 从文件中读入查找汉字：
outfile2.open("test1.txt",ios::in); //打开文本
while(!outfile2.eof())
{
outfile2>>s[i]; //读入要查找的汉字，保存在s[100][3]数组
}
输出：
1. 查找成功
if(flag){
（输出到屏幕）cout<<L.s[i]<<"查找成功！查找次数为："<<num<<endl;
（输出到文件）file<<L.s[i]<<"查找成功！查找次数为："<<num<<endl; }
2. 查找不成功
if(flag=0){
（输出到屏幕）cout<<L.s[i]<<"查找失败！查找次数为："<<num<<endl;
（输出到文件）file<<L.s[i]<<"查找失败！查找次数为："<<num<<endl;
}
函数关系调用
输入
主程序 查找 search（）；
转置 inverse（）
输出 查找成功：输出查找成功以及比较次数
查找失败：输出查找失败以及比较次数
四． 调试分析
在汉字的存储中，曾遇到过问题，以前处理的都是合法字符，后来解决了这个问题。
五． 运行结果
六． 实验心得
通过该实验，我掌握了自组织线性表的构造方法，也理解了转置的基本原理
第二篇：线性表实验报告
天津农学院
数据结构实验报告
学 院: 天津农学院
专 业: 信息管理与信息系统
班 级: 一班
学 号: 1008044203
姓 名: 谢亚峰
一、实验目的——————————————————————————2
二、实验需求——————————————————————————2
2.1输入的形式和输入的范围———————————————————2
2.2输出的形式—————————————————————————2
2.3程序所能达到的功能—————————————————————2
2.4顺序存储测数数据——————————————————————2
2.5链式存储测试数据——————————————————————2
三、概要设计——————————————————————————2
3.1链式存储——————————————————————————2
3.2基本算法——————————————————————————3
四、详细设计——————————————————————————4
4.1顺序存储——————————————————————————4
4.2链式存储——————————————————————————9
五、附录————————————————————————————12
5.1顺序存储结构源代码—————————————————————12
5.2链式存储结构源代码—————————————————————17
六、实验总结——————————————————————————19
.
一、实验目的
编制一个演示顺序和链式存储单链表插入、删除、查找等操作的程序
二、需求分析
本演示程序用visual c++ 6.0环境用c语言编写，完成单链表的生成，任意位置的插入、删除，以及确定某一元素在单链表中的位置。
2.1、 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；查找操作时需要输入元素的值。在所有输入中，元素的值都是整数
2.2、 输出的形式：在所有三种操作中都显示操作是否正确以及操作后单链表的内容。其中删除操作后显示删除的元素的值。
2.3 、程序所能达到的功能：完成单链表的生成、插入、删除。
2.4 、顺序存储测试数据：
A． 生成操作中依次输入1，2，3，9，8，25，30生成一个单链表。
B． 插入操作中输入位置和插入的数：2，22返回插入后的元素。
C． 删除操作中依输入删除位置1将删除第一个元素。
2.5、链式存储测试数据：
A.输入元素个数为5，初始化表输入元素依次为1,2,6,5,12然后输出表中元素。
B.在表中插入元素：位置和数值分别为2,55然后输出表中元素。
C.删除表中元素：输入要删除元素位置3，然后输出删除后元素。
三．概要设计
3.1顺序存储
抽象数据类型线性表的定义：
ADT {
数据对象：D={ai |ai∈ ElemSet,i=1,2,……,n,n≥0}
数据关系：R1={<ai-1,ai>|ai-1,ai∈ D,i=2,……,n}
基本操作：
InitList_sq(&L)
操作结果：构造一个空的线性表L。
ListInsert_sq(&L,i,e)
初始条件：线性表L已存在,1≤i≤L.Length+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
ListDelete_sq(&L,i,&e)
初始条件：线性表L已存在且非空,1≤i≤L.Length。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
input()
} ADT;
3.11本程序包含7个函数：
① 主函数main()
② 初始化单链表函数void input()
③ 显示操作菜单函数menu()
④ 显示单链表内容函数di InitList_sq(sqlist &L)
⑤ 插入元素函数Status ListInsert_sq(sqlist &L,int i,int e)
⑥ 删除元素函数Status ListDelete_sq(sqlist &L,int i,int &e)
3.2链式存储结构：
3.21基本算法：
Status InitList_ Sq(SqList &L)
Status ListInsert_ Sq(SqList &L, int i, Elemtype e){
if(i<1||i>L.length+1) return ERROR;
q=&(L.elem[i-1]);
for(p=&(L.elem[L.length-1]); p>=q; --p)
*(p+1)=*p;
*q=e;
++l.length;
return OK;
}//ListInsert_ Sq;
Status ListDelete_ Sq(SqList &L, int i, Elemtype e){
if(i<1||i>L.length+1) return ERROR;
p=&(L.elem[i-1]);
e=*p
q=L.elem+L.length-1;
for(++p;p<=q;++p)
*(p-1)=*p;
--L.length;
return OK;
}//ListDelete_ Sq;
四．详细设计
4.1顺序存储
4.11抽象数据类型线性表顺序存储结构的表示和实现
//线性表结构类型
#define LIST_INIT_SIZE 100//线性表存储空间的初始分量
#define LISTINCREMENT 10//线性表存储空间的分配增量
typedef struct
{
elemtype *elem;//存储空间基址
int length;//当前线性表的长度
int listsize;//当前分配的存储容量（以sizeof(elemtype)为单位）
}sqlist;
//建立线性表
Status InitList_sq(sqlist &L)
{//构造一个空的线性表
L.elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype));
if(!L.elem) exit(OVERFLOW);//存储分配失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
return OK;
}//InitList_sq
//在线性表指定位置插入指定元素
Status ListInsert_sq(sqlist &L,int i,int e)
{ //在线性表L中第i个位置前插入新的元素e
//i的合法值1<=i<=L.length+1
if(i<1||i>L.length+1) return ERROR;//i值不合法
if(L.length>=L.listsize)//当存储空间已满，增加分配
{
newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase) exit(OVERFLOW);//存储分配失败
L.elem=newbase; //新基址
L.listsize+=LISTINCREMENT; //增加存储容量
}
q=&(L.elem[i-1]); //q为插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p) *(p+1)=*p; //插入位置及之后的元素后移
*q=e; //插入e
++L.length;//表长增加1
return OK;
}//ListInsert_sq
//在线性表指定位置删除元素
Status ListDelete_sq(sqlist &L,int i,int &e)
{ //在顺序表L中删除第i个元素,并用e返回其值
//i的合法值1<=i<=L.length
if(i<1||i>L.length) return ERROR;//i值不合法
p=&(L.elem[i-1]);//p为被删除元素的位置
e=*p; //被删除元素复制给e
q=L.elem+L.length-1;//表尾元素的位置
for(++p;p<=q+1;++p)//被删除元素之后的元素前移
*(p-1)=*p;
--L.length;//线性表长度减1
return OK;
}//ListDelete_sq
4.12主函数的伪码算法
void main()//主函数
{
printf("\t\t》》》》》》》>>数据结构实验一<<《《《《《《《\n");
printf("\t\t*********线性表的顺序存储结构和实现***********\n");
do
{
menu();
printf("\t\t★请按提示输入指令:");
scanf("%d",&a);
switch(a)
{//调用各函数
case 1: input(); break;
case 2: if(ListInsert_sq(L,i,e)==1) output();
else printf("☆插入位置不合法,请重新输入~\n"); break;
case 3: if(ListDelete_sq(L,i,e)==1)
{
output();
printf("\t\t☆所删除元素为：%d\n",e);
}
else printf("☆删除位置不合法，请重新输入~\n"); break;
case 0: printf("\t\t☆谢谢您的使用,再见 (*^__^*)! \n"); return;
default : printf("\t\t☆输入有误,请重新输入 (*^__^*) \n");
}
}while(a!=0);
}
4.13使用说明
程序执行后显示
========================
0----EXIT
1----START VALUE
2----INSERT
3----DELETE =======================
SELECT:
在select后输入数字选择执行不同的功能。要求首先输入足够多的插入元素，才可以进行其他的操作。每执行一次功能，就会显示执行的结果（正确或错误）以及执行后单链表的内容。
选择0：退出程序
选择1：开始对表初始化
要求输入要插入的位置和元素的值（都是整数）。
选择2：选择插入位置及元素，
要求输入要删除元素的位置，执行成功后返回元素的值。
选择3：要删除元素位置 ，
执行成功后返回删除表中的元素。
4.14测试结果（可以截图）
1） 建立单链表：
4.2链式存储结构
4.21抽象数据类型线性表链式存储结构的表示和实现
#include<stdlib.h>//头文件
#include<stdio.h>
typedef struct
{int *elem;//存储空间基址
int length;/当前线性表的长度
}sqlist;
void init(sqlist *L)
{
L->elem=(int*)malloc(100*sizeof(int));当前分配的存储容量（以sizeof(elemtype)为单位）
L->length=0;
}
void read1(sqlist *L,int n)//表的初始化
{int i;
printf("========= 请输入元素===========:");
for(i=0;i<n;++i)
scanf("%d",&L->elem[i]);
L->length=n;
}
void print(sqlist L)
{ int i;
for(i=0;i<=L.length-1;++i)
printf("%5d",L.elem[i]);
printf("\n");}
void insert(sqlist *L,int i,int e)//插入元素函数
{int *p,*q;
if(i<1||i>L->length+1)
printf("error");
else
{q=&L->elem[i-1];
for(p=&L->elem[L->length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
++L->length;
}
}
void delist(sqlist *L,int i ,int *e)
{ int *p,*q;
if(i<1||i>L->length)
printf("错误\n");
else {q=&L->elem[i-1];
*e=*q;
for(p=q;p<=&L->elem[L->length-1];++p)
*(p)=*(p+1);
--L->length;
}
4.22主函数的伪码算法
void main()
{sqlist L; int e;int i,n;
init(&L); printf("▁▁▁▁请输入元素个数▁▁▁▁▁;");
scanf("%d",&n);
read1(&L,n);
printf("▲输入后表中元素是:");
print(L);
printf("▲请输入要插入元素的位置和元素;");
scanf("%d%d",&i,&e);
insert(&L,i,e);
printf("▲插入后的表中元素为:");
print(L);
printf("▲请输入要删除的元素位置;");
scanf("%d",&i);
delist(&L,i,&e);
printf("▲删除后表中元素为:");
print(L);
getchar();
}
4.23测试结果：
五、附录
5.1顺序存储源代码：
#include<stdio.h>//头文件
#include<stdlib.h>
#include<malloc.h>
#define LIST_INIT_SIZE 100//线性表存储空间的初始分量
#define LISTINCREMENT 10//线性表存储空间的分配增量
#define OVERFLOW -2//宏定义
#define OK 1//宏定义
#define ERROR 0//宏定义
typedef int elemtype;//类型定义
typedef int Status;
typedef struct
{
elemtype *elem;//存储空间基址
int length;//当前线性表的长度
int listsize;//当前分配的存储容量（以sizeof(elemtype)为单位）
}sqlist;
int *p,*q;//定义全局变量
int n,i,e,a;//定义全局变量
sqlist L;//定义结构体L
//自定义函数的声明
Status InitList_sq(sqlist &L);//建表
Status ListInsert_sq(sqlist &L,int i,int e);//插入元素函数
Status ListDelete_sq(sqlist &L,int i,int &e);//删除元素函数
void menu();//菜单函数
void input();//初始化线性表的函数
void output();//显示线性表元素的函数
void main()//主函数
{
printf("\t\t》》》》》》》>>数据结构实验一<<《《《《《《《\n");
printf("\t\t*********线性表的顺序存储结构和实现***********\n");
do
{
menu();
printf("\t\t★请按提示输入指令:");
scanf("%d",&a);
switch(a)
{//调用各函数
case 1: input(); break;
case 2: if(ListInsert_sq(L,i,e)==1) output();
else printf("☆插入位置不合法,请重新输入~\n"); break;
case 3: if(ListDelete_sq(L,i,e)==1)
{
output();
printf("\t\t☆所删除元素为：%d\n",e);
}
else printf("☆删除位置不合法，请重新输入~\n"); break;
case 0: printf("\t\t☆谢谢您的使用,再见 (*^__^*)! \n"); return;
default : printf("\t\t☆输入有误,请重新输入 (*^__^*) \n");
}
}while(a!=0);
}
Status InitList_sq(sqlist &L)
{//构造一个空的线性表
L.elem=(elemtype *)malloc(LIST_INIT_SIZE*sizeof(elemtype));
if(!L.elem) exit(OVERFLOW);//存储分配失败
L.length=0; //空表长度为0
L.listsize=LIST_INIT_SIZE;//初始存储容量
return OK;
}//InitList_sq
Status ListInsert_sq(sqlist &L,int i,int e)
{ //在线性表L中第i个位置前插入新的元素e
//i的合法值1<=i<=L.length+1
int *newbase;
printf("\t\t☆请输入要插入的位置：");
scanf("%d%d"",&i,&e);
if(i<1||i>L.length+1) return ERROR;//i值不合法
if(L.length>=L.listsize)//当存储空间已满，增加分配
{
newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));
if(!newbase) exit(OVERFLOW);//存储分配失败
L.elem=newbase; //新基址
L.listsize+=LISTINCREMENT; //增加存储容量
}
q=&(L.elem[i-1]); //q为插入位置
for(p=&(L.elem[L.length-1]);p>=q;--p) //插入位置及之后的元素后移
*(p+1)=*p;
*q=e;//插入e
++L.length;//表长增加1
return OK;
}//ListInsert_sq
Status ListDelete_sq(sqlist &L,int i,int &e)
{ //在顺序表L中删除第i个元素,并用e返回其值
//i的合法值为1<=i<=L.length
printf("\t\t☆请输入要删除的位置：");
scanf("%d",&i);
if(i<1||i>L.length) return ERROR;//i值不合法
p=&(L.elem[i-1]);//p为被删除元素的位置
e=*p; //被删除元素复制给e
q=L.elem+L.length-1;//表尾元素的位置
for(++p;p<=q+1;++p)//被删除元素之后的元素前移
*(p-1)=*p;
--L.length;//线性表长度减1
return OK;
}//ListDelete_sq
void menu()
{//菜单函数
printf("\t\t============= 请按提示输入指令================\n");
printf("\t\t------------★1输入线性表初始值---------------\n");
printf("\t\t------------★2向线性表插入元素---------------\n");
printf("\t\t------------★3删除线性表元素-----------------\n");
printf("\t\t------------★0退出系统-----------------------\n");
}//menu
void input()
{//初始化线性表元素
if(InitList_sq(L)!=1)
{
printf("☆分配存储空间失败!!!");
return;
}
printf("\t\t☆请输入线性表元素的个数：");
scanf("%d",&n);
InitList_sq(L);
printf("\t\t☆请输入线性表的%d个元素：",n);
for(i=0;i<n;i++)//将输入元素存入线性表
scanf("%d",&L.elem[i]);
L.length=i;//当前线性表长
output();//调用输出函数，查看线性表元素
}//input
void output()
{
printf("\t\t☆操作后线性表内元素为：\n\t\t");
for(i=0;i<L.length;i++)//显示当前线性表元素
printf("%d ",L.elem[i]);
printf("\n");
}//output
5.2链式存储源代码：
#include<stdlib.h>
#include<stdio.h>
typedef struct
{int *elem;
int length;
}sqlist;
void init(sqlist *L)
{
L->elem=(int*)malloc(100*sizeof(int));
L->length=0;
}
void read1(sqlist *L,int n)
{int i;
printf("========= 请输入元素===========:");
for(i=0;i<n;++i)
scanf("%d",&L->elem[i]);
L->length=n;
}
void print(sqlist L)
{ int i;
for(i=0;i<=L.length-1;++i)
printf("%5d",L.elem[i]);
printf("\n");}
void insert(sqlist *L,int i,int e)
{int *p,*q;
if(i<1||i>L->length+1)
printf("error");
else
{q=&L->elem[i-1];
for(p=&L->elem[L->length-1];p>=q;--p)
*(p+1)=*p;
*q=e;
++L->length;
}
}
void delist(sqlist *L,int i ,int *e)
{ int *p,*q;
if(i<1||i>L->length)
printf("error\n");
else {q=&L->elem[i-1];
*e=*q;
for(p=q;p<=&L->elem[L->length-1];++p)
*(p)=*(p+1);
--L->length;
}
}
void main()
{sqlist L; int e;int i,n;
init(&L); printf("▁▁▁▁请输入元素个数▁▁▁▁▁;");
scanf("%d",&n);
read1(&L,n);
printf("▲输入后表中元素是:");
print(L);
printf("▲请输入要插入元素的位置和元素;");
scanf("%d%d",&i,&e);
insert(&L,i,e);
printf("▲插入后的表中元素为:");
print(L);
printf("▲请输入要删除的元素位置;");
scanf("%d",&i);
delist(&L,i,&e);
printf("▲删除后表中元素为:");
print(L);
getchar();
}
六、实验总结
1.学会了线性表顺序存储结构的各项操作。
2.熟练了线性表顺序存储结构实现的算法和程序编写。
3.懂得了return OK存在的意义并合理的利用返回值。
4.学会了用返回值检查程序的错误之处，避免了盲目的查找错误。
5.合理输出运行程序的提示性语句，可以增强程序的可读性和可操作性。
6.在定义和使用同一变量或者函数等名称时尽量使用复制粘贴，可以避免字母大小写不一致等原因出现的低级错误。
7. 执行删除操作时，所删除元素后的元素全部前移，将前移的元素个数+1即把后面的空值赋值给原来的最后一个元素，可以节省存储空间！
8.编写程序时应考虑算法的时间和空间复杂度，选择最优的算法编写程序。
9.程序编写的规范化和视觉美感同程序本身一样重要！