C语言数据结构线性表的基本操作实验报告

1、实验一 线性表的基本操作一、实验目的与基本要求1掌握数据结构中的一些基本概念。数据、数据项、数据元素、数据类型和数 据结构，以及它们之间的关系。2了解数据的逻辑结构和数据的存储结构之间的区别与联系；数据的运算与数 据的逻辑结构的关系。3掌握顺序表和链表的基本操作：插入、删除、查找以及表的合并等运算。4掌握运用 C 语言上机调试线性表的基本方法。二、实验条件1硬件：一台微机2软件：操作系统和 C 语言系统三、实验方法确定存储结构后，上机调试实现线性表的基本运算。四、实验内容1建立顺序表，基本操作包括：初始化，建立一个顺序存储的链表，输出顺序 表，判断是否为空，取表中第 i 个元素，定位函数（返回

2、第一个与 x 相等的 元素位置），插入，删除。2建立单链表，基本操作包括：初始化，建立一个链式存储的链表，输出顺序 表，判断是否为空，取表中第 i 个元素，定位函数（返回第一个与 x 相等的 元素位置），插入，删除。3 假设有两个按数据元素值非递减有序排列的线性表A和B,均以顺序表作为存储结构。编写算法将 A表和B表归并成一个按元素值非递增有序（允许值 相同）排列的线性表C。（可以利用将B中元素插入A中，或新建C表）4.假设有两个按数据元素值非递减有序排列的线性表 A和B,均以单链表作为 存储结构。编写算法将A表和B表归并成一个按元素值递减有序（即非递增有序， 允许值相同）排列的线性表 C。五

3、、附源程序及算法程序流程图1. 源程序（1）源程序 （实验要求 1和 3）#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arrint * elem;int length;int listsize;出 nn）;Sqlist;void menu（）;printf( 1.创建线性表 Lann);printf( 2. 判断 La 是否为空表 nn);printf( 3.插入元素 (La)nn);printf( 4.删除元素 (La)nn);printf( 5.定位元素 (La)nn);printf( 6.取元素 (La

4、)nn);printf( 7.输出线性表 nn);printf( 8.创建线性表 Lbnn);printf( 9. 归并为一个线性表 Lann);printf(*nn);/* 创建顺序线性表 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);elseL-length=0;L-listsize=LIST_INIT_SIZE;printf( 输入顺序表 a:n); scanf(%d,&n);while

5、(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/* 在顺序线性表中第i 个

6、元素前插入新元素 e */void ListInsert(Sqlist *p,int i,int e)int *newbase;int *q1;int *q2;while(ip-length+1)n:);printf( 您输入的 i 超出范围 !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+=LIST

7、INCREMENT; 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;/* 对

8、比 a 与 b 相等 */ bool compare(int a,int b)if(a=b) return 1;else return 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);else printf( 没有该元素 !n);/* 用 e 返回 L 中第 i 个数据

9、元素的值 */ 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)newba

10、se=(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)e

11、xit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;(2)源程序 (实验要求 2 和 4)typedef struct LNodeint data; struct LNode *next;LNode, *LinkList; void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete

12、(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(LinkList L,int e);LinkList MergeList_L(LinkList La,LinkList Lb); int total=0;void main()LinkList La;LinkList Lb;La=(LinkList)ma

13、lloc(sizeof(struct LNode); La-next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode); Lb-next=NULL;int n;int m;int x; menu();scanf(%d,&n); while(n)switch(n)case 0: ; break; case 1:La-next=InitList();break;case 2:ListEmpty(La);break;case 3:n);printf( 请输入要插入到第几个节点前 scanf(%d,&m);printf( 请输入插入的数据 :n); scanf

14、(%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:ShowLi

15、st(La);break;case 8:Lb-next=InitList();break;case 9:La=MergeList_L(La,Lb);printf( 归并成功 n);break;menu();scanf(%d,&n);void menu()printf(*nn);printf(0.退出 nn ”)；printf(1.创建线性表 Lann);printf(2.判断是否为空表 nn);printf(3.插入元素 nn);printf(4.删除元素 nn);printf(5.定位元素 nn);printf(6.取元素 nn);printf(7.输出线性表 nn);printf(8.创建

16、线性表 Lbnn);printf(9.归并两线性表 nn);printf(*nn);程图(实验要求1和3)图1主函数流程图图2创建线性表La流程图图3判断La是否为空表流程图 图4插入元素(La)流程图 图5删除元素(La)流程图 图6定位元素(La)流程图图7取元素(La)流程图 图8输出线性表流程图 图9输出线性表流程图 流程图(实验要求2和4)开始图10主函数流程图图11创建线性表La流程图图12判断是否为空表流程图图13插入元素流程图 图14删除元素流程图图15定位元素流程图图图16取元素流程图图17创建Lb流程图 图18归并两表流程图六、运行结果1. （ 实验要求 1和 3） 点击运行，首先出现的是菜单界面，选择菜单选项进行操作，如图所示。按“ 1”回车后，即可以创建顺序表La，输入“0”结束添加，如图所示 输入 2，判断 La 是否为空表，如图所示。 输入 3，在指定的位序插入元素，如图所示