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

《2022年C语言数据结构线性表的基本操作实验报告.docx》由会员分享，可在线阅读，更多相关《2022年C语言数据结构线性表的基本操作实验报告.docx（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源试验一线性表的基本操作一、试验目的与基本要求1. 把握数据结构中的一些基本概念；数据、数据项、数据元素、数据类型和数据结构，以及它们之间的关系；2. 明白数据的规律结构和数据的储备结构之间的区分与联系；数据的运算与数据的规律结构的关系；3. 把握次序表和链表的基本操作：插入、删除、查找以及表的合并等运算；4. 把握运用 C 语言上机调试线性表的基本方法；二、试验条件1. 硬件：一台微机2. 软件：操作系统和 C 语言系统三、试验方法确定储备结构后，上机调试实现线性表的基本运算；四、试验内容1. 建立次序表，基本操作包括：初始化，建立一个次序储备的链表，输出次序表，判定是否为空，取表

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

3、素值递减有序（即非递增有序，答应值相同）排列的线性表C；五、附源程序及算法程序流程图1. 源程序（1） ）源程序 试验要求 1 和3 #include #include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arr欢迎下载精品学习资源int * elem; int length; int listsize;Sqlist;void menu;/菜单void InitListSqlist *p;void ShowListSqlist *p;/创建线性表/输出次序线性表void ListDele

4、teSqlist *p,int i,int &e; void ListInsertSqlist *p;e/在次序线性表中删除第i 个元素，并用 e 返回其值/在次序线性表中第i 个元素前插入新元素void ListEmptySqlist *p;void GetListSqlist *p,int i,int &e; void ListInsertSqlist *p,int i,int e;/判定 L 是否为空表/用 e 返回 L 中第 i 个数据元素的值bool compareint a,int b;void LocateElemSqlist *L,int e;/在次序线性表L中查找第 1个值与

5、e中意compared 元素的位序void MergeList_LSqlist *La,Sqlist *Lb;/归并void mainSqlist La;Sqlist Lb;int n,m,x;menu;scanf%d,&n;whilenswitchncase 0: ; break;case 1:InitList&La;break;case 2:ListEmpty&La;break;case 3:printf 请输入插入的位序scanf%d,&m;:n;printf 请出入要插入的数scanf%d,&x;:n;ListInsert&La,m,x;break;case 4:printf 请输入删

6、除元素的位序: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;printfLa中第 %d 个元素的值为 %dn,m,x;break;case 7:ShowList&La;break; case 8:InitList&Lb;break; case 9:MergeList_

7、L&La,&Lb; printf 归并成功 .;break;menu; scanf%d,&n;/* 菜单 */ void menuprintf*nn; printf0.退出 nn;printf1.创建线性表 Lann;printf2.判定 La 是否为空表 nn; printf3.插入元素 Lann;printf4.删除元素 Lann;printf5.定位元素 Lann;printf6.取元素 Lann; printf7.输出线性表 nn;欢迎下载精品学习资源printf8.创建线性表 Lbnn;printf9.归并为一个线性表Lann;printf*nn;/* 创建次序线性表 L*/ voi

8、d InitListSqlist *Lint n; int i=0;L-elem=int *mallocLIST_INIT_SIZE*sizeofint; ifNULL=L-elemprintf 储存支配失败 .n;elseL-length=0;L-listsize=LIST_INIT_SIZE; printf 输入次序表 a:n; scanf%d,&n;whilenL-elemi=n; i+;L-length+;L-listsize=L-listsize-4; scanf%d,&n;/* 输出次序线性表 */ void ShowListSqlist *pint i;if0=p-lengthp

9、rintf 数组为空 .n;欢迎下载精品学习资源elsefori=0;ilength;i+ printf%d,p-elemi;printfn;欢迎下载精品学习资源/* 判定 L 是否为空表 */ void ListEmptySqlist *p欢迎下载精品学习资源if0=p-lengthprintfL是空表 .n;欢迎下载精品学习资源elseprintfL不是空表 .n;欢迎下载精品学习资源/* 在次序线性表中第i 个元素前插入新元素e */ void ListInsertSqlist *p,int i,int eint *newbase; int *q1;int *q2;whileip-len

10、gth+1printf 您输入的 i 超出范畴 .n 请重新输入要插入的位置n:; scanf%d,&i;ifp-length=p-listsizenewbase=int *reallocp-elem,p-listsize+LISTINCREMENT*sizeofint; if.newbaseexit0;欢迎下载精品学习资源elsep-elem=newbase;p-listsize+=LISTINCREMENT;欢迎下载精品学习资源q1=&p-elemi-1;forq2=&p-elemp-length-1;q2=q1;-q2*q2+1=*q2;*q1=e;+p-length;/*/ 在次序线性

11、表中删除第i 个元素，并用 e 返回其值 */ void ListDeleteSqlist *p,int i,int &eint *q1,*q2; whileip-lengthprintf 您输入的 i 超出范畴 . 请重新输入 :; scanf%d,&i;欢迎下载精品学习资源q1=&p-elemi-1; e=*q1;q2=p-elem+p-length-1; for+q1;q1length;/* 对比 a 与 b 相等 */ bool compareint a,int bifa=breturn 1;欢迎下载精品学习资源elsereturn 0;欢迎下载精品学习资源/* 在次序线性表L 中查找

12、第 1 个值与 e 中意 compared 元素的位序 */ void LocateElemSqlist *L,int eint i=1; int *p;p=L-elem;whileilength & .compare*p+,e+i;ifilengthprintf 第 1 个与 e 相等的元素的位序为 %dn,i;欢迎下载精品学习资源elseprintf 没有该元素 .n;欢迎下载精品学习资源/* 用 e 返回 L 中第 i 个数据元素的值 */ void GetListSqlist *p,int i,int &eSqlist *p1; p1=p;e=p1-elemi-1;/*已知次序线性表L

13、a 和 Lb 是元素按值非递减排列*/*把 La 和 Lb 归并到 La 上,La 的元素也是按值非递减*/void MergeList_LSqlist *La,Sqlist *Lbint i=0,j=0,k,t; int *newbase; Sqlist *pa,*pb; pa=La; pb=Lb;欢迎下载精品学习资源whileilength & jlengthifpa-elemi = pb-elemjifpa-listsize=0newbase=int*reallocpa-elem,pa-listsize+LISTINCREMENT*sizeofint;if.newbaseexit0;欢迎

14、下载精品学习资源elsefork=pa-length-1; k=i; k-pa-elemk+1=pa-elemk; pa-length+;pa-elemi=pb-elemj; i+;j+;i+;欢迎下载精品学习资源whilejlengthif pa-listsize length-j newbase=int*reallocpa-elem,pa-listsize+LISTINCREMENT*sizeofint;if.newbaseexit0;forj;jlength;j+,i+pa-elemi=pb-elemj; pa-length+;fori=0;ilength/2;i+t=pa-elemi;

15、pa-elemi=pa-elempa-length-i-1; pa-elempa-length-i-1=t;欢迎下载精品学习资源（2） ）源程序 试验要求 2 和4 #include #include #includetypedef struct LNodeint data;struct LNode *next;LNode, *LinkList;void menu;LinkList InitList;void ShowListLinkList L;void ListDeleteLinkList L,int i,int &e; void ListEmptyLinkList L;void GetL

16、istLinkList L,int i,int &e; void ListInsertLinkList L,int i,int e; bool compareint a,int b;void LocateElemLinkList L,int e;LinkList MergeList_LLinkList La,LinkList Lb;int total=0; void mainLinkList La;LinkList Lb;La=LinkListmallocsizeofstruct LNode; La-next=NULL; Lb=LinkListmallocsizeofstruct LNode;

17、 Lb-next=NULL;int n; int m; int x; menu;scanf%d,&n; whilenswitchncase 0: ; break; case 1:La-next=InitList;break; case 2:ListEmptyLa;break;欢迎下载精品学习资源case 3:printf 请输入要插入到第几个节点前:n; scanf%d,&m;printf 请输入插入的数据 :n; scanf%d,&x; ListInsertLa,m,x;break;case 4:printf 请输入删除元素的位序:n; scanf%d,&m;ListDeleteLa,m,x

18、;printf 删除的元素为 :%dn,x;break; case 5:printf 请输入要找的与线性表中相等的数:n; scanf%d,&m;LocateElemLa,m;break; case 6:printf 请输入查找的位序 :n; scanf%d,&m;GetListLa,m,x;printfLa中第 %d 个元素的值为 %dn,m,x;break; case 7:ShowListLa;break; case 8:Lb-next=InitList;break; case 9:La=MergeList_LLa,Lb; printf 归并成功 n;break;menu; scanf%d

19、,&n;void menuprintf*nn;printf0.退出 nn;printf1.创建线性表 Lann; printf2.判定是否为空表 nn; printf3.插入元素 nn;欢迎下载精品学习资源printf4.删除元素 nn; printf5.定位元素 nn; printf6.取元素 nn; printf7.输出线性表 nn;printf8.创建线性表 Lbnn; printf9.归并两线性表 nn;printf*nn;/创建链式线性表 L LinkList InitListint count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEn

20、d=pNew=LinkListmallocsizeofstruct LNode; printf 请输入数据 :n;scanf%d,&pNew-data;whilepNew-datacount+; ifcount=1欢迎下载精品学习资源elsepNew-next=pHead; pEnd=pNew; pHead=pNew;pNew-next=NULL; pEnd-next=pNew; pEnd=pNew;欢迎下载精品学习资源pNew=LinkListmallocsizeofstruct LNode; printf 请输入数据 :n;scanf%d,&pNew-data;欢迎下载精品学习资源free

21、pNew; total=total+count; return pHead;/判定 L 是否为空表void ListEmptyLinkList LifNULL=L-nextprintf 此表为空表 .n;欢迎下载精品学习资源elseprintf 此表不为空表 .n;欢迎下载精品学习资源/在链式线性表中第i 个元素前插入新元素e void ListInsertLinkList L,int i,int eLinkList p; LinkList s; p=L;int j=0; whilep&jnext;+j;if.p|ji-1printf 不存在您要找的节点 .n;欢迎下载精品学习资源elses=

22、LinkListmallocsizeofint; s-data=e;s-next=p-next; p-next=s;printf 插入节点成功 .n;欢迎下载精品学习资源/输出链式线性表void ShowListLinkList LLinkList p; p=L-next; ifp=NULLprintf 此表为空表 .n;else欢迎下载精品学习资源whilepprintf%d,p-data; p=p-next;printfn;/在链式线性表中删除第i 个元素，并用 e 返回其值void ListDeleteLinkList L,int i,int &eLinkList p; LinkList

23、 q; p=L;int j=0;whilep-next & jnext;+j;if.p-next|ji-1printf 没有找到要删除的位置.;欢迎下载精品学习资源elseq=p-next;p-next=q-next; e=q-data; freeq;欢迎下载精品学习资源/用 e 返回 L 中第 i 个数据元素的值void GetListLinkList L,int i,int &eLinkList p; p=L-next; int j=0;whilep-next & jnext;+j;if.p|ji-1printf 没有找到要查找的位置.;elsee=p-data;欢迎下载精品学习资源/对比

24、 a与 b 相等bool compareint a,int bifa=breturn 1;欢迎下载精品学习资源elsereturn 0;欢迎下载精品学习资源/在链式线性表 L 中查找第 1 个值与 e 中意 compared 元素的位序void LocateElemLinkList L,int eint i=0; LinkList p; p=L;whilep-next & .comparep-data,ep=p-next; i+;ifNULL=p-nextif0=comparep-data,e printf 没有该元素 .n;欢迎下载精品学习资源elseelseprintf 第 1 个与 e

25、相等的元素的位序为 %dn,i;欢迎下载精品学习资源ifcomparep-data,eprintf 没有该元素 .n;LinkList MergeList_LLinkList La,LinkList Lbint i,j,k;LinkList pa_1,pb_1,pa_2,pb_2,pc,pd; pa_1=La-next;pc=pa_2=La;pb_1=pb_2=Lb-next; ifpa_1-data pb_1-datapc=pa_2=Lb; pa_1=Lb-next; pb_1=pb_2=La-next;欢迎下载精品学习资源whilepa_1 & pb_1ifpa_1-data = pb_1

26、-data欢迎下载精品学习资源elsepa_2-next=pb_1; pb_2=pb_1-next; pb_1-next=pa_1; pb_1=pb_2; pa_2=pa_2-next;pa_1=pa_1-next; pa_2=pa_2-next;欢迎下载精品学习资源ifpb_1pa_2-next=pb_1; pd=LinkListmallocsizeofstruct LNode; pd-next=NULL;pa_2=pd; k=total;fori=0;inext; forj=1;jnext;pb_1=LinkListmallocsizeofstruct LNode; pa_2-next=p

27、b_1;pa_2=pa_2-next;pa_2-data=pa_1-data; k-;pa_2-next=NULL; return pd;欢迎下载精品学习资源2. 流程图 试验要求 1 和 3开头输入nNWhile（ n ）Yswitchn欢迎下载精品学习资源123456789欢迎下载精品学习资源欢迎下载精品学习资源创建线性表La判定 L是否为空表插入元素删除元素定位元素取元素输出线性表创建线性表Lb归并为一个线性表 La欢迎下载精品学习资源menu; scanf%d,&n;开头图 1 主函数流程图开头L-elem=int*mallocLIST_INIT_SIZE*sizeofintYNULL

28、=L-elemNL-length=0;L-listsize=LIST_INIT_SIZE;printf输入次序表a:n; scanf%d,&n；Nwhile（n ）YL-elemi=n； i+; L-length+;L-listsize=L-listsize-4; scanf%d,&n;终止图 2 创建线性表La 流程图欢迎下载精品学习资源开头Ns-top=s-baseY此栈为空栈此栈不为空栈终止图 3 判定 La 是否为空表流程图开头0=p-lengthprintfL是空表 .n;printfL不是空表.n;终止图 4 插入元素 La 流程图欢迎下载精品学习资源开头Yip-length+1N

29、i值不在范畴内，重新输入Np-length=p-listsizeY空间不足，接着支配空间p-elem=newbase;p-listsize+=LISTINCREMENT;q1=&p-elemi-1;q2=&p-elemp-length-1Nq2=q1Y*q2+1=*q2;-q2*q1=e;+p-length;终止图 5 删除元素 La 流程图欢迎下载精品学习资源开头p=L-elem;Nilength &.compare*p+,eY+i；NilengthY输出位序没有该元素终止图 6 定位元素 La 流程图开头p1=p;e=p1-elemi-1;终止图 7 取元素 La 流程图欢迎下载精品学习资

30、源开头Y0=p-lengthN数组为空输出全部元素终止图 8 输出线性表流程图欢迎下载精品学习资源开头pa=La; pb=Lb;Nilength & jlengthYpa-elemi = pb-NelemjYNpa-listsize=0Ynewbase=int *reallocpa-elem,pa-listsize+LISTINCREMENT*sizeofint;N.newbaseY1exit0;k=pa-length-1Nk=i欢迎下载精品学习资源Ypa-elemk+1=pa-elemk;k-pa-length+;pa-elemi=pb-elemj;i+; j+;i+;i=0Nilength

31、/2欢迎下载精品学习资源欢迎下载精品学习资源Njlength1YNpa-listsize length-jYnewbase=int *reallocpa-elem,pa-listsize+LISTINCREMENT*sizeofint;N.newbaseYt=pa-elemi;pa-elemi=pa-elempa-length-i-1; pa-elempa-length-i-1=t;欢迎下载精品学习资源Yexit0;欢迎下载精品学习资源Njlengthi+欢迎下载精品学习资源Ypa-elemi=pb-elemj; pa-length+;终止j+ i+图 9 输出线性表流程图欢迎下载精品学习资源

32、流程图试验要求 2 和 4开头menu （）创建头结点La,Lb并输入 nNwhilenYswitchn1创建线性表La2判定是否为空表3456插入元素删除元素定位元素取元素7输出线性表8创建线性表Lb9归并两线性表menu;scanf%d,&n;终止图 10 主函数流程图开头LinkList pHead=NULL; LinkList pEnd,pNew;pEnd=pNew=LinkListmallocsizeofstructLNode; scanf%d,&pNew-data;NpNew-dataYcount+;Ncount=1YpNew-next=pHead;pEnd=pNew;pHead=

33、pNew;pNew-next=NULL; pEnd-next=pNew;pEnd=pNew;pNew=LinkListmallocsizeofstructLNode; scanf%d,&pNew-data;终止图 11 创建线性表 La 流程图欢迎下载精品学习资源开头NNULL=L-nextY输出空表输出不为空表终止图 12 判定是否为空表流程图欢迎下载精品学习资源开头LinkList p;LinkList s;p=L;Np&jnext;+j;.p|ji-1NY输出找不到节点s=LinkListmallocsizeofint;s-data=e;s-next=p-next;p-next=s ；终

34、止图 13 插入元素流程图欢迎下载精品学习资源开头LinkList p;LinkList q; p=L;Np-next & jnext;+j;N.p-next|ji-1Y输出没找到位置q=p-next;p-next=q-next; e=q-data;终止图 14 删除元素流程图欢迎下载精品学习资源开头LinkList p;p=L;开头Np-next & .comparep-data,eYLinkList p;p=L-next;p=p-next;i+;NNULL=p-nextNp-next & jdata,ep=p-next;+j;Y输出位序输出没有该元素.p|ji-1NY没有找到要查找的位置c

35、omparep-data,eNY没有该元素e=p-data;终止终止图 15 定位元素流程图图图 16 取元素流程图欢迎下载精品学习资源开头LinkList pHead=NULL;LinkList pEnd,pNew; pEnd=pNew=LinkListmallocsizeofstructLNode;scanf%d,&pNew-data;NpNew-dataYcount+;Ncount=1YpNew-next=pHead;pEnd=pNew; pHead=pNew;pNew-next=NULL;pEnd-next=pNew; pEnd=pNew;pNew=LinkListmallocsizeofstructLNode; scanf%d,&pNew-data;终止图 17 创建 Lb 流程图欢迎下载精品学习资源开头pa_1=La-next;pc=pa_2=La; pb_1=pb_2=Lb-next;Npa_1-data pb_1-dataYpc=pa_2=Lb; pa_1=Lb-next; pb_1=pb_2=La-next;Npa_1 & pb_