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

实验一：线性表的基本操作

【实验目的】

学习掌握线性表的顺序存储结构、链式存储结构的设计与操作。对顺序表建立、插入、删除的基本操作，对单链表建立、插入、删除的基本操作算法。

【实验内容】

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 #define LISTINCREMENT typedef int ElemType;

typedef int Status;

typedef struct {

ElemType *elem;

int length;

int listsize;

} SqList;

Status InitList( SqList &L ) {

10

100

int i,n;

L.elem = (ElemType*) malloc (LIST_INIT_SIZE*sizeof (ElemType));

if (!L.elem) return(OVERFLOW);

printf(\"输入元素的个数:\");

scanf(\"%d\

printf(\"输入各元素的值:\");

for(i=0;iscanf(\"%d\

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;iprintf(\"%d\\

}

void main()

{

int i,e;

SqList L;

InitList(L) ;

VisitList(L);

printf(\"输入插入位置和值:\");

scanf(\"%d,%d\

printf(\"插入元素后，表中的值:\");

ListInsert(L,i,e);

VisitList(L);

printf(\"输入删除位置:\");

scanf(\"%d\

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\

printf(\"输入各元素的值:\");

for(i=0;iscanf(\"%d\

L.length = n;

L.listsize = LIST_INIT_SIZE;

return OK;

}

void VisitList(SqList L)

{ int i;

for(i=0;iprintf(\"%d\\

}

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&&jp=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&&jp=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\

for (i = n; i > 0; --i) {

p = (LinkList) malloc (sizeof (LNode));//生成新结点

scanf(\"%d\输入指针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\\

p=p->next;

}

}

void main(){

int i,n;

LinkList L;

ElemType e;

CreateList(L,n);

VisitList(L);

printf(\"输入插入位置和值:\");

scanf(\"%d,%d\

printf(\"插入元素后，表中的值:\");

ListInsert(L,i,e);

VisitList(L);

printf(\"输入删除位置:\");

scanf(\"%d\

printf(\"删除元素后，表中的值:\");

ListDelete(L,i,e);

VisitList(L);

}

【实验心得】

今天是本学期的第一次上机实验课，老师先给我们发了本次上机的内容以及部分实验代码，因为是第一次接触这门课程，还没有理解这门学科的特点和学习方法，所以同学们都觉得无从下手。后来老师根据班里的情况，把实验步骤演示了一遍，同时也讲解了实验的思路，我们根据老师的讲解和演示，自己又动手做了一遍，虽然在调试的过程中遇到很多问题，但是在老师的讲解下都一一解决了。

通过再次实验我明白了上机的重要性，也掌握了线性表的顺序存储结构、链式存储结构的设计与操作，对顺序表和单链表的建立、插入、删除等基本操作算法有了一定的了解。