时间:2021-05-19
线性表是一种线性结构,它是具有相同类型的n(n≥0)个数据元素组成的有限序列。
一、数组
数组有上界和下界,数组的元素在上下界内是连续的。
存储10,20,30,40,50的数组的示意图如下:
数组的特点:数据是连续的;随机访问速度快。
数组中稍微复杂一点的是多维数组和动态数组。对于C语言而言,多维数组本质上也是通过一维数组实现的。至于动态数组,是指数组的容量能动态增长的数组;对于C语言而言,若要提供动态数组,需要手动实现;而对于C++而言,STL提供了Vector;对于Java而言,Collection集合中提供了ArrayList和Vector。
二、单向链表
单向链表(单链表)是链表的一种,它由节点组成,每个节点都包含下一个节点的指针。
单链表的示意图如下:
表头为空,表头的后继节点是"节点10"(数据为10的节点),"节点10"的后继节点是"节点20"(数据为10的节点),...
单链表删除节点
删除"节点30"
删除之前:"节点20" 的后继节点为"节点30",而"节点30" 的后继节点为"节点40"。
删除之后:"节点20" 的后继节点为"节点40"。
单链表添加节点
在"节点10"与"节点20"之间添加"节点15"
添加之前:"节点10" 的后继节点为"节点20"。
添加之后:"节点10" 的后继节点为"节点15",而"节点15" 的后继节点为"节点20"。
单链表的特点是:节点的链接方向是单向的;相对于数组来说,单链表的的随机访问速度较慢,但是单链表删除/添加数据的效率很高。
三、双向链表
双向链表(双链表)是链表的一种。和单链表一样,双链表也是由节点组成,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
双链表的示意图如下:
表头为空,表头的后继节点为"节点10"(数据为10的节点);"节点10"的后继节点是"节点20"(数据为10的节点),"节点20"的前继节点是"节点10";"节点20"的后继节点是"节点30","节点30"的前继节点是"节点20";...;末尾节点的后继节点是表头。
双链表删除节点
删除"节点30"
删除之前:"节点20"的后继节点为"节点30","节点30" 的前继节点为"节点20"。"节点30"的后继节点为"节点40","节点40" 的前继节点为"节点30"。
删除之后:"节点20"的后继节点为"节点40","节点40" 的前继节点为"节点20"。
双链表添加节点
在"节点10"与"节点20"之间添加"节点15"
添加之前:"节点10"的后继节点为"节点20","节点20" 的前继节点为"节点10"。
添加之后:"节点10"的后继节点为"节点15","节点15" 的前继节点为"节点10"。"节点15"的后继节点为"节点20","节点20" 的前继节点为"节点15"。
下面介绍双链表的实现,分别介绍C/C++/Java三种实现。
1. C实现双链表
实现代码
双向链表头文件(double_link.h)
双向链表实现文件(double_link.c)
#include <stdio.h>#include <malloc.h>/*** C 语言实现的双向链表,能存储任意数据。** @author skywang* @date 2013/11/07*/// 双向链表节点typedef struct tag_node{struct tag_node *prev;struct tag_node *next;void* p;}node;// 表头。注意,表头不存放元素值!!!static node *phead=NULL;// 节点个数。static int count=0;// 新建“节点”。成功,返回节点指针;否则,返回NULL。static node* create_node(void *pval){node *pnode=NULL;pnode = (node *)malloc(sizeof(node));if (!pnode){printf("create node error!\n");return NULL;}// 默认的,pnode的前一节点和后一节点都指向它自身pnode->prev = pnode->next = pnode;// 节点的值为pvalpnode->p = pval;return pnode;}// 新建“双向链表”。成功,返回0;否则,返回-1。int create_dlink(){// 创建表头phead = create_node(NULL);if (!phead)return -1;// 设置“节点个数”为0count = 0;return 0;}// “双向链表是否为空”int dlink_is_empty(){return count == 0;}// 返回“双向链表的大小”int dlink_size() {return count;}// 获取“双向链表中第index位置的节点”static node* get_node(int index){if (index<0 || index>=count){printf("%s failed! index out of bound!\n", __func__);return NULL;}// 正向查找if (index <= (count/2)){int i=0;node *pnode=phead->next;while ((i++) < index)pnode = pnode->next;return pnode;}// 反向查找int j=0;int rindex = count - index - 1;node *rnode=phead->prev;while ((j++) < rindex)rnode = rnode->prev;return rnode;}// 获取“第一个节点”static node* get_first_node(){return get_node(0);}// 获取“最后一个节点”static node* get_last_node(){return get_node(count-1);}// 获取“双向链表中第index位置的元素”。成功,返回节点值;否则,返回-1。void* dlink_get(int index){node *pindex=get_node(index);if (!pindex){printf("%s failed!\n", __func__);return NULL;}return pindex->p;}// 获取“双向链表中第1个元素的值”void* dlink_get_first(){return dlink_get(0);}// 获取“双向链表中最后1个元素的值”void* dlink_get_last(){return dlink_get(count-1);}// 将“pval”插入到index位置。成功,返回0;否则,返回-1。int dlink_insert(int index, void* pval){// 插入表头if (index==0)return dlink_insert_first(pval);// 获取要插入的位置对应的节点node *pindex=get_node(index);if (!pindex)return -1;// 创建“节点”node *pnode=create_node(pval);if (!pnode)return -1;pnode->prev = pindex->prev;pnode->next = pindex;pindex->prev->next = pnode;pindex->prev = pnode;// 节点个数+1count++;return 0;}// 将“pval”插入到表头位置int dlink_insert_first(void *pval){node *pnode=create_node(pval);if (!pnode)return -1;pnode->prev = phead;pnode->next = phead->next;phead->next->prev = pnode;phead->next = pnode;count++;return 0;}// 将“pval”插入到末尾位置int dlink_append_last(void *pval){node *pnode=create_node(pval);if (!pnode)return -1;pnode->next = phead;pnode->prev = phead->prev;phead->prev->next = pnode;phead->prev = pnode;count++;return 0;}// 删除“双向链表中index位置的节点”。成功,返回0;否则,返回-1。int dlink_delete(int index){node *pindex=get_node(index);if (!pindex){printf("%s failed! the index in out of bound!\n", __func__);return -1;}pindex->next->prev = pindex->prev;pindex->prev->next = pindex->next;free(pindex);count--;return 0;}// 删除第一个节点int dlink_delete_first(){return dlink_delete(0);}// 删除组后一个节点int dlink_delete_last(){return dlink_delete(count-1);}// 撤销“双向链表”。成功,返回0;否则,返回-1。int destroy_dlink(){if (!phead){printf("%s failed! dlink is null!\n", __func__);return -1;}node *pnode=phead->next;node *ptmp=NULL;while(pnode != phead){ptmp = pnode;pnode = pnode->next;free(ptmp);}free(phead);phead = NULL;count = 0;return 0;}双向链表测试程序(dlink_test.c)
#include <stdio.h>#include "double_link.h"/*** C 语言实现的双向链表的测试程序。** (01) int_test()* 演示向双向链表操作“int数据”。* (02) string_test()* 演示向双向链表操作“字符串数据”。* (03) object_test()* 演示向双向链表操作“对象”。** @author skywang* @date 2013/11/07*/// 双向链表操作int数据void int_test(){int iarr[4] = {10, 20, 30, 40};printf("\n----%s----\n", __func__);create_dlink(); // 创建双向链表dlink_insert(0, &iarr[0]); // 向双向链表的表头插入数据dlink_insert(0, &iarr[1]); // 向双向链表的表头插入数据dlink_insert(0, &iarr[2]); // 向双向链表的表头插入数据printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 双向链表是否为空printf("dlink_size()=%d\n", dlink_size()); // 双向链表的大小// 打印双向链表中的全部数据int i;int *p;int sz = dlink_size();for (i=0; i<sz; i++){p = (int *)dlink_get(i);printf("dlink_get(%d)=%d\n", i, *p);}destroy_dlink();}void string_test(){char* sarr[4] = {"ten", "twenty", "thirty", "forty"};printf("\n----%s----\n", __func__);create_dlink(); // 创建双向链表dlink_insert(0, sarr[0]); // 向双向链表的表头插入数据dlink_insert(0, sarr[1]); // 向双向链表的表头插入数据dlink_insert(0, sarr[2]); // 向双向链表的表头插入数据printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 双向链表是否为空printf("dlink_size()=%d\n", dlink_size()); // 双向链表的大小// 打印双向链表中的全部数据int i;char *p;int sz = dlink_size();for (i=0; i<sz; i++){p = (char *)dlink_get(i);printf("dlink_get(%d)=%s\n", i, p);}destroy_dlink();}typedef struct tag_stu{int id;char name[20];}stu;static stu arr_stu[] ={{10, "sky"},{20, "jody"},{30, "vic"},{40, "dan"},};#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )void object_test(){printf("\n----%s----\n", __func__);create_dlink(); // 创建双向链表dlink_insert(0, &arr_stu[0]); // 向双向链表的表头插入数据dlink_insert(0, &arr_stu[1]); // 向双向链表的表头插入数据dlink_insert(0, &arr_stu[2]); // 向双向链表的表头插入数据printf("dlink_is_empty()=%d\n", dlink_is_empty()); // 双向链表是否为空printf("dlink_size()=%d\n", dlink_size()); // 双向链表的大小// 打印双向链表中的全部数据int i;int sz = dlink_size();stu *p;for (i=0; i<sz; i++){p = (stu *)dlink_get(i);printf("dlink_get(%d)=[%d, %s]\n", i, p->id, p->name);}destroy_dlink();}int main(){int_test(); // 演示向双向链表操作“int数据”。string_test(); // 演示向双向链表操作“字符串数据”。object_test(); // 演示向双向链表操作“对象”。return 0;}运行结果
----int_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=30dlink_get(1)=20dlink_get(2)=10----string_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=thirtydlink_get(1)=twentydlink_get(2)=ten----object_test----dlink_is_empty()=0dlink_size()=3dlink_get(0)=[30, vic]dlink_get(1)=[20, jody]dlink_get(2)=[10, sky]2. C++实现双链表
实现代码
双向链表文件(DoubleLink.h)
双向链表测试文件(DlinkTest.cpp)
#include <iostream>#include "DoubleLink.h"using namespace std;// 双向链表操作int数据void int_test(){int iarr[4] = {10, 20, 30, 40};cout << "\n----int_test----" << endl;// 创建双向链表DoubleLink<int>* pdlink = new DoubleLink<int>();pdlink->insert(0, 20); // 将 20 插入到第一个位置pdlink->append_last(10); // 将 10 追加到链表末尾pdlink->insert_first(30); // 将 30 插入到第一个位置// 双向链表是否为空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 双向链表的大小cout << "size()=" << pdlink->size() <<endl;// 打印双向链表中的全部数据int sz = pdlink->size();for (int i=0; i<sz; i++)cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;}void string_test(){string sarr[4] = {"ten", "twenty", "thirty", "forty"};cout << "\n----string_test----" << endl;// 创建双向链表DoubleLink<string>* pdlink = new DoubleLink<string>();pdlink->insert(0, sarr[1]); // 将 sarr中第2个元素 插入到第一个位置pdlink->append_last(sarr[0]); // 将 sarr中第1个元素 追加到链表末尾pdlink->insert_first(sarr[2]); // 将 sarr中第3个元素 插入到第一个位置// 双向链表是否为空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 双向链表的大小cout << "size()=" << pdlink->size() <<endl;// 打印双向链表中的全部数据int sz = pdlink->size();for (int i=0; i<sz; i++)cout << "pdlink("<<i<<")=" << pdlink->get(i) <<endl;}struct stu{int id;char name[20];};static stu arr_stu[] ={{10, "sky"},{20, "jody"},{30, "vic"},{40, "dan"},};#define ARR_STU_SIZE ( (sizeof(arr_stu)) / (sizeof(arr_stu[0])) )void object_test(){cout << "\n----object_test----" << endl;// 创建双向链表DoubleLink<stu>* pdlink = new DoubleLink<stu>();pdlink->insert(0, arr_stu[1]); // 将 arr_stu中第2个元素 插入到第一个位置pdlink->append_last(arr_stu[0]); // 将 arr_stu中第1个元素 追加到链表末尾pdlink->insert_first(arr_stu[2]); // 将 arr_stu中第3个元素 插入到第一个位置// 双向链表是否为空cout << "is_empty()=" << pdlink->is_empty() <<endl;// 双向链表的大小cout << "size()=" << pdlink->size() <<endl;// 打印双向链表中的全部数据int sz = pdlink->size();struct stu p;for (int i=0; i<sz; i++){p = pdlink->get(i);cout << "pdlink("<<i<<")=[" << p.id << ", " << p.name <<"]" <<endl;}}int main(){int_test(); // 演示向双向链表操作“int数据”。string_test(); // 演示向双向链表操作“字符串数据”。object_test(); // 演示向双向链表操作“对象”。return 0;}示例说明
在上面的示例中,我将双向链表的"声明"和"实现"都放在头文件中。而编程规范告诫我们:将类的声明和实现分离,在头文件(.h文件或.hpp)中尽量只包含声明,而在实现文件(.cpp文件)中负责实现!
那么为什么要这么做呢?这是因为,在双向链表的实现中,采用了模板;而C++编译器不支持对模板的分离式编译!简单点说,如果在DoubleLink.h中声明,而在DoubleLink.cpp中进行实现的话;当我们在其他类中创建DoubleLink的对象时,会编译出错。具体原因,可以参考"为什么C++编译器不能支持对模板的分离式编译"。
运行结果
----int_test----is_empty()=0size()=3pdlink(0)=30pdlink(1)=20pdlink(2)=10----string_test----is_empty()=0size()=3pdlink(0)=thirtypdlink(1)=twentypdlink(2)=ten----object_test----is_empty()=0size()=3pdlink(0)=[30, vic]pdlink(1)=[20, jody]pdlink(2)=[10, sky]3. Java实现双链表
实现代码
双链表类(DoubleLink.java)
测试程序(DlinkTest.java)
运行结果
----int_test----isEmpty()=falsesize()=3dlink(0)=30dlink(1)=20dlink(2)=10----string_test----isEmpty()=falsesize()=3dlink(0)=thirtydlink(1)=twentydlink(2)=ten----object_test----isEmpty()=falsesize()=3dlink(0)=[30, vic]dlink(1)=[20, jody]dlink(2)=[10, sky]以上就是本文的全部内容,希望大家能够理解,对大家有所帮助。
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
栈(Stack)是一种特殊的线性表,因为它只能在线性表的一端进行插入或删除元素(即进栈和出栈)SplStack就是继承双链表(SplDoublyLinkedLi
模拟单链表线性表:线性表(亦作顺序表)是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,
线性表中有链表和顺序表两类,顺序表所占的存储空间必须连续,链表没有这个要求,连续指的是存储空间的连续,顺序存储结构中,线性表中每一个数据元素在计算机存储空间中的
本文实例讲述了C#实现单链表(线性表)的方法。分享给大家供大家参考,具体如下:顺序表由连续内存构成,链表则不同。顺序表的优势在于查找,链表的优势在于插入元素等操
C++数据结构线性表-数组实现线性表的数组实现,实现几个核心的功能,语言是C++,如果有更好的想法和意见,欢迎留言~~~/*Author:Moyiii*线性表的