线性表基本操作实验报告.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 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;ie);
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{
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&&jnext;++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&&jnext;++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);
}
【实验心得】
今天是本学期的第一次上机实验课，老师先给我们发了本次上机的内容以及部分实验代码，因为是第一次接触这门课程，还没有理解这门学科的特点和学习方法，所以同学们都觉得无从下手。后来老师根据班里的情况，把实验步骤演示了一遍，同时也讲解了实验的思路，我们根据老师的讲解和演示，自己又动手做了一遍，虽然在调试的过程中遇到很多问题，但是在老师的讲解下都一一解决了。
通过再次实验我明白了上机的重要性，也掌握了线性表的顺序存储结构、链式存储结构的设计与操作，对顺序表和单链表的建立、插入、删除等基本操作算法有了一定的了解。
9 / 9