用顺序存储实现两个线性表合并

合并两个线性表中的元素，相同的元素只保留一个，代码如下：

#pragma once

#define ListSize 200

#include

using namespace std;

typedef int DataType;

typedef struct

{

DataType list[ListSize];

int length;

}SeqList;

//初始化线性表

void InitList(SeqList *L)

{

L->length = 0;//把线性表长度置为0

}

//判断线性表是否为空,线性表为空返回1，否则返回0

int ListEmpty(SeqList L)

{

if (L.length == 0)

return 1;

else

return 0;

}

//按照序号查找

int GetElem(SeqList L, int i, DataType *e)

/*查找线性表中第i个元素，查找成功返回给e，并返回1表示成功，否则返回-1，表示失败*/

{

if (i<1 || i>L.length)

return -1;

else

*e = L.list[i - 1];

return 1;

}

//按照内容查找

int LocateElem(SeqList L, DataType e)

{

int i;

for (i = 0; i < L.length; i++)/*从第一个元素开始与e进行比较*/

if (L.list[i] == e)       /*若存在与e相等的元素*/

return i + 1;         /*返回该元素的在线性表中的序号*/

return 0;                     /*否则，返回0 */

}

//插入操作

int InsertList(SeqList *L, int i, DataType e)

/*在顺序表中的第i个位置插入元素e，插入成功返回1，插入不合法返回-1，顺序表满返回0.*/

{

int j;

if (i<1||i>L->length+1)/*在插入元素前，判断插入位置是否合法*/

{

cout <<"插入位置"<

return -1; 

}

else if (L->length>=ListSize)/*在插入元素之前，判断顺序表是否已经满，不能插入元素*/

{

cout << "顺序表已经满，不能插入元素。" << endl;

return 0;

}

else

{

for (j = L->length; j >= i; j--)

/*将第i个位置以后的元素依次后移*/

{

L->list[j] = L->list[j - 1];

}

L->list[i - 1] = e;

L->length = L->length + 1;

return 1;

}

}

/*删除操作，删除第i个元素*/

int DeleteList(SeqList *L, int i, DataType *e)

{

int j;

if (L->length<=0)

{

cout << "顺序表表已空，不能进行删除！" << endl;

return 0;

}

else if (i<1||i>L->length)

{

cout << "删除位置不合适！" << endl;

return -1;

}

else

{

*e = L->list[i - 1];

for (j = i; j <= L->length - 1;j++)

{

L->list[j - 1] = L->list[j];

}

L->length = L->length - 1;

return 1;

}

}

/*求线性表的长度*/

int ListLength(SeqList L)

{

return L.length;

}

/*清空顺序表*/

void ClearList(SeqList *L)

{

L->length = 0;

}

扩展资料

线性表的顺序存储结构，就是在内存中找到一块空间，通过占位的方式，把一定内存空间给占了，然后把相同数据类型的数据元素依次存放在这块空间中。

既然线性表的每个数据元素的类型相同，所以C语言（其他语言也相同）用一维数组来实现顺序存储结构，即把第一个数据元素存到数组下标为0的位置中，接着把线性表相邻的元素存储在数组中相邻的位置。

顺序存储的属性

三个属性：

1、存储空间的起始位置：数组data，它的存储位置就是存储空间的存储位置。

2、线性表的最大存储容量：数组的长度MaxSize.

3、线性表的当前长度：length。

#include
/*线性表*/
struct TLink {
int data;
struct TLink * next;
};/*end struct TLink*/

/*生成新元素*/
struct TLink * new_item(int number)
{
struct TLink * r = 0;
r = (struct TLink *)malloc(sizeof(struct TLink));
r->data = number;
r->next = 0;
return r;
}/*end new_item*/

/*在线性表中查询数据*/
struct TLink * lookup(struct TLink * root, int number)
{
struct TLink * h = root;
while(h) {
if (h->data == number) return h;
h = h->next ;
}/*end lookup*/
return 0;
}

/*在线性表中追加一个数据*/
void append(struct TLink * * root, int number)
{
struct TLink * r = 0, * n = 0;
if (!root) return ;

/*不记录重复元素*/
if (lookup(*root, number)) return;

/*如果表为空则新建表*/
r = *root;
if (!r) {
*root = new_item(number);
return ;
}/*end if*/

/*为保证为有序线性表，如果数据比表头还小则作为表头*/
if (number < r->data ) {
n = new_item(number);
n->next = r;
*root = n;
return ;
}/*end if*/

/*在有序线性表中查找位置插入元素*/
while(r) {
n = r->next ;

/*如果已经是表尾则直接追加*/
if (!n) {
n = new_item(number);
r->next = n;
return ;
}/*end if*/

/*在中央某处插入*/
if (number < n->data ) {
r->next = new_item(number);
r->next->next = n;
return ;
}/*end if*/
r = n;
}/*end while*/
}/*end append*/

/*打印有序线性表*/
void print(struct TLink * root)
{
struct TLink * r = root;
printf("【");
while(r) {
printf("%d ", r->data );
r = r->next ;
}/*end while*/
printf("\b】\n");
}/*end print*/

/*将有序线性表h1合并至有序线性表h0，并销毁线性表h1*/
void merge(struct TLink ** h0, struct TLink ** h1)
{
struct TLink * h = 0, * k = 0;
if (!h0 || !h1) return ;
h = *h1;
while(h) {
append(h0, h->data );
k = h;
h = h->next ;
free(k);
}/*end h*/
h1 = 0;
}

int main(void)
{
int i = 0; struct TLink * x=0, *y = 0;
int a[] = ;
int b[] = ;
printf("原数据为：\n数组A：【");
for(i = 0; i < 6; i++) {
printf("%d ", a[i]);
append(&x, a[i]);
}/*next*/
printf("\b】\n数组B：【");
for(i = 0; i < 6; i++) {
printf("%d ", b[i]);
append(&y, b[i]);
}/*next*/
printf("\b】\n转换为有序线性表\nA：");
print(x);
printf("B：");
print(y);
printf("AB合并后为：");
merge(&x, &y);
print(x);
return 0;
}

#include
#include
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define Compare( a, b) ( ((a) == (b)) ? (1) : (0) )
typedef int ElemType;
typedef int Status;
typedef struct{
ElemType *elem;
int length;
int listsize;
}Sqlist;
Status InitList_Sq(Sqlist *L) {
L->elem = (ElemType *) malloc (LIST_INIT_SIZE * sizeof(ElemType) );
if(!L->elem) exit( OVERFLOW );
L->length=0;
L->listsize = LIST_INIT_SIZE;
return OK;
}
Status ListInsert_Sq ( Sqlist *L, int i, ElemType e ){
ElemType *newbase, *p, *q;
if(i<1 || i>L->length+1) return ERROR;
if(L->length >= L->listsize) {
newbase = (ElemType *)realloc(L->elem, (L->listsize+LISTINCREMENT)*sizeof(ElemType) );
if(!newbase) exit(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 ListDisplay(Sqlist A){
int i=0;
while(i < A.length) {
printf("%5d", A.elem[i]);
i++;
}
}
void Mergelist_Sq(Sqlist La, Sqlist Lb, Sqlist *Lc) {
ElemType *pa, *pb, *pc, *pa_last, *pb_last;
pa = La.elem;
pb = Lb.elem;
Lc->listsize = Lc->length = La.length + Lb.length;
Lc->elem = (ElemType*) malloc (Lc->listsize * sizeof(ElemType));
pc = Lc->elem;
if(!Lc->elem) exit(OVERFLOW);
pa_last = La.elem + La.length - 1;
pb_last = Lb.elem + Lb.length - 1;
while( pa <= pa_last && pb <= pb_last) {
if(*pa <= *pb) *pc++ = *pa++;
else *pc++ = *pb++;
}
while(pa <= pa_last) *pc++ = *pa++;
while(pb <= pb_last) *pc++ = *pb++;
}
void INSERTION_SORT(Sqlist *A)
{
int i, j, key;//key 是关键字，从j开始的部分，是未排序的部分；i 则代表已排序数组最后元素的数组下标
for(j = 1; j != A->length; j++) {
key = A->elem[j];
i = j - 1;
while( i >= 0 && A->elem[i] > key ) {
A->elem[i+1] = A->elem[i];
--i;
}
A->elem[i+1] = key;
}
}
int main( void ) {
int e, i, a, b;
Sqlist A, B, C;
InitList_Sq(&A);
InitList_Sq(&B);
printf("请输入第一个表结点数：");
scanf("%d", &a);
for(i=0; i< a; i++){
printf("请输入第%d个数\n", i+1);
scanf("%d", &e);
ListInsert_Sq(&A,i+1,e);
}
ListDisplay(A);
printf("\n请输入第二个表结点数：");
scanf("%d", &a);
for(i=0; i< a; i++){
printf("请输入第%d个数\n", i+1);
scanf("%d", &e);
ListInsert_Sq(&B,i+1,e);
}
ListDisplay(B);
printf("\n");
INSERTION_SORT(&A);
INSERTION_SORT(&B);
ListDisplay(A);
printf("\n");
ListDisplay(B);
printf("\n两个表的合并：\n");
Mergelist_Sq(A, B, &C);
ListDisplay(C);
printf("\n");
system("PAUSE");
}
/*当两个顺序表合并的时候，最大的问题，可能不是合并本身，而是合并前的排序 ,考虑到
了了们的水平有限，这里就使用了比较简单的插入排序。*/