数据结构与算法实验报告-线性表.doc

沈 阳 工 程 学 院学 生 实 验 报 告（课程名称： 数据结构与算法 ）实验题目： 线性表 班 级 学 号 姓 名 地 点 指导教师 实 验 日 期 : 年 月 日一、实验目的1 了解线性表的逻辑结构特性，以及这种特性在计算机内的两种存储结构。2 掌握线性表的顺序存储结构的定义及其C语言的实现。3 掌握线性表的链式存储结构单链表的定义及其C语言的实现。4 掌握线性表的基本操作二、实验环境Turbo C或是Visual C+三、实验内容与要求实验1 顺序表的操作请编制C程序，利用顺序存储方式来实现下列功能：根据键盘输入数据建立一个线性表，并输出该线性表；然后根据屏幕菜单的选择，可以进行表的创建，数据的插入删除并在插入和删除数据后再输出线性表；最后在屏幕菜单中选择0，即可结束程序的运行。分析：当我们要在顺序表的第i个位置上插入一个元素时，必须先将线性表的第i个元素之后的所有元素一次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。当要删除第i个元素时，也只需将第i个元素之后的所有元素前移一个位置。算法描述：对每个算法，都要写出算法的中文描述。本实验中要求分别写出在第i个（从1开始计数）结点前插入数据为x的结点、删除指定结点、创建一个线性表。打印线性表等的算法描述。实验2 单链表的操作请编制C程序，利用链式存储方式来实现线性表的创建、插入、删除和查找等操作。具体地说，就是要根据键盘输入的数据建立一个单链表；然后根据屏幕菜单的选择，可以进行数据的插入或删除，并在插入或删除数据后，再输出单链表；最后在屏幕菜单中选择0，即可结束程序的运行。算法描述：本实验要求分别写出在单链表中第i（从1开始计数）个位置之后插入元素、创建单链表、在单链表中删除第i个位置的元素、顺序输出单链表的内容等的算法描述。四、实验过程及结果分析实验1 顺序表的操作#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2#include#include#define ML 1/线性表#define TURE 1#define FALSE 0#define OK 1#define ERR 0typedef struct int listML;int size;int MAXSIZE;sqList;sqList *Init_List(sqList *L,int ms);void Disp_List(sqList *L);int LocateElem_List(sqList *L,int x);int Insert_List(sqList *L,int x,int mark);int Delete_List1(sqList *L,int item);int Delete_List2(sqList *L,int mark);sqList *Init_List(sqList *L,int ms)L=(sqList *)malloc(ms*sizeof(sqList);if(!L)printf(Memory allocation failuren);exit(OVERFLOW);elseL-size=0; L-MAXSIZE=ms;return L;void Disp_List(sqList *L)int i;for(i=0;isize;i+)printf(%d,L-listi);printf(n);int LocateElem_List(sqList *L,int x)int i=0;for(i=0;isize;i+)if(L-listi=x)return i;if(iL-size) return -1;int Insert_List(sqList *L,int x,int mark)int i=1;if(L-size=L-MAXSIZE)return -1;if(mark0)for(i=L-size+1;i=mark;i-)L-listi+1=L-listi; L-listi=x;else if(marklistL-size=x; L-size+;return FALSE;int Delete_List1(sqList *L,int item)int i,j;for(i=0;isize;i+)if(item=L-listi)break;if(isize)for(j=i+1;jsize-1;j+)L-listj=L-listj+1;L-size-;return i;return FALSE;int Delete_List2(sqList *L,int mark)int i,item;if(mark0)item=L-listmark;for(i=mark+1;isize-1;i+)L-listi=L-listi+1;L-size-;return i;return FALSE;void main()int p,n,x=0; sqList a,*b;b=Init_List(&a,ML);printf(listaddr=%dtsize=%dtMaxSize=%d,b-list,b-size,b-MAXSIZE);while(1)printf(n请输入值，0为结束输入：);scanf(%d,&x);if(!x) break;printf(请输入插入位置：);scanf(%d,&p);Insert_List(b,x,p);printf(线性表为：n); Disp_List(b);while(1)printf(请输入查找值，输入0结束查找操作：);scanf(%d,&x);if(!x) break;n=LocateElem_List(b,x);if(n0) printf(没找到n);elseprintf(又符合条件的值，位置为：%dn,n+1);while(1)printf(请输入删除值，输入0结束查找操作：);scanf(%d,&x);if(!x) break;n=Delete_List1(b,x);if(n0)printf(没找到n);elseprintf(删除成功，线性表为:);Disp_List(b);while(1)printf(请输入删除值位置，输入o结束查找操作:);scanf(%d,&p);if(!p) break;n=Delete_List2(b,p);if(p0) printf(位置越界n);elseprintf(线性表为:);Disp_List(b);实验2 单链表的操作#include #include #define null 0typedef int ElemType; /* 字符型数据*/struct LNodeElemType data;struct LNode *next;void setnull(struct LNode *p);int length (struct LNode *p);ElemType get(struct LNode *p,int i);void insert(struct LNode *p,ElemType x,int i);void dele(struct LNode *p,int i);void display(struct LNode *p);int locate(struct LNode *p,ElemType x);void main()struct LNode *head,*q; /*定义静态变量*/int select,x1,x2,x3,x4;int i,n; int m,g;char e,y; setnull(&head); /*建设链表并设置为空表*/ printf(请输入数据长度: ); scanf(%d,&n); for(i=1;inext; return(n);ElemType get(struct LNode *p,int i)int j=1;struct LNode *q=*p;while (jnext; j+; if(q!=null) return(q-data); elseprintf(位置参数不正确!n);return 0;int locate(struct LNode *p,ElemType x)int n=0; struct LNode *q=*p;while (q!=null&q-data!=x) q=q-next; n+; if(q=null) return(-1); else return(n+1);void insert(struct LNode *p,ElemType x,int i)int j=1; struct LNode *s,*q; s=(struct LNode *)malloc(sizeof(struct LNode); s-data=x; q=*p; if(i=1) s-next=q; *p=s; else while(jnext!=null) q=q-next; j+; if(j=i-1) s-next=q-next; q-next=s; else printf(位置参数不正确!n); void dele(struct LNode *p,int i)int j=1; struct LNode *q=*p,*t; if(i=1) t=q; *p=q-next; else while(jnext!=null) q=q-next; j+; if(q-next!=null&j=i-1) t=q-next; q-next=t-next; else printf(位置参数不正确!n); if(t!=null) free(t);void display(struct LNode *p)struct LNode *q; q=*p; p