顺序表的一些基本操作

      # include <stdio.h>
      # include <malloc.h>
      # include <stdlib.h>
      # define LIST_INIT_SIZE 1000
      # define LISTINCREMENT 10
      # define OK 1
      # define ERROR 0
      # define OVERFLOW -1
      typedef struct
      {
     	int *elem;
     	int length;
     	int listsize;
      }SqList;
      int InitList_Sq(SqList &L)
      {
      	L.elem = (int *)malloc(LIST_INIT_SIZE * sizeof (int));
     	if (!L.elem)
     		exit(OVERFLOW);
      	L.listsize = LIST_INIT_SIZE;
      	L.length = 0;
     	return OK;
      }
      int Create_SqList(SqList &L)
      {
     	int i,n;
     	printf("请输入您要创建顺序表元素的个数:");
     	scanf("%d",&n);
     	for (i=0; i<n; i++)
      	{
     		scanf("%d",&L.elem[i] );
      	}
      	L.length = n;
     	return OK;
      }
      void Display(SqList L)
      {
     	int i;
     	for (i=0; i<L.length; i++)
      	{
     		printf("%4d",L.elem [i]);
      	}
     	printf("\n");
      }
      void MergeList_Sq(SqList La, SqList Lb, SqList &Lc)
      {
     	int *pa,*pb,*pc;
     	int *pa_last,*pb_last;
      	pa = La.elem;
      	pb = Lb.elem;
      	Lc.listsize = Lc.length = La.length+Lb.length;
      	pc = Lc.elem = (int *)malloc(Lc.listsize*sizeof(int));
     	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++;
      }
      int ListInsert_Sq(SqList &L, int i, int e)
      {
     	int *p,*q,*newbase;
     	if (i<0 || i>L.length +1)
     		return ERROR;
     	if(L.length >L.listsize )
      	{
      		newbase = (int *)realloc(L.elem ,(L.listsize + LISTINCREMENT) * sizeof (int));
     		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;
      }
      int ListDelete_Sq(SqList &L, int i, int &e)
      {
     	int *p,*q;
     	if (i<0 || i>=L.length )
     		return ERROR;
      	p = &L.elem [i-1];
      	e = *p;
     	printf("您删除的元素是: %d\n",e);
      	q = L.elem + L.length -1;
     	for (++p; p<=q; ++p)
      	{
      		*(p-1) = *p;
      	}
      	--L.length ;
     	return OK;
      }
      int GetElem(SqList L,int i,int &e)
      {
     	if(i<1 || i>L.length)
     		return ERROR;
      	e=*(L.elem+i-1);
      return OK;
      }
      int equal(int e1,int e2)
      {
     	if(e1==e2)
     		return OK;
     	else
     		return ERROR;
      }
      int LocateElem_Sq(SqList L, int e,int (*compare)(int, int))
      {
     	int i;
     	int *p;
      	i = 1;
      	p = L.elem;
     	while (i <= L.length && !(*compare)(*p++, e))
      		++i;
     	if (i <= L.length)
     		return i;
     	else
     		return 0;
      }
      void DifferList(SqList La,SqList Lb,SqList &Le)//实现两个集合的差集
      {
     	int La_len,Lb_len,Le_len,i;
     	int e;
      	La_len = La.length;
      	Lb_len = Lb.length;
      	Le_len = Le.length ;
     	for (i=1; i<=La_len; i++)
      	{
      		GetElem(La, i, e);
     		if (!LocateElem_Sq(Lb, e, equal))
      			ListInsert_Sq(Le, ++Le_len, e);
      	}
      }
      void Union(SqList &La, SqList Lb) {
     	int La_len,Lb_len,i;
     	int e;
      	La_len = La.length;
      	Lb_len = Lb.length;
     	for (i=1; i<=Lb_len; i++)
      	{
      		GetElem(Lb, i, e);
     		if (!LocateElem_Sq(La, e, equal))
      			ListInsert_Sq(La, ++La_len, e);
      	}
      }
      void InferList(SqList La,SqList Lb,SqList &Ld)//实现两个集合的交集
      {
     	int *pa,*pb,*pd;
         pa=La.elem;//pa指向第一个元素
         pb=Lb.elem;//pb指向第二个元素
       int i,j;
         pd=Ld.elem=(int *)malloc(Ld.listsize*sizeof(int));//pd分配空间
         Ld.length=0;
        for(i=0;i<La.length;i++)
         {
      for(j=0;j<Lb.length;j++)
       {
      if(La.elem[i]==Lb.elem[j])
       {
       Ld.elem[Ld.length]=La.elem[i];
       Ld.length++;
       }
       }
         }
      }
      int main(void)
      {
     	int i,e;
      	SqList L;
      	SqList La,Lb,Lc,Ld,Le;
      	InitList_Sq(L);
      	InitList_Sq(La);
      	InitList_Sq(Lb);
      	InitList_Sq(Lc);
      	InitList_Sq(Ld);
      	InitList_Sq(Le);
     	printf(" ------------------------------------------------------------------------\n");
     	printf(" | 欢 迎 使 用 本 系 统! |\n");
     	printf(" | 制 作 人 ：风尘三侠 |\n");
     	printf(" | 1:建立一个顺序表 5:求两个顺序表的差集 |\n");
     	printf(" | 2:插入一个元素 6:求两个顺序表的并集 |\n");
     	printf(" | 3:删除一个元素 7:求两个顺序表的交集 |\n");
     	printf(" | 4:求两个顺序表的归并 8: 退出本系统 |\n");
     	printf(" ------------------------------------------------------------------------\n");
     	do{
     	printf("请选择您要执行的操作:");
     	scanf("%d",&i);
     	switch(i)
      	{
     	case 1:
      		{
      			Create_SqList(L);
     			printf("您创建的顺序表是:");
      			Display(L);
     			break;
      		}
     	case 2:
      		{
     			printf("请先创建一个顺序表!\n");
      			Create_SqList(L);
     			printf("您创建的顺序表是:");
      			Display(L);
     			printf("请输入您要插入的元素:");
     			scanf("%d",&e);
     			printf("请输入您要插入元素的位置:");
     			scanf("%d",&i);
      			ListInsert_Sq(L,i,e);
     			printf("插入元素后的顺序表是:");
      			Display(L);
     			break;
      		}
     	case 3:
      		{
     			printf("请先创建一个顺序表!\n");
      			Create_SqList(L);
     			printf("您创建的顺序表是:");
      			Display(L);
     			printf("请输入您要删除元素的位置:");
     			scanf("%d",&i);
      			ListDelete_Sq(L,i,e);
     			printf("删除元素后的顺序表是:");
      			Display(L);
     			break;
      		}
     	case 4:
      		{
     			printf("请创建第一个顺序表!\n");
      			Create_SqList(La);
     			printf("您创建顺序表是:");
      			Display(La);
     			printf("请创建第二个顺序表!\n");
      			Create_SqList(Lb);
     			printf("您创建顺序表是:");
      			Display(Lb);
     			printf("两顺序表归并后的顺序表是:");
      			MergeList_Sq(La,Lb,Lc);
      			Display(Lc);
     			break;
      		}
     	case 5:
      		{
     			printf("请创建第一个顺序表!\n");
      			Create_SqList(La);
     			printf("您创建顺序表是:");
      			Display(La);
     			printf("请创建第二个顺序表!\n");
      			Create_SqList(Lb);
     			printf("您创建顺序表是:");
      			Display(Lb);
     			printf("两顺序表的差集是:");
      			DifferList(La,Lb,Le);
      			Display(Le);
     			break;
      		}
     	case 6:
      		{
     			printf("请创建第一个顺序表!\n");
      			Create_SqList(La);
     			printf("您创建顺序表是:");
      			Display(La);
     			printf("请创建第二个顺序表!\n");
      			Create_SqList(Lb);
     			printf("您创建顺序表是:");
      			Display(Lb);
     			printf("两顺序表的并集是:");
      			Union(La,Lb);
      			Display(La);
     			break;
      		}
     	case 7:
      		{
     			printf("请创建第一个顺序表!\n");
      			Create_SqList(La);
     			printf("您创建顺序表是:");
      			Display(La);
     			printf("请创建第二个顺序表!\n");
      			Create_SqList(Lb);
     			printf("您创建顺序表是:");
      			Display(Lb);
     			printf("两顺序表的交集是:");
      			InferList(La,Lb,Ld);
      			Display(Ld);
     			break;
      		}
     	case 8:
      		{
     			exit(0);
      		}
     	default:
      		{
     			printf("您的输入有误，请重新输入!\n!");
     			break;
      		}
      	}
      	}while(i!=8);
     		return 0;
      }
  
 

文章来源: blog.csdn.net，作者：悦来客栈的老板，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq523176585/article/details/6819019