课程实验报告1线性表

课 程 实 验 报 告 专 业 年 级 2012级软件工程 课 程 名 称 数据结构C语言描述 指 导 教 师 申红婷 学 生 姓 名 王晓霞 学 号 20122205041002 实 验 日 期 2012.10.31 实 验 地 点 A3笃行楼A栋306 实 验 成 绩 教务处制 2013年10月31日实验项目名称线性表实验实验目的及要求一目的： 1使学生对线性表的顺序存储结构、基本操作和应用，能通过实验达到掌握和应用的目的。 2.使学生对线性表的线性表的链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。二要求： 实验前认真预习实验内容。实验时自觉遵守课堂纪律，严格按操作规程操作，既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。实验内容线性表的顺序存储结构和线性表的链式结构、基本操和应用。实验步骤1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include#include#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的顺序表长度*/#define INCREM 5 /*溢出时，顺序表长度的增量*/typedef int ElemType; /*定义表元素的类型*/typedef struct SqlistElemType *slist; /*存储空间的基地址*/int length; /*顺序表的当前长度*/int listsize; /*当前分配的存储空间*/Sqlist;int InitList_sq(Sqlist *L); /* 初始化顺序表，为其分配存储空间 */int CreateList_sq(Sqlist *L,int n); /* 创建一个顺序表 */int ListInsert_sq(Sqlist *L,int i,ElemType e);/* 将新元素e插入到顺序表第i个位置 */int PrintList_sq(Sqlist *L); /*输出顺序表的元素*/int ListDelete_sq(Sqlist *L,int i); /*删除第i个元素*/int ListLocate(Sqlist *L,ElemType e); /*查找值为e的元素*/int InitList_sq(Sqlist *L) L-slist=(ElemType*)malloc(INIT_SIZE*sizeof(ElemType); if(!L-slist) return ERROR; L-length=0; L-listsize=INIT_SIZE; return OK; /*InitList*/int CreateList_sq(Sqlist *L,int n) ElemType e; int i; for(i=0;in;i+) printf(input data %d,i+1); scanf(%d,&e); if(!ListInsert_sq(L,i+1,e) return ERROR; return OK;/*CreateList*/*输出顺序表中的元素*/int PrintList_sq(Sqlist *L) int i; for(i=1;ilength;i+) printf(%5d,L-slisti-1); return OK;/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int k;if(iL-length+1) return ERROR; if(L-length=L-listsize) L-slist=(ElemType*)realloc(L-slist,(INIT_SIZE+INCREM)*sizeof(ElemType); if(!L-slist) return ERROR; L-listsize+=INCREM; for(k=L-length-1;k=i-1;k-) L-slistk+1= L-slistk; L-slisti-1=e; L-length+; return OK;/*ListInsert*/*在顺序表中删除第i个元素*/int ListDelete_sq(Sqlist *L,int i)if (L-length=0) return 0;if(iL-length) return 0;for(int j;jlength;j+) L-slistj-1=L-slistj; L-length-; return 1; /*在顺序表中查找指定值元素，返回其序号*/int ListLocate(Sqlist *L,ElemType e) for(int i=1; ilength;i+)if(L-slisti-1=e) return i;return 0;int main() Sqlist sl; int n,m,k; printf(please input n:); /*输入顺序表的元素个数*/ scanf(%d,&n); if(n0) printf(n1-Create Sqlist:n); InitList_sq(&sl); CreateList_sq(&sl,n); printf(n2-Print Sqlist:n); PrintList_sq(&sl); printf(nplease input insert location and data:(location,data)n); scanf(%d,%d,&m,&k); ListInsert_sq(&sl,m,k); printf(n3-Print Sqlist:n); PrintList_sq(&sl); printf(nplease input delete location: locationn); scanf(%d,&m); ListDelete_sq(&sl,m); printf(n4-Print Sqlistn); PrintList_sq(&sl); printf(nplease input data datan); scanf(%d,&m); ListLocate(&sl,m);printf(n5-Print Sqlistn); PrintList_sq(&sl);printf(n); else printf(ERROR); return 0;l 运行结果l 算法分析 首先应该选择顺序表的动态存储方式进行顺序表结构的定义，然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令，接着编写各种操作函数的函数体，而在主函数中要首先调用InitList_sq(&sl)函数初始化，然后调用InitList_sq()创建顺序表，调用PrintList_sq()函数输出该顺序表中元素的值；然后调用ListInsert_sq()函数，进行插入操作，并输出插入新元素后的状态。2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：int ListDelete_sq(Sqlist *L,int i)if (L-length=0) return 0;if(iL-length) return 0;for(int j=i;jlength;j+) L-slistj-1=L-slistj; L-length-; return 1; l 运行结果l 算法分析 当在主函数里面调用删除功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把顺序表和序号i传值进去时，程序可以先判断所传值是否满足条件，若满足，则开始从顺序表第一个元素开始依次遍历，直到找到第i个位置的元素，并将其删除，后面的元素依次前移，填补。而表的长度则减一，删除成功。若不满足，则返回0，表示删除失败。查找算法代码： int ListLocate(Sqlist *L,ElemType e) for(int i=1; ilength;i+)if(L-slisti-1=e) return i; return 0; l 运行结果l 算法分析 当在主函数里面调用查找功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把顺序表和要查找的值e传值进去时，程序开始从顺序表第一个元素开始依次遍历，直到找到值为e的元素，并返回其位置序号，查找成功。若遍历了顺序表所有元素依然没有符合条件的e的值，则返回0，表示查找失败。3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include#include#define ERROR 0#define OK 1typedef int ElemType; /*定义表元素的类型*/typedef struct LNode /*线性表的单链表存储*/ ElemType data; struct LNode *next;LNode,*LinkList;LinkList CreateList(int n); /* 建立带表头节点的单链表 */void PrintList(LinkList L); /*输出带头结点单链表的所有元素*/int GetElem(LinkList L,int i,ElemType *e); /* 在单链表中查找第i个节点的值 */LinkList CreateList(int n) LNode *p,*q,*head; int i; head=(LinkList)malloc(sizeof(LNode); head-next=NULL; p=head; for(i=0;idata); /*输入元素值*/ q-next=NULL; /*结点指针域置空*/ p-next=q; /*新结点连在表末尾*/ p=q; return head;/*CreateList*/void PrintList(LinkList L) LNode *p; p=L-next; /*p指向单链表的第1个元素*/ while(p!=NULL) printf(%5d,p-data); p=p-next; /*PrintList*/int GetElem(LinkList L,int i,ElemType *e) LNode *p;int j=1; p=L-next; while(p&jnext;j+; if(!p|ji) return ERROR; *e=p-data; return OK;/*GetElem*/int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L-next; while(p&jnext;j+; if(!p) return ERROR; q=(LNode *)malloc(sizeof(LNode); q-data=e; q-next=p-next; p-next=q; return OK;int DeleteList(LinkList L,ElemType e) LNode *p,*q; p=L-next; while(p&p-data!=e) q=p;p=p-next; if(!p) return ERROR; else q-next=p-next;free(p); return OK; int main() int n,i;ElemType e; LinkList L=NULL; /*定义指向单链表的指针*/ printf(please input n:); /*输入单链表的元素个数*/ scanf(%d,&n); if(n0) printf(n1-Create LinkList:n); L=CreateList(n); printf(n2-Print LinkList:n); PrintList(L); printf(n3-GetElem from LinkList:n); printf(input i=); scanf(%d,&i); if(GetElem(L,i,&e) printf(No%i is %d,i,e); else printf(not exists);printf(n4-Insert from LinkList:n); /*调用插入函数*/ printf(input i=); scanf(%d,&i); /*指定插入位置*/ printf(input e=); scanf(%d,&e); /*输入欲插入元素的值*/ InsertList(L,i,e); PrintList(L); /*输出调用后的结果*/ printf(n5-Delete from LinkList:n);/*调用删除函数*/ printf(input e=); scanf(%d,&e); /*输入欲删除元素的值*/ DeleteList(L,e); PrintList(L); /*输出调用后的结果*/printf(n); else printf(ERROR); return 0;l 运行结果l 算法分析 首先应该进行单链表结构的定义，然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令，接着编写各种操作函数的函数体，而在主函数中要首先调用LinkList CreateList(int n)创建带头结点的单链表，输入结点数，然后依次输入各个结点的值。接着调用打印单链表功能函数输出单链表中的值。再调用查找功能函数，输入查找元素的位置，输出对应元素的值。然后调用插入功能函数，输入要插入的位置和元素，打印输出插入后的新链表。同理调用删除功能函数，输入要删除的元素值，最后打印输出删除后的单链表。 4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。插入算法代码：int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L-next; while(p&jnext;j+; if(!p) return ERROR; q=(LNode *)malloc(sizeof(LNode); q-data=e; q-next=p-next; p-next=q; return OK;l 运行结果l 算法分析当在主函数里面调用查找功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把单链表，要插入的位置序号和元素内容传值进去时，程序开始从单链表第一个元素开始依次遍历，直到找到插入位置的前一个节点，用指针p指向它。然后创建一个以e为值的新节点指针q，修改节点*q的next域指向节点*p的下一个节点，再将节点*p的next域修改为指向新节点*s。返回ok，表示插入成功。最后打印输出插入后的新链表。删除算法代码：int DeleteList(LinkList L,ElemType e) LNode *p,*q; p=L-next; while(p&p-data!=e) q=p;p=p-next; if(!p) return ERROR; else q-next=p-next;free(p); return OK; l 运行结果l 算法分析当在主函数里面调用删除功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把单链表，要删除的元素内容传值进去时，程序开始从单链表第一个元素开始依次遍历，直到找到删除位置的前一个节点，用指针p指向它。指针q指向要删除的节点。然后修改指针p的next域为指向待删除节点*q的后继节点。返回ok，表示删除成功。最后打印输出删除后的新链表。实验环境（一）运行环境说明PC计算机，Windows 2000(或Windows XP) 及以上版本，C（二）基础数据设置及说明计算机，Windows 2000(或Windows XP) 及以上版本，C均能正常运行。实验结果与分析 通过这次实验，我学会了线性表的定义和逻辑结构的特性，以及它的顺序和链式存储表示的结构定义和相应的操作的实现。而且有了自己亲自在顺序表和单链表的各种算法设计，让我体会到了顺序表和单链表各自所具有的优缺点，这使得我明白了应该在什么情况下去使用顺序表和单链表。同时，在此次实验的完成过程中，我已经掌握了顺序表和单链表的结构定义方式和在这些线性表上的基本操作，以及应该如何在主函数中调用并实现它们。然而在实验过程中，我也毫无疑问地遇到了许多的问题，但是通过我及时的查阅资料，请教老师同学，我最终攻克了这些问题，例如，在刚开始我不懂得如何去用结构定义顺序表和单链表，还有一些操作无法用代码实现以及在传参过程中的疏漏。这些困难使得我的理论知识更加扎实，从而更能灵活的操作它并将其运用的实际操作中去。总而言之，此次关于线性表的实验让我学到了很多。教师评语注：可根据实际情况加页