数据结构实验指导书——线性表的操作

实验1线性表的基本操作一、实验目的(1)掌握线性表的逻辑特征；(2)掌握线性表顺序存储结构的特点，熟练掌握顺序表的基本运算；(3)熟练掌握线性表的链式存储结构定义及基本操作；(4)理解循环链表和双链表的特点和基本运算；(5)加深对顺序存储数据结构的理解和链式存储数据结构的理解，逐步培养解决实际问题的编程能力；二、实验内容1、创建有若干个元素（可以是整型数值）的顺序表，实现对顺序表的初始化，对已建立的顺序表插入操作、删除操作、遍历输出顺序表。要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：（1）从键盘上依次输入21、18、30、75、42、56，创建顺序表，并输出顺序表中的各元素值。（2）分别在单链表的第3个位置插入67，给出插入成功或失败的信息，并输出此时顺序表中的各元素值。（3）删除顺序表中的第6个数据元素，给出删除成功或失败的信息，并输出此时顺序表中的各元素值。（4）查找顺序表中是否有75这个元素，如果有返回该元素在顺序表中的位序。2、创建有若干个元素（可以是整型数值）的单链表，实现对单链表的初始化，对已建立的顺序表插入操作、删除操作、查找操作、遍历输出单链表表。要求各个操作均以函数的形式实现，在主函数中调用各个函数实现以下操作：（1）从键盘上依次输入21、18、30、75、42、56，创建单链表，并输出单链表中的各元素值。（2）分别在单链表的第4个位置，给出插入成功或失败的信息，并输出单链表中的各元素值。（3）删除单链表中的第2个数据元素，给出删除成功或失败的信息，并输出单链表中的各元素值。（4）查找顺序表中的第五个元素并输出该元素的值。三、参考代码(1)顺序表的操作#includemalloc.h#includestdio.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2typedefintStatus;#defineINIT_SIZE100/*初始分配空间的大小*/#defineLISTINCREMENT10/*分配增量*/typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;/*ElemTypeelem[INIT_SIZE],注两者区别。存储空间的起始地址。*//*线性表中数据元素个数，即表长*//*线性表所申请的存储空间的大小*/SqListCreateList_Sq(SqListL)/*创建一个空的线性表*/{L.elem=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(ERROR);L.length=0;/*表长为0*/L.listsize=INIT_SIZE;/*申请的空间为初始大小*/returnL;}StatusInsertList_Sq(SqList*L,inti,ElemTypee)/*在线性表的第i个位置前插入元素e*/{int*newbase,*q,*p;intj;if((i1)||(iL-length+1)){printf(i值不合法!\n);exit(ERROR);}if(L-length=L-listsize)/*当前空间已满，增加分配空间*/{newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(ERROR);L-elem=newbase;L-listsize=L-listsize+LISTINCREMENT;}q=&(L-elem[i-1]);for(p=&(L-elem[L-length-1]);p=q;--p)*(p+1)=*p;*q=e;L-length++;}SqListDeleteList_Sq(SqList*L,inti,ElemType*e)/*删除线性表中的第i个元素，并获得所删元素的值*/{intj;if((i1)||(iL-length)){printf(i值不合法!\n);exit(ERROR);}*e=L-elem[i-1];for(j=i;j=L-length;j++)L-elem[j-1]=L-elem[j];L-length--;}voidPrint_Sq(SqListL)/*遍历顺序线性表*/{inti;printf(\nThelist:\n);for(i=0;iL.length;i++){if((i+1)%10==0)printf(%3d\n,L.elem[i]);elseprintf(%3d,L.elem[i]);}}intGetLength(SqListL){returnL.length;}intequal(ElemTypee1,ElemTypee2)/*判两个元素是否相等*/{if(e1==e2)return1;elsereturn0;}intLocateElem_Sq(SqListL,ElemTypee,int(*compare)(ElemTypee1,ElemTypee2)){inti;i=1;while(i=L.length&&!(*compare)(L.elem[i-1],e))i++;if(i=L.length)returni;elsereturn0;}voidGetelem(SqListL,inti,ElemType*e){*e=L.elem[i-1];}intListEmpty(SqListL){if(L.length==0)return1;elsereturn0;}voidmain(){inti;SqListLq;ElemTypee;Lq=CreateList_Sq(Lq);InsertList_Sq(&Lq,1,21);InsertList_Sq(&Lq,2,18);InsertList_Sq(&Lq,3,30);InsertList_Sq(&Lq,4,75);InsertList_Sq(&Lq,5,42);InsertList_Sq(&Lq,6,56);Print_Sq(Lq);InsertList_Sq(&Lq,3,67);Print_Sq(Lq);DeleteList_Sq(&Lq,6,e);Print_Sq(Lq);if(i=LocateElem_Sq(Lq,75,equal))printf(\nthepositionofthecertaindatais%d,i);elseprintf(\nthenumberisnotfound\n);getch();}（2）单链表的操作#includestdio.h#includestdlib.htypedefintElemType;/*定义结点类型*/typedefstructNode{ElemTypedata;/*单链表中的数据域*/structNode*next;/*单链表的指针域*/}Node,*LinkedList;/*单链表的初始化*/LinkedListLinkedListInit(){Node*L;L=(Node*)malloc(sizeof(Node));/*申请结点空间*/if(L==NULL)/*判断是否有足够的内存空间*/printf(申请内存空间失败\n);L-next=NULL;/*将next设置为NULL,初始长度为0的单链表*/returnL;}/*单链表的建立2，尾插法建立单链表*/LinkedListLinkedListCreatT(){Node*L,*r;intx;L=(Node*)malloc(sizeof(Node));/*申请头结点空间*/L-next=NULL;/*初始化一个空链表*/r=L;/*r始终指向终端结点，开始时指向头结点*/while(scanf(%d,&x)!=EOF){Node*p;p=(Node*)malloc(sizeof(Node));/*申请新的结点*/p-data=x;/*结点数据域赋值*/r-next=p;/*将结点插入到表头L--|1|--|2|--NULL*/r=p;}r-next=NULL;returnL;}/*单链表的插入，在链表的第i个位置插入x的元素*/LinkedListLinkedListInsert(LinkedListL,inti,ElemTypex){Node*pre;inttempi;/*pre为前驱结点*/Node*p;pre=L;for(tempi=1;tempii;tempi++)pre=pre-next;/*查找第i个位置的前驱结点*//*插入的结点为p*/p=(Node*)malloc(sizeof(Node));p-data=x;p-next=pre-next;pre-next=p;returnL;}/*单链表的删除，在链表中删除值为x的元素*/LinkedListLinkedListDelete(LinkedListL,ElemTypex){Node*p,*pre;/*pre为前驱结点，p为查找的结点*/p=L-next;while(p-data!=x)/*查找值为x的元素*/{pre=p;p=p-next;}pre-next=p-next;/*删除操作，将其前驱next指向其后继。*/free(p);returnL;}intGetElem_L(LinkedListL,inti,ElemTypee){/*L是带头结点的链表的头指针，以e返回第i个元素*/Node*p;intj;p=L-next;j=1;/*p指向第一个结点，j为计数器*/while(p&&ji){p=p-next;++j;}/*顺指针向后查找，直到p指向第i个元素*//*或p为空（P=最后一个元素内的指针域值）*/if(!p||ji)return0;/*第i个元素不存在*/e=p-data;/*取得第i个元素*/returne;}intmain(){inti,e1;ElemTypex,e;LinkedListlist,start;printf(pleaseinputthenumberofthelist:);list=LinkedListCreatT();for(start=list-next;start!=NULL;start=start-next)printf(%d,start-data);printf(\n);printf(pleaseinputtheinsertpositonofthenumber:);scanf(%d,&i);printf(pleaseinputtheinsertvalue:);scanf(%d,&x);LinkedListInsert(list,i,x);for(start=list-next;start!=NULL;start=start-next)printf(%d,start-data);printf(\n);printf(Pleaseinputtheremovedelementvalue:);scanf(%d,&x);LinkedListDelete(list,x);for(start=list-next;start!=NULL;start=start-next)printf(%d,start-data);printf(\n);e1=GetElem_L(list,5,e);printf(\nthefifthnumberis%d,e1);getch();return0;}