【数据结构超详细2万字——左牵链表，右擎顺序表】

💖 技术宅，拯救世界！

🎁作者：@excmber
🎁专栏：《数据结构从入门到入土》
🎁 对读者的话：相信奇迹的人本身和奇迹一样伟大

---

🌹感谢大家的点赞 和关注 🌹，如果有需要可以看我主页专栏哟💖

---

🚢1.前言

学过数据结构的友友应该都知道线性表可以说是数据结构这一部分的核心了，因为后面学的栈，队列，字符串，数组等都以这个作为基础。所以说要想学好数据结构，学好学精线性表是必须的，注意本片博客运用的是部分c++语法结构，所以友友们注意文件后缀名是cpp哦。
话不多说我们这就开始。😜

---

---

🚢2.顺序表

---

🚗2.1顺序表简介

---

🐱‍👓首先我们看看顺序表的存储

和我们前一篇文章讲得一样顺序表的存储和其在内存中的相对位置有关详情请见数据结构——绪论及其有关说明。

🥇 先来一道超简单的例题

只需要98+3*5=113就可以了哦，相信这难不到各位大佬🧐

---

💕咱就是说以手机联系人为例来展开我们的顺序表💕

---

🚗2.2顺序表的定义函数

---

🐱‍👓既然前面都说到了相对位置，那当然少不了我们可爱的数组咯

🐳话不多说，直接上代码

//头文件书写
#include
#include
#include
//一组宏定义
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
//顺序表结构体定义--这里我们以手机联系人为例
typedef int Status;
typedef int ElemType;
typedef struct {char name[];char tel[];//手机联系人姓名与电话
}ElemType;//友友们可以根据自己需要来定义
typedef struct {ElemType elem[LIST_INIT_SIZE];int length;
}SqList;

可以看出定义结构体方式为数组，即分配了一个静态的空间存放数据元素，实际上这种方法很少应用到实际app中。
那么有什么方法可以分配一个动态存储空间呢———相信大家一定会想到指针。

---

🐳 直接上代码

//动态分配空间
typedef struct {ElemType *elem;//指针分配int length;int listsize;
}SqList;

---

这种动态分配方式就很好解决了分配空间的问题，系统会根据用户的需要分配空间👏

---

🚗2.3顺序表的初始化

---

🐱‍👓下面我们来康康顺序表的初始化。

---

🐳咱就是说先来康康代码。

Status initList_Sq(SqList &L)
{L.elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);//为顺序表分配一个LIST_INIT_SIZE大小的空间// L.elem = new ElemType[LIST_INIT_SIZE];if (L.elem == NULL) exit(OVERFLOW);//分配失败，程序退出L.length = 0;//记录表此时长度L.listsize = LIST_INIT_SIZE;//记录表最大表长return OK;
}

---

看到这里小伙伴们可能会有些疑惑，malloc后面这一大坨是什么鬼？
🧐malloc函数其实是一个向系统申请空间的函数，后面的即为申请一片大小为 LIST_INIT_SIZE的空间。同时我们也可以利用c++函数中的new函数为我们的线性表分配空间，头函数我在上一篇文章已经说过了，需要的友友请移步数据结构——绪论及其有关说明👏。

---

🚗2.3顺序表的查找

---

🐱‍👓现在我们来看看顺序表最基本的查找操作。

---

🐳老规矩先上代码

Status Locate(SqList &L, char person[])
{int i;for (i = 0; i < L.length; i++)if (strcmp(L.elem[i].name, person) == 0) break;if (i < L.length)printf("%s的电话号码是%d\n", person, L.elem[i].tel);elseprintf("查无此人!\n");return OK;
}

---

此处我是根据手机联系人的名字来查找其电话号码，先遍历整个线性表并通过strcmp函数来查找和关键字序列相同的。

---

🚩查找操作时间复杂度分析：老规矩根据我门上一节讲的知识，只需要找算法最深层嵌套循环的语句频度即可以算出其时间复杂度，显然得出其时间复杂度为O（n）。详细请看数据结构——绪论及其语法分析。

---

🚗2.4顺序表的插入

---

🐱‍👓来了，来了，激动人心的插入操作。

---

🐳先来点小菜。

Status Listinsert_Sq(SqList &L, int i, ElemType e)//输入插入位置及插入元素
{int j;for (j = L.length; j >= i; j--)L.elem[j] = L.elem[j - 1];L.elem[i - 1] = e;L.length++;return OK;
}

---

这里我们通过输入插入位置与插入内容实现了新元素的插入，同时我们通过向后移动的方法来实现插入👏。如果向前移动，元素将会被覆盖，从而让整个线性表错位。记得最后表长一定要加一哦。

---

🚩插入操作时间复杂度分析：O（n）。

---

🚗2.5顺序表的删除

---

🐱‍👓接下来是最后一个删除操作

---

🐳哎嘿，它来了，它来了，它带着代码来了。

Status ListDelete_Sq(SqList &L, char person[])
{int i, j;for (i = 0; i < L.length; i++)if (strcmp(L.elem[i].name, person) == 0) break;for (j = i; j < L.length; j++)L.elem[j] = L.elem[j+1];L.length--;return OK;
}

---

这里我们依然是根据要删除的名字进行删除（方法基本和前面的strcmp基本一致），只不过删除的方式是通过后面的元素逐步覆盖前面的元素👏。

---

🚩删除操作时间复杂度分析：O（n）。

---

🐱‍👓到这我们的顺序表基本操作就结束了，本片博客的第三章会对顺序表进行具体的应用哦💕

---

🚢3.链表

---

🐱‍👓接下来迎来我们的重头戏——链表。

---

🚗3.1链表简介

---

🐱‍👓上一章中我们提到过链表中数据元素是与其物理位置无关的。主要用指针来表明其逻辑关系。

---

🚗3.2单链表的定义函数

---

🐳老规矩，先来一段扑鼻香的代码

//宏定义和前面一样，此处就不再写出来
typedef int Status;
typedef int ElemType;
tyepedef struct LNode{ElemType data;//数据域struct LNode* next;//指针域
}Lnode;

---

🐱‍👓链表的定义就主要有指针域和数据域这两个。

---

🚗3.3链表的初始化

---

🐳老规矩，先上代码。

Status Create_LinkList(LinkList &L)
{L = (LinkList)malloc(sizeof(LNode));L->next = NULL;return OK;
}

---

🐱‍👓链表的初始化无非就是向系统申请一片内存空间(此处需注意内存空间必须是之前定义的LNode地址)，然后再用指针指向他并将其指针域置空。

---

🚗3.4链表的查找

---

🐳先来康康一段代码。

Status Seek_LinkList(LinkList &L, char person[])
{LinkList p;p = L->next;while (strcmp(p->data, person) == 0 && p != NULL)p = p->next;if (p != NULL)return OK;elsereturn NULL;
}

---

🐱‍👓这里我是根据查找人的姓名并通过strcmp函数实现了data域与查找人姓名的匹配。注意此处data域需要自己定义一个name[] 数组。在本片博客的第四章会有具体的实例给大家参考。

---

🚗3.5链表的取值

---

🐳先来康康一段代码。

Status GetElem_LinkList(LinkList &L, int i,ElemType e)
{LinkList p;int j = 1, k = 0;p = L->next;while (j < i && p)p = p->next; j++;if (j > i || !p)return ERROR;e = p->data;return OK;
}

---

🐱‍👓这里我们根据查找的位置i，通过遍历整个链表从而得到第i个元素的值，while函数结束的标志就是刚好遍历到第i-1个值之后，p指针正好指向那个元素，之后再其data域存储在e中。

---

🚗3.6链表的建立

---

🚓3.6.1头插法建立链表

---

🐳接下来迎来我们的重头戏——头插法。

Status insertfront_LinkList(LinkList &L, int n)
{LinkList p;int i;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;for (i = n; i > 0; i--){p = (LinkList)malloc(sizeof(LNode));scanf("%d", &p->data);p->next = L->next;L->next = p;}return OK;
}

---

🐱‍👓首先我们建立链表肯定要先初始化，操作跟前面一样此处不再赘述。我们先来看一组图片。

---

🐱‍👓这里我们的目的是什么呢？头插顾名思义头部插入，我们得保证每个元素插入其中必须是头部，所以在我们这里必须更改头指针L的指向，先生成一个新节点p，将头指针指向它，并将头指针原来所指的数据域改为p指针所指向。这样我们就实现了元素的头插。

---

🥇 再来一道超简单的例题

相信懂了头插法的友友们肯定三秒就能出答案吧🤞。

---

🚓3.6.2尾插法建立链表

---

🐳我们接下来再来看看另外一种方法——尾插法。

Status insertback_LinkList(LinkList &L, int n)
{LinkList pa, pb;int i;L = (LinkList)malloc(sizeof(LNode));L->next = NULL;pb = L;for (i = 0; i < n; i++){pa = (LinkList)malloc(sizeof(LNode));scanf("%d", pa->data);pa->next = NULL;pb->next = pa;pb = pa;}return OK;
}

---

🐱‍👓我们先来看看一组帮大家理解的图片

🐱‍👓让我们先来跟头插法比较一下，头插法需要动用头指针L来改变指向来实现头插，那么尾插法呢？🧐相信有不少的友友想到了，我们再令一个尾指针pb通过改变尾指针指向来实现尾插，方法和头插一样，先申请一片内存空间pa，再将pa的next域置空（尾部）。
再将尾指针pb指向它。最后再让pa成为新的尾指针即可实现尾插。🤞

---

🥇 再来一道超简单的例题

🧐光速解答，正好跟头插相反。

---

🚓3.6.3指定位置插入

---

🐳既然头插跟尾插说完了，我们现在来说说指定位置插入。

Status insertplace_LinkList(LinkList &L, int i,ElemType e)
{LinkList p,s;int j=0;p = L;while (p && j < i - 1)p = p->next; ++j;if (!p && j > i - 1) return ERROR;s = (LinkList)malloc(sizeof(LNode));s->data = e;s->next = p->next;p->next = s;return OK;
}

---

🐱‍👓我们先来看看一组帮大家理解的图片

🐱‍👓学完了头插和尾插，此处就变得好理解得多了，我们只需要用while函数寻找指定位置i，之后p指针正好指向i位置，我们只需要调转p指针方向指向插入的新节点s，再将s的next域改为p的next即可🤞。

---

🚗3.7链表的删除

---

🐳学完了插入，当然接下来就是我们的删除啦。

Status Delete_LinkList(LinkList &L, int i)
{LinkList p, q;p = L;int j=0;while (p && j < i - 1)p = p->next; ++j;if (!p && j > i - 1) return ERROR;q = p->next;p->next = q->next;free(q);return OK;
}

---

🐱‍👓我们先来看看一组帮大家理解的图片

🐱‍👓链表的删除十分之简单，它并不像顺序表那样要删除具体的元素值，它只需要改变指针的指向即可。我们依然还是通过while函数找到插入位置再将p指针指向一个后面的节点q（需要删除的节点），再将p指针的next域置为q的next域🤞。最后我们再释放p所占的内存空间，这样我们就完成了节点的删除。

---

🚗3.8链表的合并

---

🐳接下来，我们来看一个链表的应用——合并。

Status merge_LinkList(LinkList &La, LinkList &Lb)
{LinkList pa, pb, pc;LinkList Lc;Lc = La;pc = Lc;pa = La->next;pb = Lb->next;while (pa && pb){if (pa->data > pb->data){pc->next = pa; pa = pa->next; pc = pc->next;}else{pc->next = pb; pb = pb->next; pc = pc->next;}}if (pa != NULL)pc->next = pa;elsepc->next = pb;free(Lb);return OK;
}

---

‍🐱‍👓我们先来看看一组帮大家理解的图片

---

🐱‍👓首先我们如果要合并链表，必须改变指针的指向，此处我们基于建立了三个链表La，Lb，Lc后，分别用三个指针作为其移动指针pa,pb,pc;根据数据元素的大小，来对有序链表进行一个合并操作。较大元素即移入pc指向的新链表，然后元素后移，直至其中一个表为空。🧐那么我们还有一个表呢，我们可以假设一个表还未空，那么可以直接将pc指针指向它。

---

🚗3.9链表的其它形式

---

🐱‍👓对于我们得链表主要有两种形式，其余的基本是这两种的组合或者分支，我们先来介绍这两种循环链表 与 双向链表。

---

---

🚓3.9.1循环链表

---

🐳我们先来看看循环链表。

Status Loop_LinkList(LinkList &L, ElemType e)
{L = (LinkList)malloc(sizeof(LNode));L->next = L;//循环链表//这里我们从尾节点开始查找e元素的值LinkList p;p = L->next;while (p->next != L->next)p = p->next;while (p->data != e && p->next!=L)p = p->next;if (p->next == L)return ERROR;elsereturn OK;
}

🐱‍👓对于循环链表我们得先搞清楚其循环条件以及循环原理。换不多说，先来看一组图片。

---

🐱‍👓这里我们通过图片可以看出循环链表实际上就是把尾指针指向了头结点.由此完成了循环遍历。它的好处是我们可以从任意节点开始查找想要的值，不需要从头到尾进行遍历。

---

🚓3.9.2双向链表

---

🐳老规矩，先上代码。

typedef struct DLNode {ElemType data;struct DLNode* prior;struct DLNode* next;
}DLNode,*DLinkList;
//指定位置插入
Status insertPlace_DLinkList(DLinkList &L, int i, ElemType e)
{DLinkList p,s;int j = 0;while (p && j < i - 1)p = p->next; ++j;if (!p && j > i - 1)return ERROR;s = (DLinkList)malloc(sizeof(DLNode));s->prior = p->prior;p->prior->next = s;s->next = p;p->prior = s;return OK;
}
Status Delete_DLinkList(DLinkList &L, int i)
{DLinkList p;int j = 0;while (p && j < i - 1)p = p->next; ++j;if (!p && j > i - 1)return ERROR;p->prior->next = p->next;p->next->prior = p->prior;free(p);return OK;
}

---

🐱‍👓这里我们一共涉及了三段代码，分别是结构体定义，链表的指定位置插入，以及链表的指定位置删除，看不懂的友友我们就来看一组图片。

---

‍‍🐱‍👓这里我们可以看双向链表对比单链表就多了个前驱prior,可就是因为这个前驱使得其查找数据元素工作变得十分容易。

---

🚗3.10链表的混合（了解）

---

🐱‍👓我们在上一节说到双向链表与循环链表，那么这两种的组合呢？

---

‍‍🐱‍👓双向循环实际上就是双向链表将尾指针指向了头部。相信友友们能自己写出来代码了。

---

🚢4.线性表的应用

---

🚗4.1单链表与顺序表对比

---

‍‍🐱‍👓我们先来对比对比链表与顺序表。

---

‍‍🐱‍👓总的来说，顺序表和链表各有千秋，并不存在哪个好的问题。

---

🚗4.2顺序表手机联系人实操

---

---

‍‍🐱‍👓手机中的联系人无非就是线性表的应用。可以通过链表的基本操作来对联系人进行增删改查。

---

🐳我们先来看看顺序表整体代码。

#define _CRT_SECURE_NO_WARNINGS 
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10typedef int Status;
typedef struct {char name[10];char tel[12];
}ElemType;
typedef struct {ElemType* elem;int length;int listsize;
}SqList;
Status initList_Sq(SqList &L)
{L.elem = (ElemType*)malloc(sizeof(ElemType) * LIST_INIT_SIZE);//为顺序表分配一个LIST_INIT_SIZE大小的空间// L.elem = new ElemType[LIST_INIT_SIZE];if (L.elem == NULL) exit(OVERFLOW);//分配失败，程序退出L.length = 0;//记录表此时长度L.listsize = LIST_INIT_SIZE;//记录表最大表长return OK;
}
Status Listinput(SqList &L)
{strcpy(L.elem[0].name, "老陈");strcpy(L.elem[0].tel, "13624579990");strcpy(L.elem[1].name, "Lily");strcpy(L.elem[1].tel, "13551877806");strcpy(L.elem[2].name, "李丽");strcpy(L.elem[2].tel, "18802854568");strcpy(L.elem[3].name, "李林");strcpy(L.elem[3].tel, "13489786576");L.length = 4;return OK;
}
Status Locate(SqList &L, char person[])
{int i;for (i = 0; i < L.length; i++)if (strcmp(L.elem[i].name, person) == 0) break;if (i < L.length)printf("%s的电话号码是%s\n", person, L.elem[i].tel);elseprintf("查无此人!\n");return OK;
}
void print_List(SqList &L)
{for (int i = 0; i < L.length; i++)printf("%10s%13s\n", L.elem[i].name, L.elem[i].tel);
}
Status Listinsert_Sq(SqList &L, int i, ElemType e)//输入插入位置及插入元素
{int j;for (j = L.length; j >= i; j--)L.elem[j] = L.elem[j - 1];L.elem[i - 1] = e;L.length++;return OK;
}
Status ListDelete_Sq(SqList &L, char person[])
{int i, j, k;for (i = 0; i < L.length; i++)if (strcmp(L.elem[i].name, person) == 0) break;for (j = i; j < L.length; j++)L.elem[j] = L.elem[j+1];L.length--;return OK;}
int main()
{SqList L;Status insertResult, DeleteResult;char name[10];ElemType person;int i;initList_Sq(L);Listinput(L);printf("你想查找谁的电话？");scanf("%s", &name);Locate(L, name);printf("请输入新增联系人的姓名：");scanf("%s", &person.name);printf("请输入新增联系人的电话：");scanf("%s", &person.tel);printf("请输入插入的位置：");scanf("%d", &i);insertResult = Listinsert_Sq(L, i, person);if (insertResult == ERROR)printf("插入位置非法！\n");else if (insertResult == OVERFLOW)printf("存储位置已满！\n");elseprint_List(L);printf("请输入要删除联系人的名字：");scanf("%s", name);DeleteResult = ListDelete_Sq(L, name);if (DeleteResult == ERROR)printf("删除位置非法！\n");elseprint_List(L);return 0;
}

运行结果

---

🚗4.3单链表手机联系人实操

---

🐳我们再来看看单链表整体代码。

#include
#include
#include
#include
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef struct Telephone
{char name[10];char Tel[12];
}ElemType;
typedef struct LNode
{ElemType data;struct LNode *next;
}LNode,*LinkList;
LinkList Creat_LinkList(int n)//向后插入法 
{LinkList head;LNode *r,*s;head=(LinkList)malloc(sizeof(LNode));head->next=NULL;r=head;for(int i=1;i<=n;++i){s=(LNode*)malloc(sizeof(LNode));printf("请输入第%d个联系人的姓名:\n",i);scanf("%s",s->data.name);printf("请输入第%d个联系人的电话:\n",i);scanf("%s",s->data.Tel);s->next=NULL;r->next=s;r=s;}return head;
}
void Print_LinkList(LinkList H)
{LNode *p;p=H->next;while(p!=NULL){printf("姓名：%s,电话：%s\n",p->data.name,p->data.Tel);p=p->next;}
}
LNode *Locate(LinkList L,char person[])
{LNode *p; p=L->next;while(strcmp(p->data.name,person)!=0 && p!=NULL){p=p->next;}return p;
}
Status ListInsert(LinkList &L,int i,ElemType e)
{LNode *p,*s;int j;p=L;j=0;while(p && (j<i-1)){p=p->next;j++;}                                                                                  if(!p || j>i-1) return ERROR;//s=new LNode;s=(LNode *)malloc(sizeof(LNode));s->data=e;s->next=p->next;p->next=s;return OK;
}
Status ListDelete(LinkList &L,char person[])
{LNode *p,*q;p=L;q->next=p;while(strcmp(p->data.name,person)!=0 && p->next!=NULL){p=p->next;q=q->next;}if(!(q->next))return ERROR;p=q->next;q->next=p->next;delete p;return OK;} 
int main()
{LinkList L,p;int n,i;ElemType person;char name[10];printf("请输入通讯录人数:");scanf("%d",&n);L=Creat_LinkList(n);Print_LinkList(L);printf("请输入待查找人姓名："); scanf("%s",name);p=Locate(L,name);printf("%s的电话：%s\n",name,p->data.Tel);printf("请输入插入位置：");scanf("%d",&i);printf("请输入新联系人姓名：");scanf("%s",person.name);printf("请输入新联系人电话：");scanf("%s",person.Tel);ListInsert(L,i,person);Print_LinkList(L);printf("请输入要删除联系人的姓名：");scanf("%s",name);ListDelete(L,name);Print_LinkList(L);return 0;
}

运行结果

---

🚢5.结语

---

讲了这么多，我们的文章也接近尾声了，相信吸收了这篇文章的小伙伴们已经为数据结构打下了坚实的基础，后续我还会继续更新数据结构相关内容，最后再次感谢大家的点赞和关注。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！