数据结构实验1顺序表-链表

数据结构实验1顺序表-链表淮海工学院计算机科学系实验报告书课程名： 《数据结构》题 目： 线性表数据结构试验班级：软件112学号：姓名：评语：《 数据结构 》实验报告 -0-线性表实验报告要求1目的与要求:1）掌握线性表数据结构的基本概念和抽象数据类型描述；2）熟练掌握线性表数据结构的顺序和链式存储存表示；3）熟练掌握线性表顺序存储结构的基本操作算法实现；4）熟练掌握线性表的链式存储结构的基本操作算法实现;5）掌握线性表在实际问题中的应用和基本编程技巧;6）按照实验题目要求独立正确地完成实验内容（提交程序清单及相关实验数据与运行结果）；7）按照报告格式和内容要求，认真书写实验报告，并在试验后的第三天提交电子（全班同学提交到学委，再统一打包提交给老师）和纸质（每班每次5份，学委安排，保证每个同学至少提交一次）；8）积极开展实验组组内交流和辅导， 严禁《 数据结构 》实验报告 -1-复制和剽窃他人实验成果，一旦发现严肃处理；9）上实验课前，要求每个同学基本写好程序，并存储在自己的U盘上，用于实验课堂操作时调试和运行。凡不做准备，没有提前编写程序者，拒绝上机试验。实验内容或题目一、顺序表的基本操作实现实验要求：数据元素类型ElemType取整型int。按照顺序存储结构实现如下算法：1）创建任意整数线性表（即线性表的元素值随机在键盘上输入）的顺序存储结构（即顺序表），长度限定在25之内；2）打印/显示（遍历）该线性表（依次打印 /显示出表中元素值）；3）在顺序表中查找第 i个元素，并返回其值；4）在顺序表第i个元素之前插入一已知元素；5）在顺序表中删除第 i个元素；6）求顺序表中所有元素值（整数）之和；二、链表（带头结点）基本操作实验要求：数据元素类型 ElemType取字符型char。按《 数据结构 》实验报告 -2-照动态单链表结构实现如下算法：1）按照头插法或尾插法创建一个带头结点的字符型单链表（链表的字符元素从键盘输入），长度限定在10之内；2）打印（遍历）该链表（依次打印出表中元素值，注意字符的输入顺序与链表的结点顺序） ；3）在链表中查找第 i个元素，i合法返回元素值，否则，返回FALSE；4）在链表中查找与一已知字符相同的第一个结点，有则返回TRUE，否则，返回FALSE；5）在链表中第i个结点之前插入一个新结点；6）在线性表中删除第 i个结点；7）计算链表的长度。实验步骤与源程序#include<iostream>#defineOK 1#defineERROR0#defineTRUE1#defineFALSE0#defineElemTypeint#define MAXSIZE25/* 此处的宏定义常量表示《 数据结构 》实验报告 -3-线性表可能达到的最大长度 */usingnamespacestd;typedefstruct{ElemTypeelem[MAXSIZE];/*线性表占用的数组空间*/int last; /* 记录线性表中最后一个元素在数组elem[]中的位置（下标值），空表置为-1*/}SeqList;voidOutputSeqList(SeqList*L){cout<<"顺序表如下："<<endl;inti;for(i=0;i<=L->last;i++)cout<<L->elem[i]<<'\n';cout<<endl;}intGetDate(SeqList*L)《 数据结构 》实验报告 -4-{intt;cout<<"请输入要查找的元素的序数："<<endl;cin>>t;if((t<0)||(t>L->last)){cout<<"输入错误！";return(ERROR);}elsereturn(L->elem[t-1]);}intInsList(SeqList*L){inti,e;cout<<"请输入要插入的元素插入位置及要插入的元素"<<endl;cin>>i>>e;intk;if((i<1)||(i>L->last+2))/* 首先判断插入《 数据结构

》实验报告

-5-位置是否合法

*/{printf(" 插入位置

i

值不合法

");return(ERROR);}if(L->last>=MAXSIZE-1){printf("表已满无法插入return(ERROR);

");}for(k=L->last;k>=i-1;k--)

/*

为插入元素而移动位置

*/L->elem[k+1]=L->elem[k];L->elem[i-1]=e;/*在C语言数组中，第i个元素的下标为i-1*/L->last++;return(OK);}intDelList(SeqList*L,ElemType*m)《 数据结构 》实验报告 -6-{intw;cout<<"请输出要删除的元素位置： "<<endl;cin>>w;intk;if((w<1)||(w>L->last+1)){cout<<"删除位置不合法!"<<endl;;return(ERROR);}*m=L->elem[w-1];/* 将删除的元素存放到 e所指向的变量中*/L->elem[k-1]=L->elem[k];

/*

将后面的元素依次前移

*/L->last--;return(OK);}intsum(SeqList*L)《 数据结构 》实验报告 -7-{inti,n=0;for(i=0;i<L->last+1;i++)n=n+L->elem[i];return(n);}voidmain(){int*q,n;SeqList *L;L=(SeqList*)malloc(sizeof(SeqList));q=(int*)malloc(sizeof(int));cout<<"请输入顺序表长度：";cin>>n;L->last=n-1;cout<<"请输入顺序表："<<endl;inti;《 数据结构 》实验报告 -8-for(i=0;i<n;i++)cin>>L->elem[i];charc='y';while(c!='n'){cout<<"请选择你要进行的操作："<<endl;cout<<"1.输出顺序表；"<<'\n'<<"2.查找元素；"<<'\n'<<"3.插入元素；"<<'\n'<<"4.删除元素；"<<'\n'<<"5.求和"<<endl;intxuanze;cin>>xuanze;switch(xuanze){case1:OutputSeqList(L);break;case2:cout<<GetDate(L)<<endl;break;case3:InsList(L);break;case4:DelList(L,q);break;case5:cout<<sum(L)<<endl;break;;}《 数据结构 》实验报告 -9-cout<<"是否要继续进行操作 y/n:"<<endl;cin>>c;}#include<stdio.h>#include<malloc.h>#defineMAX15#defineTURE1#defineFALSE0typedefcharElemType;typedefstructNode{chardate;structNode*next;}Node,*LinkList;voidInitList(LinkList*L){*L=(LinkList)malloc(sizeof(char));(*L)->next=NULL;}voidPrintfLink(LinkListL){LinkListp;《 数据结构 》实验报告 -10-p=L->next;printf("链表为:");while(p!=NULL){printf("%c",p->date);p=p->next;}}voidCreate(LinkListL){LinkLists,r;charc;intflag=1;intn;r=L;printf("元素个数:");scanf("%d",&n);if(n>MAX)printf("超出限定长度!");else{printf("输入字符(以#键结束):");while(flag)《 数据结构 》实验报告 -11-{scanf("%c",&c);if(c!='#'){s=(Node*)malloc(sizeof(char));s->date=c;r->next=s;r=s;}elseflag=0;r->next=NULL;}}}voidOrder(LinkListL){charc;Node*r,*q,*p;for(r=L->next;r->next!=NULL;r=r->next){p=r;for(q=r->next;q;q=q->next)《 数据结构 》实验报告 -12-if((q->date)<(p->date))p=q;if(p!=r){c=r->date;r->date=p->date;p->date=c;}}PrintfLink(L);}void Get(LinkListL,inti,ElemType*e){intj;Node *p;p=L;j=-1;while((p->next!=NULL)&&(j<i)){p=p->next;j++;}*e=p->date;if(i==j)printf("第%d个元素为:%c",i,*e);《 数据结构 》实验报告 -13-elseprintf("FALSE");}voidLocate(LinkListL,ElemTypee){inti=1;LinkListp;p=L->next;while(p&&p->date!=e){i=i++;p=p->next;}if(!p)printf("FALSE\n");else{printf("TRUE\n");printf("该元素在第%d个位置!",i-1);}}voidInsList(LinkListL,inti,ElemTypee){《 数据结构 》实验报告 -14-Node*p,*s;intk=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(LinkListL,inti,ElemType*e){Node*p,*r;intj;j=0;《 数据结构 》实验报告 -15-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个元素:%c\n",i,*e);}elseprintf("删除结点的位置 i不合理!");}voidListLength(LinkListL){Node*p;intj=0;p=L->next;while(p!=NULL){p=p->next;《 数据结构

》实验报告

-16-j++;}printf("

单链表的长度

:%d",j);}voidmenu(){printf("\n************************ 菜 单*********************");printf("\n 1.创建任意字符型单循环链表");printf("\nprintf("\nprintf("\n

2.打印（遍历）该链表");3.查找第i个元素");4.查找与一已知字符相同的元素");printf("\n

5.插入元素

");printf("\n

6.删除第

i个结点

");printf("\n

7.计算链表的长度

");printf("\n8.退出");printf("\n***********************************************");}voidmain(){《 数据结构 》实验报告 -17-inti;intflag=0;ElemTypee;LinkListL;L=(LinkList)malloc(sizeof(char));InitList(&L);menu();while(!flag){printf("\n\n 请输入你的选择