一、线性表及其分类
(定义部分参考自《大话数据结构》及维基百科)
线性表(List / Linear List):零个或多个数据元素的有限序列。
线性表的基本操作(涉及算法中方法实现):
线性表初始化;
求线性表长度;
获取元素操作;
查找元素操作;
插入元素操作;
删除元素操作;
其他:判断线性表是否为空;清空线性表;
线性表可以存储结构特点分为两类:
1.顺序表 Sequence List(线性表的顺序存储结构):用一段地址连续的存储单元一次存储线性表的数据元素。
根据存储单元的内存开辟方式可以分为(根据不同的需求顺序表可以按照以下不同的方式实现):
1.1静态顺序表:保存数据元素的内存是在程序编译时就开辟的,空间大小是静态的。(针对C语言:可由数组实现。)
1.2动态顺序表:保存数据元素的内存是在程序运行时才开辟的,空间大小是动态的。(针对C语言:可由标准函数malloc和free动态实现。)
2.链表 Linked List(线性表的链式存储结构):由n个结点链结成的链表。
根据结点(node)的内存开辟方式可以分为(根据不同的需求链表可以按照以下不同的方式实现):
2.1.1静态链表:保存结点的内存是在程序编译时就开辟的,空间大小是静态的。(针对C语言:可由数组实现。)
2.1.2动态链表:保存结点的内存是在程序运行时才开辟的,空间大小是动态的。(针对C语言:可由标准函数malloc和free动态实现。)
根据结点(node)中存储逻辑关系的数据特征分类,常见有下面三种(根据不同的需求链表可以按照以下不同的方式实现):
(单链接或双链接,已排序或未排序,循环或非循环)
2.2.1单链表(singly linked list) :每个对象含关键字和后继指针
2.2.2双向链表(doubly linked list):每个对象含关键字,前驱指针和后继指针
2.2.3循环链表(circular linked list)(也可再分为单循环链表和双循环链表):首尾对象含有指针指向,形成圆环。
(上述更详细分类和术语可参考: http://zh.wikipedia.org/wiki/线性表http://en.wikipedia.org/wiki/Linked_list)
分析:对于线性表这一数据结构的分类,不同的作者有不同的分类方法,这里我采用我认为相对比较科学全面的分类方式,也尽量避免这些术语乱用。这些分类方式首先是脱离具体的程序设计语言去定义的,接着算法再利用特定的程序设计语言进行实现。我这边主要用C语言实现这些链表的数据结构和方法,供以后使用。
顺序表和链表优缺点比较:
顺序表:
优点: 随机存取时间复杂度为O(1);无需为表中元素之间的逻辑关系额外增加存储空间
缺点: 插入、删除操作需要移动大量的元素,时间复杂度为O(n);表的长度难以确定
链表:
优点: 插入、删除节点时不移动数据, 效率高,时间复杂度为O(1)
缺点: 存取时要遍历,效率低,时间复杂度为O(n)
因此,综上所诉,顺序存储结构适合频繁存取、查找,很少插入、删除的情况;链式存储适合频繁插入、删除,很少存取的情况;
二、线性表C实现
目标:
1.实现大多数类型的线性表数据结构,用于其他算法调用,以后需要使用现在未实现的线性表时在逐步加入;
2.算法具有通用,高效,简洁,注释充分四个特点,便于进行其他程序设计语言移植;
特点:
1.所有线性表的文件含有共用的文件头(list.h)(主要是通用的宏定义和标准函数库头文件包含,避免重复定义,方便维护);
2.由于不同类型的线性表使用的结构体名和函数名可能一致,各自含有相应的头文件(*.h)和实现文件(*.c),C语言不具有函数重载功能,因此只能独立使用这些线性表的数据类型(优点是避免因类型过多导致结构体名和函数名命名较乱,缺点是不能够在同一个文件中同时使用);
3.实现各个类型的线性表的基本操作。
注意:
1.实现线性表基本操作时函数的返回值值得考究,这里原则上尽量减少不必要返回值。
2.实现线性表基本操作时函数的返回状态可以用枚举类型实现(未实现)。
3.断言语句(assert)的参数需要认真考虑。
汇总:
头文件(list.h):
/** * @file list.h * @brief list header that has macro definition used by many types of list. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #ifndef __LIST_H__ #define __LIST_H__ #include <stdio.h> #include <stdlib.h> #include <string.h> // #define NDEBUG #include <assert.h> /// list return state #ifndef OK #define OK 1 #endif #ifndef ERROR #define ERROR 0 #endif #ifndef TRUE #define TRUE 1 #endif #ifndef FALSE #define FALSE 0 #endif /// list array maz length used by static sequence list, can be modified #define LIST_MAXSIZE 1000 /// list initialize size used by dynamic sequence list, can be modified #define LIST_INIT_SIZE 1000 /// list memory increated size used by dynamic sequence list, can be modified #define LIST_INCREMENT 2 /// data type, can be modified typedef int Status; ///< status data type typedef int ElementType; ///< element data type typedef int CommonType; ///< common data type #endif // __LIST_H__
静态顺序表(sequence_list_satic.h sequence_list_static.c):
/** * @file sequence_list_static.h * @brief static sequence list header. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #ifndef __SEQUENCE_LIST_STATIC_H__ #define __SEQUENCE_LIST_STATIC_H__ #include "list.h" /// static sequence list structure typedef struct { ElementType data[LIST_MAXSIZE]; ///< list elements CommonType length; ///< list length }SqList; /// static sequence list method /// initialize list void InitList(SqList* L); /// detect if list is empty Status ListEmpty(SqList* L); /// clear list void ClearList(SqList* L); /// get list length CommonType ListLength(SqList* L); /// get element from the list Status GetElem(SqList* L, CommonType index, ElementType* e); /// locate element of the index CommonType LocateElem(SqList* L, ElementType e); /// insert element to the list Status ListInsert(SqList* L, CommonType index, ElementType e); /// delete element from the list Status ListDelete(SqList* L, CommonType index, ElementType* e); #endif // __SEQUENCE_LIST_STATIC_H__
/** * @file sequence_list_static.c * @brief static sequence list method implements. * The methods use <assert.h> to help debug the program. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #include "sequence_list_static.h" /** * @brief initialize the list. * * @param[in,out] L list struct pointer * */ void InitList(SqList* L) { assert(L != NULL); /// initialize length only, ignore the list data L->length = 0; } /** * @brief detect if the list is empty. * * @param[in] L list struct pointer * * @return return TRUE if empty, else return FALSE */ Status ListEmpty(SqList* L) { assert(L != NULL && L->length >= 0); /// always have length >= 0 if (L->length) return FALSE; else return TRUE; } /** * @brief clear the list. * * @param[in,out] L list struct pointer * */ void ClearList(SqList* L) { assert(L != NULL); /// set length only, ignore the list data L->length = 0; } /** * @brief get list length. * * @param[in] L list struct pointer * * @return list length */ CommonType ListLength(SqList* L) { assert(L != NULL && L->length >= 0); return L->length; } /** * @brief get element from the list. * * @param[in] L list struct pointer * @param[in] index the index from the list * @param[out] e the element by index * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status GetElem(SqList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL && L->length >= 0); /// index should be in reasonable range if (index > L->length || index < 1) return ERROR; /// get element from list *e = L->data[index - 1]; return OK; } /** * @brief locate element by index. * * @param[in] L list struct pointer * @param[in] e the element to be located * * @warning index begin from 1 * * @return return the index of the element if success, else return 0 */ CommonType LocateElem(SqList* L, ElementType e) { assert(L != NULL && L->length >= 0); CommonType i; for (i = 1; i <= L->length; i++) if (L->data[i - 1] == e) /// get index of the first found element from list return i; return 0; } /** * @brief insert element to the list at given index. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[in] e the element to be insert * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status ListInsert(SqList* L, CommonType index, ElementType e) { assert(L != NULL && L->length >= 0); /// list length and index should be in reasonable range if (L->length == LIST_MAXSIZE || index > (L->length + 1) || index < 1) return ERROR; /// move the element after the index position to next position CommonType i; for (i = L->length - 1; i >= index - 1; i--) L->data[i + 1] = L->data[i]; /// increase list length L->length++; /// insert element L->data[index - 1] = e; return OK; } /** * @brief delete element from the list. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[out] e the element to be deleted * * @warning index begin from 1 * * @return return OK and set e if success, else return ERROR */ Status ListDelete(SqList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL && L->length >= 0); /// index should be in reasonable range if (index > L->length || index < 1) return ERROR; /// get deleted element *e = L->data[index - 1]; /// move the element after the index position to previous position CommonType i; for (i = index; i < L->length; i++) L->data[i - 1] = L->data[i]; /// decrease list length L->length--; return OK; }
动态顺序表(sqlist_dynamic.h sqlist_dynamic.c):
/** * @file sequence_list_dynamic.h * @brief dynamic sequence list header. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #ifndef __SEQUENCE_LIST_DYNAMIC_H__ #define __SEQUENCE_LIST_DYNAMIC_H__ #include "list.h" /// dynamic sequence list structure typedef struct { ElementType* data; ///< list elements CommonType length; ///< list length CommonType listsize; ///< list size mallocated }SqList; /// dynamic sequence list method /// initialize list void InitList(SqList* L); /// destroy list void DestroyList(SqList* L); /// detect if list is empty Status ListEmpty(SqList* L); /// clear list void ClearList(SqList* L); /// get list length CommonType ListLength(SqList* L); /// get element from the list Status GetElem(SqList* L, CommonType index, ElementType* e); /// locate element of the index CommonType LocateElem(SqList* L, ElementType e); /// insert element to the list Status ListInsert(SqList* L, CommonType index, ElementType e); /// delete element from the list Status ListDelete(SqList* L, CommonType index, ElementType* e); #endif // __SEQUENCE_LIST_DYNAMIC_H__
/** * @file sequence_list_dynamic.c * @brief dynamic sequence list method implements. * The methods use <assert.h> to help debug the program. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #include "sequence_list_dynamic.h" /** * @brief initialize the list. * * @param[in,out] L list struct pointer * */ void InitList(SqList* L) { assert(L != NULL); /// initialize length list size and malloc memory if ((L->data = malloc(LIST_INIT_SIZE * sizeof(ElementType))) == NULL) { assert(0); exit(EXIT_FAILURE); } L->length = 0; L->listsize = LIST_INIT_SIZE; } /** * @brief destroy the list. * * @param[in,out] L list struct pointer * */ void DestroyList(SqList* L) { assert(L != NULL && L->length >= 0 && L->length <= L->listsize); /// clear length list size and free memory free(L->data); L->data = NULL; L->length = 0; L->listsize = 0; } /** * @brief detect if the list is empty. * * @param[in] L list struct pointer * * @return return TRUE if empty, else return FALSE */ Status ListEmpty(SqList* L) { assert(L != NULL && L->length >= 0 && L->length <= L->listsize); /// always have length >= 0 if (L->length) return FALSE; else return TRUE; } /** * @brief clear the list. * * @param[in,out] L list struct pointer * */ void ClearList(SqList* L) { assert(L != NULL); /// set length only, ignore the list data L->length = 0; } /** * @brief get list length. * * @param[in] L list struct pointer * * @return list length */ CommonType ListLength(SqList* L) { assert(L != NULL && L->length >= 0 && L->length <= L->listsize); return L->length; } /** * @brief get element from the list. * * @param[in] L list struct pointer * @param[in] index the index from the list * @param[out] e the element by index * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status GetElem(SqList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL && L->length >= 0 && L->length <= L->listsize); /// index should be in reasonable range if (index > L->length || index < 1) return ERROR; /// get element from list *e = L->data[index - 1]; return OK; } /** * @brief locate element by index. * * @param[in] L list struct pointer * @param[in] e the element to be located * * @warning index begin from 1 * * @return return the index of the element if success, else return 0 */ CommonType LocateElem(SqList* L, ElementType e) { assert(L != NULL && L->length >= 0 && L->length <= L->listsize); CommonType i; for (i = 1; i <= L->length; i++) if (L->data[i - 1] == e) /// get index of the first found element from list return i; return 0; } /** * @brief insert element to the list at given index. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[in] e the element to be insert * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status ListInsert(SqList* L, CommonType index, ElementType e) { assert(L != NULL && L->length >= 0 && L->length <= L->listsize); /// list length and index should be in reasonable range if (index > (L->length + 1) || index < 1) return ERROR; /// malloc memory if not enough if (L->length == L->listsize) { ElementType* newbase = (ElementType*)realloc( L->data, (L->listsize + LIST_INCREMENT) * sizeof(ElementType)); if (newbase == NULL) { assert(0); exit(EXIT_FAILURE); } L->data = newbase; L->listsize += LIST_INCREMENT; } /// move the element after the index position to next position CommonType i; for (i = L->length - 1; i >= index - 1; i--) L->data[i + 1] = L->data[i]; /// increase list length L->length++; /// insert element L->data[index - 1] = e; return OK; } /** * @brief delete element from the list. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[out] e the element to be deleted * * @warning index begin from 1 * * @return return OK and set e if success, else return ERROR */ Status ListDelete(SqList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL && L->length >= 0 && L->length <= L->listsize); /// index should be in reasonable range if (index > L->length || index < 1) return ERROR; /// get deleted element *e = L->data[index - 1]; /// move the element after the index position to previous position CommonType i; for (i = index; i < L->length; i++) L->data[i - 1] = L->data[i]; /// decrease list length L->length--; return OK; }
动态单链表(linked_list_dynamic.h
linked_list_dynamic.c):
/** * @file linked_list_dynamic.h * @brief dynamic linked list header. * the data was not in the first node. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #ifndef __LINKED_LIST_DYNAMIC_H__ #define __LINKED_LIST_DYNAMIC_H__ #include "list.h" /// node structure typedef struct Node { ElementType data; ///< data in the node struct Node* next; ///< pointer to next node }Node; /// define single linked list typedef Node* LinkList; /// dynamic linked list method /// initialize list void InitList(LinkList* L, CommonType size); /// destroy list void DestroyList(LinkList* L); /// detect if list is empty Status ListEmpty(LinkList* L); /// clear list void ClearList(LinkList* L); /// get list length CommonType ListLength(LinkList* L); /// get element from the list Status GetElem(LinkList* L, CommonType index, ElementType* e); /// locate element of the index CommonType LocateElem(LinkList* L, ElementType e); /// insert element to the list Status ListInsert(LinkList* L, CommonType index, ElementType e); /// delete element from the list Status ListDelete(LinkList* L, CommonType index, ElementType* e); #endif // __LINKED_LIST_DYNAMIC_H__
/** * @file linked_list_dynamic.c * @brief dynamic linked list method implements. * The methods use <assert.h> to help debug the program. * @author chenxilinsidney * @version 1.0 * @date 2015-01-19 */ #include "linked_list_dynamic.h" /** * @brief initialize the list.insert node in the head of list. * The method can be alse modified to insert node in the tail * of list. * * @param[in,out] L list struct pointer * @param[in] size list data size * */ void InitList(LinkList* L, CommonType size) { assert(size >= 0); /// initialize first node if ((*L = (LinkList)malloc(sizeof(Node))) == NULL) { assert(0); exit(EXIT_FAILURE); } (*L)->next = NULL; /// initialize other node LinkList new_node; while (size--) { /// add new node to the head of the list if ((new_node = (LinkList)malloc(sizeof(Node))) == NULL) { assert(0); exit(EXIT_FAILURE); } new_node->data = 0; new_node->next = (*L)->next; (*L)->next = new_node; } } /** * @brief destroy the list. * * @param[in,out] L list struct pointer * */ void DestroyList(LinkList* L) { assert(L != NULL); /// pointer to the first node LinkList q, p = (*L); /// free memory while (p) { q = p->next; free(p); p = q; } /// set first node to null *L = NULL; } /** * @brief detect if the list is empty. * * @param[in] L list struct pointer * * @return return TRUE if empty, else return FALSE */ Status ListEmpty(LinkList* L) { assert(L != NULL); /// check the first data node if ((*L)->next) return FALSE; else return TRUE; } /** * @brief clear the list. * * @param[in,out] L list struct pointer * */ void ClearList(LinkList* L) { assert(L != NULL); /// pointer to the first data node LinkList q, p = (*L)->next; /// free memory while (p) { q = p->next; free(p); p = q; } /// set first data node to NULL (*L)->next = NULL; } /** * @brief get list length. * * @param[in] L list struct pointer * * @return list length */ CommonType ListLength(LinkList* L) { assert(L != NULL); /// pointer to the first data node CommonType length = 0; LinkList p = (*L)->next; /// pointer to next node while (p) { p = p->next; length++; } return length; } /** * @brief get element from the list. * * @param[in] L list struct pointer * @param[in] index the index from the list * @param[out] e the element by index * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status GetElem(LinkList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL); /// pointer to the first data node CommonType j = 1; LinkList p = (*L)->next; /// pointer to node of index while (p && j < index) { /// pointer to next node p = p->next; j++; } /// can not get the element by index if(!p || j > index) return ERROR; /// get element from list *e = p->data; return OK; } /** * @brief locate element by index. * * @param[in] L list struct pointer * @param[in] e the element to be located * * @warning index begin from 1 * * @return return the index of the element if success, else return 0 */ CommonType LocateElem(LinkList* L, ElementType e) { assert(L != NULL); /// pointer to the first data node CommonType index = 0; LinkList p = (*L)->next; /// pointer to next node while (p) { index++; /// get index of the first found element from list if(p->data == e) return index; p = p->next; } return 0; } /** * @brief insert element to the list at given index. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[in] e the element to be insert * * @warning index begin from 1 * * @return return OK if success, else return ERROR */ Status ListInsert(LinkList* L, CommonType index, ElementType e) { assert(L != NULL); CommonType j = 1; /// pointer to the first node LinkList s, p = *L; /// pointer to node of index while (p->next && j < index) { p = p->next; j++; } /// can not get the location by index if(!p->next || j > index) return ERROR; /// malloc memory if ((s = (LinkList)malloc(sizeof(Node))) == NULL) { assert(0); exit(EXIT_FAILURE); } /// insert element s->data = e; s->next = p->next; p->next = s; return OK; } /** * @brief delete element from the list. * * @param[in,out] L list struct pointer * @param[in] index the index from the list * @param[out] e the element to be deleted * * @warning index begin from 1 * * @return return OK and set e if success, else return ERROR */ Status ListDelete(LinkList* L, CommonType index, ElementType* e) { assert(L != NULL && e != NULL); CommonType j = 1; /// pointer to the first node LinkList q, p = *L; /// pointer to node of index while (p->next && j < index) { p = p->next; j++; } /// can not get the location by index if (!(p->next) || j > index) return ERROR; /// get deleted element q = p->next; p->next = q->next; *e = q->data; free(q); return OK; }
单链表一些知识补充:
头结点:链表的第一个有效结点前面的结点,头结点并不存放有效数据,也就是数据域为空,加头结点的主要目的是为了方便链表的操作。
首节点:链表的第一个有效结点,结点包含数据域和指针域。
尾结点:尾结点的指针域为空。
头指针:指向头结点的指针变量,它存放了头结点的地址(在这里注意一下,指针变量存放的是地址,也就是说头指针存放的是头结点的地址,一般通过头指针对链表进行操作)。