线性表大作业任务书

作业1：线性表作业目的了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。掌握线性表的顺序存储结构的定义及其C语言的实现。掌握线性表的链式存储结构——单链表的定义及其C语言的实现。掌握线性表在顺序存储结构即顺序表中的各种基本操作。掌握线性表在链式存储结构——单链表的各种基本操作。作业要求1.认真阅读和掌握本实验的程序。2.上机运行本程序。3.保存和打印出程序的运行结果，并结合程序进行分析。4.按照对线性表和单链表的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。作业内容1.顺序表的操作请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行表的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕菜单中选择0，即可结束程序的运行。分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素一次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将第i个元素之后的所有元素前移一个位置。算法描述：对每个算法，都要写出算法的中文描述。要求分别写出在第i个（从1开始计数）结点前插入数据为x的结点、删除指定结点、创建一个线性表。打印线性表等的算法描述。2.单链表的操作请编制C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。算法描述：要求分别写出在带头结点的单链表中第i（从1开始计数）个位置之后插入元素、创建带头结点的单链表、在带头结点的单链表中删除第i个位置的元素、顺序输出单链表的内容等的算法描述。实验一：1.实验程序源代码#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-2#include<stdio.h>#include<stdlib.h>#defineML1//线?性?表À¨ª#defineTURE1#defineFALSE0#defineOK1#defineERR0typedefstruct{intlist[ML];intsize;intMAXSIZE;}sqList;sqList*Init_List(sqList*L,intms);voidDisp_List(sqList*L);intLocateElem_List(sqList*L,intx);intInsert_List(sqList*L,intx,intmark);intDelete_List1(sqList*L,intitem);intDelete_List2(sqList*L,intmark);sqList*Init_List(sqList*L,intms){ L=(sqList*)malloc(ms*sizeof(sqList));if(!L){ printf("申¦¨º请?内¨²存ä?空?间?出?错䨪\n"); exit(OVERFLOW); }else L->size=0; L->MAXSIZE=ms;returnL;}voidDisp_List(sqList*L){inti;for(i=0;i<L->size;i++) printf("%d",L->list[i]); printf("\n");}intLocateElem_List(sqList*L,intx){inti=0;for(i=0;i<=L->size;i++)if(L->list[i]==x)returni;if(i>L->size)return-1;}intInsert_List(sqList*L,intx,intmark){inti=1;if(L->size>=L->MAXSIZE)return-1;if(mark>0){for(i=L->size+1;i>=mark;i--) L->list[i+1]=L->list[i]; L->list[i]=x; }elseif(mark<0) L->list[L->size]=x; L->size++;returnFALSE;}intDelete_List1(sqList*L,intitem){inti,j;for(i=0;i<L->size;i++)if(item==L->list[i])break;if(i<L->size){for(j=i+1;j<L->size-1;j++) L->list[j]=L->list[j+1]; L->size--;returni;}returnFALSE;}intDelete_List2(sqList*L,intmark){inti,item;if(mark>0){ item=L->list[mark];for(i=mark+1;i<L->size-1;i++) L->list[i]=L->list[i+1]; L->size--;returni; }returnFALSE;}voidmain(){intp,n,x=0;sqLista,*b; b=Init_List(&a,ML); printf("listaddr=%d\tsize=%d\tMaxSize=%d",b->list,b->size,b->MAXSIZE);while(1){ printf("\n请?输º?入¨?值¦Ì，ê?0为a结¨¢束º?输º?入¨?：êo"); scanf("%d",&x);if(!x)break; printf("\n请?输º?入¨?插?入¨?位?置?：êo\n"); scanf("%d",&p); Insert_List(b,x,p); printf("\n线?性?表À¨ª为a：êo\n");Disp_List(b); }while(1){ printf("\n请?输º?入¨?查¨¦找¨°值¦Ì，ê?输º?入¨?0结¨¢束º?查¨¦找¨°操¨´作Á¡Â：êo\n"); scanf("%d",&x);if(!x)break; n=LocateElem_List(b,x);if(n<0)printf("\n没?找¨°到Ì?\n");else printf("\n又®?符¤?合?条¬?件t的Ì?值¦Ì，ê?位?置?为a：êo%d\n",n+1); }while(1){ printf("\n请?输º?入¨?删¦?除y值¦Ì，ê?输º?入¨?0结¨¢束º?查¨¦找¨°操¨´作Á¡Â：êo\n"); scanf("%d",&x);if(!x)break; n=Delete_List1(b,x);if(n<0) printf("\n没?找¨°到Ì?\n");else{ printf("\n删¦?除y成¨¦功|，ê?线?性?表À¨ª为a:\n"); Disp_List(b); } } while(1){ printf("\n请?输º?入¨?删¦?除y值¦Ì位?置?，ê?输º?入¨?o结¨¢束º?查¨¦找¨°操¨´作Á¡Â:\n"); scanf("%d",&p);if(!p)break; n=Delete_List2(b,p);if(p<0)printf("\n位?置?越?界?\n");else{ printf("\n线?性?表À¨ª为a:\n"); Disp_List(b); } }}2.实验运行图3.算法分析：（1）顺序表的初始化即是创造一个空表顺序表的初始化即构造一个空表，这对表是一个加工型的运算，因此，将L设为指针参数，首先动态分配存储空间，然后，将表中length指针置为0，表示表中没有数据元素。算法如下：StatusInitList_Sq(SqList*L){L->elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));//分配存储空间if(!L->elem)exit(OVERFLOW);//存储分配失败L->length=0;//空表长度为0L->listsize=LIST_INIT_SIZE;//初始存储容量returnOK;}//InitList_Sq此算法的时间复杂度为O(1)。（2）在顺序表中“查询”是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。intLocateElem(SqListL,ElemTypee，void(*compare)(ElemType,ElemType)){//在顺序表L中查找第1个值与e满足判定条件compare()的元素//若找到，则返回其在L中的位序，否则返回0i=1;//i的初值为第1元素的位序p=L.elem;//p的初值为第1元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))算法时间复杂度的分析：算法中的基本操作是“判定”，它出现在while循环中，而函数compare()的时间复杂度显然是个常量。因此执行判定的次数取决于元素在线性表中的“位序”，至多和表长相同。所以，此算法的时间复杂度为：O(ListLength(L))。（3）假设在线性表的第i个元素之前插入一个元素e，使得线性表(a1，a2，...，ai-1，ai，ai+1，...，an)改变成为表长为n+1表:(a1，a2，...，ai-1，e，ai，ai+1，...，an)。即：1、改变了表中元素之间的关系，使<ai-1，ai>改变为<ai-1,e>和<e,ai>2、表长增1（4假设删除线性表中第i个元素，使得线性表：(a1，a2，...，ai-1，ai，ai+1，...，an)；改变成为表长为n-1的线性表：(a1，a2，...，ai-1，ai+1，...，an)。即：1、改变了表中元素之间的关系，使<ai-1，ai>和<ai，ai+1>改变为<ai-1，ai>。2、表长减1实验二1实验源程序#include<stdio.h>#include<malloc.h>#definenull0typedefintElemType;/*字Á?符¤?型¨ª数ºy据Y*/structLNode{ ElemTypedata;structLNode*next;};voidsetnull(structLNode**p);intlength(structLNode**p);ElemTypeget(structLNode**p,inti);voidinsert(structLNode**p,ElemTypex,inti);voiddele(structLNode**p,inti);voiddisplay(structLNode**p);intlocate(structLNode**p,ElemTypex);voidmain(){structLNode*head,*q;/*定¡§义°?静2态¬?变À?量¢?*/intselect,x1,x2,x3,x4;inti,n;intm,g;chare,y; setnull(&head);/*建¡§设¦¨¨链¢¡ä表À¨ª并¡é设¦¨¨置?为a空?表À¨ª*/ printf("请?输º?入¨?数ºy据Y长¡è度¨¨:"); scanf("%d",&n);for(i=1;i<=n;i++) { printf("将?数ºy据Y插?入¨?到Ì?单Ì£¤链¢¡ä表À¨ª中D:"); scanf("%d",&y); insert(&head,y,i); }/*插?入¨?数ºy据Y到Ì?链¢¡ä表À¨ª*/ display(&head); /*显?示º?链¢¡ä表À¨ª所¨´有®D数ºy据Y*/ printf("select1求¨®长¡è度¨¨length()\n"); printf("select2取¨?结¨¢点Ì?get()\n"); printf("select3求¨®值¦Ì查¨¦找¨°locate()\n"); printf("select4删¦?除y结¨¢点Ì?delete()\n"); printf("select0退ª?出?\n"); printf("inputyourselect:"); scanf("%d",&select);while(select!=0) {switch(select) {case1: { x1=length(&head); printf("输º?出?单Ì£¤链¢¡ä表À¨ª的Ì?长¡è度¨¨%d",x1); display(&head); }break;case2: { printf("请?输º?入¨?要°a取¨?得Ì?结¨¢点Ì?:"); scanf("%d",&m); x2=get(&head,m); printf("%d",x2); display(&head); }break;case3: { printf("请?输º?入¨?要°a查¨¦找¨°的Ì?数ºy据Y:"); scanf("%d",&e); x3=locate(&head,e); printf("%d",x3); display(&head); }break;case4: { printf("请?输º?入¨?要°a删¦?除y的Ì?结¨¢点Ì?:"); scanf("%d",&g); dele(&head,g); display(&head); }break; } printf("select1求¨®长¡è度¨¨length()\n"); printf("select2取¨?结¨¢点Ì?get()\n"); printf("select3求¨®值¦Ì查¨¦找¨°locate()\n"); printf("select4删¦?除y结¨¢点Ì?delete()\n"); printf("select0退ª?出?\n"); printf("inputyourselect:"); scanf("%d",&select); }}voidsetnull(structLNode**p){ *p=null;}intlength(structLNode**p){intn=0;structLNode*q=*p;while(q!=null) { n++; q=q->next; }return(n);}ElemTypeget(structLNode**p,inti){intj=1;structLNode*q=*p;while(j<i&&q!=null) { q=q->next; j++; }if(q!=null)return(q->data);else {printf("位?置?参?数ºy不?正y确¨¡¤!\n");return0;}}intlocate(structLNode**p,ElemTypex){intn=0;structLNode*q=*p;while(q!=null&&q->data!=x) { q=q->next; n++; }if(q==null)return(-1);elsereturn(n+1);}voidinsert(structLNode**p,ElemTypex,inti){intj=1;structLNode*s,*q; s=(structLNode*)malloc(sizeof(structLNode)); s->data=x; q=*p;if(i==1) { s->next=q; *p=s; }else {while(j<i-1&&q->next!=null) { q=q->next; j++; }if(j==i-1) { s->next=q->next; q->next=s; }else printf("位?置?参?数ºy不?正y确¨¡¤!\n"); } }voiddele(structLNode**p,inti){intj=1;struct