线性表c

发表于 | 分类于
字数统计: 1.5k

线性表的抽象数据类型

线性表（简称为表）是零个或多个元素的有穷序列。

$L=(k_{0},k_{1},\dots,k_{n-1})$

线性表的逻辑结构：$L=<K,R>$

其中$K={k_{0},k_{1},\dots,k_{n-1}}$,$R={<k_{i},k_{i+1}>|0\le i\le n-2}$,$i$称为元素$k_{i}$的索引或下标，表中的元素又称表目。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
ADT List is
    operations
    List createNullList(void)//创建并返回一个空线性表
    int insertPre(List list,position p,DataType x)
    //在list中p位置前插入值为x的元素，并返回插入成功与否的标志
    int insertPost(List list, position p,DataType x)
    //在list中p位置后插入值为x的元素，并返回插入成功与否的标志
    int deleteV(List list,DataType x)
    //在list中删除一个值为x的元素，并返回删除成功与否的标志
    int deleteP(List list,position p)
    //在list中删除位置为p的元素，并返回删除成功与否的标志
    Position locate(List list,DataType x)
    //在list中查找值为x的元素的位置
    int isNLL(List list)
    //判断list是否为空线性表
end ADT List;

顺序表的c语言描述

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
struct SeqList{
    int MAXNUM;//顺序表可以存放的元素个数
    int n;//实际存放在线性表中元素的个数
    DataType * element;//element[0],……,element[n-1]存放线性表中的元素
}
typedef struct SeqList *PSeqList;
/*如果palist是一个PSeqList类型的指针变量，则：
palist->MAXNUM：顺序表中可以存放元素的个数；
palist->n:顺序表中实际元素的个数
palist->element[0],……,palist->element[n-1]:顺序表中的各个元素*/

//顺序表的基本操作
//创建空顺序表
PSeqList createNullList_seq(int m){
    /*创建新的顺序表*/
    PSeqList palist = (PSeqList)malloc(sizeof(struct SeqList));
    if (palist!=NULL){
        palist->element=(DataType*)malloc(sizeof(DataType)*m);
        if(palist>element){
            palist->MAXNUM=m;
            palist->n=0;/*空表长度为0*/
            return palist;
        }
        else free palist;
    }
    printf("Out of space!\n");/*存储分配失败*/
    return NULL;
}

//判断线性表是否为空
int isNullList_seq(PSeqList palist){
    /*判别palist所指顺序表是否为空表*/
    return (palist->n==0);
}

//在顺序表中求某元素的下标
int locate_seq(PSeqList palist,DataType x){
    /*求x在palist所指顺序表中的下标*/
    int q;
    for (q=0;q<palist->n;q++)
        if (palist->element[q]==x)
            return q;
    return -1;
}

//顺序表的插入
int insertPre_seq(PSeqList palist,int p,DataType x){
    /*在palist所指顺序表中下标为p的元素之前插入元素x*/
    int q;
    if (palist->n >= palist->MAXNUM){ /*溢出*/
        printf("Overflow!\n");
        return 0;
    }
    if (p<0 || p>palist->n){  /*不存在下表为p的元素*/
        printf("Not Exist!\n");
        return 0;
    }
    for(q=palist->n-1;q>=p;q--) /*插入位置及之后的元素均后移一个位置*/
        palist->element[q+1] = palist->element[q];
    palist->element[p]=x;  /*插入元素x*/
    palist->n=palist->n+1; /*元素个数加1*/
    return 1;
}

//顺序表中按下标删除元素
int deleteP_seq(PSeqList palist,int p){
    /*在palist所指顺序表中删除下标为p的元素*/
    int q;
    if (p<0||p>palist->n-1){ /*不存在下标志为p的元素*/
        printf("Not exist!\n");
        return 0;        
    }
    for(q=p;q<palist->n-1;p++){ /*被删除元素之后的元素均前移一个位置*/
        palist->element[q]=palist->element[q+1];
   	palist->n=palist->n-1;  /*元素个数减1*/
    return 1;
    }
}

//顺序表中按值删除元素
int deleteV_seq(PSeqList palist,DataType x){
    /*实现的算法只要首先调用locate_seq(palist,x),在palist所指顺序表中寻找一个值为x的元素的下标，假设为p，然后调用deleteP_seq(palist,p)即可*/
    p=locate_seq(palist,x);
    deleteP_seq(palist,p);
    return 0;
}

单链表的C语言描述

每个节点包括两个域：

  1. 数据域：存放元素本身信息。

  2. 指针域：存放其后继节点的存储位置

    （1）最后一个元素的指针不指向任何节点，称为空指针，用“NULL”表示；

    （2）指向链表中第一个节点的指针称为这个链表的头指针。

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
struct Node;	//单链表节点类型
typedef struct Node * PNode; //节点指针类型
struct Node{	//单链表节点结构
    DataType info;
    PNode link;
};

typedef struct Node * LinkList;	/*单链表类型*/
LinkList llist;	/*llist是一个链表的头指针*/

//创建一个带头结点的空单链表
LinkList createNullList_link(void){
    LinkList llist;
    //申请头节点空间
    llist = (LinkList)malloc(sizeof(struct Node));
    if (llist!=NULL)
        llist->link = NULL;
    else
        printf("Out of space!\n");//创建失败
    return llist;
}

//判断单链表是否为空
int isNullList_link(LinkList llist){
    return (llist->link==NULL);
    /*因为llist指向头节点，总是非空，所以算法中只要检查llist->link是否为空即可*/
}

//在带头节点的单链表llist中找第一个值为x的节点存储位置
PNode locate_link(LinkList llist, Datatype x){
    PNode p;
    if (llist==NULL) 
        return NULL;//找不到时返回空指针
    p = llist->link;
    while(p!=NULL && p->info!=x)
        p=p->link;
    return p;
}

/*在带头结点的单链表llist中下表为p的节点后插入值为x的新节点*/
int insertPost_link(LinkList llist,PNode p,Datatype x){
    PNode q = (PNode)malloc(sizeof(Struct Node)); /*申请新节点*/
    if (q==NULL){
        printf("Out of space!\n");
        return 0;
    }
    else{
        q->info = x;
        q->link = p->link;/*注意指针更新次序*/
        p->link = q;
        return 1;
}
}

//在单链表中求p所指节点的前驱
PNode locatePre_link(LinkList llist, PNode p){
    PNode p1;
    if(llist==NULL) 
        return NULL;
    p1 = llist;
    while(p1!=NULL && p1->link!=p)
        p1 = p1->link;
    return p1;
}

/*在带头结点的单链表llist中，删除第一个元素值为x的节点（这里要求DataType可以使用！=比较）*/
int deleteV_link(LinkList llist,DataType x){
    PNode p,q;
    p = llist;
    if (p==NULL)
        return 0;
    while(p->link != NULL && p->link->info!=x)
        p = p->link;/*找到值为x的节点的前驱节点的存储位置*/
    if(p->link == NULL){/*没有找到值为x的节点*/
        printf("Not exists!\n");
        return 0;
	}
    else{
        q = p->link;/*找到值为x的节点*/
        p->link = q->link;/*删除该节点*/
        free(q);
        return 1;
    }    
}