《数据结构 实验项目2XXX》由会员分享，可在线阅读，更多相关《数据结构 实验项目2XXX（10页珍藏版）》请在金锄头文库上搜索。
1、实验项目2：链表及其应用实验目的: 1.掌握单链表的逻辑结构和定义2.熟练掌握单链表的插入、删除、查找定位等基本算法； 3.能利用单链表解决简单的问题，如一元多项式的运算实验要求： 1.完成算法设计和程序设计，并上机调试通过 2.完成实验报告，提供实验数据和结果 3.对插入和删除算法进行时间复杂度的估算实验内容:实现单链表的基本操作，使得对于线性表(6,9,14,23,28,50), 调用单链表基本函数实现以下操作: 1.从键盘依次往链表中输入数据 2.在第3位插入数值10,输出单链表中信息 3.删除第4位数值, 输出单链表中信息. 4.查找表中是否有数据24，有则返回其位置 5.输出线性表中
2、第i个元素的值，位序i由用户通过键盘输入（选做）实验中含有以下函数定义：void CreateList_L(LinkList &L,int n) /*按逆序产生一个链表长度为n*/int ListLength_L(LinkList L) /* 返回L中数据元素个数 */Status GetElem_L(LinkList L,int i,ElemType &e) /*在线性表中获取第i个元素，元素保存在e中，返回成功或失败信息*/Status ListDisp_L(LinkList L)/*显示单链表*/int LocateElem_L(LinkList L,ElemType e)/* 返回L中
3、e的数据元素的位序,若不存在,则返回值为0 */Status ListInsert_L(LinkList L,int i,ElemType e) /* 在带头结点的单链线性表L中第i个位置之前插入元素e */Status ListDelete_L(LinkList L,int i,ElemType &e) /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */void ShowSelect(); /显示用户提示界面运行后，用户界面如下：#include#include#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0
4、#define Null 0typedef int Status;typedef int ElemType; typedef struct LNode ElemType data; struct LNode *next; LNode ,*LinkList;/* 思考： 请将本函数改写成按线性表元素顺序产生一个单链表,长度为n,再运行一次，观察两个函数在生成单链表时，元素输入顺序有何不同。*/ void CreateList_L(LinkList &L,int n) /*按逆序产生一个链表,长度为n*/int i; LinkList P; printf(生成单链表:n); L=(LinkList
5、)malloc(sizeof(LNode); L-next=Null; for(i=n;i0;i-) printf(请输入线性表中第%d个元素:n,i); P=(LinkList)malloc(sizeof(LNode); scanf(%d,&P-data); P-next=L-next; L-next=P; int ListLength_L(LinkList L) /* 返回L中数据元素个数 */ Linklist p;int i=0;p=L-next;while(p)i+;p=p-next;return i; Status GetElem_L(LinkList L,int i,ElemTy
6、pe &e) /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */ int j=1; LinkList p=L-next; while(p&jnext; j+; if(!p|ji) printf(位置信息不正确！); return ERROR; e=p-data; /* 取第i个元素，由元素e保存 */ return OK; int LocateElem_L(LinkList L,ElemType e)/* 返回L中e的数据元素的位序,若不存在,则返回值为0 */ int i=0; LinkList p=L-next; while(p) i+; if(p-data=e) /
7、* 找到这样的数据元素 */ return i; p=p-next; return 0; Status ListInsert_L(LinkList L,int i,ElemType e) /* 在带头结点的单链线性表L中第i个位置之前插入元素e */ int j=0; LinkList p=L,s; while(p&jnext; j+; if(!p|ji-1) printf(插入元素位置信息不正确！); return ERROR; s=(LinkList)malloc(sizeof(struct LNode); s-data=e; s-next=p-next; p-next=s; return
8、 OK; Status ListDelete_L(LinkList L,int i,ElemType &e) /* 在带头结点的单链线性表L中，删除第i个元素,并由e返回其值 */ int j=0; LinkList p=L,q; while(p-next&jnext; j+; if(!p-next|ji-1) printf(删除位置信息不正确！); return ERROR; q=p-next; p-next=q-next; e=q-data; free(q); return OK; Status ListDisp_L(LinkList L)/*显示单链表*/ linklist p;whil
9、e(p)printf(%d,p-data);p=p-next; /*显示选择提示信息函数*/void ShowSelect() printf(n 请选择要执行的操作：n); printf(-n); printf( 1-生成链表n); printf( 2-求单链表长度n);printf( 3-遍历输出单链表n); printf( 4-在单链表中检索查找n); printf( 5-向单链表中插入元素n);printf( 6-从单链表中删除元素n); printf( 7-从单链表中获取指定位置的元素n); printf( 0- 退出n); printf(-n); printf(请选择操作，输入数字
10、07 nn);int main(void) LinkList L; int i,x,flag; int len; /*表示单链表长*/ int select; /*select变量表示用户的选择项*/ShowSelect();scanf(%d,&select);while(select!=0)switch(select) /根据选择执行相应操作 case 1: printf(请输入线性表中元素个数：n); scanf(%d,&i); CreateList_L(L,i);break; case 2: len=ListLength_L(L); printf(链表长为%dn,len);break;
11、case 3: ListDisp_L(L);break; case 4: printf(n请输入你想查找的数据:); scanf(%d,&x); flag=LocateElem_L(L,x); if(flag) printf(该元素在顺序表中的位置是：%dn,flag) ; else printf(该元素在顺序表中不存在); break; case 5: printf(请输入要插入的元素的值和位置，用空格分隔：n); scanf(%d %d,&x,&i); flag=ListInsert_L(L,i,x); if(flag) printf(插入操作成功); break; case 6: pri
12、ntf(请输入要删除的元素的位置：n); scanf(%d,&i); flag= ListDelete_L(L,i,x); if(flag) printf(删除操作成功,删除的元素是%d,x); break; case 7: printf(请输入要查找的元素位置：n); scanf(%d,&i); flag= GetElem_L(L,i,x); if(flag) printf(第%d位的元素是%d,i,x); break;ShowSelect();scanf(%d,&select);return 0;附录：以下内容不作为本次实验内容，本程序是线性表应用一元多项式的实现，可以求导数和一元多项式相加，内容见教材，有兴趣的同学可以自己完成，也可以看看。线性表的应用 -稀疏多项式计算器(vc环境，&符号)#include#include#define Null 0typedef struct LNode /* 项的表示,多项式的项作为LinkList的数据元素 */
