数据结构线性表实验报告
- 格式：docx
- 大小：31.97 KB
- 文档页数：17
实验报告
课程 数据结构 实验名称 实验一线性表
学号
姓名
实验日期：
实验一线性表
实验目的：
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 个结点 */
{
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 个结点 */
{
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
{
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;/* 包含 printf() 函数 */
/* 包含 exit() 函数 */
/* 包含 malloc() 函数 */
/* 定义 DataType 为 int*/
/* 包含单链表的头文件 */
p=*head;
while(p!=NULL)
{
p1=p;
p=p->next;
free(p1);
}
*head=NULL;
}
(2 )测试主函数如下：
#include
#include
#include
typedef int DataType;
#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
i++) 删除第四个数据元素 */
/* 显示当前数据元素 */
if(ListGet(head, i,
&x)==0)
{ /* 取数据元素
*/ /* 显示 */
/* 撤销单链表 */
void listInitiate(SeqList *L)
{
L->size=0; /* 初始化顺序表 L */
/* 定义初始化数据元素个数 */ printf("error!\n");
return;
}
else
printf("%d ", x);
}
Destroy(&head);
}
2－ 22 设计一个有序顺序表
头文件程序如下：
#define NULL 0
typedef struct
{
DataType List[MaxSize];
int size;
}SeqList;
