数据结构试验1顺序表链表讲解

1、除海工禽院针篇机科禽系实验报告书课程名:题目:班级:学号:姓名：数据结构线性表数据结构试验软件112评语:成绩:指导教师:批阅时间： 年 月EI数据结构实验报告线性表实验报告要求1目的与要求：1）掌握线性表数据结构的基本概念和抽象数据类型描述：2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现：4）熟练掌握线性表的链式存储结构的基本操作算法实现；5）掌握线性表在实际问题中的应用和基本编程技巧；6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结 果）；7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电

2、子（全班同 学提交到学委，再统一打包提交给老师）和纸质（每班每次5份，学委安排，保证每个同学至 少提交一次）；8）积极开展实验组组内交流和辅导，严禁复制和剽窃他人实验成果，一旦发现严肃处理;9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操 作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。2实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表）,长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印

3、/显示出表中元素值）；3）在顺序表中查找第1个元素，并返回其值；4）在顺序表第1个元素之前插入一已知元素；5）在顺序表中删除第1个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型ElemType取字符型chac按照动态单链表结构实现如卞算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序）；3）在链表中查找第1个元素，1合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TR

4、UE,否则，返回FALSE；5）在链表中第1个结点之前插入一个新结点；6）在线性表中删除第1个结点；数据结构实验报告7）计算链表的长度。3实验步骤与源程序#include #define OK1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType intdefine MAXSIZE 25 /*此处的宏定义常量表示线性表可能达到的最人长度*/using namespace std;typedef struetElemType elemMAXSIZE;/*线性表占用的数组空间*/intlast;/*记录线性表中最后一个元素在数组e

5、lem中的位置(下标值)，空表置为-1*/SeqList;void OutputSeqList(SeqList *L)cout顺序表如下：Xendl;int i;for(i=0;ilast;i+)coutLelemi，n ;coutendl;int GetDate(SeqList *L)int t;cout，/请输入要查找的元素的序数：endl;cint;if ( tL-last)数据结构实验报告cout输入错误！ “;return(ERROR);else return(LelemLt-lJ);int InsList (SeqList *L)int i, e;cout，/请输入要插入的元素插入

6、位置及要插入的元素endl;cinie;int k;if(iL-last+2) /*首先判断插入位置是否合法*/printfC插入位置i值不合法)；return(ERROR);if(L-last= MAXSIZE-1)printfC表已满无法插入)；return(ERROR);for (k=L-last ;k=il; k-)/*为插入元素而移动位置*/Lelemk+l=Lelemk;L-elemi-l=e;/*在C语言数组中，第i个元素的下标为LI*/L-last+;return(OK);int DelList (SeqList *L, ElemType *m)int w;cout请输出要删除

7、的元素位置:z/endl;数据结构实验报告4cinw;int k;if(wL-last+l)cout删除位置不合法!elemwl ;/*将删除的元素存放到e所指向的变量中*/for(k=w; klast; k+)L-elemk-l = L-elemk ;/*将后面的元素依次前移*/L-last;return(OK);int sum(SeqList *L)int i,n=0;for(i=0;ilast+l;i+)n=n+Lelemi;return(n);void mainOint *q, n;SeqList *L;L=(SeqList*)malloc(sizeof (SeqList); q =

8、(int*)malloc(sizeof(int); coutlas t 二 nT;cout请输入顺序表：endl;数据结构实验报告for(i=0;ielemi;while (c!二n )cout/z请选择你要进行的操作:z/endl;cout，l.输出顺序表；n2.查找元素；n3.插入元素：n4.删除元 素；求和endl;int xuanze;cinxuanze;switch(xuanze)case 1:OutputSeqList( L);break;case 2:coGetDat( L) endl;break;case 3:InsList( L);break;case 4:DelList(L

9、, q);break:case 5:cosum( L)endl;break;cout是否要继续进行操作y/nendl;cinc;#mclude #mclude#define MAX 15#define TURE 1#define FALSE 0 tvpedef char ElemType； tvpedef stmct Nodechar date;stmct Node * next; Node,*LnikList; void InitList(LuikList *L)*L=(LnikList)nialloc(sizeof(char);数据结构实验报告(*L)-next=NULL;void Pri

10、iitfLink(LHikList L)LinkList p; p=L next; pnntf(”链表为:“); while(p!=NULL)pnntf(H%c rp-date); p=p-next;void Create(LiiikList L)LinkList sj;char c;int flag=l;int n;r=L;pnntf(”元素个数:“)； scanfC%dS&ii);if(nMAX)printf(超出限定长度! ”);elseputf(”输入字符(以琏建结束 while(flag)scanf(”c 役&c); if(cF)s=(Node*)malloc(sizeof(char

11、);s-date=c;r-next=s;尸s;elseflag=O;r-next =NULL;void Ordei(LuikList L)char c;数据结构实验报告Nodefbr(i-L-next;r-next! =NULL;i-=r-next) p=【；fbr(q=r-next; q: q=q-next)if(q-date)date)p=q； if(p!=r) c=r-date; i-date=p-date; p-date=c; PrmtfLuik(L);void Get(LinkList L. int i，ElemType *e)int j; Node *p;P=L；J=；while

12、(p-next! =NULL)&p=p-next;J+;*e=p-date ;printf(ll|?%d 个元素为:c”,i广e);elsepimtf(MFALSEH);void Locate(LinkList L. ElemType e)int i=l;LinkList p;p=L-next; while(p&p-date! =e) i=i+; p=p-next;if(!p)pnntf(nFALSEnH);elsepnntf(nTRUEnn); 数据结构实验报告 printf(”该元素在第d个位置!”,i-1);void InsList(LinkList Ljnt iElemType e)N

13、ode *p,*s;int k=0;P=L；wlule(p!=NULL & knext;k=k卄；if(!p)pnntf(”插入位置不合理! ”)；s=(Node*)inalloc(sizeof(char);s-date=e; s-next=p next;p next=s;Oider(L);void DelList(LnikList i.ElemType *e)Node *p,*r;mtj;J=0；P=L；wlule(p-next! =NULL)&p=p-next; J+;if(p-next! =NULL)p-next=p-next-next;r=p-next;*e=r-date;删除第d 个

14、元素:cn”,i,*e);elsepnntf(”删除结点的位置i不合理!”)；void ListLength(LuikList L)数据结构实验报告Node *p;intj=O; p=L-next; while(p!=NULL)p=p-next;J+；pnntfC单链表的长度:%d-j）;void menu()pnntf（”n1.创建任意字符型单循坏链表”）；prmtf（Hn2.打印（遍历）该链表”）；3.查找第1个元素”）；pnntf（”n4.查找与一已知字符相同的元素”）;prmtf（Hn5.插入元素”）；6.删除第1个结点”）；pnntf（”n7.计算链表的长度”）；&退出”）；n *

15、*void main()mt i;int flag=O;ElemTvpe e;LinkList L;L=(LinkList)malloc(sizeof(char);InitList(&L);menuQ;while(!flag)pnntf(niin请输入你的选揪18):”); scanf(”dt&i);switch(i) case 1:Create(L); break;case 2:Order(L); break;case 3:pnntff输入要查找的第1个元素J; scanff%d 役&i）;数据结构实验报告Get(L,i, & 亡)； break;case 4:prmtfC输入查找的元素:”

16、)； rewind(stdin);scanf(”c 役&e);Locate(L,e);break;case 5:pruitf(输入插入的元素:”)； rewind(stdin);scanf(”c 役&e);InsList(L,i,e); break;case 6:prmtfC输入要删除第几个结点:”); scanf(”d 役&i);DelList(L,i,&e); break;case 7:ListLength(L); break;case &flag=l； break; 4测试数据与实验结果（可以抓图粘贴）数据结构实验报告11回数据结构实验报告C:UsersuserDesktopDebugCppl.exe*是否要继续进行操作y请行的操作：津辉，