




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、實(shí)驗(yàn)一 線性表的基本操作 一、實(shí)驗(yàn)?zāi)康呐c基本要求1掌握數(shù)據(jù)結(jié)構(gòu)中的一些基本概念。數(shù)據(jù)、數(shù)據(jù)項(xiàng)、數(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ù)的運(yùn)算與數(shù)據(jù)的邏輯結(jié)構(gòu)的關(guān)系。3 掌握順序表和鏈表的基本操作:插入、刪除、查找以及表的合并等運(yùn)算。4 掌握運(yùn)用C語言上機(jī)調(diào)試線性表的基本方法。二、實(shí)驗(yàn)條件1 硬件:一臺微機(jī)2 軟件:操作系統(tǒng)和C語言系統(tǒng)三、實(shí)驗(yàn)方法確定存儲結(jié)構(gòu)后,上機(jī)調(diào)試實(shí)現(xiàn)線性表的基本運(yùn)算。四、實(shí)驗(yàn)內(nèi)容1 建立順序表,基本操作包括:初始化,建立一個(gè)順序存儲的鏈表,輸出順序表,判斷是否為空,取表中第i個(gè)元素,定位函數(shù)(返回第一
2、個(gè)與x相等的元素位置),插入,刪除。2 建立單鏈表,基本操作包括:初始化,建立一個(gè)鏈?zhǔn)酱鎯Φ逆湵恚敵鲰樞虮?,判斷是否為空,取表中第i個(gè)元素,定位函數(shù)(返回第一個(gè)與x相等的元素位置),插入,刪除。3 假設(shè)有兩個(gè)按數(shù)據(jù)元素值非遞減有序排列的線性表A和B,均以順序表作為存儲結(jié)構(gòu)。編寫算法將A表和B表歸并成一個(gè)按元素值非遞增有序(允許值相同)排列的線性表C。(可以利用將B中元素插入A中,或新建C表)4 假設(shè)有兩個(gè)按數(shù)據(jù)元素值非遞減有序排列的線性表A和B,均以單鏈表作為存儲結(jié)構(gòu)。編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序(即非遞增有序,允許值相同)排列的線性表C。五、附源程序及算法程序流程圖1.源
3、程序(1)源程序(實(shí)驗(yàn)要求1和3)#include#include#include#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef struct arrint * elem;int length;int listsize;Sqlist;void menu(); /菜單void InitList(Sqlist *p);/ 創(chuàng)建線性表 void ShowList(Sqlist *p);/ 輸出順序線性表 void ListDelete(Sqlist *p,int i,int &e);/ 在順序線性表中刪除第i個(gè)元素,并用e返回其值v
4、oid ListInsert(Sqlist *p);/ 在順序線性表中第i個(gè)元素前插入新元素evoid ListEmpty(Sqlist *p);/ 判斷L是否為空表void GetList(Sqlist *p,int i,int &e);/ 用e返回L中第i個(gè)數(shù)據(jù)元素的值void ListInsert(Sqlist *p,int i,int e);bool compare(int a,int b);void LocateElem(Sqlist *L,int e);/ 在順序線性表L中查找第1個(gè)值與e滿足compare()d元素的位序void MergeList_L(Sqlist *La,Sq
5、list *Lb); / 歸并 void main()Sqlist La;Sqlist Lb;int n,m,x;menu();scanf(%d,&n);while(n)switch(n)case 0: ; break;case 1:InitList(&La);break;case 2:ListEmpty(&La);break;case 3:printf(請輸入插入的位序:n);scanf(%d,&m);printf(請出入要插入的數(shù):n);scanf(%d,&x);ListInsert(&La,m,x);break;case 4:printf(請輸入刪除元素的位序:n);scanf(%d,&
6、m);ListDelete(&La,m,x);printf(刪除的元素為:%dn,x);break;case 5:printf(請輸入要找的與線性表中相等的數(shù):n);scanf(%d,&m);LocateElem(&La,m);break;case 6:printf(請輸入查找的位序:n);scanf(%d,&m);GetList(&La,m,x);printf(La中第%d個(gè)元素的值為%dn,m,x);break;case 7:ShowList(&La);break;case 8:InitList(&Lb);break;case 9:MergeList_L(&La,&Lb);printf(歸
7、并成功!);break;menu();scanf(%d,&n);/*菜單*/void menu()printf(*nn);printf( 0.退出nn);printf( 1.創(chuàng)建線性表Lann);printf( 2.判斷La是否為空表nn);printf( 3.插入元素(La)nn);printf( 4.刪除元素(La)nn);printf( 5.定位元素(La)nn);printf( 6.取元素(La)nn);printf( 7.輸出線性表nn);printf( 8.創(chuàng)建線性表Lbnn);printf( 9.歸并為一個(gè)線性表Lann);printf(*nn);/*創(chuàng)建順序線性表L*/void
8、 InitList(Sqlist *L)int n;int i=0;L-elem=(int *)malloc(LIST_INIT_SIZE*sizeof(int);if(NULL=L-elem)printf(儲存分配失敗!n);elseL-length=0;L-listsize=LIST_INIT_SIZE;printf(輸入順序表a:n);scanf(%d,&n);while(n)L-elemi=n;i+;L-length+;L-listsize=L-listsize-4;scanf(%d,&n);/*輸出順序線性表*/void ShowList(Sqlist *p)int i;if(0=p
9、-length)printf(數(shù)組為空!n);elsefor(i=0;ilength;i+)printf(%d ,p-elemi);printf(n);/*判斷L是否為空表*/void ListEmpty(Sqlist *p)if(0=p-length)printf(L是空表!n);elseprintf(L不是空表!n);/*在順序線性表中第i個(gè)元素前插入新元素e */void ListInsert(Sqlist *p,int i,int e)int *newbase;int *q1;int *q2;while(ip-length+1)printf(您輸入的i超出范圍!n請重新輸入要插入的位置
10、n:);scanf(%d,&i);if(p-length=p-listsize)newbase=(int *)realloc(p-elem,(p-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);elsep-elem=newbase;p-listsize+=LISTINCREMENT;q1=&(p-elemi-1);for(q2=&(p-elemp-length-1);q2=q1;-q2)*(q2+1)=*q2;*q1=e;+p-length;/*/在順序線性表中刪除第i個(gè)元素,并用e返回其值*/void ListDelete(Sq
11、list *p,int i,int &e)int *q1,*q2;while(ip-length)printf(您輸入的i超出范圍!請重新輸入:);scanf(%d,&i);q1=&(p-elemi-1); e=*q1;q2=p-elem+p-length-1;for(+q1;q1length;/*對比a與b相等*/bool compare(int a,int b) if(a=b)return 1;elsereturn 0;/*在順序線性表L中查找第1個(gè)值與e滿足compare()d元素的位序*/void LocateElem(Sqlist *L,int e)int i=1;int *p;p=
12、L-elem;while(ilength & !compare(*p+,e)+i;if(ilength)printf(第1個(gè)與e相等的元素的位序?yàn)?dn,i);elseprintf(沒有該元素!n);/*用e返回L中第i個(gè)數(shù)據(jù)元素的值*/void GetList(Sqlist *p,int i,int &e)Sqlist *p1;p1=p;e=p1-elemi-1;/* 已知順序線性表La和Lb是元素按值非遞減排列 */* 把La和Lb歸并到La上,La的元素也是按值非遞減 */void MergeList_L(Sqlist *La,Sqlist *Lb)int i=0,j=0,k,t;int
13、 *newbase;Sqlist *pa,*pb;pa=La;pb=Lb;while(ilength & jlength)if(pa-elemi = pb-elemj)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-elemk+1=pa-elemk;pa-length+;pa-elemi=pb-elemj;i+;j+;elsei+;while(jlength)if( p
14、a-listsize length-j )newbase=(int *)realloc(pa-elem,(pa-listsize+LISTINCREMENT)*sizeof(int);if(!newbase)exit(0);for(j;jlength;j+,i+)pa-elemi=pb-elemj;pa-length+;for(i=0;ilength/2;i+)t=pa-elemi;pa-elemi=pa-elempa-length-i-1;pa-elempa-length-i-1=t;(2)源程序(實(shí)驗(yàn)要求2和4)#include#include#includetypedef struct
15、LNodeint data;struct LNode *next;LNode, *LinkList;void menu();LinkList InitList();void ShowList(LinkList L);void ListDelete(LinkList L,int i,int &e);void ListEmpty(LinkList L);void GetList(LinkList L,int i,int &e);void ListInsert(LinkList L,int i,int e);bool compare(int a,int b);void LocateElem(Link
16、List L,int e);LinkList MergeList_L(LinkList La,LinkList Lb);int total=0;void main()LinkList La;LinkList Lb;La=(LinkList)malloc(sizeof(struct LNode);La-next=NULL;Lb=(LinkList)malloc(sizeof(struct LNode);Lb-next=NULL;int n;int m;int x;menu();scanf(%d,&n);while(n)switch(n)case 0: ; break;case 1:La-next
17、=InitList();break;case 2:ListEmpty(La);break;case 3:printf(請輸入要插入到第幾個(gè)節(jié)點(diǎn)前:n);scanf(%d,&m);printf(請輸入插入的數(shù)據(jù):n);scanf(%d,&x);ListInsert(La,m,x);break;case 4:printf(請輸入刪除元素的位序:n);scanf(%d,&m);ListDelete(La,m,x);printf(刪除的元素為:%dn,x);break;case 5:printf(請輸入要找的與線性表中相等的數(shù):n);scanf(%d,&m);LocateElem(La,m);brea
18、k;case 6:printf(請輸入查找的位序:n);scanf(%d,&m);GetList(La,m,x);printf(La中第%d個(gè)元素的值為%dn,m,x);break;case 7:ShowList(La);break;case 8:Lb-next=InitList();break;case 9:La=MergeList_L(La,Lb);printf(歸并成功n);break;menu();scanf(%d,&n);void menu()printf(*nn);printf( 0.退出nn);printf( 1.創(chuàng)建線性表Lann);printf( 2.判斷是否為空表nn);p
19、rintf( 3.插入元素nn);printf( 4.刪除元素nn);printf( 5.定位元素nn);printf( 6.取元素nn);printf( 7.輸出線性表nn);printf( 8.創(chuàng)建線性表Lbnn);printf( 9.歸并兩線性表nn);printf(*nn);/ 創(chuàng)建鏈?zhǔn)骄€性表LLinkList InitList()int count=0;LinkList pHead=NULL;LinkList pEnd,pNew;pEnd=pNew=(LinkList)malloc(sizeof(struct LNode);printf(請輸入數(shù)據(jù):n);scanf(%d,&pNew
20、-data);while(pNew-data)count+;if(count=1)pNew-next=pHead;pEnd=pNew;pHead=pNew;elsepNew-next=NULL;pEnd-next=pNew;pEnd=pNew;pNew=(LinkList)malloc(sizeof(struct LNode);printf(請輸入數(shù)據(jù):n);scanf(%d,&pNew-data);free(pNew);total=total+count;return pHead;/ 判斷L是否為空表void ListEmpty(LinkList L)if(NULL=L-next)print
21、f(此表為空表!n);elseprintf(此表不為空表!n);/ 在鏈?zhǔn)骄€性表中第i個(gè)元素前插入新元素evoid ListInsert(LinkList L,int i,int e)LinkList p;LinkList s;p=L;int j=0;while(p&jnext;+j;if(!p|ji-1)printf(不存在您要找的節(jié)點(diǎn)!n);elses=(LinkList)malloc(sizeof(int);s-data=e;s-next=p-next;p-next=s;printf(插入節(jié)點(diǎn)成功!n);/ 輸出鏈?zhǔn)骄€性表void ShowList(LinkList L)LinkList
22、 p;p=L-next;if(p=NULL)printf(此表為空表!n);elsewhile(p)printf(%d ,p-data);p=p-next;printf(n);/ 在鏈?zhǔn)骄€性表中刪除第i個(gè)元素,并用e返回其值void ListDelete(LinkList L,int i,int &e)LinkList p;LinkList q;p=L;int j=0;while(p-next & jnext;+j;if(!(p-next)|ji-1)printf(沒有找到要?jiǎng)h除的位置!);elseq=p-next;p-next=q-next;e=q-data;free(q);/ 用e返回L中
23、第i個(gè)數(shù)據(jù)元素的值void GetList(LinkList L,int i,int &e)LinkList p;p=L-next;int j=0;while(p-next & jnext;+j;if(!(p)|ji-1)printf(沒有找到要查找的位置!);elsee=p-data;/ 對比a與b相等bool compare(int a,int b) if(a=b)return 1;elsereturn 0;/ 在鏈?zhǔn)骄€性表L中查找第1個(gè)值與e滿足compare()d元素的位序void LocateElem(LinkList L,int e)int i=0;LinkList p;p=L;w
24、hile(p-next & !compare(p-data,e)p=p-next;i+;if(NULL=p-next)if(0=compare(p-data,e)printf(沒有該元素!n);elseprintf(第1個(gè)與e相等的元素的位序?yàn)?dn,i);elseif(compare(p-data,e)printf(沒有該元素!n);LinkList MergeList_L(LinkList La,LinkList Lb)int 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;if(pa_1-data pb_1-data)pc=pa_2=Lb;pa_1=Lb-next;pb_1=pb_2=La-next;while(pa_1 & pb_1)if(pa_1-data = pb_1-data)pa_2-next=pb_1;pb_2=pb_1-next;pb_1-next=pa_1;pb_1=pb_2;pa_2=pa_2-next;elsepa_1=pa_1-next;pa_2=pa_2-next;if(pb_1)pa_2-n
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 三年級勞動(dòng)技術(shù)下冊教學(xué)總結(jié)計(jì)劃
- 部編版語文六年級上冊校本課程計(jì)劃
- 人美版美術(shù)一年級上冊教學(xué)質(zhì)量提升計(jì)劃
- 醫(yī)院內(nèi)部審計(jì)數(shù)據(jù)分析計(jì)劃
- 2025秋六年級上冊美術(shù)教學(xué)重點(diǎn)突破計(jì)劃
- 2025年幼兒園小班下學(xué)期社會適應(yīng)計(jì)劃
- (品牌)紡織染料限用物質(zhì)清單(RSL)管控計(jì)劃
- 雙突頜畸形護(hù)理課件
- 腕掌關(guān)節(jié)脫位的護(hù)理
- 八年級歷史融合教育計(jì)劃
- 煤矸石處置合同范本
- 《中文+酒店管理》教材編寫研究
- 放棄填報(bào)志愿的申請書
- 能源管理體系及節(jié)能知識培訓(xùn)課件
- 八項(xiàng)硬措施培訓(xùn)課件
- 政府采購廉政風(fēng)險(xiǎn)控制措施
- 拼多多商家入駐協(xié)議書二零二五年度版:電商合作要點(diǎn)全收錄3篇
- 2025年中煤集團(tuán)招聘筆試參考題庫含答案解析
- 多囊卵巢綜合征完全指南
- 小龍蝦啤酒節(jié)小龍蝦啤酒音樂節(jié)活動(dòng)策劃方案
- 醫(yī)院培訓(xùn)課件:《復(fù)用器械之預(yù)處理》
評論
0/150
提交評論