數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐指導(dǎo) 課件 1-順序表

第1章

順序表主講教師：張彬連吉首大學(xué)1.1知識(shí)簡(jiǎn)介1.1.1順序表結(jié)構(gòu)

線(xiàn)性表的順序表示稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)或順序映像，把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中，即邏輯上相鄰，物理上也相鄰。順序存儲(chǔ)是用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的元素。1.1知識(shí)簡(jiǎn)介1.1.1順序表結(jié)構(gòu)

如有n個(gè)元素的線(xiàn)性表(a1，a2，…，ai-1，ai，…，an)的順序存儲(chǔ)如下圖所示。12…i-1i…na1a2…ai-1ai

…an

假設(shè)用Loc(ai)表示第i個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，Loc(a1)就表示第一個(gè)數(shù)據(jù)元素的存儲(chǔ)位置，每個(gè)元素占c個(gè)存儲(chǔ)單元，則有：

1.1知識(shí)簡(jiǎn)介1.1.1順序表結(jié)構(gòu)

每個(gè)數(shù)據(jù)元素的存儲(chǔ)位置和起始位置相差一個(gè)常數(shù)，這個(gè)常數(shù)和數(shù)據(jù)元素在線(xiàn)性表中的位序成正比。因此，只要確定了起始位置，線(xiàn)性表中的任一數(shù)據(jù)元素都可以隨機(jī)存取，所以順序表是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示

順序表有兩種表示方式：

靜態(tài)順序表（長(zhǎng)度是固定的）

動(dòng)態(tài)順序表（長(zhǎng)度可以自己定義）1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示

靜態(tài)順序表定義如下：#defineMAXSIZE100//線(xiàn)性表的最大長(zhǎng)度typedefstructSqList{ElemTypeelem[MAXLEN];//存放順序表中的元素intlength;//順序表中元素的個(gè)數(shù)}SqList;

采用這種方式定義順序表時(shí)，表中元素的最大個(gè)數(shù)是確定的，在程序中不能被修改。如有定義SqListL，則L是一個(gè)靜態(tài)順序表，最多可放100個(gè)元素。1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示

動(dòng)態(tài)順序表定義如下：#defineMAXSIZE100//線(xiàn)性表的最大長(zhǎng)度typedefstructSqList{ElemType*elem;//順序表中存放元素空間首地址intlength;//順序表中元素的個(gè)數(shù)intsize;//順序表的大小}SqList;

采用這種方式定義順序表時(shí)，表中元素的最大個(gè)數(shù)可以根據(jù)需要定義，在程序中也可根據(jù)需要進(jìn)行擴(kuò)充。其中size表示順序表可以存儲(chǔ)的數(shù)據(jù)元素個(gè)數(shù)，如果空間不夠時(shí)不考慮擴(kuò)充空間，size可以不定義。1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示

由于elem是指針類(lèi)型，定義SqListL后，順序表L中存放數(shù)據(jù)元素的空間沒(méi)有分配，需要?jiǎng)討B(tài)分配空間。可以定義一個(gè)初始化順序表L的函數(shù)InitSqList(SqList&L)，函數(shù)可以定義如下：intInitSqList(SqList&L){L.elem=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));If(L.elem==NULL)exit(-1);//退出程序L.length=0；//初始長(zhǎng)度為0return1；}1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示

InitSqList()函數(shù)中使用了malloc()函數(shù)動(dòng)態(tài)申請(qǐng)空間，所以在程序結(jié)束之前的某個(gè)位置應(yīng)該將這些內(nèi)存空間釋放，否則會(huì)導(dǎo)致內(nèi)存泄漏。C語(yǔ)言中用free()釋放malloc()申請(qǐng)的內(nèi)存，定義釋放順序表L內(nèi)存的函數(shù)DestroySqList(SqList&L)，函數(shù)可以定義如下：voidDestroySqList(SqList&L)//釋放順序表L中申請(qǐng)的內(nèi)存{if(L.elem!=NULL)//如果elem指向的內(nèi)存沒(méi)有被釋放{free(L.elem);//釋放elem指向的內(nèi)存L.elem=NULL;//釋放內(nèi)存之后，賦值L.elem為NULL}}1.1知識(shí)簡(jiǎn)介1.1.2順序表的表示需要注意的是ElemType是元素類(lèi)型，它是一個(gè)抽象的概念，可以表示任何類(lèi)型的元素。例如線(xiàn)性表中存放整數(shù)，則可在定義之前加入typedefintElemType，元素類(lèi)型就變?yōu)檎停部梢栽诙x順序表的時(shí)候?qū)lemType修改為自己需要的類(lèi)型。1.2實(shí)驗(yàn)?zāi)康?/p>

本章的實(shí)驗(yàn)案例是以順序表作為存儲(chǔ)結(jié)構(gòu)，通過(guò)本章的實(shí)驗(yàn)加深對(duì)順序表的理解，培養(yǎng)以順序表作為線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)解決實(shí)際問(wèn)題的能力，并能分析其時(shí)間和空間復(fù)雜度，同時(shí)鍛煉學(xué)生實(shí)際編程和算法設(shè)計(jì)的能力。1.3實(shí)驗(yàn)范例

一個(gè)班有50個(gè)學(xué)生，每個(gè)學(xué)生的信息有學(xué)號(hào)、姓名和性別，現(xiàn)在有大學(xué)英語(yǔ)和高等數(shù)學(xué)兩門(mén)課程組織了考試，每個(gè)學(xué)生獲得了相應(yīng)的成績(jī)，如下表所示。要求設(shè)計(jì)一個(gè)簡(jiǎn)單的管理系統(tǒng)對(duì)學(xué)生信息進(jìn)行管理。要求用順序表實(shí)現(xiàn)。學(xué)號(hào)姓名性別大學(xué)英語(yǔ)高等數(shù)學(xué)2023001AlanF93882023002DanieM75692023003PeterM56772023004BillF87902023005HelenM79862023006AmyF68751.3實(shí)驗(yàn)范例

初始化順序表：要求建立一個(gè)長(zhǎng)度為0的順序表，用來(lái)存放學(xué)生的信息。1.3.1范例11.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.1范例1

先需要定義順序表類(lèi)型，順序表中每個(gè)元素用來(lái)存儲(chǔ)一個(gè)學(xué)生的信息，需要定義結(jié)構(gòu)體類(lèi)型，ElemType代表該結(jié)構(gòu)體類(lèi)型。然后初始化順序表L，分配能放MAXSIZE學(xué)生信息的空間。初始化時(shí)并沒(méi)有輸入學(xué)生信息，因此將順序表的有效元素個(gè)數(shù)length初始化為0。1.3實(shí)驗(yàn)范例2、算法描述1.3.1范例1

先定義結(jié)構(gòu)體類(lèi)型，包含學(xué)號(hào)、姓名、大學(xué)英語(yǔ)成績(jī)、高等數(shù)學(xué)成績(jī)，結(jié)構(gòu)體定義如下：typedefstructStudent{charNo[8];//學(xué)號(hào)charname[16];//姓名charsex;//性別intenglish;//大學(xué)英語(yǔ)成績(jī)intmath;//高等數(shù)學(xué)成績(jī)}Student;1.3實(shí)驗(yàn)范例2、算法描述1.3.1范例1

在本實(shí)驗(yàn)中當(dāng)空間不夠時(shí)，不考慮追加空間，所以順序表SqList中不需要定義size成員。順序表SqList定義如下：typedefstructSqList{Student*elem;//存放學(xué)生信息空間的首地址

intlength;//存放的學(xué)生人數(shù)}SqList;1.3實(shí)驗(yàn)范例2、算法描述1.3.1范例1

在本實(shí)驗(yàn)中當(dāng)空間不夠時(shí)，不考慮追加空間，所以順序表SqList中不需要定義size成員。順序表SqList定義如下：或者：typedefStudentElemType;typedefstructSqList{ElemType*elem;//存放學(xué)生信息空間的首地址

intlength;//存放的學(xué)生人數(shù)}SqList;1.3實(shí)驗(yàn)范例2、算法描述1.3.1范例1

順序表類(lèi)型定義好之后，定義函數(shù)InitSqList(SqList&L)對(duì)順序表L進(jìn)行初始化。該函數(shù)先新申請(qǐng)可以存放MAXSIZE個(gè)Student變量（或?qū)ο螅┑目臻g，將順序表L的初始長(zhǎng)度length設(shè)置為0。InitSqList()函數(shù)可以定義如下：intInitSqList(SqList&L)//初始化順序表L{L.elem=(Student*)malloc(MAXSIZE*sizeof(Student));if(L.elem==NULL)exit(-1);//退出程序L.length=0;//初始長(zhǎng)度為0return1;}1.3實(shí)驗(yàn)范例3、算法分析1.3.1范例1

用InitSqList()函數(shù)初始化順序表L時(shí)，只需申請(qǐng)空間并設(shè)置length的值，每個(gè)語(yǔ)句最多執(zhí)行1次。因此，該函數(shù)的時(shí)間復(fù)雜度為O(1)。1.3實(shí)驗(yàn)范例

輸入n個(gè)學(xué)生的信息：要求把n（例如n=50）個(gè)學(xué)生的信息輸入到順序表mylist中，每個(gè)學(xué)生的信息按學(xué)號(hào)、姓名、英語(yǔ)成績(jī)、數(shù)學(xué)成績(jī)的次序輸入。1.3.2范例21.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.2范例2

范例1已經(jīng)定義了順序表mylist可用于存放學(xué)生信息，現(xiàn)要求輸入n個(gè)學(xué)生的信息。輸入過(guò)程用循環(huán)實(shí)現(xiàn)，一個(gè)學(xué)生即為一個(gè)元素，在循環(huán)內(nèi)一次輸入一個(gè)學(xué)生信息，總共執(zhí)行n次即可。因此，可設(shè)計(jì)一個(gè)函數(shù)InputSqList(SqList&L,intn)實(shí)現(xiàn)在L中添加n個(gè)元素。為了檢測(cè)數(shù)據(jù)是否輸入正確，可以將順序表中的信息輸出，定義函數(shù)PrintListInfo(SqListL)輸出順序表中存儲(chǔ)的學(xué)生信息。1.3實(shí)驗(yàn)范例2、算法描述1.3.2范例2

Student類(lèi)型中學(xué)號(hào)和姓名是字符數(shù)組，性別是字符型，為了保證在輸入過(guò)程中輸入的字符正確，在輸入學(xué)號(hào)、姓名和性別之前調(diào)用fflush(stdin)來(lái)清空輸入緩沖區(qū)。InputSqList(SqList&L,intn)函數(shù)可以定義如下：voidInputSqList(SqList&L,intn){inti;for(i=0;i<n;i++){//以下讀入第i個(gè)學(xué)生的信息printf("第%d個(gè)學(xué)生的信息\n",i+1);fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(L.elem[i].No);printf("姓名:");fflush(stdin);gets(L.elem[i].name);printf("性別：");scanf("%c",&L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&L.elem[i].math);}L.length=n;//有效數(shù)據(jù)長(zhǎng)度為n}1.3實(shí)驗(yàn)范例2、算法描述1.3.2范例2

需要注意的是在InputSqList()函數(shù)中沒(méi)有對(duì)數(shù)據(jù)的合法性進(jìn)行驗(yàn)證。在對(duì)數(shù)據(jù)進(jìn)行輸入的時(shí)候，可以定義一個(gè)函數(shù)InputOneStu(Student&stu)用于輸入一個(gè)學(xué)生的數(shù)據(jù)：voidInputOneStu(Student&stu){fflush(stdin);//清空輸入緩沖區(qū)printf("學(xué)號(hào):");gets(stu.No);fflush(stdin);printf("姓名:");fflush(stdin);

gets();printf("性別：");scanf("%c",&stu.sex);printf("大學(xué)英語(yǔ)成績(jī)：");scanf("%d",&stu.english);printf("高等數(shù)學(xué)成績(jī)：");scanf("%d",&stu.math);}1.3實(shí)驗(yàn)范例2、算法描述1.3.2范例2InputSqList(SqList&L,intn)函數(shù)可改寫(xiě)成如下形式：voidInputSqList(SqList&L,intn){inti;Studenttmpstu;for(i=0;i<n;i++){InputOneStu(tmpstu);L.elem[i]=tmpstu;}L.length=n；//有效數(shù)據(jù)長(zhǎng)度為n}1.3實(shí)驗(yàn)范例2、算法描述1.3.2范例2

如果Student內(nèi)部包含指針變量，例如學(xué)生信息還包含家庭地址的信息，這個(gè)家庭地址定義為字符指針變量，如char*address。在給address賦值時(shí)，需給該指針?lè)峙淇臻g，然后調(diào)用strcpy函數(shù)將家庭地址信息復(fù)制到該空間中。此時(shí)需要定義函數(shù)來(lái)實(shí)現(xiàn)數(shù)據(jù)元素賦值，假設(shè)定義函數(shù)CopyStu(Student&this_stu,Student&other_stu)實(shí)現(xiàn)，在輸入學(xué)生信息是調(diào)用該函數(shù)CopyStu(L.elem[i],tmpstu)代替語(yǔ)句L.elem[i]=tmpstu實(shí)現(xiàn)賦值。1.3實(shí)驗(yàn)范例3、算法分析1.3.2范例2InputOneStu()函數(shù)在讀入一個(gè)學(xué)生的數(shù)據(jù)時(shí)函數(shù)內(nèi)每個(gè)語(yǔ)句執(zhí)行1次，因此InputOneStu()函數(shù)的時(shí)間復(fù)雜度為O(1)。InputSqList()函數(shù)需要讀入n個(gè)學(xué)生的數(shù)據(jù)，即需調(diào)用InputOneStu()函數(shù)n次。因此，InputSqList()函數(shù)的時(shí)間復(fù)雜度為O(1*n)，即O(n)。1.3實(shí)驗(yàn)范例

查找學(xué)生的信息：要求在順序表中查找某一姓名（如姓名為“Peter”）的同學(xué)的信息，并把查到的信息顯示出來(lái)。1.3.3范例31.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.3范例3

查找過(guò)程：可以從順序表中的第一個(gè)元素開(kāi)始往后查找，比較該元素中的姓名是否為要找的姓名，如果順序表中某個(gè)元素的姓名等于要找的姓名，則輸出該數(shù)據(jù)元素的信息。1.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.3范例3

可以從順序表中L.elem[0]開(kāi)始，比較該元素的姓名是否為要查找的姓名name，由于name是字符數(shù)組，比較需要調(diào)用strcmp()函數(shù)來(lái)實(shí)現(xiàn)。判斷strcmp(L.elem[0].name,name)的結(jié)果是否為0，如果結(jié)果為0則L.elem[0]元素中的姓名和要查找的姓名相等。如果L.elem[0]中的姓名和要查找的姓名不同，就繼續(xù)將L.elem[1]中的姓名進(jìn)行比較，以此類(lèi)推。因此，可以定義一個(gè)循環(huán)變量i，i從0開(kāi)始一直到L.length-1，比較L.elem[i]中的姓名是否為要找的姓名，如果找到則輸出相關(guān)信息。1.3實(shí)驗(yàn)范例2、算法描述1.3.3范例3

在順序表L中，查找姓名為name的學(xué)生，如果找到則輸出其信息。函數(shù)定義如下：voidSearchElemSqList(SqListL,char*name){inti;

//從第一個(gè)學(xué)生開(kāi)始往后查看

for(i=0;i<L.length;i++){

//如果有姓名為參數(shù)name的同學(xué)

if(strcmp(L.elem[i].name,name)==0){printf("學(xué)號(hào)：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);

printf("大學(xué)英語(yǔ)成績(jī)：%d\n",L.elem[i].english);

printf("高等數(shù)學(xué)成績(jī)：%d\n",L.elem[i].math);

}

}}1.3實(shí)驗(yàn)范例2、算法描述1.3.3范例3SearchElemSqList()函數(shù)實(shí)現(xiàn)了查找和輸出數(shù)據(jù)元素信息兩個(gè)功能，不符合模塊化設(shè)計(jì)思想?？梢赃M(jìn)一步將其輸出信息部分從函數(shù)中去掉，當(dāng)找到名為”P(pán)eter”的同學(xué)之后即返回該元素的下標(biāo)。如果整個(gè)表都查找完了，還找不到”P(pán)eter”，則返回-1（-1是一個(gè)不存在的下標(biāo)）。1.3實(shí)驗(yàn)范例2、算法描述1.3.3范例3SearchElemSqList函數(shù)可以改寫(xiě)如下：intSearchElemSqList(SqListL,char*name){inti;for(i=0;i<L.length;i++){if(strcmp(L.elem[i].name,name)==0)//有姓名為參數(shù)name的同學(xué)returni;//返回元素所在的位置（下標(biāo)）}return-1;}1.3實(shí)驗(yàn)范例2、算法描述1.3.3范例3

對(duì)于原來(lái)的輸出部分，設(shè)計(jì)一個(gè)函數(shù)PrintStuInfo(SqListL,inti)用于輸出順序表L中的第i個(gè)元素的信息。PrintStuInfo(SqListL,inti)函數(shù)可以定義如下：voidPrintStuInfo(SqListL,inti){printf("學(xué)號(hào)：%s\n",L.elem[i].No);printf("姓名：%s\n",L.elem[i].name);printf("性別：%c\n",L.elem[i].sex);printf("大學(xué)英語(yǔ)成績(jī)：%d\n",L.elem[i].english);printf("高等數(shù)學(xué)成績(jī)：%d\n",L.elem[i].math);}1.3實(shí)驗(yàn)范例3、算法分析1.3.3范例3SearchElemSqList()函數(shù)需要從第一個(gè)學(xué)生開(kāi)始進(jìn)行查看，在最壞的情況下需要查看所有學(xué)生的信息。因此，SearchElemSqList()函數(shù)的時(shí)間復(fù)雜度為O(n)。1.3實(shí)驗(yàn)范例

插入一個(gè)學(xué)生的信息：要求在第i個(gè)位置插入一個(gè)學(xué)生的信息，原來(lái)的第i個(gè)位置及其之后的學(xué)生都往后移動(dòng)一個(gè)位置。1.3.4范例41.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.4范例4

假設(shè)要在第2個(gè)位置插入一個(gè)新的元素（即在L.elem[1]的位置插入一個(gè)新的學(xué)生信息），需要從最后一個(gè)元素開(kāi)始往后移動(dòng)，即先把L.elem[length-1]移動(dòng)到L.elem[length]的地方，最后把原L.elem[1]移動(dòng)到L.elem[2]的地方。該移動(dòng)元素的操作需要用循環(huán)來(lái)實(shí)現(xiàn)，用for循環(huán)實(shí)現(xiàn)如下：for(j=L.length-1;j>=i-1;j--)

L.elem[j+1]=L.elem[j];

當(dāng)元素移動(dòng)完之后，再把新的元素存入第2個(gè)位置，用語(yǔ)句L.elem[i-1]=stu;（stu為新加入的學(xué)生信息）。當(dāng)新的學(xué)生信息被加入之后，順序表的有效長(zhǎng)度應(yīng)該增加1。1.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.4范例4并不是所有情況都能插入。所以在移動(dòng)元素之前需判斷該元素是否能插入到順序表中。不能插入的情況有如下四種：（1）當(dāng)i<=0時(shí)，插入的位置不正確。（2）當(dāng)i>=MAXSIZE時(shí)，插入的位置也不正確，因?yàn)檫@個(gè)位置已經(jīng)超過(guò)了順序表的長(zhǎng)度范圍。（3）即使i的位置正確，但順序表已經(jīng)滿(mǎn)了，即L.length=MAXSIZE。對(duì)于這種情況，可以把L中最后一個(gè)元素?cái)D出，也可以提示操作失敗。在本例中，我們將這種情況視為操作失敗。1.3實(shí)驗(yàn)范例1、問(wèn)題分析1.3.4范例4并不是所有情況都能插入。所以在移動(dòng)元素之前需判斷該元素是否能插入到順序表中。不能插入的情況有如下四種：（4）當(dāng)L.length<i<MAXSIZE時(shí)，將元素插入到length之后的位置，不需要移動(dòng)元素。例如順序表L中最多可以存放50個(gè)元素，插入之前L中已經(jīng)有10個(gè)元素，現(xiàn)要求將新的元素插入到第15個(gè)位置，即給出的i=15。對(duì)于這種情況，可以在程序中提示給出的i錯(cuò)誤，也可以把新的元素直接加入到L的最后面。在本例中將把新元素加到L的最后面。1.3實(shí)驗(yàn)范例2、算法描述1.3.4范例4

定義函數(shù)intInsertElemSqList(SqList&L,Studentstu,inti)實(shí)現(xiàn)在順序表L中的第i個(gè)位置插入學(xué)生信息為stu的元素。函數(shù)可以定義如下：intInsertElemSqList(SqList&L,Studentstu,inti){//插入位置不在1到MAXSIZE之間，或者空間不夠if(i<1||i>MAXSIZE||L.length==MAXSIZE)return0;//空間夠但是位置不在1-L.length之間，插入到最后一個(gè)元素后面if(i>L.length&&i<=MAXSIZE){L.elem[L.length]=stu;L.length++;return1;

}1.3實(shí)驗(yàn)范例2、算法描述1.3.4范例4

定義函數(shù)intInsertElemSqList(SqList&L,Studentstu,inti)實(shí)現(xiàn)在順序表L中的第i個(gè)位置插入學(xué)生信息為stu的元素。函數(shù)可以定義如下：intInsertElemSqList(SqList&L,Studentstu,inti){……

//將元素L.elem[L.length-1]到L.elem[i-1]逐個(gè)往后移動(dòng)一個(gè)位置for(intj=L.length-1;j>=i-1;j--)L.elem[j+1]=L.elem[j];L.elem[i-1]=stu;//將x插入到順序表中L.length++;//順序表L的長(zhǎng)度加1return1;}1.3實(shí)驗(yàn)范例3、算法分析1.3.4范例4InsertElemSqList()函數(shù)需要從最后一個(gè)元素開(kāi)始將元素逐個(gè)往后移動(dòng)，在最壞的情況下所有學(xué)生的信息都要被移動(dòng)。因此，InsertElemSqList()函數(shù)的時(shí)間復(fù)雜度為O(n)。1.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)1：按表格的方式打印顯示序順序表L中的所有信息。要求：設(shè)計(jì)一個(gè)表頭，即第一行顯示“學(xué)號(hào)

姓名

性別

英語(yǔ)

數(shù)學(xué)

總成績(jī)”，然后將每個(gè)學(xué)生的信息打印一行，盡量使打印出的信息與表頭對(duì)應(yīng)項(xiàng)對(duì)齊。任務(wù)2：寫(xiě)一個(gè)函數(shù)刪除順序表L中某一元素。要求：因有學(xué)生留級(jí)或轉(zhuǎn)學(xué)，需要將該學(xué)生信息從表L中去掉。即給出一個(gè)學(xué)號(hào)，刪除該學(xué)號(hào)的學(xué)生信息。1.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)3：在有序的順序表中加入元素后，使表仍然有序。要求：重新初始化線(xiàn)性表L，要求每次加入新的學(xué)生信息后，線(xiàn)性表L中的元素按總成績(jī)從高到低排列。任務(wù)4：將線(xiàn)性表中L的數(shù)據(jù)保存到一個(gè)磁盤(pán)文件中。要求：創(chuàng)建一個(gè)磁盤(pán)文件，將線(xiàn)性表L中的元素按次序?qū)懭胍粋€(gè)文件中，下次實(shí)驗(yàn)可以讀出該文件中的數(shù)據(jù)。1.5任務(wù)提示

任務(wù)1要求打印顯示學(xué)生信息，可以設(shè)計(jì)一個(gè)函數(shù)ShowStuInfo(SqList&L)顯示L中的信息。該函數(shù)先打印表頭，然后逐行打印每個(gè)學(xué)生的信息。ShowStuInfo(SqList&L)函數(shù)可設(shè)計(jì)如下：任務(wù)1提示voidShowStuInfo(SqList&L){ShowTitle();//顯示表頭標(biāo)題for(i=0;i<L.length;i++)

ShowOneStuInfo(L.elem[i]);//顯示一個(gè)學(xué)生的信息}

然后在ShowTitle()函數(shù)和ShowOneStuInfo()函數(shù)中對(duì)數(shù)據(jù)進(jìn)行格式化即可，比較簡(jiǎn)單的方法是使用“\t”將數(shù)據(jù)對(duì)齊。1.5任務(wù)提示

從順序表L的第一個(gè)元素開(kāi)始，依次將學(xué)生的學(xué)號(hào)和給出的學(xué)號(hào)stuNo進(jìn)行比較，如果相等，則將該元素后面的元素都往前移一個(gè)位置，同時(shí)順序表的長(zhǎng)度減1?？梢栽O(shè)計(jì)函數(shù)DeleteElemSqList(SqList&L,char*stuNo)來(lái)刪除順序表L中學(xué)號(hào)為stuNo的學(xué)生。任務(wù)2提示1.5任務(wù)提示

函數(shù)可設(shè)計(jì)如下：任務(wù)2提示voidDeleteElemSqList(SqList&L,char*stuNo){i=0;while(i<=L.length-1){

//如果第i個(gè)元素值與e相等

if