资源预览内容
第1页 / 共32页
第2页 / 共32页
第3页 / 共32页
第4页 / 共32页
第5页 / 共32页
第6页 / 共32页
第7页 / 共32页
第8页 / 共32页
第9页 / 共32页
第10页 / 共32页
亲,该文档总共32页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
实验一 线性表的基本操作一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数 据结构,以及它们之间的关系。2了解数据的逻辑结构和数据的存储结构之间的区别与联系;数据的运算与数 据的逻辑结构的关系。3掌握顺序表和链表的基本操作:插入、删除、查找以及表的合并等运算。4掌握运用 C 语言上机调试线性表的基本方法。二、实验条件1硬件:一台微机2软件:操作系统和 C 语言系统三、实验方法确定存储结构后,上机调试实现线性表的基本运算。四、实验内容1建立顺序表,基本操作包括:初始化,建立一个顺序存储的链表,输出顺序 表,判断是否为空,取表中第 i 个元素,定位函数(返回第一个与 x 相等的 元素位置),插入,删除。2建立单链表,基本操作包括:初始化,建立一个链式存储的链表,输出顺序 表,判断是否为空,取表中第 i 个元素,定位函数(返回第一个与 x 相等的 元素位置),插入,删除。3假设有两个按数据元素值非递减有序排列的线性表A和B,均以顺序表作为 存储结构。编写算法将 A 表和 B 表归并成一个按元素值非递增有序(允许值 相同)排列的线性表C。(可以利用将B中元素插入A中,或新建C表)4.假设有两个按数据元素值非递减有序排列的线性表A和B,均以单链表作为 存储结构。编写算法将 A 表和 B 表归并成一个按元素值递减有序(即非递增有 序,允许值相同)排列的线性表 C。五、附源程序及算法程序流程图1.源程序(1)源程序(实验要求 1 和 3)#include#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arr/菜单/ 创建线性表/ 输出顺序线性表在顺序线性表中删除第i个元素,并用e返回其值/在顺序线性表中第i个元素前插入新元素/ 判断 L 是否为空表/用e返回L中第i个数据元素的值/ 在顺序线性表 L 中查找第 1 个值与 e 满足int * elem; int length; int listsize; Sqlist;void menu();void InitList(Sqlist *p);void ShowList(Sqlist *p);void ListDelete(Sqlist *p,int i,int &e); / void ListInsert(Sqlist *p);evoid ListEmpty(Sqlist *p);void GetList(Sqlist *p,int i,int &e);void ListInsert(Sqlist *p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist *L,int e); compare()d 元素的位序void MergeList_L(Sqlist *La,Sqlist *Lb);/ 归并void main()Sqlist La;Sqlist Lb; int n,m,x; menu();scanf(%d,&n); while(n)switch(n)case 0: ; break; case 1:InitList(&La);break; case 2:ListEmpty(&La);break; case 3:printf(请输入插入的位序:n); scanf(%d,&m);printf(请出入要插入的数:n); scanf(%d,&x); ListInsert(&La,m,x);break;case 4:printf(请输入删除元素的位序:n); scanf(%d,&m);ListDelete(&La,m,x);printf(删除的元素为:dn,x);break; case 5:printf(”请输入要找的与线性表中相等的数:n); scanf(%d,&m);LocateElem(&La,m);break; case 6:printf(请输入查找的位序:n); scanf(%d,&m); GetList(&La,m,x);printf(La 中第d 个元素的值为dn,m,x);break; case 7:ShowList(&La);break;case 8: InitList(&Lb);break;case 9: MergeList_L(&La,&Lb); printf(归并成功!);break;menu(); scanf(%d,&n); /*菜单*/ void menu()printf(0.退出 nn);printf(1.创建线性表 Lann);printf(2判断La是否为空表nn);printf(3.插入元素(La)nn);printf(4.删除元素(La)nn);printf(5.定位元素(La)nn);printf(6.取元素(La)nn);printf(7.输出线性表nn);printf( 8.创建线性表 Lbnn);printf( 9.归并为一个线性表 Lann);/*创建顺序线性表 L*/ void InitList(Sqlist *L) int n;int i=0;L-elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int); if(NULL=L-elem)printf(储存分配失败!n); else L-length=0;L-listsize=LIST_INIT_SIZE;printf(输入顺序表a:n); scanf(%d,&n); while(n) L-elemi=n;i+;L-length+;L-listsize=L-listsize-4; scanf(%d,&n);/*输出顺序线性表*/ void ShowList(Sqlist *p)int i;if(0=p-length)printf(数组为空!n);elsefor(i=0;ilength;i+)printf(%d ,p-elemi); printf(n);/*判断L是否为空表*/void ListEmpty(Sqlist *p)if(0=p-length)printf(L 是空表!n);elseprintf(L 不是空表!n);/*在顺序线性表中第i个元素前插入新元素e */void ListInsert(Sqlist *p,int i,int e)int *newbase;int *q1;int *q2;while(ip-length+1) printf(”您输入的i超出范围!n请重新输入要插入的位置n:); scanf(%d,&i); if(p-length=p-listsize)newbase=(int *)realloc(p-elem,(p-listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);else p-elem=newbase; p-listsize+=LISTINCREMENT; q1=&(p-elemi-1);for(q2=&(p-elemp-length-1);q2=q1;-q2) *(q2+1)=*q2;*q1=e; +p-length;/*/在顺序线性表中删除第i个元素,并用e返回其值*/void ListDelete(Sqlist *p,int i,int &e)int *q1,*q2;while(ip-length)printf(您输入的i超出范围!请重新输入:”); scanf(%d,&i);q1=&(p-elemi-1);e=*q1; q2=p-elem+p-length-1;for(+q1;q1length;/*对比 a 与 b 相等*/bool compare(int a,int b)if(a=b)return 1;elsereturn 0;/*在顺序线性表 L 中查找第 1 个值与 e 满足 compare()d 元素的位序*/ void LocateElem(Sqlist *L,int e)int i=1;int *p;p=L-elem;while(ilength & !compare(*p+,e)+i;if(ilength)printf(第1个与e相等的元素的位序为dn,i);elseprintf(没有该元素!n);/*用e返回L中第i个数据元素的值*/void GetList(Sqlist *p,int i,int &e)Sqlist *p1;p1=p;e=p1-elemi-1;/*已知顺序线性表La和Lb是元素按值非递减排列*/*把La和Lb归并到La上,La的元素也是按值非递减*/void MergeList_L(Sqlist *La,Sqlist *Lb)int i=0,j=0,k,t;int *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(ilength & jlength)if(pa-elemi = pb-elemj)if(pa-listsize=0)newbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);for(k=pa-length-1; k=i; k-) pa-elemk+1=pa-elemk;pa-length+;pa-elemi=pb-elemj;i+;j+;elsei+;while(jlength)if( pa-listsize length-j )newbase=(int*)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int); if(!newbase)exit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号