《大話資料結構》第三章線性表

第三章線性表

有序、有限、最多一個前驅和一個後繼

基本操作：

InitList(&L)

ListEmpty(L)

ClearList(&L)

GetElem(L, i, &e)

LocateElem(L, e)

ListInsert(&L, i, e)

ListDelete(&L, i, &e)

ListLength(L)

線性表集合A和B的合并操作

/*将所有的線上性表Lb中，但不在La中的資料元素插入到La中*/
void union(List *La, List Lb)
{
    int La_len, Lb_len;
    ElemType e;

    La_len = ListLength(La);
    Lb_len = ListLength(Lb);

    for(int i=; i<=Lb_len; i++){
        GetElem(Lb,i,&e);
        if(!LocateElem(La,e))
        ListInsert(&La,++La_len,e); 
    }
}

線性表的順序存儲的結構代碼

#define MaxSize 20
typedef int ElemType
typedef struct{
    Elemtype data[MaxSize];
    int Length;
}SqList;

随機存取結構，其存取時間性能為O(1)

獲得元素的操作

#define OK 1
#define ERROR 0
#define TRUE 1
#define FASLE 0
typedef int Status;

Status GetElem(SqList L, int i, ElemType *e){
    if(L.Length== || i< || i>L.Length)    
        return ERROR;
    *e=L.data[i-];
    return OK;
}

插入操作

Statue ListInsert(SqList *L, int i, ElemType e){
    int k;
    if(L->Length == MaxSize)    
        return ERROR;
    if(i< || i>L->Length+)
        return ERROR;
    if(i<=L->Length){
        for(k=L->Length-; k>=i-; k--)
            L->data[k+1] = L->data[k];
    }
    L->data[i-1]=e;
    L->Length++;
    return OK;
}

删除操作

Statue ListDelete(SqList *L, int i, ElemType *e){
    int k;
    if(L->Length == )
        return ERROR;
    if(i< || i>L->Length)
        return ERROR;
    *e=L->data[i-1];
    if(i<L->Length){
        for(k=i-; k<L->Length-; k++)
            L->data[k]=L->data[k+1] 
    }
    L->Length--;
    return OK;
}

存取快，插入删除慢

鍊式存儲結構

《大話資料結構》第三章線性表

頭指針是必要元素，頭指針均不為空，但頭結點不一定是連結清單的必要元素，頭結點是為了操作的統一和友善設立的，放在第一進制素節點前，資料域一般放連結清單長度

若線性表為空表，則頭結點的指針域為空。

單連結清單的結構代碼

typedef struct Node{
       //結點由資料域和指針域組成
    ElemType data;
    struct Node *next;
} Node, *LinkList;

單連結清單的讀取

Status GetElem(LinkList L, int i, ElemType *e){
    //LinkList即為Node*
    int j;
    LinkList p;
    p=L->next;  //讓p指向第一個結點,L了解為頭結點的指針
    j=;    //j為計數器

    while(p && j<i) //p不為空且計數器j還沒等于i時，循環繼續
    {
        p=p->next;
        j++;    
    }
    if(!p || j>i)
        return ERROR;

    *e=p->data;
    return OK; 
}

單連結清單的插入

Status LinkInsert(LinkList *L, int i, ElemType e){
    int j;
    LinkList p, s;
    p=*L;
    j=;

    while(!p && j<i-){
        p=p->next;
        ++j;
    }

    if(!p || j>i-)
        return ERROR;

    s=(LinkList)malloc(sizeof(Node));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK; 
}

單連結清單的删除

Status ListDelete(LinkList *L, int i, ElemType *e){
    int j;
    LinkList p, q;
    p=*L;
    j=;

    while(p && j<i-){
        p=p->next;
        ++j; 
    }

    if(!p || j>i-)
        return ERROR;
    if(!(p->next))
        return ERROR;

    q=p->next;
    p->next = q->next;
    *e = q->data;
    free(q);
    return OK
}

建立單連結清單頭插法

void CreateListHead(LinkList *L, int n){
    LinkList p;
    int i;
    srand(time());
    *L =(LinkList)malloc(sizeof(Node));
    (*L)->next=NULL;
    for(int i=; i<=n; i++){
        p=(LinkList)malloc(sizeof(Node));
        p->data = rand()%100+;
        p->next = (*L)->next;
        (*L)->next = p; 
    }
}

建立單連結清單尾插法

void CreateLinkTail(LinkList *L, int n){
    LinkList p, r;
    int i;
    srand(time());
    (*L)=(LinkList)malloc(sizeof(Node));
    r=*L;

    for(i=; i<=n; i++){
        p = (LinkList)malloc(sizeof(Node));
        p->data = rand()%100+;
        r->next = p;
        //p->next = r->next;
        r=p; 
    }
    r->next=NULL; 
}

單連結清單的整表删除

Status ClearList(LinkList *L)
{
    LinkList p,q;
    p=(*L)->next;

    while(p){
        q=p->next;
        free(p);
        p=q;
    } 
    (*L)->next=NULL;
    return OK;
}

靜态連結清單

《大話資料結構》第三章線性表

遊标實作法

#define MaxSize 1000
typedef struct{
    ElemType data;
    int cur;    //遊标cursor 
}Component, StaticLinkList[MaxSize];

初始化

Statues InitList(StaticLinkList space){
    int i;
    for(i=; i<MaxSize-; i++)
        space[i].cur = i+;
    space[i].cur = ;
    return OK;
}
/*數組第一個元素的cur用來存放備用連結清單第一個節點的下标
把未被使用的數組元素成為備用連結清單,
下一位置資料為空則next用表示
數組的最後一個元素的cur用來存放第一個插入元素的下标，當整個連結清單為空時，為*/

連結清單的插入操作

int Malloc_SLL(StaticLinkList space){
    int i=space[].cur;

    if(space[].cur)
        space[].cur = space[i].cur;

    return i;
}

Status ListInsert(SaticLinkList L, int i, ElemType e){
    int j, k, l;
    k = MaxSize-;
    j = Malloc_SLL(L);

    if(i< || i>ListLength(L)+)
        return ERROR;

    if(j){
        L[j].data = e;
        for(l=; l<=i-; l++)
            k=L[k].cur;
        L[j].cur=L[k].cur;
        L[k].cur=j;
        return OK;
    }
    return ERROR;
}

int ListLength(StaticLinkList space){
    int j=;
    int i=space[MaxSize-].cur;

    while(i){
        j++;
        i=space[i].cur;
    }
    return j;
}

連結清單的删除操作

Status ListDelete(StaticLinkList L, int i){
    int j, k;
    k=MaxSize-;

    if(i< || i>ListLength(L))
        return ERROR;

    for(j=; j<=i-; j++)
        k=L[k].cur;

    j=L[k].cur;
    L[k].cur=L[j].cur;
    Free_SSL(L,j);

    return OK;
}

void Free_SSL(StaticLinkList space, int k){
    space[k].cur=space[].cur;
    space[].cur=k;
}

int ListLength(StaticLinkList L){
    int j,k,i;
    i=L[Maxsize-].cur;
    j=;

    while(i){
        ++j;
        i=L[i].cur;
    }

    return j;
}

循環連結清單

設定循環連結清單的尾指針rear，便于通路尾結點

判斷循環結束的條件 p->next 是否等于頭結點

《大話資料結構》第三章線性表

合并兩個連結清單的操作

《大話資料結構》第三章線性表

p=rearA->next;
rearA->next=rearB->next->next;
rearB->next=p;
free(p);

雙向連結清單

雙向連結清單的存儲結構

《大話資料結構》第三章線性表

typedef struct DulNode
{
    ElemType data;
    struct DulNode *prior;
    struct DulNode *next;
} DulNode, *DuLinkList;

雙向連結清單的插入s操作

s->prior=p;
s->next=p->next;
p->next=s;
p->next->prior=s;

Status DuListInsert(DuLinkList *L, int i, ElemType e){
    int j;
    DuLinkList p,s;
    p=*L;
    j=;

    while(p->next && j<i){
        ++j;
        p=p->next;
    }

    if(!p || j>i)
        return ERROR;

    s=(DuLinkList)malloc(sizeof(DulNode));
    s->data=e;
    s->next=p;
    s->prior=p->prior;
    p->prior=s;
    s->prior->next=s;

    return OK;
}

雙向連結清單的删除p操作

p->next->prior = p->prior;
p->prior->next = p->next;
free(p);

Status DuListDelete(DuLinkList *L, int i, ElemType *e){
    int j;
    DuLinkList p;
    p=*L;
    j=;

    while(p->next && j<i){
        p=p->next;
        ++j;
    }

    if(!p || j>i)
        return ERROR;

    *e=p->data;
    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);

    return OK;
}

《大話資料結構》第三章線性表

第三章線性表

繼續閱讀

樹的基本概念(定義、基本術語、性質)

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器

《大話資料結構》第三章 線性表

第三章 線性表

繼續閱讀

《大話資料結構》第三章線性表

第三章線性表