第一篇：数据结构多项式相加实验报告
天津理工大学计算机科学与技术专业
陈龙
题目要求：输入复杂多项式，做到化简和相加减运算。
一.算法模块分析：
将整个项目可分为四部分：
1.将输入字符串链表分析到单链表
2.单链表化简
3.链表值运算
4.输出 二.模块分块实现：
1.将输入字符串链表分析到单链表
分析：
一元稀疏多项式，包含字符有数字（系数和指数）
系数中小数点，指数符号，变量字母（以x为例）
运算符（+和-,其中加减也可以表示正负数）
通过以上分析可以构建如下结构体以用于存储每个单项
并完成相应标志任务
struct Record{
double factor;//记录系数95.12-26x+73x^3 =-80.52+48x-29x^3+4x^12
测试二：
5x+3x^2-15+21.45x^21+57.34-12x^2+20x 67x^3+51x-67x+123.456-81x+99x^21+41^2 多项式1和2最简结果: 加法运算
42.34+25x-9x^2+21.45x^21 + 123.456-97x+41x^2+67x^3+99x^21 = 165.796-72x+32x^2+67x^3+120.45x^21 减法运算
42.34+25x-9x^2+21.45x^21-123.456-97x+41x^2+67x^3+99x^21 =-81.116+122x-50x^2-67x^3-77.55x^21 四。总结
根据代码运行实例结果分析，其可以正确运算各种符合预定规则的输入。
代码健壮性良好。代码实现中，做到了不写重复代码的要求，将运算代码
合为一个。并符合代码模块化规则，将各模块分块实现，并完美的结合在一起。
具体实现代码： /* 实现多项式计算
*/
#include
int power;//记录次方
int flt;//记录后面有多少小数,用复数表示
bool flag;//记录正或者
Record *next;};Record *InitRecord(){ Record *nr=new Record();nr->power=0;//初始化次方为0
nr->factor=1;//初始化系数为1
nr->flag=true;//初始化为正数
nr->next=NULL;nr->flt=0;return nr;} class Polynomial{ public:
//初始化链表头，多项式字符串，进行分析
Polynomial(char *str=NULL);//重载构造函数，直接利用多项式进行给予对象
Polynomial(Record *h);
void Analsis(char* str);//分析多项式
void OutputPolynomial();//按规则输出多项式
Record* GetHead(){//得到头节点
return head;
} private:
void RemoveRepeatedAndZero();
//处理栈中存储的数据，将一项处理到节点中
void InsertToListTail(Record* node);
Record *head;//记录头节点
Record *tail;//记录尾节点
stack
tail=head;if(str!=NULL)Analsis(str);}
Polynomial::Polynomial(Record *h){ head=h;} void Polynomial::Analsis(char* str){ int n=strlen(str);int i=0;Record *temp;bool flag=false;
while(i { case '-':{ if(!Q.empty()) { //已经记录了数据就可以插入了 InsertToListTail(temp); i--; flag=false; } else { temp->flag=!temp->flag; } break; } case '.':{ temp->flt=-1; break; } case '+':{ if(!Q.empty()) { //已经记录了数据就可以插入了 InsertToListTail(temp); flag=false; } break; } case ' ':break; case '^':{ temp->power=1; break; } case 'x':{ temp->power=1; if(Q.empty())Q.push(1); break; } default:{ if(!(str[i]>='0'&&str[i]<='9')){ cout<<“多项式中有其它不可识别字符: ”< if(temp->flt&&!temp->power)temp->flt--; else if(temp->power)temp->power++;//多一个次方 Q.push(str[i]-'0'); break; } } i++;} this->InsertToListTail(temp);this->RemoveRepeatedAndZero();} //完成插入到链表后新的数据，同时将factor计算出来 void Polynomial::InsertToListTail(Record* node){ double fr=0.0;int p=0;int temp=0;int i=0; //统计平方值 if(node->power>1)//如果power大于1才计算 { while(--node->power>0){ temp=Q.top();Q.pop();p+=temp*powl(10,i++);} node->power=p;} if(node->flt==0)node->flt--;while(!Q.empty()){ temp=Q.top();Q.pop();fr+=temp*powl(10,++node->flt);} node->factor=fr; if(node->flag==false)//负数标志 { node->factor=-node->factor;//使系数变符号 } if(node->factor!=0){ tail->next=node;//接入新节点 tail=node;} } void Polynomial::OutputPolynomial(){ Record* p=head;if(p->next==NULL){ cout<<0< return;} int flag=0;while(p->next!=NULL){ //负数输出是会带有负号，不需要加入或验证 p=p->next; //如果系数为正，且不是头项，就应该输出‘+’ if(p->factor>0&&flag)cout<<'+'; flag=1;//标志此时不是输出第一项 if(p->factor==-1&&p->power)cout<<'-'; } //如果系数不等于1 或者没有x，就输出系数 else if(p->factor!=1||!p->power)cout< factor;if(p->power)//如果有x就要暑输出 cout<<'x'; if(p->power>1)//次方大于1，要输出 cout<<'^'< power;} cout< void Polynomial::RemoveRepeatedAndZero(){ Record* h,*p,*temp,*pre;if(head->next==NULL)return;h=head->next->next;p=head->next;pre=head; int flag=true; while(flag){ flag=false;while(p!=NULL&&h!=NULL){ if(p->power==h->power) { p->factor+=h->factor; p->next=h->next; temp=h; h=h->next; delete temp; flag=true; continue; } if(p->power>h->power) { temp=h; p->next=temp->next; temp->next=p; pre->next=temp; p=pre->next; h=p->next; flag=true; continue; } h=h->next; pre=pre->next; p=p->next;} if(p!=NULL)p->next=NULL;h=head->next->next;p=head->next;pre=head;} p=head->next;pre=head;while(p!=NULL)//去除系数为零的项 { if(p->factor==0){ temp=p; p=p->next; } pre->next=p; delete temp;} if(p!=NULL){ p=p->next;pre=pre->next;} } pre->next=NULL;//将一个节点复制到一个新空间 Record* CopyTo(Record* h){ Record* nd=InitRecord();nd->factor=h->factor;nd->flag=h->flag;nd->flt=h->flt;nd->next=NULL;nd->power=h->power;return nd;} //多项式相加过程 Record* PolyAdd(Record* a,Record *b,int flag)//flag=1=>+else-{ Record* result=InitRecord();Record* p=result;Record* temp;a=a->next;b=b->next;while(a!=NULL&&b!=NULL){ if(a->power { temp=CopyTo(a); a=a->next; } else if(b->power { temp=CopyTo(b); if(!flag)temp->factor*=-1; b=b->next; } else{ temp=CopyTo(a); if(flag) temp->factor+=b->factor; else temp->factor-=b->factor; b=b->next; a=a->next; } p->next=temp; p=temp;} if(!a)a=b;while(a!=NULL){ p->next=CopyTo(a); p=p->next; a=a->next;} p->next=NULL;return result;} int main(){ char str[50];char st2[50];Record *p,*q,*re,*m;cin>>str;cin>>st2;Polynomial exp(str);Polynomial e2(st2);p=exp.GetHead();q=e2.GetHead(); re=PolyAdd(p,q,1);Polynomial res(re);cout<<“多项式1和2最简结果:n”;cout<<“加法运算”< e2.OutputPolynomial();cout<<'='< m=PolyAdd(p,q,0);cout<<“减法运算”< e2.OutputPolynomial();cout<<'='< 注意：实验结束后提交一份实验报告电子文档 电子文档命名为“学号+姓名”，如：E01214058宋思怡 《数据结构》实验报告 （一）学号：姓名：专业年级： 实验名称：线性表 实验日期：2014年4月14日 实验目的： 1、熟悉线性表的定义及其顺序和链式存储结构； 2、熟练掌握线性表在顺序存储结构上实现基本操作的方法； 3、熟练掌握在各种链表结构中实现线性表基本操作的方法； 4、掌握用 C/C++语言调试程序的基本方法。 实验内容： 一、编写程序实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能： （1）初始化顺序表L； （2）依次在L尾部插入元素-1,21,13,24,8； （3）输出顺序表L； （4）输出顺序表L长度； （5）判断顺序表L是否为空； （6）输出顺序表L的第3个元素； （7）输出元素24的位置； （8）在L的第4个元素前插入元素0； （9）输出顺序表L； （10）删除L的第5个元素； （11）输出顺序表L。 源代码 调试分析（给出运行结果界面） 二、编写程序实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能： „„„„ „„„„ 小结或讨论: （1）实验中遇到的问题和解决方法 （2）实验中没有解决的问题 （3）体会和提高 南京信息工程大学实验（实习）报告 实验（实习）名称数据结构实验（实习）日期 2011-11-2得分指导教师周素萍 系公共管理系专业信息管理与信息系统年级10级班次1姓名常玲学号2010230700 3实验一顺序表的基本操作及C语言实现 【实验目的】 1、顺序表的基本操作及 C 语言实现 【实验要求】 1、用 C 语言建立自己的线性表结构的程序库，实现顺序表的基本操作。 2、对线性表表示的集合，集合数据由用户从键盘输入（数据类型为整型），建立相应的顺序表，且使得数据按从小到大的顺序存放，将两个集合的并的结果存储在一个新的线性表集合中，并输出。 【实验内容】 1、根据教材定义的顺序表机构，用 C 语言实现顺序表结构的创建、插入、删除、查找等操作； 2、利用上述顺序表操作实现如下程序：建立两个顺序表表示的集合（集合中无重 复的元素），并求这样的两个集合的并。 【实验结果】 [实验数据、结果、遇到的问题及解决] 一． Status InsertOrderList(SqList &va,ElemType x) { } 二． Status DeleteK(SqList &a,int i,int k) {//在非递减的顺序表va中插入元素x并使其仍成为顺序表的算法 int i;if(va.length==va.listsize)return(OVERFLOW);for(i=va.length;i>0,x } //注意i的编号从0开始 int j;if(i<0||i>a.length-1||k<0||k>a.length-i)return INFEASIBLE;for(j=0;j<=k;j++)a.elem[j+i]=a.elem[j+i+k];a.length=a.length-k;return OK; 三．// 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) { LinkList pa,pb,qa,qb;pa=A;pb=B;qa=pa;qb=pb;// 保存pa的前驱指针 // 保存pb的前驱指针 pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb){} while(pa){} qa=pa;pa=pa->next;qa->next=A->next;A->next=qa;if(pa->data data){} else{} qb=pb;pb=pb->next;qb->next=A->next;//将当前最小结点插入A表表头 A->next=qb;qa=pa;pa=pa->next;qa->next=A->next;//将当前最小结点插入A表表头 A->next=qa; } } pb=B;free(pb);return OK;qb=pb;pb=pb->next;qb->next=A->next;A->next=qb; 顺序表就是把线性表的元素存储在数组中，元素之间的关系直接通过相邻元素的位置来表达。 优点：简单，数据元素的提取速度快； 缺点：（1）静态存储，无法预知问题规模的大小，可能空间不足，或浪费存储空间；（2）插入元素和删除元素时间复杂度高——O（n） 求两个集合的并集 该算法是求两个集合s1和s2的并集，并将结果存入s引用参数所表示的集合中带回。首先把s1集合复制到s中，然后把s2中的每个元素依次插入到集合s中，当然重复的元素不应该被插入，最后在s中就得到了s1和s2的并集，也就是在s所对应的实际参数集合中得到并集。 实验报告4 排序 一、实验目的 1、掌握常用的排序方法，并掌握用高级语言实现排序算法的方法。 2、深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用。 3、了解各种方法的排序过程及其依据的原则，并掌握各种排序方法的时间复杂度的分析方法。 二、实验要求及内容 要求编写的程序所能实现的功能包括： 1、从键盘输入要排序的一组元素的总个数 2、从键盘依次输入要排序的元素值 3、对输入的元素进行快速排序 4、对输入的元素进行折半插入排序 三、实验代码及相关注释 #include typedef struct { int key;}RedType; typedef struct { RedType r[100];int length;}SqList; //1 快速排序的结构体 typedef struct { int data[100]; int last;}Sequenlist;//2 折半插入排序的结构体 int Partition(SqList &L, int low, int high) //1 寻找基准 { L.r[0]=L.r[low];//子表的第一个记录作基准对象 int pivotkey = L.r[low].key;//基准对象关键字 while(low while(low L.r[low] = L.r[high];//小于基准对象的移到区间的左侧 while(low L.r[high] = L.r[low];//大于基准对象的移到区间的右侧 } L.r[low] = L.r[0];return low;} void QuickSort(SqList &L, int low, int high) //1 快速排序 { //在序列low-high中递归地进行快速排序 if(low < high) { int pivotloc= Partition(L, low, high); //寻找基准 QuickSort(L, low, pivotloc-1);//对左序列同样递归处理 QuickSort(L, pivotloc+1, high);//对右序列同样递归处理 } } Sequenlist *Sqlset() //2 输入要折半插入排序的一组元素 { Sequenlist *L; int i; L=(Sequenlist *)malloc(sizeof(Sequenlist)); L->last=0; cout<<“请输入要排序的所有元素的总个数：”; cin>>i; cout< cout<<“请依次输入所有元素的值：”; if(i>0) { for(L->last=1;L->last<=i;L->last++) cin>>L->data[L->last]; L->last--; } return(L);} middlesort(Sequenlist *L) //2 折半插入排序 { int i,j,low,high,mid;for(i=1;i<=L->last;i++){ L->data[0]=L->data[i]; low=1; high=i-1; while(low<=high) { mid=(low+high)/2; if(L->data[0] high=mid-1;//插入点在前半区 else low=mid+1;//插入点在后半区 } for(j=i;j>high+1;j--){ L->data[j]=L->data[j-1];} //后移 L->data[high+1]=L->data[0];//插入 } return 0;} int main(){ gg: cout<<“请选择功能（1.快速排序 2.折半插入排序 3.退出程序）：”;int m;cin>>m;cout< if(m==1){ SqList L;int n;cout<<“请输入要排序的所有元素的总个数：”;cin>>n;cout< cin>>L.r[i].key; } cout< QuickSort(L,1,L.length); for(int j=1;j<=L.length;j++) { cout< } cout< cout< } if(m==2){ Sequenlist *L; int i; L=Sqlset(); cout< middlesort(L); cout<<“折半插入排序后为：”; for(i=1;i<=L->last;i++) { cout< } cout< cout< goto gg;} if(m==3){ exit(0); cout< 四、重要函数功能说明 1、Sequenlist *Sqlset() 输入要折半插入排序的一组元素 2、int Partition(SqList &L, int low, int high) 寻找快速排序的基准 3、void QuickSort(SqList &L, int low, int high) 快速排序 4、middlesort(Sequenlist *L) 折半插入排序 五、程序运行结果 下图仅为分别排序一次，可多次排序，后面有相关截图： 六、实验中遇到的问题、解决及体会 1、起初编写快速排序的程序时，我是完全按照老师PPT上的算法敲上去的，然后建立了一个SqList的结构体，调试运行时出现错误，仔细查看才意识到Partition函数中L中应该包含元素key，而我建立结构体时没有注意，然后我将key这个元素补充进去，继续调试，又出现错误，提示我Partition没有定义，我就觉得很奇怪，我明明已经写了函数定义，为什么会这样，当我又回过头来阅读程序时，我发现QuickSort函数中调用了Partition函数，但是我的Partition函数的定义在QuickSort函数的后面，于是我将Partition函数放到了QuickSort函数的前面，再次调试运行，就可以正常运行，得出结果了。这让我懂得，编程一定要认真仔细，不可大意马虎，否则又会花很多时间回过头来检查修改程序，得不偿失。 运行程序错误截图： 2、本来我是编写了两个程序，分别实现快速排序和折半插入排序的功能，但我后来想我是否可以将其合二为一，于是我想到用if选择语句用来实现不同的功能，从键盘输入功能选项m，if（m==1），可以进行快速排序，if（m==2），可以进行折半插入排序，于是我继续思考，我是否可以在一次运行程序中，多次对含有不同元素的序列进行排序，于是我用了goto语句，每次排序一次后，自动循环到选择语句，当不需要在排序的时候，可以从键盘输入3，退出程序，这样一来，程序变得更加实用和清晰明朗。这让我懂得，想要编出好的程序，要善于思考，在实现所需功能的前提下，多想问题，看是否能使程序更加实用简便。 修改程序前两个运行结果截图 （两个程序，调试运行两次，每次只能进行一次排序） 1、快速排序程序运行结果截图： 2、折半插入排序程序结果截图： 程序重要模块修改截图： 修改程序后运行截图： （一个程序，调试运行一次，可多次进行不同序列的不同排序） 数 据 结 构 实 验 报 告 1.问题描述 为某个单位建立一个员工通讯录管理系统，可以方便地查询每一个员工的办公室电话号码、手机号码及电子邮箱。2.设计分析 在本设计中，整个通讯录可以采用顺序表或链表方式存储。其功能包括通讯录链表的建立、员工通讯信息的查询、修改、插入与删除以及整个通讯录表的输出。3.员工通讯信息的结构类型定义和通讯录链表的结点类型 typedef struct { char num[5];/*员工编号*/ char name[8];/*员工姓名*/ char phone[9];/*办公室电话号码*/ char call[12];/*手机号码*/ }DataType；/*员工通讯信息的结构类型*/ typedef struct node { DataType data;/*结点的数据域*/ struct node *next;/*结点的指针域*/ }ListNode,*LinkList；/*通讯录链表的结构类型*/ 4.实验源代码 // Address_List1.cpp : 定义控制台应用程序的入口点。// //#include “stdafx.h” #include“stdio.h” #include “stdlib.h” # include char num[5]; /*员工编号*/ char name[8]; /*员工姓名*/ char phone[9]; /*办公室电话号码*/ char call[12]; /*手机号码*/ char mail[15]; /*邮箱*/ }DataType;/*通讯录单链表的结点类型*/ typedef struct node { DataType data; /*结点的数据域*/ struct node *next; /*结点的指针域*/ }LNode, *LinkList;void CreateList(LinkList &L){//逆位序输入n个元素的值，建立带表头结点的单链线性表L LinkList p; int i,n; L =(LinkList)malloc(sizeof(LNode)); L->next = NULL; cout <<“请输入创建员工的通讯信息的个数：”; cin >> n; for(i = 0;i p =(LinkList)malloc(sizeof(LNode)); cout <<“ 请输入员工信息”< cout <<“ 员工编号：”; cin>> p->data.num; cout <<“ 员工姓名：”; cin >> p->data.name; cout <<“办公室电话号码：”; cin >> p->data.phone; cout <<“ 手机号码：”; cin >> p->data.phone; cout <<“ 员工邮箱：”; cin >> p->data.mail; cout <<“================================”<< endl; p->next = L->next; L->next = p; } } void InitList(LinkList &L){//初始化线性表 L =(LinkList)malloc(sizeof(LNode)); L->next = NULL;} void DestroyList(LinkList &L){//销毁线性表 LinkList p, q; p = L; q = p->next; while(q!= NULL) { free(p); } } int ListEmpty(LinkList &L){//判断线性表是否为空 if(L->next == NULL) return TRUE; else return FALSE;} int ListLength(LinkList &L){//求链表的长度 LinkList p = L; int c = 0; while(p->next!= NULL){ c++; p = p->next; } return(c);} void GetElem(LinkList &L){//取链表第i个数据元素 LinkList p = L->next; string s; cout <<“输入员工的编号或名字:”; cin >> s; while(p!= NULL)//根据相关信息，查找员工。 { if(p->data.num == s || p->data.name == s || p->data.phone == s || p->data.call == s || p->data.mail == s) break; p = p->next; } if(!p) cout <<“查无此人!”<< endl; else{ cout <<“ 员工信息”<< endl; cout <<“ 员工编号：”<< p->data.num << endl; cout <<“ 员工姓名：”<< p->data.name << endl; cout <<“办公室电话号码：”<< p->data.phone << endl; cout <<“ 手机号码：”<< p->data.phone << endl; cout <<“ 员工邮箱：”<< p->data.mail << endl; cout <<“================================”<< endl; } } void ReviseList(LinkList &L)//修改信息 { LinkList p = L->next; char j[20]; string s; int i; cout <<“输入员工的编号或名字:”; cin >> s; while(p!= NULL){//根据相关信息，查找员工。 if(p->data.num == s || p->data.name == s || p->data.phone == s || p->data.call == s || p->data.mail == s) break; p = p->next; } if(!p) cout <<“查无此人!”<< endl; else { cout <<“n想修改什么信息？_1-编号 2-姓名 3-办公室电话号码 4-手机号码 5-邮箱”<< endl; cin >> i; cout <<“想修改成什么？”<< endl; cin >> j; switch(i){ case 1:strcpy(p->data.num, j);break; case 2:strcpy(p->data.name, j);break; case 3:strcpy(p->data.phone, j);break; case 4:strcpy(p->data.call, j);break; case 5:strcpy(p->data.mail, j);break; default: cout <<“输入错误，”<< endl; system(“pause”); } cout <<“修改完毕！”; system(“pause”); return; } } void ListDelete(LinkList &L)//删除第i个元素 { LinkList p, q; int j = 0,i;p = L; cout <<“请输入你要删除第几个员工的信息：”; cin >> i; while(p->next && j < i1)//删除位置不合理 cout <<“删除位置不合理”<< endl; q = p->next; p->next = q->next;//删除并释放结点 free(q);} void ListInsert(LinkList &L){ LinkList s, p = L; s =(LinkList)malloc(sizeof(LNode)); cout <<“ 请输入员工信息”<< endl; cout <<“ 员工编号：”; cin >> s->data.num; cout <<“ 员工姓名：”; cin >> s->data.name; cout <<“办公室电话号码：”; cin >> s->data.phone; cout <<“ 手机号码：”; cin >> s->data.phone; cout <<“ 员工邮箱：”; cin >> s->data.mail; cout <<“================================”<< endl; s->next = p->next; p->next = s;} void PrintList(LinkList &L)//打印线性表 { LinkList p = L->next; int i = 1; if(p == NULL) cout <<“通讯录为空！”<< endl; while(p!= NULL) { cout <<“第 ”< cout <<“ 员工编号：”<< p->data.num << endl; cout <<“ 员工姓名：”<< p->data.name << endl; cout <<“办公室电话号码：”<< p->data.phone << endl; cout <<“ 手机号码：”<< p->data.phone << endl; cout <<“ 员工邮箱：”<< p->data.mail << endl; cout <<“==============================”<< endl; p = L; cout <<“请输入你要删除第几个员工的信息：”; cin >> i; while(p->next && j < i1)//删除位置不合理 cout <<“删除位置不合理”<< endl; q = p->next; p->next = q->next;//删除并释放结点 free(q);} void ListInsert(LinkList &L){ LinkList s, p = L; s =(LinkList)malloc(sizeof(LNode)); cout <<“ 请输入员工信息”<< endl; cout <<“ 员工编号：”; cin >> s->data.num; cout <<“ 员工姓名：”; cin >> s->data.name; cout <<“办公室电话号码：”; cin >> s->data.phone; cout <<“ 手机号码：”; cin >> s->data.phone; cout <<“ 员工邮箱：”; cin >> s->data.mail; cout <<“================================”<< endl; s->next = p->next; p->next = s;} void PrintList(LinkList &L)//打印线性表 { LinkList p = L->next; int i = 1; if(p == NULL) cout <<“通讯录为空！”<< endl; while(p!= NULL) { cout <<“第 ”< cout <<“ 员工编号：”<< p->data.num << endl; cout <<“ 员工姓名：”<< p->data.name << endl; cout <<“办公室电话号码：”<< p->data.phone << endl; cout <<“ 手机号码：”<< p->data.phone << endl; cout <<“ 员工邮箱：”<< p->data.mail << endl; cout <<“==============================”<< endl;break; case 4: //添加 ListInsert(L); cout <<“添加信息成功！”; system(“pause”); break; case 5: PrintList(L); ListDelete(L); cout <<“删除信息成功！”; system(“pause”); break;//输出全部信息 case 6: PrintList(L); system(“pause”); break; case 7: cout <<“该通讯录共有 ”<< ListLength(L)<<“ 员工信息！”<< endl;; system(“pause”); break; default: cout <<“输入错误!”<< endl; system(“pause”); } } while(in!= 0);} 5.实验截图.第二篇：数据结构实验报告
第三篇：数据结构实验报告
第四篇：数据结构实验报告
第五篇：数据结构实验报告
点击咨询 