实验二 线性表的基本操作

实验二 线性表的基本操作

一、实验目的

1. 掌握使用VC++6.0上机调试线性表的基本方法；

2. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构上的运算。

3. 掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在链式存储结构上的运算。

二、实验要求

1. 认真阅读和掌握本实验的程序。 2. 补全程序上机调试。

3. 保存程序的运行结果和程序清单，并结合程序进行分析

三、实验内容

1. 顺序表基本操作的实现：包括顺序表的创建、插入、删除和查找，请补全程序并调试。 第1步：任务分析

完成顺序表的建立，插入，删除和查找等函数功能，有助于更好的理解顺序表的概念和使用规律。上述函数都是线性表的基本操作，根据这些基本操作，可以构成其他更复杂的操作。

第2步：程序构思

(1) 顺序表的创建：因为顺序表的结构中包括了存放数据元素的起始地址，表的容量，以及表的当前长度等部分，所以表的创建工作一方面要为这些成员赋值，而存放数据元素的空间也需要在此处进行分配，因此整个创建工作包括了空间的创建和各个成员的赋值操作。

(2) 顺序表的插入：因为顺序表中的元素是连续存放的，元素之间的关系是通过位置的相邻性来体现的。因此在顺序表中的第i个位置上插入元素的操作可以表示为：

? 从表尾到插入位置的所有元素依次向后移动一个位置 ? 将待插入元素插入到i的位置

(3) 顺序表的删除：与插入相同，删除第i个数据元素后，需要将插入位置之后一直到表尾的数据元素依次作前移操作。

(4) 顺序表的查找：在顺序表中进行查找时，只能从第一个元素开始，逐个判断是否满足查找条件，如果找到返回元素在表中的下标，否则继续向后查找，直到表结束。 第3步：部分源代码： //结构的定义： #define ListSize 50 typedef struct

{ int * elem; /* elem表示存放数据元素的基地址*/

int length; /*当前的表长度*/ int listsize; }SeqList;

//顺序表的建立

/***************************/

//函数名：CreateList(SeqList &L,int n)

//参数： L表示创建的顺序表，n表示创建的顺序表的长度 //功能：根据给定长度n和用户输入的n个数据创建顺序表L /***************************/ void CreateList(SeqList &L,int n) {

L.elem=(int*)malloc(ListSize*sizeof(int)); if (!L.elem) exit(0); L.listsize=ListSize;

printf(\

for(int i=1;i<=n;i++) scanf(\ L.length=n; }

//顺序表的打印

/***************************/ //函数名：PrintList(SeqList L) //参数： L表示要打印的顺序表

//功能： 依次打印顺序表L中的各个数据元素的值 /***************************/ void PrintList(SeqList L) {

printf(\ for(int i=1;i<=L.length;i++) printf(\}

//顺序表的查找操作

/***************************/

//函数名：LocateList(SeqList L,int x)

//参数： L表示要查找的顺序表，x表示要查找的数据元素

//返回： int型，如果找到，返回数据元素所在的下标，找不到返回0 //功能：在顺序表中进行查找,并返回查找的元素的位置 /***************************/ int LocateList(SeqList L,int x) {

for(int i=1;i<=L.length;i++) if((L.elem[i])==x) return i; else return 0; }

//顺序表的插入

/***************************/

//函数名：InsertList(SeqList &L,int i,int e)

//参数： L表示要操作的顺序表，i表示插入元素的位置，e表示要插入的数据元素 //功能：在顺序表中将e插入到第i个数据元素的位置 void InsertList(SeqList &L,int i,int e) ;

//顺序表的删除：

void DeleteList(SeqList &L,int i); /***************************/ //函数名：DeleteList(SeqList &L,int i)

//参数： L表示要操作的顺序表，i表示删除元素的位置

//功能：在顺序表中删除第i个数据元素，删除之前将其打印出来

//主程序 int main() {

SeqList L; int i,x; int n=10; /*THE SIZE OF LIST*/ L.length=0; CreateList(L,n); /*CREATE THE LIST*/ PrintList(L); /*PRINT THE LIST*/ printf(“input the reseach element\ scanf(\ i=LocateList(L,x); printf(\ scanf(\ printf(\ scanf(\ InsertList(L, i, x); /*顺序表插入*/ PrintList(L); /*打印顺序表*/ printf(\ scanf(\ DeleteList(L,i); /*顺序表删除*/ PrintList(L); /*打印顺序表*/ }

思考：有一个表元素按值非递减有序排列的顺序表，编写一个函数实现删除顺序表中多余的值相同的元素。

2. 单链表基本操作的实现：包括单链表的创建、插入、删除。 请补全程序并调试。

单链表的建立、查找、插入、删除操作等是链表的基本操作，正确实现它们，需要首先从存储形式上理解链表。单链表的存储结构描述包含数据域和指针域两部分，这两部分构成一个结点，具体用C语言的结构体来描述。链表的操作主要是弄清楚指针的变化情况，明确头指针、当前指针的指向。

第2步：程序构思

(1) 单链表的建立（头插法）

先建立头结点，将头结点的指针域置空，然后逆位序输入元素值，生成新结点，插入到头结点之后。

(2) 单链表的插入

从单链表表头开始查找插入位置的前驱结点p，即第i-1个结点，如果找到，则新建结点，设置其数据域的值为插入的值，然后修改指针，将该结点插入到p之后；如果找不到，则插入操作失败。

(3) 单链表的删除

从单链表表头开始查找删除元素的前驱结点p，如果找到删除结点和p，则将待删除结点的数据域的值保存下来，并修改p的指针指向删除结点的后继结点；如果找不到，则删除操作失败。

第3步:部分源程序 #define NULL 0 //结构的定义：

typedef struct LNode{ int data;

struct LNode *next; } LNODE,*LinkList; //链表的建立

/***************************/

//函数名：CreateList_L(LinkList &L, int n)

//参数： L表示创建的单链表，n表示创建的单链表的长度

//功能：根据给定长度n，逆位序输入n个元素的值，建立带表头结点的单链表L。 /***************************/

void CreateList_L(LinkList &L, int n) { L = (LinkList) malloc (sizeof (LNode));

L->next = NULL; // 先建立一个带头结点的单链表 for (i = n; i > 0; --i) {

p = (LinkList) malloc (sizeof (LNode)); // 生成新结点 scanf(“%d”,&p->data); // 逆位序输入元素值 p->next = L->next; L->next = p; // 插入到表头 }

} // CreateList_L //链表的打印

/***************************/ //函数名：PrintList(LinkList L) //参数： L表示单链表的头指针

//功能：逐个打印单链表L的各个数据元素的值 /***************************/ void PrintList(LinkList L){ LinkList p; p=L;

printf(\

while(p->next!=NULL){ printf(\ p=p->next; }

printf(“----------The LinkList ended!\\n\}

//求链表的长度

/***************************/ //函数名：Listlength(LinkList L) //参数： L表示单链表的头指针

//返回：int型，返回整数值，表示单链表的长度 //功能：求单链表L的长度

/***************************/ int Listlength(LinkList L){ int i=0;

LNODE *p=L;

while(p->next!=NULL){ i++;

p=p->next; }

return i; }

//链表的插入操作

/***************************/

//函数名：InsertList(LinkList &L,int i,int e)

//参数： L表示单链表的头指针，i表示插入位置，e表示插入的数据元素的值 //返回：int型，返回1，表示插入成功，0表示插入失败 //功能：将数据元素e插入到单链表L的第i个位置上 /***************************/ int InsertList(LinkList &L,int i,int e){ }

//链表的删除操作

/***************************/

//函数名：DeleteList(LinkList &L,int i)

//参数： L表示单链表的头指针，i表示删除元素的位置 //返回：int型，返回删除元素的值

//功能：将单链表L的第i个结点删除，并返回删除元素的值 /***************************/ int DeleteList(LinkList &L,int i){ }

//主程序 int main(){ LinkList L;

int length; int i,e;

CreateList(L,10); PrintList(L);

length=Listlength(L);

printf(\ printf(\ scanf(\ DeleteList(L,i); PrintList(L);

printf(\ scanf(\ InsertList(L,i,e); PrintList(L); getchar(); }

and e:\\n\

本文来源：https://www.bwwdw.com/article/votd.html