數(shù)據(jù)結(jié)構(gòu)-實(shí)驗(yàn)1-線性表的基本操作

1、實(shí)驗(yàn)1 線性表的基本操作一、 需求分析目的：掌握線性表運(yùn)算與存儲(chǔ)概念，并對(duì)線性表進(jìn)行基本操作。1.初始化線性表；2.向鏈表中特定位置插入數(shù)據(jù)；3.刪除鏈表中特定的數(shù)據(jù)；4.查找鏈表中的內(nèi)容；5.銷毀單鏈表釋放空間；二、概要設(shè)計(jì)l 基礎(chǔ)題主要函數(shù)：初始化線性表InitList（List* L，int ms）向順序表指定位置插入元素InsertList（List* L，int item，int rc）刪除指定元素值的順序表記錄DeleteList1(List* L,int item)刪除指定位置的順序表記錄 DeleteList2（List* L,int rc）查找順序表中的元素 FindList

2、（List L，int item）輸出順序表元素OutputList（List L）實(shí)驗(yàn)步驟：1，初始化順序表2，調(diào)用插入函數(shù)3，在順序表中查找指定的元素4，在順序表中刪除指定的元素5，在順序表中刪除指定位置的元素6，遍歷并輸出順序表l 提高題要求以較高的效率實(shí)現(xiàn)刪除線性表中元素值在x到y(tǒng)（x和y自定義）之間的所有元素方法：按順序取出元素并與x、y比較，若小于x且大于y，則存進(jìn)新表中。編程實(shí)現(xiàn)將兩個(gè)有序的線性表進(jìn)行合并，要求同樣的數(shù)據(jù)元素只出現(xiàn)一次。方法：分別按順序取出L1，L2的元素并進(jìn)行比較，若相等則將L1元素放進(jìn)L中，否則將L 1，L2元素按順序放進(jìn)L。l 本程序主要包含7個(gè)函數(shù)主函數(shù)m

3、ain()初始化線性表InitList（List* L，int ms）向順序表指定位置插入元素InsertList（List* L，int item，int rc）刪除指定元素值的順序表記錄DeleteList1(List* L,int item)刪除指定位置的順序表記錄 DeleteList2（List* L,int rc）查找順序表中的元素 FindList（List L，int item）輸出順序表元素OutputList（List L）提高題的程序void Combine(List* L1,List* L2,List* L)void DeleteList3(List* L,int x,

4、int y)二、 詳細(xì)設(shè)計(jì)初始化線性表InitList（List* L，int ms）void InitList(List* L,int ms)L->list=(int*)malloc(LIST_INIT_SIZE*sizeof(int);L->size=0;L->MAXSIZE=LIST_INIT_SIZE;向順序表指定位置插入元素InsertList（List* L，int item，int rc）void InsertList(List* L,int item,int rc)int i;if (L->size>=L->MAXSIZE)L->lis

5、t=(int*)realloc(L->list,(L->MAXSIZE+LISTI)*sizeof(int);L->MAXSIZE+=LISTI;for (i=L->size-1;i>=rc-1;i-)L->listi+1=L->listi;L->listrc-1=item;L->size+;刪除指定元素值的順序表記錄DeleteList1(List* L,int item)void DeleteList1(List* L,int item)int i,j;for (i=0;i<L->size;i+)if (L->list

6、i=item)break;for (j=i;j<L->size;j+)L->listj=L->listj+1;L->size-;刪除指定位置的順序表記錄 DeleteList2（List* L,int rc）void DeleteList2(List* L,int rc)int i;for (i=rc-1;i<L->size;i+)L->listi=L->listi+1;L->size-;查找順序表中的元素void FindList(List* L,int item)int i;for (i=0;i<L->size;i+)

7、if (L->listi=item)break;if (L->size=i)printf("找不到n");elseprintf("第%d個(gè)元素為%dn",i+1,item);輸出順序表元素OutputList（List L）void OutputList(List* L)int i;for (i=0;i<L->size;i+)printf("%d ",L->listi);printf("n");刪除x到y(tǒng)之間的所有元素void DeleteList3(List* L,int x,int

8、 y)int i,j,temp;if (x>y)temp=x;x=y;y=temp;for (i=0,j=0;i<L->size;i+)if (L->listi<x | L->listi>y)L->listj=L->listi;j+;L->size=j;將兩個(gè)有序的線性表進(jìn)行合并void Combine(List* L1,List* L2,List* L)int i,j,k,temp;if (L1->size>L2->size)temp=L2->size;elsetemp=L1->size;i=0,j=0

9、,k=0;while(1)if (i=L1->size | j=L2->size)break;if (L1->listi<L2->listj)L->listk=L1->listi;k+;i+;else if (L1->listi>L2->listj)L->listk=L2->listj;k+;j+;elseL->listk=L2->listj;k+;j+;i+;if (i=L1->size)for (i=j;i<L2->size;i+,k+)L->listk=L2->listi;elsefor (j=i;j<L1->size;j+,k+)L->listk=L1->listj;L->size=k;三、 調(diào)試分析體會(huì)：線性表內(nèi)數(shù)據(jù)都是順序排放所以實(shí)驗(yàn)中比較容易寫出程序時(shí)間復(fù)雜度：初始化線性表InitList（List* L，int ms） (1)向順序表指定位置插入元素InsertList（List* L，int item，int rc） (n)刪除指定元素值的順序表記錄DeleteList1(List* L,int item) (