实验报告专用纸2[教育相关]

1、延安大学计算机学院实验报告专用纸学号1060315014032姓名陈世龙班级计科15-1课程名称数据结构实验项目名称线性表任课教师曹军梅指导教师曹军梅实验组别第 组同组者教师评语及成绩： 实验成绩： 教师签字： （请按照实验报告的有关要求书写，一般必须包括：1、实验目的；2、实验内容；3、实验步骤与方法；4、实验数据与程序清单；5、出现的问题及解决方法；6、实验结果、结果分析与体会等内容。） 1、实验目的： （1）、掌握线性表的基本运算； （2）、掌握顺序存储的概念，学会对顺序存储结构进行操作； （3）、加深对顺序存储数据结构的理解，解决实际问题。 2、实验内容： （1）、线性表的顺序存储的基

2、本操作； （2）、线性表的链式存储的基本操作； （3）、线性表的应用-一元多项式的表示及相加都基本操作。 3、实验步骤与方法： （1）、采用线性表的链式存储结构；（2）、用菜单的形式完成线性表链式存储结构的基本操作；（3）、采用线性表的顺序存储结构；（4）、用菜单的形式完成线性表顺序存储结构的基本操作；（5）、运用线性表链式存储结构解决常见实际应用问题；（6）、运用线性表顺序结构解决常见实际应用问题。 4、实验数据与程序清单：实验一：线性表中查找元素位置#include #include #define NULL 0#define OVERFLOW -2实验室： 机号： 实验日期： 年 月 日

3、延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;int Locate(SeqList L

4、, ElemType e)int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/while (i=L.last)&(L.elemi!=e)i+; if (i=L.last)return(i+1); /*若找到值为e的元素，则返回其序号*/elsereturn(-1); /*若没找到，则返回空序号*/void main()SeqList l;int p,q,r;int i;printf(请输入线性表的长度:);scanf(%d,&r);l.last = r-1;printf(请输入线性表的各元素值:n);for(i=0; i=l.last; i+)scanf(%d,&l.el

5、emi);printf(请输入要查找的元素值:n);scanf(%d,&q);p=Locate(l,q);if(p = -1)printf(在此线性表中没有该元素!n);elseprintf(该元素在线性表中的位置为:%dn,p);延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表实验二：线性表中插入元素操作#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 10

6、0 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;int InsList(SeqList *L,int i,ElemType e) int k;if(iL-last+2) /*首先判断插入位置是否合法*/延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表printf(插入位置i值不合法);return(ERROR);if(L

7、-last= MAXSIZE-1)printf(表已满无法插入);return(ERROR);for(k=L-last;k=i-1;k-) /*为插入元素而移动位置*/L-elemk+1=L-elemk;L-elemi-1=e; /*在C语言数组中，第i个元素的下标为i-1*/L-last+;return(OK);void main()SeqList *l;int p,q,r;int i;l=(SeqList*)malloc(sizeof(SeqList);printf(请输入线性表的长度:);scanf(%d,&r);l-last = r-1;printf(请输入线性表的各元素值:n);fo

8、r(i=0; ilast; i+)scanf(%d,&l-elemi);printf(请输入要插入的位置:n);scanf(%d,&p);printf(请输入要插入的元素值:n);scanf(%d,&q);InsList(l,p,q);for(i=0; ilast; i+)printf(%d ,l-elemi);延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表实验三：线性表中删除元素操作#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FAL

9、SE 0#define ElemType int#defineMAXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;int DelList(SeqList *L,int i,ElemType *e) int k;if(iL-last+1) printf(删除位置不合法!);return(ERROR);*e = L-elemi-1; /* 将删除的元素存放到e

10、所指向的变量中*/ for(k=i; ilast; k+)延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表L-elemk-1 = L-elemk; /*将后面的元素依次前移*/L-last-;return(OK);void main()SeqList *l;int p,r;int *q;int i;l = (SeqList*)malloc(sizeof(SeqList);q = (int*)malloc(sizeof(int);printf(请输入线性表的长度:);scanf(%d,&r);l-last = r-1;printf(请输入线性表

11、的各元素值:n);for(i=0; ilast; i+)scanf(%d,&l-elemi);printf(请输入要删除的元素位置:n);scanf(%d,&p);DelList(l,p,q);printf(删除的元素值为:%dn,*q);实验四：线性表的合并#include #include #include #define OK 1延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#defineMAXSIZE 10

12、0 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;voidmerge(SeqList *LA, SeqList *LB, SeqList *LC)int i,j,k;i=0;j=0;k=0;while(ilast&jlast)if(LA-elemielemj)LC-elemk= LA-elemi;i+; k+;elseLC-elemk=LB-elemj;j+; k+; wh

13、ile(ilast)/*当表LA有剩余元素时，则将表LA余下的元素赋给表LC*/LC-elemk= LA-elemi;i+; k+;while(jlast) /*当表LB有剩余元素时，则将表LB余下的元素赋给表LC*/LC-elemk= LB-elemj;j+; k+;LC-last=LA-last+LB-last+1;void main()SeqList *la,*lb,*lc;int r;int i;la=(SeqList*)malloc(sizeof(SeqList);printf(请输入线性表A的长度:);scanf(%d,&r);la-last = r-1;printf(请输入线性表

14、A的各元素值:n);延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表for(i=0; ilast; i+)scanf(%d,&la-elemi);lb=(SeqList*)malloc(sizeof(SeqList);printf(请输入线性表B的长度:);scanf(%d,&r);lb-last = r-1;printf(请输入线性表B的各元素值:n);for(i=0; ilast; i+)scanf(%d,&lb-elemi);lc=(SeqList*)malloc(sizeof(SeqList);merge(la,lb,lc);prin

15、tf(合并后线性表C中的元素为:n);for(i=0; ilast; i+)printf(%d ,lc-elemi);实验五：用头插法建立单链表#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#include 延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#define ElemType chartypedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;N

16、ode, *LinkList; /* LinkList为结构指针类型*/LinkList CreateFromHead() LinkList L;Node *s;char c;int flag=1;L=(LinkList)malloc(sizeof(Node); /*建立头结点*/L-next=NULL; /*建立空的单链表L*/while(flag) /* flag初值为1，当输入$时，置flag为0，建表结束*/c=getchar(); if(c!=$)s=(Node*)malloc(sizeof(Node); /*建立新结点s*/s-data=c;s-next=L-next;/*将s结点

17、插入表头*/L-next=s;elseflag=0;return L;void main()LinkList l;Node *p;printf(用头插法建立单链表,请输入链表数据,以$结束!n);l = CreateFromHead();p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表实验六：用尾插法建立单链表#include #include #include #define OK 1#define ERROR 0#define TRU

18、E 1#define FALSE 0typedef char ElemType;typedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/void init_linklist(LinkList *l)/*对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node); (*l)-next=NULL;void CreateFromTail(LinkList L) Node *r, *s;char c;int flag =1; /*

19、设置一个标志，初值为1，当输入$时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/ c=getchar();if(c!=$)延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ void main()LinkL

20、ist l;Node *p;init_linklist(&l);printf(用尾插法建立单链表,请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;实验七：查找线性表结点值#include #include #include #define OK 1延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemTy

21、pe;typedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/void init_linklist(LinkList *l)/*对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node); (*l)-next=NULL;void CreateFromTail(LinkList L) Node *r, *s;char c;int flag =1; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/r=L; /

22、*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ Node * Get (LinkList L, int i) int j;Node *p;p=L;j=0; /*从头结点开始扫描*/while (p-next!=NULL)&(jnext; /* 扫描下一结点

23、*/j+; /* 已扫描结点计数器 */if(i = j)延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表return p; /* 找到了第i个结点 */else return NULL; /* 找不到，i0或in */ void main()LinkList l;Node *p;int j;init_linklist(&l);printf(请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf(请输入要查找的结

24、点序号:n);scanf(%d,&j);p = Get(l,j);if(p!=NULL)printf(该结点的值为:%cn,p-data);elseprintf(未找到此结点!n);实验八：判断线性表长度#include #include #include 延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef char ElemType;typedef struct Node /*结点类型定义*/ ElemType dat

25、a;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/void init_linklist(LinkList *l)/*对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node); (*l)-next=NULL;void CreateFromTail(LinkList L) Node *r, *s;char c;int flag =1; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag)

26、/*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ intListLength(LinkList L)/*求带头结点的单链表L的长度*/ Node *p;int j;p=L-next;j=0; /*用来存放单链表的长度*/while(p!=NULL) p=p-next;j+;延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计

27、科15-1实验名称线性表return j;/*j为求得的单链表长度*/ void main()LinkList l;Node *p;init_linklist(&l);printf(请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf(该单链表的长度为%dn,ListLength(l);实验九：线性表结点插入操作#include #include #include #define OK 1#define ERROR 0#define TRUE 1#define

28、FALSE 0typedef char ElemType;typedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表void init_linklist(LinkList *l)/*对单链表进行初始化*/*l=(LinkList)malloc(sizeof(Node); (*l)-next=NULL;void CreateFromTail(LinkLis

29、t L) Node *r, *s;char c;int flag =1; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/c=getchar();if(c!=$)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ int InsList(LinkList L,int i

30、,ElemType e) Node *pre,*s;int k;pre=L; k=0;while(pre!=NULL&knext;k=k+1; /*查找第i-1结点*/if(!pre) /*如当前位置pre为空表已找完还未数到第i个，说明插入位置不合理*/ printf(插入位置不合理!);return ERROR;s=(Node*)malloc(sizeof(Node); /*申请一个新的结点S */s-data=e; /*值e置入s的数据域*/s-next=pre-next;/*修改指针，完成插入操作*/pre-next=s;return OK;void main()延安大学计算机学院实验

31、报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表LinkList l;Node *p;int flag=0;int i;char c;init_linklist(&l);printf(请输入链表数据,以$结束!n);CreateFromTail(l);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;printf(请输入插入的位置和元素:n);scanf(%d,%c,&i,&c);flag=InsList(l, i, c);if(flag)printf(插入操作成功!n);elseprintf(插入操作失败!

32、n);p = l-next;while(p!=NULL)printf(%cn,p-data);p=p-next;实验十：两个单链表合并为一个单链表#include 延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表#include #include #define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int ElemType;typedef struct Node /*结点类型定义*/ ElemType data;struct Node * next;Node, *Li

33、nkList; /* LinkList为结构指针类型*/void CreateFromTail(LinkList L)Node *r, *s;char c;int flag =1;r=L;while(flag)scanf(%d,&c);if(c != -1)s=(Node*)malloc(sizeof(Node);s-data=c;r-next=s;r=s;elseflag=0;r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ LinkList MergeLinkList(LinkList LA, LinkList LB)Node *pa,*pb;Node

34、*r;LinkList LC;pa=LA-next;pb=LB-next;LC=LA;LC-next=NULL;r=LC;while(pa!=NULL & pb!=NULL)if(pa-data data)r-next=pa;r=pa;pa=pa-next;延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表elser-next=pb;r=pb;pb=pb-next;if(pa) /*若表LA未完，将表LA中后续元素链到新表LC表尾*/r-next=pa;else /*否则将表LB中后续元素链到新表LC表尾*/r-next=pb;free(LB)

35、;return(LC);void main()LinkList la,lb,lc;Node *p;la=(Node * )malloc(sizeof(Node);la-next=NULL;printf(请输入单链表A中的元素(以-1结束!):n);CreateFromTail(la);printf(单链表A中元素为:n);p = la-next;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);printf(请输入单链表B中的元素(以-1结束!):n);lb=(Node * )malloc(sizeof(Node); lb-next=NUL

36、L;CreateFromTail(lb); printf(单链表B中元素为:n);p = lb-next;while(p!=NULL)printf(%d ,p-data);p=p-next;printf(n);lc=MergeLinkList(la,lb);printf(单链表C中元素为:n);p = lc-next;while(p!=NULL)延安大学计算机学院实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表printf(%d ,p-data);p=p-next;实验十一：循环链表合并操作#include #include #include #define

37、OK 1#define ERROR 0#define TRUE 1#define FALSE 0typedef int ElemType;typedef struct Node /*结点类型定义*/ElemType data;struct Node * next;Node, *LinkList; /* LinkList为结构指针类型*/void create_clinklist(LinkList l)/*创建循环链表*/int num;Node *p;l-data=-1;l-next=l;printf(请输入循环链表的元素 (以-1结束):n);scanf(%d,&num);延安大学计算机学院

38、实验报告附页学号1060315014032姓名陈世龙班级计科15-1实验名称线性表while(num != -1)p=(Node*)malloc(sizeof(struct Node);p-data=num;p-next=l-next;l-next=p;scanf(%d,&num);LinkList merge_1(LinkList LA,LinkList LB)Node *p, *q;p=LA;q=LB;while (p-next!=LA)p=p-next;while (q-next!=LB)q=q-next;q-next=LA;p-next=LB-next;free(LB);return(

39、LA);void main()LinkList la,lb,lc;Node *p;printf(建立循环链表A，请输入数据!:n);la=(Node*)malloc(sizeof(struct Node);create_clinklist(la);p = la-next;while(p!=la)printf(%dn,p-data);p=p-next;printf(建立循环链表B，请输入数据!:n);lb=(Node*)malloc(sizeof(struct Node);create_clinklist(lb);p = lb-next;while(p!=lb)printf(%dn,p-data);p=p-next;lc=merge_1(la,lb);printf(合并后的循环链表为:n);p = lc-next;while(p!=lc)printf(%dn,p-data);p=p-next;延安大学计