实验一 顺序表基本操作

实验一顺序表基本操作实验一顺序表基本操作实验一顺序表基本操作实验一顺序表基本操作编制仅供参考审核批准生效日期地址：电话：传真:邮编:实验一顺序表基本操作一实验目的1.学会定义线性表的顺序存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。2.掌握顺序表的基本操作，实现顺序表的插入、删除、查找以及求并集等运算。3.掌握对多函数程序的输入、编辑、调试和运行过程。二实验要求1．预习C语言中结构体的定义与基本操作方法。2．对顺序表的每个基本操作用单独的函数实现。3．编写完整程序完成下面的实验内容并上机运行。4．整理并上交实验报告。三实验内容：1．编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。(2)将La置为空表。(3)销毁La。(4)在La中插入一个新的元素。(5)删除La中的某一元素。(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。(7)打印输出La中的元素值。2．编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=A∪B。四思考与提高假设两个顺序线性表La和Lb分别表示两个集合A和B，如何实现A=A∩B1．编写程序实现顺序表的下列基本操作：(1)初始化顺序表La。(2)将La置为空表。(3)销毁La。(4)在La中插入一个新的元素。(5)删除La中的某一元素。(6)在La中查找某元素，若找到，则返回它在La中第一次出现的位置，否则返回0。(7)打印输出La中的元素值。#include<>#include<>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineYES1#defineNO0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;Statuscmp(ElemTypea,ElemTypeb){if(a==b)returnYES;elsereturnNO;}//构造空的顺序表LaStatusInitList_Sq(SqList&L){=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!exit(OVERFLOW);=0;=LIST_INIT_SIZE;returnOK;}//撤销线性表L；StatusDestroy_Sq(SqList&L){free;=NULL;=0;=0;returnOK;}//清空线性表StatusClearList_Sq(SqList&L){=0;//memset(L,0,sizeof(L));returnOK;}//在顺序线性表L的第i个元素之前插入新的元素eStatusListInsert_Sq(SqList&L,inti,ElemTypee){ElemType*p;if(i<1||i>+1)returnERROR;if>={ElemType*newbase=(ElemType*)realloc,+LISTINCREMENT)*sizeof(ElemType));if(!newbase)returnERROR;=newbase;+=LISTINCREMENT;}ElemType*q=&[i-1]);for(p=&[]);p>=q;--p)*(p+1)=*p;*q=e;++;returnOK;}//在顺序线性表L中删除第i个元素，并用e返回其值StatusListDelete_Sq(SqList&L,inti,ElemType&e){ElemType*p,*q;if(i<1||i>returnERROR;p=&[i-1]);e=*p;q=+;for(++p;p<=q;++p)*(p-1)=*p;;returnOK;}//ListDelete_SqStatusLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的位序inti;ElemType*p;i=1;p=;while(i<=&&!(*compare)(*p++,e))++i;if(i<=returni;elsereturn0;}//打印顺序表voidPrintList_Sq(SqListL){inti;for(i=0;i<;i++)printf("%d",[i]);printf("\n");}intmain(){SqListLa;inti,n,e;printf("请输入元素个数：\n");scanf("%d",&n);if(InitList_Sq(La)){for(i=1;i<=n;i++){printf("请输入第%d个元素\n",i);scanf("%d",&e);ListInsert_Sq(La,i,e);}printf("-------------------------------------\n你输入的元素分别为：\n");PrintList_Sq(La);printf("-------------------------------------\n");}else{printf("初始化线性表出错！\n");printf("-------------------------------------\n");}printf("请输入你要插入的元素及插入的位置：\n");//插入元素scanf("%d%d",&e,&i);if(ListInsert_Sq(La,i,e)){printf("插入元素后线性表为：\n");PrintList_Sq(La);printf("-------------------------------------\n");}else{printf("输入位置有错！\n");printf("-------------------------------------\n");}/**/printf("请输入你要删除的元素的位置：\n");//删除元素scanf("%d",&i);if(ListDelete_Sq(La,i,e)){printf("你删除的元素为：%d,删除元素后线性表为：\n",e);PrintList_Sq(La);printf("-------------------------------------\n");}else{printf("输入位置有错！\n");printf("-------------------------------------\n");}printf("请输入你要查找的元素：\n");//查找元素scanf("%d",&e);if(i=LocateElem_Sq(La,e,cmp)){printf("你要查找的元素在第%d个位置。\n",i);printf("-------------------------------------\n");}else{printf("找不到这个元素：\n");printf("-------------------------------------\n");}if(ClearList_Sq(La))//清空线性表{printf("线性表已清空。\n");printf("--------------------------------------\n");}else{printf("线性表清空出错。\n");printf("--------------------------------------\n");}if(Destroy_Sq(La))//撤销线性表{printf("线性表已撤销。\n");printf("--------------------------------------\n");}else{printf("线性表清空出错。\n");printf("--------------------------------------\n");}return0;}2．编写程序完成下面的操作：(1)构造两个顺序线性表La和Lb，其元素都按值非递减顺序排列。(2)实现归并La和Lb得到新的顺序表Lc，Lc的元素也按值非递减顺序排列。(3)假设两个顺序线性表La和Lb分别表示两个集合A和B，利用union_Sq操作实现A=A∪B。#include<>#include<>#defineTRUE1#defineFALSE0#defineYES1#defineNO0#defineOK1#defineERROR0#defineINFEASIBLE-1#defineOVERFLOW-2typedefintStatus;typedefintElemType;#defineLIST_INIT_SIZE100#defineLISTINCERMENT10typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_Sq(SqList&L){//构造空的顺序表La=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!exit(OVERFLOW);=0;=LIST_INIT_SIZE;returnOK;}/**/StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序线性表L的第i个元素之前插入新的元素eElemType*p;if(i<1||i>+1)returnERROR;if>={ElemType*newbase=(ElemType*)realloc,+LISTINCERMENT)*sizeof(ElemType));if(!newbase)returnERROR;=newbase;+=LISTINCERMENT;}ElemType*q=&[i-1]);for(p=&[]);p>=q;--p)*(p+1)=*p;*q=e;++;returnOK;}StatusListDelete_Sq(SqList&L,inti,ElemType&e){//在顺序线性表L中删除第i个元素，并用e返回其值ElemType*p,*q;if(i<1||i>returnERROR;p=&[i-1]);e=*p;q=+;for(++p;p<=q;++p)*(p-1)=*p;;returnOK;}//ListDelete_SqStatuscmp(ElemTypea,ElemTypeb){if(a==b)returnYES;elsereturnNO;}StatusLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的位序inti;ElemType*p;i=1;p=;while(i<=&&!(*compare)(*p++,e))++i;if(i<=returni;elsereturn0;}voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){//已知顺序线性表La和Lb的元素按值非递减排列。归并La和Lb得到新的顺序线性表Lc，Lc的元素也按值非递减排列。ElemType*pa,*pb,*pc,*pa_last,*pb_last;pa=;pb=;==+;pc==(ElemType*)malloc*sizeof(ElemType));if(!exit(OVERFLOW);//存储分配失败pa_last=+;pb_last=+;while(pa<=pa_last&&pb<=pb_last){//归并if(*pa<=*pb)*pc++=*pa++;else*pc++=*pb++;}while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素}//MergeListvoidUnion_Sq(SqList&La,SqListLb){intlen1=;intlen2=;inti,pl;ElemTypee;//for(i=1;i<=len2;i++){pl=LocateElem_Sq(La,[i-1],cmp);if(pl==0) {ListInsert_Sq(La,++len1,[i-1]); }}len1=;for(i=0;i<len1;i++){if[i]==[i+1])ListDelete_Sq(La,i+2,e);}/*注意在原来La中，如果有重复也要删除到只剩下一个*/}voidPrintList_Sq(SqListL){inti;for(i=0;i<;i++)printf("%d",[i]);printf("\n");}intmain(){SqListLa,Lb,Lc;inti,n1,n2,e;printf("请输入La元素个数：\n");scanf("%d",&n1);if(InitList_Sq(La)){for(i=1;i<=n1;i++){printf("请输入La的第%d个元素！\n",i); scanf("%d",&e);ListInsert_Sq(La,i,e);}//printf("-------------------------------------\nLa的元素分别为：\n");//PrintList_Sq(La);printf("