111陈兴灶.docx
- 文档编号:12580767
- 上传时间:2023-06-06
- 格式:DOCX
- 页数:26
- 大小:91.49KB
111陈兴灶.docx
《111陈兴灶.docx》由会员分享,可在线阅读,更多相关《111陈兴灶.docx(26页珍藏版)》请在冰点文库上搜索。
111陈兴灶
实验报告2
课程数据结构实验名称单链表基本操作第页
专业计算机科学与技术班级___计本二班__学号__105032010111_姓名陈兴灶
实验日期:
2010年9月10日评分
一、实验目的
1.学会定义单链表的结点类型,实现对单链表的一些基本操作和具体的函数定义,了解并掌握单链表的类定义以及成员函数的定义与调用。
2.掌握单链表基本操作及两个有序表归并、单链表逆置等操作的实现。
二、实验要求
1.预习C语言中结构体的定义与基本操作方法。
2.对单链表的每个基本操作用单独的函数实现。
3.编写完整程序完成下面的实验内容并上机运行。
4.整理并上交实验报告。
三、实验内容
1.编写程序完成单链表的下列基本操作:
(1)初始化单链表La。
(2)在La中插入一个新结点。
(3)删除La中的某一个结点。
(4)在La中查找某结点并返回其位置。
(5)打印输出La中的结点元素值。
2.构造两个带有表头结点的有序(假设升序)单链表La、Lb,编写程序实现将La、Lb合并成一个有序(假设升序)单链表Lc。
合并思想是:
程序需要3个指针:
pa、pb、pc,其中pa,pb分别指向La表与Lb表中当前待比较插入的结点,pc指向Lc表中当前最后一个结点。
依次扫描La和Lb中的元素,比较当前元素的值,将较小者链接到*pc之后,如此重复直到La或Lb结束为止,再将另一个链表余下的内容链接到pc所指的结点之后。
四、实验步骤
第一题
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
#defineOVERFLOW-2
#defineLIST_INIT_SIZE100
#defineLISTINCREMENT10
#include
#include
#include
usingnamespacestd;
typedefintStatus;
typedefintElemType;
typedefstructLNode
{
ElemTypedata;
structLNode*next;
}LNode,*LinkList;
StatusInitList(LinkList&L)//初始化链表:
建立头结点并指向NULL
{
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
returnOK;
}
voidCreateList_L(LinkList&L,intn)//在链表中输入n个数
{
LNode*p,*q;
inti;
cout<<"请输入"< q=L; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=q->next; } p->next=NULL; }//CreateList_L StatusGetElem_L(LinkListL,inti,ElemType&e)//查找链表中第i个位置的值 { LNode*p; intj; p=L->next; j=1; while(p&&j { p=p->next; ++j; } if(! p||j>i) returnERROR; e=p->data; returnOK; }//GetElem_L StatusListInsert_L(LinkList&L,inti,ElemTypee)//在第i个位置之后插入值e { LNode*p,*s; intj=0; p=L; while(p&&j { p=p->next; ++j; } if(! p||j>i-1) returnERROR; s=(LinkList)malloc(sizeof(LNode)); s->data=e; s->next=p->next; p->next=s; returnOK; }//ListInsert_L StatusListDelete_L(LinkList&L,inti)//删除第i个数 { LNode*p,*q; intj=0; p=L; while(p->next&&j { p=p->next; ++j; } if(! (p->next)||j>i-1) returnERROR; q=p->next; p->next=q->next; free(q); returnOK; }//ListDelete_L intLocateElem_L(LinkList&L,ElemTypee)//找出链表中第一个与e相等的值的位置 { LNode*p; inti=1; p=L->next; while(p) { if(p->data! =e) {i++; p=p->next; } elsebreak; } if(! p)return0; elsereturni; }//LocateElem_L voidListTravel_L(LinkList&L)//打印链表 { LNode*p; p=L->next; while(p) { cout< p=p->next; } } voidmain() { ElemTypee; LinkListLa; inti,k,j; InitList(La); cout<<"请输入链表长度"< cin>>i;//输入4 CreateList_L(La,i);//输入1234 cout<<"您输入的链表为"< ListTravel_L(La);//预期结果: 1234 cout<<"请输入你要找的数"< cin>>j;//输入2 cout<<"你要找的数的位置为"< 你要找的数的位置为2 cout<<"请输入你要删的结点的位置"< cin>>k;//输入2 ListDelete_L(La,k); cout<<"删除后的链表为"< ListTravel_L(La);//预期结果: 134 cout<<"你要插入结点的位置为"< cin>>j;//输入2 cout<<"你要插入的数为"< cin>>e;//输入2 ListInsert_L(La,j,e); cout<<"插入后的链表为"< ListTravel_L(La);//预期结果: 1234 }; 第二题 #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE-1 #defineOVERFLOW-2 #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 #include #include #include usingnamespacestd; typedefintStatus; typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*LinkList; StatusInitList(LinkList&L)//初始化链表: 建立头结点并指向NULL { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK; } voidCreateList_L(LinkList&L,intn)//在链表中输入n个数 { LNode*p,*q; inti; cout<<"请输入"< q=L; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=q->next; } p->next=NULL; }//CreateList_L voidListTravel_L(LinkList&L)//打印链表 { LNode*p; p=L->next; while(p) { cout< p=p->next; } } voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)//合并链表 { LNode*pa,*pb,*pc; 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->next=pa? pa: pb; //free(Lb);这个不能用,不知道为什么? } } voidmain() { ElemTypee; LinkListLa,Lb,Lc; inti,k,j,n; InitList(La); InitList(Lb); InitList(Lc); cout<<"请输入链表1长度"< cin>>i;//输入3 CreateList_L(La,i);//输入123 cout<<"请输入链表2长度"< cin>>n;//输入4 CreateList_L(Lb,n);//输入3456 cout<<"您输入的链表为"< ListTravel_L(La);//预期结果123 cout< ListTravel_L(Lb);//预期结果3456 MergeList_L(La,Lb,Lc); cout<<"合并后的链表为"< ListTravel_L(Lc);//预期结果1233456 }; 五、实验结果与讨论 第一题结果 第二题结果 六、总结 得注意函数的边界问题;和储存问题,经常出现read不能为空这个错误。 七、思考与提高 1.如果上面实验内容2中合并的表内不允许有重复的数据该如何操作? 2.如何将一个带头结点的单链表La分解成两个同样结构的单链表Lb,Lc,使得Lb中只含La表中奇数结点,Lc中含有La表的偶数结点? 第一题 #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE-1 #defineOVERFLOW-2 #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 #include #include #include usingnamespacestd; typedefintStatus; typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*LinkList; StatusInitList(LinkList&L)//初始化链表: 建立头结点并指向NULL { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK; } voidCreateList_L(LinkList&L,intn)//在链表中输入n个数 { LNode*p,*q; inti; cout<<"请输入"< q=L; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=q->next; } p->next=NULL; }//CreateList_L voidListTravel_L(LinkList&L)//打印链表 { LNode*p; p=L->next; while(p) { cout< p=p->next; } } voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)//合并链表 { LNode*pa,*pb,*pc; pa=La->next; pb=Lb->next; Lc=pc=La; while(pa&&pb) { if(pa->data { pc->next=pa; pc=pa; pa=pa->next; } elseif(pa->data>pb->data) { pc->next=pb; pc=pb; pb=pb->next; } else { pc->next=pa; pc=pa; pa=pa->next; pb=pb->next; } pc->next=pa? pa: pb; //free(Lb);这个不能用,不知道为什么? } } voidmain() { LinkListLa,Lb,Lc; inti,n; InitList(La); InitList(Lb); InitList(Lc); cout<<"请输入链表1长度"< cin>>i;//输入3 CreateList_L(La,i);//输入123 cout<<"请输入链表2长度"< cin>>n;//输入4 CreateList_L(Lb,n);//输入3456 cout<<"您输入的链表为"< ListTravel_L(La);//预期结果123 cout< ListTravel_L(Lb);//预期结果3456 MergeList_L(La,Lb,Lc); cout<<"合并后的链表为"< ListTravel_L(Lc);//预期结果1233456 }; 结果 第二题 #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE-1 #defineOVERFLOW-2 #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 #include #include #include usingnamespacestd; typedefintStatus; typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*LinkList; StatusInitList(LinkList&L)//初始化链表: 建立头结点并指向NULL { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK; } voidCreateList_L(LinkList&L,intn)//在链表中输入n个数 { LNode*p,*q; inti; cout<<"请输入"< q=L; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=q->next; } p->next=NULL; }//CreateList_L voidListTravel_L(LinkList&L)//打印链表 { LNode*p; p=L->next; while(p) { cout< p=p->next; } } voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)//分解链表 { LNode*pa,*pb,*pc; inti; pa=La->next; pb=Lb; pc=Lc; for(i=1;pa! =NULL;i++) { if(i%2==1) { pb->next=pa; pb=pb->next; } else { pc->next=pa; pc=pc->next; } pa=pa->next; } pb->next=NULL; pc->next=NULL; } voidmain() { LinkListLa,Lb,Lc; inti; InitList(La); InitList(Lb); InitList(Lc); cout<<"请输入链表长度"< cin>>i; CreateList_L(La,i); cout<<"您输入的链表为"< ListTravel_L(La); MergeList_L(La,Lb,Lc); cout<<"分解后的链表为"< cout<<"La为"< ListTravel_L(Lb); cout<<"Lb为"< ListTravel_L(Lc); }; 实验结果 #defineTRUE1 #defineFALSE0 #defineOK1 #defineERROR0 #defineINFEASIBLE-1 #defineOVERFLOW-2 #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 #include #include #include usingnamespacestd; typedefintStatus; typedefintElemType; typedefstructLNode { ElemTypedata; structLNode*next; }LNode,*LinkList; StatusInitList(LinkList&L)//初始化链表: 建立头结点并指向NULL { L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; returnOK; } voidCreateList_L(LinkList&L,intn)//在链表中输入n个数 { LNode*p,*q; inti; cout<<"请输入"< q=L; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; q->next=p; q=q->next; } p->next=NULL; }//CreateList_L voidListTravel_L(LinkList&L)//打印链表 { LNode*p; p=L->next; while(p) { cout< p=p->next; } } voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc)//分解链表 { LNode*pa,*pb,*pc; pa=La->next; pb=Lb; pc=Lc; while(pa) { pb->next=pa; pb=pb->next; if(pa->next) { pc->next=pa->next; pc=pc->next; } elsebreak; pa=pa->next->next; } pb->next=NULL; pc->next=NULL; } voidmain() { LinkListLa,Lb,Lc; inti; InitList(La); InitList(Lb); InitList(Lc); cout<<"请输入链表长度"< cin>>i; CreateList_L(La,i); cout<<"您输入的链表为"< ListTravel_L(La); MergeList_L(La,Lb,Lc); cout<<"分解后的链表为"< cout<<"Lb为"< ListTravel_L(Lb); cout<<"Lc为"< ListTravel_L(Lc); };
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 111 陈兴灶