线性表的顺序表示与链式表示

1、数据结构课程实验报告课程名称数据结构实验班级实验日期2014.4.2姓名学号实验成绩实验名称线性表的顺序表示与链式表示实验目的及要求【实验目的】1. 加深理解线性表的顺序表示与链式表示的意义和区别，掌握用它们表示时各基本操作的设计与实现。2. 学会定义线性表的顺序存储类型和链式存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。3. 掌握线性表的基本操作（初始化、建立、插入、删除、遍历等）。4. 掌握对多函数程序的输入、编辑、调试和运行过程。5. 进一步熟练C语言的使用，特别是指针和链表的使用。6. 能在实际应用背景下恰当选择顺序存储和链式存储。【实验要求】1. 预习C语言

2、中的结构的定义和基本操作方法2. 对线性表的每个基本操作用单独的函数实现3. 编写完整程序完成下面的实验内容并上机运行4. 整理并上交实验报告实验环境硬件平台：普通PC机软件平台：Windows操作系统编程环境：VC6.0实验内容1. 分别建立包含10个数据元素的顺序线性表和链式线性表； 2. 从键盘输入一个数据元素和插入位置k，将元素插入到线性表中第k（包含0号位置）个位置； 3. 从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；4. 能完成查找功能； 给出程序及插入、删除前和插入、删除后线性表结果。 算法描述及实验步骤/创建顺式线性表struct numb

3、er *creat(void)struct number *head,*p1;p1=head=(struct number*)malloc( SIZE * sizeof(struct number);scanf("%ld",&p1->num);for(;p1->num!=0;L+)p1+;scanf("%ld",&p1->num);return(head);/输出顺式线性表中的元素void print(struct number*head)struct number *p;int s=L;p=head;if(p!=0)p

4、rintf("n您输入的数据为：n");for(;s>0;p+,s-)printf("%ld ",p->num);/查找顺式线性表中的元素void search(struct number *head)struct number *p;long num1;int n=0,s=0;p=head;printf("n请输入您要查找的数据：n");scanf("%ld",& num1);if(head!=0)for(;p->num!=0;p+)n+;if(p->num=num1)s=1;br

5、eak;if(s=0)printf("n没有您所要查找的数据n");elseprintf("n找到您所需数据'%ld'在表中第%d个n",num1,n);/插入顺式线性表的元素struct number *insert(struct number*head)struct number *p1,*p2;int n=1;long num1;p1=p2=head;p2=p2+L-1;printf("n请输入您要插入的数据：n");scanf("%ld",&num1);if(num1<p2-&

6、gt;num)for(p1=head;p1->num<num1;p1+)n+;for(;p2>=p1;p2-)(p2+1)->num=p2->num;(p2+1)->num=num1;L+;return(head);/删除顺式线性表的元素struct number *del(struct number*head)struct number *p1,*p2;long num1;int n=1;p1=p2=head;printf("n请输入要删除的数据：n");scanf("%ld",&num1);p2=p2+L-

7、1;for(;p1->num!=num1 && n<=L;p1+)n=n+1;if(n>L)printf("n没有您要删除的数据n");return(0);elsefor(;p1<=p2;p1+)p1->num=(p1+1)->num;L-; return(head);struct list *creat_n()/创建有n个元素的链表 struct list *q,*p,*head=NULL; printf("n输入你所要创建的结点数: "); scanf("%d",&len

8、gth); head=p=(list*)malloc(sizeof(list); /创建一个新结点并用头指针指向它 printf("输入该结点的值: "); scanf("%d", &p->data); p->next=NULL; for(int i=length-1;i>=1;i-) q=p; p=(list*)malloc(sizeof(list); /创建新结点 printf("输入该结点的值: "); scanf("%d", &p->data); q->next

9、=p; printf("输入完毕nn"); p->next=NULL; return head; struct list * output()/输出表长与结点值函数 struct list *p; p=head; printf("n当前链表中存有的元素:n"); while(p!=NULL) printf("%dn",p->data); p=p->next; printf("当前的表长是: %dnn",length);/输出当前表长 return head;void insert()/插入结点函数

10、 struct list *k,*p,*q; int x; printf("请输入你要在哪个结点值之前插入新结点: "); scanf("%d",&x); k=(list*)malloc(sizeof(list);/创建新结点 printf("请输入新结点的值: "); scanf("%d",&k->data); k->next=NULL; if(head=NULL)/若链表为空,则直接入链表 head=k; length=length+1; printf("插入成功nn&qu

11、ot;); else if(head->data=x)/在第一个结点前插入新结点 k->next=head; head=k; printf("插入成功nn"); length=length+1; else q=head; p=head->next; while(p != NULL) && (p->data != x)/找出值为X的结点的位置 q = p; p = p->next; if (p = NULL) q->next=k;/在链表末插入新结点 printf("插入成功n"); length=len

12、gth+1; else if(p->data = x)/在要求的X结点前插入新结点 k->next=p; q->next=k; printf("插入成功nn"); length=length+1; output(); int delet()/删除结点函数 struct list *q,*p; int x,y; printf("请输入你所要删除的结点值: "); scanf("%d",&x); if(head=NULL)/表空 printf("表空n"); return 0 ; else i

13、f(x=head->data)/第一个结点为删除的结点 q=head; head=head->next; y=q->data; free(q); printf("删除成功nn"); length=length-1; output(); return(y); else q=head; p=head->next; while(p != NULL) && (p->data != x)/找出值为X的结点 q=p; p=p->next; if(p=NULL) printf("没有删除对象n"); if(x=p-&

14、gt;data)/删除值为X的结点 q->next=p->next; y=p->data; free(p); printf("删除成功nn"); length=length-1; output(); return (y); else printf("表中没有指定的结点n"); output(); return 0; return 0; void find() struct list *p; int k,x,i=1; char y,n; LOOP: p=head; printf("请输入你要查找的结点值: "); sc

15、anf("%d",&x); while(p->data!=x) p=p->next; i+; printf("你所查找的结点是表中第 %d 个结点!nn",i); printf("是否要继续查找,请输入y/nnn"); k=getch(); if(k='y') i=1; goto LOOP; else return;调试过程及实验结果总结 通过此次试验，我理解到线性表的顺序表示和链式表示方法实际存在相当明显的区别，顺序结构的表示方法建立在已存在的固定的空间区域内，数据超过最大存储空间就会溢出并丢失，

16、无法实现添加或删除操作，线性表可以随机存取表中任意一元素，但在插入或删除操作时需要移动大量元素，但表示方式精简、易操作；而链式结构的表示方法虽然不如顺序结构简单，却能动态分配存储空间，可以对数据进行添加、删除和修改等操作，功能更为强大，可以提高存储效率。此外，还熟练掌握了线性表的基本操作初始化、建立、插入、删除、遍历等。掌握了对多函数程序的输入、编辑、调试和运行过程，进一步熟练了指针和链表的使用。附录#include <stdio.h>#include <stdlib.h>#define SIZE 100int L=0;struct numberlong num;/创建

17、顺式线性表struct number *creat(void)struct number *head,*p1;p1=head=(struct number*)malloc( SIZE * sizeof(struct number);scanf("%ld",&p1->num);for(;p1->num!=0;L+)p1+;scanf("%ld",&p1->num);return(head);/输出顺式线性表中的元素void print(struct number*head)struct number *p;int s=L;

18、p=head;if(p!=0)printf("n您输入的数据为：n");for(;s>0;p+,s-)printf("%ld ",p->num);/查找顺式线性表中的元素void search(struct number *head)struct number *p;long num1;int n=0,s=0;p=head;printf("n请输入您要查找的数据：n");scanf("%ld",& num1);if(head!=0)for(;p->num!=0;p+)n+;if(p->

19、;num=num1)s=1;break;if(s=0)printf("n没有您所要查找的数据n");elseprintf("n找到您所需数据'%ld'在表中第%d个n",num1,n);/插入顺式线性表的元素struct number *insert(struct number*head)struct number *p1,*p2;int n=1;long num1;p1=p2=head;p2=p2+L-1;printf("n请输入您要插入的数据：n");scanf("%ld",&num1)

20、;if(num1<p2->num)for(p1=head;p1->num<num1;p1+)n+;for(;p2>=p1;p2-)(p2+1)->num=p2->num;(p2+1)->num=num1;L+;return(head);/删除顺式线性表的元素struct number *del(struct number*head)struct number *p1,*p2;long num1;int n=1;p1=p2=head;printf("n请输入要删除的数据：n");scanf("%ld",&am

21、p;num1);p2=p2+L-1;for(;p1->num!=num1 && n<=L;p1+)n=n+1;if(n>L)printf("n没有您要删除的数据n");return(0);elsefor(;p1<=p2;p1+)p1->num=(p1+1)->num;L-; return(head);void main()struct number *head,*head1,*head2;int a;/*head=creat(); print(head);*/printf("n*n");printf(&

22、quot; *n"); printf(" * 1 创建链表 *n"); printf(" * 2 插入节点 *n"); printf(" * 3 查找数据 *n"); printf(" * 4 删除结点 *n"); printf(" * 5 输出 *n"); printf(" * 0 退出 *n"); printf(" *n"); printf("*n");scanf("%d",&a);while(

23、a!=0)switch(a)case 1:printf("请创建顺序表:"); head=creat();break;case 2:head1=insert(head);break;case 3:search(head);break;case 4:head2=del(head);break; case 5:print(head);case 0:break;printf("n继续操作请输入，否则请按0退出：n");scanf("%d",&a);#include <stdio.h> #include <stdli

24、b.h>#include<conio.h> struct list /结点类型 int data; struct list *next; ; struct list *head;/声明结点指针int static length;/声明表长变量struct list *creat_n()/创建有n个元素的链表 struct list *q,*p,*head=NULL; printf("n输入你所要创建的结点数: "); scanf("%d",&length); head=p=(list*)malloc(sizeof(list);

25、/创建一个新结点并用头指针指向它 printf("输入该结点的值: "); scanf("%d", &p->data); p->next=NULL; for(int i=length-1;i>=1;i-) q=p; p=(list*)malloc(sizeof(list); /创建新结点 printf("输入该结点的值: "); scanf("%d", &p->data); q->next=p; printf("输入完毕nn"); p->nex

26、t=NULL; return head; struct list * output()/输出表长与结点值函数 struct list *p; p=head; printf("n当前链表中存有的元素:n"); while(p!=NULL) printf("%dn",p->data); p=p->next; printf("当前的表长是: %dnn",length);/输出当前表长 return head;void insert()/插入结点函数 struct list *k,*p,*q; int x; printf(&quo

27、t;请输入你要在哪个结点值之前插入新结点: "); scanf("%d",&x); k=(list*)malloc(sizeof(list);/创建新结点 printf("请输入新结点的值: "); scanf("%d",&k->data); k->next=NULL; if(head=NULL)/若链表为空,则直接入链表 head=k; length=length+1; printf("插入成功nn"); else if(head->data=x)/在第一个结点前插入新

28、结点 k->next=head; head=k; printf("插入成功nn"); length=length+1; else q=head; p=head->next; while(p != NULL) && (p->data != x)/找出值为X的结点的位置 q = p; p = p->next; if (p = NULL) q->next=k;/在链表末插入新结点 printf("插入成功n"); length=length+1; else if(p->data = x)/在要求的X结点前插入

29、新结点 k->next=p; q->next=k; printf("插入成功nn"); length=length+1; output(); int delet()/删除结点函数 struct list *q,*p; int x,y; printf("请输入你所要删除的结点值: "); scanf("%d",&x); if(head=NULL)/表空 printf("表空n"); return 0 ; else if(x=head->data)/第一个结点为删除的结点 q=head; head=head->next; y=q->data; free(q); printf("删除成功nn"); length=length-1; output(); return(y); else q=head; p=head->next; while(p != NULL) && (p->data != x)/找出值为X的结点 q=p; p=p->next; if(p=NULL) printf(&quo