中北大学算法与数据结构实验报告课案.docx
- 文档编号:10321662
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:100
- 大小:270.73KB
中北大学算法与数据结构实验报告课案.docx
《中北大学算法与数据结构实验报告课案.docx》由会员分享,可在线阅读,更多相关《中北大学算法与数据结构实验报告课案.docx(100页珍藏版)》请在冰点文库上搜索。
中北大学算法与数据结构实验报告课案
实验类别:
算法与数据结构
专业:
信息与计算科学
班级:
13080241
学号:
1308024120
姓名:
杨燕
中北大学理学院
实验一链表的应用
(一)建立线性表
【实验内容】
1、画出详细规范的算法流程图
2、定义链表结点数据类型
3、定义链表数据类型
4、实现单向线性链表的建立
5、实现单向线性链表取元素
6、实现单向线性链表遍历
7、实现单向线性链表插入
8、实现单向线性链表删除
【实验方法与步骤】
1、定义链表结点数据类型
typedefstructLNode
{intdata;
structLNode*next;
}LNode,*LinkList;
其中intdata;表示节点是整型数据,若定义浮点型的为:
floatdata;其他类似。
2、定义链表数据类型
typedefcharDateType
typedefstructLNode
{DateTypedata;
structLNode*next;
}LNode,*LinkList;
3、实现单向线性链表的建立
#include
#include
#include
typedefstructLNode
{intdata;
structLNode*next;
}LNode,*LinkList;
voidCreateList_L(LinkList&L,intn)
{//逆位序输入n个数据元素的值,建立带头结点的单链表L
inti;
LNode*p;
L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;//先建立一个带头结点的空链表
cout<<"请输入创建的单链表中的数据:
<如:
34,67,3,-9,45,...>"< for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode));//生成新结点 cin>>p->data; p->next=L->next;//将新结点插入到单链表的头 L->next=p;//修改单链表头结点的指针域 }//for结束 if(n)cout<<"成功创建一个单链表! "< elsecout<<"创建了一个空链表! "< } voidmain() { LinkListL; intInitLNodeNum; cout<<"CreateList_L.cpp"< cout< "; cin>>InitLNodeNum; CreateList_L(L,InitLNodeNum); cout<<"OK...! "< getch(); }//endofmain()function 4、实现单向线性链表取元素 #include #include #include #defineElemTypeint #defineLIST_MAX_LENGTH100//LIST_MAX_LENGTH是单链表L的最大长度 typedefstructLNode {ElemTypedata; structLNode*next; }LNode,*LinkList; voidCreateList_L(LinkList&L,intn) {//创建一个带头结点的单链表L inti; LNode*p; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=n;i>0;--i) { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; } } intGetElem_L(LinkListL,inti,int&e)//GetElem_L()function {//L为带头结点的单链表的头指针,当第i个元素存在时,其值赋给e并返回OK, //否则返回Error LNode*p; intj=1; p=L->next;//初始化,p指向链表第一个结点,j为计数器 while(p&&j {p=p->next;++j;} if(! p||j>i) {cout<<"这个元素"< "< getch(); exit(0); }//结束if e=p->data; return(e); }//结束单链表的取元素 voidmain()//main()function { LinkListL; inte;//ecanbeEveryDataType inti,LListNodeNum;//jisacounterforcycle cout<<"GetElem_L.cpp"< cout<<"请输入创建的单链表的大小: "; cin>>LListNodeNum; cout<<"请输入创建的单链表中的数据: "< CreateList_L(L,LListNodeNum); cout< "< cout<<"你想提取哪一个位置上的数据? : "< cin>>i;//输入要提取的数据 if(i>LListNodeNum)cout< "< GetElem_L(L,LListNodeNum-i+1,e); cout< "< cout< "< getch(); } 5、实现单向线性链表遍历 #include #include #include #include #defineLIST_INIT_LENGTH10//LIST_INIT_LENGTHistheInit_Define_LengthofLinkList typedefintElemType; typedefstructLNode { intdata; structLNode*next; }LNode,*LinkList; voidCreateList_L(LinkList&L,intn)//CreatList_L()subfunction {//ToCreatreaLinkListLwithHeadNode inti; LNode*p; intarray[LIST_INIT_LENGTH]; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; printf("Pleaseinputthenodesdata: for(i=0;i scanf("%d",&array[i]); for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); p->data=array[i];//forexampletoaCreateList p->next=L->next; L->next=p; }//endoffor }//endofCreateList_L()function voidContray(LinkList&head)//Contray()function {//DeletetheNO.ielementofLinkListandreturnbyvariablee LNode*p,*q; p=head; head=NULL; while(p) { q=p; p=p->next; q->next=head; head=q; }//endofwhile cout< "; }//endofContray()function voidmain()//main()function { LinkListL; LNode*p; inti,LNodeNum;//jisjustacounterforcycle cout<<"Contray.cpp"< cout<<"Howmanynodesdoyouwanttocreate? cin>>LNodeNum; CreateList_L(L,LNodeNum); p=L; cout< for(i=0;i { p=p->next; cout< } cout< cout<<"<------------------------------<"< Contray(L);//callfunctionContray(); cout< ["; for(i=0;i { cout< L=L->next; } cout<<"]"< "< getch(); }//endofmain()function 6、实现单向线性链表插入 #include #include #include #include #defineINIT_LENGTH10 #defineOK1 #defineERROR0 typedefstructLNode//defineLNodestructure {intdata; structLNode*next; }LNode,*Linklist; intListInsert_L(Linklist&L,inti,inte) {//在带头结点的单链线性表L中第i个位置之前插入元素e LNode*p=L; intj=0; while(p&&j {p=p->next; ++j; } if(! p||j>i-1)//i小于1或i大于表长 {cout<<"错误! 这个位置不存在! "< return(ERROR); } LNode*s; s=(Linklist)malloc(sizeof(LNode));//生成新结点 s->data=e; s->next=p->next; p->next=s; return(OK); }//ListInsert_L()end voidmain()//main()function {inti,j,e; LNodenode[10]; LNode*L,*p; intarray[INIT_LENGTH+1]={5,8,12,18,25,30,37,46,51,89}; L=node; L=(Linklist)malloc(sizeof(LNode)); L->next=NULL; for(i=10;i>0;i--) {p=(Linklist)malloc(sizeof(LNode)); p->data=array[i-1]; p->next=L->next; L->next=p; } p=L; cout< cout< cout< "; for(i=0;i {p=p->next; cout< } cout< cin>>j; cout<<"请输入要插入的元素: "; cin>>e; if(ListInsert_L(L,j,e)) {cout< "; p=L; for(i=0;i<11;i++) {p=p->next; cout< } } cout< ..."; getch(); } 7、实现单向线性链表删除 #include #include #include typedefstructLNode {intdata; structLNode*next; }LNode,*LinkList; voidCreateList_L(LinkList&L,intn)//CreateList_L()function {//创建一个带头结点的单链表L inti; LNode*p; L=(LinkList)malloc(sizeof(LNode)); L->next=NULL; for(i=0;i { p=(LinkList)malloc(sizeof(LNode)); cin>>p->data; p->next=L->next; L->next=p; }//结束for }//endofCreateList()function intListDelete_L(LinkList&L,inti,int&e)//ListDelete_L()function {//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值 LNode*p,*q; intj=0; p=L; while(p->next&&j {p=p->next;++j; } if(! p||j>i-1)//删除位置不合理 {cout<<"位置"< "< getch(); return(0); } q=p->next;//用指针q指向被删除的结点 p->next=q->next;//删除第i个结点 e=q->data;//取出第i个结点数据域值 free(q);//释放第i个结点 return(e); }//结束删除元素 voidmain()//main()function { LinkListL; LNode*p; inte;//ecanbeEveryDataType inti,j;//jisjustacounterforcycle intLListNodeNum; cout<<"ListDelete_L.cpp"< cout<<"请输入创建的单链表的结点个数: "; cin>>LListNodeNum; cout< CreateList_L(L,LListNodeNum); cout< "; p=L->next; while(p)//输出创建的单链表 {cout< p=p->next; }//endoffor cout< : "; cin>>i;//输入要删除的位置 if(i<=LListNodeNum) {cout<<"数据"< for(j=1;j { L=L->next; cout< }//结束for cout< "< }//结束if elsecout<<"InputError! "< getch(); }//endofmain()function 【实验结果】 1、写出实验的总结与体会,要简洁、真实、深刻;忌空话、套话 2、单向链表和双向链表在实现时的区别 3、单向链表如何修改实现循环链表 实验二链表的应用 (二)栈的应用 【实验内容】 1、实现单向链栈的抽象数据类型 2、实现单向链栈的建立、销毁、取栈顶元素、压栈、弹栈的运算 3、给出包含括号和+、-、*、\四则运算的运算符优先级表 4、创建运算符栈和运算数栈 5、实现有一定通用性的程序,实现一个四则运算表达式的求解 6、设计测试用的运算表达式,通过键盘输入进行测试 【实验方法与步骤】 1、构造空链式队列算法 #include #include #include #defineMAXQSIZE100 #defineOK1 #defineERROR0 typedefintQElemType; typedefstructSqQueue//创建一个头结点 {QElemType*base; intfront; intrear; }SqQueue; intInitQueue(SqQueue&Q) {Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType)); if(! Q.base)//存储空间分配失败 {cout< "; return(ERROR); } Q.front=Q.rear=0; return(OK); }//InitQueue()end voidmain()//mainfunction {SqQueueQ; cout< cout< if(InitQueue(Q)) cout< 链式队列已被构造! "; cout< ..."; getch(); }//main()end 2、销毁链式队列算法 #include #include #include #defineMAXQSIZE100 #defineOK1 #defineERROR0 typedefintQElemType; typedefstructQNode//definestructureQNode {QElemTypedata; structQNode*next; }QNode,*QueuePtr; typedefstructLinkQueue//definestructureLinkQueue {QueuePtrfront; QueuePtrrear; }LinkQueue; intEnQueue(LinkQueue&Q,QElemTypee)//构造队列 {QNode*p; p=(QueuePtr)malloc(sizeof(QNode)); if(! p) {cout< "; return(ERROR); } p->data=e; p->next=NULL; if(Q.front==NULL)//newQNode {Q.front=Q.rear=p; return(OK); } Q.rear->next=p; Q.rear=p; return(OK); }//EnQueue()end intDestroyQueue(LinkQueue&Q)//销毁队列Q {while(Q.front) {Q.rear=Q.front->next; free(Q.front); Q.front=Q.rear; } return(OK); }//DestroyQueue()end voidmain()//main()function {inti,e=1; LinkQueueQ; QNode*q; Q.front=Q.rear=NULL; cout< cout< while(e) {cout<<"请输入队列当中的数据(如58到0或exit): "; cin>>e; if(e) EnQueue(Q,e)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 北大 算法 数据结构 实验 报告