【什么是算法不跟？】
空間復(fù)雜度S(n)：根據(jù)算法寫成的程序在執(zhí)行時(shí)占用存儲單元的長度。
時(shí)間復(fù)雜度T(n)：根據(jù)算法寫成的程序在執(zhí)行時(shí)消耗的時(shí)間長度俊庇。
分析算法復(fù)雜度
Tworst(n)：最壞情況復(fù)雜度
Tav(n)：平均復(fù)雜度
【什么是線性表弯屈？】
“線性表（Linear List）”：由同類數(shù)據(jù)元素構(gòu)成有序序列的線性結(jié)構(gòu)
表中的元素個(gè)數(shù)稱為線性表的長度，沒有元素時(shí)稱為空表缴淋，表的起始位置稱為表頭准给，結(jié)束位置稱為表尾泄朴。
【線性表的順序存儲實(shí)現(xiàn)】
typedef struct Lnode *List;
struct Lnode {
ElementType Data[MAXSIZE];
int Last; //線性表最后一個(gè)元素
};
struct LNode L;
List PtrL; //PtrL為指向結(jié)構(gòu)體的指針 || struct Lnode * PtrL
訪問下標(biāo)為i的元素：L.Data[i]或者PtrL->Data[i]
線性表長度：L.Last+1或者PtrL->Last+1
【線性表的主要操作】
1、初始化（建立空的順序表）
List MakeEmpty()
{
List PtrL;
PtrL=(List )malloc(sizeof(struct LNode));
PtrL->Last=-1;
return PtrL;
}
2露氮、查找
/* 查找成功的平均比較次數(shù)是（n+1）/2
平均時(shí)間性能是O（n） */
int Find()(ElementType X,List PtrL)
{
int i=0;
while(i<=PtrL->Last && PtrL->Data[i]!=X)
i++;
if(i>PtrL->Last) return -1;
else return i;
}
3祖灰、插入
/* 第i個(gè)位置上插入一個(gè)值為x的新元素 */
void Insert(ElementType X, int i, List PtrL)
{
/*MAXSIZE 數(shù)組大小*/
if (PtrL->Last == MAXSIZE - 1) {
printf("表滿");
return;
}
if (i<1 || i>PtrL->Last + 2) {
printf("位置不合法");
return;
}
for (j = PtrL->Last; j >= i - 1; j--)
PtrL->Data[j + 1] = PtrL->Data[j];
PtrL->Data[i - 1] = X;
PtrL->Last++;
return;
}
4、刪除
/* 刪除表的第i個(gè)位置上的元素 */
void Delete(int i, List PtrL)
{
int j;
if (i<1 || i>PtrL->Last + 1) {
printf("不存在第%d個(gè)元素", i);
return;
}
for (j = i; j <= PtrL->Last; j++)
PtrL->Data[j - 1] = PtrL->Data[j];
PtrL->Last--;
return;
}
