课程实验报告1线性表

1、 课 程 实 验 报 告 专 业 年 级 2012级软件工程 课 程 名 称 数据结构C语言描述 指 导 教 师 申红婷 学 生 姓 名 王晓霞 学 号 20122205041002 实 验 日 期 2012.10.31 实 验 地 点 A3笃行楼A栋306 实 验 成 绩 教务处制 2013年10月31日实验项目名称线性表实验实验目的及要求一目的： 1使学生对线性表的顺序存储结构、基本操作和应用，能通过实验达到掌握和应用的目的。 2.使学生对线性表的线性表的链式结构、基本操作和应用，能通过实验达到掌握和应用的目的。二要求： 实验前认真预习实验内容。实验时自觉遵守课堂纪律，严格按操作规程操作，

2、既要独立操作又要与其他同学配合，在实验过程中必须按照实验内容认真做完实验，并认真填写相关实验报告。实验内容线性表的顺序存储结构和线性表的链式结构、基本操和应用。实验步骤1、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1#define INIT_SIZE 5 /*初始分配的顺序表长度*/#define INCREM 5 /*溢出时，顺序表长度的增量*/typedef int ElemType; /*定义表元素的类型*/typedef

3、 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); /*输出

4、顺序表的元素*/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

5、_sq(Sqlist *L,int n) ElemType e; int i; for(i=0;i<n;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;i<=L->length;i+) printf("%5d",L->

6、slisti-1); return OK;/*PrintList*/int ListInsert_sq(Sqlist *L,int i,ElemType e) int k;if(i<1|i>L->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

7、; 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(i<1|i>L->length) return 0;for(int j;j<L->length;j+) L->slistj-1=L->slistj;

8、 L->length-; return 1; /*在顺序表中查找指定值元素，返回其序号*/int ListLocate(Sqlist *L,ElemType e) for(int i=1; i<=L->length;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(n>0) printf("n1

9、-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-Prin

10、t 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); Lis

11、tLocate(&sl,m);printf("n5-Print Sqlistn"); PrintList_sq(&sl);printf("n"); else printf("ERROR"); return 0;l 运行结果l 算法分析 首先应该选择顺序表的动态存储方式进行顺序表结构的定义，然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令，接着编写各种操作函数的函数体，而在主函数中要首先调用InitList_sq(&sl)函数初始化，然后调用InitList_sq()创建顺序表，调用PrintList_

12、sq()函数输出该顺序表中元素的值；然后调用ListInsert_sq()函数，进行插入操作，并输出插入新元素后的状态。2、为第1题补充删除和查找功能函数，并在主函数中补充代码验证算法的正确性。删除算法代码：int ListDelete_sq(Sqlist *L,int i)if (L->length=0) return 0;if(i<1|i>L->length) return 0;for(int j=i;j<L->length;j+) L->slistj-1=L->slistj; L->length-; return 1; l 运行结果l

13、 算法分析 当在主函数里面调用删除功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把顺序表和序号i传值进去时，程序可以先判断所传值是否满足条件，若满足，则开始从顺序表第一个元素开始依次遍历，直到找到第i个位置的元素，并将其删除，后面的元素依次前移，填补。而表的长度则减一，删除成功。若不满足，则返回0，表示删除失败。查找算法代码： int ListLocate(Sqlist *L,ElemType e) for(int i=1; i<=L->length;i+)if(L->slisti-1=e) return i; return 0;

14、l 运行结果l 算法分析 当在主函数里面调用查找功能函数并传参数进去时，程序将自动跳到函数体里面，利用所传参数一步步执行，在该函数里面，当把顺序表和要查找的值e传值进去时，程序开始从顺序表第一个元素开始依次遍历，直到找到值为e的元素，并返回其位置序号，查找成功。若遍历了顺序表所有元素依然没有符合条件的e的值，则返回0，表示查找失败。3、阅读下面程序，在横线处填写函数的基本功能。并运行程序，写出结果。#include<stdio.h>#include<malloc.h>#define ERROR 0#define OK 1typedef int ElemType; /*定

15、义表元素的类型*/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;

16、 head=(LinkList)malloc(sizeof(LNode); head->next=NULL; p=head; for(i=0;i<n;i+) q=(LinkList)malloc(sizeof(LNode); printf("input data %i:",i+1); scanf("%d",&q->data); /*输入元素值*/ q->next=NULL; /*结点指针域置空*/ p->next=q; /*新结点连在表末尾*/ p=q; return head;/*CreateList*/void

17、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&&j<i) p=p->next;j+; if(!p|j>i) return ERROR; *e=p->data;

18、return OK;/*GetElem*/int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L->next; while(p&&j<i-1) p=p->next;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) LN

19、ode *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(n>0) p

20、rintf("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("no

21、t 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 LinkLis

22、t:n");/*调用删除函数*/ printf("input e="); scanf("%d",&e); /*输入欲删除元素的值*/ DeleteList(L,e); PrintList(L); /*输出调用后的结果*/printf("n"); else printf("ERROR"); return 0;l 运行结果l 算法分析 首先应该进行单链表结构的定义，然后在程序的开头进行顺序表各种操作函数的声明以及预定义命令，接着编写各种操作函数的函数体，而在主函数中要首先调用LinkList Crea

23、teList(int n)创建带头结点的单链表，输入结点数，然后依次输入各个结点的值。接着调用打印单链表功能函数输出单链表中的值。再调用查找功能函数，输入查找元素的位置，输出对应元素的值。然后调用插入功能函数，输入要插入的位置和元素，打印输出插入后的新链表。同理调用删除功能函数，输入要删除的元素值，最后打印输出删除后的单链表。 4、为第3题补充插入功能函数和删除功能函数。并在主函数中补充代码验证算法的正确性。插入算法代码：int InsertList(LinkList L,int i,ElemType e) int j=1; LNode *p,*q; p=L->next; while(p

24、&&j<i-1) p=p->next;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->nex