北京交通大學(xué)-數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)1

1、數(shù)據(jù)結(jié)構(gòu)上機(jī)實(shí)驗(yàn)一實(shí)驗(yàn)內(nèi)容:單鏈表的基本操作實(shí)驗(yàn)要求: 1)鏈表的顯示要作為函數(shù)被調(diào)用. 2)把自己使用的單鏈表結(jié)構(gòu)明確的表達(dá)出來(lái).3)要求都是帶頭結(jié)點(diǎn)的單鏈表.分組要求：可單獨(dú)完成，也可兩人一組。實(shí)驗(yàn)?zāi)康? 1)熟悉C/C+基本編程,培養(yǎng)動(dòng)手能力. 2)通過(guò)實(shí)驗(yàn),加深對(duì)鏈表的理解.評(píng)分標(biāo)準(zhǔn)： 1) 第一題必做； 2）其它題為選做，不設(shè)上限。3）上機(jī)結(jié)束后，由助教檢查結(jié)果并適當(dāng)提問(wèn)，根據(jù)情況給出成績(jī)。上機(jī)題目:一)建立單鏈表+求長(zhǎng)度+顯示（3分） (1) 由鍵盤(pán)逐個(gè)輸入正整數(shù)，建立相應(yīng)的鏈表，輸入-1時(shí)，鏈表結(jié)束； (2) 顯示鏈表中的元素 (要求在顯示器可見(jiàn))； (3) 求鏈表的長(zhǎng)度；（4）

2、求鏈表的第i個(gè)元素；(i為參數(shù))二)查找+插入+刪除+顯示 （1分） 在題目(一)的單鏈表中：(1)在鏈表中第i個(gè)位置插入新的數(shù)據(jù)元素，顯示鏈表；(2)刪除鏈表的第i個(gè)元素，輸出該元素，顯示鏈表；三)就地置逆+求最大最小值（1分） 在題目(一)的單鏈表中：(1)將鏈表就地逆置 ，顯示鏈表； (2)求鏈表中的最大，最小值，顯示結(jié)果；#include#include#include#define NULL 0#define ERROR 0#define OK 1typedef int status;typedef int elemtype;typedef struct LNodeelemtype

3、data;struct LNode *next;LNode,*LinkList;CreatList_L(LinkList &L,int n)LinkList p, q;int i=0; L=(LinkList)malloc(sizeof(LNode); if(!L) exit(0); q=(LinkList)malloc(sizeof(LNode); if(!q) exit(0); L-next=q; printf(請(qǐng)輸入一個(gè)元素:n); scanf(%d, &q-data); p=q; while (q-data != -1)q = (LinkList)malloc(sizeof(LNode

4、);if(!q) exit(0); printf(請(qǐng)輸入另一個(gè)元素:n); scanf(%d, &q-data); p-next=q; p=q; i+; p-next=NULL; printf(鏈表長(zhǎng)度為： %dn,i); return OK;void print(LinkList&L)LinkList p =L-next;while(p!=NULL & p-data!=-1)printf(%3d,p-data);p = p-next;printf(n);status ListInsert_L(LinkList &L,int i,elemtype &e)int j=0;LinkList p,q

5、;p=L;while(p&jnext;j+;q=(LinkList)malloc(sizeof(LNode);q-data=e;q-next=p-next;p-next=q;return 1;status ListDelet_L(LinkList &L,int i,elemtype &e)LinkList p,q;int j=0;p=L;while(p&jnext;j+;e=p-data;q-next=q-next-next;free(p);return e;status GetElem_L(LinkList L,int i,elemtype &e)LinkList p;int j;p=L-n

6、ext;j=1;while(p&(jnext;j+;if(!p|ji)return ERROR;e=p-data;return OK;status ListReverse(LinkList &L)LinkList t,p,q; t=L-next; p=t-next; t-next=NULL;while(p!=NULL)q=p-next; p-next=t; t=p; p=q; L=t; return OK; void MostList(LinkList L)LinkList p;int i,j;p=L-next;i=j=p-data;while(p)if(idata)i=p-data;if(j

7、p-data)j=p-data;p=p-next;printf(最大值為:%dn,i);printf(最小值為:%dn,j);void main()LinkList L;int n,e,k,m,i;CreatList_L(L,n);print(L);printf(逆置后的單鏈表為:n);ListReverse(L);print(L);printf(請(qǐng)輸入要插入的數(shù)據(jù):n);scanf(%d,&e);printf(請(qǐng)輸入要插入元素的位置:n);scanf(%d,&n);ListInsert_L(L,n,e);print(L);printf(請(qǐng)輸入要?jiǎng)h除的數(shù)據(jù)的位置:n);scanf(%d,&n)

8、;printf(被刪除的元素是:n);k=ListDelet_L(L,n,k);printf(%dn,k);printf(刪除后的單鏈表為:n);print(L);printf(請(qǐng)輸入所要顯示的元素的位置:n);scanf(%d,&i);printf(所取出的元素是:n);GetElem_L(L,i,m);printf(%dn,m);MostList(L);四) 鏈表的合并（1分） (1)創(chuàng)建兩個(gè)鏈表LA，LB（各鏈表按升序排列），分別顯示兩鏈表； (2)將兩個(gè)鏈表合并成一個(gè)新的有序表（升序排列），顯示鏈表.#include#includetypedef char datatype;typed

9、ef struct node datatype data; struct node *next;listnode;typedef listnode *linklist;void main() linklist creatlist(); void printlist(linklist); linklist listadd(linklist,linklist); linklist la=creatlist(); linklist lb=creatlist(); /printlist(la); /printlist(lb); linklist lc=listadd(la,lb); printf(合并

10、后的單鏈表為：n); printlist(lc);linklist creatlist()/創(chuàng)建單鏈表 char ch; linklist head=(linklist)malloc(sizeof(listnode); linklist p,q; q=head; while(ch=getchar()!=n) p=(linklist)malloc(sizeof(listnode); p-data=ch; q-next=p; q=p; q-next=NULL; return head;void printlist(linklist head)/輸出單鏈表 linklist p; for(p=hea

11、d-next;p;p=p-next) printf(%c ,p-data); printf(n);linklist listadd(linklist la,linklist lb)/兩鏈表合并 linklist pb,pa,p,q; linklist head=(linklist)malloc(sizeof(listnode); q=head; for(pa=la-next,pb=lb-next;pa&pb;) if(pa-datapb-data) p=(linklist)malloc(sizeof(listnode); p-data=pb-data; q-next=p; q=p; pb=pb

12、-next; else if(pa-datadata) p=(linklist)malloc(sizeof(listnode); p-data=pa-data; q-next=p; q=p; pa=pa-next; else p=(linklist)malloc(sizeof(listnode); p-data=pb-data; q-next=p; q=p; pb=pb-next; pa=pa-next; if(pa=NULL&pb!=NULL) while(pb!=NULL) p=(linklist)malloc(sizeof(listnode); p-data=pb-data; q-nex

13、t=p; q=p; pb=pb-next; if(pa!=NULL&pb=NULL) while(pa!=NULL) p=(linklist)malloc(sizeof(listnode); p-data=pa-data; q-next=p; q=p; pa=pa-next; q-next=NULL; return head;五）單循環(huán)鏈表（2分）（1）建兩個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表LA，LB單循環(huán)鏈表，（2）將兩個(gè)循環(huán)單鏈表合并為一個(gè)循環(huán)單鏈表，其頭指針為L(zhǎng)A。#include#includetypedef struct Lnode int data; struct Lnode *next; L

14、Node, *LinkList;LinkList CreatList_L(void) LinkList head; LinkList p1,p2; head=p1=p2=(LinkList)malloc(sizeof(LNode); scanf(&d,&p1-data); head-next=p1; while(p1-data!=-1) p2-next=p1; p2=p1; p1=(LinkList)malloc(sizeof(LNode); scanf(%d,&p1-data); p2-next=head; return head;LinkList MergeList(LinkList LA

15、,LinkList LB)LinkList p,q,m,n;n=LA;p=LA-next;q=m=LB-next;while(p-next!=LA)p=p-next;while(q-next!=LB)q=q-next;q-next=p-next;p-next=m;p=q;return n;void ShowList(LinkList L)printf(鏈表為:n);LinkList p;p=L-next;while(p!=L)printf(%dn,p-data);p=p-next;printf(n);void main()LinkList LA,LB,LC;printf(請(qǐng)輸入循環(huán)鏈表A的元素

16、:);LA=CreatList_L();ShowList(LA);printf(請(qǐng)輸入循環(huán)鏈表B的元素:);LB=CreatList_L();ShowList(LB);LC=MergeList(LA,LB);printf(合并后);ShowList(LC);六）單鏈表應(yīng)用（2分）建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位，并在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算。#include #include #include /* 鏈表結(jié)點(diǎn) */typedef struct _Node struct _Node *next; /* 指向下一個(gè)結(jié)點(diǎn) */ u

17、nsigned char bit; /* 當(dāng)前結(jié)點(diǎn)所代表的二進(jìn)制位 */ Node;/* 在鏈表的結(jié)尾添加一個(gè)結(jié)點(diǎn) */void addNode(Node *prior, unsigned char bit) Node *node = (Node *)malloc(sizeof(Node); node-next = NULL; node-bit = bit; prior-next = node;void insToHead(Node *head, unsigned char bit) Node *node = (Node *)malloc(sizeof(Node); node-next = h

18、ead-next; node-bit = bit; head-next = node;Node* createList(void) int bit; Node *head = (Node *)malloc(sizeof(Node); head-next = NULL; while (bit = getch() != 26) if (bit = 1 | bit = 0) bit = bit - 0; printf(%d, bit); insToHead(head, bit); printf(n); return head;/* 低端二進(jìn)制位放在鏈表的前面 */void inc(Node *hea

19、d) Node *node; unsigned char add; /* 頭結(jié)點(diǎn)并不算在二進(jìn)制數(shù)中，所以它的二進(jìn)制位是無(wú)效的 */ /* 如果只有頭結(jié)點(diǎn), 加1則生成一個(gè)結(jié)點(diǎn) */ /* 這就是說(shuō)生成一個(gè)值為1的二進(jìn)制數(shù)鏈表 */ if (head-next = NULL) addNode(head, 1); return; add = 1; node = head; /* add表示要在當(dāng)前結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)的二進(jìn)制值上加1 */ while (add) /* 如果當(dāng)前結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)不存在，則增加一個(gè)結(jié)點(diǎn)在結(jié)尾，且其值為1 */ if (node-next = NULL) addNode(node, 1); return; /* 如果當(dāng)前結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)