数据结构实验1报告G计算机141-韩坚

1、淮海工学院计算机工程学院实验报告书课程名：数据结构题目：线性数据实验班级：G 计算机 141学号：2014150230姓名：韩坚评语：成绩：指导教师：批阅时间：年月日一、目的与要求1）掌握线性表的顺序存储结构和链式存储结构；2）熟练掌握顺序表和链表基本算法的实现；3）掌握利用线性表数据结构解决实际问题的方法和基本技巧；4）按照实验题目要求独立正确地完成实验内容（编写、调试算法程序，提交程序清单及及相关实验数据与运行结果）；5）按时提交实验报告。实验环境计算机、 C 语言程序设计环境实验学时2 学时，必做实验。二、实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType 取整

2、型int 。按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出）：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入），长度限定在25之内；2）打印（遍历）该线性表（依次打印出表中元素值）；3 ）在线性表中查找第 i 个元素，并返回其值；4 ）在线性表中第 i 个元素之前插入一已知元素；5 ）在线性表中删除第 i 个元素；6 ）求线性表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型 ElemType 取字符型 char 。按照动态单循环链表结构实现如下算法（各算法边界条件适当给出） ：1 ）创建任意字符型有序 （递增排序） 单循环链表 （即链表的

3、字符元素随机在键盘上输入），长度限定在 15 之内；2）打印（遍历）该链表（依次打印出表中元素值）；3）在链表中查找第 i 个元素， i 合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回 FALSE；5 ）在链表中按照有序方式插入一已知字符元素；6 ）在线性表中删除第 i 个结点；7 ）计算链表的长度。三、实验步骤与源程序一、顺序表的源程序#include "stdafx.h"#include "stdio.h"2/16#include "stdlib.h"#includ

4、e "iostream.h"int dayin(int lint,int a);int chazhao(int lint);int charu(int lint,int j);int shanchu(int lint,int j);int qiuhe(int lint ,int j);int main(int argc, char* argv)int lint25;int i;cout<<" 输入线性表元素长度小于25"<<endl;cout<<" 输入写入元素的个数:"<<endl;c

5、in>>i;cout<<"输入元素 "<<endl;for(int j=0;j<i;j+)scanf("%d",&lintj);int a;int k=1；while(k)cout<<"1:打印线性表 "<<endl;cout<<"2:查找元素 "<<endl;cout<<"3:插入元素 "<<endl;cout<<"4:删除元素 "<&

6、lt;endl;cout<<"5:线性表元素求和"<<endl;cout<<"0:退出 "<<endl;cout<<"1,2,3,4,5选择 _"cin>>a;switch(a)case 1: dayin(lint,i);break;case 2: chazhao(lint);break;case 3: i=charu(lint,i);break;case 4: i=shanchu(lint,i);break;case 5: qiuhe(lint,i);break

7、;case 0: k=0 ;break;3/16return 0;int dayin(int lint,int a)for(int i=0;i<a;i+)printf("%dt",linti);cout<<endl;return 0;int chazhao(int lint )cout<<" 输入要查的第几个数"<<endl;int k=0;cin>>k;int i=0;int * p=lint;if(k>25)printf("输入有误 !");elsecout<<

8、;*(p+k-1)<<endl;p=NULL;return 0;int charu(int lint,int j)int i;i=j;int k;int l;if(j>=25)printf("线性表已满 ");return 0;cout<<" 输入要插入的位置和数据"<<endl;cout<<" 位置 :"cin>>k;cout<<" 数据 :"cin>>l;for(j=j-1;j>=k-1;j-)4/16lintj+1

9、=lintj;lintk=l;printf("插入成功 ");return i+1;int shanchu(int lint ,int j)cout<<" 输入删除的第几个数"<<endl;int k=0;cin>>k;int i;for(i=k-1;i<j;i+)linti=linti+1;printf("删除成功 ");return j-1;int qiuhe(int lint,int j)int sum=0;for(int i=0;i<j;i+)sum=sum+linti;prin

10、tf("所有元素和为%dn",sum);return 0;二、链表（带头结点）的源程序#include "stdafx.h"#include<stdlib.h>#include<stdio.h>5/16struct LNodechar elem;struct LNode* next;*l,*p,*nnew;int i,a,k,n;char c,s;/*-创建函数 -*/void intilist(void)l=(struct LNode *)malloc(sizeof(struct LNode);l->next=NULL;s

11、ystem("PAUSE");printf("Input the total of the elems:.");scanf("%d",&n);getchar();if(n>15)printf("Error!");for(i=n;i>0;i-)nnew=(struct LNode *)malloc(sizeof(struct LNode);nnew->next=l->next;l->next=nnew;p=l;while(p->next!=NULL) p=p->nex

12、t;p->next=l;printf("Input elems:.n");p=l->next;for(i=1;i<=n;i+)scanf("%c",&p->elem);getchar();p=p->next;return;/*-排序函数 -*/void Sequence(struct LNode * l, int n)int i;char swap,*e,*f;for(i=1;i<=n-1;i+) p=l->next; while(p->next!=l)if(p->elem>p->

13、next->elem) e=&p->elem; f=&p->next->elem;swap=*e;*e=*f;*f=swap;6/16p=p->next;return;/*-打印函数 -*/void Print(struct LNode * l, int n)int i;p=l->next;for(i=1;i<=n;i+)printf("%ct",p->elem);p=p->next;printf("n");return;/*-查找函数 -*/void Locate(struct LN

14、ode * l, int n,int m)int i;if(m>n) printf("FALSE!t");return; else p=l;for(i=1;i<=m;i+)p=p->next;printf("The elem is:%cn",p->elem);return;/*-已知字母匹配首结点查找函数-*/void LocateLNode(struct LNode * l, int n,char m)int i;p=l;for(i=1;i<=n;i+)p=p->next; if(p->elem=m) prin

15、tf("TRUE!n");return;if(i>n) printf("FALSE!n");return;/*-插入函数 -*/7/16void Insert(struct LNode * l, int n,char m)nnew=(struct LNode *)malloc(sizeof(struct LNode);nnew->next=l->next;l->next=nnew;nnew->elem=m;n=n+1;Sequence(l,n);Print(l,n);return;/*-删除函数 -*/void Delete

16、(struct LNode * l, int n,int m)int i;p=l;for(i=1;i<m;i+)p=p->next;p->next=p->next->next;n=n-1;printf("The new list is:");Print(l,n);return;/*-求表长函数 -*/void Length(int n)int i;int length=0;for(i=1;i<=n+1;i+)length=length+sizeof(struct LNode);printf("The length of the

17、list is:%d",length);return;/*-菜单函数 -*/void menu()int j;menulab:printf("* MENU *nn");printf("Create the new list :.press 1nn");printf("Sequence the list :.press 2nn");8/16printf("Search the Lnode by order :.press 3nn");printf("Search the Lnode by elem

18、 :.press 4nn");printf("Insert the elem :.press 5nn");printf("Delete the elem by order :.press 6nn");printf("Return the length of the list :.press 7nn");printf("exit the programe :.press 0nn");printf("* END *nn");printf("Please choose the nu

19、mber from (07).");checklabel: scanf("%1d",&j);getchar();if(j<0|j>7)printf("Error! Please choose again.");goto checklabel;printf("ntYou choose the number %dn ",j);printf("ntPress any key to continue.");getchar();system("PAUSE"); /*clear

20、 screen*/switch(j)case 1:/*创建链表并输入元素*/intilist();system("PAUSE"); /*clear screen*/goto menulab;case 2: /*排序并打印链表*/Sequence(l,n);printf("The orignal list is:n");Print(l,n);printf("Press any key to continue.");getchar();system("PAUSE"); /*clear screen*/goto menu

21、lab;case 3:/*查找第 i 个元素 */printf("Input which LNode you want to locate(Input number):");scanf("%d",&a);getchar();Locate(l,n,a);printf("Press any key to continue.");getchar();system("PAUSE"); /*clear screen*/goto menulab;case 4:/*查找与已知字符相同的第一个结点*/printf(&quo

22、t;Input the elem you want to search ");scanf("%c",&c);getchar();9/16LocateLNode(l,n,c);printf("Press any key to continue.");getchar();system("PAUSE"); /*clear screen*/goto menulab;case 5:/*插入已知字符的结点*/printf("Input the elem you want to insert:");scanf(

23、"%c",&s);getchar();Insert(l,n,s);n=n+1;printf("Press any key to continue.");getchar();system("PAUSE"); /*clear screen*/goto menulab;case 6:/*删除第 i 个结点 */printf("Input which one you want to delete:");scanf("%d",&k);if(k<1|k>n)printf("ERROR!");elseDelete(l,n,k);n=n-1;getchar();system("PAUSE"); /*clear screen*/goto menu