数据结构实验一要求.doc

实验1：线性表的顺序表示与链式表示【实验目的】1. 加深理解线性表的顺序表示与链式表示的意义和区别，掌握用它们表示时各基本操作的设计与实现。2. 学会定义线性表的顺序存储类型和链式存储类型，实现C程序的基本结构，对线性表的一些基本操作和具体的函数定义。3. 掌握线性表的基本操作（初始化、建立、插入、删除、遍历等）。4. 掌握对多函数程序的输入、编辑、调试和运行过程。5. 进一步熟练C语言的使用，特别是指针和链表的使用。6. 能在实际应用背景下恰当选择顺序存储和链式存储。【实验要求】1. 预习C语言中的结构的定义和基本操作方法2. 对线性表的每个基本操作用单独的函数实现3. 编写完整程序完成下面的实验内容并上机运行4. 整理并上交实验报告【实验内容】1. 分别建立包含10个数据元素的顺序线性表和链式线性表； 2. 从键盘输入一个数据元素和插入位置k，将元素插入到线性表中第k（包含0号位置）个位置； 3. 从键盘输入一个数据元素关键字或位置k（包含1号位置），从线性表中删除相应数据元素；4. 能完成查找功能； 5. 给出程序及插入、删除前和插入、删除后线性表结果。 【实验指导】顺序表示和链式表示可以分成两个程序来调试（见示例程序和）。教材中的算法一般要作少许修改才能运行，这些修改包括：1、算法函数中局部变量的定义，如ListInsert_Sq中的i,newbase,p,q等；2、可能出现的“类”C语言的语句，必须改为C语言语句，如数据交换语句xy;3、如果采用TC作为C语言调试环境，算法函数的“引用”类型参数要改为指针类型参数并修改程序中的使用方法，如ListInsert_Sq中的参数&L要改为*L。程序中使用L方法的修改见示例程序。一个简单程序通常主要由三部分构成：1、常量定义（#define），类型定义(typedef)及函数原型定义(#include)；2、算法函数，即InitList_Sq、ListInsert_Sq、ListDelete_Sq等；3、主函数。【思考提高】实现两个线性表的并。示例程序，InitList_Sq、ListInsert_Sq、ListDelete_Sq在TC2.0中的调试：#include stdio.h#include malloc.h#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2#define LIST_INIT_SIZE 10#define LISTINCREMENT 4typedef int Status;typedef int ElemType;typedef struct ElemType *elem; int length; int listsize;SqList;Status InitList_Sq(SqList *L) L-elem=(ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType); if (!L-elem) return(OVERFLOW); L-length=0; L-listsize=LIST_INIT_SIZE; return OK; Status ListInsert_Sq(SqList *L,int i,ElemType e) ElemType *q,*p,*newbase; if (iL-length+1) return ERROR; if (L-length=L-listsize) newbase=(ElemType*)realloc(L-elem,(L-listsize+LISTINCREMENT)*sizeof(ElemType); if (!newbase) return(OVERFLOW); L-elem=newbase; L-listsize+=LISTINCREMENT; q=&(L-elemi-1); for(p=&(L-elemL-length-1);p=q;-p) *(p+1)=*p; *q=e; +L-length; return OK; Status ListDelete_Sq(SqList *L,int i,ElemType *e) ElemType *p,*q; if (iL-length) return ERROR; p=&(L-elemi-1); *e=*p; q=(L-elem+L-length-1); for (+p;plength; return OK; void main() SqList Lst; int i,n=15; ElemType e; if (InitList_Sq(&Lst)=OK) for(i=1;i=n;i+) if(ListInsert_Sq(&Lst,i,i)!=OK) break; printf(n); for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); getch(); if (ListDelete_Sq(&Lst,10,&e)=OK) printf(delete_elem=%dn,e); getch(); for (i=0;iLst.length;i+) printf(i,e=%d,%dn,i,Lst.elemi); else printf(delete_elem is failedn); 示例程序，InitList_L、ListInsert_L、ListDelete_L在VC6.0中的调试：#include math.h#include malloc.h#include stdio.h#define ERROR 0#define TRUE 1#define FLASE 0#define OK 1#define INFEASIBLE -1#define OVERFLOW -2typedef struct Lnode ElemType data; struct Lnode *next;Lnode, *LinkList;Status ListInsert_L(LinkList &L, int i, ElemType e) LinkList s,p; int j; p = L; j = 0; while(p&jnext;+j; if(!p|ji-1) return ERROR; s = (Lnode *)malloc(sizeof(Lnode); if(!s) return OVERFLOW; s-data = e; s-next = p-next; p-next = s; return OK;Status ListDelete_L(LinkList &L, int i, ElemType &e) LinkList s,p; int j; p = L; j = 0; while(p-next & jnext;+j; if(!(p-next)|ji-1) return ERROR; s = p-next; p-next = s-next; e = s-data; free(s); return OK;Status InitList_L(LinkList &L) L = (Lnode *)malloc(sizeof(Lnode); if (L) L-next = NULL; return OK; else return ERROR;int cmp(Event a, Event b);Status OrderInsert_L(LinkList &L, ElemType e, int (*cmp)(Event a, Event b) Lnode *p,*q;p=(Lnode *)malloc(sizeof(Lnode); if(!p)return(OVERFLOW);p-data = e;q=L; while(q-next & cmp(e,q-next-data)0)q=q-next; p-next = q-next;q-next = p; return OK; int EmptyList(LinkList L) if(!L-next) return 1; return 0; LinkList GetHead(LinkList L) if(!L-next) return NULL; return L-next; Status DelFirst(LinkList L, LinkList &p) p = L-next; if(!p) return ERROR; L-next = p-next; return OK; void main()/ 主程序略示例3#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*)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=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()/插入结点函数 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); 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 = 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-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 0; return 0; void find() st