#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<n;i++)
scanf("%d",&(l->elem[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<j;i++,j--)
{
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");
}
}
}