线性表的基本操作实验报告.doc

实验一:线性表的基本操作
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。
【实验内容】
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〈L.length;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〈i—1) {
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)
｛
printf(”%d\t”，p—〉data)；
p=p->next;
}
}
void main（)｛
int i,n；
LinkList L；
ElemType e；
CreateList(L，n);
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)；
}
【实验心得】
今天是本学期的第一次上机实验课,老师先给我们发了本次上机的内容以及部分实验代码,因为是第一次接触这门课程，还没有理解这门学科的特点和学习方法，所以同学们都觉得无从下手。后来老师根据班里的情况,把实验步骤演示了一遍，同时也讲解了实验的思路,我们根据老师的讲解和演示，自己又动手做了一遍，虽然在调试的过程中遇到很多问题，但是在老师的讲解下都一一解决了。
通过再次实验我明白了上机的重要性,也掌握了线性表的顺序存储结构、链式存储结构的设计与操作，对顺序表和单链表的建立、插入、删除等基本操作算法有了一定的了解。