实验二 线性表的应用
实验二线性表的应用（2学时）
一、实验目的：掌握线性表的基本结构和操作方法，培养学生灵活使用结构解决实际问题的能力。
二、实验内容：
设计一个100位以内的长整数加减运算的程序。
三、实验要求：
1，输入输出要求：每四位一组，组间用逗号分隔；
2，加和减分别用不同的程序实现
3，程序应考虑输入数据的符号
四、参考程序
/*设计一个100位以内的长整数加减运算的程序。
实验要求：
1，输入输出要求：每四位一组，组间用逗号分隔；
2，程序应考虑输入数据的符号*/
#include
#include
#include
#include
#include
#define LEN sizeof(struct student)
struct student{
int score;
struct student *next;
};
int lenm,lenn,lensum;//m与n的长度
void main()
{
struct student *creat(int *d,int *len);
void print(struct student *head);
struct student *add(struct student *m,struct student *n);
struct student *sub(struct student *m,struct student *n);
int compare(struct student *m,struct student *n);
struct student *m,*n,*sum;
int s1,s2,s3,k;
char ch;
printf("输入第一个数：\n");
m=creat(&s1,&lenm);//输入第一个数放在链表m中，s1为其符号
printf("\n选择运算，输入＋或－:");
scanf("%c",&ch);getchar();
printf("\n输入第二个数：\n");
n=creat(&s2,&lenn);//输入第一个数放在链表n中，s2为其符号
k=compare(m,n);//k=1则m>n,k=-1则m if(ch=='+')//加法运算 { if(s1*s2>0){s3=s1;sum=add(m,n);} else { if(s1>0&&k==1) {s3=1;sum=sub(m,n);}//m>0,n<0,m>|n|,m+n=m-|n| if(s1>0&&k==-1){s3=-1;sum=sub(n,m);}//m>0,n<0,m<|n|,m+n=-(|n|-m) if(s1<0&&k==1){s3=-1;sum=sub(m,n);}//m<0,n>0,|m|>|n|,m+n=-(|m|-n) if(s1<0&&k==-1){s3=1;sum=sub(n,m);}//m<0,n>0,|m|<|n|,m+n=n-|m| if(k==0) s3=0; } }//endif+ if(ch=='-')//减法运算 { if(s1*s2<0) {s3=s1;sum=add(m,n);} else{ if(s1>0&&k==1) {s3=1;sum=sub(m,n);}//m>0,n>0,m>n,m-n=m-n if(s1>0&&k==-1){s3=-1;sum=sub(n,m);}//m>0,n>0,m if(s1<0&&k==1){s3=-1;sum=sub(m,n);}//m<0,n<0,|m|>|n|,m-n=-(|m|-|n|) if(s1<0&&k==-1){s3=1;sum=sub(n,m);}//m<0,n<0,|m|<|n|,m-n=|n|-|m| if(k==0) s3=0; } }//endif- if(s3>0) {printf("结果为：+");print(sum);} if(s3<0) {printf("结果为：-");print(sum);} if(s3==0) printf("结果为：0"); }//endmain struct student *creat(int *sign,int *n)//输入数据并建立链表首结点存放最低4位数据{ void print(struct student *head);struct student *p1,*p2; int i=0,j,k=0,len; char s[5],c[130]; *sign=1; gets(c); if(c[0]=='-'){i=1;*sign=-1;} p1=p2=(struct student *)malloc(LEN);//建立尾结点 p1->score=0; p1->next=NULL; len=strlen(c); for(;i { j=0; while(c[i]>='0'&&c[i]<='9')//取出逗号之间的每一组数存放到字符数组s中 { s[j++]=c[i++]; k++; } s[j]='\0'; p1=(struct student *)malloc(LEN); p1->score=atoi(s);//将s转换成整数 p1->next=p2;//插入到链表头 p2=p1; } *n=k; return(p1); } struct student *add(struct student *m,struct student *n)//加法运算 { struct student *p1,*p2,*head;//p2指向链表上最后一个结点，p1指向新建立的结点int sumb=0,n1,n2,n3; n1=lenm;n2=lenn; n3=n1>n2?n1:n2; p2=p1=(struct student *)malloc(LEN); p1->score=(m->score+n->score)%10000; sumb=(m->score+n->score+sumb)/10000; p2->next=NULL; head=p2; m=m->next;n=n->next; while(m!=NULL&&n!=NULL) { p1=(struct student *)malloc(LEN); p1->score=(m->score+n->score+sumb)%10000; sumb=(m->score+n->score+sumb)/10000; p1->next=NULL; p2->next=p1; p2=p1; m=m->next; n=n->next; } while(m!=NULL) { p1=(struct student *)malloc(LEN); p1->score=(m->score+sumb)%10000; sumb=(m->score+sumb)/10000; p1->next=NULL; p2->next=p1; p2=p1; m=m->next; } while(n!=NULL) { p1=(struct student *)malloc(LEN); p1->score=(n->score+sumb)%10000; sumb=(n->score+sumb)/10000; p1->next=NULL; p2->next=p1; p2=p1; n=n->next; } lensum=n3; return head; }//endadd struct student *sub(struct student *m,struct student *n)//减法运算{ struct student *p1,*p2,*head; int sumb=0,n1,n2; n1=lenm;n2=lenn; p2=p1=(struct student *)malloc(LEN); if(m->score>=n->score)p1->score=m->score+sumb-n->score; else{p1->score=m->score-n->score+10000;sumb=-1;} p1->next=NULL; m=m->next;n=n->next; head=p2; while(n) { p1=(struct student *)malloc(LEN); p1->next=NULL; if(m->score+sumb>=n->score) { p1->score=m->score+sumb-n->score; sumb=0; } else { p1->score=m->score+sumb-n->score+10000; sumb=-1; } p2->next=p1; p2=p1;m=m->next;n=n->next; } while(m) { p1=(struct student *)malloc(LEN); p1->next=NULL; p1->score=m->score+sumb; sumb=0; p2->next=p1; p2=p1;m=m->next; } lensum=n1; return head; }//endsub int compare(struct student *m,struct student *n)//比较两数大小{ int i=0; if(lenm>lenn) return 1; if(lenm while(m&&n) { if(m->score>n->score) i=1; if(m->score m=m->next;n=n->next; } return i; }//endcompare void print(struct student *head) { int num[100],k=0,i; while(head) { num[k++]=head->score; head=head->next; } for(i=k-1;i>=0;i--) printf("%04d,",num[i]); getch(); } 实验一线性表的应用 一、实验教学目的 1、熟悉将算法转换成程序代码的过程。 2、了解顺序表的逻辑结构特性，熟练掌握顺序表存储结构的C语言描述方法。 3、熟悉链表数据结构的定义和插入、删除等基本操作，会使用链表的基本操作解决一些实际问题 二、实验教学内容 1、实验题目 (1)用C语言数组实现顺序表,并在顺序表上实现：①在第3个位置插入666; ②将第8个元素删除；③在顺序表中查找值为65的元素。 (2)已知有两个多项式Pn(x)和Qm(x)，基于链表设计算法实现Pn(x)+Qm(x)运算，而且不重新开辟存储空间。 ⑶基于链表编程实现多项式乘法运算 2、实验要求： (1)要求用静态分配的一维数组和动态分配的一维数组来完成实验题目。分析静态分配的一维数组和动态分配的一维数组在顺序表基本操作实现上的共同点和区别。 (2)熟悉链表及其运算的实现。 ①自己编写实现函数； ②对所编写的算法进行时间复杂度分析。 ⑶实验⑴、⑵必做，实验⑶选做。 3、实验预备知识 （1）复习C语言相关知识（如：结构体、用typedef自定义类型、函数）。 （2）阅读顺序表与链表的类型定义和相应的插入、删除、查找等基本操作。 4、实验环境 （1）一台运行 Windows 2000/XP 操作系统的计算机。 （2）选用turbo c、visual c++、delphi、c++ builder 或visual basic等任何一种语言。 5、实验说明 （1）顺序存储定义 #define MAXSIZE 100/*表中元素的最大个数*/ typedef int datatype; /*元素类型*/ typedef struct {datatype data[MAXSIZE]; /*静态线性表*/ int last; /*表的实际长度*/ }seqlist; /*顺序表的类型名*/ （2）建立顺序表时可利用随机函数自动产生数据。 （3）注意问题 ①插入、删除时元素的移动原因、方向及先后顺序。 ②不同的函数形参与实参的传递关系。 （4）链表类型定义 typedef int datatype;/*元素类型*/ typedef struct node {datatype data; struct node *next; }lnode,*linklist;/*单链表的类型定义*/ （5）为了算法实现简单，最好采用带头结点的单向链表。 （6）注意问题 ①重点理解链式存储的特点及指针的含义。 ②注意比较顺序存储与链式存储的各自特点。 ③注意比较带头结点、无头结点链表实现插入、删除算法时的区别。 ④单向链表的操作是数据结构的基础，一定要注意对这部分的常见算法的理解。 三、实验内容和实验步骤：（由学生填写） 四、实验用测试数据和相关结果分析：（由学生填写） 五、实验总结：（由学生填写） 六、程序参考模板 《数据结构》实验报告 专业： 学号： 姓名： 实验二线性表 【实验目的】 1.熟悉VC环境，学习如何使用C语言实现线性表的两种存储结构。 2.通过编程、上机调试，进一步理解线性表的基本概念，东运用C语言实现线性表基本操作。 3.熟练掌握线性表的综合应用问题。 【实验内容】 1、一个线性表有n个元素（n-MAXSIZE.MAXSIZE指线性表的最大长度），且递增有。现有一元素x要插入到线性表的适当位置上，并保持线性表原有的顺序不变。设计程序实现。要求：采用顺序存储表示实现；采用链式存储表示方法实现：比较两种方法的优劣。 2.从单链表中删除指定的元素x，若x在单链表中不存在，给出提示信息。 要求： ①指定的值x由键盘输入； ②程序能处理空链表的情况。 3.设有头结点的单链表，编程对表中的任意值只保留一个结点，删除其余值相同的结点。 要求： ①该算法用函数（非主函数)实现； ②在主函数中调用创建链表的函数创建一个单链表，并调用该函数，验证算法的正确性。LinkedList Exchange（LinkedList HEAD,p) //HEAD是单链表头结点的指针，p是链表中的一个结点。本算法将p所指结点与其后 继结点交换。 （q=head->next；//q是工作指针，指向链表中当前待处理结点。 pre=head；//pre是前驱结点指针，指向q的前驱。 while（q'=null &&q1=p)(pre=q；q=q->next；]/未到p结点，后移指针。 if（p->next==null)printf(“p无后继结点\n”）；/p是链表中最后一个结点，无后继。 else/处理p和后继结点交换 （q=p->next；//暂存p的后继。 pre->next=q://p前驱结点的后继指向p的后继。 p->next=q->next；//p的后继指向原p后继的后继。 q->next=p：//原p后继的后继指针指向p。} }//算法结束。 4.已知非空单链表第一个结点由head指出，请写一算法，交换p所指结点与其下一个结点在链表中的位置。 要求： 实验一线性表的基本操作实现及其应用 一、实验目的 1、熟练掌握线性表的基本操作在两种存储结构上的实现。 2、会用线性链表解决简单的实际问题。 二、实验内容 题目一、该程序的功能是实现单链表的定义和操作。该程序包括单链表结构类型以及对单链表操作的具体的函数定义和主函数。其中，程序中的单链表（带头结点）结点为结构类型，结点值为整型。单链表操作的选择以菜单形式出现，如下所示： please input the operation： 1.初始化 2.清空 3.求链表长度 4.检查链表是否为空 5.检查链表是否为满 6.遍历链表（设为输出元素） 7.从链表中查找元素 8.从链表中查找与给定元素值相同的元素在表中的位置 9.向链表中插入元素 10. 从链表中删除元素 其他键退出。。。。。 其中黑体部分必做 题目二、约瑟夫环问题： 设编号为1，2，3，……，n的n(n>0)个人按顺时针方向围坐一圈，每个人持有一个正整数密码。开始时任选一个正整数做为报数上限m，从第一个人开始顺时针方向自1起顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的下一个人开始重新从1报数。如此下去，直到所有人全部出列为止。令n最大值取30。要求设计一个程序模拟此过程，求出出列编号序列。 struct node (一) 1．进入选择界面后，先选择7，进行插入： 2.选择4，进行遍历，结果为： 3.选择2，得出当前链表长度. 4.选择3，得出当前链表为. 5.选择分别选择5、6进行测试. 6.选择8，分别按位置和元素值删除. 7.选择9，或非1-8的字符，程序结束. 数据结构 实验1：线性表的基本操作及其应用 班级：RB软工移151 学号：201560140140 姓名：袁若飞 实验一线性表 一、实验目的 1、帮助读者复习C++语言程序设计中的知识。 2、熟悉线性表的逻辑结构。 3、熟悉线性表的基本运算在两种存储结构上的实现，其中以熟悉链表的操作为侧重点。 二、实验内容 本次实验提供4个题目，每个题目都标有难度系数，*越多难度越大，题目一、二是必做题。题目三、题目四选作。 三、实验准备知识 1、请简述线性表的基本特性和线性表的几种基本操作的机制 ①答：线性表的基本特性是：对线性表中某个元素ai来说，称其前面的元素ai-1为ai的直接前驱，称其后前面的元素ai+1为ai的直接后继。显然，线性表中每个元素最多有一个直接前驱和一个直接后继。 ②答：线性表的几种基本操作的机制有六个： （1）初始化线性表initial_List(L)——建立线性表的初始结构，即建空表。这也是各种结构都可能要用的运算。 （2）求表长度List_length(L)——即求表中的元素个数。 （3）按序号取元素get_element(L,i)——取出表中序号为i的元素。（4）按值查询List_locate(L,x)——取出指定值为x的元素，若存在该元素，则返回其地址；否则，返回一个能指示其不存在的地址值或标记。 （5）插入元素List_insert(L,i,x)——在表L的第i个位置上插入值为x的元素。显然，若表中的元素个数为n，则插入序号i应满足1<=i<=n+1。（6）删除元素List_delete（L，i）——删除表L中序号为i的元素，显然，待删除元素的序号应满足1<=i<=n。 2、掌握线性表的逻辑结构。 3、掌握线性表的链式存储结构。 4、熟练掌握线性表的插入、删除等操作。 实验二线性表(顺序存储) 一、实验目的 1. 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。 2. 重点是线性表的基本操作在两种存储结构上的实现；本次实验以顺序存储的操作为侧重点；并进一步学习结构化的程序设计方法。 二、实例 1. 线性表的顺序存储表示（结构）及实现。 阅读下列程序请注意几个问题： （1）关于线性表的顺序存储结构的本质是：在逻辑上相邻的两个数据元素a i-1, a i，在存储地址中也是相邻的,既地址连续。不同的教材有不同的表示，有的直接采用一维数组，这种方法有些过时。有的采用含‘动态分配’一维数组的结构体，这种方法过于灵活抽象（对读者要求过高）。我们采用的是含‘静态’一维数组和线性表长的结构体： typedef struct { ElemType a[MAXSIZE]; /* 一维数组子域 */ int length; /* 表长度子域 */ }SqList; /* 顺序存储的结构体类型 */ （2）本程序是一个完整的、子函数较多的源程序。目的为学生提供一个示范，提供顺序存储表示的资料，供学生参考。比如，主函数中简单“菜单设计”(do-while循环内嵌套一个 switch结构)技术。在学习数据结构的初级阶段，并不强要求学生一定使用“菜单设计”技术，同学们可以在main()函数中直接写几个简单的调用语句，就象前面的复数处理程序中的main()一样。但是随着学习的深入，尽早学会使用“菜单设计”技术，会明显提高编程和运行效率。 [源程序] （略） 三、实验题 1. 一个线性表有n个元素（n 实验1 线性表及其应用 题目1 顺序表的建立与基本操作 一、实验目的 1. 通过实验，掌握include命令及头文件的使用 2. 通过实验，掌握顺序表的建立与输出 3. 通过实验，掌握顺序表的基本操作 二、实验内容 1. 练习顺序表的建立与输出 2. 练习顺序表的基本操作 三、实验前的准备 1. 理解并掌握顺序表的存储结构、基本操作 2. 复习include命令的使用 3. 预习实习指导书，并准备相关的程序清单 四、实验步骤与方法 （1）建立自己的工作目录 （2）在当前文件夹下建立函数结果状态代码的定义文件Status.h（课本p10（1）预定义常量和类型）和数据结构数据文件SqList.h（内容包括顺序表的描述、顺序表建立、顺序表的查询、插入、删除与输出等功能。） （3）理解并运行下列程序： #include 姓名学号 ElemType data; //待插入元素 SqList L; //定义SqList类型变量 InitList_Sq(L); //初始化顺序表 printf("※1. 请输入所需建立的线性表的长度："); scanf_s("%d", &LIST_MAX); printf("※2. 请录入数据："); for (i = 0; i 实验一线性表的基本操作 一、实验目的 1. 熟悉C/C++语言上机环境； 2. 掌握线性表的基本操作：查找、插入、删除等运算在顺序存储、链式存储结构上的运算。 二、实验环境 1. 装有Visual C＋＋6.0的计算机。 2. 本次实验共计2学时。 三、实验内容 1. 建立顺序表，基本操作包括：初始化、建立顺序表、输出顺序表、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 2. 设有两个非递增有序的线性表A和B，均已顺序表作为存储结构。编写算法实现将A表和B表合并成一个非递增有序排列的线性表（可将线性表B插入线性表A中，或重新创建线性表C）。 3. 建立单链表，基本操作包括：初始化、判断是否为空、取表中第i个元素、查找、插入和删除。并在主函数中完成对各种函数的测试。 四、源程序 #include 实验一线性表及其应用 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容 1.顺序线性表的建立、插入及删除。 2.链式线性表的建立、插入及删除。 三、实验步骤 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度。 2.利用前面的实验先建立一个顺序表L={21，23，14，5，56，17，31}，然后在第i个位置插入元素68。 3.建立一个带头结点的单链表，结点的值域为整型数据。要求将用户输入的数据按尾插入法来建立相应单链表。 四、实现提示 1.由于C语言的数组类型也有随机存取的特点，一维数组的机内表示就是顺序结构。因此，可用C语言的一维数组实现线性表的顺序存储。 在此，我们利用C语言的结构体类型定义顺序表： #define MAXSIZE 1024 typedef int elemtype; /* 线性表中存放整型元素*/ typedef struct { elemtype vec[MAXSIZE]; int len; /* 顺序表的长度*/ }sequenlist; 将此结构定义放在一个头文件sqlist.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出顺序表的建立及常量的定义。 2. 注意如何取到第i个元素，在插入过程中注意溢出情况以及数组的下标与位序（顺序表中元素的次序）的区别。 3.单链表的结点结构除数据域外，还含有一个指针域。用C语言描述结点结构如下： typedef int elemtype; typedef struct node 实验一线性表操作 实验目的： (1)掌握在顺序、链式存储结构上实现线性表的各种基本运算。 (2)重点掌握单链表的基本操作及应用。 (3)学会综合运用C语言中函数、指针、结构体等知识进行编程。 本次实验中，下列实验项目选做一。 1、顺序表的综合操作 [问题描述] 设计算法，实现线性结构上的顺序表的建立以及元素的查找、插入、删除等操作。 [基本要求及提示] （1）从键盘输入10个整数，建立顺序表。 （2）从键盘输入1个整数，在顺序表中查找该结点的位置。若找到，输出结点的位置；若找不到，则显示“找不到”。 （3）从键盘输入2个整数，一个表示欲插入的位置i，另一个表示欲插入的数值x，将x插入在对应位置上，输出顺序表所有结点值，观察输出结果。 （4）从键盘输入1个整数，表示欲删除结点的位置，输出顺序表所有结点值，观察输出结果。 （5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、线性表的逆置 [问题描述] （1）以顺序存储结构实现线性表的就地逆置。 （2）以链式存储结构实现线性表的就地逆置。 注：线性表的就地逆置就是在原表的存储空间内将线性表（a1,a2,a3,…,an）逆置为（an，an-1，…，a2，a1）。 [基本要求及提示] （1）从键盘输入10个整数，建立顺序表。 （2）实现顺序表逆置，并将结果输出。 （3）从键盘输入10个整数，建立链表。 （4）实现链表逆置，并将结果输出。 （5）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。也可以将顺序表和链表上的操作分开，做成两个程序。 3、线性表的元素分类 [问题描述] 已知线性表中元素均为正整数，设计算法将其调整为前后两部分，前边均为奇数，后边均为偶数。即实现线性表的元素的分类。 [基本要求及提示] （6）从键盘输入10个整数，建立顺序表。 实验1 线性表的基本操作 一、需求分析 目的： 掌握线性表运算与存储概念，并对线性表进行基本操作。 1.初始化线性表； 2.向链表中特定位置插入数据； 3.删除链表中特定的数据； 4.查找链表中的容； 5.销毁单链表释放空间； 二、概要设计 ●基础题 主要函数： 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 实验步骤： 1，初始化顺序表 2，调用插入函数 3，在顺序表中查找指定的元素 4，在顺序表中删除指定的元素 5，在顺序表中删除指定位置的元素 6，遍历并输出顺序表 ●提高题 要求以较高的效率实现删除线性表中元素值在x到y（x和y自定义）之间的所有元素 方法： 按顺序取出元素并与x、y比较，若小于x且大于y，则存进新表中。 编程实现将两个有序的线性表进行合并，要求同样的数据元素只出现一次。 方法： 分别按顺序取出L1，L2的元素并进行比较，若相等则将L1元素放进L中，否则将L 1，L2元素按顺序放进L。 本程序主要包含7个函数 主函数main() 初始化线性表InitList（List* L，int ms） 向顺序表指定位置插入元素InsertList（List* L，int item，int rc）删除指定元素值的顺序表记录DeleteList1(List* L,int item) 删除指定位置的顺序表记录 DeleteList2（List* L,int rc） 查找顺序表中的元素 FindList（List L，int item） 输出顺序表元素OutputList（List L） 提高题的程序 void Combine(List* L1,List* L2,List* L) void DeleteList3(List* L,int x,int y) 二、详细设计 初始化线性表InitList（List* L，int ms） void InitList(List* L,int ms) { L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int)); L->size=0; L->MAXSIZE=LIST_INIT_SIZE; 实验报告——线性表应用一、实验目的 用单链表储存一元多项式，并实现两个多项式的相加运算。 二、实验内容 1.先创建链表，存储多项式； 2.输出多项式； 3.两个多项式相加； 4.输出多项式。 三、程序代码 #include void print(Polynode*L) { Polynode*p; p=L->next; printf("a="); if(p&&p->coef!=0) printf("%.2f*x^%d",p->coef,p->exp); while(p->next!=NULL) { if((p->next->coef)>0&&p) printf("+"); else printf("-"); p=p->next; printf("%.2f*x^%d",fabs(p->coef),p->exp); } } //多项式相加 void polyadd(Polylist polya,Polylist polyb) { Polynode*p,*q,*tail,*temp; int sum; p=polya->next; q=polyb->next; tail=polya; while (p!=NULL&&q!=NULL) { if(p->exp 一．实验名称 1.线性表基本操作； 2.处理约瑟夫环问题 二．试验目的： 1．熟悉C语言的上机环境，掌握C语言的基本结构。 2．定义单链表的结点类型。 3．熟悉对单链表的一些基本操作和具体的函数定义。 4．通过单链表的定义掌握线性表的链式存储结构的特点。 5．熟悉对单链表的一些其它操作。 三．实验内容 1.编制一个演示单链表初始化、建立、遍历、求长度、查询、插入、删除等操作的程序。 2.编制一个能求解除约瑟夫环问题答案的程序。 实验一线性表表的基本操作问题描述： 1. 实现单链表的定义和基本操作。该程序包括单链表结构类型以及对单链表操作 的具体的函数定义 程序中的单链表（带头结点）结点为结构类型，结点值为整型。 /* 定义DataType为int类型*/ typedef int DataType; /* 单链表的结点类型*/ typedef struct LNode {DataType data; struct LNode *next; }LNode,*LinkedList; LinkedList LinkedListInit() //初始化单链表 void LinkedListClear(LinkedList L) //清空单链表 int LinkedListEmpty(LinkedList L)//检查单链表是否为空 void LinkedListTraverse(LinkedList L)//遍历单链表 int LinkedListLength(LinkedList L)//求单链表的长度 /* 从单链表表中查找元素*/ LinkedList LinkedListGet(LinkedList L,int i) /* 从单链表表中查找与给定元素值相同的元素在链表中的位置*/ int LinkedListLocate(LinkedList L, DataType x) void LinkedListInsert(LinkedList L,int i,DataType x) //向单链表中插入元素 /* 从单链表中删除元素*/ void LinkedListDel(LinkedList L,DataType x) 北京邮电大学电信工程学院 数据结构实验报告 实验名称：实验1——线性表 学生姓名： 班级： 班内序号： 学号： 日期： 1．实验要求 1、实验目的：熟悉C++语言的基本编程方法，掌握集成编译环境的调试方法 学习指针、模板类、异常处理的使用 掌握线性表的操作的实现方法 学习使用线性表解决实际问题的能力 2、实验内容： 题目1： 线性表的基本功能： 1、构造：使用头插法、尾插法两种方法 2、插入：要求建立的链表按照关键字从小到大有序 3、删除 4、查找 5、获取链表长度 6、销毁 7、其他：可自行定义 编写测试main()函数测试线性表的正确性。 2. 程序分析 2.1 存储结构 带头结点的单链表 2.2 关键算法分析 1.头插法 a、伪代码实现：在堆中建立新结点 将x写入到新结点的数据域 修改新结点的指针域 修改头结点的指针域,将新结点加入链表中b、代码实现： Linklist::Linklist(int a[],int n)//头插法 {front=new Node; front->next=NULL; for(int i=n-1;i>=0;i--) {Node*s=new Node; s->data=a[i]; s->next=front->next; front->next=s; } } 2、尾插法 a、伪代码实现：a.在堆中建立新结点 b.将a[i]写入到新结点的数据域 c.将新结点加入到链表中 d.修改修改尾指针 b、代码实现: Linklist::Linklist(int a[],int n,int m)//尾插法 {front=new Node; Node*r=front; for(int i=0;i 实验报告 课程名称____数据结构上机实验__________ 实验项目______线性表的应用____________实验仪器________PC机___________________ 系别_____电子信息与通信学院___ 专业________ ___ 班级/学号______ __ 学生姓名______ ___________ 实验日期_______________________ 成绩_______________________ 指导教师_______________________ 实验一.线性表的应用 1.实验目的：掌握线性链表的存储、运算及应用。利用链 表实现一元多项式计算。 2.实验内容： 1)编写函数，实现用链表结构建立多项式； 2)编写函数，实现多项式的加法运算； 3)编写函数，实现多项式的显示； 4)测试：编写主函数，它定义并建立两个多项式，显示 两个多项式，然后将它们相加并显示结果。变换测试用的多项式，检查程序的执行结果。 选做内容：修改程序，选择实现以下功能： 5)多项式求值：编写一个函数，根据给定的x值计算并 返回多项式f(x)的值。测试该函数（从终端输入一个x的值，调用该函数并显示返回结果）。 6)多项式相减：编写一个函数，求两个多项式相减的多 项式。 7)多项式相乘：编写一个函数，求两个多项式的乘积多 项式。 3.算法说明： 1)多项式的建立、显示和相加算法见讲义。可修改显示 函数，使输出的多项式更符合表达规范。 2)多项式减法：同次项的系数相减（缺项的系数是0）。 例如a(x)=-5x2+2x+3，b(x)= -4x3+3x，则a(x)-b(x) =4x3-5x2-x+3。提示：a(x)-b(x) = a(x)+(-b(x))。 3)多项式乘法：两个多项式的相乘是“系数相乘，指数 相加”。算法思想是用一个多项式中的各项分别与另 一个多项式相乘，形成多个多项式，再将它们累加在 一起。例如，a(x)=-5x2+2x+3，b(x)=-4x3+3x，则 a(x)*b(x) = (-4x3)*(-5x2+2x+3)+(3x)*(-5x2+2x+3) = (20x5-8x4-12x3) + (-15x3+6x2+9x) = 20x5-8x4-27x3+6x2+9x。 4.实验步骤： 根据实验报告的要求，我对文件夹里的C文件进行了丰 富和修改，步骤如下： 链表结构建立多项式： typedef struct polynode { float coef; //系数 int exp; //指数 struct polynode *next; //下一结点指针 } PNode; 编写函数，实现多项式的加法运算； PNode * PolyAdd (PNode *f1, PNode *f2) //实现加法功能。 实验编号：2四川师大《数据结构》实验报告2016年9月30日 实验二线性表及其实现_ 一．实验目的及要求 （1）熟悉线性表的基本运算在两种存储结构（顺序结构和链式结构）上的实现，以线性表的各种操作（建立、插入、删除等）的实现为实验重点。 （2）通过本次实验帮助学生加深对顺序表、链表的理解，并加以应用。 （3）掌握循环链表和双链表的定义和构造方法。 二．实验内容 （1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找）、排序等），并设计一 个菜单调用线性表的基本操作。 （2）建立一个按元素递增有序的单链表L，并编写程序实现： a）将x插入其中后仍保持L的有序性； b）将数据值介于min和max之间的结点删除，并保持L的有序性； c）将单链表L逆置并输出； （3）编程实现将两个按元素递增有序的单链表合并为一个新的按元素递增的单链表。 注：（1）为必做题，（2）~（3）选做。 三．主要仪器设备及软件 （1）PC机 （2）Dev C++ ,Visual C++, VS2010等 四．实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1）编程实现线性表两种存储结构（顺序存储、链式存储）中的基本操作的实现（线性表的创建、插入、删除、查找（顺序查找、折半查找）、排序等），并设计一 个菜单调用线性表的基本操作。 A.顺序储存： 代码部分： Main.cpp: #include"Sqlist.h" int main() { Sqlist L; int e = 0, number=0,locat =0,elect=0; int ret;//存放返回值 printf("请先创建一个含有10个整型元素的顺序表！\n"); Initlist_Sq(L); do { elect=Print_Sq(L); switch (elect) { case 0: break; case 1://插入 printf("请输入你想添加的位置和数字（用空格隔开）："); scanf_s("%d%d",&number,&locat); ListInsert_Sq(L, number, locat); break; case 2://删除 printf("请输入你想删除数字的位置："); scanf_s("%d", &locat); listDelete_Sq(L, locat, e); printf("the delete number is %d\n", e); break; case 3://顺序查找 printf("请输入你想查找的数字："); scanf_s("%d", &number); ret=listFine1_Sq(L, locat, number); if(ret) { printf("%d在表中的位置是%d\n", number, locat); 数据结构实验报告一 题目：线性表的应用举例班级：信息一班 姓名：冯琴琴 学号： 120108010001 得分： 实验一线性表的应用举例 1. 求两个线性表La和Lb的并集 La = La U Lb 2. 已知线性表La和Lb中的数据元素按值非递减有序排列，要求将La和Lb归并成一个新的线性表Lc，且Lc中的数据元素仍按值非递减有序排列。 #include 学 《数据结构》课程 实验报告 实验名称：线性表基本操作的实现实验室(中心)： 学生信息： 专业班级： 指导教师： 实验完成时间： 2016 实验一线性表基本操作的实现 一、实验目的 1.熟悉C语言的上机环境，进一步掌握C语言的结构特点。 2.掌握线性表的顺序存储结构的定义及C语言实现。 3.掌握线性表的链式存储结构——单链表的定义及C语言实现。 4.掌握线性表在顺序存储结构即顺序表中的各种基本操作。 5.掌握线性表在链式存储结构——单链表中的各种基本操作。 二、实验内容及要求 1.顺序线性表的建立、插入、删除及合并。 2.链式线性表的建立、插入、删除及连接。 三、实验设备及软件 计算机、Microsoft Visual C++ 6.0软件 四、设计方案（算法设计） ㈠采用的数据结构 本程序顺序表的数据逻辑结构为线性结构，存储结构为顺序存储；链表的数据逻辑结构依然为线性结构，存储结构为链式结构。 ㈡设计的主要思路 1.建立含n个数据元素的顺序表并输出该表中各元素的值及顺序表的长度，顺序表的长度和元素由用户输入； 2.利用前面建立的顺序表，对顺序表进行插入、删除及合并操作； 3.建立一个带头结点的单链表，结点的值域为整型数据，链表的元素由用户输入； 4.对前面建立的链表进行插入、删除及连个链表的连接操作； ㈢算法描述 1、顺序表 void Init(sqlist &);//初始化顺序表 BOOL Inse(sqlist &,int,char); //在线性表中插入元素 BOOL del(sqlist&,int,char &); //在线性表中删除元素 int Loc(sqlist,char); //在线性表中定位元素 void print(sqlist); //输出顺序表 void combine( sqlist & , sqlist & , sqlist &);//两个线性表的合并 2、链表 void CreaL(LinkList &,int); //生成一个单链表 BOOL LInsert(LinkList &,int,char); //在单链表中插入一个元素 BOOL LDele(LinkList &,int,char &); //在单链表中删除一个元素 BOOL LFind_key(LinkList,char,int &); //按关键字查找一个元素 BOOL LFind_order(LinkList,char &,int); //按序号查找一个元素 void LPrint(LinkList); //显示单链表所有元素 void LUnion(LinkList &,LinkList &,LinkList &,int); //两个链表的连接 五、程序代码 1、顺序表 #include 实验报告二线性表 一、实验目的： （1）理解线性表的逻辑结构、两种存储结构和数据操作； （2）应用顺序表的基本算法实现集合A=AUB算法，应用顺序表的基本算法实现两有序顺序表的归并算法；（单链表的归并算法） （3）掌握单链表的遍历、插入和删除等操作算法，实现多项式相加。 二、实验容： 1、设有线性表LA＝（3,5,8,11）和LB=（2,6,8,9,11,15,20）； ①若LA和LB分别表示两个集合A和B，求新集合 A＝A U B（‘并’操作，相同元素不保留）； 预测输出：LA=（3,5,8,11,2,6,9,15,20） 实现代码： package Q1_1; public class Node实验1__线性表的应用
数据结构线性表实验报告
实验一 线性表的基本操作实现及其应用
201560140140--袁若飞--实验1：线性表的基本操作及其应用
实验二 线性表(顺序存储)
实验1 线性表及其应用
实验一线性表与应用(I)
实验一 线性表的基本操作
《数据结构》实验一 线性表及其应用
实验一 线性表操作实验题目
数据结构_实验1_线性表的基本操作
数据结构《线性表的应用》实验报告
线性表实验报告
数据结构实验一题目一线性表实验报告
数据结构线性表的应用实验报告
数据结构_实验二_线性表及其实现
线性表的应用举例实验报告(燕山大学)
数据结构实验线性表基本操作
实验二线性表