//數組實作線性表(順序表)
struct node
{
ElemType data[MAXSIZE]; //存放線性表的數組
int length; //線性表的長度
};
typedef struct node SeqList;
//順序表的初始化(置空)
void SeqListInit(SeqList L)
{
L.length = ;
}
//順序表的長度
int SeqListLength(SeqList L)
{
return L.length;
}
//順序表的取元素操作
ElemType SeqListGet(SeqList L, int i)
{
if( (i>=) && (i<=L.length) ) //判斷是否合法
return L.data[i-];
else
{
printf("i值不合法");
exit();
}
}
//exit(0)是一個庫函數,它使程式立即正常終止。如果參數值為0,則認為是正常退出,如果參數值為非零,則認為是非正常退出,說明存在着執行錯誤。
//順序表的定位操作
int SeqListLocation(SeqList L, ElemType e)
{
int i =;
while( (i<=L.length) && (e!=L.data[i-]) )
i++;
if(i<=L.length)
return i; //傳回元素e在順序表中的位置
else
{
printf("此元素不在表中");
return ;
}
}
//順序表的求前驅操作
ElemType SeqListPrior(SeqList L, ElemType e)
{
int i = SeqListLocation(L,e);
if(==i) //先判斷e是否為第一個元素
{
printf("第一個元素沒有前驅");
exit();
}
else
return L.data[i-];
}
//順序表的後繼操作
ElemType SeqListLater(SeqList L, ElemType e)
{
int i = SeqListLocation(L,e);
if(L.length == i)
{
printf("最後一個元素沒有後繼");
exit();
}
else
return L.data[i];
}
//順序表的前插操作
void SeqListInsert(SeqList L, int i, ElemType b)
{
if(L.length == MAXSIZE) //表滿
{
printf("表已滿,無法進行插入操作\n");
exit();
}
if( (i<) || (i>L.length+) ) //i值不合适
{
printf("i值不合适\n");
exit();
}
int j;
for(j=L.length-; j>i-; j--) //移出插入元素的位置
L.data[j+] = L.data[j];
L.data[i-] = b;
L.length++;
}
//順序表的删除操作
void SeqListDel(SeqList L, int i)
{
if( (i<) || (i>L.length) ) //i值不合法
{
printf("i不合法");
exit();
}
int j;
for(j=i; j<=L.length-; j++)
L.data[j-] = L.data[j];
L.length--;
}
//順序表的判空操作
bool SeqListEmpty(SeqList L)
{
return !L.length; //檢視變量length的值是否為0,為0傳回true,否則傳回false
}
//順序表的周遊操作
void SeqListTraverse(SeqList L)
{
int i;
if(SeqListEmpty(L))
printf("隻是一個空表");
else
for(i=; i<=L.length; i++)
printf("%d", L.data[i-]);
}
//線性表的合并:直接合并,儲存合并
//直接合并:将存在于線性表Lb但不存在于線性表La的元素插入La中
void SeqListUnion(SeqList La, SeqList Lb)
{
int n,i;
n = SeqListLength(La);
for(i=; i<=SeqListLength(Lb); i++)
{
ElemType x = SeqListGet(Lb, i);
if(SeqListLocation(La,x) == )
{
SeqListInsert(La, n+, x);
n++;
}
}
}
//儲存合并:兩個都是有序的線性表,合并成一個新的線性表,新的線性表仍然是有序的
void SeqListMerge(SeqList La, SeqList Lb, SeqList Lc)
{
SeqListInit(Lc);
int i =; int j =; int k = ;
while( (i<=SeqListLength(La)) && (j<=SeqListLength(Lb)) )
{
if( SeqListGet(La,i) <= SeqListGet(Lb,j) )
{
SeqListInsert(Lc, k+, SeqListGet(La,i));
k++; i++;
}
else
{
SeqListInsert(Lc, k+, SeqListGet(Lb,j));
k++; i++;
}
}
while( i<=SeqListLength(La) ) //将La中剩餘的元素插入到Lc中
{
SeqListInsert(Lc, k+, SeqListGet(La,i));
k++; i++;
}
while( j<=SeqListLength(Lb) ) //将Lb中剩餘的元素插入到Lc中
{
SeqListInsert(Lc, k+, SeqListGet(Lb,j));
k++; j++;
}
}
建立一個順序表,使用者通過輸入個數和一組非遞減順序的數,即順序表按照非遞減順序排列,對順序表進行建立,删除指定位置的數,查找指定位置的數,插入一個數字功能。程式代碼如下:
#include "stdio.h"
#include "stdlib.h"
#define listsize 100
typedef struct{
int data[listsize];
int length;
}Seqlist;
void main()
{
void createlist(Seqlist *l,int n);
void printlist(Seqlist *l,int n);
void locateElem(Seqlist *l,int n);
void listinsert(Seqlist *l,int i,int n);
void listdelete(Seqlist *l,int i,int n);
int n;
int i=;
Seqlist l;
l.length=;
printf("請輸入線性表長度:");
scanf("%d",&n);
createlist(&l,n);
printlist(&l,n);
locateElem(&l,n);
listinsert(&l,i,n);
listdelete(&l,i,n);
printf("\n");
}
//建立順序表
void createlist(Seqlist *l,int n)
{
int i;
printf("請輸入順序表元素:\n");
for(i=;i<n;i++)
{
scanf("%d",&l->data[i]);
l->length=n;
}
}
//輸出順序表
void printlist(Seqlist *l,int n)
{
int i;
printf("順序表為:");
for(i=;i<n;i++)
{
printf("%d ",l->data[i]);
}
}
//查找元素
void locateElem(Seqlist *l,int n)
{
int i=,*p;
p=l->data;
printf("\n請輸入要查找的元素n:");
scanf("%d",&n);
while(i<=l->length&&(*p++!=n)) ++i;
if(i<=l->length)
printf("要查找的數的位置為:%d",i);
}
//插入元素
void listinsert(Seqlist *l,int i,int n)
{
int *q,*p;
printf("\n請輸入要插入的數:");
scanf("%d",&n);
if(l->length==)
{
l->data[]=n;
++l->length;
}
q=&(l->data[]);
while((*q<=n)&&(q<=&(l->data[l->length-])))
{
++q;
}
++l->length;
for(p=&(l->data[l->length-]);p>=q;--p)
{
*(p+)=*p;
*p=n;
}
printf("輸出新表:\n");
for(i=;i<l->length;i++)
{
printf("%d ",l->data[i]);
}
}
//删除元素
void listdelete(Seqlist *l,int i,int n)
{
int *p,*q;
printf("\n請輸入要删除的數的位置:");
scanf("%d",&i);
if(i<||i>l->length)
printf("删除元素失敗!");
p=&l->data[i-];
n=*p;
q=l->data+l->length-;
for(++p;p<=q;++p)
{
*(p-)=*p;
--l->length;
}
for(i=;i<l->length+;i++)
{
printf("%d ",l->data[i]);
}
}