Las Nubes
0%

数据结构之线性表

Posted on Edited on

线性表顺序表示和实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include "malloc.h"
#include "stdlib.h"

#define LIST_INIT_SIZE 80
#define LIST_INCREMENT 10
#define OK 1;

typedef int Status;

typedef struct{
    char name[8];
    int age;
}ElemType;

typedef struct {
    ElemType *elem;
    int length; //当前长度
    int listSize; //当前分配的存储容量
}SqList;

Status InitList_Sq( SqList *L ){
    L->elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!L->elem) _exit(0);
    L->length = 0;
    L->listSize = LIST_INIT_SIZE;
    return OK;
}

Status ListInsert_Sq(SqList *L,int i,ElemType e){
    if(i<0 || i > L->length+1 )
        _exit(0);

    if(L->length+1>L->listSize){
        L->elem = (ElemType*)realloc(L->elem,LIST_INCREMENT*sizeof(ElemType)+L->listSize*sizeof(ElemType));
        L->listSize += LIST_INCREMENT;
        if(!L->elem)
            exit(0);
    }
    i -= 1;
    int j;
    for(j=L->length;j>i-1;j--)
        L->elem[j] = L->elem[j-1];
    L->elem[j] = e;
    L->length++;

    return OK;
}

Status ListDelete_Sq(SqList *L,int i,ElemType *e){
    int j;
    if(i<1 || i>L->length)
        exit(0);

    for(j=0;j<i-1;j++)
        L->elem[j] = L->elem[j+1];

    L->length--;
    return OK;
}

顺序表的链式表示和实现

头结点：在单链表上设置一个结点，它本身不存放数据，它的指针域指向第一个元素的地址。

首元结点： 链表中第一个元素所在的节点，它是头节点后边的第一个节点。

头指针：链表的头指针永远指向链表中第一个节点的位置，换句话说，如果链表有头节点，头指针指向头节点；否则，头指针指向首元节点。

是实话，不一理解为啥一定要有头指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include "stdio.h"
#include "malloc.h"
#include "stdlib.h"

#define OK 1
#define ERROR 0

typedef int Status;

//typedef struct{
//    char name[8];
//    int age;
//}ElemType;

typedef int ElemType;

typedef struct LNode {
    ElemType data;
    struct LNode* next;
}LNode, * LinkList;

Status InitList(LinkList& L) {
    L = (LinkList)malloc(sizeof(LNode));
    if (!L) return ERROR;
    L->next = nullptr;
    return OK;
}

Status InsertList(LinkList& L, int i, ElemType m) {
    int j = 1;
    LNode* pre = L;
    if (i < 1) return ERROR;
    while (j++ < i && pre->next != nullptr)
        pre = pre->next;
    LNode* newLNode = (LNode*) malloc(sizeof (LNode));
    newLNode->data = m;
    newLNode->next = pre->next;
    pre->next = newLNode;
    return OK;
}

Status FindInList(LinkList& L, int i, ElemType &m) {
    int j = 1;
    LNode* pre = L;
    if (i < 1) return ERROR;
    while (j++ < i && pre->next != nullptr)
        pre = pre->next;
    if (j - 1 != i || pre->next == nullptr)
        return ERROR;

    m = pre->next->data;
    return OK;
}

int main() {
    LinkList L = nullptr;
    int i;

    if (InitList(L) != OK) {
        printf("hhhhhh");
        return 0;
    }

    for (i = 1; i < 10; i++) {
        if (InsertList(L, i,i) != OK) {
            printf("hhhhh:%d", i);
            return 0;
        } else{
            printf("insert Ok:%d\n",i);
        }
    }

    ElemType  m = 0;
    for (i = 1; i < 10; i++) {
        if (FindInList(L, i, m) == OK) {
            printf("%d %d\n", i, m);
        }
        else{
            printf("find wrong:%d\n",i);
        }
    }

    printf("Ok");
    return 1;
}

循环链表与双向链表

循环链表：单链表最后一个结点的指针域没有利用， 如果使其指向头指针（头结点），则首尾构成 一个循环，称作循环链表。

优点：从表中任一结点出发均可找到表中其它结点。

特点：在循环链表中多采用尾指针，指向表尾的指针称为是尾指针。采用头指针时，查找第一个结点容易，查找尾结 点不容易，如果采用尾指针，则查找第一个结点和最后 一个结点都容易。

双向链表： 一个链表的每一个结点含有两个指针域：一个指针指向 其前驱结点，另一个指针指向其后继结点，这样的链表称为 双向链表。

小练习

  • 设L为带头结点的单链表，编写算法从头到尾反向输出每个结点的值。

    1
    2
    3
    4
    5
    6
    7
    void VersePrint(LinkList L){
        if(L->next == NULL){}
        else{
            VersePrint(L->next);
            printf("%d\n",L->next->data);
        }
    }