数据结构如何改写为长尾词？

本文共计3097个文字，预计阅读时间需要13分钟。

链式存储结构中，结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理位置上不一定相邻。线性表的链式存储表示又称非顺序映像或链式映像，使用一组任意的存储单元存储线性表的结点，这些存储单元可以是连续的，也可以是不连续的。

链式存储结构

结点在存储器中的位置是任意的，即逻辑上相邻的数据元素在物理上不一定相邻。线性表的链式表示又称为非顺序影像或链式映像。 用一组物理位置任意的存储单元来存放线性表的数据元素。 这组存储单元既可以是连续的，也可以是不连续的，甚至是零散分布在内存中的任意位置上的。 链表中元素的逻辑次序和物理次序不一定相同。 在顺序表中，用存储位置的先后就能描述这些数据元素的先后，想取哪个元素，可以直接计算地址就能找到； 在链表中，是随意存储，在存储数据元素时，需要描述出这些元素的逻辑关系，在存储每一个元素的同时，我们还存储了它下一个元素在哪。 单链表是由头指针唯一确定，因此单链表可以用头指针的名字来命名。

与链式存储有关的术语

1.结点：数据元素的存储映像。由数据域和指针域两部分组成 2.链表：n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构。 3.单链表、双链表、循环链表： 结点只有一个指针域的链表，称为单链表或线性链表。 结点有两个指针域的链表，称为双链表 首尾相接的链表称为循环链表 4.头指针、头结点和首元结点： 头指针：是指向链表中的第一个结点的指针 首元结点：是指链表中存储第一个数据元素a1的结点 头结点：是在链表的首元结点之前附设的一个结点；

如何表示空表

在链表中设置头结点有什么好处？

头结点的数据域内装的是什么？

链表（链式存储结构）的特点

单链表的定义和表示

带头结点的单链表 单链表的存储结构 例如，存储学生学号、姓名、成绩的单链表结点类型定义如下：

单链表基本操作的实现

单链表的初始化

即构造一个空表。 算法步骤： （1）生成新结点作头结点，用指针L指向头结点。 （2）将头结点的指针域置空。 算法描述

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

补充算法1————判断链表是否为空

空表：链表中无元素，称为空链表（头指针和头结点仍然在） 算法思路：判断头结点指针域是否为空

int ListEmpty(LinkList L)//若L为空表，则返回1，否则返回0 { if(L->next)//非空 return 0; else return 1; }

补充算法2————单链表的销毁

链表销毁后不存在 算法思路：从头指针开始，依次释放所有结点 一个变量想要指向某一个空间，则将空间的地址赋给它就可以了 将delete换为free就是C的语法

Status DestroyList_L(LinkList &L) { LinkList p; while(L) { p=L; L=L->next; free p; } return OK; }

补充算法3————清空链表

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在） 算法思路：依次释放所有结点，并将头结点指针域设置为空 如何获得第一个结点地址？头结点的next域，p=L->next; 怎么指向头结点？p=L； 最后L->next=NULL;就可以啦！

Status ClearList(LinkList &L) { LinkList p,q;//指针p用来存放当前我们要来删除的结点，指针q用来存放指针p的下一个结点 p=L->next;//从首元结点开始 while(p)//没到表尾 { q=p->next; free p; p=q; } L->next=NULL;//头结点指针域为空 return OK; }

补充算法4————求单链表的表长

算法思路：从首元结点开始，依次计数所有结点

int ListLength_L(LinkList L) {//返回L中数据元素个数 LinkList p; p=L->next;//p指向第一个结点 i=0; while(p)//遍历单链表，统计结点数 { i++; p=p->next; } return i; }

⭐重要算法————取单链表中第i个元素的内容

顺序表里是如何找到第i个元素？L->elem[i-1] 算法步骤： 1.从第1个结点（L->next）顺链扫描，用指针p指向当前扫描到的结点，p初值p=L->next。 2.j做计数器，累计当前扫描过的结点数，j初值为1。 3.当p指向扫描到的下一结点时，计数器j加1。 4.当j==i时，p所指的结点就是要找的第i个结点。 算法描述：

Status GetElem_L(LinkList L,int i,ElemType &e) {//获取线性表L中的某个数据元素的内容，通过变量e返回 p=L->next;j=1;//初始化 while(p&&j<i) {//向后扫描，直到p指向第i个元素或p为空 p=p->next; ++j; } if(!p||j>i)//第i个元素不存在 return ERROR; e=p->data;//取第i个元素 return OK; }

⭐重要算法————单链表的按值查找

分为两种情况： 按值查找1：根据指定数据获取该数据所在的位置（该数据的地址），返回变量p的值 按值查找2：根据指定数据获取该数据所在的位置序号（是第几个数据元素），返回计数器的值 算法步骤： 1.从第一个结点起，依次和e相比较。 2.如果找到一个其值与e相等的数据元素，则返回其在链表中的位置或地址。 3.如果查遍整个链表都没有找到其值和e相等的元素，则返回0或“NULL”。 算法描述：

Lnode *LocatElem_L(LinkList L,ElemType e) { p=L->next; while(p&&p->data!=e) p=p->next; return p; }

算法描述：根据指定数据获取该数据位置序号

int LocateElem_L(LinkList L,ElemType e) { p=L->next;j=1; while(p&&p->data!=e) { p=p->next; j++; } if(p) return j; else return 0; }

⭐重要算法————插入操作

算法步骤： ①和②不能换，会丢失ai的地址。 算法描述

Status ListInsert_L(LinkList &L,int i,ElemType e) { p=L;j=0; while(p&&j<i-1)//寻找第i-1个结点，p指向i-1结点 { p=p->next; ++j; } if(!p||j>i-1) return ERROR;//大于表长+1或者小于1，插入位置非法 s=newLNode; s->data=e;//生成新结点s，将结点s的数据域置为e s->next=p->next;//将结点s插入L中 p->next=s; return OK; }

⭐重要算法————删除第i个结点

算法步骤： 算法描述：

Status ListDelete_L(LinkList &L,int i,ElemType &e) { p=L;j=0;q； while(p->next&&j<i-1) {//寻找第i个结点，并令p指向其前驱 p=p->next; ++j; } if(!(p->next)||j>i-1)//删除位置不合适 return ERROR; q=p->next;//临时保存被删结点的地址以备释放 p->next=q->next;//改变删除结点前驱结点的指针域 e=p->data;//保存删除结点的数据域 free q;//释放删除结点的空间点开始，依次将各结点插入到链表的前端 ![image.png](s2.51cto.com/images/202304/060a22537e653fe3c1520855b3173d42896608.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=) ![image.png](s2.51cto.com/images/202304/232ab8c7921dbcfae29608b26ede0e2de433e0.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_30,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=) 算法描述： ```c void CreateList_L(LinkList &L,int n) { L=newLNode; L->next=NULL; for(i=n;i>0;-i) { p=(LNode*)malloc(sizeof(LNode)); scanf(&p->data); p->next=L->next;//插入表头 L->next=p; } }

单链表的建立————尾插法

尾插法————元素插入在链表的尾部，也叫后插法

//正位序输入n各元素的值，建立带表头结点的单链表L void CreateList_L(LinkList &L,int n) { L->next=NULL; r=L;//尾指针r指向头结点 for(i=0;i<n;++i) { p=newLNode;//生成新结点，输入元素值 p->next=NULL; r->next=p;//插入到表尾 r=p;//r指向新的尾结点 } }

单链表代码实现

//单链表操作 #include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int ElemType; typedef int Status; typedef struct { ElemType data; struct LNode* next; }LNode,*LinkList; Status InitList_L(LinkList L) {//单链表的初始化 L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; return OK; } /*int GreateList_L(LinkList &L,int n) {//头插法 LinkList newLNode; LinkList p; L=newLNode; L->next=NULL; for(i=n;i>0;i--) { p=(LNode*)malloc(sizeof(LNode)); scanf(&p->data); p->next=L->next; L->next=p; } }*/ Status CreatList(LinkList * L) { LinkList p,s; *L=(LinkList)malloc(sizeof(LNode)); //创建头结点 p=*L; //创建一直指向表尾的指针 p->next=NULL; //将头节点的指针指向NULL int x; printf("请输入元素，输入0即停止输入\n"); scanf("%d",&x); while(x){ s=(LinkList)malloc(sizeof(LNode));//创建新的结点 s->data=x; //将数据赋值给新结点的数据域 p->next=s; p=s; scanf("%d",&x); } p->next=NULL; } Status GetElem_L(LinkList L, int i, ElemType* e) {//取单链表中第i个元素的内容 LinkList p; p=L->next; int j=1; while (p && j < i) { p = p->next; ++j; } if (!p || j > i) return ERROR; e = p->data; return p->data; } /*int LocateElem_L(LinkList L, ElemType e) {//按值查找,返回p LinkList p; p = L->next; while (p && p->data != e) { p = p->next; } return p; }*/ int LocateElem_L(LinkList L,ElemType e) {//按值查找，返回位置 LinkList p; p=L->next; int j=1; while(p&&p->data!=e) { p=p->next; j++; } if(p) return j; else { printf("No Found!"); exit(OVERFLOW); } } Status ListInsert_L(LinkList L, int i, ElemType e) {//插入 LinkList p = L; LinkList s; s=(LinkList)malloc(sizeof(LNode)); int j = 0; while (p && j < i - 1)//寻找i-1个结点，p指向i-1个结点 { p = p->next; ++j; } if (!p || j > i - 1) return ERROR; s->data = e;//生成新结点s，将结点s的数据域置为e s->next = p->next;//将结点s插入L中 p->next = s; return OK; } Status ListDelete_L(LinkList *L, int i,ElemType *e) {//删除 LinkList p, q; p = *L; int j=0; while(p->next&&j<i-1)//寻找第i个结点，并令p指向其前驱 { p=p->next; ++j; } if(!(p->next)||j>i-1) return ERROR; q=p->next;//临时保存被删结点前驱结点以备释放 p->next=q->next;//改变删除结点前驱的指针域 *e=q->data;//保存删除结点的数据域 free(q);//释放删除结点 return OK; } int ListEmpty(LinkList L) { if(L->next) return 0; else return 1; } Status DestroyList_L(LinkList L) { LinkList p; while(L) { p=L; L=L->next; free(p); } return OK; } Status ClearList(LinkList L) { LinkList p,q;//指针p用来存放当前我们要来删除的结点，指针q用来存放p的下一个结点 p=L->next; while(p) { q=p->next; free(p); p=q; } L->next=NULL; return OK; } int ListLength_L(LinkList L) { LinkList p; p=L->next; int i=0; while(p) { i++; p=p->next; } return i; } void PrintList(LinkList L) { LinkList p=L->next; printf("链表如下:\n"); while(p!=NULL) { printf("%d ",p->data); p=p->next; } printf("\n"); } int main() {//测试代码 LinkList L; int i; int j; int n; ElemType e; InitList_L(L); CreatList(&L); PrintList(L); printf("请输入要取出元素的位序:"); scanf("%d",&i); e=GetElem_L(L,i,&e); printf("第%d个元素是%d\n",i,e); printf("请输入要查找的元素:"); scanf("%d",&e); j=LocateElem_L(L,e); printf("%d的位序为%d\n",e,j); printf("请输入要插入的元素及插入位置:"); scanf("%d %d",&e,&i); ListInsert_L(L,i,e); PrintList(L); printf("请输入要删除元素的位置:"); scanf("%d",&i); ListDelete_L(&L,i,&e); printf("删除后的链表为:\n"); PrintList(L); return 0; }

单链表的优缺点