線性表(二)鏈?zhǔn)浇Y(jié)構(gòu)表示與實(shí)現(xiàn)

鏈?zhǔn)奖硎?/h5>

線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的特點(diǎn)是用一組任意的得存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素(這組存儲(chǔ)單元可以是連續(xù)的,也可以是不連續(xù)的)士败。因此闯两,為了表示ai和ai+1之間的邏輯關(guān)系,對(duì)數(shù)據(jù)元素ai來(lái)說(shuō)谅将,除了存儲(chǔ)其本身的信息之外漾狼,還需存儲(chǔ)一個(gè)指示其直接后繼存儲(chǔ)位置的信息八拱。這兩部分信息組成ai的存儲(chǔ)映像宁改,稱為結(jié)點(diǎn)(node)。
結(jié)點(diǎn)包括兩個(gè)域:其中存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域盾舌;存儲(chǔ)直接后繼存儲(chǔ)位置的域稱為指針域隅熙。指針域中存儲(chǔ)的信息稱作指針志衣。n個(gè)結(jié)點(diǎn)鏈組成一個(gè)鏈表,即為線性表的式存儲(chǔ)結(jié)構(gòu)猛们。由于每個(gè)節(jié)點(diǎn)中只包含一個(gè)指針域念脯,故又稱線性鏈表單鏈表

元素定義
typedef int ElemType;
單鏈表定義
typedef struct LNode{
        ElemType data;
        struct LNode *next;
}LNode, *LinkList;            // 帶頭結(jié)點(diǎn)線性鏈表

我們?cè)趩捂湵淼牡谝粋€(gè)結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn)弯淘,稱為頭結(jié)點(diǎn)绿店。頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲(chǔ)任何信息,也可以存儲(chǔ)如線性表長(zhǎng)度等類的附加信息庐橙,頭結(jié)點(diǎn)的指針指向第一個(gè)元素結(jié)點(diǎn)的存儲(chǔ)位置假勿。

鏈?zhǔn)酱鎯?chǔ)

在單鏈表中,任何兩個(gè)元素的存儲(chǔ)位置之間沒(méi)有固定的聯(lián)系态鳖。然后转培,每個(gè)元素的存儲(chǔ)位置都包含在其直接前驅(qū)結(jié)點(diǎn)的信息之中,由此在單鏈表中浆竭,去得第i個(gè)數(shù)據(jù)元素必須從頭指針出發(fā)尋找浸须。因此單鏈表是非隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)惨寿,這種存儲(chǔ)結(jié)構(gòu)相對(duì)于順序存儲(chǔ)結(jié)構(gòu),具有空間利用合理删窒,插入和刪除時(shí)不需要移動(dòng)等優(yōu)點(diǎn)裂垦,因此在很多場(chǎng)合下,鏈?zhǔn)酱鎯?chǔ)是線性表的首選存儲(chǔ)結(jié)構(gòu)肌索。

基本操作
#include <stdio.h>
#include <stdlib.h>

#define FAILURE -1
#define SUCCESS 1

typedef int ElemType;  // 元素定義

typedef struct LNode{
        ElemType data;
        struct LNode *next;
}LNode, *LinkList;      // 帶頭結(jié)點(diǎn)

int compare(ElemType e1, ElemType e2){
        // 比較e1和e2元素是否相同蕉拢,具體實(shí)現(xiàn)和ElemType類型有關(guān)
        if(e1 == e2) 
                return SUCCESS;
        else
                return FAILURE;
}

int visit(ElemType e){ 
        // 訪問(wèn)e元素,具體實(shí)現(xiàn)和ElemType類型有關(guān)
        printf("%d ", e); 
        return SUCCESS;
} 

void InitList_L(LinkList *L){
        // 初始化線性鏈表诚亚,L指向data為空的頭結(jié)點(diǎn)
        *L = (LinkList)malloc(sizeof(LNode));
        if (!*L) exit(-1);      //創(chuàng)建頭結(jié)點(diǎn)失敗
        (*L)->next = NULL;
}

void DestroyList_L(LinkList *L){
        // 銷毀單鏈表, 不僅釋放數(shù)據(jù)節(jié)點(diǎn)晕换,也銷毀頭結(jié)點(diǎn)
        LinkList p = *L;        //頭結(jié)點(diǎn)
        LinkList np; 
        while(p){
                np = p->next;
                free(p);
                p = np; 
        }   
        *L = NULL;
}

void ClearList_L(LinkList *L){
        // 帶頭結(jié)點(diǎn)的鏈表,僅清除數(shù)據(jù)節(jié)點(diǎn)
        LinkList p = (*L)->next;
        LinkList np; 
        while(p){
                np = p->next;
                free(p);
                p = np; 
        }   
        (*L)->next = NULL;
}

int ListEmpty_L(LinkList L){ 
        if(L->next == NULL)
                return SUCCESS;
        else
                return FAILURE;
}

int ListLength_L(LinkList L){
        // 返回單鏈表的長(zhǎng)度
        int i = 0;
        while(L->next){
                i++;
                L = L->next;
        }
        return i;
}

int GetElem_L(LinkList L, int i, ElemType *e){
        // 用e返回線性表L中第i位置元素
        // 其中1<=i<=L.length
        int p = 1;
        L = L->next;
        while(L && p < i){
                p++;
                L = L->next;
        }
        if(!L || p > i) return FAILURE;
        *e = L->data;
        return SUCCESS;
}

int LocateElem_L(LinkList L, ElemType e, int (*compare)(ElemType, ElemType)){
        // 從L中查找第一個(gè)與e元素滿足compare函數(shù)關(guān)系的元素
        // 如果不存在則返回0
        int p = 1;
        L = L->next;
        while(L){
                if(compare(L->data, e) > 0){    // 找到
                        return p;
                } else{
                        L = L->next;
                        p++;
                }
        }
        return FAILURE;
}

int PriorElem_L(LinkList L, ElemType cur_e, ElemType *pre_e){
        // 若cur_e是L中元素且不是第一個(gè),則用pre_e返回它的前驅(qū)站宗,否則失敗
        LinkList pre, cur;
        pre = L;
        cur = L->next;
        if(cur->data == cur_e) return FAILURE;  //第一個(gè)位置
        while(cur && cur->data != cur_e){
                pre = cur;
                cur = cur->next;
        }
        if(!cur) return FAILURE;
        *pre_e = pre->data;
        return SUCCESS;
}

int NextElem_L(LinkList L, ElemType cur_e, ElemType *next_e){
        // cur_e是L中元素且不是最后一個(gè)届巩,則用next_e返回它的后繼元素
        LinkList cur, next;
        cur = L;
        next = cur->next;
        while(next && cur->data != cur_e){
                cur = next;
                next = next->next;
        }
        if(!next) return FAILURE;
        *next_e = next->data;
        return SUCCESS;
}

int InsertList_L(LinkList L, int i, ElemType e){
        // 在帶頭結(jié)點(diǎn)的L中第i位置之前插入e
        LNode *p = L;   // p指向L頭結(jié)點(diǎn)
        int j=0;
        while(p && j<i-1){
                p = p->next;
                j++;
        }
        if(!p || j > i-1) return FAILURE;       // i值不合理
        LNode *s = (LNode*)malloc(sizeof(LNode));
        s->data = e;
        s->next = p->next;
        p->next = s;
        return SUCCESS;
}

int DeleteList_L(LinkList L, int i,  ElemType *e){
        // 刪除線性鏈表L中第i位置節(jié)點(diǎn),并由e返回
        LNode *p = L;
        int j = 0;
        while(p && j<i-1){
                p = p->next;
                j++;
        }
        if(!p || j>i-1) return FAILURE;
        // 此時(shí)p指向第i-1位置節(jié)點(diǎn)
        // q指向待刪除節(jié)點(diǎn)
        LNode *q = p->next;
        // 移除節(jié)點(diǎn)
        p->next = p->next->next;
        // 將值返回
        *e = q->data;
        free(q);
        return SUCCESS;
}

int ListTraverse_L(LinkList L, int (*visit)(ElemType)){
        // 對(duì)L中每一個(gè)元素調(diào)用visit函數(shù)份乒,一旦visit失敗恕汇,則操作失敗
        L = L->next;
        while(L){
                if(visit(L->data) < 0) return FAILURE;
                L = L->next;
        }
        return SUCCESS;
}

void MergeList_L(LinkList La, LinkList Lb, LinkList *Lc){
        // 歸并兩個(gè)有序線性鏈表,要求結(jié)果也有序排列
        LNode *pa = La->next, *pb = Lb->next;
        LNode *pc;
        *Lc = pc = La;  // Lc以La頭結(jié)點(diǎn)為頭結(jié)點(diǎn)
        while(pa && pb){
                if(pa->data <= pb->data){
                        pc->next = pa;
                        pa = pa->next;
                } else{
                        pc->next = pb;
                        pb = pb->next;
                }

                pc = pc->next;
        }
        // 歸并剩余結(jié)點(diǎn)
        pc->next = pa ? pa:pb;
        free(Lb);       // 釋放Lb頭結(jié)點(diǎn)
}

void difference(LinkList La, LinkList Lb){
        // 計(jì)算帶頭結(jié)點(diǎn)的線性鏈表La和Lb的差集或辖,并將結(jié)果保存在La鏈表中
        LinkList pa = La;
        while(pa->next){
                LinkList pb = Lb->next;
                while(pb && pb->data != pa->next->data) pb = pb->next;
                if(!pb) pa = pa->next;  // 沒(méi)有在pb中找到
                else {                  // 在pb中找到
                        LinkList tem = pa->next;
                        pa->next = pa->next->next;
                        free(tem);
                }
        }
}

void main(){
        // 聲明線性列表L
        LinkList L;
        // 初始化線性列表瘾英,令L指向頭結(jié)點(diǎn)
        printf("****************** init list *************\n");
        InitList_L(&L);
        // 頭結(jié)點(diǎn)位置
        printf("L position is: %p\n", L);
        // 頭結(jié)點(diǎn)中data值
        printf("L data is: %d\n", L->data);
        // 插入值
        printf("*********** insert value ************\n");
        int a[] = {1, 3, 4, 5, 10, 5, 7};
        int i;
        for(i=0;i<7;i++){
                InsertList_L(L, i+1, a[i]);
        }
        printf("插入值后:\n");
        ListTraverse_L(L, visit);
        // get elem
        printf("\n****************** get elem from L*************\n");
        ElemType e1, e2;
        if(GetElem_L(L, 0, &e1) > 0){
                printf("get elem at index 0 success, reutrn value: %d\n", e1);
        } else {
                printf("get elem at index 0 failure\n");
        }
        if(GetElem_L(L, 4, &e2) > 0){
                printf("get elem at index 4 success, return value: %d\n", e2);
        } else {
                printf("get elem at index 4 failure\n");
        }
        if(GetElem_L(L, 20, &e2) >0){
                printf("get elem at index 20 success, return value: %d\n", e2);
        } else {
                printf("get elem at index 20 failure.\n");
        }
        // locate elem
        printf("\n***************** locate elem *************** \n");
        int index1, index2;
        index1 = LocateElem_L(L, -10, compare);
        index2 = LocateElem_L(L, 7, compare);
        if(index1 > 0){
                printf("locate -10 in L success, index at: %d\n", index1);
        } else {
                printf("locate -10 in L failure!\n");
        }
        if(index2 > 0){
                printf("locate 7 in L success, index at: %d\n", index2);
        } else {
                printf("locate 7 in L failure!\n");
        }
        // prior elem
        printf("\n*********** prior elem *************\n");
        ElemType pre_e1, pre_e2;
        if(PriorElem_L(L, 1, &pre_e1) > 0){
                printf("find prior elem of 1 in L success, value is: %d\n",
                                pre_e1);
        } else {
                printf("find prior elem of 1 in L failure!\n");
        }
        if(PriorElem_L(L, 7, &pre_e2) > 0){
                printf("find prior elem of 7 in L success, value is: %d\n",
                                pre_e2);
        } else {
                printf("find prior elem of 7 in L failure!\n");
        }
        // next elem
        printf("\n************ next elem ************\n");
        ElemType next_e1, next_e2;
        if(NextElem_L(L, 1, &next_e1) > 0){
                printf("find next elem of 1 in L success, valueu is: %d\n",
                                next_e1);
        } else {
                printf("find next elem of 1 in L failure!\n");
        }
        if(NextElem_L(L, 7, &next_e2) > 0){
                printf("find next elem of 7 in L success, value is: %d\n",
                                next_e2);
        } else {
                printf("find next elem of 7 failure!\n");
        }
        // traverse
        printf("\n***********traverse************\n");
        if(ListTraverse_L(L, visit) > 0){
                printf("traverse L success!\n");
        } else {
                printf("traverse L failure!\n");
        }
        // 刪除一個(gè)元素
        ElemType e;
        printf("\n**************delete elem******************\n");
        if(DeleteList_L(L, 1, &e)>0){
                printf("delete success at index 1, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 1\n");
        }
        printf("now elem: ");
        ListTraverse_L(L, visit);
        printf("\n");

        if(DeleteList_L(L, 0, &e)>0){
                printf("delete success at index 0, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 0\n");
        }

        if(DeleteList_L(L, 6, &e)>0){
                printf("delete success at index 6, deleted value is: %d\n", e);
        } else {
                printf("delete failure at index 6\n");
        }
        // 銷毀
        printf("********** destroy **************\n");
        DestroyList_L(&L);
        printf("L position is: %p\n", L);

        // 歸并兩個(gè)順序表
        printf("\n********* start Merge ****************\n");
        LinkList La, Lb, Lc;
        InitList_L(&La);
        InitList_L(&Lb);
        InitList_L(&Lc);

        int la[] = {2, 4, 5, 10, 22};
        int lb[] = {1, 3, 8, 10, 12, 22, 34};

        for(i=0;i<5;i++){
                InsertList_L(La, i+1, la[i]);
        }
        for(i=0;i<7;i++){
                InsertList_L(Lb, i+1, lb[i]);
        }

        printf("La is: ");
        ListTraverse_L(La, visit);
        printf("\nLb is: ");
        ListTraverse_L(Lb, visit);
        MergeList_L(La, Lb, &Lc);
        printf("\nthe merge result Lc is: ");
        ListTraverse_L(Lc, visit);
        printf("\n");

        // 求差集
        LinkList Ld, Le;
        InitList_L(&Ld);
        InitList_L(&Le);

        int ld[] = {5, 10, 20, 15, 25, 30};
        int le[] = {5, 15, 35, 25, 30};

        for(i=0;i<6;i++){
                InsertList_L(Ld, i+1, ld[i]);
        }
        for(i=0;i<5;i++){
                InsertList_L(Le, i+1, le[i]);
        }

        printf("\n************** compute difference*****\n");
        printf("Ld is: ");
        ListTraverse_L(Ld, visit);
        printf("\n");
        printf("Le is: ");
        ListTraverse_L(Le, visit);

        printf("\nthe result that value in Ld and not in Le is: ");
        difference(Ld, Le);
        ListTraverse_L(Ld, visit);

        printf("\n");
}
運(yùn)行結(jié)果
****************** init list *************
L position is: 0x24e6010
L data is: 0
*********** insert value ************
插入值后:
1 3 4 5 10 5 7 
****************** get elem from L*************
get elem at index 0 failure
get elem at index 4 success, return value: 5
get elem at index 20 failure.

***************** locate elem *************** 
locate -10 in L failure!
locate 7 in L success, index at: 7

*********** prior elem *************
find prior elem of 1 in L failure!
find prior elem of 7 in L success, value is: 5

************ next elem ************
find next elem of 1 in L success, valueu is: 3
find next elem of 7 failure!

***********traverse************
1 3 4 5 10 5 7 traverse L success!

**************delete elem******************
delete success at index 1, deleted value is: 1
now elem: 3 4 5 10 5 7 
delete failure at index 0
delete success at index 6, deleted value is: 7
********** destroy **************
L position is: 0x7ffe356bc5f8

********* start Merge ****************
La is: 2 4 5 10 22 
Lb is: 1 3 8 10 12 22 34 
the merge result Lc is: 1 2 3 4 5 8 10 10 12 22 22 34 

************** compute difference*****
Ld is: 5 10 20 15 25 30 
Le is: 5 15 35 25 30 
the result that value in Ld and not in Le is: 10 20 
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市颂暇,隨后出現(xiàn)的幾起案子缺谴,更是在濱河造成了極大的恐慌,老刑警劉巖耳鸯,帶你破解...
    沈念sama閱讀 211,817評(píng)論 6 492
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件湿蛔,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡县爬,警方通過(guò)查閱死者的電腦和手機(jī)阳啥,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,329評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)财喳,“玉大人察迟,你說(shuō)我怎么就攤上這事《撸” “怎么了扎瓶?”我有些...
    開封第一講書人閱讀 157,354評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)泌枪。 經(jīng)常有香客問(wèn)我概荷,道長(zhǎng),這世上最難降的妖魔是什么碌燕? 我笑而不...
    開封第一講書人閱讀 56,498評(píng)論 1 284
  • 正文 為了忘掉前任误证,我火速辦了婚禮继薛,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘雷厂。我一直安慰自己,他們只是感情好叠殷,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,600評(píng)論 6 386
  • 文/花漫 我一把揭開白布改鲫。 她就那樣靜靜地躺著,像睡著了一般林束。 火紅的嫁衣襯著肌膚如雪像棘。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 49,829評(píng)論 1 290
  • 那天壶冒,我揣著相機(jī)與錄音缕题,去河邊找鬼。 笑死胖腾,一個(gè)胖子當(dāng)著我的面吹牛烟零,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播咸作,決...
    沈念sama閱讀 38,979評(píng)論 3 408
  • 文/蒼蘭香墨 我猛地睜開眼锨阿,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了记罚?” 一聲冷哼從身側(cè)響起墅诡,我...
    開封第一講書人閱讀 37,722評(píng)論 0 266
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎桐智,沒(méi)想到半個(gè)月后末早,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,189評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡说庭,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,519評(píng)論 2 327
  • 正文 我和宋清朗相戀三年然磷,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片刊驴。...
    茶點(diǎn)故事閱讀 38,654評(píng)論 1 340
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡样屠,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出缺脉,到底是詐尸還是另有隱情痪欲,我是刑警寧澤,帶...
    沈念sama閱讀 34,329評(píng)論 4 330
  • 正文 年R本政府宣布攻礼,位于F島的核電站业踢,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏礁扮。R本人自食惡果不足惜知举,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 39,940評(píng)論 3 313
  • 文/蒙蒙 一瞬沦、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧雇锡,春花似錦逛钻、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 30,762評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至立肘,卻和暖如春边坤,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背谅年。 一陣腳步聲響...
    開封第一講書人閱讀 31,993評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工茧痒, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人融蹂。 一個(gè)月前我還...
    沈念sama閱讀 46,382評(píng)論 2 360
  • 正文 我出身青樓旺订,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親超燃。 傳聞我的和親對(duì)象是個(gè)殘疾皇子耸峭,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,543評(píng)論 2 349

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