数据结构与算法实验线性表

1、沈阳工程学院学生实验报告（课程名称：数据结构与算法 ）实验题目：线性表班级网本112班学号 2011414217姓名樊鹏鹏地点 F606 指导教师实验日期:2012 年 9 月27 日一、实验目的1了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结 构。2掌握线性表的顺序存储结构的定义及其 C语言的实现。3 掌握线性表的链式存储结构一一单链表的定义及其C语言的实现。4 掌握线性表的基本操作二、实验环境Turbo C 或是 Visual C+三、实验内容与要求实验1顺序表的操作请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据 建立一个线性表，并输出该线性表；然后根据屏幕菜

2、单的选择，可以进行表 的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕 菜单中选择0,即可结束程序的运行。分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性 表的第i个元素之后的所有元素一次后移一个位置， 以便腾出一个位置，再把 新元素插入到该位置。当要删除第i个元素时，也只需将第i个元素之后的所 有元素前移一个位置。算法描述：对每个算法，都要写出算法的中文描述。本实验中要求分别 写出在第i个（从1开始计数）结点前插入数据为x的结点、删除指定结点、 创建一个线性表。打印线性表等的算法描述。实验2单链表的操作请编制C程序，利用链式存储方式来实现线性表的创建、插入、

3、删除和 查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表；然后 根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后， 再输出单链表；最后在屏幕菜单中选择 0,即可结束程序的运行。算法描述：本实验要求分别写出在单链表中第 i （从1开始计数）个位置 之后插入元素、创建单链表、在单链表中删除第i个位置的元素、顺序输出单 链表的内容等的算法描述。四、实验过程及结果分析顺序表：#i nclude <stdio.h>#i nclude <stdlib.h>#define SIZE 100int L=0;struct nu mberlong num;/*

4、 创建顺式线性表*/struct nu mber *creat(void)struct nu mber *head,*p1;p1=head=(struct nu mber*)malloc( SIZE * sizeof(struct nu mber); sca nf("%ld",&p1-> nu m);for(;p1- >num !=0;L+)p1+;scan f("%ld",&p1-> nu m);return(head);/* 输出顺式线性表中的元素*/void prin t(struct nu mber*head)s

5、truct nu mber *p;int s=L;p=head;if(p!=O)prin tf("n您输入的数据为：n");for(;s>0;p+,s-)printf("%ld ",p->num);/* 查找顺式线性表中的元素*/void search(struct nu mber *head)struct nu mber *p;long nu m1;int n=0,s=0;p=head;prin tf("n请输入您要查找的数据：n");sca nf("%ld",& num1);if(head!

6、=0)for(;p->nu m!=0;p+)n+;if(p->num=nu m1)s=1;break;if(s=0)printf("n没有您所要查找的数据n");elseprintf("n找到您所需数据ld'在表中第<个n",num1,n);/* 插入顺式线性表的元素 */struct nu mber *in sert(struct nu mber*head)struct nu mber *p1,*p2;int n=1;long nu ml;p1=p2=head;p2=p2+L-1;prin tf("n请输入您要插入的

7、数据：n");sca nf("%ld",&nu m1);if(nu m1<p2->num)for(p1=head;p1- >num<nu m1;p1+)n+;for(;p2>=p1;p2-)(p2+1)-> num=p2->num;(p2+1)->num=nu m1;L+;return(head);/* 删除顺式线性表的元素 */struct nu mber *del(struct nu mber*head)struct nu mber *p1,*p2;long nu m1;int n=1;p1=p2=hea

8、d;prin tf("n请输入要删除的数据： n");sea nf("%ld",&nu ml); p2=p2+L-1;for(;p1- >num!=num1 && n<=L;p1+)n=n+1;if(n >L)printf("n没有您要删除的数据n");return(O);elsefor(;p1<=p2;p1+)p1- >num=(p1+1)->num;L-; return(head);void mai n()struct nu mber *head,*head1,*head

9、2; int a;/*head=creat(); prin t(head);*/*prin tf("nprintf("printf("printf("printf("printf("printf("*n");按1:创建n");按2：插入n");按3:查找n");按4:删除n");按5:输出n");按0:退出n");prin tf("*n")；sea nf("%d",&a);while(a!=O)switch(

10、a)case 1:printf("请创建顺序表:");head=creat();break;case 2:head1= in sert(head);break;case 3:search(head);break;case 4:head2=del(head);break;case 5:pri nt(head);case 0:break;printf("n继续操作请输入，否则请按 0退出：n");scan f("%d",&a);n “ w 1 a 3 4 5 n请刨建J帧序表r 23456?fl0缠绫操作i青输入否则谙按0退岀：请

11、输入您娈插入的数据；继缴操彳乍请输入，否则请按退岀.3请输入您裝 查找的数扌居图1继緘操作请输入.否则请按越岀,情输入要删除的数据：継续操作请输入，否则请按砸出: S您输入的数据为；1234678?继续操作请输入'否则请按刊退岀:图2链表：#i nclude "stdio.h"#i nclude "malloc.h"typedef struct nodeint data;struct node *n ext;LNode,*Li nkList;int len;/* 创建链式线性表*/Lin kList CreatLi nk()int x,co un

12、 t=0;Lin kList p,q,h;h=NULL;p=(Li nkList)malloc(sizeof(LNode);sca nf("%d", &x);p->data=x;p-> next=NULL;while(x!=0)coun t+;if(co un t=1)q=h=p;elseq->n ext=p;q=p；p=(Li nkList)malloc(sizeof(LNode);scan f("%d", &x);p->data=x;p->n ext=NULL;return h;/* 删除链式线性表的元素

13、 */LinkList del(LinkList h,int data)Li nkList p1,p2;if(h=NULL)prin tf("n list n ull!n");return h;p仁h;while(data!=p1->data&&p1-> next!=NULL)p2=p1;p仁p1- >n ext;if(data=p1->data)if(p1=h)h=p1- >n ext;else p2->n ext=p1- >n ext;prin tf("delete:%ldn",data);l

14、en=le n-1;else prin tf("%ld not bee n foun d!n",data); return(h);/* 输出链式线性表的元素*/void Prin tLi nk(LNode *h)LNode *p;p=h;while(p!=NULL)prin tf("%d ",p->data);p=p->n ext;/* 计算链式线性表的长度*/int Lin kLe n(Lin kList h)Lin kList p=h;int coun t=0;while(p!=NULL)coun t+;p=p->n ext;ret

15、ur n count;/* 查找链式线性表中的元素*/Lin kList QueryL in k(L in kList h,i nt x)Lin kList q,p;q=P=h;while(p!=NULL)if(p->data=x)break;elseq=p;p=p->n ext;if(p!=NULL)return q;elsereturn NULL;/* 向链式线性表插入元素*/Lin kList In sertL in k(L in kList h,i nt i,i nt x)Lin kList p,q;int j;p=(Li nkList)malloc(sizeof(LNod

16、e); p->data=x;if(i=0)p->n ext=h;h=p；elseq=h;j=1；while(q!=NULL && j<i)j+；q=q->n ext;if(q!=NULL)p->n ext=q->n ext;q->n ext=p;elseprin tf(" no found'n ”)；return h;void main()Lin kList h,p;int x,a;printf("请按菜单进行操作!nprin tf("*n")printf("按1 :创建链表n&

17、quot;);printf("按2 :插入兀素n");printf("按3 :链表长度n");printf("按4 :查找元素n");printf("按5 :删除元素n");printf("按6 :输出链表n");printf("按0 :退出运行n");prin tf("*n")printf("请选择操作:")；sca nf("%d",&a);while(a!=0)switch(a)case 1:printf

18、("请输入:");h=CreatLink(); printf(”创建链表成功!")； break;case 2:pri ntf("请输入要插入的元素：");sca nf("%d", &x);h=ln sertL in k(h,1,x); break;case3:len=LinkLen(h);printf("该链表的长度为:%d",le n);break;case 4:printf(" 请输入要查找的元素:");scanf("%d",&x); p=QueryL in k(h,x);if(p!=NULL)prin tf("fi nd=%dn ",p->n ext->data);elseprin tf(" no found'n ”)； break;case 5: printf("n请输入要删除的元素:");scan f("%d", &x);if(x!=O)h=del(h,x);break;case 6: printf("输出