线性表的基本操作实验报告
- 格式：doc
- 大小：32.00 KB
- 文档页数：9
实验一：线性表的基本操作
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法.
【实验内容】
1. 顺序表的实践
1） 建立4个元素的顺序表s=sqlist[］={1，2,3，4,5}，实现顺序表建立的基本操作。
2） 在sqlist [］={1,2，3,4,5}的元素4和5之间插入一个元素9,实现顺序表插入的基本操作。
3） 在sqlist [］={1,2，3，4,9，5}中删除指定位置(i=5)上的元素9，实现顺序表的删除的基本操作.
2. 单链表的实践
3. 1） 建立一个包括头结点和4个结点的(5，4,2,1）的单链表,实现单链表建立的基本操作。
2） 将该单链表的所有元素显示出来.
3） 在已建好的单链表中的指定位置(i=3）插入一个结点3，实现单链表插入的基本操作。
4） 在一个包括头结点和5个结点的(5，4,3,2,1）的单链表的指定位置（如i=2）删除一个结点，实现单链表删除的基本操作。
5） 实现单链表的求表长操作。
【实验步骤】
1。打开VC++。
2.建立工程:点File—〉New,选Project标签,在列表中选Win32 Console
Application，再在右边的框里为工程起好名字，选好路径，点OK—>finish.至此工程建立完毕。
3。创建源文件或头文件：点File-〉New，选File标签，在列表里选C++ Source
File。给文件起好名字，选好路径，点OK.至此一个源文件就被添加到了刚创建的工程之中。
4．写好代码
5．编译－＞链接－＞调试
1、#include "stdio。h”
#include ”malloc.h"
#define OK 1
＃define OVERFLOW -2
#define ERROR 0
#define LIST_INIT_SIZE 100
＃define LISTINCREMENT 10
typedef int ElemType；
typedef int Status;
typedef struct {
ElemType ＊elem;
int length;
int listsize；
} SqList;
Status InitList( SqList &L ) ｛
int i，n;
L.elem = (ElemType*） malloc (LIST_INIT_SIZE＊sizeof （ElemType))；
if （!L.elem） return（OVERFLOW);
printf（”输入元素的个数：”）;
scanf（”%d”，＆n);
printf(”输入各元素的值：”)；
for（i=0;i〈n；i++)
scanf（"％d",＆L.elem[i］)；
L.length = n；
L。listsize = LIST_INIT_SIZE;
return OK； }
Status ListInsert（SqList ＆L, int i, ElemType e） ｛
ElemType *newbase，*p，＊q;
if (i < 1 ｜| i > L。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.elem［i—1]）;
for (p = ＆(L。elem［L。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((i < 1） |｜ （i 〉 L。length)) return ERROR;
p = ＆（L.elem[i—1］);
e = ＊p；
q = L.elem+L.length—1;
for (++p； p <= q; ++p） ＊（p-1） = *p；
—-L.length;
return OK;
}
void VisitList（SqList L) { int i;
for（i=0；i〈L.length；i++）
printf（"％d\t"，L。elem[i])；
｝
void main(）
｛
int i，e;
SqList L;
InitList（L） ；
VisitList（L）;
printf（”输入插入位置和值："）；
scanf(”％d，%d”，&i，&e）；
printf（"插入元素后,表中的值："）；
ListInsert（L,i,e)；
VisitList(L）；
printf（"输入删除位置：”）；
scanf（"％d”,＆i）；
printf("删除元素后，表中的值:”);
ListDelete(L，i，e）；
VisitList(L）;
}
2、#include "stdio。h"
#include ”malloc。h”
#define OK 1
#define OVERFLOW -2
＃define LIST_INIT_SIZE 100
＃define LISTINCREMENT 10
typedef int ElemType;
typedef int Status； typedef struct {
ElemType ＊elem；
int length;
int listsize；
｝ SqList；
Status InitList( SqList ＆L ） ｛
int i，n；
L。elem = (ElemType*) malloc (LIST_INIT_SIZE＊sizeof (ElemType));
if (！L。elem） return（OVERFLOW)；
printf("输入元素的个数：”);
scanf(”％d",＆n);
printf（”输入各元素的值:"）；
for(i=0;i〈n；i++)
scanf（"％d",＆L。elem[i]）；
L。length = n;
L。listsize = LIST_INIT_SIZE;
return OK；
｝
void VisitList(SqList L）
{ int i；
for(i=0；i
printf（”%d\t"，L。elem［i］);
}
void main(）
｛
SqList L;
InitList(L) ；
VisitList（L)； ｝
3、#include ”stdio.h”
＃include ”malloc.h”
#define OK 1
＃define OVERFLOW —2
#define ERROR 0
typedef int Status；
typedef int ElemType；
typedef struct LNode ｛
ElemType data；
struct LNode ＊next;
} LNode，＊LinkList；
Status ListInsert（LinkList ＆L，int i,ElemType e){
LinkList p,s;
int j；
p=L;j=0;
while（p＆＆j
p=p—>next；++j;
｝
if（！p｜｜j>i） return ERROR；
s=(LinkList)malloc(sizeof（LNode））;
s-〉data=e；
s—〉next=p-〉next；
p-〉next=s;
return OK；
｝
Status ListDelete(LinkList ＆L,int i,ElemType &e）{
LinkList p，q;
int j； p=L;j=0;
while（p—〉next＆&j〈i-1)｛
p=p-〉next；++j;
｝
if(!(p-〉next）｜|j〉i-1） return ERROR；
q=p—〉next；p—〉next=q—〉next;
e=q—〉data;free（q)；
return OK；
｝
Status CreateList（LinkList ＆L, int n） {
int i;
LinkList p；
L = （LinkList） malloc （sizeof （LNode)）；
L—>next = NULL;
printf("输入元素的个数和相应值："）；
scanf（"％d",&n)；
for (i = n; i 〉 0； ——i） ｛
p = (LinkList） malloc (sizeof (LNode));//生成新结点
scanf("%d"，＆p—〉data）；//输入指针p指出i=n时所对应的数值
p->next = L->next；
L->next = p；
}
return OK；
｝
void VisitList(LinkList L)
｛LNode *p；
p=L—〉next；
while（p）
