#include
#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define list_init_size 100 //线性表存储空间的初始分配量
#define list_increament 10 //线性表存储空间的分配增量
typedef int elemtype;
struct node
{
elemtype * elem;
int length;
int listsize;
};
typedef struct node sqlist;
//初始化一个空的顺序表L，若初始化成功返回1，否则返回0。
int initlist_sq(sqlist *l,int n)
{
int i;
l->elem=(elemtype *)malloc(list_init_size*sizeof(elemtype));
if(!(l->elem))
{
printf("内存分配失败.\n");
return ERROR;
}
printf("请输入线性表中的元素:\n");
for(i=0;i
printf("\n");
l->length=n;
l->listsize=list_init_size;
return OK;
}
//打印线性表
void print_sq(sqlist *l)
{
int i,j=1;
for(i=0;ilength;i++)
{
printf("%4d",l->elem[i]);
j++;
if(j%10==0)
printf("\n");
}
printf("\n该线性表的长度是%d.\n",l->length);
printf("\n该线性表的最大容量是%d.\n",l->listsize);
}
//从线性表L中取第i个元素，并由e带出。若取元素成功则返回1，取元素不成功返回0。
int getelem_sq(sqlist *l,int i,elemtype *e)
{
if(i>0&&ilength)
{
*e=l->elem[i-1];
return OK;
}
else
{
printf("输入的位置有问题\n");
return ERROR;
}
}
//判断线性表L是否为空表，若是空表返回1，若不是空表返回0。
int listempty_sq(sqlist *l)
{
if(l->length>0)
{
printf("该线性表不为空.\n");
return ERROR;
}
else
{
printf("该线性表为空.\n");
return OK;
}
}
//清空一个线性表L，若清空成功返回1。
int clearlist_sq(sqlist *l)
{
l->length=0;
printf("该线性表已清空.\n");
return OK;
}
//在线性表L中找cure的前驱结点并由pre_e带出。
void priorelem_sq(sqlist *l,int cur_e,elemtype *pre_e)
{
int i;
int flag=0;
if(l->elem[0]==cur_e)
{
printf("第一个元素没有前驱结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*pre_e=l->elem[i-1];
printf("该线性表中第%d个元素%d的前驱结点是%d\n",i+1,cur_e,*pre_e);
flag++;
}
else
continue;
}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);
}
//在线性表L中找cure的后继结点，若有则由next_e带出。
void nextelem_sq(sqlist *l,int cur_e,elemtype *next_e)
{
int i;
int flag=0;
if(l->elem[l->length-1]==cur_e)
{
printf("最后一个元素没有后继结点.\n");
flag=1;
}
else
{
for(i=1;ilength;i++)
{
if(l->elem[i]==cur_e)
{
*next_e=l->elem[i+1];
printf("该线性表中第%d个元素%d的后继结点是%d\n",i+1,cur_e,*next_e);
flag++;
}
else
continue;
}
}
if(flag==0)
printf("在该线性表中找不见元素%d\n",cur_e);
}
//返回线性表的长度
int listlength_sq(sqlist *l)
{
return(l->length);
}
//在线性表L的第i个位置插入一个数据元素e。插入不成功返回0。
int listinsert_sq(sqlist *l,int i,elemtype e)
{
int j;
elemtype * newbase;
if(il->length+1)
{
printf("插入的位置错误\n");
return ERROR;
}
if(l->length>=l->listsize)
{
newbase=(elemtype *)realloc(l->elem,(l->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("内存在扩充时失败");
return ERROR;
}
l->elem=newbase;
l->listsize=l->listsize+list_increament;
}
for(j=l->length-1;j>=i-1;j--)
l->elem[j+1]=l->elem[j];
l->elem[i-1]=e;
l->length++;
return OK;
}
//删除线性表L中的第i个数据元素,并由e带出删除的元素，若删除不成功返回0。
int listdelete_sq(sqlist *l,int i,elemtype *e)
{
int j;
if(il->length)
{
printf("输入的位置有问题\n");
return ERROR;
}
*e=l->elem[i-1];
for(j=i;jlength-1;j++)
l->elem[j-1]=l->elem[j];
l->length--;
return OK;
}
//将现有的线性表置逆。
void convert_sq(sqlist *l)
{
int i,j,t;
for(i=0,j=l->length-1;i
t=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=t;
}
}
//将非递减的有序表La和Lb归并为一个新的非递减的有序表Lc。
int mergelist_sq(sqlist *la,sqlist *lb,sqlist *lc)
{
elemtype *pa,*pb,*pc,*pa_last,*pb_last;
pa=la->elem;
pb=lb->elem;
pa_last=la->elem+la->length-1;
pb_last=lb->elem+lb->length-1;
lc->listsize=lc->length=la->length+lb->length;
lc->elem=(elemtype*)malloc((la->length+lb->length)*sizeof(elemtype));
pc=lc->elem;
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++;
return OK;
}
//La和Lb中的元素分别表示两个集合A和B，求一个新的集合A=（A-B）∪(B-A)。
int unionl(sqlist *la,sqlist *lb)
{
int i,j;
elemtype *newbase;
if(la->length+lb->length>la->listsize)
newbase=(elemtype*)realloc(la->elem,(la->listsize+list_increament)*sizeof(elemtype));
if(!newbase)
{
printf("\na表的长度不够，且内存分配失败");
return ERROR;
}
for(i=1;ilength;i++)
{
for(j=1;jlength;j++)
if(lb->elem[i-1]==la->elem[j-1])
break;
else
continue;
if(j>la->length)
{
la->elem[j-1]=lb->elem[i-1];
la->length++;
}
}
return OK;
}
void deld_sq(sqlist *l)
{
int i,j,k;
elemtype s;
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]==l->elem[j])
{
for(k=j;klength-2;k++)
l->elem[k]=l->elem[k+1];
l->length--;
j--;
}
for(i=0;ilength-2;i++)
for(j=i+1;jlength-1;j++)
if(l->elem[i]>l->elem[j])
{
s=l->elem[i];
l->elem[i]=l->elem[j];
l->elem[j]=s;
}
}
//在线性表L中查找与k相匹配的元素，返回在表中的位置。
void sqsearch(sqlist *l,int k)
{
int i;
int flag=0;
for(i=0;ilength-1;i++)
{
if(l->elem[i]==k)
{
printf("元素%d的位置是%d!\n",k,i+1);
flag++;
}
else
continue;
}
if(flag==0)
printf("线性表中不存在元素:%d!\n",k);
}
int cmp(int a,int b)
{
if(a>b)
return 1;
else
return 0;
}
//在线性表L中找第一个与e满足compare关系的元素的位序。
void locateelem_sq(sqlist *l,int e, int (*compare)(int a,int b))
{
int i=1;
int flag=0;
for(i=1;ilength;i++)
{
if(compare(l->elem[i-1],e))
{
printf("比%d大的元素的位序为:%d\n",e,i);
flag++;
}
else
continue;
}
if(flag==0)
printf("不存在比%d大的元素!\n",e);
}
void showmenu()
{
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
printf(" * 选择响应的操作 *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * **\n");
printf(" * *\n");
printf(" * [0] 显 示 该 表 [99] 退 出 程 序 *\n");
printf(" * [1] 读 取 元 素 [ 2] 插 入 元 素 [ 3] 删 除 元 素 *\n");
printf(" * [ 4] 寻 找 前 驱 [ 5] 寻 找 后 继 [ 6] 返 回 表 长 *\n");
printf(" * [ 7] 置 逆 操 作 [ 8] 合 并 两 表 [ 9] 两 表 并 集 *\n");
printf(" * [10] 判 空 [11] 清 空 [12]有序无重复元素 *\n");
printf(" * [13] 顺 序 检 索 [14] 寻 找 位 序 *\n");
printf(" * *\n");
printf(" * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *\n");
}
void main()
{
int n,m,i,k,cure,select;
elemtype e, pre_e, next_e;
sqlist l,r,la,lb,lc;
printf("请输入你要创建的线性表的长度:");
scanf("%d",&n);
printf("\n");
initlist_sq(&l,n);
printf("你创建的线性表如下:\n");
print_sq(&l);
while(1)
{
showmenu();
printf("请选择响应的操作:");
scanf("%d",&select);
switch(select)
{
case 99:exit(1);
case 0:print_sq(&l);
break;
case 1:
printf("请输入所取元素的位置:\n");
scanf("%d",&i);
if(getelem_sq(&l,i,&e)==1)
printf("线性表中第%d个元素为%d\n",i,e);
break;
case 2:
printf("请输入要插入的位置:\n");
scanf("%d",&i);
printf("请输入要插入的元素:\n");
scanf("%d",&cure);
listinsert_sq(&l,i,cure);
printf("插入操作完成后的线性表是:");
print_sq(&l);
break;
case 3:printf("你要删除哪一个元素：\n");
scanf("%d",&i);
listdelete_sq(&l,i,&e);
printf("你删除的第%d个元素是:%d\n",i,e);
printf("删除操作完成后的线性表是:");
print_sq(&l);
break;
case 4:
printf("请输入要寻找前驱结点的元素:\n");
scanf("%d",&cure);
priorelem_sq(&l,cure,&pre_e);
break;
case 5:
printf("请输入一个元素以便寻找其后继结点:\n");
scanf("%d",&cure);
nextelem_sq(&l,cure,&next_e);
break;
case 6:
printf("该线性表的长度是%d\n",listlength_sq(&l));
break;
case 7:
printf("置逆之前的线性表为：\n");
print_sq(&l);
convert_sq(&l);
printf("置逆之后的线性表为：\n");
print_sq(&l);
break;
case 8:printf("\n请输入你要创建的线性表la的长度:");
scanf("%d",&n);
initlist_sq(&l,n);
printf("\n请输入你要创建的线性表lb的长度:");
scanf("%d",&m);
initlist_sq(&r,m);
mergelist_sq(&l,&r,&lc);
printf("合并后的线性表为:\n");
print_sq(&lc);
break;
case 9:
printf("请输入la的长度n:");
scanf("%d",&n);
initlist_sq(&la,n);
printf("请输入lb的长度m:");
scanf("%d",&m);
initlist_sq(&lb,m);
unionl(&la,&lb);
printf("并集后的la为:\n");
print_sq(&la);
break;
case 10:
listempty_sq(&l);
break;
case 11:
clearlist_sq(&l);
break;
case 12:deld_sq(&l);
printf("\n修改为有序且无重复元素后的线性表为:");
printf("\n");
print_sq(&l);
break;
case 13:
printf("请输入要查找的元素:");
scanf("%d",&k);
sqsearch(&l, k);
break;
case 14:
printf("请输入一个数据元素:\n");
scanf("%d",&cure);
locateelem_sq(&l,cure,cmp);
break;
default:
printf("请选择菜单中的操作,按99退出程序\n");
}
}
}
线性表是逻辑定义，顺序存储或者链式存储是其在内存中的存放形式
顺序存储是以元素存储的空间位置表示元素逻辑关系，数组则是顺序存储中最为简单的形式
链式存储的线性表简称为链表，不过现在只要是链式存储的不管逻辑结构是什么样的都叫链表
开始结点指的是链表的头结点，通常用head表示，终端结点指的是链表的最后一个结点，如果一个结点的指针域next=NULL，那么这个结点就是终端结点，直接前驱是指链表中的某一个结点的上一个结点就是该结点的直接前驱，直接后继（直接后驱）该结点的下一个结点，需要注意的是在单链表中开始结点只有直接后继，终端结点只有直接前驱。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024