線性表之順序表操作

求後繼是指：輸入一個元素值（而不是位置），求該元素在順序表中的直接後繼元素值。

注意：對每個功能進行測試時，要求把不合法的情況也測試一下。具體見下面的測試用例。

（3）驗收/測試用例

通過菜單調用各個操作，測試點：

⦁ 沒有初始化前進行其他操作，程式是否能控制住；即，如果沒有初始化線性表，其他的功能是無法正常進行的，如果選擇進行其他操作，要提示先進行初始化；

⦁ 初始化一個順序表（初始化順序表，是指初始化一個空的線性表，裡面的元素個數是0）；

⦁ 插入資料(位置， 資料)，要測插入位置不合法的情況（0,1）、（2,1），正确插入3個資料（1，20）、（1，10）、（3,30）；

⦁ 顯示順序表中的資料，螢幕輸出10， 20， 30；

⦁ 判空，螢幕輸出順序表非空；

⦁ 輸出順序表長度，螢幕輸出3；

⦁ 擷取指定位置元素，要測指定位置在【1，3】範圍之外的情況和之内的情況；

⦁ 定位，輸入：40， 輸出：不存在，輸入20，輸出位置為2；

⦁ 求直接前驅，要測求第一個元素的前驅、不存在順序表中的元素的直接前驅，其他元素的直接前驅；輸入10，輸出：第一個元素沒有前驅，輸入20，輸出前驅是10，輸入40，輸出該元素不存在；

⦁ 求直接後繼，要測最後一個元素的後繼、不存在順序表中的元素的直接後繼，其他元素的直接後繼；同上求前驅；

⦁ 删除，要測位置在【1，3】範圍之外的情況和之内的情況；

⦁ 清空操作後再測長度，判斷是否為空；

⦁ 銷毀順序表，銷毀線性表之後還能不能做插入，删除等操作，如果選其他操作，就要提示線性表已經銷毀不存在；

⦁ 測試合并操作，第一個線性表中的元素是（2,3,4，5），第二個線性表中的内容是（1,4,6,7，8,9），合并後的結果，請輸出。

#include<stdio.h>

#include<stdlib.h>

#define LIST_INIT 100

#define LISTINCREMENT 10

#define ERROR 0

#define OK 1

typedef int status ;

typedef int ElemType;

typedef struct{

ElemType *elem;

int length;

int listsize;

}list;

void mnue();

status intlist(list &); //1

void destroylist(list &); //2

void clearlist(list &); //3

status listempty (list &p); //4

status listlength(list &p); //5

status getelem(ElemType,list &p); //6

status listlocal(ElemType,list &p); //7

status priorelem(ElemType,list &p); //8

status nextelem(ElemType , list &p); //9

status listinsert(ElemType,status,list &p);//10

void listdelete(ElemType,list &p); //11

void listvisit(list &p); //12

void listsum(list,list,list&); //13

int main()

{

list l;

l.elem=NULL;

int select,m,n,i;

int charu;

while(1)

{

mnue();

printf("\n請輸入你的選擇是:\n");

scanf("%d",&select);

if(select>14)

printf(“輸入不合法，請重試。\n”);

else if(select<=0)

{

printf(“已退出！\n”);

return 0;

}

else if(select>0)

{

switch(select)

{

case 1:

m=intlist(l);

if(m= =0) printf(“建立失敗。\n”);

else printf(“建立成功。\n”);

break;

case 2:

destroylist(l);

break;

case 3:

clearlist(l);

printf(“清空完成。\n”);

break;

case 4:

m=listempty(l);

if(m==0) printf(“線性表為空。\n”);

else printf(“線性表不為空。\n”);

break;

case 5:

m=listlength(l);

printf(“線性表的長度為%d。\n”,m);

break;

case 6:

printf(“輸入想擷取的元素位置：\n”);

scanf("%d",&m);

n=getelem(m,l);

printf(“元素為%d：\n”,n);

break;

case 7:

printf(“輸入想查詢的元素：\n”);

scanf("%d",&m);

n=listlocal(m,l);

printf(“元素位置為%d：\n”,n);

break;

case 8:

printf(“輸入元素：\n”);

scanf("%d",&m);

n=priorelem(m,l);

printf(“元素前驅為%d：\n”,n);

break;

case 9:

printf(“輸入元素：\n”);

scanf("%d",&m);

n=nextelem(m, l);

printf(“元素後繼為%d：\n”,n);

break;

case 10:

printf(“輸入元素、位置：\n”);

scanf("%d %d",&m,&n);

charu= listinsert(m,n,l);

break;

case 11:

printf(“所需删除元素：\n”);

scanf("%d",&m);

listdelete(m,l);

break;

case 12:

listvisit(l);

break;

case 13:

list La;list Lb;list L;

La.elem=(ElemType )malloc(4sizeof(ElemType));

Lb.elem=(ElemType )malloc(4sizeof(ElemType));

L.elem=(ElemType )malloc(8sizeof(ElemType));

printf(“輸入la的4個元素：\n”);

for(i=0;i<4;i++)

{

scanf("%d",&La.elem[i]);

}

printf(“輸入lb的4個元素：\n”);

for(i=0;i<4;i++)

{

scanf("%d",&La.elem[i]);

}

listsum(La,Lb,L);

break;

}

}

}

return 0;

}

void mnue()

{

printf(“1-----初始化一個線性表\n”);

printf(“2-----銷毀線性表\n”);

printf(“3-----清空線性表\n”);

printf(“4-----判斷線性表是否為空\n”);

printf(“5-----求線性表長度\n”);

printf(“6-----擷取線性表中指定位置元素\n”);

printf(“7-----擷取線性表元素的位置\n”);

printf(“8-----求前驅\n”);

printf(“9-----求後繼\n”);

printf(“10-----線性表指定位置插入元素\n”);

printf(“11-----删除線性表指定位置元素\n”);

printf(“12-----顯示線性表\n”);

printf(“13-----合并兩個非遞減有序的線性表\n”);

printf(“14-----退出，輸入一個負數\n”);

}

status intlist(list &p) //1

{

p.elem=(ElemType )malloc(LIST_INITsizeof(ElemType));

if(!p.elem) return ERROR;

p.length=0;

p.listsize=LIST_INIT;

return OK;

}

void destroylist(list &p) //2

{

free(p.elem);

p.length=0;

p.listsize=0;

p.elem=NULL;

printf(“銷毀完成。\n”);

}

void clearlist(list &p) //3

{

p.length=0;

}

status listempty (list &p)//4

{

if(p.length= =0)

return ERROR;

else return OK;

}

status listlength(list &p)//5

{

return p.length;

}

status getelem(ElemType m,list &p)//6

{

if(m<0||m>=p.length)

printf(“不在長度範圍内請再次輸入：\n”);

return p.elem[m-1];

}

status listlocal(status m,list &p)//7

{

for (int i=0;i<p.length;i++)

{

if(m= =p.elem[i])

return i;

}

printf(“沒有此元素，不好意思請再次輸入：\n”);

return 0;

}

status priorelem(ElemType m,list &p)//8

{

for (int i=0;i<p.length;i++)

{

if((m= =p.elem[i])&&i= =0)

printf(“此元素沒有前驅，請再次輸入：\n”);

if(m= =p.elem[i])

return p.elem[i-1];

}

printf(“沒有此元素，不好意思請再次輸入：\n”);

return 0;

}

status nextelem(ElemType m, list &p)//9

{

for (int i=0;i<p.length;i++)

{

if((m = =p.elem[i]) & & i= =p.length)

printf(“此元素沒有後繼，請再次輸入：\n”);

if(m= =p.elem[i])

return p.elem[i+1];

}

printf(“沒有此元素，不好意思請再次輸入：\n”);

return 0;

}

status listinsert(ElemType m,ElemType n,list &p) //10

{

if(n<0||n>p.length+1)

{

printf(“不在長度範圍内請再次輸入。\n”);

return ERROR;

}

if(p.length>=p.listsize)

{

p.elem=(ElemType *)realloc(p.elem,(p.listsize+LISTINCREMENT)*sizeof(ElemType)) ;

if(!p.elem)

{

printf(“再次申請線性表失敗！\n”);

return ERROR;

}

p.listsize+=LISTINCREMENT;

}

p.elem[p.length]=m;

++p.length;

printf(“插入完成，完美，是我心中的大佬。\n”);

return OK;

}

void listdelete(ElemType m,list &p)

{

for (int i=0;i<p.length;i++)

{

if(m==p.elem[i])

{

p.elem[i]=p.elem[i+1];

}

else

{

printf(“沒有此元素，請再次輸入：\n”);

}

printf(“删除成功！\n”);

}

}

void listvisit(list &p)

{

printf(“此線性表為：\n”);

for (int i=0;i<p.length;i++)

{

printf("%d \n",p.elem[i]);

}

–p.length;

}

void listsum(list La,list Lb,list &Lc)

{

int i;int j;

list pa;list pb;list pc;

pa.elem=(ElemType )malloc(4sizeof(ElemType));

pb.elem=(ElemType )malloc(4sizeof(ElemType));

pa.elem=La.elem;

pb.elem=Lb.elem;

Lc.listsize=La.length+Lb.length;

Lc.length=La.length+Lb.length;

pc.elem=Lc.elem;

pc.elem=(ElemType )malloc(Lc.listsizesizeof(ElemType));

if(!pc.elem)

printf(“建立lc線性表失敗！”);

for(i=0;i<pa.length;i++)

{

pc.elem[i]=pa.elem[i];

}

for(i=pa.length,j=0;i<pc.length,j<pb.length;i++,j++)

{

pc.elem[i]=pb.elem[j];

}

printf(“合并線性表成功.”);

}