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

实验一：线性表的基本操作
【实验目的】
学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、 插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法.
【实验内容】
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。给文件起好名字，选好路径，点0皿至此一个源文件就被添加到了刚创建
的工程之中。
4. 写好代码
5. 编译-＞链接-＞调试
1、#include "stdio°h”
#include "malloc.h"
#define OK 1
#define OVERFLOW -2
#define ERROR 0
#define LIST_INIT_SIZE 1
#define LISTINCREMENT 10
typedef int ElemType;
typedef int Status;
typedef struct {
ElemType * elem;
intlength;
intlistsize;
} 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 1
#define LISTINCREMENT 10 typedef int ElemType;
typedef int Status;
typedef struct {
ElemType * elem;
intlength;
intlistsize;
} 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(! pl I 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 )l|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);
}
【实验心得】
今天是本学期的第一次上机实验课，老师先给我们发了本次上机的内容以 及部分实验代码，因为是第一次接触这门课程，还没有理解这门学科的特点和 学习方法，所以同学们都觉得无从下手.后来老师根据班里的情况，把实验步骤 演示了一遍，同时也讲解了实验的思路，我们根据老师的讲解和演示，自己又动 手做了一遍，虽然在调试的过程中遇到很多问题，但是在老师的讲解下都一一 解决了。
通过再次实验我明白了上机的重要性，也掌握了线性表的顺序存储结构、 链式存储结构的设计与操作，对顺序表和单链表的建立、插入、删除等基本操 作算法有了一定的了解.