下载文档原格式
实验1线性表及其应⽤实验报告暨南⼤学本科实验报告专⽤纸课程名称数据结构成绩评定实验项⽬名称线性表及其应⽤指导教师王晓明实验项⽬编号实验⼀实验项⽬类型综合性实验地点南海楼601 学⽣姓名朱芷漫学号2010051875学院信息科学技术学院系计算机专业计算机科学与技术实验时间2011年9⽉7⽇18:30午～9⽉7⽇20:30午温度℃湿度⼀、实验⽬的和要求实验⽬的：熟练掌握线性表基本操作的实现及应⽤实验要求：在上机前写出全部源程序完毕并调试完毕。
⼆、实验原理和主要内容1.建⽴4个元素的顺序表SqList={2，3，4，5}，实现顺序表的基本操作；在SqList={2,3,4,5}的元素4与5之间插⼊⼀个元素9，实现顺序表插⼊的基本操作；在SqList={2,3,4,9,5}中删除指定位置(i=3)上的元素，实现顺序表删除的操作。
2.利⽤顺序表完成⼀个班级的⼀个学期的课程的管理：能够增加、删除、修改学⽣的成绩记录。
三、主要仪器设备PC机，Windows XP操作平台，Visual C++四、调试分析学⽣课程管理系统的调试过程中发现⼀些错误，主要是参数设置的问题，经过修改，错误得到排除。
五、测试结果1.顺序表2.学⽣课程管理系统附录（源程序）1.顺序表的操作#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_SIZE 10 #define LISTINCREMENT 2 typedef struct shunxubiao{ElemType *list;int size;int Maxsize;}SqList;int InitList_Sq(SqList &L) {// 构造⼀个空的线性表L。
1 线性表及其应用问题：约瑟夫环问题描述：编号为1，2，…，n的n个人按顺时针方向围坐一圈。
每人持有一个密码(正整数)，一开始任选一个正整数作为报数上限值m，从第一个人开始按顺时针方向自1开始报数，报到m时停止报数。
报m的人出列，将他的密码作为新的m值，从他顺时针方向的下一个人开始重新从1报数，直至所有人全部出列为止。
试设计一个程序求出出列顺序。
基本要求：利用单向循环链表存储结构模拟此过程。
2 栈和队列及其应用题目：魔王语言解释问题描述：有一个魔王总是使用自己的一种非常精练而抽象的语言讲话，没有人能听的懂，但他的语言是可以逐步解释成人能听懂的语言，因为他的语言是由以下两种形式的规则由人得语言逐步抽象上去的：（1）α→β1β2…βm（2）(θδ1δ2…δn)→θδnθδn-1…θδ1θ在这两种形式中，从左到有均表示解释。
试写一个魔王语言的解释系统，把他的话解释成人能听的懂的话。
基本要求：用下述两条具体规则和上述规则形式（2）实现。
设大写字母表示魔王语言的词汇；小写字母表示人的语言词汇；希腊字母表示可以用大写字母或小写字母代换的变量。
魔王语言可含人的词汇。
（1）B→tAdA（2）A→sae3 串及其应用题目：文学研究助手问题描述：存在一篇英文文章(以串表示)，以及若干关键字。
编写程序统计关键字的出现次数。
基本要求：改进KMP算法以适应多关键字匹配。
4 数组和广义表题目：数组转置问题描述：存在稀疏矩阵A，编写程序将A转置为B。
基本要求：用三元组表示稀疏矩阵，应用算法5.2完成转置。
5 树、图及其应用题目：Huffman编/译码器问题描述：使用Huffman编码进行通信可以节省通信成本。
对于双工系统而言，要求在发送端和接受端均有编码器和译码器。
试为该系统设计一个编/译码器。
基本要求：至少具有功能（1）初始化（2）编码（3）译码（4）打印代码。
6 存储管理、查找和排序题目：内部排序算法比较问题描述：通过随机数据比较各算法的关键字比较次数与移动次数。
浙江大学城市学院实验报告课程名称数据结构与算法实验项目名称实验一线性表应用---多项式计算实验成绩指导老师（签名）日期一.实验目的和要求1．进一步掌握线性表的的基本操作。
2．掌握线性表的典型应用----多项式表示与计算。
二. 实验内容1．设用线性表( (a1, e1), (a2, e2), ……, (am, em) ) 表示多项式P(x) = a1*x e1 + a2*x e2+…+ am*x em，其中：a1～am为非零系数，0≤e1＜e2＜…..＜em，请编写用链式存储结构（带表头附加结点的单链表）存储该多项式时，多项式基本操作的实现函数。
多项式基本操作应包括初始化多项式、清除多项式、输出多项式、插入一项、删除一项、多项式求值、多项式相加等。
要求：把多项式线性表的结构定义及多项式基本操作实现函数存放在头文件Linkpoly.h中，主函数存放在主文件test6_1.cpp中，在主函数中通过调用Linkpoly.h中的函数进行测试。
2．选做：编写用顺序存储结构存储多项式时，多项式基本操作的实现函数。
要求：把多项式线性表的结构定义及多项式基本操作实现函数存放在文件Seqpoly.h中，在主文件test6_1.cpp中增加测试语句对Seqpoly.h中的函数进行测试。
3．填写实验报告，实验报告文件取名为report1.doc。
4．上传实验报告文件report1.doc与源程序文件test6_1.cpp及Linkpoly.h、Seqpoly.h（若有）到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路包括每个函数的功能说明，及一些重要函数的算法实现思路※注1：除了[多项式求值]与[多项式相加]两个函数外，线性表的基本操作函数，大部分沿用上学期[线性表的链式/顺序表示和实现]两个实验中的函数。
※注2：选作部分函数功能与思路与非选作部分基本一致，略去思路描述函数：void InitList(LNode *&H)功能：初始化单链表思路：使用附带头结点的方式初始化单链表函数：int LengthList (LNode *H)功能：求单链表长度思路：遍历整个单链表，设置变量记录并返回它的长度函数：bool EmptyList (LNode *H)功能：判断单链表是否为空表思路：判断头结点的后一结点是否为空，若空则为空表函数：void TraverseList(LNode *H)功能：遍历单链表思路：遍历整个单链表，输出所含所有元素函数：bool InsertList ( LNode *&H, ElemType item, int pos)功能：向单链表插入一个元素思路：创建新结点，根据pos的值来确定位置并向单链表中插入新元素。
实验1 线性表及其应用实验性质：验证性实验学时：2学时一、实验目的1.掌握线性表的顺序存储结构在计算机的表示方法及其基本操作的实现；2.掌握线性表的链式存储结构在计算机的表示方法及其基本操作的实现；3.能够利用线性表结构对实际问题进行分析建模，利用计算机求解。
二、实验预备知识1.复习C/C++语言相关知识（如：结构体的定义、typedef的使用、函数的定义、调用及参数传递方式）；2.阅读并掌握顺序表与链表的类型定义及其查找、插入、删除等基本操作。
三、实验内容1.理解并分别用顺序表、链表的操作运行下列程序：#include <iostream>using namespace std;#include "Status.h"typedef int ElemType;#include "SqList.h" //用#include "LinkList.h"替换void main(){SqList L; //用LinkList L;替换，与#include "LinkList.h"配合int n,i;ElemType e;InitList(L);cout<<"\nL=";ListTraverse(L);cout<<"\n请设置将向线性表L中输入的元素个数：";cin>>n;CreateList(L,n);cout<<"\nL=";ListTraverse(L);cout<<"\nL的表长为："<<ListLength(L)<<endl;cout<<"\n请输入想要获取的元素位序：";cin>>i;if(GetElem(L,i,e)) cout<<"\n第"<<i<<"个元素为："<<e<<endl;else cout<<"\n第"<<i<<"个元素不存在！"<<endl;cout<<"\n请输入要查找的元素：";cin>>e;if(i=LocateElem(L,e)) cout<<"\n元素"<<e<<"的位置为："<<i<<endl;else cout<<"\n元素"<<e<<"不存在！"<<endl;cout<<"\n请输入插入位置和所插入元素：";cin>>i>>e;if(ListInsert(L,i,e)){cout<<"\nL=";ListTraverse(L);}else cout<<"\n插入操作失败！"<<endl;cout<<"\n请输入被删元素的位置：";cin>>i;if(ListDelete(L,i,e)) cout<<"\n被删元素为："<<e<<endl;else cout<<"\n删除操作失败！"<<endl;cout<<"\nL=";ListTraverse(L);}本题目说明：（1）头文件Status.h的内容如下：#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;（2）头文件SqList.h（内容包括顺序表的结构定义及基本操作实现）。
数据结构实验报告实验一线性表的应用一、实验目的：1．掌握线性表的两种存储结构及实现方式；2．熟练掌握顺序表和链表的建立、插入和删除的算法。
二、实验要求：1．C完成算法设计和程序设计并上机调试通过。
2．撰写实验报告，提供实验结果和数据。
3．写出算法设计小结和心得。
三、实验内容：1．用顺序表表示集合，编写程序以实现集合的交、并、差运算。
2．设带头结点的单链表ha和hb中结点数据域值按从小到大顺序排列，且各自链表内无重复的结点，要求：（1）建立两个按升序排列的单链表ha和hb。
（2）将单链表ha合并到单链表hb中，且归并后的hb链表内无重复的结点，结点值仍保持从小到大顺序排列。
（3）输出合并后单链表hb中每个结点的数据域值。
四、程序源代码：1.#include<stdio.h>#include<stdlib.h>#define LIST_INIT_CAPACITY 100 typedef int ElementType;typedef struct List{ElementType elem[LIST_INIT_CAPACITY]; int nLength;}SqList;void init(struct List*L)//初始化顺序表{if(L)L->nLength=0;}int visit(SqList*L,ElementType e)//遍历顺序表{for(int i=0;i<L->nLength;i++){if(L->elem[i]==e){return 0;break;}elsecontinue;return 1;}}SqList*jiao(SqList*L1,SqList*L2,SqList*L3)//求两个集合的交集{int n=0;for(int i=0;i<L1->nLength;i++){for(int j=0;j<L2->nLength;i++){if(L1->elem[i]==L2->elem[j]){L3->elem[n]=L1->elem[i];n++;}elsecontinue;}}printf("集合的交集：\n");return L3;}SqList*bing(SqList*L1,SqList*L2,SqList*L3)//求两个集合的并集{int j=0;for (int i=0;i<L1->nLength;i++){if (visit(L2,L1->elem[i])){L3->elem[j]=L1->elem[i];L3->nLength++;j++;}elsecontinue;}printf("集合的并集：\n");return L3;}SqList*cha(SqList*L1,SqList*L2,SqList*L3)//求两个集合的差集{int j=0;for(int i=0;i<L1->nLength;i++){if(visit (L2,L1->elem[i])){L3->elem[j]=L1->elem[i];j++;L3->nLength++;}elsecontinue;}printf("集合的差集：\n");return L3;}void show(SqList *list)//显示线性表元素{for (int i=0;i<list->nLength;i++){printf(" %d",list->elem[i]);}printf("\n");}void main(){SqList*list1,*list2,*list3;list1=(SqList*)malloc(sizeof(SqList));list2=(SqList*)malloc(sizeof(SqList));list3=(SqList*)malloc(sizeof(SqList));init(list1);init(list2);init(list3);intstr1[6]={1,2,3,4,5,6},str2[7]={1,3,4,5,7,9,10};for(int i=0;i<6;i++){list1->elem[i]=str1[i];list1->nLength=i+1;}for(i=0;i<7;i++){list2->elem[i]=str2[i];list2->nLength++;}printf("初始集合：\n");show(list1);show(list2);list3=jiao(list1,list2,list3);show(list3);init(list3);list3=bing(list1,list2,list3);show(list3);init(list3);list3=cha(list1,list2,list3);show(list3);}2.#include <stdio.h>#include<stdlib.h>typedef int ElementType;typedef struct ListNode{ElementType data;struct ListNode *next;}sLinkList;sLinkList*create(ElementType i)//创建接点{sLinkList *p;p=(sLinkList*)malloc(sizeof(sLinkList));if(!p)exit(0);elsep->data=i;return p;}void anotherorder(sLinkList*head){sLinkList*P;P=head->next;if(head!=NULL)//头指针不为空{while (P->next!=NULL){sLinkList*q;//p的后继指针sLinkList*t;q=P->next;t=P->next->next;q->next=head->next;head->next=q;P->next=t;}}}void print(sLinkList*head)//输出链表{if(head==NULL){exit(0);}sLinkList*p=head->next;while(p!=NULL){printf("%4d",p->data);p=p->next;}printf("\n");}void hebing(sLinkList *p,sLinkList *q,sLinkList *l)//将两个链表合并{ sLinkList*z;q=q->next;l=l->next;while(q!=NULL&&l!=NULL){if(q->data>l->data){z=create(l->data);p->next=z;z->next=NULL;p=z;l=l->next;}elseif(q->data<l->data){z=create(q->data);p->next=z;z->next=NULL;p=z;q=q->next;}elseif(q->data==l->data){for(int i=0;i<2;i++){z=create(q->data);p->next=z;z->next=NULL;p=z;}q=q->next;l=l->next;}}if(q==NULL){while (l!=NULL){z=create(l->data);p->next=z;z->next=NULL;p=z;l=l->next;}}if(l==NULL){while (q!=NULL){z=create(q->data);p->next=z;z->next=NULL;p=z;q=q->next;}}printf("合并后：\n");}void deletelist(sLinkList*p)//删除多余元素节点{if(p!=NULL)p=p->next;sLinkList*q;//中间指针while (p!=NULL){int i=p->data;sLinkList*head=p;while (head->next!=NULL){if(i==head->next->data){q=head->next;head->next=q->next;free(q);}elsehead=head->next;}p=p->next;}printf("最终结果：\n");}void main(){sLinkList *ha; ha=(sLinkList*)malloc(sizeof(ListNode)); if(ha!=NULL)//判空{ha->next=NULL;ha->data=-1;}sLinkList *p;sLinkList *q=ha;int a[5]={2,4,6,8,10};for (int i=0;i<5;i++){p=create(a[i]);q->next=p;p->next=NULL;q=p;}printf("初始：\n");print(ha);sLinkList *hb;hb=(sLinkList*)malloc(sizeof(ListNode)); if(hb!=NULL)//判空{hb->next=NULL;hb->data=-1;}q=hb;int b[6]={1,4,5,8,9,10};for (i=0;i<6;i++){p=create(b[i]);q->next=p;p->next=NULL;q=p;}print(hb);//构建ha,hbsLinkList *hc;hc=(sLinkList*)malloc(sizeof(ListNode)); hebing(hc,ha,hb);print(hc);deletelist(hc);print(hc);}五、测试结果：1.2.六、小结（包括收获、心得体会、存在的问题及解决问题的方法、建议等）经过这次实验，我对线性表的两种形式顺序表和链表有了进一步的了解，对线性表之间的运算及线性表的简单应用有了更深的体会。
计算机系数据结构实验报告（1）实验目的：帮助学生掌握线性表的基本操作在顺序和链表这两种存储结构上的实现，尤以链表的操作和应用作为重点。
问题描述：1、构造一个空的线性表L。
2、在线性表L的第i个元素之前插入新的元素e；3、在线性表L中删除第i个元素，并用e返回其值。
实验要求：1、分别利用顺序和链表存储结构实现线性表的存储，并设计出在不同的存储结构中线性表的基本操作算法。
2、在实验过程中，对相同的操作在不同的存储结构下的时间复杂度和空间复杂度进行分析。
算法分析：由于两种存储结构都用来创建线性结构的数据表，可采用相同的输出模式和整体结构类似的算法，如下：v1.0 可编辑可修改实验内容和过程：顺序存储结构线性表程序清单：//顺序存储结构线性表的插入删除#include <iostream>#include <>using namespace std;# define LISTSIZE 100# define CREMENTSIZE 10typedef char ElemType; //定义数据元素类型为字符型typedef struct {ElemType *elem; //数据元素首地址int len; //当前元素个数int listsize; //当前存储最大容量}SqList;//构造一个空的线性表Lint InitList(SqList &L){=(ElemType *)malloc(LISTSIZE*sizeof(ElemType));if (! exit(-2); //分配空间失败=0;=LISTSIZE;}//在顺序线性表L中第i个位置之前插入新的元素eint ListInsert(SqList &L,int i,ElemType e){if (i<1||i>+1) return -1; //i值不合法if >={ElemType *newelem=(ElemType *)realloc,+CREMENTSIZE)*sizeof(ElemType));//存储空间已满，增加分配if(!newelem) exit (-2); //分配失败=newelem;+=CREMENTSIZE;}ElemType *q=&[i-1]) ;for (ElemType *p=&[]);p>=q;--p) *(p+1)=*p; //插入位置及其后的元素后移 *q=e; ++;return 1;}//在顺序线性表L中删除第i个元素，并用e返回其值int ListDelete(SqList &L,int i,ElemType&e){if (i<1||i> return -1; //i值不合法ElemType *p=&[i-1]);e=*p; ElemType*q=+;for (++p;p<=q+1;++p) *(p-1)=*p; //被删除元素之后的元素前移;return 1;}int main (){SqList L; char e,ch;int i,j,state;InitList(L); //构造线性表printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化gets;for ( j=1;[j-1]!='\0';j++) =j; //获取表长[j]='\0';printf("操作：插入（I）还是删除(D)\n"); //判断进行插入还是删除操作AGAIN:cin>>ch;if(ch=='I'){cout<<"插在第几个元素之前:"; //插入操作cin>>i; cout<<"输入要插入的新元素:";cin>>e;cout<<endl;printf("输入数据：L=(%s) ListInsert(L,%d,%c)",,i,e);state=ListInsert (L,i,e);}else if (ch=='D'){cout<<"删除第几个元素："; //删除操作cin>>i;cout<<endl;printf("输入数据：L=(%s) DeleteList(L,%d,e)",,i);state=ListDelete(L,i,e);}else goto AGAIN; //操作指示符输入错误处理cout<<endl<<"正确结果：";if(state==-1) cout<<"ERROR,";printf("L=(%s) ",; //输出结果if(ch=='D'&&state!=-1) cout<<",e="<<e;}链式存储结构线性表程序清单：// - - - - -单链存储结构线性表的插入删除 - - - - -#include <iostream>#include <>using namespace std;#define null 0typedef char ElemType; //定义数据元素类型为字符型typedef struct LNode{ElemType data;struct LNode *next;}LNode,*LinkList;int GetElem(LinkList L,int i,ElemType &e) //获取第i个元素的值 {LinkList p;int j;p=L->next; j=1;while(p&&j<i){p=p->next; ++j; //寻找第i个元素}if(!p||j>i) return -1; //寻找失败e=p->data;return 1;}int ListInsert(LinkList &L,int i,ElemType e){//在带头结点的单链线性表L中第i个元素之前插入元素eLinkList p,s; int j;p=L;j=0;while(p&&j<i-1) {p=p->next;++j;}if(!p||j>i-1) return -1;s=(LinkList) malloc( sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return 1;}int ListDelete(LinkList&L,int i,ElemType&e){//在带头结点的单链线性表L中,删除第i个元素，并由e返回其值LinkList p,q; int j;p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}if(!(p->next)||j>i-1) return -1;q=p->next;p->next=q->next;e=q->data;free(q);return 1;}int newdata(LinkList&L,char *ch){int k;printf("请输入原始数据(字符串个数0~99)：L="); //数据初始化gets(ch);for (k=0;ch[k]!='\0';k++) ListInsert(L,k+1, ch[k]); //将初始化数据插入链表L中cout<<"OK"<<endl;return k; //返回链表中的元素个数}int main (){char *ch;ch=(char *)malloc(100*sizeof(char)); //定义数组用来辅助数据初始化LinkList L; //头指针LNode head; //头结点L=&head; =null;int i,k,state; char e,CH,f;k=newdata(L,ch); //调用函数使链表数据初始化=k; //将元素个数存入头结点的数据域printf("操作：插入（I）还是删除(D)\n"); //判断进行插入还是删除操作AGAIN:cin>>CH;if(CH=='I'){cout<<"插在第几个元素之前:"; //插入操作cin>>i; cout<<"输入要插入的新元素:";cin>>e;cout<<endl;printf("输入数据：L=(%s) ListInsert(L,%d,%c)",ch,i,e);state=ListInsert(L,i,e);++;}else if (CH=='D'){cout<<"删除第几个元素："; //删除操作cin>>i;cout<<endl;printf("输入数据：L=(%s) DeleteList(L,%d,e)",ch,i);state=ListDelete(L,i,e);--;}else goto AGAIN; //操作指示符输入错误处理cout<<endl<<"正确结果：";if(state==-1) cout<<"ERROR,"; //输出结果cout<<"L=(";for(int m=1;>=m;m++) //一一输出数据{GetElem(L,m,f);cout<<f;}cout<<")";if(CH=='D'&&state!=-1) cout<<",e="<<e; //删除操作反馈e }实验结果：由于两个程序的输出模式相同，在此只列一组测试数据：L = () ListInsert (L, 1, 'k')L = (EHIKMOP) ListInsert (L, 9, 't')L = (ABCEHKNPQTU) ListInsert(L, 4, 'u') L = () ListDelete (L, 1, e)L = (DEFILMNORU) ListDelete_Sq(L, 5, e) L = (CD) ListDelete_Sq(L, 1, e)测试过程中所注意到的问题主要还是输出与输入界面的问题，通过灵活使用cout和cin函数来不断改进。
实验报告实验项目：线性表的运用实验器材: Vc++6.0编程工具系别: 电子信息工程系学号: 0632323姓名: 赵烨昕实验日期: 2008.10.17指导老师:______________________张玲_________________________________ 实验成绩:____________________________________________________________实验一线性表的应用一.实验目的：掌握线性链表的存储、运算及应用。
利用链表实现一元多项式计算。
二.实验步骤：（1）编写函数，实现用链表结构建立多项式；（2）编写函数，实现多项式的加法运算；（3）编写函数，实现多项式的显示；（4）测试：编写主函数，它定义并建立两个多项式，显示两个多项式，然后将它们相加并显示结果。
变换测试用的多项式，检查程序的执行结果。
三.程序清单：#include <stdio.h>#include <malloc.h>typedef struct node{ float coef; /*序数*/int expn; /*指数*/struct node *next; /*指向下一个结点的指针*/} PolyNode;void InitList(PolyNode *&L) /*初始化多项式单链表*/{L=(PolyNode *)malloc(sizeof(PolyNode)); /*建立头结点*/L->next=NULL;}int GetLength(PolyNode *L) /*求多项式单链表的长度*/{int i=0;PolyNode *p=L->next;while (p!=NULL) /*扫描单链表L，用i累计结点个数*/{i++;p=p->next;}return i;}PolyNode *GetElem(PolyNode *L,int i) /*返回多项式单链表中第i个结点的指针*/{int j=1;PolyNode *p=L->next;if (i<1 || i>GetLength(L))return NULL;while (j<i) /*沿next域找第i个结点*/{p=p->next;j++;}return p;}PolyNode *Locate(PolyNode *L,float c,int e) /*在多项式单链表中按值查找*/ {PolyNode *p=L->next;while (p!=NULL && (p->coef!=c ||p->expn!=e))p=p->next;return p;}int InsElem(PolyNode *&L,float c,int e,int i) /*在多项式单链表中插入一个结点*/ {int j=1;PolyNode *p=L,*s;s=(PolyNode *)malloc(sizeof(PolyNode));s->coef=c;s->expn=e;s->next=NULL;if (i<1 || i>GetLength(L)+1)return 0;while (j<i) /*查找第i-1个结点*p*/{p=p->next;j++;}s->next=p->next;p->next=s;return 1;}int DelElem(PolyNode *L,int i) /*在多项式单链表中删除一个结点*/{int j=1;PolyNode *p=L,*q;if (i<1 || i>GetLength(L))return 0;while (j<i) /*在单链表中查找第i-1个结点，由p指向它*/{p=p->next;j++;}q=p->next; /*q指向被删结点*/p->next=q->next; /*删除*q结点*/free(q);return 1;}void DispList(PolyNode *L) /*输出多项式单链表的元素值*/{PolyNode *p=L->next;while (p!=NULL){printf("(%g,%d) ",p->coef,p->expn);p=p->next;}printf("\n");}void CreaPolyList(PolyNode *&L,float C[],int E[],int n){int i;InitList(L);for (i=0;i<n;i++)InsElem(L,C[i],E[i],i+1);}void SortPloy(PolyNode *&L) /*对L的多项式单链表按expn域递增排序*/ {PolyNode *p=L->next,*q,*pre;L->next=NULL;while (p!=NULL){if (L->next==NULL) /*处理第1个结点*/{L->next=p;p=p->next;L->next->next=NULL;}else /*处理其余结点*/{pre=L;q=pre->next;while (q!=NULL && p->expn>q->expn) /*找q->expn刚大于或等于p->expn的结点*q的前驱结点*pre*/{pre=q;q=q->next;}q=p->next; /*在*pre结点之后插入*p*/p->next=pre->next;pre->next=p;p=q;}}}PolyNode *AddPoly(PolyNode *pa,PolyNode *pb){PolyNode *pc,*p1=pa->next,*p2=pb->next,*p,*tc,*s;pc=(PolyNode *)malloc(sizeof(PolyNode)); /*新建头结点*pc*/ pc->next=NULL; /*pc为新建单链表的头结点*/tc=pc; /*tc始终指向新建单链表的最后结点*/while (p1!=NULL && p2!=NULL){if (p1->expn<p2->expn) /*将*p1结点复制到*s并链到pc尾*/{s=(PolyNode *)malloc(sizeof(PolyNode));s->coef=p1->coef;s->expn=p1->expn;s->next=NULL;tc->next=s;tc=s;p1=p1->next;}else if (p1->expn>p2->expn) /*将*p2结点复制到*s并链到pc尾*/{s=(PolyNode *)malloc(sizeof(PolyNode));s->coef=p2->coef;s->expn=p2->expn;s->next=NULL;tc->next=s;tc=s;p2=p2->next;}else /*p1->expn=p2->expn的情况*/{if (p1->coef+p2->coef!=0) /*序数相加不为0时新建结点*s并链到pc尾*/{s=(PolyNode *)malloc(sizeof(PolyNode));s->coef=p1->coef+p2->coef;s->expn=p1->expn;s->next=NULL;tc->next=s;tc=s;}p1=p1->next;p2=p2->next;}}if (p1!=NULL) p=p1; /*将尚未扫描完的余下结点复制并链接到pc单链表之后*/else p=p2;while (p!=NULL){s=(PolyNode *)malloc(sizeof(PolyNode));s->coef=p->coef;s->expn=p->expn;s->next=NULL;tc->next=s;tc=s;p=p->next;}tc->next=NULL; /*新建单链表最后结点的next域置空*/return pc;}void main(){PolyNode *L1,*L2,*L3;float C1[]={3,6,5,7},C2[]={-9,8,11};int E1[]={2,0,15,4},E2[]={9,1,6};InitList(L1);InitList(L2);InitList(L3);CreaPolyList(L1,C1,E1,4);CreaPolyList(L2,C2,E2,3);printf("两多项式相加运算\n");printf(" 原多项式A:");DispList(L1);printf(" 原多项式B:");DispList(L2);SortPloy(L1);SortPloy(L2);printf("排序后的多项式A:");DispList(L1);printf("排序后的多项式B:");DispList(L2);L3=AddPoly(L1,L2);printf("多项式相加结果:");DispList(L3);}实验结果如下：选作题：从终端输入多项式实现多项式相加。
实验一线性表的建立与应用一实验目的：通过实验，了解并掌握线性表逻辑特性和物理特性，了解并掌握队列和栈的运算方法，培养结合理论知识进行实际应用的实践能力。
二实验内容：队列示意图队列也是一种运算受限制的线性表，它的运算包括：初始化队、入队、退队、读取队首和队尾的数据。
当队列为空时不允许退队，当队列未满的时候不允许入队。
在实际应用中，通常使用循环队列循环队列示意图初始化循环队列四、实验步骤1 进入Turbo C 2.0，新建一个文件。
2 输入程序，程序要求使用子函数进行组织。
3 将源程序保存到指定文件夹“D:\学生姓名”。
4 按F9调试，纠正语法错误。
5按Ctrl＋F9运行，调试逻辑错误。
6 按Alt＋F5查看结果。
五、实验中应注意的问题与思考题：五、实验中应注意的问题与思考题：1 在对栈和队列的运算过程中保证数据结构的逻辑完整性。
2 栈和循环队列元素的打印。
在打印过程中应该正确分析循环队列的具体情况，做到正确打印。
3 栈与队列均不允许在中间插入数据，保证运算的正确性；线性队列不能重复使用，不符合流程化要求，应采取循环队列。
4 当栈满，而此时要进行退队入栈运算时应进行怎样的处理才能避免数据的丢失？退队入栈时，判断栈是否为满：若为满，则把数据存到其他地方。
5 当队列满，而此时要进行退栈入队运算时应进行怎样的处理才能避免数据的丢失？退栈入队时，判断队列是否为满：若为满，则把数据存到其他地方。
6 应用程序要求循环执行，每次运算结束后要求打印栈和队列中的元素，以查看结果。
7 对各个功能模块采用独立编制子函数，增强程序的可执行性、可移植性和可读性。
增加情报信息量，对实际应用中可能发生的情况考虑周全，对非法情形要提出适当的处理方案。
六、源程序#include "stdlib.h"#include "stdio.h"void push(s,m,top,x) /*******入栈************/int s[],x; int m,*top;{if(*top==m) {printf("栈上溢\n");return;}*top=*top+1;s[*top-1]=x;return;}void pop(s,m,top,y) /************退栈************/int s[],*y; int m,*top;{if(*top==0) {printf("栈下溢\n");return;}*y=s[*top-1];*top=*top-1;return;}out_s(s,m,top) /************输出栈内元素******************/int s[],m,*top;{int *q;q=s+*top-1;printf("输出栈内元素: ");if(q>=s)while(q>=s){ printf("%d ",*(q--)); }else printf("没有元素!!!");printf("\n"\n ");return;}void addcq(q,m,rear,front,s,x) /**************入队******************/int q[],x; int m,*rear,*front,*s;{if((*s==1)&&(*rear==*front)){printf("队列上溢\n");return;}*rear=*rear+1;if(*rear==m+1) *rear=1;q[*rear-1]=x;*s=1;return;}void delcq(q,m,rear,front,s,y) /**************退队*****************/int q[],*y; int m,*rear,*front,*s;{if(*s==0) {printf("队列下溢\n");return;}*front=*front+1;if(*front==m+1) *front=1;*y=q[*front-1];if(*front==*rear) *s=0;return;}out_q(q,m,front,rear,s) /******************输出队内元素******/ int q[],m,*front,*rear,*s;{int k;k=(*front)%m;*front=(*front)%m;*rear=(*rear)%m;printf("输出队列内元素: ");if(*s==1){if(*front<*rear)while(k<*rear){ printf("%d ",q[k]);k++;}else{while(k<=m-1){ printf("%d ",q[k]);k++;}k=0;while(k<*rear){ printf("%d ",q[k]);k++;}}}else { printf("没有元素!!!"); }printf("\n\n ");}main(){int x,y,z,m,n,*s,*q,top,rear,front,l,i,k,j;l=0;m=5;n=5;s=malloc(m*sizeof(int));q=malloc(n*sizeof(int));top=0;rear=n;front=n;printf("输入0, 退出\n");printf("输入1, 压栈\n");printf("输入2, 入队\n");printf("输入3, 弹栈\n");printf("输入4, 退队\n");printf("输入5, 弹栈入队\n");printf("输入6, 退队压栈\n");printf("输入0-6:");scanf("%d",&y);for(;y!=0;){switch(y){case 1:{printf("输入压栈元素\n");scanf("%d",&x);push(s,m,&top,x);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}case 2: {printf("输入入队元素");scanf("%d",&y);addcq(q,n,&rear,&front,&l,y);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}case 3:{pop(s,m,&top,&i);out_s(s,m,&top) ;out_q(q,n,&front,&rear,&l);break;}case 4: {delcq(q,n,&rear,&front,&l,&k);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}case 5:{if(top==0){ pop(s,m,&top,&i);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}pop(s,m,&top,&i);addcq(q,n,&rear,&front,&l,i);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}case 6:{if(l==0){ delcq(q,n,&rear,&front,&l,&k);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}delcq(q,n,&rear,&front,&l,&k);push(s,m,&top,k);out_s(s,m,&top);out_q(q,n,&front,&rear,&l);break;}default:break;}printf("输入0, 退出\n");printf("输入1, 压栈\n");printf("输入2, 入队\n");printf("输入3, 弹栈\n");printf("输入4, 退队\n");printf("输入5, 弹栈入队\n");printf("输入6, 退队压栈\n");printf("输入0-6:");scanf("%d",&y);}free(q);free(s);}七、实验总结通过实验，了解并掌握了线性表逻辑特性和物理特性，了解并掌握了队列和栈的运算方法，培养了结合理论知识进行实际应用的实践能力，受益匪浅。
实验一_线性表操作_实验报告实验一：线性表操作一、实验目的1.理解线性表的基本概念和特点。
2.掌握线性表的基本操作，包括插入、删除、查找等。
3.通过实验，提高动手能力和解决问题的能力。
二、实验原理线性表是一种较为常见的数据结构，它包含零个或多个数据元素，相邻元素之间有前后关系。
线性表具有以下特点：1.元素之间一对一的顺序关系。
2.除第一个元素外，每个元素都有一个直接前驱。
3.除最后一个元素外，每个元素都有一个直接后继。
常见的线性表有数组、链表等。
本实验主要针对链表进行操作。
三、实验步骤1.创建链表：首先创建一个链表，并给链表添加若干个节点。
节点包括数据域和指针域，数据域存储数据，指针域指向下一个节点。
2.插入节点：在链表中插入一个新的节点，可以选择在链表的头部、尾部或中间插入。
3.删除节点：删除链表中的一个指定节点。
4.查找节点：在链表中查找一个指定数据的节点，并返回该节点的位置。
5.遍历链表：从头节点开始，依次访问每个节点的数据。
四、实验结果与分析1.创建链表结果：我们成功地创建了一个链表，每个节点都有数据域和指针域，数据域存储数据，指针域指向下一个节点。
2.插入节点结果：我们成功地在链表的头部、尾部和中间插入了新的节点。
插入操作的时间复杂度为O(1)，因为我们只需要修改指针域即可。
3.删除节点结果：我们成功地删除了链表中的一个指定节点。
删除操作的时间复杂度为O(n)，因为我们可能需要遍历整个链表才能找到要删除的节点。
4.查找节点结果：我们成功地在链表中查找了一个指定数据的节点，并返回了该节点的位置。
查找操作的时间复杂度为O(n)，因为我们可能需要遍历整个链表才能找到要查找的节点。
5.遍历链表结果：我们成功地遍历了整个链表，并访问了每个节点的数据。
遍历操作的时间复杂度为O(n)，因为我们可能需要遍历整个链表。
通过本次实验，我们更加深入地理解了线性表的基本概念和特点，掌握了线性表的基本操作，包括插入、删除、查找等。
集美大学数据结构课程实验报告课程名称：数据结构班级：实验成绩：指导教师：吴晓晖姓名：实验项目名称：实验1--线性表及其应用学号：上机实践日期：一、目的理解线性表数据结构及其应用；二、实验内容1．线性表的抽象数据类型的定义2．线性表存储映像---顺序表类定义(包括方法实现)及测试（要求：main中要测试每个方法）测试如下：定义一个顺序表，最大50,存储以下数据元素(1,-9,6,10,400,30,60),输出之。
查找的测试如下：元素30存在否，测试元素67存在否。
插入测试如下：在表的第5个位置插入元素值为12，在第10个元素后插入元素值为18。
删除测试:……。
.3．线性表存储映像—链表的类定义(包括方法实现)及测试（要求：main中要测试每个方法）4．使用顺序表实现有序集合的合并，并分析其时间与空间复杂度。
测试LA('a,e,g,h,x,y )与LB(c,d,e,r)的合并并输出。
5．使用链表实现一元多项式运算，并测试以下两个一元多项的加法，输出实现加法后的结果表示。
并分析其时间与空间复杂度pa=1+10x3-2x100+1000x1300,pb=-1+13x15+2x100-10x10106．设计一个循环链表类，完成约瑟夫问题的解决。
测试共10个人围成一圈，每个人都有一个表示其身份的号牌，从第1个人开始报数，报到3的人出列，求出列的号牌顺序。
可简化用1….10分别表示第1个人至第10个人的号牌。
三、实验使用环境VC++ 6.0控制台程序附：文件—新建---项目（选项卡）--选择console application，给项目名四、实验关键代码与结果展示（部分截图）查找测试：五、附录（代码）。
数据结构实验
实验一线性表及其应用
一、实验目的
1、掌握用上机调试线性表的基本方法；
2、掌握线性表的基本操作，插入、删除、查找，以及线性表在顺序存储结构上的
应用。
3、按要求完成实验报告
二、实验环境
硬件：PC 微型计算机、256M以上内存，40G以上硬盘。
软件：Windows XP，VC或
三、实验内容
定义一个可以存放学生元素的有序顺序表。
学生元素中包含两个数据项：姓名，成绩。
注意顺序表以学生成绩有序存放。
要求完成一个程序，能添加、删除学生元素，并显示顺序表中所有元素。
四、实验步骤
1、编写程序，定义学生类Student，记录两个数据项：姓名，成绩。
并提供构造函数。
2、
在此基础上添加三个学生，一个分数为45，一个分数为88，一个分数为75。
检查学生添加后顺学表中的学生信息是否还以成绩为序非递减排列。
实验代码：
头文件函数：
c1.h
c2.h
功能函数：
Basic_Operation.cpp
主函数：
插入：
合并并按非递减排序：
删除：。
姓名学号ElemType data; //待插入元素SqList L; //定义SqList类型变量InitList_Sq(L); //初始化顺序表printf("※1. 请输入所需建立的线性表的长度：");scanf_s("%d", &LIST_MAX);printf("※2. 请录入数据：");for (i = 0; i<LIST_MAX; i++){scanf_s("%d", &(L.elem[i])); //向顺序表中输入数据++L.length; //表长自增1}printf("※3. 请选择数据的排序方式（0：递减，1：递增）：");scanf_s("%d", &DIR);if (DIR){BubbleSortList_Sq(L, INCREASE); //将顺序表递增排序printf("※4. 数据递增排列：");}else{BubbleSortList_Sq(L, DECREASE); //将顺序表递减排序printf("※4. 数据递减排列：");}PrintfList_Sq(L); //打印输出printf("\n※5. 请输入待插入的元素：");scanf_s("%d", &data);InsertSequentList_Sq(L, data); //将数据元素插入到顺序表L中printf("※6. 插入元素后的顺序表：");PrintfList_Sq(L); //打印输出InverseList_Sq(L); //将顺序表就地逆置printf("\n※7. 就地逆置后的顺序表：");PrintfList_Sq(L); //打印输出printf("\n\n");return 0;}2.头文件”ADT.h”的部分程序如下：#ifndef ADT_H_#define ADT_H_/************************************************************* 常量和数据类型预定义************************************************************//* ------函数结果状态代码------ */#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2/* ------排序方式状态------ */#define INCREASE 1 //递增#define DECREASE 0 //递减/* ------数据类型预定义------ */typedef int Status; //函数结果状态类型typedef int_bool; //bool状态类型/************************************************************* 数据结构类型定义************************************************************//************************线性表*************************//* ------顺序表数据类型定义------ */typedef int ElemType; //顺序表中元素的数据类型/* ------线性表的动态存储分配初始常量预定义------ */#define LIST_INIT_SIZE 100 //线性表存储空间的初始分配量#define LISTINCREMENT 10 //线性表存储空间的分配增量/* ------顺序存储结构类型定义------ */typedef struct{ElemType * elem; //存储空间基址int length; //当前长度int listsize; //当前分配的存储容量}SqList; //顺序表类型3.头文件”DataStructure_LinearList.h”中部分函数定义如下：#include<stdio.h>#include<malloc.h>#include"ADT.h"/** 函数原型：Status InverseList_Sq(SqList &L)* 函数功能：将线性表L就地逆置* 入口参数：结构体类型SqList的引用* 出口参数：返回函数结果状态*/Status InverseList_Sq(SqList &L){int i; //循环变量ElemType temp; //临时变量for (i = 0; i <= (L.length + 1) / 2; i++) //根据对称中心进行数据交换{temp = L.elem[i]; //缓存需要交换的数据L.elem[i] = L.elem[L.length - 1 - i]; //对称位置数据交换L.elem[L.length - 1 - i] = temp;}return OK;} //InverseList_Sq/** 函数原型：Status InsertSequentList_Sq(SqList &L, ElemType e);* 函数功能：向已经过排序的线性表L中插入元素，插入位置由数据在线性表的大小关系确定* 入口参数：结构体类型SqList的引用，待插入的数据* 出口参数：返回函数结果状态*/Status InsertSequentList_Sq(SqList &L, ElemType e){int i,j; //位序变量ElemType *p, *q; //插入位置指针ElemType *newbase; //动态存储分配新基址指针if (L.length >= L.listsize) //当存储空间已满，增加分配{newbase = (ElemType *)realloc(L.elem, (L.listsize +LISTINCREMENT)*sizeof(ElemType)); //存储再分配if (!newbase) //分配失败，返回错误return OVERFLOW;L.elem = newbase; //将新的地址指针赋值，注：另定义一个指针变量newbase,而不用L.elem，是因为防止存储分配失败，使原基址被覆盖L.listsize += LISTINCREMENT; //增加存储容量}if (L.elem[0] <= L.elem[1]) //判断此顺序表是否为递增{for (i = 0; i < L.length; i++) //顺序查找{if (e >= L.elem[i]) //判断待插入元素是否大于当前位置元素j = i; //保存当前元素位序}p = &(L.elem[j+1]); //指向满足上条件元素的后一个位置for (q = &(L.elem[L.length - 1]); q >= p; --q) //将待插入元素位*(q + 1) = *q;*p = e; //插入元素++L.length; //表长自增}else{for (i = 0; i < L.length; i++) //顺序查找{if (e <= L.elem[i]) //判断待插入元素是否小于当前位置元素j = i; //保存当前元素位序}p = &(L.elem[j + 1]); //指向满足上条件元素的后一个位置for (q = &(L.elem[L.length - 1]); q >= p; --q) //将待插入元素位置后的元素依次后移一个位置*(q + 1) = *q;*p = e; //插入元素++L.length; //表长自增}return OK;} //InsertSequentList_Sq/** 函数原型：Status BubbleSortList_Sq(SqList &L,Status direction)* 函数功能：将已有数据的线性表L进行排序，排序方式由参数direction确定* 入口参数：已建立顺序表的引用&L，排序方式direction，当direction = INC = 1时，为递增，反之则为递减* 出口参数：返回函数结果状态*/Status BubbleSortList_Sq(SqList &L,Status direction){int i,j; //循环控制变量ElemType temp; //临时缓存变量if (L.length == 0){printf("错误,当前线性表为空,请录入数据：\n");return ERROR; //线性表错误}if (L.length == 1)return OK;if (L.length >= 2) //表中元素至少多于2个{for (i = L.length; i > 0; --i) //起泡法排序{for (j = 0; j < i - 1; j++){if (L.elem[j]>L.elem[j + 1]) //前一个元素大于后一个元素{temp = L.elem[j]; //保持较大的元素if (direction) //排序方式为递增{L.elem[j] = L.elem[j + 1]; //交换L.elem[j + 1] = temp;}}else{temp = L.elem[j]; //保持较小的元素if (!direction) //排序方式为递减{L.elem[j] = L.elem[j + 1]; //交换L.elem[j + 1] = temp;}}}}}return OK;} //BubbleSortList_Sq运行结果实验结果分析：从以上实验运行结果来说，程序可以实现实验要求的基本内容，至于数据输入等操作步骤从上图可以简单、明了的看出。
实验1 线性表及其应用
题目1 顺序表的建立与基本操作
一、实验目的
1. 通过实验，掌握include命令及头文件的使用
2. 通过实验，掌握顺序表的建立与输出
3. 通过实验，掌握顺序表的基本操作
二、实验内容
1. 练习顺序表的建立与输出
2. 练习顺序表的基本操作
三、实验前的准备
1. 理解并掌握顺序表的存储结构、基本操作
2. 复习include命令的使用
3. 预习实习指导书，并准备相关的程序清单
四、实验步骤与方法
（1）建立自己的工作目录
（2）在当前文件夹下建立函数结果状态代码的定义文件Status.h（课本p10（1）预定义常量和类型）和数据结构数据文件SqList.h（内容包括顺序表的描述、顺序表建立、顺序表的查询、插入、删除与输出等功能。
）
（3）理解并运行下列程序：
#include <stdio.h>
#include <stdlib.h>
#include "Status.h"
#include "SqList.h"
void main()
{
SqList a;
int i, k;
InitList_Sq(a);
printf("please input the data ,end of -99\n");
k = 0; scanf("%d",&i);
while (i != -99)
{
a.elem[k] = i; k++; scanf("%d",&i);
}
a.length = k;
printf("\n output the data:");
for (i = 0; i<=a.length-1; i++)
printf("%d ",a.elem[i]);
printf("\n");
}
（4）编写算法，通过调用SqList.h中的相关函数，完成顺序表中指定位置数据的输出、元素的插入和删除
题目2 链表的操作
一、实验目的
1. 通过实验，掌握链表的输入与输出
2. 通过实验，掌握链表的基本操作
二、实验内容
1. 建立自己的有关链表的头文件
2. 练习链表的输入与输出
3. 练习链表的基本操作的实现
4. 练习链表基本操作的应用
三、实验前的准备
1. 复习相关课程内容，理解并掌握链表基本操作算法
2. 准备相关的程序清单
3. 阅读实验指导书
四、实验步骤与方法
（一）建立自己的头文件“LinkList.h” ，内容包括单链表数据结构的说明，链表的建立与输出、插入与删除操作等
（二）理解并运行下面的程序
将用户输入的数据按头插入法建立一个带头结点的单链表。
输入结点数据时以输入一串字符的方式实现，‟$‟字符为结束输入字符。
#include <stdio.h>
#include <malloc.h>
#include “LinkList.h ”
int count_head(LinkList head) /* 带头结点的单链表: 输出单链表元素值并计数*/ {
int i=0;
LinkList p;
p = head->next;
printf( “输出单链表元素值：” );
while(p != NULL)
{
printf( “%c”,p->data);
i++;
p = p->next;
}
printf( “ \n ” );
return i;
}
LinkList creatlink_head_head (LinkList &head) /* 用头插入法建立带头结点的单链表*/
{
LinkList t;
char ch;
t = (LinkLIst)malloc(sizeof(LNode));
head = t;
t->next = NULL;
printf( “ 单链表元素值为单个字符, 连续输入，$ 为结束字符: “ );
while((ch = getchar())!= … $ ‟ )
{
t = (LinkLIst) malloc(sizeof(LNode));
t->data = ch;
t->next = head->next;
head->next = t;
}
return(head);
}
main()
{
struct LNode *head = NULL;
int num;
pri ntf( “ \n 建立单链表\n\n ” );
head = creatlink_head_head(head);
fflush(stdin);/*清除缓冲区的内容*/
num = count_head(head);
printf( “ 单链表元素个数= %d\n ” , num);
}
运行情况如下：
输入：
输出：
（三）单链表基本操作的应用
编写算法，通过调用LinkList.h中的相关函数，完成单链表指定位置元素的插入、删除。
