线性表的基本操作教案

1、实验一 线性表的基本操作一、实验目的学习掌握线性表的顺序存储结构、链式存储结构。设计顺序表的创建、插入、删除等基本操作，设计单链表的建立、插入、删除等基本操作。二、实验内容1.顺序表的实践（1）顺序表的创建：基于顺序表的动态分配存储结构，创建一个顺序表S，初始状态S=(1，2，3，4，5)。（2）顺序表的遍历：依次输出顺序表的每个数据元素。（3）顺序表的插入：在顺序表S=(1，2，3，4，5)的数据元素4和5之间插入一个值为9的数据元素。（4）顺序表的删除：顺序表S=(1，2，3，4，9，5)中删除指定位置（i=3）的数据元素3。（5）顺序表的按值查找：查找顺序表S中第1个值等于4的数据元素位

2、序。（6）顺序表的清空：释放顺序表的存储空间。2.单链表的实践（1）单链表的创建：创建一个包括头结点和4个元素结点的单链表L=（5，4，2，1）。（2）单链表的遍历：依次输出顺序表的每个数据元素。（3）单链表的取值：输出单链表中第i个（i=2）数据元素的值。（4）单链表的插入：在已建好的单链表的指定位置（i=3）插入一个结点3。（5）单链表的删除：在一个包括头结点和5个结点的单链表L=（5，4，3，2，1）中，删除指定位置（i=2）的结点，实现的基本操作。（6）求单链表的表长：输出单链表的所有元素和表长。（7）单链表的判空：判断单链表是否为空表。（8）单链表的清空：释放单链表的存储空间。三、程

3、序源代码1.线性表的基本操作#include #includeusing namespace std;#define OK 1#define OVERFLOW -2#define ERROR 0#define LIST_INIT_SIZE 100#define LISTINCEREMENT 10typedef int Status;typedef int Elemtype;typedef Elemtype *Triplet;typedef struct /定义结构体类型：顺序表Elemtype *elem;int length;int listsize; Sqlist;Status Initl

4、ist( Sqlist &L ) /int n,i;L.elem = (Elemtype*) malloc (LIST_INIT_SIZE*sizeof(Elemtype);if(!L.elem) return(OVERFLOW);cout n;for(int i=0; i L.elemi;L.length = n;L.listsize = LIST_INIT_SIZE;return OK;Status TraverList(Sqlist L) for(int i=0; iL.length; i+) cout L.elemi ;cout endl;Status ListInsert (Sqli

5、st &L,int i,Elemtype e) /插入Elemtype *newbase,*p,*q;if(iL.length+1) return ERROR;/i不合法if(L.length = L.listsize) /需要重新分配存储空间newbase = (Elemtype *) realloc(L.elem,(L.listsize + LISTINCEREMENT)*sizeof (Elemtype);if(!newbase) exit(OVERFLOW);/分配失败L.elem = newbase;L.listsize += LISTINCEREMENT;q = &(L.elemi

6、-1);for(p=&(L.elemL.length-1); p=q; -p)*(p+1)=*p;*q=e;+L.length;return OK;Status ListDelete(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; p=q; +p)*(p-1)=*p;-L.length;return OK;Status LocateElem(Sqlist L,Elemtype &e) /查找int i

7、;Elemtype *p;i=1;p=L.elem;while(i=L.length&*(p+)!=e) +i;if(i=L.length) return i;else return 0;Status ClearList(Sqlist &L) free(L.elem);cout 该表已被清空！;return OK;int main() Sqlist L;int i,z;Elemtype e;if(Initlist(L)=OVERFLOW) cout endl OVERFLOW;return 0;TraverList(L);while(1) cout - endl;cout 选择要执行的基本操作

8、： endl 1:插入元素 endl 2.删除元素 endl 3.查找元素 endl 4.退出 z;switch(z) case 1:cout 输入要插入元素的位置和值： i e;if(ListInsert(L,i,e)=OK)TraverList(L);elsecout 插入的位置不合法。 endl;break;case 2:cout 输入要删除元素的位置： i;if(ListDelete(L,i,e)=OK) TraverList(L);cout 删除的元素值为： e endl; else cout 删除的位置不合法。 endl;break;case 3:cout 输入要查找元素的值： e

9、;if(LocateElem(L,e)cout 该元素的位置是第 LocateElem(L,e) 位 endl; else cout 该元素不存在！ endl;case 4:cout 操作结束 endl;ClearList(L);exit(0);default:cout 选择有误，请重新选择！ endl;2.链表的基本操作#include#include#include#include#include#define OVERFLOW -2#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define INFEASIBLE -1#d

10、efine LIST_INIT_SIZE 100#define LISTINCREMENT 10using namespace std;typedef int Status;typedef int ElemType;typedef struct LNode ElemType data;struct LNode *next; LNode,*LinkList; /LNode结构体类型别名，LinkList结构体指针别名Status InitLNode(LinkList &L) /初始化链表，n个元素，线性表长度为nint n,i;LinkList p,r;L=(LinkList)malloc(si

11、zeof(LNode);/动态申请一个结点（头节点）if(!L)return OVERFLOW;L-next=NULL;r=L;cout n;for(i=0; i p-data;r-next=p;r=p;r-next=NULL;return OK;/InitLNodevoid ListDisp(LinkList L) /遍历单链表，依次输出各元素LinkList p;p=L-next;cout endl The LinkList L:endl;/依次访问L的每一个结点，直到结尾while(p!=NULL) cout data next;cout next;/p指针初值：NULL取值指向第一个元

12、素的值while(p&jnext;+j;/若p为空未找到，ji（i值不合法）,取值错误返回ERRORif(!p|ji)return ERROR;e=p-data;return OK;/GetElemStatus ListInsert(LinkList &L,int i,ElemType e) /往单链表L中第i个位置之前插入新的元素eLinkList p,s;int j=0;p=L;while(p&jnext;+j;if(!p|ji-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;/1p-next=s

13、;/2,顺序不能变return OK;/ListInsertStatus ListInse(LinkList &L,int i,ElemType &e) /删除单链表L中第i个元素，用e返回其值LinkList p,q;int j;p=L;j=0;while(p-next&jnext;+j;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;free(q);return OK;/ListInseStatus ListLength(LinkList L) /求链表长度LinkList p;int i=0;p=L-next;

14、while(p!=NULL) i+;p=p-next;return i;/ListLengthStatus LNodeEmpty(LinkList L) /若单链表L为空表返回TRUE，否则返回FALSEif(L-next=NULL)return TRUE;elsereturn FALSE;/LNodeEmptyStatus ClearList(LinkList &L) /清空单链表LinkList p;p=L-next;while(p!=NULL) L-next=p-next;free(p);p=L-next;/ClearList;int main() LinkList L;int i,s;

15、ElemType e;InitLNode(L);if(ListLength(L)=0) ListDisp(L);cout 表为空。 endl;return 0;while(1) cout - endl;cout 选择操作： endl 1:输出某个元素的值； endl 2.在某个元素之前插入一个元素; endl 3.删除某个元素; endl 4.输出链表中的元素及其长度; endl 5.退出 s;switch(s) case 1:cout i;if(!GetElem(L,i,e)cout 该元素不存在！ endl;elsecout 第 i 个元素的值是： e endl;break;case 2:

16、cout i e;cout 当前链表的所有元素为： endl;if(ListInsert(L,i,e)=OK)ListDisp(L);elsecout 插入的位置不合法。 endl;break;case 3:cout i;if(ListInse(L,i,e)=OK) cout 删除的元素值为： e endl;cout 当前链表的所有元素为： endl;ListDisp(L); else cout 删除的位置不合法。 endl;break;case 4:cout 当前链表的所有元素为： endl;ListDisp(L);cout 链表的长度为： ListLength(L) endl;break;case 5:cout 操作结束! 该表已被清空！ endl;ClearList(L);exit(0);default:cout 选择有误，请重新选择！ endl;四、程序运行结果1、顺序表的实践，运行结果如下：2、单链表的实践，运行结果如下：五、实验心得本次的实验我经过数个小时的练习，学会了一些语法和一些特殊结构，对线性链表和顺序链表更加熟悉了，主要收获如下：对于线性链表和顺序表都属于线性表问题，但是线性链表的插入删除比顺序表要简单，方便。顺序表的查