線性表

【什么是算法不跟?】
空間復(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;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末畔规,一起剝皮案震驚了整個(gè)濱河市局扶,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌叁扫,老刑警劉巖三妈,帶你破解...
    沈念sama閱讀 223,002評論 6 519
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異莫绣,居然都是意外死亡畴蒲,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,357評論 3 400
  • 文/潘曉璐 我一進(jìn)店門对室,熙熙樓的掌柜王于貴愁眉苦臉地迎上來模燥,“玉大人,你說我怎么就攤上這事掩宜∧杪睿” “怎么了?”我有些...
    開封第一講書人閱讀 169,787評論 0 365
  • 文/不壞的土叔 我叫張陵牺汤,是天一觀的道長辽旋。 經(jīng)常有香客問我,道長檐迟,這世上最難降的妖魔是什么补胚? 我笑而不...
    開封第一講書人閱讀 60,237評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮锅减,結(jié)果婚禮上糖儡,老公的妹妹穿的比我還像新娘。我一直安慰自己怔匣,他們只是感情好握联,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,237評論 6 398
  • 文/花漫 我一把揭開白布桦沉。 她就那樣靜靜地躺著,像睡著了一般金闽。 火紅的嫁衣襯著肌膚如雪纯露。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,821評論 1 314
  • 那天代芜,我揣著相機(jī)與錄音埠褪,去河邊找鬼。 笑死挤庇,一個(gè)胖子當(dāng)著我的面吹牛钞速,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播嫡秕,決...
    沈念sama閱讀 41,236評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼渴语,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了昆咽?” 一聲冷哼從身側(cè)響起驾凶,我...
    開封第一講書人閱讀 40,196評論 0 277
  • 序言:老撾萬榮一對情侶失蹤,失蹤者是張志新(化名)和其女友劉穎掷酗,沒想到半個(gè)月后调违,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,716評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡泻轰,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,794評論 3 343
  • 正文 我和宋清朗相戀三年技肩,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片糕殉。...
    茶點(diǎn)故事閱讀 40,928評論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡亩鬼,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出阿蝶,到底是詐尸還是另有隱情雳锋,我是刑警寧澤,帶...
    沈念sama閱讀 36,583評論 5 351
  • 正文 年R本政府宣布羡洁,位于F島的核電站玷过,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏筑煮。R本人自食惡果不足惜辛蚊,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,264評論 3 336
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望真仲。 院中可真熱鬧袋马,春花似錦、人聲如沸秸应。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,755評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至桑谍,卻和暖如春延柠,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背锣披。 一陣腳步聲響...
    開封第一講書人閱讀 33,869評論 1 274
  • 我被黑心中介騙來泰國打工贞间, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人雹仿。 一個(gè)月前我還...
    沈念sama閱讀 49,378評論 3 379
  • 正文 我出身青樓增热,卻偏偏與公主長得像,于是被迫代替她去往敵國和親盅粪。 傳聞我的和親對象是個(gè)殘疾皇子钓葫,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,937評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 1.線性表的定義 線性表:零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列序列:也就是說元素之間是有順序的,若元素存在多個(gè),則第一個(gè)元...
    e40c669177be閱讀 2,071評論 6 15
  • 3.2 線性表的定義 線性表悄蕾,從名字上你就能感覺到票顾,是具有像線一樣的性質(zhì)的表。 零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列帆调。 這...
    努力生活的西魚閱讀 928評論 0 1
  • 前言 上一篇《數(shù)據(jù)結(jié)構(gòu)和算法之時(shí)間復(fù)雜度和空間復(fù)雜度》中介紹了時(shí)間復(fù)雜度的概念和常見的時(shí)間復(fù)雜度奠骄,并分別舉例子進(jìn)行...
    VV木公子閱讀 4,344評論 2 26
  • 一.線性表 定義:零個(gè)或者多個(gè)元素的有限序列。也就是說它得滿足以下幾個(gè)條件:??①該序列的數(shù)據(jù)元素是有限的番刊。??②...
    Geeks_Liu閱讀 2,701評論 1 12
  • 從數(shù)據(jù)的邏輯結(jié)構(gòu)來分含鳞,數(shù)據(jù)元素之間存在的關(guān)聯(lián)關(guān)系被稱為數(shù)據(jù)的邏輯結(jié)構(gòu)。歸納起來芹务,應(yīng)用程序中的數(shù)據(jù)大致喲如下四種基本...
    Jack921閱讀 939評論 0 2