一、实验目的

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("%d\t",*(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("%d\t",*(L.elem+i));printf("\n");
}

结果：