北京交通大學(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á)出來.3)要求都是帶頭結(jié)點(diǎn)的單鏈表.分組要求：可單獨(dú)完成，也可兩人一組。實(shí)驗(yàn)?zāi)康? 1)熟悉C/C+基本編程,培養(yǎng)動手能力. 2)通過實(shí)驗(yàn),加深對鏈表的理解.評分標(biāo)準(zhǔn)： 1) 第一題必做； 2）其它題為選做，不設(shè)上限。3）上機(jī)結(jié)束后，由助教檢查結(jié)果并適當(dāng)提問，根據(jù)情況給出成績。上機(jī)題目:一)建立單鏈表+求長度+顯示（3分） (1) 由鍵盤逐個(gè)輸入正整數(shù)，建立相應(yīng)的鏈表，輸入-1時(shí)，鏈表結(jié)束； (2) 顯示鏈表中的元素 (要求在顯示器可見)； (3) 求鏈表的

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

3、us;typedef int elemtype;typedef struct LNodeelemtype 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("請輸入一個(gè)元素:n"); scanf

4、("%d", &q->data); p=q; while (q->data != -1)q = (LinkList)malloc(sizeof(LNode);if(!q) exit(0); printf("請輸入另一個(gè)元素:n"); scanf("%d", &q->data); p->next=q; p=q; i+; p->next=NULL; printf("鏈表長度為： %dn",i); return OK;void print(LinkList&L)Lin

5、kList 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;p=L;while(p&&j<i-1) p=p->next;j+;q=(LinkList)malloc(sizeof(LNode);q->dat

6、a=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&&j<i) q=p; p=p->next;j+;e=p->data;q->next=q->next->next;free(p);return e;status GetElem_L(LinkList L,int i,elemtype &e)LinkList p;in

7、t j;p=L->next;j=1;while(p&&(j<i)p=p->next;j+;if(!p|j>i)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)L

8、inkList p;int i,j;p=L->next;i=j=p->data;while(p)if(i<p->data)i=p->data;if(j>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)

9、;print(L);printf("請輸入要插入的數(shù)據(jù):n");scanf("%d",&e);printf("請輸入要插入元素的位置:n");scanf("%d",&n);ListInsert_L(L,n,e);print(L);printf("請輸入要?jiǎng)h除的數(shù)據(jù)的位置:n");scanf("%d",&n);printf("被刪除的元素是:n");k=ListDelet_L(L,n,k);printf("%dn"

10、,k);printf("刪除后的單鏈表為:n");print(L);printf("請輸入所要顯示的元素的位置: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<stdio.h>#inclu

11、de<stdlib.h>typedef char datatype;typedef 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); /printli

12、st(lb); linklist lc=listadd(la,lb); printf("合并后的單鏈表為：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->n

13、ext=NULL; return head;void printlist(linklist head)/輸出單鏈表 linklist p; for(p=head->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-&

14、gt;next,pb=lb->next;pa&&pb;) if(pa->data>pb->data) p=(linklist)malloc(sizeof(listnode); p->data=pb->data; q->next=p; q=p; pb=pb->next; else if(pa->data<pb->data) p=(linklist)malloc(sizeof(listnode); p->data=pa->data; q->next=p; q=p; pa=pa->next; e

15、lse 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->next=p; q=p; pb=pb->next; if(pa!=NULL&&pb=NULL) while(pa!=NU

16、LL) 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)單鏈表，其頭指針為LA。#include<stdio.h>#include<malloc.h>typedef struct Lnode int data; struct Lnode *next; LNode

17、, *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-&

18、gt;next=head; return head;LinkList MergeList(LinkList LA,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

19、=L->next;while(p!=L)printf("%dn",p->data);p=p->next;printf("n");void main()LinkList LA,LB,LC;printf("請輸入循環(huán)鏈表A的元素:");LA=CreatList_L();ShowList(LA);printf("請輸入循環(huán)鏈表B的元素:");LB=CreatList_L();ShowList(LB);LC=MergeList(LA,LB);printf("合并后");ShowList

20、(LC);六）單鏈表應(yīng)用（2分）建立一個(gè)帶頭結(jié)點(diǎn)的線性鏈表，用以存放輸入的二進(jìn)制數(shù)，鏈表中每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位，并在此鏈表上實(shí)現(xiàn)對二進(jìn)制數(shù)加1的運(yùn)算。#include <stdio.h>#include <stdlib.h>#include <conio.h>/* 鏈表結(jié)點(diǎn) */typedef struct _Node struct _Node *next; /* 指向下一個(gè)結(jié)點(diǎn) */ unsigned char bit; /* 當(dāng)前結(jié)點(diǎn)所代表的二進(jìn)制位 */ Node;/* 在鏈表的結(jié)尾添加一個(gè)結(jié)點(diǎn) */void addNode(Node

21、*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 = head->next; node->bit = bit; head->next = node;Node* c

22、reateList(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(No

23、de *head) Node *node; unsigned char add; /* 頭結(jié)點(diǎn)并不算在二進(jìn)制數(shù)中，所以它的二進(jìn)制位是無效的 */ /* 如果只有頭結(jié)點(diǎn), 加1則生成一個(gè)結(jié)點(diǎn) */ /* 這就是說生成一個(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