數(shù)據(jù)結(jié)構(gòu)線性表設(shè)計(jì)代碼

1、河南城建學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)名稱：_實(shí)驗(yàn)一 線性表操作     成績(jī)：_ _專業(yè)班級(jí)：_ 信管2班 _   姓名：_張凱迪_ 學(xué)號(hào)：_083215217_ 實(shí)驗(yàn)日期 ：  2016 年  4 月  27 日一、實(shí)驗(yàn)?zāi)康?掌握用C+/C語(yǔ)言調(diào)試程序的基本方法。2掌握線性表的基本運(yùn)算，如插入、刪除等。二、實(shí)驗(yàn)內(nèi)容線性表在順序、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上的插入元素，刪除元素運(yùn)算。三、實(shí)驗(yàn)要求1用C+/C完成算法設(shè)計(jì)和程序設(shè)計(jì)并上機(jī)調(diào)試通過(guò)。2撰寫實(shí)驗(yàn)報(bào)告，提供實(shí)驗(yàn)結(jié)果和數(shù)據(jù)。3分

2、析算法，并簡(jiǎn)要給出算法設(shè)計(jì)小結(jié)和心得。四、程序?qū)崿F(xiàn)源程序清單五、寫出輸入數(shù)據(jù)及運(yùn)行結(jié)果、算法分析上述程序在Visual C+ 6.0環(huán)境下加以實(shí)現(xiàn)。經(jīng)過(guò)多次測(cè)試，程序運(yùn)行正確。例如：輸入，運(yùn)行結(jié)果如圖所示，圖中顯示了（一）順序表的基本操作源代碼#include<iostream>using namespace std;#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int Status;typedef int ElemType;#define LIST_INIT_S

3、IZE 100#define LISTINCREMENT 10typedef struct /結(jié)構(gòu)體ElemType *elem;int length;int listsize;SqList;SqList Lx;Status InitList_Sq(SqList &L) /分配空間 L.elem=new ElemTypeLIST_INIT_SIZE; if(!L.elem)exit(OVERFLOW); L.length =0; L.listsize=LIST_INIT_SIZE; return OK;Status ListInsert(SqList &L,int i,Elem

4、Type e) /插入新元素 int *q,*p;ElemType *newbase;if(i<1 | i>L.length+1) return ERROR;if(L.length>=L.listsize) newbase=new ElemTypeL.listsize+LISTINCREMENT; if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; q=&(L.elemi-1); for (p=&(L.elemL.length-1);p>=q;-p) *(p+1)

5、=*p; *q=e; +L.length; return OK;Status Listlength(SqList L) /長(zhǎng)度 int *p=L.elem; /判斷線形表是否存在while(p) return (L.length); Status GetElem(SqList L, int i,ElemType &e) /取元素 if(i<1 | i>L.length)return ERROR;else e=L.elemi-1;return e;void MergeList(SqList La,SqList Lb,SqList &Lc) /合并 ElemType a

6、i,bj;InitList_Sq(Lc);int i=1,j=1,k=0;int La_len,Lb_len;La_len=Listlength(La);Lb_len=Listlength(Lb);while(i<=La_len)&&(j<=Lb_len) GetElem(La,i,ai);GetElem(Lb,j,bj); if(ai<=bj) ListInsert(Lc,+k,ai);+i; else ListInsert(Lc,+k,bj);+j; while(i<=La_len) GetElem(La,i+,ai);ListInsert(Lc,+

7、k,ai);while(j<=Lb_len) GetElem(Lb,j+,bj);ListInsert(Lc,+k,bj);void show(SqList L,int i) /顯示 int j;ElemType k; cout<<"順序表顯示如下:"<<endl; for(j=0;j<i-1;j+) k=L.elemj; cout<<k<<"->" if(j=i-1 && i>0) k=L.elemj; cout<<k; cout<<endl

8、;void create(SqList &L,int n) /輸入元素 int e;for(int i=0;i<n;i+) cin>>e;L.elemi=e;L.length=i+1; Status ListDelete_Sq(SqList &L,int i,ElemType &e) /刪除 ElemType *p, *q;if(i<1 | i>L.length) return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p<=q;+p) *(p-1)=*p;-L.

9、length;return OK;Status Listxiugei(SqList &L,int i,ElemType &e) /修改 if(i<1 | i>L.length)return ERROR; else L.elemi-1=e; return OK; void shuru(SqList &L1) /順序表的創(chuàng)建 int a;InitList_Sq(L1);cout<<"請(qǐng)輸入順序表的長(zhǎng)度："cin>>a;cout<<"請(qǐng)輸入順序表的元素(共"<<a<<

10、;"個(gè))"<<endl; create(L1,a); show(L1,a);void chaxun(SqList &L1) /取第i個(gè)位置的元素 int j;ElemType e1;cout<<"請(qǐng)選擇所要取出元素的位置:"cin>>j; while(j<0|j>Listlength(L1) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;cout<<"請(qǐng)選擇所要取出元素的位置:" cin>>j; GetEle

11、m(L1,j,e1);cout<<"取出的元素為:"<<e1<<endl;void xiugai(SqList &L1) /修改第i個(gè)位置的元素 int a;int j; ElemType e1;a=L1.length;cout<<"請(qǐng)選擇所要修改元素的位置:"cin>>j;while(j<0|j>Listlength(L1) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;cout<<"請(qǐng)選擇所要修改元素的

12、位置:" cin>>j; cout<<"要修改成的元素:"cin>>e1;Listxiugei(L1,j,e1);cout<<"修改后的順序表數(shù)據(jù):"<<endl;show(L1,a);void shanchu(SqList &L1) /刪除順序表里的元素 int a;int j; ElemType e1;a=L1.length;cout<<"請(qǐng)選擇所要?jiǎng)h除元素的位置:"cin>>j;while(j<0|j>Listlen

13、gth(L1) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;cout<<"請(qǐng)選擇所要?jiǎng)h除元素的位置:" cin>>j; ListDelete_Sq(L1,j,e1);cout<<"修改后的順序表數(shù)據(jù):"<<endl;show(L1,a-1);void charu(SqList &L1) /插入元素到順序表里 int a; int j; ElemType e1;a=L1.length;cout<<"請(qǐng)選擇所要插入元素的位置:&qu

14、ot;cin>>j;while(j<0|j>Listlength(L1) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;cout<<"請(qǐng)選擇所要插入元素的位置:" cin>>j; cout<<"要插入的元素:"cin>>e1;ListInsert(L1,j,e1);cout<<"修改后的順序表數(shù)據(jù):"<<endl;show(L1,a+1);void hebing(SqList &L3)

15、 /合并兩個(gè)順序表 SqList L1,L2; int a,b; InitList_Sq(L1); InitList_Sq(L2); cout<<"請(qǐng)輸入第一個(gè)有序表的長(zhǎng)度：" cin>>a; cout<<"請(qǐng)輸入第一個(gè)有序表的元素(共"<<a<<"個(gè))"<<endl; create(L1,a); show(L1,a); cout<<"請(qǐng)輸入第二個(gè)有序表的長(zhǎng)度：" cin>>b; cout<<"請(qǐng)輸

16、入第二個(gè)有序表的元素(共"<<b<<"個(gè))"<<endl; create(L2,b); show(L2,b); MergeList(L1,L2,L3); cout<<"合并后的有序表如下：" show(L3,a+b);void main() /主菜單 int choice; for(;) cout<<" 順序表的基本操作 "<<endl; cout<<" 1.順序表的創(chuàng)建"<<endl; cout<<

17、;" 2.順序表的顯示"<<endl; cout<<" 3.順序表的長(zhǎng)度"<<endl; cout<<" 4.取第i個(gè)位置的元素"<<endl; cout<<" 5.修改第i個(gè)位置的元素"<<endl; cout<<" 6.插入元素到順序表里"<<endl; cout<<" 7.刪除順序表里的元素"<<endl; cout<<&quo

18、t; 8.合并兩個(gè)順序表"<<endl; cout<<" 9.退出系統(tǒng)"<<endl; cout<<"請(qǐng)選擇：" cin>>choice; switch(choice) case 1: shuru(Lx);break; case 2: show(Lx,Lx.length);break; case 3: cout<<"順序表的長(zhǎng)度:"<<Listlength(Lx)<<endl;break; case 4: chaxun(Lx);b

19、reak; case 5: xiugai(Lx);break; case 6: charu(Lx);break; case 7: shanchu(Lx);break; case 8: hebing(Lx);break; case 9: cout<<"退出系統(tǒng)!"<<endl;exit(0);break; default : cout<<"輸入有誤，請(qǐng)重新選擇"<<endl;break; 運(yùn)行結(jié)果、順序表得創(chuàng)建顯示如下圖2-1順序表的插入如下2-2順序表的刪除如下2-3（二）鏈?zhǔn)奖淼幕静僮髟创a#inclu

20、de<iostream>using namespace std;#define true 1#define false 0#define ok 1#define error 0#define overflow -2typedef int Status;typedef int ElemType;typedef struct LNode /存儲(chǔ)結(jié)構(gòu) ElemType data; struct LNode *next;LNode,*LinkList;void CreateList(LinkList &L,int n) /尾插法創(chuàng)建單鏈表 LinkList p; L=new LNo

21、de; L->next=NULL; /建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表 LinkList q=L; /使q指向表尾 for(int i=1;i<=n;i+) p=new LNode; cin>>p->data; p->next=NULL; q->next=p; q=p; Status GetElem(LinkList L,int i,ElemType &e)/取第i個(gè)元素 LinkList p=L->next; int j=1; while(p&&j<i) p=p->next; +j; if(!p|j>i) re

22、turn error; /第i個(gè)元素不存在 e=p->data; return ok;Status LinkInsert(LinkList &L,int i,ElemType e) /插入 LinkList p=L; int j=0; while(p&&j<i-1) p=p->next; +j; /尋找第i-1個(gè)結(jié)點(diǎn) if(!p|j>i-1) return error; /i小于1或者大于表長(zhǎng)加1 LinkList s=new LNode; /生成新結(jié)點(diǎn) s->data=e; s->next=p->next; /插入L中 p-&

23、gt;next=s; return ok; Status ListDelete(LinkList &L,int i,ElemType &e) / 刪除 LinkList p=L; LinkList q; int j=0; while(p->next&&j<i-1) /尋找第i個(gè)結(jié)點(diǎn)，并令p指向其前驅(qū) p=p->next; +j; if(!(p->next)|j>i-1) return error; /刪除位置不合理 q=p->next; p->next=q->next; /刪除并釋放結(jié)點(diǎn) e=q->data;

24、 delete(q); return ok;void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) /合并兩個(gè)順序鏈表LinkList pa,pc,pb;pa=La->next;pb=Lb->next;Lc=pc=La;while(pa&&pb) if(pa->data<=pb->data) pc->next=pa; pc=pa; pa=pa->next; else pc->next=pb; pc=pb; pb=pb->next; pc->n

25、ext=pa?pa:pb; delete(Lb); void show(LinkList L) /顯示 LinkList p; p=L->next; while(p) cout<<p->data<<"->" p=p->next; cout<<endl;int Length(LinkList L,int i) /表長(zhǎng) i=0; LinkList p=L->next; while(p) +i; p=p->next; return i; void xiugai(LinkList L) /修改 int i,j=

26、1; ElemType k; ElemType e,m; LinkList p=L->next; cout<<"請(qǐng)輸入要修改的元素位置(0<i<length):" cin>>i; GetElem(L,i,e); cout<<"該位置的元素:"<<e<<endl; cout<<"修改后的元素值:" cin>>k; while(p&&j<i) p=p->next; +j; m=p->data; p->

27、;data=k; cout<<"修改后的單鏈表顯示如下:"<<endl; show(L); void hebing() /合并兩個(gè)單鏈表 int a,b; LinkList La,Lb,Lc; cout<<"請(qǐng)輸入第一個(gè)有序鏈表的長(zhǎng)度:"<<endl; cin>>a; cout<<"請(qǐng)輸入第一個(gè)有序鏈表的元素共（"<<a<<"個(gè)）："<<endl; CreateList(La,a); show(La); co

28、ut<<"請(qǐng)輸入第二個(gè)有序鏈表的長(zhǎng)度:"<<endl; cin>>b; cout<<"請(qǐng)輸入第二個(gè)有序鏈表的元素共（"<<b<<"個(gè)）："<<endl; CreateList(Lb,b); show (Lb); MergeList(La,Lb,Lc); cout<<"合并后的有序鏈表如下："<<endl; show(Lc);void main() /主函數(shù) int select; int x; ElemTyp

29、e y; LinkList list; for(;) cout<<" 單鏈表的基本操作"<<endl; cout<<" 1.單鏈表的創(chuàng)建"<<endl; cout<<" 2.單鏈表的顯示"<<endl; cout<<" 3.單鏈表的長(zhǎng)度"<<endl; cout<<" 4.取第i個(gè)位置的元素"<<endl; cout<<" 5.修改第i個(gè)位置的元素&quo

30、t;<<endl; cout<<" 6.插入元素到單鏈表里"<<endl; cout<<" 7.刪除單鏈表里的元素"<<endl; cout<<" 8.合并兩個(gè)單鏈表"<<endl; cout<<" 9.退出系統(tǒng)"<<endl; cout<<"請(qǐng)選擇:" cin>>select; switch(select) case 1:cout<<"請(qǐng)輸入

31、單鏈表的長(zhǎng)度:"<<endl; cin>>x; cout<<"請(qǐng)輸入"<<x<<"個(gè)元素"<<endl; CreateList(list,x); break; case 2: cout<<"單鏈表顯示如下:"<<endl; show(list); break; case 3: int s; cout<<"單鏈表的長(zhǎng)度為:"<<Length(list,s)<<endl; bre

32、ak; case 4: cout<<"請(qǐng)選擇所要取出元素的位置:" cin>>x; while(x<0|x>Length(list,s) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl; cout<<"請(qǐng)選擇所要取出元素的位置:" cin>>x; GetElem(list,x,y); cout<<"該位置的元素為:"<<y<<endl; break; case 5: xiugai(list); break; case 6: cout<<"請(qǐng)選擇要插入的位置:" cin>>x; while(x<0|x>Length(list,s) cout<<"輸入有誤，請(qǐng)重新輸入"<<endl;