实验二 线性表的基本操作
一、实验目的
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语言的结构体来描述。链表的操作主要是弄清楚指针的变化情况，明确头指针、当前指针的指向。