第一篇:数据结构线性表实验报告
实验报告
课程名:数据结构
实验名:线性表及其操作 姓名: 班级: 学号:
撰写时间:2014.09.24
一 实验目的与要求
1.掌握线性表的实现
2.掌握线性表的基本操作的实现
二 实验内容
• 分别完成线性表的顺序表示及链式表示
• 在两种表示上, 分别实现一些线性表的操作, 至少应该包括 – 在第i个位置插入一个元素 – 删除第i个元素 – 返回线性表长
– 返回第i个元素的值
三 实验结果与分析
#include
{
printf(“%d, ”,(*p).value);
p=(*p).next;//指针指向下一个结构体
} printf(“n”);} void Link(){
struct V*head;head=(struct V*)malloc(sizeof(struct V));//开辟一个长度为size的内存
(*head).value=-100;//表头为-100(*head).next=NULL;printf(“------------线性表链式表示------------n”);
int i,n=10;struct V*p=head;printf(“10个数据:n”);for(i=0;i (*p).next=(struct V*)malloc(sizeof(struct V)); p=(*p).next; (*p).value=2*i; (*p).next=NULL;} PrintLink(head);//调用PrintLink函数 printf(“删除第四个数据:n”);int k=4;p=head;for(i=1;i p=(*p).next;} struct V*temp=(*p).next;//k表示插入和删除的位置 (*p).next=(*temp).next;free(temp);PrintLink(head);printf(“插入第十个数据:n”); k=10;p=head;for(i=1;i p=(*p).next;} temp=(*p).next;(*p).next=(struct V*)malloc(sizeof(struct V));(*(*p).next).value=-99;(*(*p).next).next=temp;PrintLink(head);} //---------线性表顺序表示-----------void seq1(){ int i,n=10,k=4;int a[10];//---------输出数组元素------------printf(“-------------线性表顺序表示---------n”);for(i=0;i a[i]=i;} printf(“数组元素为:n”);for(i=0;i printf(“%3d”,a[i]);} printf(“n”);//--------插入一个数组元素---------int m=n+1,j=12;//插入元素12 int b[20];for(i=0;i if(i { b[i]=a[i]; } else if(i==k) {b[i]=j;} else {b[i]=a[i-1];} } printf(“输出插入一个元素的数组:n”);for(i=0;i { if(i {c[i]=a[i];} else {c[i]=a[i+1];} } printf(“输出删除一个元素的数组:n”);for(i=0;i printf(“数组元素为:n”);for(i=1;i<=a[0];i++){a[i]=i;} for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-----在k位置插入一个元素------------for(i=a[0];i>=k;i--){a[i+1]=a[i];} a[k]=-100;++a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”);//-------在k---------------for(i=0;i>k;i++){a[i]=a[i+1];} a[k]=-1;a[0]=n;--a[0];for(i=0;i<2*a[0];i++){printf(“%d,”,a[i]);} printf(“n”); } int main(int argc,char *argv[]){ seq1();seq2();Link();return 0;} 图1:实验结果截图 实验分析:已在程序中按规定格式标注。 数据结构原理实验报告 学号: 姓名: 线性表 一、问题描述 1.实现ADT表 2.设表的Reverse运算将表中元素的次序反转。扩充用数组实现表的结构List,增加函数Reverse(L),将表L中元素的次序反转,并要求就地实现Reverse运算。 二、算法描述 从i=0开始,将表中第N个元素与N-i-1个元素调换即可 三、核心代码 void ReverseList(List L){ ListItem tmp;int i;for(i=0;i } tmp = L->table[i];L->table[i] = L->table[L->n-1-i];L->table[L->n-1-i] = tmp;} 四、运行结果 }(一)单链表的基本操作 #include LinkList q=L;//使q指向表尾 } Status GetElem(LinkList L,int i,ElemType &e)//取第i个元素 { LinkList p=L->next;int j=1;while(p&&jnext;++j;} for(int i=1;i<=n;i++){ p=new LNode; cin>>p->data;p->next=NULL;q->next=p;q=p;} if(!p||j>i)return error;//第i个元素不存在 e=p->data;return ok;} Status LinkInsert(LinkList &L,int i,ElemType e)//插入 { LinkList p=L;int j=0;while(p&&j s->data=e;s->next=p->next;//插入L中 p->next=s;return ok;} Status ListDelete(LinkList &L,int i,ElemType &e)// 删除 { LinkList p=L;LinkList q;int j=0;while(p->next&&j p=p->next;++j;} if(!(p->next)||j>i-1)return error;//删除位置不合理 q=p->next;p->next=q->next;//删除并释放结点 e=q->data;delete(q);return ok; } void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc){ //合并两个顺序链表 LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb){ if(pa->data<=pb->data) { pc->next=pa; pc=pa;pa=pa->next;} else { pc->next=pb; pc=pb; pb=pb->next;} } pc->next=pa?pa:pb;delete(Lb);} void show(LinkList L)//{ LinkList p;p=L->next;while(p){ cout< data<<“-->”;p=p->next;} cout< 显示 表长 3 p=p->next;} return i;} void xiugai(LinkList L)//修改 { int i,j=1;ElemType k;ElemType e,m;LinkList p=L->next;cout<<“请输入要修改的元素位置(0>i;GetElem(L,i,e);cout<<“该位置的元素:”< cin>>x; cout<<“请输入”< CreateList(list,x);break;case 2: cout<<“单链表显示如下:”< show(list);break;case 3: int s;cout<<“单链表的长度为:”< ListDelete(list,x,y); } break;case 8: hebing();break;case 9: exit(0);break;default : cout<<“输入有误,请重新输入”< 四、测试结果 1)顺序表 的测试结果 8 2)单链表的测试结果 五、心得体会 当听到老师说写数据结构实验报告时,我有点惊讶,才学了不到一个月,就要写实验报告。记得去年学习C++时,学了一个学期,程序设计用了三周,才完成的,这个实验报告居然要一周完成两个设计,觉得很难。但是现在一周过去了,我也写完了,自我感觉良好。 通过这次写实验报告,我深切的理解了这门课的本质。刚开始学这门课时,当时还不清楚这门课程的目的,现在,我真正的理解了:数据结构像是身体的骨骼,而C++是填充这骨骼的肉体,二者相结合才能使整个程序更加完整,健全。数据结构是个框架,模型,抽象数据类型中列举了各种操作,而所用的C++语言,将各种操作描述出来构成算法。数据结构+算法=程序设计。 在这次设计的过程中,我还遇到了,很多的问题。顺序表是按顺序存储的,用了一维数组来存储,又结合C++的程序设计,我又用了类,但是,在执行时出现了问题。后来问同学,指出我的错误,不过获益不少。我又重新整理思路,把顺序表的基本操作写好了。虽然走了很多弯路,但是让我认识到,一定要创新,大胆,不能按照旧的思路去干新的事情。 单链表写起来简单多了,这个很快就搞定了。但是细节上出了问题。比如说,有些变量的重复定义,有些变量又没有定义,在调用函数,就直接复制过来,没有改参数……通过修改,我深刻理解到:细节决定成败,在以后,不管做任何事情都要认真,细心。 这次的实验报告,让我受益匪浅,不仅有知识方面的,还有生活和精神上的。总之,我会继续我的兴趣编程,相信在编程的过程中,能不断的提高自己。 实验报告二 线性表的顺序存储 班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX 专业: XXXX 2858505197@qq.com 一、实验目的: (1)掌握顺序表的基本操作的实现方法。 (2)应用顺序表的基本算法实现集合A=AUB算法。 (3)应用顺序表的基本算法实现两有序顺序表的归并算法。 二、实验内容: 1、线性表顺序存储结构的基本操作算法实现(要求采用类模板实现) [实现提示](同时可参见教材p5822-p60页算法、ppt)函数、类名称等可自定义,部分变量请加上学号后3位。库函数载和常量定义:(代码)#include (1)顺序表存储结构的定义(类的声明):(代码) template SeqList(datatype a[ ], int n);//有参构造函数 ~SeqList(){};//析构函数为空 int Length();//求线性表的长度 datatype Get(int i);//按位查找,取线性表的第i个元素 int Locate(datatype item);//查找元素item void Insert(int i, datatype item);//在第i个位置插入元素item datatype Delete(int i);//删除线性表的第i个元素 void display();//遍历线性表,按序号依次输出各元素 private: datatype data[MaxSize];//存放数据元素的数组 int length;//线性表的长度 }; (2)初始化顺序表算法实现(不带参数的构造函数)/* *输 入:无 *前置条件:顺序表不存在 *功 能:构建一个顺序表 *输 出:无 *后置条件:表长为0 */ 实现代码: template (3)顺序表的建立算法(带参数的构造函数) /* *输 入:顺序表信息的数组形式a[],顺序表长度n *前置条件:顺序表不存在 *功 能:将数组a[]中元素建为长度为n的顺序表 *输 出:无 *后置条件:构建一个顺序表 */ 实现代码: template cout<<“数组元素个数不合法”< data[i]=a[i];length=n;}(4)在顺序表的第i个位置前插入元素e算法 /* *输 入:插入元素e,插入位置i *前置条件:顺序表存在,i要合法 *功 能:将元素e插入到顺序表中位置i处 *输 出:无 *后置条件:顺序表插入新元素,表长加1 */ 实现代码: template cout<<“溢出”< cout<<“i不合法!”< data[j]=data[j-1];data[i-1]=item;length++;}(5)删除线性表中第i个元素算法 /* *输 入:要删除元素位置i *前置条件:顺序表存在,i要合法 *功 能:删除顺序表中位置为i的元素 *输 出:无 *后置条件: 顺序表册除了一个元素,表长减1 */ 实现代码: template cout<<“表为空,无法删除元素!”< cout<<“i不合法!”< for(j=i;j data[j-1]=data[j];//注意数组下标从0记 length--;return item;}(6)遍历线性表元素算法 /* *输 入:无 *前置条件:顺序表存在 *功 能:顺序表遍历 *输 出:输出所有元素 *后置条件:无 */ 实现代码: template cout<<“表为空,无法输出!”< cout< (7)获得线性表长度算法 /* *输 入:无 *前置条件:顺序表存在 *功 能:输出顺序表长度 *输 出:顺序表长度 *后置条件:无 */ 实现代码: template (8)在顺序线性表中查找e值,返回该元素的位序算法 /* *输 入:查询元素值e *前置条件:顺序表存在 *功 能:按值查找值的元素并输出位置 *输 出:查询元素的位置 *后置条件:无 */ 实现代码: template //下标为i的元素等于item,返回其序号i+1 return 0;//查找失败 } (9)获得顺序线性表第i个元素的值 /* *输 入:查询元素位置i *前置条件:顺序表存在,i要合法 *功 能:按位查找位置为i的元素并输出值 *输 出:查询元素的值 *后置条件:无 */ 实现代码: template cout<<“i不合法!”< (10)判表空算法 /* *输 入:无 *前置条件:无 *功 能:判表是否为空 *输 出:为空返回1,不为空返回0 *后置条件:无 */ 实现代码: template return 1;} else { return 0;} } (11)求直接前驱结点算法 /* *输 入:要查找的元素e,待存放前驱结点值e1 *前置条件:无 *功 能:查找该元素的所在位置,获得其前驱所在位置。*输 出:返回其前驱结点的位序。*后置条件:e1值为前驱结点的值 */ 实现代码: template return k;else { cout<<“无前驱结点!”< return 0;} }(12)求直接后继结点算法 /* *输 入:要查找的元素e,待存放后继结点值e1 *前置条件:无 *功 能:查找该元素的所在位置,获得其后继所在位置。*输 出:返回其后继结点的位序。*后置条件:e1值为后继结点的值 */ 实现代码: template cout<<“无后继结点!”< return k;} } 上机实现以上基本操作,写出main()程序: void main(){ SeqList if(Seq.Empty()){ cout<<“线性表为空!”< } Seq.Insert(1,1);Seq.Insert(2,2);Seq.Insert(3,3);Seq.Insert(4,4);Seq.Insert(5,5);//插入元素操作 cout<<“输出插入的五个元素:”< cout< cout<<“2是第”< cout<<“第五个元素是:”< cout<<“线性表的长度为:”< Seq.Delete(3);//删除元素 cout<<“删除第三个元素后的线性表为:”< cout< cout<<“元素2前驱结点的数值为:”< cout<<“元素4后继结点的位置为:”< cout<<“元素4后继结点的数值为:”< 要求对每个算法都加以测试,判断是否正确;并测试不同类型数据的操作。粘贴测试数据及运行结果: 2、用以上基本操作算法,实现A=AUB算法。(利用函数模板实现)/* *输 入:集合A,集合B *前置条件:无 *功 能:实现A=AUB *输 出:无 *后置条件:A中添加了B中的元素。*/ 实现代码: template return *this;else { int k=item.Length(); int num=this->Length(); for(int i=1;i<=k;i++) { for(int j=0;j if(data[j]==item.Get(i)) { break; } else if(num-1==j&&data[num-1]!=item.Get(i)) { this->Insert(++num,item.Get(i)); } } return *this;} } void main(){ SeqList B.Insert(1,2);B.Insert(2,6);B.Insert(3,1);B.Insert(4,8);B.Insert(5,9);//插入集合B中元素 A.Add(B);A.display();cout< 3、对以上顺序表类中的基本操作算法适当加以补充,实现向一个有序的(非递减)的顺序表中插入数据元素e算法。/* *输 入:插入元素e *前置条件:顺序表已有序 *功 能:将元素e插入到顺序表中适当的位置,使顺序表依然有序 *输 出: 无 *后置条件:有序顺序表插入了新元素,且表长加1。*/ 实现代码: template if((data[i] { for(int k=num;k>i;k--) data[k]=data[k-1]; data[i+1]=item; length++; break; } if(data[i]>item) { for(int k=num;k>i;k--) data[k]=data[k-1]; data[i]=item; length++; break; } } } void main(){ SeqList cout<<“原顺序表为:”< cout< cout<<“插入新元素后的顺序表为:”< 4、算法实现:La,Lb为非递减的有序线性表,将其归并为Lc,该线性表仍有序(未考虑相同时删除一重复值)(利用函数类板实现)MergeList: /* *输 入:有序线性表La,有序线性表Lb *前置条件:顺序表已有序 *功 能:将两线性表归并,不去掉相同元素 *输 出: 返回一个新的有序线性表Lc *后置条件:无 */ 实现代码: template Seq1.orderInsert(Seq2.Get(i));} return Seq1;} void main(){ SeqList cout<<“合并后的Lc为:”< cout< 粘贴测试数据及运行结果: 三、心得体会:(含上机中所遇问题的解决办法,所使用到的编程技巧、创新点及编程的心得) 实验报告三 线性表的链式存储 班级: 2010XXX 姓名: HoogLe 学号: 2010XXXX 专业: XXXX 2858505197@qq.com 一、实验目的: (1)掌握单链表的基本操作的实现方法。(2)掌握循环单链表的基本操作实现。(3)掌握两有序链表的归并操作算法。 二、实验内容:(请采用模板类及模板函数实现) 1、线性表链式存储结构及基本操作算法实现 [实现提示](同时可参见教材p64-p73页的ADT描述及算法实现及ppt)函数、类名称等可自定义,部分变量请加上学号后3位。也可自行对类中所定义的操作进行扩展。所加载的库函数或常量定义: #include LinkList(T a[],int n);//利用数组初始化带头结点的单链表构造函数实现 ~LinkList();int length();//求单链表表长算法 T get(int i);//获得单链表中第i个结点的值算法 int locate(T temp);void insert(int i,T temp);//在带头结点单链表的第i个位置前插入元素e算法 T Delete(int i);//在带头结点单链表中删除第i个元素算法 void print();//遍历单链表元素算法 bool isEmpty();//判单链表表空算法 void deleleAll();//删除链表中所有结点算法(这里不是析构函数,但功能相同)private: Node 前置条件:无 动作:初始化一个带头结点的空链表 输出:无 后置条件:头指针指向头结点。 //初始化带头结点空单链表构造函数实现 template (3)利用数组初始化带头结点的单链表构造函数实现 输入:已存储数据的数组及数组中元素的个数 前置条件:无 动作:利用头插或尾插法创建带头结点的单链表 输出:无 后置条件:头指针指向头结点,且数组中的元素为链表中各结点的数据成员。//利用数组初始化带头结点的单链表构造函数实现 template 动作:在带头结点的单链表中第i个位置之前插入元素e 输出:无 后置条件:单链表中增加了一个结点 //在带头结点单链表的第i个位置前插入元素e算法 template p=p->next; count++;} if(p==NULL)cout<<“i不合法,越界!”;else{ Node s->data = temp; s->next = p->next; p->next = s;} }(5)在带头结点单链表中删除第i个元素算法 输入:删除第i个结点,待存放删除结点值变量e 前置条件:单链表不空,i的值要合法 动作:在带头结点的单链表中删除第i个结点,并返回该结点的值(由e传出)。输出:无 后置条件:单链表中减少了一个结点 //在带头结点单链表中删除第i个元素算法 template p=p->next; count++;} if(p==NULL)cout<<“i不合法,越界!”;else{ Node T x= s->data; p->next = s->next; return x;} }(6)遍历单链表元素算法 输入:无 前置条件:单链表不空 动作:遍历输出单链表中的各元素。输出:无 后置条件:无 //遍历单链表元素算法 template cout< data<<“ ”; p=p->next;} cout< (7)求单链表表长算法。输入:无 前置条件:无 动作:求单链表中元素个数。输出:返回元素个数 后置条件:无 //求单链表表长算法 template p=p->next; count++;} return--count;} (8)判单链表表空算法 输入:无 前置条件:无 动作:判表是否为空。 输出:为空时返回1,不为空时返回0 后置条件:无 //判断非空 template (9)获得单链表中第i个结点的值算法 输入:无 前置条件:i不空,i合法 动作:找到第i个结点。 输出:返回第i个结点的元素值。后置条件:无 //获得单链表中第i个结点的值算法 template p=p->next; count++;} if(p==NULL)cout<<“i不合法,越界!”;else{ return p->data;} } (10)删除链表中所有结点算法(这里不是析构函数,但功能相同)输入:无 前置条件:单链表存在 动作:清除单链表中所有的结点。输出:无 后置条件:头指针指向空 //删除所有元素 template Node p=p->next; t->next=NULL;} } (11)上机实现以上基本操作,写出main()程序: 参考p72 void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数(前端插入!) LinkList if(list1.isEmpty()){ cout<<“链表不为空!”< cout<<“链表为空!”< 2、参考单链表操作定义与实现,自行完成单循环链表的类的定义与相操作操作算法。template void insert(int i,T temp);//在带头结点单循环链表的第i个位置前插入元素e算法 T Delete(int i);//在带头结点单循环链表中删除第i个元素算法 void print();//遍历单循环链表元素算法 private: Node 动作:利用头插或尾插法创建带头结点的单循环链表 输出:无 后置条件:头指针指向头结点,且数组中的元素为链表中各结点的数据成员,尾指针指向头结点。 //利用数组初始化带头结点的单循环链表构造函数实现 template s->next = head->next;head->next=s; length++;} } (2)在带头结点单循环链表的第i个位置前插入元素e算法 输入:插入位置i,待插入元素e 前置条件:i的值要合法 动作:在带头结点的单循环链表中第i个位置之前插入元素e 输出:无 后置条件:单循环链表中增加了一个结点 //在带头结点单循环链表的第i个位置前插入元素e算法 template while(count p=p->next; count++; } Node s->data = temp; s->next = p->next; p->next = s;} }(3)在带头结点单循环链表中删除第i个元素算法 输入:删除第i个结点,待存放删除结点值变量e 前置条件:单循环链表不空,i的值要合法 动作:在带头结点的单循环链表中删除第i个结点,并返回该结点的值(由e传出)。输出:无 后置条件:单循环链表中减少了一个结点 //在带头结点单循环链表中删除第i个元素算法 template if(i>length)cout<<“i不合法,越界!”< while(count p=p->next; count++; } Node T x= s->data; p->next = s->next; return x;} } (4)遍历单循环链表元素算法 输入:无 前置条件:单循环链表不空 动作:遍历输出单循环链表中的各元素。输出:无 后置条件:无 //遍历单循环链表元素算法 template cout< data<<“ ”; p=p->next;} cout< (5)上机实现以上基本操作,写出main()程序: void main(){ int a[10]={1,2,3,4,5,6,7,8,9,0};//测试带参数的构造函数(前端插入!) LinkList 3、采用链式存储方式,并利用单链表类及类中所定义的算法加以实现线性表La,Lb为非递减的有序线性表,将其归并为新线性表Lc,该线性表仍有序(未考虑相同时删除一重复值)的算法。模板函数: template if(p1->data>p2->data) { this->insert(++num,p1->data); p1=p1->next; } else{ this->insert(++num,p2->data); p2=p2->next; } } if(!p1){ p1=p2;} while(p1){ this->insert(++num,p1->data); p1=p1->next;} } void main(){ int a[5]={1,2,5,6,9};int b[5]={0,3,4,7,8};LinkList 选做题: 1、按一元多项式ADT的定义,实现相关操作算法: ADT PNode is Data 系数(coef)指数(exp)指针域(next):指向下一个结点 Operation 暂无 end ADT PNode ADT Polynomial is Data PNode类型的头指针。Operation Polynomail 初始化值:无 动作:申请头结点,由头指针指向该头结点,并输入m项的系数和指数,建立一元多项式。 DestroyPolyn 输入:无 前置条件: 多项式已存在 动作:消毁多项式。输出:无 后置条件:头指针指向空 PolyDisplay 输入:无 前置条件: 多项式已存在,不为空 动作:输出多项式各项系数与指数 输出:无 后置条件:无 AddPoly 输入:另一个待加的多项式 前置条件:一元多项式pa和pb已存在。动作及后置条件:完成多项式相加运算,(采用pa=pa+pb形式,并销毁一元多项式pb)输出:无 end ADT Polynomial 2、实现一元多项式的减法,操作描述如下: SubPoly 输入:待减的多项式pb 前置条件:一元多项式pa和pb已存在。 动作及后置条件:完成多项式减法运算,即:pa=pa-pb,并销毁一元多项式pb。输出:无 3、参考P74-P79页双向链表的存储结构定义及算法,编程实现双向链表的插入算法和删除算法。 三、心得体会:(含上机中所遇问题的解决办法,所使用到的编程技巧、创新点及编程的心得)第二篇:福州大学数据结构实验报告-线性表
第三篇:数据结构--实验报告 线性表的基本操作
第四篇:数据结构实验报告二线性表的顺序存储
第五篇:数据结构实验报告三线性表的链式存储