《数据结构》上机实验一

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

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

3、mber *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)printf(n您输入的数据为：n);for(;s0;p+,s-)printf(%ld

4、 ,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;break;if(s=0)printf(n没有您所要查找的数据n);elseprintf(n找到您所需数据%ld在表中第%d个n,num1,n);/插入顺式线性表的元素struct number *insert(struct

5、 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(num1num)for(p1=head;p1-num=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;

6、printf(n请输入要删除的数据：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n没有您要删除的数据n);return(0);elsefor(;p1num=(p1+1)-num;L-; return(head);struct list *creat_n()/创建有n个元素的链表 struct list *q,*p,*head=NULL; printf(n输入你所要创建的结点数: ); scanf(%d,&length); head=p=(list*)malloc(sizeof(list); /创建一个新结点并用头指针指

7、向它 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-next=NULL; return head; struct list * output()/输出表长与结点值函数 struct list *p; p=head; printf(n当前链表中存有的元素:n); whil

8、e(p!=NULL) printf(%dn,p-data); p=p-next; printf(当前的表长是: %dnn,length);/输出当前表长 return head;void insert()/插入结点函数 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)/若链表为空,则直接入链表 he

9、ad=k; length=length+1; printf(插入成功nn); 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=length+1; else if(p-data =

10、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 if(x=head-data)/第一个结点为删除的结点 q=head; head=head-next; y=q-data; free(q); printf(删除成功nn); le

11、ngth=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-data)/删除值为X的结点 q-next=p-next; y=p-data; free(p); printf(删除成功nn); length=length-1; output(); return (y); else printf(表中没有指定的结点n); output(); return

12、0; return 0; void find() struct list *p; int k,x,i=1; char y,n; LOOP: p=head; printf(请输入你要查找的结点值: ); scanf(%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;调试过程及实验结果程序运行过程中输入了顺序表，结果输出结果符合情况，程序成功。程序运行过程中输入

13、了链表，结果输出结果符合情况，程序成功。总结通过此次试验，我理解到线性表的顺序表示和链式表示方法实际存在相当明显的区别，顺序结构的表示方法建立在已存在的固定的空间区域内，数据超过最大存储空间就会溢出并丢失，无法实现添加或删除操作，线性表可以随机存取表中任意一元素，但在插入或删除操作时需要移动大量元素，但表示方式精简、易操作；而链式结构的表示方法虽然不如顺序结构简单，却能动态分配存储空间，可以对数据进行添加、删除和修改等操作，功能更为强大，可以提高存储效率。附录#include #include #define SIZE 100int L=0;struct numberlong num;/创建顺

14、式线性表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;p=head;if(p!=0)printf(n您输入的数据为：n);for(;s0;p+,

15、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;break;if(s=0)printf(n没有您所要查找的数据n);elseprintf(n找到您所需数据%ld在表中第%d个n,num1,n);/插入顺式线性表的元素struct number *

16、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(num1num)for(p1=head;p1-num=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=

17、1;p1=p2=head;printf(n请输入要删除的数据：n);scanf(%ld,&num1);p2=p2+L-1;for(;p1-num!=num1 & nL)printf(n没有您要删除的数据n);return(0);elsefor(;p1num=(p1+1)-num;L-; return(head);void main()struct number *head,*head1,*head2;int a;/*head=creat(); print(head);*/printf(n*n);printf( *n); printf( * 1 创建链表 *n); printf( * 2 插入节

18、点 *n); printf( * 3 查找数据 *n); printf( * 4 删除结点 *n); printf( * 5 输出 *n); printf( * 0 退出 *n); printf( *n); printf(*n);scanf(%d,&a);while(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);ca

19、se 0:break;printf(n继续操作请输入，否则请按0退出：n);scanf(%d,&a);#include #include #include 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*)ma

20、lloc(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=p; printf(输入完毕nn); p-next=NULL; return head; struct list * output()/输出表长与结点值函数 struct list *p; p

21、=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(请输入你要在哪个结点值之前插入新结点: ); scanf(%d,&x); k=(list*)malloc(sizeof(list);/创建新结点 printf(请输入新结点的值: ); scanf(%d,&k-data); k-next=N

22、ULL; if(head=NULL)/若链表为空,则直接入链表 head=k; length=length+1; printf(插入成功nn); 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);

23、length=length+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 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-nex