实验报告
实验一 线性表
实验目的：
1.理解线性表的逻辑结构特性；
2.熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；
3.熟练掌握线性表的链表存储结构的描述方法，以及在该存储结构下的基本操作；并能灵活运用；
4.掌握双向链表和循环链表的的描述方法，以及在该存储结构下的基本操作。
实验原理：
线性表顺序存储结构下的基本算法；
线性表链式存储结构下的基本算法；
实验内容：
2－21设计单循环链表，要求：
（1） 单循环链表抽象数据类型包括初始化操作、求数据元素个数操作、插入操作、删除操作、取消数据元素操作和判非空操作。
（2） 设计一个测试主函数，实际运行验证所设计单循环链表的正确性。
2－22 .设计一个有序顺序表，要求：
（1） 有序顺序表的操作集合有如下操作：初始化、求数据元素个数、插入、删除和取数据元素。有序顺序表与顺序表的主要区别是：有序顺序表中的数据元素按数据元素值非递减有序。
（2） 设计一个测试主函数，实际运行验证所设计有序顺序表的正确性。
（3） 设计合并函数ListMerge（L1,L2,L3）,功能是把有序顺序表L1和L2中的数据元素合并到L3，要求L3中的数据元素依然保持有序。并设计一个主函数，验证该合并函数的正确性。
程序代码：
2－21（1）头文件LinList.h如下：
typedef struct node
{
DataType data;
struct node *next;
}SLNode;
/*（1）初始化ListInitiate(SLNode * * head)*/
void ListInitiate(SLNode * * head)
{ /*如果有内存空间，申请头结点空间并使头指针head指向头结点*/
if((*head=(SLNode *)malloc(sizeof(SLNode)))==NULL)exit(1);
(*head)->next=NULL; /*置结束标记NULL*/
}
/*(2)求当前数据元素个数ListLength(SLNode * head)*/
int ListLength(SLNode * head)
{
SLNode *p=head;
int size=0;
while(p->next!=head)
{
p=p->next;
size++;
}
return size;
}
/*(3)插入ListInsert(SLNode * head， int i， DataType x)*/
/*在带头结点的单链表的第i(0<=i<=size)个结点前*/
/*插入一个存放数据元素x的结点。插入成功时返回1，失败返回0*/
int ListInsert(SLNode * head, int i, DataType x)
{
SLNode *p, *q;
int j;
p=head;
j=-1;
while(p->next!=head && j<i-1)
/*最终让指针指向第i-1个结点*/
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("The inserted position is error!");
return 0;
}
/*生成新结点由指针q指示*/
if((q=(SLNode *)malloc(sizeof(SLNode)))==NULL) exit(1);
q->data=x;
q->next=p->next;
p->next=q;
return 1;
}
/*(4)删除ListDelete(SLNode * head， int i， DataType *x) */
/*删除带头结点的单链表head的第i(0<=i<=size)个结点前*/
/*被删除结点的数据元素域由x带回。删除成功时返回1，失败返回0*/
int ListDelete(SLNode * head, int i, DataType *x)
{
SLNode *p, *s;
int j;
p=head;
j=-1;
while(p->next!=head && p->next->next!=head && j<i-1)
/*最终让指针指向第i-1个结点*/
{
p=p->next;
j++;
}
if(j!=i-1)
{
printf("The deleted position of parameter is error!");
return 0;
}
s=p->next; /*指针s指指向ai结点*/
*x=s->data;
p->next=p->next->next; /*删除*/
free(s); /*释放指针s所指结点的内存空间*/
return 1;
}
/*(5)取数据元素ListGet(SLNode * head， int i， DataType *x)*/
int ListGet(SLNode * head, int i, DataType *x)
{
SLNode *p;
int j;
p=head;
j=-1;
while(p->next!=head && j<i)
{
p=p->next;
j++;
}
if(j!=i)
{
printf("The gotten position of parameter is error!");
return 0;
}
*x=p->data;
return 1;
}
/*(6)撤销单链表Destroy(SLNode * * head)*/
void Destroy(SLNode * * head)
{
SLNode *p, *p1;
p=*head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
*head=NULL;
}
（2）测试主函数如下：
#include <stdio.h> /*包含printf()函数*/
#include <stdlib.h> /*包含exit()函数*/
#include <malloc.h> /*包含malloc()函数*/
typedef int DataType; /*定义DataType为int*/
#include "LinList.h" /*包含单链表的头文件*/
void main(void)
{
SLNode *head; /*定义头指针变量*/
int i, x;
ListInitiate(&head); /*初始化*/
for(i=0;i<10;i++) /*插入10个数据元素*/
{
if(ListInsert(head, i, i+1)==0)
{
printf("error!\n");
return;
}
}
if(ListDelete(head, 4, &x)==0) /*删除第四个数据元素*/
{
printf("error!\n");
return;
}
for(i=0; i<ListLength(head); i++) /*显示当前数据元素*/
{
if(ListGet(head, i, &x)==0) /*取数据元素*/
{
printf("error!\n");
return;
}
else
printf("%d ", x); /*显示*/
}
Destroy(&head); /*撤销单链表*/
}
2－22 设计一个有序顺序表
头文件程序如下：
#define NULL 0
typedef struct
{
DataType List[MaxSize];
int size;
}SeqList;
void listInitiate(SeqList *L) /*初始化顺序表 L */
{
L->size=0; /* 定义初始化数据元素个数 */
}
int ListLength(SeqList L)
{
return L.size;
}
int ListInsert(SeqList *L, int i, DataType x)
{
int j;
if (L->size>=MaxSize)
{
printf("顺序表已满无法插入！\n");
return 0;
}
else if (i<0||i>L->size)
{
printf("参数i不合法！\n");
return 0;
}
else
{
for(j=L->size; j>i; j--)
L->List[j]=L->List[j-1];
L->List[i]=x;
L->size++;
return 1;
}
}
int ListDelete(SeqList *L, int i, DataType *x)
{
int j;
if(L->size<=0)
{
printf("顺序表已空无数据元素可删！\n");
return 0;
}
else if(i<0||i>L->size-1)
{
printf("参数i不合法！\n");
return 0;
}
else
{
*x=L->List[i];
for(j=i+1; j<L->size-1;j++)
L->List[j-1]=L->List[j];
L->size--;
return 1;
}
}
int ListGet(SeqList L, int i, DataType *x)
{
if(i<0||i>L.size-1)
{
printf("参数i不合法！\n");
return 0;
}
else
{
*x=L.List[i];
return 1;
}
}
/*测试主函数设计如下：*/
#include<stdio.h>
#define MaxSize 100
typedef int DataType;
#include "SeqList.h"
int SLOrderInsert(SeqList *L,DataType x)
{
int j;
if(L->size>=MaxSize-1 )
{
printf("顺序表已满无法插入！\n");
return 0;
}
{
for(j=L->size-1;j>0&& x<L->list[j];j--)
L->list[j+1]=L->list[j];
L->list[j+1]=x;
L->size++;
return 1;
}
}
void main(void)
{
SeqList MyList;
int a[]={1,2,4,5,6,8,9};/*数组a中的数据元素递增有序*/
int i,n=7;
int x;
ListInitiate(&MyList);
for(i=0;i<n+1;i++)
ListInitiate(&MyList);
SLOrderInsert(&MyList,a[i]);
for(i=0;i<n+1;i++)
{
ListGet(MyList,i,x);
printf("%d",a[i]);
}
}
实验结果：
（1）2－21运行结果如下：
（2）2－22运行结果如下：
总结与思考
（1）在TC2的使用过程中遇到很多问题，路径问题总是导致错误。有序顺序表的操作集合和线性表的操作集合类似。
（2）带头结点循环链表的操作实现与带头结点的单链表的操作实现方法相似，但也有差别主要在：
1、在初始化函数中，把语句(*head)->next=NULL改为(*head)->next=head。
2、在其它函数中，循环判定条件p->next!=NULL和p->next->next!=NULL中的NULL换成头指针head.
第二篇：数据结构--实验报告_线性表的基本操作备用
实验目的
实验内容和要求
源代码
顺序表的代码
单链表的代码
测试结果
顺序表的测试结果
单链表的测试结果
五、心得体会
实验一 线性表的基本操作及其应用
一、实验目的
1、帮助读者复习C++语言程序设计中的知识。
2、熟悉线性表的逻辑结构。
3、熟悉线性表的基本运算在两种存储结构上的实现。
4、掌握顺序表的存储结构形式及其描述和基本运算的实现。
5、熟练掌握动态链表结构及有关算法的设计
二、实验内容
题目一：顺序表的基本操作
[问题描述]
实现顺序表的建立、求长度，取元素、修改元素、插入、删除等顺序表的基本操作。
[基本要求]
（1）依次从键盘读入数据，建立带头结点的顺序表；
（2）输出顺序表中的数据元素
（3）求顺序表的长度；
（4）根据指定条件能够取元素和修改元素；
（5）实现在指定位置插入和删除元素的功能。
（6）根据算法，将两个有序的顺序表合并成一个有序顺序表。
[测试数据] 由学生任意指定。
题目二：单链表的基本操作
[问题描述]
实现带头结点的单链表的建立、求长度，取元素、修改元素、插入、删除等单链表的基本操作。
[基本要求]
（1）依次从键盘读入数据，建立带头结点的单链表；
（2）输出单链表中的数据元素
（3）求单链表的长度；
（4）根据指定条件能够取元素和修改元素；
（5）实现在指定位置插入和删除元素的功能。
（6）根据算法，将两个有序的单链表合并成一个有序单链表。
[测试数据]
由学生任意指定。
三、源代码
顺序表的基本操作
#include＜iostream＞
using namespace std;
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct { //结构体
ElemType *elem;
int length;
int listsize;
}SqList;
SqList Lx;
Status InitList_Sq(SqList &L) //分配空间
{ L.elem=new ElemType[LIST_INIT_SIZE];
if(!L.elem)exit(OVERFLOW);
L.length =0;
L.listsize=LIST_INIT_SIZE;
return OK;
}
Status ListInsert(SqList &L,int i,ElemType e) //插入新元素
{ int *q,*p;ElemType *newbase;
if(i＜1 || i＞L.length+1) return ERROR;
if(L.length＞=L.listsize)
{ newbase=new ElemType[L.listsize+LISTINCREMENT];
if(!newbase) exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
for (p=&(L.elem[L.length-1]);p＞=q;--p)
*(p+1)=*p;
*q=e;
++L.length;
return OK;
}
Status Listlength(SqList L) //长度
{ int *p=L.elem; //判断线形表是否存在
while(p)
{ return (L.length); }
}
Status GetElem(SqList L, int i,ElemType &e) //取元素
{ if(i＜1 || i＞L.length)
return ERROR;
else
{ e=L.elem[i-1];
return e;
}
}
void MergeList(SqList La,SqList Lb,SqList &Lc) //合并
{ ElemType ai,bj;
InitList_Sq(Lc);
int i=1,j=1,k=0;
int La_len,Lb_len;
La_len=Listlength(La);
Lb_len=Listlength(Lb);
while((i＜=La_len)&&(j＜=Lb_len))
{ GetElem(La,i,ai);GetElem(Lb,j,bj);
if(ai＜=bj)
{ ListInsert(Lc,++k,ai);++i; }
else
{ ListInsert(Lc,++k,bj);++j; }
}
while(i＜=La_len)
{ GetElem(La,i++,ai);
ListInsert(Lc,++k,ai);
}
while(j＜=Lb_len)
{ GetElem(Lb,j++,bj);
ListInsert(Lc,++k,bj);
}
}
void show(SqList L,int i) //显示
{ int j;ElemType k;
cout＜＜"顺序表显示如下:"＜
for(j=0;j
{ k=L.elem[j];
cout＜"; }
if(j==i-1 && i＞0)
{ k=L.elem[j]; cout＜
cout＜
}
void create(SqList &L,int n) //输入元素
{ int e;
for(int i=0;i
{ cin＞＞e;
L.elem[i]=e;
L.length=i+1; }
}
Status ListDelete_Sq(SqList &L,int i,ElemType &e) //删除
{ ElemType *p, *q;
if(i＜1 || i＞L.length) 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;
}
Status Listxiugei(SqList &L,int i,ElemType &e) //修改
{ if(i＜1 || i＞L.length)
return ERROR;
else
{ L.elem[i-1]=e;
return OK; }
}
void shuru(SqList &L1) //顺序表的创建
{ int a;
InitList_Sq(L1);
cout＜＜"请输入顺序表的长度：";
cin＞＞a;
cout＜＜"请输入顺序表的元素(共"＜
create(L1,a);
show(L1,a);
}
void chaxun(SqList &L1) //取第i个位置的元素
{ int j;ElemType e1;
cout＜＜"请选择所要取出元素的位置:";
cin＞＞j;
while(j＜0||j＞Listlength(L1))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要取出元素的位置:";
cin＞＞j; }
GetElem(L1,j,e1);
cout＜＜"取出的元素为:"＜
void xiugai(SqList &L1) //修改第i个位置的元素
{ int a;
int j; ElemType e1;
a=L1.length;
cout＜＜"请选择所要修改元素的位置:";
cin＞＞j;
while(j＜0||j＞Listlength(L1))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要修改元素的位置:";
cin＞＞j; }
cout＜＜"要修改成的元素:";
cin＞＞e1;
Listxiugei(L1,j,e1);
cout＜＜"修改后的顺序表数据:"＜
show(L1,a);
}
void shanchu(SqList &L1) //删除顺序表里的元素
{ int a;
int j; ElemType e1;
a=L1.length;
cout＜＜"请选择所要删除元素的位置:";
cin＞＞j;
while(j＜0||j＞Listlength(L1))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要删除元素的位置:";
cin＞＞j; }
ListDelete_Sq(L1,j,e1);
cout＜＜"修改后的顺序表数据:"＜
show(L1,a-1);
}
void charu(SqList &L1) //插入元素到顺序表里
{ int a; int j; ElemType e1;
a=L1.length;
cout＜＜"请选择所要插入元素的位置:";
cin＞＞j;
while(j＜0||j＞Listlength(L1))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要插入元素的位置:";
cin＞＞j; }
cout＜＜"要插入的元素:";
cin＞＞e1;
ListInsert(L1,j,e1);
cout＜＜"修改后的顺序表数据:"＜
show(L1,a+1);
}
void hebing(SqList &L3) //合并两个顺序表
{ SqList L1,L2;
int a,b;
InitList_Sq(L1); InitList_Sq(L2);
cout＜＜"请输入第一个有序表的长度："; cin＞＞a;
cout＜＜"请输入第一个有序表的元素(共"＜
create(L1,a);
show(L1,a);
cout＜＜"请输入第二个有序表的长度："; cin＞＞b;
cout＜＜"请输入第二个有序表的元素(共"＜
create(L2,b);
show(L2,b);
MergeList(L1,L2,L3);
cout＜＜"合并后的有序表如下："; show(L3,a+b);
}
void main() //主菜单
{ int choice;
for(;;)
{ cout＜＜" 顺序表的基本操作"＜
cout＜＜" 1.顺序表的创建"＜
cout＜＜" 2.顺序表的显示"＜
cout＜＜" 3.顺序表的长度"＜
cout＜＜" 4.取第i个位置的元素"＜
cout＜＜" 5.修改第i个位置的元素"＜
cout＜＜" 6.插入元素到顺序表里"＜
cout＜＜" 7.删除顺序表里的元素"＜
cout＜＜" 8.合并两个顺序表"＜
cout＜＜" 9.退出系统"＜
cout＜＜"请选择：";
cin＞＞choice;
switch(choice)
{ case 1: shuru(Lx);break;
case 2: show(Lx,Lx.length);break;
case 3: cout＜＜"顺序表的长度:"＜
case 4: chaxun(Lx);break;
case 5: xiugai(Lx);break;
case 6: charu(Lx);break;
case 7: shanchu(Lx);break;
case 8: hebing(Lx);break;
case 9: cout＜＜"退出系统!"＜
default : cout＜＜"输入有误，请重新选择"＜
}
}
单链表的基本操作
#include＜iostream＞
using namespace std;
#define true 1
#define false 0
#define ok 1
#define error 0
#define overflow -2
typedef int Status;
typedef int ElemType;
typedef struct LNode //存储结构
{ ElemType data;
struct LNode *next;
}LNode,*LinkList;
void CreateList(LinkList &L,int n) //尾插法创建单链表
{ LinkList p;
L=new LNode;
L-＞next=NULL; //建立一个带头结点的单链表
LinkList q=L; //使q指向表尾
for(int i=1;i＜=n;i++)
{ p=new LNode;
cin＞＞p-＞data;
p-＞next=NULL;
q-＞next=p;
q=p; }
}
Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素
{ LinkList p=L-＞next;
int j=1;
while(p&&j
{ p=p-＞next;
++j; }
if(!p||j＞i) return error; //第i个元素不存在
e=p-＞data;
return ok;
}
Status LinkInsert(LinkList &L,int i,ElemType e) //插入
{ LinkList p=L;
int j=0;
while(p&&j
{ p=p-＞next;
++j; } //寻找第i-1个结点
if(!p||j＞i-1)
return error; //i小于1或者大于表长加1
LinkList s=new LNode; //生成新结点
s-＞data=e;
s-＞next=p-＞next; //插入L中
p-＞next=s;
return ok;
}
Status ListDelete(LinkList &L,int i,ElemType &e) // 删除
{ LinkList p=L;
LinkList q;
int j=0;
while(p-＞next&&j
{ //寻找第i个结点，并令p指向其前驱
p=p-＞next;
++j; }
if(!(p-＞next)||j＞i-1) return error; //删除位置不合理
q=p-＞next;
p-＞next=q-＞next; //删除并释放结点
e=q-＞data;
delete(q);
return ok;
}
void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)
{ //合并两个顺序链表
LinkList pa,pc,pb;
pa=La-＞next;
pb=Lb-＞next;
Lc=pc=La;
while(pa&&pb)
{ if(pa-＞data＜=pb-＞data)
{ pc-＞next=pa;
pc=pa;
pa=pa-＞next; }
else
{ pc-＞next=pb;
pc=pb;
pb=pb-＞next; }
}
pc-＞next=pa?pa:pb;
delete(Lb);
}
void show(LinkList L) //显示
{ LinkList p;
p=L-＞next;
while(p)
{ cout＜data＜＜"--＞";
p=p-＞next; }
cout＜
}
int Length(LinkList L,int i) //表长
{ i=0;
LinkList p=L-＞next;
while(p)
{ ++i;
p=p-＞next; }
return i;
}
void xiugai(LinkList L) //修改
{ int i,j=1;
ElemType k;
ElemType e,m;
LinkList p=L-＞next;
cout＜＜"请输入要修改的元素位置(0
cin＞＞i;
GetElem(L,i,e);
cout＜＜"该位置的元素:"＜
cout＜＜"修改后的元素值:";
cin＞＞k;
while(p&&j
{ p=p-＞next;
++j; }
m=p-＞data;
p-＞data=k;
cout＜＜"修改后的单链表显示如下:"＜
show(L);
}
void hebing() //合并两个单链表
{ int a,b;
LinkList La,Lb,Lc;
cout＜＜"请输入第一个有序链表的长度:"＜
cin＞＞a;
cout＜＜"请输入第一个有序链表的元素共（"＜
CreateList(La,a);
show(La);
cout＜＜"请输入第二个有序链表的长度:"＜
cin＞＞b;
cout＜＜"请输入第二个有序链表的元素共（"＜
CreateList(Lb,b);
show (Lb);
MergeList(La,Lb,Lc);
cout＜＜"合并后的有序链表如下："＜
show(Lc);
}
void main() //主函数
{ int select;
int x;
ElemType y;
LinkList list;
for(;;)
{ cout＜＜" 单链表的基本操作"＜
cout＜＜" 1.单链表的创建"＜
cout＜＜" 2.单链表的显示"＜
cout＜＜" 3.单链表的长度"＜
cout＜＜" 4.取第i个位置的元素"＜
cout＜＜" 5.修改第i个位置的元素"＜
cout＜＜" 6.插入元素到单链表里"＜
cout＜＜" 7.删除单链表里的元素"＜
cout＜＜" 8.合并两个单链表"＜
cout＜＜" 9.退出系统"＜
cout＜＜"请选择:";
cin＞＞select;
switch(select)
{ case 1:cout＜＜"请输入单链表的长度:"＜
cin＞＞x;
cout＜＜"请输入"＜
CreateList(list,x);
break;
case 2: cout＜＜"单链表显示如下:"＜
show(list);
break;
case 3: int s;
cout＜＜"单链表的长度为:"＜
break;
case 4: cout＜＜"请选择所要取出元素的位置:";
cin＞＞x;
while(x＜0||x＞Length(list,s))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要取出元素的位置:";
cin＞＞x; }
GetElem(list,x,y);
cout＜＜"该位置的元素为:"＜
break;
case 5: xiugai(list); break;
case 6: cout＜＜"请选择要插入的位置:"; cin＞＞x;
while(x＜0||x＞Length(list,s))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要插入元素的位置:";
cin＞＞x; }
cout＜＜"要插入的元素值:";
cin＞＞y;
LinkInsert( list,x,y);
cout＜＜"插入后单链表显示如下:"＜
show(list);
break;
case 7: cout＜＜"请选择要删除的位置:"; cin＞＞x;
while(x＜0||x＞Length(list,s))
{ cout＜＜"输入有误，请重新输入"＜
cout＜＜"请选择所要删除元素的位置:";
cin＞＞x; }
ListDelete(list,x,y);
cout＜＜"要删除的元素值:"＜
cout＜＜"删除后的单链表显示如下:"＜
show(list);
break;
case 8: hebing();
break;
case 9: exit(0);
break;
default : cout＜＜"输入有误，请重新输入"＜
break;
}
}
}
四、测试结果
顺序表 的测试结果
单链表的测试结果
五、心得体会
当听到老师说写数据结构实验报告时，我有点惊讶，才学了不到一个月，就要写实验报告。记得去年学习C++时，学了一个学期，程序设计用了三周，才完成的，这个实验报告居然要一周完成两个设计，觉得很难。但是现在一周过去了，我也写完了，自我感觉良好。
通过这次写实验报告，我深切的理解了这门课的本质。刚开始学这门课时，当时还不清楚这门课程的目的，现在，我真正的理解了：数据结构像是身体的骨骼，而C++是填充这骨骼的肉体，二者相结合才能使整个程序更加完整，健全。数据结构是个框架，模型，抽象数据类型中列举了各种操作，而所用的C++语言，将各种操作描述出来构成算法。数据结构+算法=程序设计。
在这次设计的过程中，我还遇到了，很多的问题。顺序表是按顺序存储的，用了一维数组来存储，又结合C++的程序设计，我又用了类，但是，在执行时出现了问题。后来问同学，指出我的错误，不过获益不少。我又重新整理思路，把顺序表的基本操作写好了。虽然走了很多弯路，但是让我认识到，一定要创新，大胆，不能按照旧的思路去干新的事情。
单链表写起来简单多了，这个很快就搞定了。但是细节上出了问题。比如说，有些变量的重复定义，有些变量又没有定义，在调用函数，就直接复制过来，没有改参数……通过修改，我深刻理解到：细节决定成败，在以后，不管做任何事情都要认真，细心。
这次的实验报告，让我受益匪浅，不仅有知识方面的，还有生活和精神上的。总之，我会继续我的兴趣编程，相信在编程的过程中，能不断的提高自己。