数据结构实验指导书——线性表的操作
- 格式:doc
- 大小:59.00 KB
- 文档页数:9
实验1 线性表的基本操作
一、实验目的
(1) 掌握线性表的逻辑特征;
(2) 掌握线性表顺序存储结构的特点,熟练掌握顺序表的基本运算;
(3) 熟练掌握线性表的链式存储结构定义及基本操作;
(4) 理解循环链表和双链表的特点和基本运算;
(5 )加深对顺序存储数据结构的理解和链式存储数据结构的理解,逐步培养解决实际问题的编程能力;
二、实验内容
1、创建有若干个元素(可以是整型数值)的顺序表,实现对顺序表的初始化,对已建立的顺序表插入操作、删除操作、遍历输出顺序表。
要求各个操作均以函数的形式实现,在主函数中调用各个函数实现以下操作:
(1)从键盘上依次输入21、18、30、75、42、56,创建顺序表,并输出顺序表中的各元素值。
(2)分别在单链表的第3个位置插入67,给出插入成功或失败的信息,并输出此时顺序表中的各元素值。
(3)删除顺序表中的第6个数据元素,给出删除成功或失败的信息,并输出此时顺序表中的各元素值。
(4)查找顺序表中是否有75这个元素,如果有返回该元素在顺序表中的位序。
2、创建有若干个元素(可以是整型数值)的单链表,实现对单链表的初始化,对已建立的顺序表插入操作、删除操作、查找操作、遍历输出单链表表。
要求各个操作均以函数的形式实现,在主函数中调用各个函数实现以下操作:
(1)从键盘上依次输入21、18、30、75、42、56,创建单链表,并输出单链表中的各元素值。
(2)分别在单链表的第4个位置,给出插入成功或失败的信息,并输出单链表中的各元素值。
(3)删除单链表中的第2个数据元素,给出删除成功或失败的信息,并输出单链表中的各元素值。
(4)查找顺序表中的第五个元素并输出该元素的值。
三、参考代码
(1) 顺序表的操作
#include
#include
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define INIT_SIZE 100
/*初始分配空间的大小*/
#define LISTINCREMENT 10
/*分配增量*/
typedef int ElemType;
typedef struct{
ElemType *elem;
int length;
int listsize;
}SqList;
/*ElemType elem[INIT_SIZE],注两者区别。存储空间的起始地址。*/
/*线性表中数据元素个数,即表长*/
/*线性表所申请的存储空间的大小*/
SqList CreateList_Sq(SqList L)
/*创建一个空的线性表*/
{
L.elem=(ElemType *)malloc(INIT_SIZE*sizeof(ElemType));
if (!L.elem) exit(ERROR);
L.length=0; /*表长为0*/
L.listsize=INIT_SIZE;
/*申请的空间为初始大小*/
return L;
}
Status InsertList_Sq(SqList *L, int i, ElemType e)
/*在线性表的第i个位置前插入元素e*/
{ int * newbase,*q,*p;
int j;
if ((i<1)||(i>L->length+1)) {printf("i值不合法!\n");exit(ERROR);} if (L->length>=L->listsize) /*当前空间已满,增加分配空间*/ {
newbase=(ElemType
*)realloc(L->elem,(L->listsize+LISTINCREMENT)*sizeof(ElemType));
if (!newbase) exit(ERROR);
L->elem=newbase;
L->listsize= L->listsize+LISTINCREMENT;
}
q=&(L->elem[i-1]);
for(p=&(L->elem[L->length-1]);p>=q;--p)
*(p+1)=*p;
*q=e;
L->length++;
}
SqList DeleteList_Sq(SqList *L, int i, ElemType *e)
/* 删除线性表中的第i个元素,并获得所删元素的值*/
{ int j;
if ((i<1)||(i>L->length)) {printf("i值不合法!\n");exit(ERROR);}
*e=L->elem[i-1];
for(j=i;j<=L->length;j++)
L->elem[j-1]=L->elem[j];
L->length--;
}
void Print_Sq(SqList L)
/*遍历顺序线性表*/
{ int i;
printf("\nThe list:\n");
for(i=0;i { if ((i+1)%10==0) printf("%3d\n",L.elem[i]); else printf("%3d ",L.elem[i]); } } int GetLength(SqList L) { return L.length; } int equal(ElemType e1,ElemType e2) /*判两个元素是否相等*/ { if (e1==e2) return 1; else return 0; } int LocateElem_Sq(SqList L,ElemType e, int (* compare)(ElemType e1,ElemType e2)) { int i; i=1; while(i<=L.length && !(* compare)(L.elem[i-1],e)) i++; if (i<=L.length) return i; else return 0; } void Getelem(SqList L,int i,ElemType *e) { *e=L.elem[i-1]; } int ListEmpty(SqList L) { if (L.length==0) return 1; else return 0; }