线性表的抽象数据类型的实现实验报告

1、下载可编辑数据结构实验报告实验名称 ：线性表的抽象数据类型的实现学号： 2011129127姓名：刘瑞奇指导老师 ：解德祥.专业 .整理 .下载可编辑计算机与信息学院实验 1 线性表的抽象数据类型的实现实验目的1.掌握线性表的顺序存储结构和链式存储结构；2.熟练掌握顺序表和链表基本算法的实现；3.掌握利用线性表数据结构解决实际问题的方法和基本技巧；4.按照实验题目要求独立正确地完成实验内容（编写 、调试算法程序 ，提交程序清单及及相关实验数据与运行结果）；5. 按时提交实验报告 。实验环境计算机 、 C 语言程序设计环境实验学时2 学时 ，选做实验 。实验内容一、顺序表的基本操作实现实验要求

2、：数据元素类型 ElemType 取整型 int 。 按照顺序存储结构实现如下算法（各算法边界条件和返回结果适当给出 ）：创建任意整数线性表 （即线性表的元素值随机在键盘上输入）， 长度限定在 20 之内；打印（遍历）该线性表 （依次打印出表中元素值）；在线性表中查找第 i 个元素 ，并返回其值 ；在线性表中第 i 个元素之前插入一已知元素；在线性表中删除第 i 个元素 ；求线性表中所有元素值 （整数 ）之和 ；实验步骤C 源程序代码/*file:seqlist.cpp*/.专业 .整理 .下载可编辑#include<stdio.h>#include<stdlib.h>

3、#include<malloc.h>#define size 20#define elemtype intstruct seqlist elemtype elemsize; int last;void menu() printf("n.");printf("n0.退出操作 .");printf("n1.建立数据类型为整形的顺序表 （长度小于 20).");printf("n2.打印线性表 .");printf("n3.在线性表中查找第 i 个元素，并返回其值 .");printf(&

4、quot;n4.在线性表中第 i 个元素之前插入一已知元素 .");printf("n5.在线性表中删除第 i 个元素 .");printf("n6.求线性表中所有元素值 （整数）之和 .");printf("n7.初始化 .n");void ins(seqlist *L)L->last=-1;void creat(seqlist *L)int i=0;elemtype j;printf(" 请输入线性表元素 (-1 结束 ):");scanf("%d",&j);whil

5、e( j!=-1) L->elemi+=j; L->last+;.专业 .整理 .下载可编辑if(i>size-1)break;scanf("%d",&j);void print(seqlist *L) int i;printf(" 顺序表中元素为 :");for(i=0;i<=L->last;i+)printf("%dt",L->elemi);int find(seqlist *L,int i)if(i<1|i>L->last+1)return 0;elsereturn(

6、L->elemi-1);int insert(seqlist *L,int i,int x)int j;if(L->last+1=size|i<1|i>L->last+2)return 0;L->last+;for( j=L->last;j>=i-1;j-)L->elemj+1=L->elemj;L->elemi-1=x;return 1;int del(seqlist *L,int i) int e,j; if(L->last=-1|i<1|i>L->last+1)return 0;.专业 .整理 .下

7、载可编辑elsee=L->elemi-1;for( j=i;j<=L->last+1;j+)L->elemj-1=L->elemj;L->last-; return 1;int sum(seqlist *L) int i=0,s=0;if(L->last=-1)return 0;for(i=0;i<=L->last;i+) s+=L->elemi;return s;int isempty(seqlist *L) if(L->last=-1) return 1;else return 0;void main()int i,cz,e

8、; elemtype date; seqlist L; menu();printf(" 请输入你要执行的操作的序号:");i=scanf("%d",&cz);while(1)if(!i)printf(" 只能输入数值 ");elsebreak;printf("n再输入一次 ："); rewind(stdin);i=scanf("%d",&cz);.专业 .整理 .下载可编辑while(cz) switch(cz) case 1:if(isempty(&L) ins(&am

9、p;L); creat(&L); elseprintf(" 表已经存在 ，先清空再进行此操作 ！n");break;case 2:if(isempty(&L)printf(" 表为空 n");elseprint(&L);break;case 3:printf(" 输入待查找元素的位置 :n");scanf("%d",&i);if(find(&L,i)printf(" 查找的第 %d 个元素为 %dn",i,find(&L,i);elseprintf

10、(" 查找位置错误 n");break;case 4:printf(" 请输入要插入的元素及位置:n");scanf("%d",&date);scanf("%d",&i);if(insert(&L,i,date)printf(" 插入元素成功 !n");elseprintf(" 插入位置不合法或栈已满!n");break;.专业 .整理 .下载可编辑case 5:printf(" 请输入要删除元素的位置n");scanf("

11、;%d",&i);e=L.elemi-1;if(del(&L,i) printf(" 删除第 %d 个值为 %d 的元素 n",i,e);printf(" 删除成功 n");Else printf(" 删除位置不合法或表已空 n"); break;case 6:if(isempty(&L)printf(" 表已空 !n");else printf(" 线性表中所有元素值 （整数）和:%dn",sum(&L); break;case 7:ins(&

12、L);break;default:printf(" 无此操作 !n");break;menu();printf(" 请输入你要执行的操作的序号:");i=scanf("%d",&cz);while(1) if(!i)printf("n 只能输入数值 "); else break;printf("n再输入一次 ："); rewind(stdin);i=scanf("%d",&cz);.专业 .整理 .下载可编辑测试数据与实验结果7.初始化1.建表2.打印3.查找

13、4.插入不合法长度超过205.删除然后打印4. 插入合法.专业 .整理 .下载可编辑6.求和二、链表（带头结点 ）基本操作实验要求 ：数据元素类型ElemType取字符型char 。 按照动态单循环链表结构实现如下算法（各算法边界条件适当给出）：创建任意字符型有序（递增排序 ）单循环链表（即链表的字符元素随机在键盘上输入 ）， 长度限定在15 之内；打印（遍历）该链表 （依次打印出表中元素值）；在链表中查找第i 个元素 ， i 合法返回元素值，否则 ，返回 FALSE；在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回 FALSE； 在链表中按照有序方式插入一已知字符元素；

14、在线性表中删除第i 个结点 ；计算链表的长度。实验步骤C 源程序代码#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define elemtype char#define size 15static int n=0;typedef struct Nodeelemtype data;.专业 .整理 .下载可编辑struct Node * next;Node,*linklist;void init(linklist *L)*L=(linklist)malloc(sizeof(Node);(*L)->

15、;next=*L;n=0;void creat(linklist L)int i=0,j;Node *s,*r;elemtype csize,t;r=L->next;printf(" 请输入字符型元素 (最多 15 个 ,输入字符 '' 结束 ):"); scanf("%s",c);while(ci!='')n+;i+;i=0;for(i=0;i<n;i+)for( j=i;j<n-i-1;j+)if(cj<cj+1)t=cj;cj=c j+1;c j+1=t;for(i=0;i<n;i+)t

16、=ci;s=(Node *)malloc(sizeof(Node);s->data=t;r->next=s;.专业 .整理 .下载可编辑r=s;void length(linklist L)printf(" 链表长度为 :%d",n);void show(linklist L)int j;Node *p;p=L;if(!p)printf(" 表为空 !");return;for( j=0;j<n;j+)printf("%c",p->next->data);p=p->next;int isempty(

17、linklist L)Node *pre;pre=L;if(pre->next=L)return 1;return 0;void find4(linklist L,int i)int j=0;Node *p;if(i<1|i>size)printf(" 查找位置错误!");p=L;.专业 .整理 .下载可编辑while( j<i)p=p->next;j+;if(i=j)printf("%c",p->data);void find5(linklist L,elemtype k)int i=1,j;Node *p;p=L-

18、>next;if(n=0)printf(" 表为空 !n");return;for( j=0;j<n;j+)if(p->data!=k)p=p->next;else printf("第 %d 个元素是要查找的元素%c",i,k);return;printf(" 链表中无此字符!");void insert(linklist L,elemtype t)Node *r,*s;int i=0;r=L;if(n=size)printf(" 表已满 !");return;for(i;i<n-1&

19、amp;&t<r->next->data;i+).专业 .整理 .下载可编辑i+;r=r->next;s=(Node *)malloc(sizeof(Node);s->data=t;s->next=r->next;r->next=s;printf(" 插入成功 !");n+;return;void del(linklist L,int i)int j=0;Node *p,*r;if(i<1|i>n) printf("删除位置不对 !");return;p=L;while( j<i-

20、1)j+;p=p->next;printf(" 开始删除 ");r=p->next;p->next=r->next;free(r);printf(" 删除成功 !");n-;void menu()printf(".n");printf("0. 退出程序 .n");printf("1. 初始化单循环链表.n");printf("2. 创建任意字符型有序（递减排序最长 15 ）单循环链表 .n");printf("3. 打印（遍历）该链表 （依次

21、打印出表中元素值） .n");.专业 .整理 .下载可编辑printf("4.在链表中查找第i 个元素 .n");printf("5.在链表中查找与一已知字符相同的第一个结点.n");printf("6.在链表中按照有序方式插入一已知字符元素.n");printf("7.在线性表中删除第i 个结点 .n");printf("8.计算链表的长度 .n");printf(".n");void main()int cz,i,j,k;char key,t;linklist

22、L;menu();printf(" 请输入你要执行的操作的序号:");i=scanf("%d",&cz);while(1)if(!i)printf("n只能输入数值 ");elsebreak;printf("n再输入一次 ： ");rewind(stdin);i=scanf("%d",&cz);while(cz)switch(cz)case 1:init(&L);break;case 2:if(isempty(L)creat(L);elseprintf(" 表已存在 ，请先初始化单循环链表!n");.专业 .整理 .下载可编辑break;case 3:show(L);break;case 4:printf(" 请输入查找的第i 个元素的i 值:");j=scanf("%d",&i);whil