线性表——数据结构实验报告

时间：2024.5.15

实验报告

题目：编制一个演示集合的并交和差运算的程序

班级：姓名：学号：完成日期：年月日

一，需求分析 1集合的元素限定为小写字母字符[?a?..?z?]。集合输入的形式为一个以“回车键”为标志的字符串，串中字符顺序不限，不允许出现重复字符。输出的运算结果字符串中将不含重复字符。

2以对话方式执行。

3程序执行的命令包括：

1）构造集合；2）将集合整理为只含小写字符；3）将集合按从小到大排列；4）选择对集合的操作；5）求交集；6）求并集；7）求差集

4测试数据

（1）Set1=”magzine”, Set2=”paer”,

Set1∪Set2=”aegimnprz”, Set1∩Set2=”ae”, Set1-Set2=”gimnz”。

（2）Set1=”012oper4a6tin89”, Set2=”eordta”,

Set1∪Set2=”adeinoprt”, Set1∩Set2=”aeort”, Set1-Set2=”inp”。

二，概要设计

1基本操作

Lnode *InitList(void); //初始化一个集合要求无重复数

ListPrint_L(struct Lnode *head); //输出所设定的集合

ListDifference(struct Lnode *a,struct Lnode *b);//作集合的差运算

Lnode *ListArrange(struct Lnode *head); //使集合中只存在小写字母

MergeList_L(struct Lnode *ah,struct Lnode *bh); //将两个集合合并

ListSwitch(struct Lnode *La,struct Lnode *Lb); //选择对集合进行的并、交、差操作

ListSame(struct Lnode *La,struct Lnode *Lb); //作集合的交集

Lnode *ListSort(struct Lnode *La); //进行集合元素的排列

三，详细设计

1元素类型、结点类型和指针类型

typedef char ElemType;

typedef int Status;

typedef struct Lnode{

ElemType data;

struct Lnode *next;

}Lnode,*LinkList;

LinkList InitList(void)

{ //由p1,p2申请空间，获得数据并组成链表

p1=p2=(LinkList)malloc(sizeof(LinkList));

while(p1->data!='\n')

p2->next=p1;

p2=p1;}

2根据有序表的基本操作的特点，有序表采用有序链表实现。

其中部分伪码算法如下：

LinkList InitList(void) //初始化一个集合

{ int n;

struct Lnode *head;

struct Lnode *p1,*p2;

n=0;

p1=p2=(LinkList)malloc(sizeof(LinkList));

scanf("%c",&p1->data);

head=0;

while(p1->data!='\n')

{n=n+1;

if(n==1) head=p1;

else p2->next=p1;

p2=p1;

p1=(LinkList)malloc(sizeof(LinkList));

scanf("%c",&p1->data);

}

void MergeList_L(LinkList ah,LinkList bh) //作两个集合的并集 { struct Lnode *pa2,*pa1,*pb1,*pb2;

pa2=pa1=ah;

pb2=pb1=bh;

do{

while ((pb1->data>pa1->data)&&(pa1->next!=NULL))

{pa2=pa1;

pa1=pa1->next;

}

if(pb1->data<=pa1->data)

{if(ah==pa1)

ah=pb1;

else pa2->next=pb1;

pb1=pb1->next;

pb2->next=pa1;

pa2=pb2;

pb2=pb1;

}

}while((pa1->next!=NULL)||(pa1==NULL&&pb1==NULL));

if((pb1!=NULL)&&(pb1->data>pa1->data)&&(pa1->next==NULL)) pa1->next=pb1;

pa2=pa1=ah;

pa1=pa1->next;

while(pa1!=NULL)

{ if(pa1->data==pa2->data) {pa2->next=pa1->next;pa1=pa1->next;} else {pa2=pa1;pa1=pa1->next;}

}

void ListSame(LinkList La,LinkList Lb) //作集合的交集 { struct Lnode *pa,*Lc,*pb,*pc;

Lc=pc=La;

for(pa=La;pa!=NULL;pa=pa->next)

{for(pb=Lb;pb!=NULL;pb=pb->next)

if(pa->data==pb->data)

{pc->data=pa->data;pc=pc->next;break;}

}pc->data=NULL;pc->next=NULL;

}

void ListDifference(LinkList a,LinkList b) //作集合的差运算 { struct Lnode *p,*p1,*p2,*head1,*head2;

p1=head1=a;

head2=b;

while(p1!=NULL)

{p2=head2;

while((p1->data!=p2->data)&&(p2->next!=NULL))

p2=p2->next;

if(p1->data==p2->data)

if(p1==head1)

head1=p1->next;

else

{p->next=p1->next;//将a-b的结果放在a中

p1=p1->next;}

else {p=p1;p1=p1->next;}

}

3主函数和其他函数

void main()

{ //主函数

struct Lnode *La,*Lb;

La=InitList(); //设定第一个集合

Lb=InitList(); //设定第二个集合

ListPrint_L(La); //输出第一个设定的集合

ListPrint_L(Lb); //输出第二个设定的集合

ListArrange(La); //使第一个集合中只存在小写字母 ListArrange(Lb); //使第二个集合中只存在小写字母 ListSort(La); //整理第一个集合，使其按小到大排列 ListSort(Lb); //整理第二个集合，使其按小到大排列 ListSwitch(La,Lb); //选择对集合进行的并、交、差操作 }//main

void ListPrint_L(LinkList head) //输出初始化的集合 { struct Lnode *p;

printf("\n");

p=head;

if(p!=NULL)

{printf(" %c",p->data);

p=p->next;

} while(p!=NULL);

}

LinkList ListArrange(LinkList head) //使集合中只存在小写字母 { struct Lnode *p2,*p1;

p2=p1=head;

while(p1!=NULL)

{ if((p1->data>='0')&&(p1->data<='9'))

{p2->next=p1->next; //将a-b的结果放在a中 p1=p1->next;}

else {p2=p1;p1=p1->next;}

}

printf("\n集合中只存在小写字母 ");

p1=head;

while(p1!=NULL)

{printf("%c ",p1->data);

p1=p1->next;}

return (head);

}

LinkList ListSort(LinkList La)

{ //进行集合元素的由小到大排列，再进行集合的并交差操作

struct Lnode *Lc,*pc,*pa,*pc1;

Lc=pc=(LinkList)malloc(sizeof(LinkList));

pc->next=(LinkList)malloc(sizeof(LinkList));

pa=La->next;

pc->next->data=La->data;

pc->next->next=NULL;

for(pc=Lc;pa!=NULL; pa=pa->next)

{ pc1=(LinkList)malloc(sizeof(LinkList));

pc1->data=pa->data;

while((!pc->next)&&(pc1->data>pc->next->data)) pc=pc->next; pc1->next=pc->next;

pc->next=pc1;

}

printf("\n整理元素后为：\n");

pc=Lc->next;

while(pc!=NULL)

{printf(" %c",pc->data);

pc=pc->next;}

printf("\n");

return(Lc);

}

void ListSwitch(LinkList La,LinkList Lb )//选择对集合进行的并、交、差操作

{ int i;

printf("\n\n\n 1.进行集合并集运算。\n 2.进行集合交集运算。\n 3.进行集合差运算。\n\n请选择序号：\n"); scanf("%d",&i);

switch(i)

{ case 1:MergeList_L(La,Lb);//进行集合并集运算

break;

case 2:ListSame(La,Lb);//进行集合交集运算

break;

case 3:ListDifference(La,Lb);//进行集合差运算

}

4函数的调用关系图反映了层次结构：

main

InitList ListPrint_L ListArrange ListSort ListSwitch

MergeList_L ListSame ListDifference

四，调试分析

1本程序的模块划分比较合理，且尽可能将指针的操作封装在结点和链表的两个模块中，致使集合模块的调试比较顺利，反之，如此划分的模块并非完全合理，因为在实现集合操作的编码中依然需要判别指针是否为空。按理，两个链表的并交差的操作也应封装在链表的模块中，只要进行相应的应用即可。

2由于有序表采用有序链表，各操作的算法时间复杂度比较合理。

五，用户手册六，测试结果

执行命令第一个集合元素是：

请输入集合：

注意不存在相同的元素及大写字母。后键入magzine后，构造集合[magzine] 执行命令第二个集合元素是：

请输入集合：

注意不存在相同的元素及大写字母。后键入paer后，构造集合[paer] 执行命令此时，输出第一个集合输出magzine

执行命令此时，输出第二个集合输出paer

执行命令此时，使第一个集合中只存在小写字母

集合中只存在小写字母输出magzine

执行命令此时，使第二个集合中只存在小写字母

集合中只存在小写字母输出paer

执行命令整理元素后为：aegimnz

整理元素后为：aepr

执行命令请选择序号：

1构造集合的并集：adeinoprt

2构造集合的交集：aeort

3构造集合的差集：inp

七，附录

源程序文件名清单：

stdio.h

malloc.h

第二篇：数据结构实验报告在实现线性表的基础上实现逆置功能

数据结构实验报告

1．实验题目

在实现线性表的基础上实现逆置功能

2．需求分析

　　本演示程序用TC编写，完成线性表的逆置功能。

① 输入的形式和输入值的范围：逆转线性表中的元素首先需要输入需要逆转的元素，然后通过计算机逆转以后输出。在输入和输出都要求其值为整数。

② 输出的形式：在操作中显示操作是否正确以及操作后逆转的内容。

　　③ 程序所能达到的功能：完成线性表的元素逆转操作。

　　④ 测试数据：

　　　输入3,1,2.

输出结果为2,1,3.

3．概要设计

　1）为了实现上述程序功能，需要定义线性表的抽象数据类型：

typedef struct LNode {

定义元素的类型：ElemType data;

定义的*next结构体类型的指针：struct LNode *next;}

作用：定义链表结构体

2）定义新的链表

Status Initial_L(LinkList L)

3）定义链表实现插入元素功能

Status GetElem_L(LinkList L,int i,ElemType *e)

4）定义链表实现打印出初始链表的功能：

Status Print(LinkList L)

5）定义链表实现插入元素的功能：

Status ListInsert_L(LinkList L,int i,ElemType e)

6）定义链表实现逆转元素的过程：

Status ListInv(LinkList L)

4. 详细设计

　　1）为了实现上述程序功能，需要定义线性表的抽象数据类型：

typedef struct LNode {

定义元素的类型：ElemType data;

定义的*next结构体类型的指针：struct LNode *next;}

作用：定义链表结构体

2）为了实现上述功能，需要新的链表：

Status Initial_L(LinkList L)

{

L->next=NULL;

L->data=-1000;

return OK;

}

3）为了实现上述功能，需要能够插入元素，故引用该函数：

Status GetElem_L(LinkList L,int i,ElemType *e)

{

return OK;

}

4）将链表的初始值打印出来：

Status Print(LinkList L)

{

LNode *p;

p=L->next;

if(p==NULL) printf("链表为空!\n");

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

return OK;

}

Status Print(LinkList L,char *s)

{

LNode *p;

p=L->next;

if(p==NULL) {printf("链表为空!\n"); return ERROR;}

printf(s);

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

return OK;

}

5）为了实现上述功能，还需要插入功能：

Status ListInsert_L(LinkList L,int i,ElemType e)\*L为链表，i为链表的长度，e为过渡空间指针*\

{

LNode *p,*s;

p=L;

int j=0;

while(p&&j<i-1) \*当链表不为空且插入的元素要插入的位置小于等于链表的长度就执行以下语句*\

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

if(!p||j>i-1) return ERROR;\*p为空，则非p为真，if语句可执行，链表为空或者插入在链表的后面，后面是不允许的，所以终止*\

s=(LinkList) malloc(sizeof(LNode));\*插入节点，包括指针域和数据域*\

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

6)实现逆置功能：

Status ListInv(LinkList L)

{

LNode *p,*q,*r;

p=L->next;

if(p==NULL ||p->next==NULL)

{

printf("链表只有一个结点或为空，无需逆转！\n");

return OK;

}

q=p->next;

r=q->next;

p->next=NULL;

while(r!=NULL)

{

q->next=p;

p=q;q=r;

r=r->next;

}

q->next=p;

L->next=q;

return OK;

}

5．调试分析

说明：原因在于在打头文件的时候，漏打了其中一个部分，导致指针变量不同，出现错误。

6．使用说明

在编辑程序的时候将要逆转的元素打出，如图，然后点击运行实现元素的逆转过程。

7．测试结果

　　8．程序

1）头文件

#define ElemType int

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

typedef struct LNode

{

ElemType data;

struct LNode *next;

}LNode,*LinkList;

enum Status {OK=1,ERROR=0,OVERFLOW=2,FULL=3};

Status Initial_L(LinkList L)

{

L->next=NULL;

L->data=-1000;

return OK;

}

Status GetElem_L(LinkList L,int i,ElemType *e)

{

return OK;

}

Status Print(LinkList L)

{

LNode *p;

p=L->next;

if(p==NULL) printf("链表为空!\n");

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

return OK;

}

Status Print(LinkList L,char *s)

{

LNode *p;

p=L->next;

if(p==NULL) {printf("链表为空!\n"); return ERROR;}

printf(s);

while(p!=NULL)

{

printf("%d ",p->data);

p=p->next;

}

printf("\n");

return OK;

}

Status ListInsert_L(LinkList L,int i,ElemType e)

{

LNode *p,*s;

p=L;

int j=0;

while(p&&j<i-1)

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

if(!p||j>i-1) return ERROR;

s=(LinkList) malloc(sizeof(LNode));

s->data=e;

s->next=p->next;

p->next=s;

return OK;

}

Status ListInv(LinkList L)

{

LNode *p,*q,*r;

p=L->next;

if(p==NULL ||p->next==NULL)

{

printf("链表只有一个结点或为空，无需逆转！\n");

return OK;

}

q=p->next;

r=q->next;

p->next=NULL;

while(r!=NULL)

{

q->next=p;

p=q;q=r;

r=r->next;

}

q->next=p;

L->next=q;

return OK;

}

2）主函数

#include "LinkList.h"

void main()

{

LinkList head;

head=(LinkList) malloc(sizeof(LNode));

int i=Initial_L(head);

if(i==1) printf("初始化成功!\n");

Print(head);

ListInsert_L(head,1,2);

ListInsert_L(head,1,1);

ListInsert_L(head,1,3);

Print(head,"初始链表为: ");

ListInv(head);

Print(head,"逆转后链表为: ");

}

更多相关推荐：

数据结构线性表操作实验报告: 数据结构实验报告实验题目线性表的操作实验目的1掌握上机调试线性表的基本方法2掌握线性表的一些基本操作实验内容将两个有序链表合并为一个有序链表一需求分析1实验程序中先创建两个有序链表演示程序以用户和计算机的对话方...
数据结构线性表试验报告: 线性表上机实习1实验目的1熟悉将算法转换为程序代码的过程2了解顺序表的逻辑结构特性熟练掌握顺序表存储结构的C语言描述方法3熟练掌握顺序表的基本运算查找插入删除等掌握顺序表的随机存取特性4了解线性表的链式存储结构...
数据结构线性表实验报告: 《数据结构》实验报告院系应用科技学院专业电子信息工程姓名##学号10级电信班20##年10月11日1.实验目的1.掌握线性表的基本运算。2.掌握顺序村存储的概念，学会对顺序存储数据结构进行操作。3.加深对顺序存…
数据结构--实验报告线性表的基本操作: 一、实验目的二、实验内容和要求三、源代码1)顺序表的代码2)单链表的代码四、测试结果1)顺序表的测试结果2)单链表的测试结果五、心得体会实验一线性表的基本操作及其应用一、实验目的1、帮助读者复习C++语言程序设…
数据结构实验报告线性表的顺序表示和实现: 数学与计算科学学院实验报告实验项目名称线性表的顺序表示和实现所属课程名称数据结构A实验类型验证性实验日期20xx年4月5号班级信管1002班学号20xx44070218姓名张松涛成绩1234附录1源程序5678...
数据结构实验报告三线性表的链式存储: 实验报告三线性表的链式存储班级20xxXXX姓名HoogLe学号20xxXXXX专业XXXX2858505197qqcom一实验目的1掌握单链表的基本操作的实现方法2掌握循环单链表的基本操作实现3掌握两有序链表...
数据结构线性表实验报告: 浙江万里学院实验报告专业班级计算机111实验小组第十组实验日期20xx921

数据结构实验报告1线性表的顺序存储结构: 数据结构实验报告1线性表的顺序存储结构，内容附图。
数据结构实验报告在实现线性表的基础上实现逆置功能: 数据结构实验报告1实验题目在实现线性表的基础上实现逆置功能2需求分析本演示程序用TC编写完成线性表的逆置功能输入的形式和输入值的范围逆转线性表中的元素首先需要输入需要逆转的元素然后通过计算机逆转以后输出在输入和...
数据结构与算法实验报告-线性表: 沈阳工程学院学生实验报告课程名称数据结构与算法实验题目线性表班级网本112班学号20xx414217姓名樊鹏鹏地点F606指导教师吕海华祝世东实验日期20xx年9月27日1234567891011121314
数据结构实验报告: 专业年级学号学生姓名指导老师华中师范大学信息管理系编数据结构实验报告I实验要求1每次实验中有若干习题每个学生至少应该完成其中的两道习题2上机之前应作好充分的准备工作预先编好程序经过人工检查无误后才能上机以提高上...
川师数据结构实验报告(含截图): 数据结构实验教学大纲学时课程总64学分4实验学时24实验个数7实验学分15课程性质必做适用专业计算机科学与技术软件工程网络工程教材及参考书数据结构C语言版严蔚敏吴伟民清华大学出版社20xx年11月数据结构题集C...

数据结构线性表实验报告（35篇）

热门关注

数据结构线性表实验报告

数据结构实验报告

华中科技大学·计算机13级·数据结构实验报告

北邮数据结构实验报告——线性表

数据结构实验报告实验一线性表

数据结构顺序表实验报告