一、实验目的
1.了解线性表的逻辑结构特性及其基本操作。
2.熟练掌握线性表的顺序存储结构的定义及其基本操作的C 语言实现。
3.掌握顺序表的应用，逐步培养解决实际问题的能力。
4.熟练掌握C语言中指针、结构体与数组的知识，为以后的各个实验做准备。
二、实验内容
1.(必做题) 设计并验证以下算法：设顺序表L中的数据元素为整数且非递增有序，删除其值相同的多余元素，即顺序表L中相同的元素只保留一个，并逆置删除后的顺序表L。
(1) 根据键盘输入数据建立顺序表L。
(2) 输出顺序表L、删除值相同多余元素后的顺序表L、逆置的顺序表L。
(3) 假设顺序表L的长度为n,要求以O(m)的时间复杂度完成对值相同多余元素的删除。
2.设计并验证以下算法: 设顺序表A和B中的数据元素为整数且单调递增
有序，将这两张表合并成顺序表C。
(1) 顺序表C单调递减有字。
(2) 根据键盘输入数据建立顺序表A和B。
(3) 输出顺序表A、B和C。
三、代码实现与结果
第一题：
代码：
#include <stdlib.h>#include <stdio.h>#define LIST_INIT_SIZE 10 //顺序表存储空间的初始分配量#define LISTINCREMENT 2 //顺序表存储空间的分配增量 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 //函数结果状态代码#define INFEASIBLE -1#define OVERFLOW -2typedef int status;typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}SqList; //定义线性表的存储结构 status InitList_Sq(SqList &L);void CreateSqList(SqList &L);void RefineSqList(SqList L1,SqList &L2);void Inverse(SqList &L);void PrintSq_List(SqList L);int main(int argc, char* argv[]){SqList L1,L2;if(InitList_Sq(L1)==OK && InitList_Sq(L2)==OK){CreateSqList(L1);printf("SqList L1:n");PrintSq_List( L1);RefineSqList(L1,L2);printf("pure SqList L2:n");PrintSq_List(L2);Inverse(L2);printf("inverse pure SqList L2:n");PrintSq_List(L2);}return 0;}status InitList_Sq(SqList &L) //构造一个新的顺序表L{L.elem = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);if(!L.elem) return OVERFLOW;L.length=0;L.listsize = LIST_INIT_SIZE;return OK;}void CreateSqList(SqList &L) //创建一个线性表L{int i; for(i=0;i<L.listsize;i++){scanf("%d",L.elem+i);L.length++;}}void RefineSqList(SqList L1,SqList &L2) //精制顺序表L1，L2{ElemType pre,cur;int i,j=0;for(i=0;i<L1.length;i++){if(i==0){pre=*(L1.elem);*(L2.elem+j) = pre;j=++L2.length;}else{cur = *(L1.elem+i);if(cur == pre) continue;else{pre = cur;*(L2.elem+j) = cur;j=++L2.length;}}}}void Inverse(SqList &L) //逆置顺序表L{int l=L.length,i;ElemType q;for(i=0;i<l/2;i++){q=*(L.elem+i);*(L.elem+i)=*(L.elem+l-1-i);*(L.elem+l-1-i) =q;}}void PrintSq_List(SqList L) //输出顺序表L{int l=L.length,i;for(i=0;i<l;i++)printf("%dt",*(L.elem+i));printf("n");}
结果：
第二题：
代码：
#include <stdio.h>#include <stdlib.h>#define LIST_INIT_SIZE 5 //顺序表存储空间的初始分配量 #define LISTINCREMENT 2 //顺序表存储空间的分配增量 #define TRUE 1#define FALSE 0#define OK 1#define ERROR 0 //函数结果状态代码 #define INFEASIBLE -1 #define OVERFLOW -2typedef int status;typedef int ElemType;typedef struct{ElemType *elem;int length;int listsize;}SqList; //定义线性表的存储结构 status InitList_Sq(SqList &L); void CreateSqList(SqList &L); void RefineSqList(SqList La,SqList &Lb); void CombineSqList(SqList La,SqList Lb,SqList *Lc);void Inverse(SqList &L); void PrintSq_List(SqList L); int main(int argc, char* argv[]){SqList La,Lb,Lc,Ld;if(InitList_Sq(La)==OK && InitList_Sq(Lb)==OK && InitList_Sq(Lc)==OK && InitList_Sq(Ld)==OK){printf("Please input La's number:n");CreateSqList(La);printf("The list of La is:");PrintSq_List(La);printf("Please input Lb's number:n");CreateSqList(Lb);printf("The list of Lb is:");PrintSq_List(Lb);printf("n");CombineSqList(La,Lb,&Ld);Inverse(Ld);RefineSqList(Ld,Lc);printf("The lastest Lc is:");PrintSq_List(Lc);}return 0;}status InitList_Sq(SqList &L) //构造两个新的顺序表La,lb {L.elem = (ElemType*)malloc(sizeof(ElemType)*LIST_INIT_SIZE);if(!L.elem) return OVERFLOW;L.length=0;L.listsize = LIST_INIT_SIZE;return OK;}void CreateSqList(SqList &L) //创建两个线性表La,Lb {int i;for(i=0;i<L.listsize;i++){scanf("%d",L.elem+i);L.length++;}}void RefineSqList(SqList La,SqList &Lb) //精制顺序表La，Lb{ElemType pre,cur;int i,j=0;for(i=0;i<La.length;i++){if(i==0){pre=*(La.elem);*(Lb.elem+j) = pre;j=++Lb.length;}else{cur = *(La.elem+i);if(cur == pre) continue;else{pre = cur;*(Lb.elem+j) = cur;j=++Lb.length;}}}}void CombineSqList(SqList La,SqList Lb,SqList *Lc) //合并顺序表La,Lb为Lc{int k=0,p=0, l=0; while((k<La.length) && (p<Lb.length)) {if(La.elem[k]<=Lb.elem[p]){Lc->elem[l]=La.elem[k];k++;}else{Lc->elem[l]=Lb.elem[p];p++;}l++;}while(k<La.length){Lc->elem[l]=La.elem[k];l++;k++;}while(p<Lb.length){Lc->elem[l]=Lb.elem[p];l++;p++;}Lc->length=La.length+Lb.length;}void Inverse(SqList &L) //逆置顺序表Lc{int l=L.length,i;ElemType q;for(i=0;i<l/2;i++){q=*(L.elem+i);*(L.elem+i)=*(L.elem+l-1-i);*(L.elem+l-1-i)=q;}}void PrintSq_List(SqList L) //输出顺序表La,Lb,Lc{int l=L.length,i;for(i=0;i<l;i++)printf("%dt",*(L.elem+i));printf("n");}
结果：