循环单链表的实验报告

《数据结构》实验报告

1、实验名称:设计循环单链表 2、实验日期: 2011-3-4 3、基本要求：

1）循环单链表的操作，包括初始化、求数据元素个数、插入、删

除、取数据元素；

2）设计一个测试主函数实际运行验证所设计循环单链表的正确性。

4、测试数据：

依次输入1，2，3，4，5，6，7，8，9，10，删除5，再依次输出

数据元素。

5、算法思想或算法步骤:

主函数主要是在带头结点的循环单链表中删除第i个结点，其主

要思想是在循环单链表中寻找到第i-1个结点并由指针p指示，然后让指针s指向a[i]结点，并把数据元素a[i]的值赋给x，最后把a[i]结点脱链，并动态释放a[i]结点的存储空间。

6、模块划分：

1）头文件LinList.h。头文件LinList.h中包括：结点结构体定

义、初始化操作、求当前数据个数、插入一个结点操作、删除一个结点操作以及取一个数据元素操作；

2）实现文件xhdlb.cpp。包含主函数void main(void)，其功能是测试所设计的循环单链表的正确性。

7、数据结构：

链表中的结点的结构体定义如下：

typedef struct Node {

DataType data; struct Node *next; }SLNode;

8、源程序：

源程序存放在两个文件中，即头文件LinList.h和实现文件xhdlb.cpp。 //头文件LinList.h typedef struct Node {

DataType data; struct Node *next; }SLNode;

void ListInitiate(SLNode **head) //初始化 {

*head=(SLNode *)malloc(sizeof(SLNode)); //申请头结点，由head指示其地址 (*head)->next=*head; }

int ListLength(SLNode *head) {

SLNode *p=head; //p指向头指针 int size=0; //size初始值为0 while(p->next!=head) //循环计数 {

p=p->next; size++; }

return size; }

int ListInsert(SLNode *head,int i,DataType x)

//在带头结点的循环单链表head的第i（0<=i<=size）个结点前插//入一个存放数据元素x的结点。插入成功返回1；失败则返回0 {

SLNode *p,*q; int j; p=head; j=-1;

while(p->next!=head&&j

//最终让指针p指向第i-1个结点 {

p=p->next; j++; }

if(j!=i-1) {

printf(\插入位置参数错!\ return 0; }

q=(SLNode *)malloc(sizeof(SLNode)); //生成新结点 q->data=x; //新结点数据域赋值 q->next=p->next; p->next=q; return 1; }

int ListDelete(SLNode *head,int i,DataType *x)

//删除带头结点循环单链表head的第i(0<=i<=size-1)个结点被删//除结点的数据域值由x带回。删除成功则返回1；失败则返回0。 {

SLNode *p,*s; int j; p=head; j=-1;

while(p->next!=head&&p->next->next!=NULL&&j

p=p->next; j++; }

if(j!=i-1) {

printf(\删除位置参数错!\ return 0; }

s=p->next; //指针s指向a[i]结点 *x=s->data; //把指针s所指结点的数据域值赋予x p->next=p->next->next; //删除

free(s); //释放指针s所指结点的内存空间 return 1; }

int ListGet(SLNode *head,int i,DataType *x) {

SLNode *p; int j; p=head;

本文来源：https://www.bwwdw.com/article/cjvp.html