北京交通大学-数据结构上机实验1.doc

数据结构上机实验一实验内容:单链表的基本操作实验要求: 1)链表的显示要作为函数被调用. 2)把自己使用的单链表结构明确的表达出来.3)要求都是带头结点的单链表.分组要求：可单独完成，也可两人一组。实验目的: 1)熟悉C/C+基本编程,培养动手能力. 2)通过实验,加深对链表的理解.评分标准： 1) 第一题必做； 2）其它题为选做，不设上限。3）上机结束后，由助教检查结果并适当提问，根据情况给出成绩。上机题目:一)建立单链表+求长度+显示（3分） (1) 由键盘逐个输入正整数，建立相应的链表，输入-1时，链表结束； (2) 显示链表中的元素 (要求在显示器可见)； (3) 求链表的长度；（4）求链表的第i个元素；(i为参数)二)查找+插入+删除+显示 （1分） 在题目(一)的单链表中：(1)在链表中第i个位置插入新的数据元素，显示链表；(2)删除链表的第i个元素，输出该元素，显示链表；三)就地置逆+求最大最小值（1分） 在题目(一)的单链表中：(1)将链表就地逆置 ，显示链表； (2)求链表中的最大，最小值，显示结果；#include#include#include#define NULL 0#define ERROR 0#define OK 1typedef int status;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(请输入一个元素:n); scanf(%d, &q-data); p=q; while (q-data != -1)q = (LinkList)malloc(sizeof(LNode);if(!q) exit(0); printf(请输入另一个元素:n); scanf(%d, &q-data); p-next=q; p=q; i+; p-next=NULL; printf(链表长度为： %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;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-next;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(jp-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(请输入要插入的数据:n);scanf(%d,&e);printf(请输入要插入元素的位置:n);scanf(%d,&n);ListInsert_L(L,n,e);print(L);printf(请输入要删除的数据的位置:n);scanf(%d,&n);printf(被删除的元素是:n);k=ListDelet_L(L,n,k);printf(%dn,k);printf(删除后的单链表为:n);print(L);printf(请输入所要显示的元素的位置:n);scanf(%d,&i);printf(所取出的元素是:n);GetElem_L(L,i,m);printf(%dn,m);MostList(L);四) 链表的合并（1分） (1)创建两个链表LA，LB（各链表按升序排列），分别显示两链表； (2)将两个链表合并成一个新的有序表（升序排列），显示链表.#include#includetypedef 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); /printlist(lb); linklist lc=listadd(la,lb); printf(合并后的单链表为：n); printlist(lc);linklist creatlist()/创建单链表 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=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-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-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-next=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;五）单循环链表（2分）（1）建两个带头结点的循环单链表LA，LB单循环链表，（2）将两个循环单链表合并为一个循环单链表，其头指针为LA。#include#includetypedef struct Lnode int data; struct Lnode *next; LNode, *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,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(请输入循环链表A的元素:);LA=CreatList_L();ShowList(LA);printf(请输入循环链表B的元素:);LB=CreatList_L();ShowList(LB);LC=MergeList(LA,LB);printf(合并后);ShowList(LC);六）单链表应用（2分）建立一个带头结点的线性链表，用以存放输入的二进制数，链表中每个结点的data域存放一个二进制位，并在此链表上实现对二进制数加1的运算。#include #include #include /* 链表结点 */typedef struct _Node struct _Node *next; /* 指向下一个结点 */ unsigned char bit; /* 当前结点所代表的二进制位 */ Node;/* 在链表的结尾添加一个结点 */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 = head-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;/* 低端二进制位放在链表的前面 */void inc(Node *head) Node *node; unsigned char add; /* 头结点并不算在二进制数中，所以它的二进制位是无效的 */ /* 如果只有头结点, 加1则生成一个结点 */ /* 这就是说生成一个值为1的二进制数链表 */ if (head-next = NULL) addNode(head, 1); return; add = 1; node = head; /* add表示要在当前结点的后续结点的二进制值上加1 */ while (add) /* 如果当前结点的后续结点不存在，则增加一个结点在结尾，且其值为1 */ if (node-next = NULL) addNode(node, 1); return; /* 如果当前结点的后续结点