顺序表的一些基本操作
【摘要】
# 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 *e...
-
# 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
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）