期中数据结构总结

单链表

单链表的节点

单链表的节点分为数据域和指针域，可以将它们视为一个整体，称之为节点，稍后我们会用结构体来表示节点。
数据域，顾名思义，就是存放数据的地方。
指针域，是用来存放指针变量的地方，指针指向下一个节点的地址。

单链表的表示

单链表是线性表的链式表示和实现。把节点链接起来，就形成了单链表。

定义表示节点的结构体

如何用C语言描述节点？这里我们用到了struct。

1
2
3
4
5
6


struct node {
    /* 后继节点 */
    struct node *next;
    /* 值 */
    int data;
};

首先我们定义了一个结构体，结构体的标记为node。
其次，它具有两个属性，一个是int类型的data，也就是上文提到的数据域。还一个是指针域。 如何理解struct node *next呢？
要知道，指针域是存放指针变量的，这个变量名叫做 next,又因为这个指针是指向下一个节点的地址的，换句话说，这个指针指向的是一个我们定义的用来表示节点的结构体。所以这个指针变量的类型为 struct node。星号*表示它是指针变量。所以合起来就是struct node *next。最后，为了方便，我们可以使用typedef关键字为struct node取一个别名。

1
2
3
4
5
6


typedef struct node {
    /* 后继节点 */
    struct node *next;
    /* 值 */
    int data;
}list;

这样，在后面的代码书写中, list就等价于struct node了。比如我们使用这个结构体创建一个新的节点， list *new_node就等价于struct node *new_node。

单链表的创建

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


list * create_list()
{
    /* 创建一个新的节点，由于使用了typedef关键字，此处 node *head与struct node *head等价    */
    list *head = (list *)malloc(sizeof(list));
    if(head==NULL) return NULL;
    /* 初始化节点 */
    head->data = 0; // 头结点数据域，我们用来表示链表长度
    head->next = NULL; 
    return head;
}

此函数会创建一个单链表，并返回头指针。头指针是指向头结点地址的指针，和节点中指向下一个节点的指针是相同类型。
首先，我们用malloc函数开辟了一块list大小的内存，并返回了指向该内存块首地址的指针，同时将此指针赋值给头指针变量。
接着，判断此指针是否为空，为空，则说明内存申请失败（一般不会）。
然后，对该节点进行初始化。
最后，函数返回头指针，结束。

为什么设置头节点？
头节点的数据域一般无意义，这里为了方便后面的插入和删除操作而设置，头节点并非链表所必须。
头节点后面的第一个元素节点，称为首元节点。

单链表的插入

试想如下情况，一个新的节点n，要插入到x节点后。按照一般思路可能是:

1
2


x->next = n;
n->next = x->next;

显然，这是错误的，因为执行x->next = n之后，n->next = x->next等价于n->next = n ，所以正确的做法应该是这样；

1
2


n->next = x->next;
x->next = n;

完整版插入函数：插入函数接受三个参数，被插入节点的链表的指针head，新结点的数据data，和要插入的位置pos;

 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


list * list_insert_node(list *head, int data, int pos)
{   
    int i;
    list *current = head;

    /* 如果要插入的位置比链表长，则属于非法操作 */
    if(pos > current->data) return NULL;

    /* 创建一个节点，并初始化 */
    list *node = (list *)malloc(sizeof(list));
    if(node==NULL) return NULL;
    node->data = data;
    node->next = NULL;

    /* 遍历链表，找到要插入的位置 */
    for(i=0;i<pos;i++){
        current = current->next;
    }

    /* 插入 */
    node->next = current->next;
    current->next = node;

    /* 链表长度+1 */
    head->data++;
    return head;
}

可以在main函数中调用测试：

1
2
3
4


list *l = create_list();
printf("当前链表长度：%d\n", l->data);
list_insert_node(l, 1, 0);
printf("当前链表长度：%d\n", l->data);

使用gcc编译:

1

gcc -fsanitize=address -fno-omit-frame-pointer  -g linked_list.c  && ./a.out

输出正常且无内存报错信息：

1
2


当前链表长度：0
当前链表长度：1

单链表的遍历

较为简单，不再解释

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


/* 打印链表数据，但不包括头结点的数据*/
void print_list(list *head)
{
    list *current = head->next;
    while (current)
    {
        printf("%d \t", current->data);
        current = current->next;
    }
    printf("\n");
}

单链表的删除

假设要删除head后的节点，那么直接让head->next = head->next->next即可，但不要忘记释放被删除的节点。基于此思路：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


list *list_delete_data(list *head, int pos)
{
    int i;
    list *current = head;

    /* 如果要删除的位置比链表长，则属于非法操作 */
    if(pos > current->data) return NULL;

    /* 遍历链表，找到要删除的节点的前一个节点的指针 */
    for(i=0;i<pos;i++){
        current = current->next;
    }
    // 临时记录将被删除的节点
    list *temp = current->next;
    // 删除节点
    current->next = current->next->next;
    
    //释放掉被删除节点的内存
    free(temp);
    head->data--;
    return head;
}

单链表的测试

这样，一个基础的链表就写好了，可以在main函数中测试。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


int main()
{
    int i;
    list *l = create_list();
    // 多次插入数据
    for(i=0;i<5;i++){
        list_insert_node(l, i, 0);
        print_list(l);
    }
    list_delete_data(l, 0);
    print_list(l);
    return 0;
}

编译与输出：

1
2
3
4
5
6
7


# gcc -fsanitize=address -fno-omit-frame-pointer  -g linked_list.c  && ./a.out
0 
1       0 
2       1       0 
3       2       1       0 
4       3       2       1       0 
3       2       1       0 

完整代码

 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
87
88
89
90
91
92
93
94
95
96


#include <stdio.h>
#include <stdlib.h>

/* 定义表示单链表节点的结构体 */
typedef struct node {
    int data;
    struct node *next;
}list;

/* 创建一个单链表，返回头指针 */
list * create_list()
{
    /* 创建一个新的节点，由于使用了typedef关键字，此处 list *head与struct node *head等价    */
    list *head = (list *)malloc(sizeof(list));
    if(head==NULL) return NULL;
    /* 初始化节点 */
    head->data = 0; // 头结点数据域，我们用来表示链表长度
    head->next = NULL; // 头节点指针域，暂时没有下一个节点，所以为空
    return head;
}

list *list_insert_node(list *head, int data, int pos)
{   
    int i;
    list *current = head;

    /* 如果要插入的位置比链表长，则属于非法操作 */
    if(pos > current->data) return NULL;

    /* 创建一个节点，并初始化 */
    list *node = (list *)malloc(sizeof(list));
    if(node==NULL) return NULL;
    node->data = data;
    node->next = NULL;

    /* 遍历链表，找到要插入的位置 */
    for(i=0;i<pos;i++){
        current = current->next;
    }

    /* 插入 */
    node->next = current->next;
    current->next = node;

    /* 链表长度+1 */
    head->data++;
    return head;
}

/* 打印链表数据，但不包括头结点的数据*/
void print_list(list *head)
{
    list *current = head->next;
    while (current)
    {
        printf("%d \t", current->data);
        current = current->next;
    }
    printf("\n");
}


list *list_delete_data(list *head, int pos)
{
    int i;
    list *current = head;

    /* 如果要删除的位置比链表长，则属于非法操作 */
    if(pos > current->data) return NULL;

    /* 遍历链表，找到要删除的节点的前一个节点的指针 */
    for(i=0;i<pos;i++){
        current = current->next;
    }
    // 临时记录将被删除的节点
    list *temp = current->next;
    current->next = current->next->next;
    
    //释放掉被删除节点的内存
    free(temp);
    head->data--;
    return head;
}

int main()
{
    int i;
    list *l = create_list();
    for(i=0;i<5;i++){
        list_insert_node(l, i, 0);
        print_list(l);
    }
    list_delete_data(l, 0);
    print_list(l);
    return 0;
}

双链表

关于双端链表

双端链表也叫双向链表或双链表，它是一种非常实用的数据结构。单链表的节点只有一个指针域，且指向下一个节点，而双链表则有两个指针域，分别指向直接前驱和直接后继。同时也意味着，表头和表尾都能方便的进行插入和删除的操作，进而能轻易同时实现栈和队列的功能。

双端链表的实现

双链表的表示

双链表可以用表示链表节点的list_node和表示链表本身的list两个结构体来表示。下面的代码，参考了redis的双端链表。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/* 链表节点 */
typedef struct list_node 
{   
    /* 前驱节点 */
    struct list_node *prev;
    /* 后继节点 */
    struct list_node *next;
    /* 值 */
    void *value;
} list_node;

/* 链表 */
typedef struct list
{   
    /* 表长度 */
    unsigned long length;
    /* 表头 */
    list_node *head;
    /* 表尾 */
    list_node *tail;
} list;

链表节点(list_node)带有prev和next两个指针，这意味着，可以从表头到表尾或表尾到表头两个方向遍历或迭代链表。
链表本身(list)和队列(queue)类似，维护head和tail两个指针，这意味着，在表头或者表尾的插入的复杂度为O(1)，而单链表在表尾执行插入操作时，需要从表头遍历到表尾后插入，复杂度为O(n)。

函数清单

下面是用于操作队列的函数名及其作用与复杂度

函数	作用	算法复杂度
list_create	创建新链表	O(1)
list_empty	清空链表节点，但不清除链表本身	O(N)
list_release	清除整个链表	O(N)
list_add_node_head	在表头添加一个节点	O(1)
list_add_node_tail	在表尾添加一个节点	O(1)
list_get_value_head	获取表头节点数据	O(1)
list_get_value_tail	获取表尾节点数据	O(1)
list_del_node	删除一个节点	O(1)
list_get_iterator	创建一个迭代器	O(1)
list_release_iterator	释放迭代器	O(1)
list_next	获取迭代器下一个节点值	O(1)

双链表的创建

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* 创建链表 */
list *list_create(void)
{
    /* 创建链表 */
    list *list = (struct list *)malloc(sizeof(struct list));
    if(list==NULL) return NULL;
    
    /* 初始化链表 */
    list->head = list->tail = NULL;
    list->length = 0;
    
    return list;
}

表头插入操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/* 添加一个节点在链表头部 */
list * list_add_node_head(list *list, void *value)
{   
    /* 新建一个链表节点 */
    list_node *node = (list_node *)malloc(sizeof(list_node));
    if(node==NULL) return NULL;
    node->value = value;
    /* 如果链表为空 */
    if(list->length == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    }else {
        /* 设置新节点 */
        node->prev = NULL;
        node->next = list->head;
        /* 设置链表 */
        list->head->prev = node;
        list->head = node;
    }
    list->length++;
    return list;
}

首先，创建一个新的链表节点。
然后，判断双链表的长度，也即判断双链表是否为空。
如果为空，则让链表的头尾指针head与tail都指向该新节点，且新节点(node)指向前驱节点的指针prev和指向后继节点的指针next都设置为NULL。

如果不为空，则说明链表中已有节点存在。
此时，先设置新节点，指针prev置为NULL，指针next指向链表头指针(head)指向的节点，也即表头节点。
然后让头指针指向的节点的prev指针指向新节点。
最后，将指针head指向新节点。

执行完节点的插入操作后，别忘了让链表长度自增1。

表尾插入操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 添加一个节点在链表尾部 */
list * list_add_node_tail(list *list, void *value)
{
    /* 新建一个链表节点 */
    list_node *node = (list_node *)malloc(sizeof(list_node));
    if(node==NULL) return NULL;
    node->value = value;
    if(list->length==0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->length++;
    return list;
}

首先，也要创建一个新的链表节点。
接着也需要判断链表是否为空，如果是，则与链表为空时表头的插入操作相同。
否则，让新节点prev指向链表表尾节点，next置为NULL。
然后，链表的tail->next指向新节点，表尾指针tail指向新节点。
最后，插入完成，链表长度自增1。

节点的删除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 删除一个节点 */
void list_del_node(list *list, list_node *node)
{   
    /* 判断该节点是否有直接前驱 */
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    
    /* 判断该节点是否有直接后继 */
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    
    /* 释放该节点 */
    free(node);
    list->length--;
}

该方法主要用于从表头或者表尾获取数据后对其节点的删除操作。

首先判断该节点是否有直接前驱，如果有，则将直接前驱的next指针指向该节点的直接后继。如果没有，则说明该节点是首元节点，位于表头，将表头指针指向该节点的直接后继即可。

接着是判断该节点是否有直接后继，如果有，则将该节点的直接后继的prev指针指向该节点的直接前驱。如果没有，则说明该节点位于表尾，将表尾指针指向该节点的直接前驱即可。、

最后释放该节点的内存，并将链表长度自减1。

返回表头或表尾数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 获取表头数据 */
void *list_get_value_head(list *list)
{
    if(list->head == NULL) return NULL;
    /* 临时创建一个变量保存数据 */
    void *value = list->head->value;
    /* 删除该节点 */
    list_del_node(list, list->head);
    return value;
}

/* 获取表尾数据 */
void *list_get_value_tail(list *list)
{
    if(list->tail == NULL) return NULL;
    void *value = list->tail->value;
    list_del_node(list, list->tail);
    return value;
}

由于list有表头和表尾指针，所以获得其数据也非常方便。

链表的释放与清除

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


/* 清空链表中所有的节点但是不删除链表本身 */
void list_empty(list *list)
{
    unsigned long length;
    list_node *current, *next;
    current = list->head;
    length = list->length;
    while (length--)
    {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->length = 0;
}

/* 释放整个链表 */
void list_release(list *list)
{
    list_empty(list);
    free(list);
}

在清除链表所有节点时，我们从表头根据链表长度遍历到表尾逐个清除，最后使链表head与tail指针为NULL。
释放整个链表只需要先清除该链表节点，再释放该链表本身即可。

链表迭代器的实现

宏定义迭代器方向

1
2


#define LIST_START_HEAD 0
#define LIST_START_TAIL 1

其中LIST_START_HEAD表示沿着节点的next指针前进，从表头到表尾遍历。
LIST_START_TAIL则表示，沿着节点的prev指针前进，从表尾到表头遍历。

迭代器的表示

1
2
3
4
5
6
7
8


/* 迭代器结构 */
typedef struct list_iter
{
    /* 下一个节点 */
    list_node *next;
    /* 方向 */
    int direction;
}list_iter;

迭代器定义了两个成员，其中next是表示指向下一个节点的指针，direction表示迭代方向，对应上方的宏定义。

迭代器的创建

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* 创建一个迭代器 */
list_iter *list_get_iterator(list *list, int direction)
{
    list_iter *iter = (list_iter *) malloc(sizeof(list_iter));
    if(iter==NULL) return NULL;
    /* 判断迭代方向 */
    if(direction == LIST_START_HEAD)
        iter->next = list->head;
    else 
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

在初始化迭代器时，接受两个参数，分别是需要迭代的链表，和迭代的方向。
判断给定参数，如果从表头遍历到尾遍历，则将迭代器的next指针指向链表的表头，反之则指向表尾。

获取迭代器的下一个数据

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* 返回链表下一个节点值 */
void *list_next(list_iter *iter)
{
    list_node *current = iter->next;
    if (current==NULL) return NULL;

    if(iter->direction == LIST_START_HEAD)
        iter->next = current->next;
    else 
        iter->next = current->prev;

    return current->value;
}

在获取迭代器的下一个数据时，首先判断当前迭代器next指针指向的节点是否为空，如果空，则返回NULL。
接着迭代器next指针根据迭代方向指向下一个节点。
最后返回数据。

迭代器的释放

1
2
3
4
5


/* 释放迭代器内存 */
void list_release_iterator(list_iter *iter)
{
    free(iter);
}

释放迭代器，还是挺简单的。

在main方法中测试

 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


int main() 
{   
    /* 测试数据 */
    char a = 'A';
    char b = 'B';
    char c = 'C';

    /* 创建链表 */
    list *list = list_create(); 
    
    /* 测试空表是否报错 */
    printf("-----测试空链表是否报错\n");
    printf("%p\n", list_get_value_head(list));
    printf("%p\n", list_get_value_tail(list));

    /* 表头添加数据 */
    list_add_node_head(list, &a);
    list_add_node_head(list, &b);
    /* 表尾添加数据 */
    list_add_node_tail(list, &c);
    list_add_node_tail(list, &a);

    printf("-----此时链表长度：%d\n", list->length);
    printf("-----测试表头出队-----\n");
    /* 先出队两次，测试表头出队 */
    while (list->length>2)
    {   
        printf("%c\n", *(char*)list_get_value_head(list));
    }
    printf("-----测试表尾出队-----\n");
    /* 测试表尾出队 */
    while (list->length)
    {   
        printf("%c\n", *(char*)list_get_value_tail(list));
    }

    /* 添加数据 */
    list_add_node_head(list, &a);
    list_add_node_head(list, &b);
    list_add_node_head(list, &c);

    /* 创建一个正向迭代器迭代器 */
    list_iter *iter = list_get_iterator(list, LIST_START_HEAD);
    /* 测试迭代器 */
    printf("-----测试迭代器-------\n");
    printf("%c\n", *(char *)list_next(iter));
    printf("%c\n", *(char *)list_next(iter));

    /* 释放迭代器 */
    list_release_iterator(iter);

    /* 清除链表节点 */
    list_empty(list);
    
    printf("-----测试空链表是否报错\n");
    printf("%p\n", list_get_value_head(list));
    printf("%p\n", list_get_value_tail(list));

    /* 释放链表 */
    list_release(list);

    return 0;
}

编译并输出：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


# gcc -fsanitize=address -fno-omit-frame-pointer  -g list.c  && ./a.out
-----测试空链表是否报错
(nil)
(nil)
-----此时链表长度：4
-----测试表头出队-----
B
A
-----测试表尾出队-----
A
C
-----测试迭代器-------
C
B
-----测试空链表是否报错
(nil)
(nil)

完整代码

  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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152


#include <stdio.h>
#include <stdlib.h>
#include "list.h"


/* 创建链表 */
list *list_create(void)
{
    list *list = (struct list *)malloc(sizeof(struct list));
    if(list==NULL) return NULL;
    list->head = list->tail = NULL;
    list->length = 0;
    return list;
}

/* 清空链表中所有的节点但是不删除链表本身 */
void list_empty(list *list)
{
    unsigned long length;
    list_node *current, *next;
    current = list->head;
    length = list->length;
    while (length--)
    {
        next = current->next;
        free(current);
        current = next;
    }
    list->head = list->tail = NULL;
    list->length = 0;
}

/* 释放整个链表 */
void list_release(list *list)
{
    list_empty(list);
    free(list);
}

/* 创建一个迭代器 */
list_iter *list_get_iterator(list *list, int direction)
{
    list_iter *iter = (list_iter *) malloc(sizeof(list_iter));
    if(iter==NULL) return NULL;
    if(direction == LIST_START_HEAD)
        iter->next = list->head;
    else 
        iter->next = list->tail;
    iter->direction = direction;
    return iter;
}

/* 释放迭代器内存 */
void list_release_iterator(list_iter *iter)
{
    free(iter);
}

/* 返回链表下一个节点值 */
void *list_next(list_iter *iter)
{
    list_node *current = iter->next;
    if (current==NULL) return NULL;
    
    /* 判断迭代器方向，并将迭代器`next`指针指向下一个节点。 */
    if(iter->direction == LIST_START_HEAD)
        iter->next = current->next;
    else 
        iter->next = current->prev;

    return current->value;
}

/* 添加一个节点在链表头部 */
list *list_add_node_head(list *list, void *value)
{   
    /* 新建一个链表节点 */
    list_node *node = (list_node *)malloc(sizeof(list_node));
    if(node==NULL) return NULL;
    node->value = value;
    /* 如果链表为空 */
    if(list->length == 0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    }else{
        node->prev = NULL;
        node->next = list->head;
        list->head->prev = node;
        list->head = node;
    }
    list->length++;
    return list;
}

/* 添加一个节点在链表尾部 */
list *list_add_node_tail(list *list, void *value)
{
    /* 新建一个链表节点 */
    list_node *node = (list_node *)malloc(sizeof(list_node));
    if(node==NULL) return NULL;
    node->value = value;
    if(list->length==0) {
        list->head = list->tail = node;
        node->prev = node->next = NULL;
    } else {
        node->prev = list->tail;
        node->next = NULL;
        list->tail->next = node;
        list->tail = node;
    }
    list->length++;
    return list;
}


/* 删除一个节点 */
void list_del_node(list *list, list_node *node)
{   
    /* 判断该节点是否有直接前驱 */
    if (node->prev)
        node->prev->next = node->next;
    else
        list->head = node->next;
    
    /* 判断该节点是否有直接后继 */
    if (node->next)
        node->next->prev = node->prev;
    else
        list->tail = node->prev;
    
    /* 释放该节点 */
    free(node);
    list->length--;
}

/* 获取头部元素 */
void *list_get_value_head(list *list)
{
    if(list->head == NULL) return NULL;
    void *value = list->head->value;
    list_del_node(list, list->head);
    return value;
}

/* 获取尾部元素 */
void *list_get_value_tail(list *list)
{
    if(list->tail == NULL) return NULL;
    void *value = list->tail->value;
    list_del_node(list, list->tail);
    return value;
}

栈

什么是栈

栈（stack）是一种后进先出（Last In First Out, LIFO）的线性表，表尾有特殊含义，称为栈顶（top）。

栈的操作

栈最常用的操作有两种，一种是在表尾插入元素的操作称为入栈（push），也叫压栈；另一种是在表尾删除元素的操作称为出栈（pop）, 也叫弹栈。

栈的表示

栈有可以用数组表示，也即顺序栈，也可以用链表表示，叫做链式栈，简称链栈（本文主要讨论对象）。
单链表可以在表头、表尾或者其他任意合法位置插入元素，如果只能在单链表的表尾插入和删除元素，那么就可以将其视为链栈。
因此，在单链表的基础上，我们再维护一个top指针即可。

栈的节点定义与top指针

定义表示链栈节点的结构体

1
2
3
4


typedef struct stack_node {
    struct stack_node *next;
    void *data;
}stack_node;

定义表示链栈的结构体

1
2
3
4


typedef struct stack {
    struct stack_node *top;
    int length; // 表示栈的高度
}stack;

注意，top指针指向的是一个表示栈的节点的结构体。

函数清单

下面是用于操作栈的函数名及其作用与复杂度

函数	作用	算法复杂度
stack_create	创建新的链式栈	O(1)
stack_release	释放栈，以及栈中的节点	O(N)
stack_push	入栈	O(1)
stack_pop	出栈	O(1)
stack_empty	释放栈中所有节点，但不释放栈本身	O(N)

创建栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


/* 创建栈 */
stack *stack_create()
{
    stack *stack =  (struct stack*)malloc(sizeof(struct stack));
    /* 等价写法：
    stack *s =  (stack*)malloc(sizeof(stack)); */
    if(stack==NULL) return NULL;
    /* 初始化 */
    stack->length = 0;
    stack->top = NULL;
    return stack;
}

入栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/* 入栈 */
stack *stack_push(stack *stack, void *data)
{
    /* 创建一个节点 */
    stack_node *node = (struct stack_node*)malloc(sizeof(struct stack_node));
    if(node==NULL) return NULL;
    node->data = data;

    /* 插入 */
    node->next = stack->top;
    stack->top = node;

    stack->length++;
    return stack;
}

在有元素入栈时，首先创建一个节点，然后执行插入操作，将新节点的后继节点next指向栈顶节点，接着移动栈顶指针至指向新节点node。最后，栈的高度自增1。

出栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


/* 出栈 */
void *stack_pop(stack *stack)
{
    /* 临时保存栈顶元素 */
    stack_node *current = stack->top;
    if(current==NULL) return NULL;
    void *data = current->data;
    stack->top = stack->top->next;

    free(current);
    stack->length--;
    return data;
}

出栈时，首先临时保存栈顶节点指针，用于在返回栈顶节点数据域的值之前的释放操作。接着移动栈顶指针至栈顶节点的下一个节点。最后释放临时保存的节点，栈的高度自减1，返回数据，出栈操作完成。

清空栈

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/* 清空栈中所有元素，但不释放栈本身 */
void stack_empty(stack *stack)
{
    int length = stack->length;
    stack_node *current, *next;
    current = stack->top;

    /* 根据栈的高度确定删除节点的次数 */
    while (length--)
    {
        next = current->next;
        free(current);
        current = next; 
    }
    
    stack->length = 0;
    stack->top = NULL;
}

清除栈

1
2
3
4
5
6


/* 清空栈中所有元素并删除栈 */
void stack_release(stack *stack)
{
    stack_empty(stack);
    free(stack);
}

测试

同样的，我们在main函数中测试。

 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


int main()
{
    char a = 'a';
    char b = 'b';
    char c = 'c';

    /* 创建一个栈 */
    stack *stack = stack_create();

    printf("%p\n", stack_pop(stack));

    /* 压栈 */
    stack_push(stack, &a);
    stack_push(stack, &b);
    stack_push(stack, &c);
    /* 出栈 */
    while (stack->length > 0)
    {
        printf("%c\n", *(char *)stack_pop(stack));
    }

    /* 压栈 */
    stack_push(stack, &a);
    stack_empty(stack);
    printf("%p\n", stack_pop(stack));

    /* 释放栈 */
    stack_release(stack);
    return 0;
}

编译并输出

1
2
3
4
5
6


# gcc -fsanitize=address -fno-omit-frame-pointer  -g stack.c  && ./a.out
(nil)
c
b
a
(nil)

完整代码

 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


#include <stdio.h>
#include <stdlib.h>
#include "stack.h"

/* 创建栈 */
stack *stack_create()
{
    stack *stack =  (struct stack*)malloc(sizeof(struct stack));
    /* 等价写法：
    stack *s =  (stack*)malloc(sizeof(stack)); */
    if(stack==NULL) return NULL;
    /* 初始化 */
    stack->length = 0;
    stack->top = NULL;
    return stack;
}

/* 入栈 */
stack *stack_push(stack *stack, void *data)
{
    /* 创建一个节点 */
    stack_node *node = (struct stack_node*)malloc(sizeof(struct stack_node));
    if(node==NULL) return NULL;
    node->data = data;

    /* 插入 */
    node->next = stack->top;
    stack->top = node;

    stack->length++;
    return stack;
}


/* 出栈 */
void *stack_pop(stack *stack)
{
    /* 临时保存栈顶元素 */
    stack_node *current = stack->top;
    if(current==NULL) return NULL;
    void *data = current->data;
    stack->top = stack->top->next;

    free(current);
    stack->length--;
    return data;
}

/* 清空栈中所有元素，但不清除栈本身 */
void stack_empty(stack *stack)
{
    int length = stack->length;
    stack_node *current, *next;
    current = stack->top;
    /* 根据栈的高度确定删除节点的次数 */
    while (length--)
    {
        next = current->next;
        free(current);
        current = next; 
    }
    
    stack->length = 0;
    stack->top = NULL;
}

/* 清空栈中所有元素并删除栈 */
void stack_release(stack *stack)
{
    stack_empty(stack);
    free(stack);
}

队列

什么是队列

队列（queue）是一种先进先出（First In First Out， FIFO）的线性表。

队列的表示

队列也有顺序和链式两种表示方法。同样，我们可以将链式队列理解为一种特殊的链表，只允许在表头删除，在表尾插入。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


/* 队列节点 */
typedef struct queue_node {
    /* 后继节点 */
    struct queue_node *next;
    /* 值 */
    void *data;
}queue_node;

/* 队列本身 */
typedef struct queue {
    /* 队头 */
    struct queue_node *head;
    /* 队尾 */
    struct queue_node *tail;
    /* 队列长度 */
    int length;
}queue;

队列的操作

通常来说，队列常用的操作也是插入和删除两种。为了方便理解，可以将执行删除的一端称为队头（head），执行插入操作的一端称为队尾（tail）。

函数清单

下面是用于操作队列的函数名及其作用与复杂度

函数	作用	算法复杂度
queue_create	创建新队列	O(1)
queue_release	释放队列，以及队列中的节点	O(N)
queue_push_data	入队	O(1)
queue_pull_data	出队	O(1)
queue_empty	释放队列中节点(头节点除外)，但不释放队列本身	O(N)

创建新队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


/* 创建队列 */
queue *queue_create()
{
    /* 创建一个队列 */
    queue *queue = (struct queue*)malloc(sizeof(struct queue));
    
    /* 为了方便操作，队列默认创建一个队列节点 */
    queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
    if(queue==NULL || node==NULL) return NULL;

    node->data = NULL;
    node->next = NULL;
    
    /* 初始化队列 */
    queue->head = queue->tail = node;
    queue->length = 0;

    return queue;
}

在创建新队列时，首先创建队列本身，接着，创建一个队列节点（头节点），并将队列的head和tail指针都指向这个节点。最后，队列的长度设置为0。

入队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


/* 入队 */
queue *queue_push_data(queue *queue, void *data)
{
    /* 创建一个节点 */
    queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
    if(node==NULL) return NULL;
    node->data = data;

    /* 在队尾插入元素 */
    queue->tail->next = node;
    queue->tail = queue->tail->next;

    queue->length++;
    return queue;
}

在有元素需要入队的时候，执行在表尾的插入操作。
首先创建一个新的节点，接着让最后一个节点，也即队尾指针tail指向的节点的next指针指向新的节点，然后，队尾指针tail也指向新的节点。最后，队列长度自增1。

出队

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


/* 出队 */
void* queue_pull_data(queue *queue)
{
    queue_node *current = queue->head->next;
    
    /* 判断队列中是否有数据 */
    if(current==NULL) return NULL;

    void *data = current->data;
    
    queue->head->next = current->next;
    
    /* 判断队列中除头结点外，是否只有一个节点，避免尾指针丢失 */
    if(queue->tail==current) {
        queue->tail = queue->head;
    }

    free(current);
    queue->length--;
    return data;
}

有元素出队时，首先判断队列是否有数据，如果没有，则返回NULL，如果没有，则返回头节点的下一个节点（首元节点）的数据。
接着，判断队列中除头结点外，是否只有一个节点。如果只有首元节点，那么下一步释放首元节点的内存时，tail指针将会被一同释放，进而造成尾指针的丢失。
最后，释放出队的节点内存，队列长度自减1。

清空队列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


// 释放队列中所有节点，但不释放队列本身
void queue_empty(queue *queue)
{   
    int length = queue->length;
    queue_node *current, *next;

    // 注意这里不释放头节点
    current = queue->head->next;
    while (length--)
    {   
        next = current->next;
        free(current);
        current = next;
    }
    
    queue->head->next = NULL;
    queue->head->data = NULL;
    queue->tail = queue->head;
    queue->length = 0;
}

释放队列的所有数据节点，但不释放头节点，所有循环从head->next开始。
因为，head->next被free过，所以再次设置为NULL。
最后，设置队列长度为0，释放完毕。

清除队列

1
2
3
4
5
6
7
8


// 释放队列，包括队列中节点
void queue_release(queue *queue)
{
    queue_empty(queue);
    /* 注意，头节点也要释放 */
    free(queue->head);
    free(queue);
}

在释放队列本身及其节点的时候，我们只需要调用queue_empty函数，再释放头节点和队列本身即可。

测试

 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


int main()
{
    char a = 'a';
    char b = 'b';
    char c = 'c';
    
    queue *queue = queue_create();
    printf("%p\n", queue_pull_data(queue));
    
    queue_push_data(queue, &a);
    queue_push_data(queue, &b);
    queue_push_data(queue, &c);

    while (queue->length)
    {
        printf("%c\n", *(char *)queue_pull_data(queue));
    }
    
    queue_push_data(queue, &c);
    queue_push_data(queue, &c);
    
    /* 释放队列中节点 */
    queue_empty(queue);
    printf("%p\n", queue_pull_data(queue));
    
    /* 释放队列 */
    queue_release(queue);
    return 0;
}

完整代码

 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
87
88
89
90
91


#include <stdio.h>
#include <stdlib.h>
#include "queue.h"

/* 创建队列 */
queue *queue_create()
{
    /* 创建一个队列 */
    queue *queue = (struct queue*)malloc(sizeof(struct queue));
    
    /* 为了方便操作，队列默认创建一个队列节点 */
    queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
    if(queue==NULL || node==NULL) return NULL;

    node->data = NULL;
    node->next = NULL;
    
    /* 初始化队列 */
    queue->head = queue->tail = node;
    queue->length = 0;

    return queue;
}

/* 入队 */
queue *queue_push_data(queue *queue, void *data)
{
    /* 创建一个节点 */
    queue_node *node = (struct queue_node*)malloc(sizeof(struct queue_node));
    if(node==NULL) return NULL;
    node->data = data;

    /* 在队尾插入元素 */
    queue->tail->next = node;
    queue->tail = queue->tail->next;

    queue->length++;
    return queue;
}

/* 出队 */
void *queue_pull_data(queue *queue)
{
    queue_node *current = queue->head->next;
    
    /* 判断队列中是否有数据 */
    if(current==NULL) return NULL;

    void *data = current->data;
    
    queue->head->next = current->next;
    
    /* 判断队列中除头结点外，是否只有一个节点，避免尾指针丢失 */
    if(queue->tail==current) {
        queue->tail = queue->head;
    }

    free(current);
    queue->length--;
    return data;
}

/* 释放队列中所有节点，但不释放队列本身 */
void queue_empty(queue *queue)
{   
    int length = queue->length;
    queue_node *current, *next;

    /* 注意这里不释放头节点 */
    current = queue->head->next;
    while (length--)
    {   
        next = current->next;
        free(current);
        current = next;
    }
    
    queue->head->next = NULL;
    queue->head->data = NULL;
    queue->tail = queue->head;
    queue->length = 0;
}

/* 释放队列，包括队列中节点 */
void queue_release(queue *queue)
{
    queue_empty(queue);
    /* 注意，头节点也要释放 */
    free(queue->head);
    free(queue);
}

字符串

什么是字符串

字符串（String）是由零个或多个字符组成的有限序列，是数据结构中一种基础且重要的数据类型。字符串通常用于表示和处理文本信息。

字符串的操作

字符串的常见操作包括：

赋值 (StrAssign)：将一个字符串常量或变量赋给另一个字符串变量。
求串长 (StrLength)：计算字符串中字符的个数。
串连接 (Concat)：将两个字符串首尾相接，形成一个新的字符串。
求子串 (SubString)：从一个主字符串中取出一部分字符，构成一个新的子字符串。
串比较 (StrCompare)：比较两个字符串的大小。比较规则通常是按字典序进行比较。
定位子串 (Index)：在一个主字符串中查找一个子字符串首次出现的位置。

字符串的表示

字符串主要有两种存储表示方法：顺序存储结构和链式存储结构。

顺序存储结构（顺序串）：用一组地址连续的存储单元来存储字符串中的字符序列。通常使用定长数组或动态分配的数组来实现。
链式存储结构（链串）：用一个链表来表示一个字符串，每个节点可以存储一个或多个字符。

顺序串的节点定义

在C语言中，通常使用一个字符数组来表示顺序串，并用一个整型变量记录其长度。

1
2
3
4


typedef struct {
    char *ch;   // 指向动态分配存储区的指针
    int length; // 字符串的当前长度
} HString;

注意这里的 ch 是一个指针，指向动态分配的内存空间，这样可以根据字符串的实际长度来分配存储空间，更加灵活。

函数清单

下面是用于操作顺序串的常用函数及其作用与复杂度。

函数	作用	算法复杂度
StrAssign	创建一个字符串	O(N)
StrLength	返回字符串的长度	O(1)
Concat	连接两个字符串	O(N+M)
SubString	获取子字符串	O(M)
StrCompare	比较两个字符串	O(min(N, M))
StrFree	释放字符串	O(1)

创建字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


/* 创建一个其值为chars的串T */
int StrAssign(HString *T, const char *chars) {
    if (T->ch) free(T->ch); // 释放旧的空间

    int len = 0;
    const char *c = chars;
    while (*c) {
        len++;
        c++;
    }

    if (!len) {
        T->ch = NULL;
        T->length = 0;
    } else {
        T->ch = (char *)malloc(len * sizeof(char));
        if (!T->ch) return 0; // 分配失败
        for (int i = 0; i < len; i++) {
            T->ch[i] = chars[i];
        }
        T->length = len;
    }
    return 1;
}

求串长

1
2
3
4


/* 返回串S的元素个数 */
int StrLength(HString S) {
    return S.length;
}

串连接

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


/* 用T返回S1和S2连接而成的新串 */
int Concat(HString *T, HString S1, HString S2) {
    if (T->ch) free(T->ch);

    T->length = S1.length + S2.length;
    T->ch = (char *)malloc(T->length * sizeof(char));
    if (!T->ch) return 0; // 分配失败

    for (int i = 0; i < S1.length; i++) {
        T->ch[i] = S1.ch[i];
    }
    for (int i = 0; i < S2.length; i++) {
        T->ch[S1.length + i] = S2.ch[i];
    }
    return 1;
}

求子串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/* 用Sub返回串S的第pos个字符起长度为len的子串 */
int SubString(HString *Sub, HString S, int pos, int len) {
    // 参数校验
    if (pos < 1 || pos > S.length || len < 0 || len > S.length - pos + 1) {
        return 0; // 参数不合法
    }

    if (Sub->ch) free(Sub->ch);

    if (!len) {
        Sub->ch = NULL;
        Sub->length = 0;
    } else {
        Sub->ch = (char *)malloc(len * sizeof(char));
        if (!Sub->ch) return 0; // 分配失败
        for (int i = 0; i < len; i++) {
            Sub->ch[i] = S.ch[pos - 1 + i];
        }
        Sub->length = len;
    }
    return 1;
}

串比较

1
2
3
4
5
6
7
8
9


/* 若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0 */
int StrCompare(HString S, HString T) {
    for (int i = 0; i < S.length && i < T.length; i++) {
        if (S.ch[i] != T.ch[i]) {
            return S.ch[i] - T.ch[i];
        }
    }
    return S.length - T.length;
}

释放字符串

1
2
3
4
5
6
7
8


/* 释放串S所占用的存储空间 */
void StrFree(HString *S) {
    if (S->ch) {
        free(S->ch);
        S->ch = NULL;
    }
    S->length = 0;
}

测试

我们在main函数中对上述函数进行测试。

 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


#include <stdio.h>
#include <stdlib.h>

// ... (将上面的结构体定义和函数实现放在这里)

void PrintString(HString S) {
    for (int i = 0; i < S.length; i++) {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

int main() {
    HString S1, S2, T, Sub;
    S1.ch = NULL; S2.ch = NULL; T.ch = NULL; Sub.ch = NULL;

    // 创建字符串
    StrAssign(&S1, "hello");
    printf("S1: "); PrintString(S1);
    printf("S1 length: %d\n", StrLength(S1));

    StrAssign(&S2, "world");
    printf("S2: "); PrintString(S2);

    // 串连接
    Concat(&T, S1, S2);
    printf("T (S1+S2): "); PrintString(T);

    // 求子串
    SubString(&Sub, T, 6, 5);
    printf("Sub of T from 6 with length 5: "); PrintString(Sub);

    // 串比较
    int cmp = StrCompare(S1, S2);
    printf("Compare S1 and S2: %d\n", cmp);

    // 释放字符串
    StrFree(&S1);
    StrFree(&S2);
    StrFree(&T);
    StrFree(&Sub);

    printf("Strings freed.\n");

    return 0;
}

编译并输出

1
2
3
4
5
6
7
8


# gcc your_string_file.c -o a.out && ./a.out
S1: hello
S1 length: 5
S2: world
T (S1+S2): helloworld
Sub of T from 6 with length 5: world
Compare S1 and S2: -15
Strings freed.

完整代码

  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
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131


//顺序串基本运算的算法
#include <stdio.h>
#define MaxSize 100
typedef struct
{	
	char data[MaxSize];
	int length;			//串长
} SqString;
 
void StrAssign(SqString &s,char cstr[])	//字符串常量赋给串s
{
	int i;
	for (i=0;cstr[i]!='\0';i++)
		s.data[i]=cstr[i];
	s.length=i;
}
 
void DestroyStr(SqString &s)
{  }
 
void StrCopy(SqString &s,SqString t)	//串复制
{
	int i;
	for (i=0;i<t.length;i++)
		s.data[i]=t.data[i];
	s.length=t.length;
}
 
bool StrEqual(SqString s,SqString t)	//判串相等
{
	bool same=true;
	int i;
	if (s.length!=t.length)				//长度不相等时返回0
		same=false;
	else 
		for (i=0;i<s.length;i++)
			if (s.data[i]!=t.data[i])	//有一个对应字符不相同时返回0
			{	same=false;
				break;
			}
	return same;
}
 
int StrLength(SqString s)	//求串长
{
	return s.length;
}
 
SqString Concat(SqString s,SqString t)	//串连接
{
	SqString str;
	int i;
	str.length=s.length+t.length;
	for (i=0;i<s.length;i++)	//将s.data[0..s.length-1]复制到str
		str.data[i]=s.data[i];
	for (i=0;i<t.length;i++)	//将t.data[0..t.length-1]复制到str
		str.data[s.length+i]=t.data[i];
	return str;
}
 
SqString SubStr(SqString s,int i,int j)	//求子串
{
	SqString str;
	int k;
	str.length=0;
	if (i<=0 || i>s.length || j<0 || i+j-1>s.length)
		return str;					//参数不正确时返回空串
	for (k=i-1;k<i+j-1;k++)  		//将s.data[i..i+j]复制到str
		str.data[k-i+1]=s.data[k];
	str.length=j;
	return str;
} 
 
SqString InsStr(SqString s1,int i,SqString s2)	//插入串
{
	int j;
	SqString str;
	str.length=0;
	if (i<=0 || i>s1.length+1)  //参数不正确时返回空串
		return str;
	for (j=0;j<i-1;j++)      		//将s1.data[0..i-2]复制到str
		str.data[j]=s1.data[j];
	for (j=0;j<s2.length;j++)		//将s2.data[0..s2.length-1]复制到str
		str.data[i+j-1]=s2.data[j];
	for (j=i-1;j<s1.length;j++)		//将s1.data[i-1..s1.length-1]复制到str
		str.data[s2.length+j]=s1.data[j];
	str.length=s1.length+s2.length;
	return str;
}
 
SqString DelStr(SqString s,int i,int j)		//串删去
{
	int k;
	SqString str;
	str.length=0;
	if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串
		return str;
	for (k=0;k<i-1;k++)       		//将s.data[0..i-2]复制到str
		str.data[k]=s.data[k];
	for (k=i+j-1;k<s.length;k++)	//将s.data[i+j-1..s.length-1]复制到str
		str.data[k-j]=s.data[k];
	str.length=s.length-j;
	return str;
}
 
SqString RepStr(SqString s,int i,int j,SqString t)	//子串替换
{
	int k;
	SqString str;
	str.length=0;
	if (i<=0 || i>s.length || i+j-1>s.length) //参数不正确时返回空串
		return str;
	for (k=0;k<i-1;k++)				//将s.data[0..i-2]复制到str
		str.data[k]=s.data[k];
	for (k=0;k<t.length;k++)   		//将t.data[0..t.length-1]复制到str
		str.data[i+k-1]=t.data[k];
	for (k=i+j-1;k<s.length;k++)	//将s.data[i+j-1..s.length-1]复制到str
		str.data[t.length+k-j]=s.data[k];
	str.length=s.length-j+t.length;
	return str;
}
 
void DispStr(SqString s)	//输出串s
{
	int i;
	if (s.length>0)
	{	for (i=0;i<s.length;i++)
			printf("%c",s.data[i]);
		printf("\n");
	}
}