线性表的代码实现(C语言)

119 阅读 0 评论 79 点赞

我是靠谱客的博主傲娇枫叶，这篇文章主要介绍线性表的代码实现(C语言)，现在分享给大家，希望可以做个参考。

一、线性表顺序结构实现

初始化一个空的线性表

复制代码

1
2
3
4
5
6
7
8
9
10
int InitList(SqList *L){
	L->elem = (ElemType *) malloc(list_init_size * sizeof(ElemType));
    if (!L->elem) {
        exit(OVERFLOW);
    }
    L->length = 0;
    L->listsize = list_init_size;
	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
int InputList(SqList *L, int n) {

    int i, *newbase;

    if (n < 0) {
        return ERROR;
    }

    if (n > L->listsize) {

        newbase = (ElemType *) malloc(listincreament * sizeof(ElemType));
        if (!newbase) {
            exit(OVERFLOW);
        }

        L->elem = newbase;
        L->listsize += listincreament;
    }
    for (i = 0; i < n; i++) {
        printf("请输入第 %d 个元素：",i+1);
        scanf("%d", &L->elem[i]);
        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
int InsertList(SqList *L, int i, int e) {

    int *newbase;
    int *p;
    int *q;
    if (i < 1 || i > L->length + 1) return ERROR;
    if (L->length >= L->listsize) {

        newbase = (ElemType *) realloc(L->elem, (L->listsize + listincreament) * sizeof(ElemType));
        if (!newbase) exit(OVERFLOW);
        for (int j = 0; j < L->length; j++) {
            newbase[j] = L->elem[j];

        }
        L->elem = newbase;
        L->listsize += listincreament;
    }
    q = &(L->elem[i - 1]);
    printf("%d",q);
    for (p = &(L->elem[L->length - 1]); p >= q; p--)
        printf("%dt",p);
        *(p + 1) = *p;
    *q = e;
    L->length += 1;
    return L->length;
}

输出线性表中的元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
int OutputList(SqList *L, int i) {

    int j;
    printf("更新后的线性表为：");
    for (j = 0; j < i; j++) {
        printf("%dt", L->elem[j]);

    }

    return OK;
}

在线性表中删除第i个元素,并用e返回其值

复制代码

1
2
3
4
5
6
7
8
9
10
int DeleteList(SqList *L, int i, int *e) {

    if (i < 1 || i > L->length) return ERROR;
    e = L->elem[i - 1];
    int *p = &L->elem[i - 1];
    for (int *q = p + 1; q <= p + (L->length - i); q++) *(q - 1) = *q;
    L->length -= 1;
    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
int main() {
    SqList S;
    char a;
    a = 'Y';
    int k, data, position, *e;
    InitList(&S);
    printf("请输入元素的个数: ");
    scanf("%d", &k);
    InputList(&S, k);
    while (a == 'Y') {
        printf("请输入要插入的元素：");
        scanf("%d", &data);
        printf("请输入要插入的位置： ");
        scanf("%d", &position);
        InsertList(&S, position, data);
        printf(&S.length);
        OutputList(&S, k + 1);
        printf("n请输入要删除的元素的位置： ");
        scanf("%d", &position);
        DeleteList(&S, position, e);
        OutputList(&S, k);
        printf("请问是否继续?(Y:继续 N:结束)n");
        getchar();
        scanf("%c", &a);

    }

    system("pause");

    return OK;
}

二、线性表链式结构实现

初始化空的链表

复制代码

1
2
3
4
5
6
7
8
9
10
11
Status InitList(LinkList L){

    L = (LinkList) malloc(sizeof(LNode));
    if(!L){
        exit(-1);
    }
    L->next = NULL;

    return OK;
}

求线性表的表长

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
Status GetListLen(LinkList L){
    LinkList P;
    int count = 0;
    P = L->next;
    while(P){
        P = P->next;
        count++;
    }

    return count;
}

查找指定位序的元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
Status CheckListByOrder(LinkList L, int k){

    LinkList P;
    int count = 1;
    P = L->next;
    while(P && count < k){
        P = P->next;
        count++;
    }

    if ((count == k)&&P){
        printf("你查找的元素为:%dn",P->data);
    } else {
        printf("元素不存在n");
    }
}

按值查找线性表的元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status CheckListValue(LinkList L, int X){

    LinkList P;
    P = L->next;
    while(P && (P->data!=X)){
        P = P->next;
    }
    if (P){
        printf("查找成功,你查找的元素为:%d",P->data);
    } else {
        printf("没有此元素");
    }
}

向线性表中插入元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Status InsertList(LinkList L, int i, ElemType e){

    LinkList P, S;
    int count = 0;
    P = L;
    while(P && (count < i-1)){
        P = P->next;
        count++;
    }
    if (!P || count > i-1){
        return -1;
    } else {
        S = (LinkList)malloc(sizeof(LNode));
        S->data = e;
        S->next = P->next;
        P->next = S;
    }

    return OK;
}

删除线性表中指定的元素

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Status DeleteList(LinkList L, int i){

    LinkList P, Q;
    int count = 0;
    P = L;
    while(P && count < i-1){
        P = P->next;
        count++;
    }
    if (!(P->next) && count >i-1){
        printf("参数错误！n");
    } else {
        Q = P->next;
        P->next = Q->next;
        free(Q);
    }

    return OK;
}

输出线性链表

复制代码

1
2
3
4
5
6
7
8
9
10
11
void ExportList(LinkList L){

    LinkList P = L->next;
    printf("更新的链表为:");
    while (P){
        printf("%dt",P->data);
        P = P->next;
    }

}

主函数

复制代码

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
int main(){

    LinkList ML;
    InitList(ML);
    int j,n,x,len,cz,xz,del;
    char a = 'Y';
    while (a == 'Y'){
    printf("请输入插入值的个数:");
    scanf("%d",&n);
    for (j = 1; j <= n; j++) {
        printf("请输入第 %d 个插入的值:",j);
        scanf("%d",&x);
        InsertList(ML, j, x);
    }

    // 输出链表的值
    ExportList(ML);
    printf("n");

    // 求表长
    len = GetListLen(ML);
    printf("链表的长度为:%dn",len);

    // 按值查找
    printf("请输入按值查找的数:");
    scanf("%d",&cz);
    CheckListValue(ML, cz);
    printf("n");

    // 按序号查找
    printf("请输入要查找的数的序号:");
    scanf("%d",&xz);
    CheckListByOrder(ML, xz);
    printf("n");

    // 删除
    printf("请输入要删除数的下标:");
    scanf("%d",&del);
    DeleteList(ML, del);
    ExportList(ML);
    printf("n");
    printf("请否需要继续:");
    getchar();
    scanf("%c",&a);

    }
    return 0;
}