实验报告专用纸.docx

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

4、 int i=0; /*i为扫描计数器，初值为0，即从第一个元素开始比较*/ while (i=L.last)&(L.elemi!=e)i+; if (i=L.last) return(i+1); /*若找到值为e的元素，则返回其序号*/ else return(-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.e

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

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

7、AXSIZE-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(请输入线性表的各元素

8、值:n); for(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); 延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表实验三：线性表中删除元素操作#include #include #include #define OK 1#define ERROR 0#define TRUE 1#defi

9、ne FALSE 0#define ElemType int#define MAXSIZE 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; /*

10、 将删除的元素存放到e所指向的变量中*/ for(k=i; ilast; k+)延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科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;

11、printf(请输入线性表的各元素值: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延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表#define ERROR 0#define TRUE 1#define FALSE 0#define ElemType int#define M

12、AXSIZE 100 /*此处的宏定义常量表示线性表可能达到的最大长度*/typedef struct ElemType elemMAXSIZE; /*线性表占用的数组空间*/ int last; /*记录线性表中最后一个元素在数组elem 中的位置（下标值），空表置为-1*/SeqList;void merge(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+; else LC-elemk=

13、LB-elemj; j+; k+; while(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

14、,&r); la-last = r-1; printf(请输入线性表A的各元素值:n);延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科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(siz

15、eof(SeqList); merge(la,lb,lc); printf(合并后线性表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 延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表#define ElemType chartypedef struct Node /*结点类型定义*/ ElemTyp

16、e data; struct Node * next;Node, *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); /*建

17、立新结点s*/ s-data=c; s-next=L-next;/*将s结点插入表头*/ L-next=s; else flag=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;延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表实验六：用尾插法建立单链表#include #include #include

18、 #define OK 1#define ERROR 0#define TRUE 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(LinkL

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

20、最后一个结点的next链域置为空，表示链表的结束*/ 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; 实验七：查找线性表结点值#include #include #include #define OK 1延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表#define ERROR 0#defin

21、e TRUE 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 fl

22、ag =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; else flag=0; r-next=NULL; /*将最后一个结点的next链域置为空，表示链表的结束*/ Node * Get (LinkList L, int i) int j; Node *p;

23、p=L; j=0; /*从头结点开始扫描*/ while (p-next!=NULL)&(jnext; /* 扫描下一结点*/ j+; /* 已扫描结点计数器 */ if(i = j)延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科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-n

24、ext; while(p!=NULL) printf(%cn,p-data); p=p-next; printf(请输入要查找的结点序号:n); scanf(%d,&j); p = Get(l,j); if(p!=NULL) printf(该结点的值为:%cn,p-data); else printf(未找到此结点!n);实验八：判断线性表长度#include #include #include 延安大学计算机学院实验报告附页学号12姓名陈世龙班级计科15-1实验名称线性表#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0typed

25、ef 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; /*设置一个标志，初值为1，当输入$时，flag为0，建表结束*/ r=L; /*r指针动态指向链表的当前表尾，以便于做尾插入，其初值指向头结点*/ while(flag) /*循环输入表中元素值，将建立新结点s插入表尾*/ c=getchar(); if(c!=$)