《数据结构实验1顺序表.doc》由会员分享，可在线阅读，更多相关《数据结构实验1顺序表.doc（19页珍藏版）》请在三一文库上搜索。
1、淮海工学院计算机科学系实验报告书课程名：数据结构题目：线性表数据结构试验班级：软件 112学号：姓名：评语：成绩： 指导教师：批阅时间：年月线性表实验报告要求1 目的与要求 :1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现；4）熟练掌握线性表的链式存储结构的基本操作算法实现 ;5）掌握线性表在实际问题中的应用和基本编程技巧 ;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结 果）；7）按照报告格式和内容要求， 认真书写实验报告， 并在试验后的第三天提交电子 （全
2、班同 学提交到学委，再统一打包提交给老师）和纸质（每班每次 5 份，学委安排，保证每个同学至 少提交一次） ；8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理；9）上实验课前，要求每个同学基本写好程序，并存储在自己的 U 盘上，用于实验课堂操 作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。2 实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型 ElemType 取整型 int。按照顺序存储结构实现如下算法：1）创建任意整数线性表 （即线性表的元素值随机在键盘上输入）的顺序存储结构 （即顺序表）长度限定在 25 之内；2）打印 /显示（遍历
3、）该线性表（依次打印 /显示出表中元素值） ；3）在顺序表中查找第 i 个元素，并返回其值；4）在顺序表第 i 个元素之前插入一已知元素；5）在顺序表中删除第 i 个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型 ElemType 取字符型 char 。按照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在 10 之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第 i 个元素， i 合法返回元素值，否则，返回 FALSE
4、 ；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE ，否则，返回 FALSE ；5）在链表中第 i 个结点之前插入一个新结点；6）在线性表中删除第 i 个结点；7）计算链表的长度。3 实验步骤与源程序#include <iostream>#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define MAXSIZE 25 /* 此处的宏定义常量表示线性表可能达到的最大长度 */ using namespace std;typedef structElemType
5、elemMAXSIZE; /* 线性表占用的数组空间 */，空表int last; /* 记录线性表中最后一个元素在数组 elem 中的位置(下标值) 置为 -1*/SeqList;void OutputSeqList(SeqList *L)cout<<" 顺序表如下： "<<endl;int i; for(i=0;i<=L->last;i+)cout<<L->elemi<<'n'cout<<endl;int GetDate(SeqList *L)int t;cout<<
6、;" 请输入要查找的元素的序数： "<<endl;cin>>t;if( t<0) | (t>L->last)cout<<" 输入错误！ " return(ERROR);else return(L->elemt-1);int InsList(SeqList *L)int i,e;cout<<" 请输入要插入的元素插入位置及要插入的元素 "<<endl; cin>>i>>e;int k;if(i<1) | (i>L-&g
7、t;last+2) /* 首先判断插入位置是否合法 */printf(" 插入位置 i 值不合法 ");return(ERROR);if(L->last>= MAXSIZE-1)printf(" 表已满无法插入 ");return(ERROR);for(k=L->last;k>=i-1;k-) /* 为插入元素而移动位置 */ L->elemk+1=L->elemk;L->elemi-1=e; /* 在 C 语言数组中，第 i 个元素的下标为 i-1*/ L->last+;return(OK);int De
8、lList(SeqList *L,ElemType *m)int w;cout<<" 请输出要删除的元素位置： "<<endl;cin>>w;int k;if(w<1)|(w>L->last+1)cout<<" 删除位置不合法 !"<<endl; return(ERROR);*m = L->elemw-1; /* 将删除的元素存放到 e 所指向的变量中 */ for(k=w; k<=L->last; k+)L->elemk-1 = L->elemk
9、; /*将后面的元素依次前移 */L->last-;return(OK);int sum(SeqList *L)int i,n=0;for(i=0;i<L->last+1;i+) n=n+L->elemi;return(n);void main()int *q,n;SeqList *L;L=(SeqList*)malloc(sizeof(SeqList);q = (int*)malloc(sizeof(int);cout<<" 请输入顺序表长度： " cin>>n;L->last=n-1;cout<<&quo
10、t; 请输入顺序表： "<<endl;int i;for(i=0;i<n;i+)cin>>L->elemi;char c='y'while(c!='n')cout<<" 请选择你要进行的操作： "<<endl;删除元cout<<"1. 输出顺序表； "<<'n'<<"2. 查找元素； "<<'n'<<"3. 插入元素； "&
11、lt;<'n'<<"4. 素； "<<'n'<<"5. 求和 "<<endl;int xuanze;cin>>xuanze;switch(xuanze)case 1:OutputSeqList( L);break;case 2:cout<<GetDate( L)<<endl;break;case 3:InsList( L);break;case 4:DelList(L,q);break;case 5:cout<<sum(
12、L)<<endl;break;cout<<" 是否要继续进行操作 y/n:"<<endl;cin>>c;#include<stdio.h> #include<malloc.h> #define MAX 15 #define TURE 1 #define FALSE 0 typedef char ElemType; typedef struct Node char date;struct Node * next; Node,*LinkList;void InitList(LinkList *L)*L=(L
13、inkList)malloc(sizeof(char);(*L)->next=NULL;void PrintfLink(LinkList L)LinkList p;p=L->next;printf(" 链表为 :");while(p!=NULL)printf("%c ",p->date);p=p->next;void Create(LinkList L)LinkList s,r;char c;int flag=1;int n;r=L;printf(" 元素个数 :");scanf("%d",
14、&n);if(n>MAX)printf(" 超出限定长度 !");elseprintf(" 输入字符 (以 #键结束 ):");while(flag)scanf("%c",&c);if(c!='#')s=(Node*)malloc(sizeof(char); s->date=c;r->next=s;r=s;elseflag=0;r->next =NULL;void Order(LinkList L)char c;Node *r,*q,*p;for(r=L->next;r-&
15、gt;next!=NULL;r=r->next ) p=r;for(q=r->next;q;q=q->next )if(q->date)<(p->date) p=q;if(p!=r)c=r->date;r->date=p->date; p->date=c; PrintfLink(L);void Get(LinkList L, int i, ElemType *e)int j; Node *p;p=L; j=-1;while (p->next!=NULL)&&(j<i)p=p->next;j+;*e=p
16、->date ;if(i=j)printf(" 第 %d 个元素为 :%c",i,*e);elseprintf("FALSE");void Locate(LinkList L, ElemType e)int i=1;LinkList p;p=L->next ;while(p&&p->date!=e)i=i+;p=p->next;if(!p)printf("FALSEn");elseprintf("TRUEn");printf(" 该元素在第 %d 个位置 !&quo
17、t;,i-1); void InsList(LinkList L,int i,ElemType e)Node *p,*s;int k=0;p=L;while(p!=NULL&&k<i-1) p=p->next; k=k+;if(!p)printf(" 插入位置不合理 !"); s=(Node*)malloc(sizeof(char); s->date=e;s->next=p->next;p->next=s;Order(L);void DelList(LinkList L,int i,ElemType *e)Node *p,
18、*r;int j;j=0;p=L;while(p->next!=NULL)&&(j<i-1) p=p->next; j+; if(p->next!=NULL) p->next=p->next->next; r=p->next;*e=r->date ; printf(" 删除第 %d 个元素 :%cn",i,*e);elseprintf(" 删除结点的位置 i 不合理 !"); void ListLength(LinkList L)Node *p;int j=0;p=L->next
19、;while(p!=NULL)p=p->next; j+;printf(" 单链表的长度 :%d",j);void menu()printf("n菜单);printf（"n1.创建任意字符型单循环链表"）;printf（"n2.打印（遍历）该链表 "）;printf（"n3.查找第 i 个元素 "）;printf（"n4.查找与一已知字符相同的元素"）;printf（"n5.插入元素 "）;printf（"n6.删除第 i 个结点"）;pr
20、intf（"n7.计算链表的长度"）;printf（"n8.退出 "）;);printf("n void main()int i;int flag=0;ElemType e;LinkList L;L=(LinkList)malloc(sizeof(char);InitList(&L);menu();while(!flag)printf("nn 请输入你的选择 (18):");scanf("%d",&i);switch(i)case 1:Create(L); break;case 2:Ord
21、er(L);break;case 3:printf(" 输入要查找的第 i 个元素 :"); scanf("%d",&i);Get(L,i,&e); break;case 4:printf(" 输入查找的元素 :"); rewind(stdin);scanf("%c",&e);Locate(L,e); break;case 5: printf(" 输入插入的元素 :"); rewind(stdin); scanf("%c",&e); InsList(L,i,e); break;case 6: printf(" 输入要删除第几个结点 :"); scanf("%d",&i); DelList(L,i,&e);break;case 7:ListLength(L); break;case 8:flag=1; break;4 测试数据与实验结果（可以抓图粘贴）5 结果分析与实验体会1. 编程时，要注意随时写点注释，有利于编译；2. 要先熟悉书本上的内容，否则编译会有困难；3. 不能太过死板，要灵活运用所学知识。数据结构实验报告- 13 -