C語言數(shù)據(jù)結(jié)構(gòu)線性表的基本操作實驗報告

實驗一 線性表的基本操作一、實驗目的與基本要求1．掌握數(shù)據(jù)結(jié)構(gòu)中的一些基本概念。數(shù)據(jù)、數(shù)據(jù)項、數(shù)據(jù)元素、數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)，以及它們之間的關(guān)系。2．了解數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)之間的區(qū)別與聯(lián)系；數(shù)據(jù)的運算與數(shù)據(jù)的邏輯結(jié)構(gòu)的關(guān)系。3．掌握順序表和鏈表的基本操作：插入、刪除、查找以及表的合并等運算。4．掌握運用C語言上機調(diào)試線性表的基本方法。二、實驗條件1．硬件：一臺微機2．軟件：操作系統(tǒng)和 C語言系統(tǒng)三、實驗方法確定存儲結(jié)構(gòu)后，上機調(diào)試實現(xiàn)線性表的基本運算。四、實驗內(nèi)容1．建立順序表，基本操作包括：初始化，建立一個順序存儲的鏈表，輸出順序表，判斷是否為空，取表中第i個元素，定位函數(shù)（返回第一個與x相等的元素位置），插入，刪除。2．建立單鏈表，基本操作包括：初始化，建立一個鏈式存儲的鏈表，輸出順序表，判斷是否為空，取表中第 i個元素，定位函數(shù)（返回第一個與 x相等的元素位置），插入，刪除。3．假設(shè)有兩個按數(shù)據(jù)元素值非遞減有序排列的線性表 A和B，均以順序表作為存儲結(jié)構(gòu)。編寫算法將 A表和B表歸并成一個按元素值非遞增有序（允許值相同）排列的線性表 C。（可以利用將B中元素插入A中，或新建C表）4．假設(shè)有兩個按數(shù)據(jù)元素值非遞減有序排列的線性表A和B，均以單鏈表作為存儲結(jié)構(gòu)。編寫算法將A表和B表歸并成一個按元素值遞減有序（即非遞增有序，允許值相同）排列的線性表C。五、附源程序及算法程序流程圖源程序（1）源程序(實驗要求1和3)#include<>#include<>#include<>#defineLIST_INIT_SIZE100#defineLISTINCREMENT10typedefstructarr{int*elem;intlength;intlistsize;}Sqlist;voidmenu();出\n\n");printf("1.創(chuàng)建線性表La\n\n");printf("2.判斷La是否為空表\n\n");printf("3.插入元素(La)\n\n");printf("4.刪除元素(La)\n\n");printf("5.定位元素(La)\n\n");printf("6.取元素(La)\n\n");printf("7.輸出線性表\n\n");printf("8.創(chuàng)建線性表Lb\n\n");printf("9.歸并為一個線性表La\n\n");printf("********************\n\n");}/*創(chuàng)建順序線性表 L*/voidInitList(Sqlist*L){intn;inti=0;L->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int));if(NULL==L->elem)printf(" 儲存分配失敗!\n");else{L->length=0;L->listsize=LIST_INIT_SIZE;printf(" 輸入順序表 a:\n");scanf("%d",&n);while(n){L->elem[i]=n;i++;L->length++;L->listsize=L->listsize-4;scanf("%d",&n);}}}/*輸出順序線性表 */voidShowList(Sqlist*p){inti;if(0==p->length)printf(" 數(shù)組為空!\n");elsefor(i=0;i<p->length;i++)printf("%d",p->elem[i]);printf("\n");}/*判斷L是否為空表*/voidListEmpty(Sqlist*p){if(0==p->length)printf("L 是空表!\n");elseprintf("L 不是空表!\n");}/*在順序線性表中第 i個元素前插入新元素 e*/voidListInsert(Sqlist*p,inti,inte){int*newbase;int*q1;int*q2;while(i<1||i>p->length+1){printf("您輸入的i超出范圍!\n請重新輸入要插入的位置\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+=LISTINCREMENT;}}q1=&(p->elem[i-1]);for(q2=&(p->elem[p->length-1]);q2>=q1;--q2)*(q2+1)=*q2;*q1=e;++p->length;}/*/在順序線性表中刪除第i個元素，并用e返回其值*/voidListDelete(Sqlist*p,inti,int&e){int*q1,*q2;while(i<1||i>p->length){printf(" 您輸入的i超出范圍!請重新輸入:");scanf("%d",&i);}q1=&(p->elem[i-1]);e=*q1;q2=p->elem+p->length-1;for(++q1;q1<=q2;++q1)*(q1-1)=*q1;--p->length;}/*對比a與b相等*/boolcompare(inta,intb){if(a==b)return1;elsereturn0;}/*在順序線性表 L中查找第1個值與e滿足compare()d 元素的位序*/voidLocateElem(Sqlist*L,inte){inti=1;int*p;p=L->elem;while(i<=L->length&&!compare(*p++,e))++i;if(i<=L->length)printf(" 第1個與e相等的元素的位序為 %d\n",i);elseprintf(" 沒有該元素!\n");}/*用e返回L中第i個數(shù)據(jù)元素的值 */voidGetList(Sqlist*p,inti,int&e){Sqlist*p1;p1=p;e=p1->elem[i-1];}/* 已知順序線性表 La和Lb是元素按值非遞減排列/* 把La和Lb歸并到La上,La的元素也是按值非遞減

*/

*/voidMergeList_L(Sqlist*La,Sqlist*Lb){inti=0,j=0,k,t;int*newbase;Sqlist*pa,*pb;pa=La;pb=Lb;while(i<pa->length&&j<pb->length){if(pa->elem[i]>=pb->elem[j]){if(pa->listsize==0){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(k=pa->length-1;k>=i;k--)pa->elem[k+1]=pa->elem[k];pa->length++;pa->elem[i]=pb->elem[j];i++;j++;}elsei++;}while(j<pb->length){if(pa->listsize<pb->length-j){newbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));if(!newbase)exit(0);}for(j;j<pb->length;j++,i++){pa->elem[i]=pb->elem[j];pa->length++;}}for(i=0;i<pa->length/2;i++){t=pa->elem[i];pa->elem[i]=pa->elem[pa->length-i-1];pa->elem[pa->length-i-1]=t;}}（2）源程序(實驗要求2和4)#include<>#include<>#include<>typedefstructLNode{intdata;structLNode*next;}LNode,*LinkList;voidmenu();LinkListInitList();voidShowList(LinkListL);voidListDelete(LinkListL,inti,int&e);voidListEmpty(LinkListL);voidGetList(LinkListL,inti,int&e);voidListInsert(LinkListL,inti,inte);boolcompare(inta,intb);voidLocateElem(LinkListL,inte);LinkListMergeList_L(LinkListLa,LinkListLb);inttotal=0;voidmain(){LinkListLa;LinkListLb;La=(LinkList)malloc(sizeof(structLNode));La->next=NULL;Lb=(LinkList)malloc(sizeof(structLNode));Lb->next=NULL;intn;intm;intx;menu();scanf("%d",&n);while(n){switch(n){case0:;break;case1:La->next=InitList();break;case2:ListEmpty(La);break;case3:printf(" 請輸入要插入到第幾個節(jié)點前 :\n");scanf("%d",&m);printf(" 請輸入插入的數(shù)據(jù) :\n");scanf("%d",&x);ListInsert(La,m,x);break;case4:printf(" 請輸入刪除元素的位序 :\n");scanf("%d",&m);ListDelete(La,m,x);printf(" 刪除的元素為 :%d\n",x);break;case5:printf(" 請輸入要找的與線性表中相等的數(shù) :\n");scanf("%d",&m);LocateElem(La,m);break;case6:printf(" 請輸入查找的位序 :\n");scanf("%d",&m);GetList(La,m,x);printf("La 中第%d個元素的值為%d\n",m,x);break;case7:ShowList(La);break;case8:Lb->next=InitList();break;case9:La=MergeList_L(La,Lb);printf(" 歸并成功\n");break;}menu();scanf("%d",&n);}}voidmenu(){printf("********************\n\n");printf("0. 退出\n\n");printf("1. 創(chuàng)建線性表 La\n\n");printf("2. 判斷是否為空表 \n\n");printf("3. 插入元素\n\n");printf("4. 刪除元素\n\n");printf("5. 定位元素\n\n");printf("6. 取元素\n\n");printf("7. 輸出線性表\n\n");printf("8. 創(chuàng)建線性表 Lb\n\n");printf("9. 歸并兩線性表\n\n");printf("********************\n\n");}程圖(實驗要求1和3)開始輸入nNWhile（n）Yswitch(n)123456789創(chuàng)建線性表判斷L是否為插入元素刪除元素定位元素取元素輸出線性表創(chuàng)建線性表歸并為一個La空表Lb線性表Lamenu();scanf("%d",&n);開始圖1主函數(shù)流程圖開始L->elem=(int*)malloc(LIST_INIT_SIZE*sizeof(int))YNULL==L->elemNL->length=0;L->listsize=LIST_INIT_SIZE;printf(" 輸入順序表 a:\n");scanf("%d",&n) ；Nwhile （ n）YL->elem[i]=n ； i++;L->length++;L->listsize=L->listsize-4;scanf("%d",&n);結(jié)束圖2創(chuàng)建線性表 La流程圖開始Ns->top==s->baseY此棧為空棧此棧不為空棧結(jié)束圖3判斷La是否為空表流程圖開始0==p->lengthprintf("L 是空表 !\n");printf("L 不是空表 !\n");結(jié)束圖4插入元素(La)流程圖開始Yi<1||i>p->length+1Ni值不在范圍內(nèi)，重新輸入Np->length>=p->listsizeY空間不足，接著分配空間p->elem=newbase;p->listsize+=LISTINCREMENT;q1=&(p->elem[i-1]);q2=&(p->elem[p->length-1])Nq2>=q1Y*(q2+1)=*q2;--q2*q1=e;++p->length;結(jié)束圖5刪除元素(La)流程圖開始p=L->elem;N i<=L->length&&!compare(*p++,e)Y++i ；Ni<=L->lengthY輸出位序沒有該元素結(jié)束圖6定位元素(La)流程圖開始p1=p;e=p1->elem[i-1];結(jié)束圖7取元素(La)流程圖開始Y(0==p->lengthN數(shù)組為空輸出所有元素結(jié)束圖8輸出線性表流程圖開始pa=La;pb=Lb;Ni<pa->length&&j<pb->lengthY(pa->elem[i]>=pb->elem[j]YNpa->listsize==0Y

Nnewbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));N!newbaseYexit(0);k=pa->length-1Nk>=iYpa->elem[k+1]=pa->elem[k];k--pa->length++;pa->elem[i]=pb->elem[j];i++;j++;i++;Nj<pb->length 1YNpa->listsize<pb->length-jYnewbase=(int*)realloc(pa->elem,(pa->listsize+LISTINCREMENT)*sizeof(int));N!newbaseYexit(0);Nj<pb->lengthYpa->elem[i]=pb->elem[j];pa->length++;j++i++

1i=0Ni<pa->length/2Yt=pa->elem[i];pa->elem[i]=pa->elem[pa->length-i-1];pa->elem[pa->length-i-1]=t;i++結(jié)束圖9輸出線性表流程圖流程圖(實驗要求2和4)開始menu（）創(chuàng)建頭結(jié)點La,Lb并輸入nNwhile(n)Yswitch(n)123456789創(chuàng)建線性判斷是否插入元素刪除元素定位元素取元素輸出線性創(chuàng)建線性歸并兩線表La為空表表表Lb性表menu();scanf("%d",&n);結(jié)束圖10主函數(shù)流程圖開始LinkListpHead=NULL;LinkListpEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(structLNode));scanf("%d",&pNew->data);NpNew->dataYcount++;Ncount==1YpNew->next=pHead;pEnd=pNew;pHead=pNew;pNew->next=NULL;pEnd->next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(structLNode));scanf("%d",&pNew->data);結(jié)束圖11創(chuàng)建線性表 La流程圖開始NNULL==L->nextY輸出空表輸出不為空表結(jié)束圖12判斷是否為空表流程圖開始LinkListp;LinkLists;p=L;Np&&j<i-1Yp=p->next;++j;N!p||j>i-1Y輸出找不到節(jié)點s=(LinkList)malloc(sizeof(int));s->data=e;s->next=p->next;p->next=s；結(jié)束圖13插入元素流程圖開始LinkListp;LinkListq;p=L;Np->next&&j<i-1Yp=p->next;++j;N!(p->next)||j>i-1Y輸出沒找到位置q=p->next;p->next=q->next;e=q->data;結(jié)束圖14刪除元素流程圖開始LinkListp;p=L;Np->next&&!compare(p->data,e)

開始Yp=p->next;i++;NULL==p->nextYN

N

LinkListp;p=L->next;Np->next&&j<i-1Yp=p->next;0==compare(p->data,e)Y輸出沒有輸出位序該元素Ncompare(p->data,e)Y沒有該元素結(jié)束

++j;N!(p)||j>i-1Y沒有找到要查找的位置e=p->data;結(jié)束圖15定位元素流程圖圖 圖16取元素流程圖開始LinkListpHead=NULL;LinkListpEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(structLNode));scanf("%d",&pNew->data);NpNew->dataYcount++;Ncount==1YpNew->next=pHead;pEnd=pNew;pHead=pNew;pNew->next=NULL;pEnd->next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(structLNode));scanf("%d",&pNew->data);結(jié)束圖17創(chuàng)建Lb流程圖開始pa_1=La->next;pc=pa_2=La;pb_1=pb_2=Lb->next;Npa