实验报告课程名称数据结构实验项目实验一线性表的生成与操作题目一顺序表和链表的创建与基本操作系别___ _计算机学院 _ ______专业__ __计算机大类_ __班级/学号__(1406/2014011288)_____学生姓名 _______(孙文学)_________实验日期_(2015年10月19日)成绩_______________________指导教师黄改娟实验题目:实验一线性表的生成与操作------顺序表和链表的创建与基本操作(自己所选择实验题目,必填)一、实验目的1)掌握线性表的顺序存储和链式存储结构;2)验证顺序表及链表的基本操作的实现;(验证)3)理解算法与程序的关系,能够将算法转换为对应程序;4)体会线性表在实际应用中能够解决的问题。
(设计、综合)二、实验内容1)根据实验一题目列表,选定题目,说明题目的主要需求;2)结合所选定的题目,定义存储结构,并完成对应应用的线性表创建、插入、删除、查找等基本操作的算法描述;3)程序编码实现,并获得运行结果。
三、报告内容1)实验题目及主要存储结构定义(提示:请根据所选定题目,描述存储结构)题目:顺序表和链表的创建及基本操作顺序表我是采用数组存储的,链表是采用结构体存储的2)结合题目,说明对相应线性表的基本操作算法描述(提示:可用自然语言、流程图、伪代码等均可,要求对每一个操作,都给出具体的算法描述)基本操作:#顺序表#(1)插入:在线性表中的x位置插入y----将x位置及之后的元素都往后挪一位,将y的值赋给a[x].(2)删除:删除位置为x的元素----另y=a[x],然后x之后的元素都往前挪一位。
(3)查找:寻找值为y的元素----从a[0]开始,若a[i]==y,则返回i,否则i++。
#链表#(1)插入:当i小于要插入的位置x时,i++,插入p->data------p->next=s->next;s->next=p;(2)删除:当p->data不等于要删除的值x时,p=p->next;q=p->next;p->next=q->next;free(q);(3)查找:当p->data!=x时,p=p->next,找到之后返回p->data3)程序源码(提示:列出所编写程序的代码。
如果利用图形界面IDE等编程,这里只要求写出关键操作的程序代码。
此外,程序一定要有注释说明)1.顺序表的基本操作(用数组实现)#include<stdlib.h>#include<stdio.h>int main(){int N,i,j,e,x;printf("请输入线性表长度N:");scanf("%d",&N);a=(int *)malloc(N*sizeof(int));for(i=0;i<N;i++) //初始化a[i]=i;printf("初始顺序表为:");for(i=0;i<N;i++)printf("%d ",a[i]);printf("\n");printf("插入请输0,删除请输1,查找输入2:"); scanf("%d",&x);if(x==0){printf("请输入插入位置i和数e:");//插入scanf("%d%d",&i,&e);a=(int *)realloc(a,(N+1)*sizeof(int));for(j=N-1;j>=i-1;j--){a[j+1]=a[j];}a[i-1]=e;for(i=0;i<N+1;i++)printf("%d ",a[i]);printf("\n");}else if(x==1){ //删除printf("请输入删除位置i:");scanf("%d",&i);for(i;i<N;i++)a[i-1]=a[i];for(i=0;i<N-1;i++)printf("%d ",a[i]);printf("\n");}else if(x==2){ //查找printf("请输入查找位置i:");scanf("%d",&i);printf("%d\n",e);}else {printf("输入错误!");}free(a);a=NULL;return 0;}2.单链表的基本操作#include<stdio.h>#include<stdlib.h>#define ERROR 0#define OK 1typedef int status;typedef int ElemType;typedef struct Node{ElemType data;struct Node *next;} LNode,*LinkList;void Build(LinkList L)//建立一个带头结点的单链表{int n;LinkList p,q;p=L;printf("请输入n:\n");scanf("%d",&n);printf("请输入n个数据元素:\n");while(n--){q=(LinkList)malloc(sizeof(LNode));scanf("%d",&q->data);q->next=NULL;p->next=q;p=q;}void Print(LinkList L)//计算单链表的长度,然后输出单链表{int num=0;LinkList p;p=L->next;while(p){num++;printf("%d ",p->data);p=p->next;}printf("\n长度为%d\n",num);}void Tips(){printf("按数字键选择相应操作\n");printf("<1> 输出单链表及其长度:\n");printf("<2> 删除值为x的结点:\n");printf("<3> 在第n个位置插入值X:\n");printf("<4> 查找值为X的位置n:\n");printf("<0> 退出:\n");}void Delete(LinkList L,int x)//删除值为x的结点{LinkList p,q;p=L;while( p->next &&p->next->data!=x)p=p->next;if(p->next){q=p->next;p->next=q->next;free(q);printf("删除成功!!\n\n");Print(L);}printf("链表中没有%d\n\n",x);}void Insert(LinkList L,LinkList p,ElemType e)//在第n个位置插入值X {LinkList s;int i=1;s=L;while(i<e){s=s->next;i++;}p->next=s->next;s->next=p;Print(L);}/////查找值为X的位置nvoid find(LinkList L,int e){int n=1;LinkList p;p=L;while(p->next&&p->next->data!=e){p=p->next;n++;}if(p->next)printf("%d的位置是%d\n",e,n);elseprintf("不存在%d",e);}int main(){int op,x,n;LinkList L,p;L=(LinkList)malloc(sizeof(LNode));L->next=NULL;L->data=-1;Build(L);Tips();scanf("%d",&op);while(op){switch(op){case 1:Print(L);break;case 2:printf("请输入要查找的删除X:\n");scanf("%d",&x);Delete(L,x);break;case 3:printf("请输入要插入的元素X和插入的位置n:\n");scanf("%d",&x);scanf("%d",&n);p=(LinkList)malloc(sizeof(LNode));p->data=x;Insert(L,p,n);printf("插入成功\n\n");break;case 4:printf("请输入要查找的元素X:\n");scanf("%d",&x);find(L,x);}Tips();scanf("%d",&op);}return 0;}4)运行结果(提示:运行结果要求能反应每一种操作前后的结果变化情况)1.顺序表2.链表。