数据结构实验二.doc

实验二 线性表的建立及基本操作方法实现【实验项目】：完成线性表的基本运算，从而了解线性表的基本特征，基本运算算法一、 【实验目的】：1. 理解和掌握线性表的类型定义方法。2. 掌握顺序表中的基本运算，包括顺序表的创建、元素的添加、删除，判空及判满等基本操作。3. 掌握链表中的基本运算，包括结点的定义，链表的创建等基本操作。4. 掌握利用尾插法建立单链表和显示单链表元素的算法。5. 掌握单链表的查找（按序号）算法。6. 掌握单链表的插入、删除算法。二、 【实验内容】：(一) 编写一个程序ALGO2-1.CPP，实现顺序表的各种基本运算，并在此基础上设计一个主程序完成如下功能：(1) 初始化顺序表L;(2) 依次采用尾插法插入a，b，c，d，e(3) 输出顺序表L;(4) 输出顺序表L长度；(5) 判断顺序表L是否为空；(6) 判断顺序表L 的第3个元素；(7) 输出元素a的位置；(8) 在第4个元素位置上插入f元素；(9) 输出顺序表L;(10) 删除L的第3个元素；(11) 输出顺序表L;(12) 释放顺序表L;(二) 编写一个程序ALGO2-2.CPP，实现单链表的各种基本运算，并在此基础上设计一个主程序完成如下功能：(1) 初始化单链表H;(2) 依次采用尾插法插入a，b，c，d，e元素；(3) 输出单链表h；(4) 输出单链表h的长度；(5) 判断单链表h是否为空；(6) 输出单链表h的第三个元素；(7) 输出元素a的位置；(8) 在第4个元素位置上插入f元素；(9) 输出单链表h；(10) 删除L的第3个元素；(11) 输出单链表h；(12) 释放单链表h；（一）程序：#include #include #define MaxSize 50typedef char ElemType;typedef struct ElemType elemMaxSize; int length; SqList;extern void InitList(SqList *&L);extern void DestroyList(SqList *L);extern int ListEmpty(SqList *L);extern int ListLength(SqList *L);extern void DispList(SqList *L);extern int GetElem(SqList *L,int i,ElemType &e);extern int LocateElem(SqList *L, ElemType e);extern int ListInsert(SqList *&L,int i,ElemType e);extern int ListDelete(SqList *&L,int i,ElemType &e);void main()SqList *L;ElemType e;printf(1)初始化顺序表Ln);InitList(L);printf(2)依次采用尾插法插入a,b,c,d,e元素n);ListInsert(L,1,a);ListInsert(L,2,b);ListInsert(L,3,c);ListInsert(L,4,d);ListInsert(L,5,e);printf(3)输出顺序表L:);DispList(L);printf(4)顺序表L长度=%dn,ListLength(L);printf(5)顺序表L为%sn,(ListEmpty(L)?空:非空);GetElem(L,3,e);printf(6)顺序表L的第3个元素=%cn,e);printf(7)元素a的位置=%dn,LocateElem(L,a);printf(8)在第4个元素位置上插入f元素n);ListInsert(L,4,f);printf(9)输出顺序表L:);DispList(L);printf(10)删除L的第3个元素n); ListDelete(L,3,e);printf(11)输出顺序表L:);DispList(L);printf(12)释放顺序表Ln);DestroyList(L);（二）程序#include #include/#define maxsize 1024typedef char ElemType;typedef struct nodeElemType data;struct node *next;LinkList; /初始化线性表void InitList (LinkList *&h)h=(LinkList *)malloc(sizeof(LinkList);h-next=NULL;/求线性表的长度 int ListLength(LinkList *h) int i=0;LinkList *p=h-next;while(p!=NULL)i+;p=p-next;return i;/求出线性表中第i个元素int GetElem(LinkList *h,int i,ElemType &e) int j=0;LinkList *p=h-next;if(iListLength(h)return (0);while(jnext;j+;e=p-data;return (1);/判断单链表是否为空 int ListEmpty (LinkList *h) return(h-next=NULL); /输出元素的位置（按元素值查找） int LocateElem(LinkList *h,ElemType e) LinkList *p=h-next; int i=1; while(p!=NULL & p-data!=e) p=p-next; i+; if(p=NULL) return(0); else return(i); /插入数据元素 int ListInsert(LinkList *&h,int i,ElemType e) int j=0; LinkList *p=h,*s; while(jnext; if(p=NULL) return 0; else s=(LinkList *)malloc(sizeof(LinkList); s-data=e; s-next=p-next; p-next=s; return 1; /删除数据元素 int ListDelete (LinkList *&h,int i,ElemType &e) int j=0; LinkList *p=h,*q ; while(jnext; if(p=NULL) return 0; else q=p-next; if(q=NULL) return 0; e=q-data; p-next=q-next; free(q); return 1; /销毁线性表 int DestroyList(LinkList *&h) LinkList *p=h,*q=p-next; while(q!=NULL) free(p); p=q; q=p-next; free(p); /输出线性表int DispList (LinkList *h)LinkList *p=h-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n); /主函数 void main()int i;ElemType e;LinkList *h;InitList(h); /初始化单链表h printf(1.初始化顺序表n); printf(n); printf(2.采用尾插法插入a,b,c,d,e元素n) ;ListInsert(h,1,a); /插入元素 ListInsert(h,2,b); ListInsert(h,3,c); ListInsert(h,4,d); ListInsert(h,5,e); printf(n);printf(3.输出单链表h：); DispList(h);printf(n); printf(4.长度:%dn,ListLength(h); printf(n); printf(5.单链表h为%sn,(ListEmpty(h)?空:非空); printf(n); GetElem(h,3,e); printf(6.单链表h的第3个元素是%cn,e); printf(n); printf(7.元素a的位置是第%d个元素n,LocateElem(h,a); printf(n); printf(8.在第4个元素位置上插入f元素n); ListInsert(h,4,f); printf(n);