数据结构与算法 -- 链表
标签： 数据结构与算法 -- 链表 博客 51CTO博客
2023-07-22 18:24:14 260浏览
数据结构与算法 -- 链表，NULL。其中第一个节点叫做头节点，指向头结点的指针叫做头指针。最后一个节点叫做尾节点。
一、链表介绍
1、链表有地址不连续的结点序列，必须通过指针相互连接。
2、链表的分类：
（1）单向线性链表
每个节点中除了存储数据结构内容以外，还需要保存指向下一个节点的指针，叫做后指针。最后一个节点的后指针为NULL。其中第一个节点叫做头节点，指向头结点的指针叫做头指针。最后一个节点叫做尾节点。
（2）单向循环链表
与单向线性链表不同的是，链表尾节点的后指针指向头节点。首尾相接构成环状结构。
（3）双向线性链表
每个节点除了存放本身元素以外，还需要保存指向下一个节点的指针，叫做后指针，以及指向前一个节点的指针，叫做前指针。双向线性链表中头节点的前指针为空，以及尾节点后指针也是空指针。
（4）双向循环链表
与双向线性链表相比，头节点中的前指针指向尾节点，尾节点的后指针指向头节点，构成环状结构。
（5）其他
除了以上链表以外，还有很多链表，如数组链表、链表数组等等。
简单介绍完了，下面开始一一讲解下。
二、单向线性链表 （重点）
1、参看：C中链表
链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链表指向列表中的下一个节点，而最后一个节点则指向一个空值。如下：
一个单向链表的节点被分成两个部分。第一部分保存或者显示关于节点的信息，第二部分存储下一个节点的地址。单向链表只可向一个方向遍历。
链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时存储指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没有必要了，不如在链表上存储指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要存储反向的指针，见下面的双向链表）节点。
相对于下面的双向链表，这种普通的，每个节点只有一个指针的链表也叫单向链表，或者单链表。通常用在每次只会按顺序遍历这个链表的时候（例如图的邻接表，通常都是按固定顺序访问的）。
举个例子：建立链表保存学生的信息，并且可以进行，插入、删除操作，并将学生的信息输出。
参看：链表实现学生信息管理
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct node
{
int number;
char name[10];
char sex[5];
int classes;
int tel;
struct node *next;
};
typedef struct node NODE;
void scanning(NODE *head); /*申明浏览函数*/
NODE *insert(NODE *head); /*申明插入函数*/
void del(NODE *head); /*申明删除函数*/
void fix(NODE *head); /*申明修改函数*/
int main (void)
{
int choice;
int flag=1;
NODE *head;
head=(NODE *)malloc(sizeof(NODE));
head->next=NULL;
while(flag)
{
printf("请选择功能:\n 1—信息浏览\n 2—插入信息\n 3—删除信息\n 4-修改信息\n 0—退出程序\n");
scanf("%d",&choice);
switch(choice)
{
case 1:
scanning(head);break;
case 2:
head=insert(head);break;
case 3:
del(head);break;
case 4:
fix(head);break;
case 0:
flag=0; break;
}
}
printf("\n");
printf("谢谢使用！\n");
return 0;
}
void scanning(NODE *head) /*定义浏览函数*/
{
NODE *t;
t=head;
t=t->next;
if(t==NULL)
{
printf("\n");
printf("无记录！请先输入学生信息：\n");
printf("\n");
}
while(t!=NULL)
{
printf("学号：%d\n",t->number);
printf("姓名：%s\n",t->name);
printf("性别：%s\n",t->sex);
printf("班级：%d\n",t->classes);
printf("联系方式：%d\n",t->tel);
printf("\n");
t=t->next;
}
}
NODE *insert(NODE *head) /*定义插入函数*/
{
NODE *t,*p;
int a,b,c;
char e[10],f[5];
t=(NODE *)malloc(sizeof(NODE));
p=head;
if(p->next==NULL) /*原本无元素*/
{
printf("请输入学号：\n");
scanf("%d",&a);
printf("请输入姓名：\n");
scanf("%s",e);
printf("请输入性别：\n");
scanf("%s",f);
printf("请输入班级：\n");
scanf("%d",&b);
printf("请输入号码：\n");
scanf("%d",&c);
t->number=a;
strcpy(t->name,e);
strcpy(t->sex,f);
t->classes=b;
t->tel=c;
p->next=t;
t->next=NULL;
}
else /*原本有元素*/
{
printf("请输入学号：\n");
scanf("%d",&a);
printf("请输入姓名：\n");
scanf("%s",e);
printf("请输入性别：\n");
scanf("%s",f);
printf("请输入班级：\n");
scanf("%d",&b);
printf("请输入号码：\n");
scanf("%d",&c);
t->number=a;
strcpy(t->name,e);
strcpy(t->sex,f);
t->classes=b;
t->tel=c;
t->next=p->next;
p->next=t;
}
return head;
}
void del(NODE *head) /*定义删除函数*/
{
int m;
NODE *s,*t;
s=head;
t=head->next;
printf("请输入你要删除的同学的学号：\n");
scanf("%d",&m);
while(t!=NULL)
{
if((t->number)!=m)
{
s=s->next;
t=t->next;
}
else
{
s->next=t->next;
free(t);
break;
}
}
}
void fix(NODE *head) /*定义修改函数*/
{
NODE *p,*t;
int m,q,z=1;
p=head;
t=(NODE *)malloc(sizeof(NODE));
printf("请输入你要修改的学生的学号：\n");
scanf("%d",&m);
p=p->next;
while(p!=NULL)
{
if((p->number)==m)
{
while(z)
{
printf("你想要修改哪项数据？\n 1代表学号\n 2代表姓名\n 3代表性别\n 4代表班级\n 5代表联系方式\n (注意：修改完毕请输入0)\n");
scanf("%d",&q);
switch(q)
{
case 1:
printf("请输入修改后的学号！\n");
scanf("%d",&t->number);
p->number=t->number;
break;
case 2:
printf("请输入修改后的姓名！\n");
scanf("%s",t->name);
strcpy(p->name,t->name);
break;
case 3:
printf("请输入修改的性别！\n");
scanf("%s",t->sex);
strcpy(p->sex,t->sex);
break;
case 4:
printf("请输入修改的班级！\n");
scanf("%d",&t->classes);
p->classes=t->classes;
break;
case 5:
printf("请输入修改后的联系方式！\n");
scanf("%d",&t->tel);
p->tel=t->tel;
break;
case 0:
z=0;
break;
}
}
}
p=p->next;
}
}
2、自写单链表
扩展：数据结构与算法：链表基础
扩展：链表各类操作详解
代码实现说明：
插入节点时，需要考虑多种情况，如输入坐标不合法、插入到头节点、在其他位置插入新节点等。插入方式为新建节点的下个节点指向头节点，而后让头节点指向新建节点，完成插入。其他位置插入则是循环到坐标位置。
删除节点时，也需要考虑多种情况，如输入坐标坐标不合法、删除头节点、删除其他节点等。删除方式为头节点找个替身，然后将头节点指向头节点的下个节点。其他位置删除则是循环到坐标位置。
//实现单链表中的各种操作
#include <stdio.h>
#include <stdlib.h>//动态分配内存
//定义节点的数据类型
typedef struct Node
{
int data;//数据内容，可以是其他的数据类型
struct Node* next;//下一个节点地址
}Node;
typedef struct
{
int cnt;//记录节点个数
Node* head;//头节点
}List;//链表
//创建新节点的功能
Node* create_node(int data)
{
Node* pn=(Node*)malloc(sizeof(Node));
pn->next=NULL;
pn->data=data;
}
//向指定的位置插入指定的新节点
void insert(List* pl,int pos,int data)
{
//1.判断pos坐标是否合法
if(pos < 0 || pos > pl->cnt)//插入坐标不合法
{
//printf("插入坐标不合法，插入新节点失败\n");
//return;
//pos=0;//默认插入到头节点位置
pos=pl->cnt;//插入到尾部
}
//2.创建新节点
//Node* pn=(Node*)malloc(sizeof(Node));
//pn->next=NULL;
//pn->data=data;
Node* pn=create_node(data);
//3.当头节点位置插入节点时
if(0==pos)
{
pn->next=pl->head;
pl->head=pn;
pl->cnt++;
return;
}
//4.当向其他位置插入新节点时
Node* p=pl->head;
int i=0;
for(i=1;i<pos;i++)
{
p=p->next;//指向下一个
}
pn->next=p->next;
p->next=pn;
//节点个数加1
pl->cnt++;
}
//向链表的头节位置插入新节点
void push_head(List* pl,int data)
{
//创建新的节点
//Node* pn=(Node*)malloc(sizeof(Node));
//pn->next=NULL;
//pn->data=data;
//Node* pn=create_node(data);
//插入新节点到链表头部
//pn->next=pl->head;
//pl->head=pn;
//pl->cnt++;
insert(pl,0,data);
}
//遍历链表的操作
void travel(List* pl)
{
Node* p=pl->head;
if (NULL == p)
{
printf ("链表已空\n");
return ;
}
printf("链表中的元素有：\n");
while(NULL!=p)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
}
//计算链表中节点个数
int size(List* pl)
{
return pl->cnt;
}
//判断链表是否为空
int empty(List* pl)
{
return NULL==pl->head;
}
//判断链表是否为满
int full(List* pl)
{
return 0;
}
//向链表的尾部插入新节点
void push_tail(List* pl,int data)
{
insert(pl,pl->cnt,data);
}
//删除链表中指定下标的节点
void del(List* pl,int pos)
{
//1.判断坐标是否合法
if(pos<0||pos>=pl->cnt)//注意其中有等于的情况
{
printf("坐标不合法，删除节点失败\n");
return;
}
//2.当删除头节点时的处理方案
if(0==pos)
{
Node* p=pl->head;
pl->head=pl->head->next;
free(p);
p=NULL;
pl->cnt--;
return;
}
//3.当删除其他节点时的处理方法
Node* p=pl->head;
int i=0;
for(i=1;i<pos;i++)
{
p=p->next;
}
//下面代码是pos=1时的功能代码
Node* q=p->next;
p->next=p->next->next;
free(q);
q=NULL;
pl->cnt--;
}
//清空链表中的所有节点
void clear(List* pl)
{
printf ("清空链表中的所有节点\n");
while(pl->head!=NULL)
{
//保存即将释放的节点地址
Node* p=pl->head;
//头指针指向下一个节点
pl->head=pl->head->next;
//释放保存的节点
free(p);
p=NULL;
}
//将链表中节点元素的个数置为0
pl->cnt=0;
}
int main()
{
//创建链表
List list;
list.head=NULL;
list.cnt=0;
push_head(&list,11);
push_head(&list,22);
push_head(&list,33);
push_head(&list,44);
travel(&list);
insert(&list,3,100);
travel(&list);
insert(&list,3,66);
travel(&list);
insert(&list,3,55);
travel(&list);
insert(&list,-2,77);
travel(&list);
insert(&list,8,88);
travel(&list);
del(&list,9);
travel(&list);
del(&list,0);
travel(&list);
del(&list,3);
travel(&list);
printf("链表中元素个数是：%d\n",size(&list));
printf("%s\n",full(&list)?"链表为满":"链表未满");
printf("%s\n",empty(&list)?"链表为空":"链表未空");
clear(&list);
travel(&list);
return 0;
}
输出结果：
链表中的元素有：
44 33 22 11
链表中的元素有：
44 33 22 100 11
链表中的元素有：
44 33 22 66 100 11
链表中的元素有：
44 33 22 55 66 100 11
链表中的元素有：
44 33 22 55 66 100 11 77
链表中的元素有：
44 33 22 55 66 100 11 77 88
坐标不合法，删除节点失败
链表中的元素有：
44 33 22 55 66 100 11 77 88
链表中的元素有：
33 22 55 66 100 11 77 88
链表中的元素有：
33 22 55 100 11 77 88
链表中元素个数是：7
链表未满
链表未空
清空链表中的所有节点
链表已空3、单向线性链表总结
每个节点除了存放元素数据之外，还需要保存指向下一个节点的指针，即所谓后指针。
链表尾节点的后指针为空指针。
三、单向循环链表
对于一个循环链表来说其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表利于节约数据存储缓存，假定你在一个列表中有一对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的指针可以被作为访问指针。如下：
循环链表中第一个节点之前就是最后一个节点，反之亦然。换换链表的无边界使得这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大（详见下面的示例）。当然，如果只会在最后插入数据（或者只会之前），处理也是很容易的。
另外有一种模拟的循环链表，就是访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。
代码实现说明：
插入节点时， 需要考虑多种情况，如输入坐标不合法、插入到头节点、在其他位置插入新节点等。插入方式为 新建节点的下个节点指向新建节点，而后让头节点指向新建节点，完成插入。 其他位置插入则是循环到坐标位置。
和线性链表不同，如果链表无节点则新建节点下个节点不指向NULL，而是执行本身。
删除节点时，也需要考虑多种情况，如输入坐标坐标不合法、删除头节点、删除其他节点等。删除方式为头节点找个替身，然后将头节点指向头节点的下个节点。其他位置删除则是循环到坐标位置。
当删除的只剩一个节点时，删除后需要设置为NULL。
1、单向循环链表
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFESIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int Boolean;
typedef int ElemType;
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *LinkList; /* 另一种定义LinkList的方法 */
/* bo2-4.c 设立尾指针的单循环链表(存储结构由c2-2.h定义)的12个基本操作 */
Status InitList_CL(LinkList *L)
{ /* 操作结果：构造一个空的线性表L */
*L=(LinkList)malloc(sizeof(struct LNode)); /* 产生头结点,并使L指向此头结点 */
if(!*L) /* 存储分配失败 */
exit(OVERFLOW);
(*L)->next=*L; /* 指针域指向头结点 *
return OK;
}
Status DestroyList_CL(LinkList *L)
{ /* 操作结果：销毁线性表L */
LinkList q,p=(*L)->next; /* p指向头结点 */
while(p!=*L) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;/
return OK;
}
Status ClearList_CL(LinkList *L) /* 改变L */
{ /* 初始条件：线性表L已存在。操作结果：将L重置为空表 */
LinkList p,q;
*L=(*L)->next; /* L指向头结点 */
p=(*L)->next; /* p指向第一个结点 */
while(p!=*L) /* 没到表尾 */
{
q=p->next;
free(p);
p=q;
}
(*L)->next=*L; /* 头结点指针域指向自身 */
return OK;
}
Status ListEmpty_CL(LinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L->next==L) /* 空 */
return TRUE;
else
return FALSE;
}
int ListLength_CL(LinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i=0;
LinkList p=L->next; /* p指向头结点 */
while(p!=L) /* 没到表尾 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem_CL(LinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* 初始化,j为计数器 */
LinkList p=L->next->next; /* p指向第一个结点 */
if(i<=0||i>ListLength_CL(L)) /* 第i个元素不存在 */
return ERROR;
while(j<i)
{ /* 顺指针向后查找,直到p指向第i个元素 */
p=p->next;
j++;
}
*e=p->data; /* 取第i个元素 */
return OK;
}
int LocateElem_CL(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件：线性表L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i=0;
LinkList p=L->next->next; /* p指向第一个结点 */
while(p!=L->next)
{
i++;
if(compare(p->data,e)) /* 满足关系 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem_CL(LinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 否则操作失败，pre_e无定义 */
LinkList q,p=L->next->next; /* p指向第一个结点 */
q=p->next;
while(q!=L->next) /* p没到表尾 */
{
if(q->data==cur_e)
{
*pre_e=p->data;
return TRUE;
}
p=q;
q=q->next;
}
return FALSE;
}
Status NextElem_CL(LinkList L,ElemType cur_e,ElemType *next_e)
{ /* 初始条件：线性表L已存在 */
/* 操作结果：若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继， */
/* 否则操作失败，next_e无定义 */
LinkList p=L->next->next; /* p指向第一个结点 */
while(p!=L) /* p没到表尾 */
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status ListInsert_CL(LinkList *L,int i,ElemType e) /* 改变L */
{ /* 在L的第i个位置之前插入元素e */
LinkList p=(*L)->next,s; /* p指向头结点 */
int j=0;
if(i<=0||i>ListLength_CL(*L)+1) /* 无法在第i个元素之前插入 */
return ERROR;
while(j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
s=(LinkList)malloc(sizeof(struct LNode)); /* 生成新结点 */
s->data=e; /* 插入L中 */
s->next=p->next;
p->next=s;
if(p==*L) /* 改变尾结点 */
*L=s;
return OK;
}
Status ListDelete_CL(LinkList *L,int i,ElemType *e) /* 改变L */
{ /* 删除L的第i个元素,并由e返回其值 */
LinkList p=(*L)->next,q; /* p指向头结点 */
int j=0;
if(i<=0||i>ListLength_CL(*L)) /* 第i个元素不存在 */
return ERROR;
while(j<i-1) /* 寻找第i-1个结点 */
{
p=p->next;
j++;
}
q=p->next; /* q指向待删除结点 */
p->next=q->next;
*e=q->data;
if(*L==q) /* 删除的是表尾元素 */
*L=p;
free(q); /* 释放待删除结点 */
return OK;
}
Status ListTraverse_CL(LinkList L)
{ /* 初始条件:L已存在。操作结果:依次对L的每个数据元素调用函数vi()。一旦vi()失败,则操作失败 */
LinkList p=L->next->next;
while(p!=L->next)
{
printf("%d ",p->data);
p=p->next;
}
printf("\n");
return OK;
}
Status compare(ElemType c1,ElemType c2)
{
if(c1==c2)
return TRUE;
else
return FALSE;
}
int main()
{
LinkList L;
ElemType e;
int j;
Status i;
i = InitList_CL(&L);
printf("初始化单循环链表L i=%d(1:初始化成功)\n", i);
i=ListEmpty_CL(L);
printf("L是否空 i=%d(1:空 0:否)\n",i);
ListInsert_CL(&L,1,3); /* 在L中依次插入3,5 */
ListInsert_CL(&L,2,5);
i=GetElem_CL(L,1,&e);
j=ListLength_CL(L);
printf("L中数据元素个数=%d,第1个元素的值为%d。\n",j,e);
printf("L中的数据元素依次为：");
ListTraverse_CL(L);
PriorElem_CL(L,5,&e); /* 求元素5的前驱 */
printf("5前面的元素的值为%d。\n",e);
NextElem_CL(L,3,&e); /* 求元素3的后继 */
printf("3后面的元素的值为%d。\n",e);
printf("L是否空 %d(1:空 0:否)\n",ListEmpty_CL(L));
j=LocateElem_CL(L,5,compare);
if(j)
printf("L的第%d个元素为5。\n",j);
else
printf("不存在值为5的元素\n");
i=ListDelete_CL(&L,2,&e);
printf("删除L的第2个元素：\n");
if(i)
{
printf("删除的元素值为%d,现在L中的数据元素依次为：",e);
ListTraverse_CL(L);
}
else
printf("删除不成功！\n");
printf("清空L：%d(1: 成功)\n",ClearList_CL(&L));
printf("清空L后，L是否空：%d(1:空 0:否)\n",ListEmpty_CL(L));
printf("销毁L：%d(1: 成功)\n",DestroyList_CL(&L));
return 0;
}
输出结果：
初始化单循环链表L i=1(1:初始化成功)
L是否空 i=1(1:空 0:否)
L中数据元素个数=2,第1个元素的值为3。
L中的数据元素依次为：3 5
5前面的元素的值为3。
3后面的元素的值为5。
L是否空 0(1:空 0:否)
L的第2个元素为5。
删除L的第2个元素：
删除的元素值为5,现在L中的数据元素依次为：3
清空L：1(1: 成功)
清空L后，L是否空：1(1:空 0:否)
销毁L：1(1: 成功)
2、再例
#include <stdio.h>
#include <stdlib.h>
/*存储结构的定义*/
typedef struct CLinkList {
int data ;
struct CLinkList * next ;
}node;
/************************************************************************/
/* 操作 */
/************************************************************************/
/*初始化循环链表*/
void ds_init(node ** pNode) {
int item ;
node * temp ;
node * target ;
printf("输入结点的值，输入0完成初始化\n");
while(1) {
scanf("%d",&item) ;
fflush(stdin) ;
if(item == 0)
return ;
if((*pNode) == NULL) { /*循环链表中只有一个结点*/
*pNode = (node*)malloc(sizeof(struct CLinkList)) ;
if(!(*pNode))
exit(0) ;
(*pNode)->data = item ;
(*pNode)->next = *pNode ;
}
else {
/*找到next指向第一个结点的结点*/
for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ;
/*生成一个新的结点*/
temp = (node *) malloc(sizeof(struct CLinkList)) ;
if(!temp)
exit(0) ;
temp->data = item ;
temp->next = *pNode ;
target->next = temp ;
}
}
}
/*插入结点*/
/*参数：链表的第一个结点，插入的位置*/
void ds_insert(node ** pNode ,int i) {
node * temp ;
node * target ;
node * p ;
int item ;
int j = 1 ;
printf("输入要插入结点的值:");
scanf("%d",&item) ;
if(i == 1) { //新插入的结点作为第一个结点
temp = (node *)malloc(sizeof(struct CLinkList)) ;
if(!temp)
exit(0) ;
temp ->data = item ;
/*寻找到最后一个结点*/
for(target = (*pNode) ; target->next != (*pNode) ; target = target->next) ;
temp->next = (*pNode) ;
target->next = temp ;
*pNode = temp ;
}
else {
target = *pNode ;
for( ; j < (i-1) ; target=target->next,++ j) ;
temp = (node *)malloc(sizeof(struct CLinkList)) ;
if(!temp)
exit(0) ;
temp ->data = item ;
p = target->next ;
target->next = temp ;
temp->next = p ;
}
}
/*删除结点*/
void ds_delete(node ** pNode,int i) {
node * target ;
node * temp ;
int j = 1 ;
if(i == 1) { //删除的是第一个结点
/*找到最后一个结点*/
for(target = *pNode ; target->next != *pNode ;target = target->next) ;
temp = *pNode ;
*pNode = (*pNode)->next ;
target->next = *pNode ;
free(temp) ;
}
else {
target = *pNode ;
for( ; j < i-1 ; target= target->next,++j) ;
temp = target->next ;
target->next = temp->next ;
free(temp) ;
}
}
/*返回结点所在位置*/
int ds_search(node * pNode,int elem) {
node * target ;
int i = 1 ;
for(target = pNode ; target->data != elem && target->next != pNode ; ++i , target = target->next) ;
if(target->next == pNode) /*表中不存在该元素*/
return 0 ;
else
return i ;
}
/*遍历*/
void ds_traverse(node * pNode) {
node * temp ;
temp = pNode ;
printf("***********链表中的元素******************\n");
do {
printf("%4d ",temp->data) ;
}while((temp = temp->next) != pNode) ;
printf("\n") ;
}
int main()
{
node * pHead = NULL ;
char opp;
int find;
printf("\n1.初始化链表 \n2.插入结点 \n3.删除结点 \n4.返回结点位置 \n5.遍历链表 \n0.退出 \n请选择你的操作：\n");
while(opp != '0'){
scanf("%c",&opp);
switch(opp){
case '1':
ds_init(&pHead);
printf("\n");
ds_traverse(pHead) ;
break;
case '2':
printf("输入需要插入结点的位置？");
scanf("%d", &find);
ds_insert(&pHead,find) ;
printf("在位置%d插入值后：\n", find) ;
ds_traverse(pHead) ;
printf("\n");
break;
case '3':
printf("输入需要删除的结点位置？");
scanf("%d", &find);
ds_delete(&pHead,find) ;
printf("删除第%d个结点后:\n", find) ;
ds_traverse(pHead) ;
printf("\n");
break;
case '4':
printf("你要查找倒数第几个结点的值？");
scanf("%d", &find);
printf("元素%d所在位置：%d\n", find, ds_search(pHead,find)) ;
//ListTraverse(L);
printf("\n");
break;
case '5':
ds_traverse(pHead) ;
printf("\n");
break;
case '0':
exit(0);
}
}
return 0 ;
}3、又例
//循环链表是一种手尾相接的链表,在单链表中,如果最后一个结点的指针域不指向空,而是指向头结点,整个链表就形成一个环,这是另一种的链式存储结构,成为单循环链表,类似的还有多重循环链表
//为了使空表和非空表的处理一致,同样设置了一个头结点
//创建头结点后,应有h->next=h语句
//特点1.从任意结点出发可以很容易的找到其他的结点,在某些算法上易于实现
//特点2.单循环链表的操作和实现和单链表的上基本一致,但注意的是算法的循环条件p或p->next 是否为空改为是否等于头指针
#include <stdio.h>
#include "stdlib.h"
typedef int elemetType;
typedef struct Node {
elemetType data;
struct Node* next;
}cNode,*circleList;
#pragma mark --创建有n个结点的循环链表
cNode* create(int n) {
cNode*cNew,*cHead,*cTail; //声明三个链表
cHead=(cNode*)malloc(sizeof(cNode));//头结点申请空间
cHead->next=cHead; // 空链表指向自身
cTail=cHead; //cTail的指针指向cHead
int i = 0;
for (i=0; i<n; i++) {
cNew=malloc(sizeof(cNode));
if (cNew==NULL) {
printf("errpr\n");
exit(0);
}
cNew->data=i;
if (cHead->next==cHead) {//此时为空链表
cHead->next=cNew;
cTail=cNew; //cTail指向新添加的结点
}else { //不是空链表的时候
cTail->next=cNew;
cTail=cNew;
}
}
cTail->next=cHead;//添加完毕后,把尾指针的指针域指向头结点
return cTail;
}
#pragma mark --单循环链表的遍历
void traverse(cNode*c) {
cNode* tempNode;
tempNode=c;
printf("------链表中的元素--------\n");
printf("%4d ",tempNode->data) ;
do {
printf("%4d ",tempNode->data) ;
}while((tempNode = tempNode->next) != c);
printf("\n") ;
printf("\n") ;
}
#pragma mark --在单循环列表查找值为x的结点
cNode* get(cNode*h,elemetType x) {
cNode*p;
p=h->next;
while (p!=h&&p->data!=x)
p=p->next;
if (p==h) {
printf("----不好意思,您转了一圈还是没有找到----\n");
return NULL;
}
printf("--找到了--\n");
return p;
}
#pragma mark 返回结点所处的位置
int searchPosition(cNode * pNode,int elem) {
cNode * target ;
int i = 1 ;
for(target = pNode ; target->data != elem && target->next != pNode ; ++i , target = target->next) ;
if(target->next == pNode) /*表中不存在该元素*/
return 0 ;
else
return i ;
}
int main(int argc, const char * argv[]) {
// insert code here...
cNode*c=create(20);
traverse(c);
get(c, 40);
get(c, 10);
int position=searchPosition(c, 6);
printf("position====%d\n",position);///????为什么等于9
return 0;
}
输出结果：
------链表中的元素--------
19 19 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
----不好意思,您转了一圈还是没有找到----
--找到了--
position====9
4、单向循环链表总结
每个节点除了存放元素数据之外，还需要保存指向下一个节点的指针，即所谓后指针。
链表尾节点的后指针指向首节点，首尾相接构成环状。
四、双向线性链表
C语言中一种更复杂的链表式“双向链表”或“双面链表”。其表中的每个节点有两个连接：一个指向前一个节点，（当这个“连接”为第一个：“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当这个“连接”为最后一个：“连接”时，指向空值或者空列表）。例如：
在一些低级语言中，XOR-linking 提供一种在双向链表中通过用一个词来表示两个链接（前后）,我们通常不提倡这种方法.
双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样就可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至于整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。
由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数据里的情况，也可以直接用这个数组表示链表并用第 0 个或者第 -1 个 （如果编译器支持）节点固定的表示这个虚拟节点。
1、双向线性链表
参看：（C语言版）链表（三）——实现双向链表创建、删除、插入、释放内存等简单操作
参看：链表（单向、双向、单向循环、双向循环）学习过程总结——有源代码、注释和示意图
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *pNext;
struct Node *pPre;
}NODE, *pNODE;
//创建双向链表
pNODE CreateDbLinkList(void);
//打印链表
void TraverseDbLinkList(pNODE pHead);
//判断链表是否为空
int IsEmptyDbLinkList(pNODE pHead);
//计算链表长度
int GetLengthDbLinkList(pNODE pHead);
//向链表插入节点
int InsertEleDbLinkList(pNODE pHead, int pos, int data);
//从链表删除节点
int DeleteEleDbLinkList(pNODE pHead, int pos);
//删除整个链表，释放内存
void FreeMemory(pNODE *ppHead);
int main(void)
{
int flag = 0, length = 0;
int position = 0, value = 0;
pNODE head = NULL;
head = CreateDbLinkList();
flag = IsEmptyDbLinkList(head);
if (flag)
printf("双向链表为空！\n");
else
{
length = GetLengthDbLinkList(head);
printf("双向链表的长度为：%d\n", length);
TraverseDbLinkList(head);
}
printf("请输入要插入节点的位置和元素值(两个数用空格隔开)：");
scanf("%d %d", &position, &value);
flag = InsertEleDbLinkList(head, position, value);
if (flag)
{
printf("插入节点成功！\n");
TraverseDbLinkList(head);
}
else
printf("插入节点失败！\n");
flag = IsEmptyDbLinkList(head);
if (flag)
printf("双向链表为空，不能进行删除操作！\n");
else
{
printf("请输入要删除节点的位置：");
scanf("%d", &position);
flag = DeleteEleDbLinkList(head, position);
if (flag)
{
printf("删除节点成功！\n");
TraverseDbLinkList(head);
}
else
printf("删除节点失败！\n");
}
FreeMemory(&head);
if (NULL == head)
printf("已成功删除双向链表，释放内存完成！\n");
else
printf("删除双向链表失败，释放内存未完成！\n");
return 0;
}
//创建双向链表
pNODE CreateDbLinkList(void)
{
int i, length = 0, data = 0;
pNODE pTail = NULL, p_new = NULL;
pNODE pHead = (pNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
pHead->data = 0;
pHead->pPre = NULL;
pHead->pNext = NULL;
pTail = pHead;
printf("请输入想要创建链表的长度：");
scanf("%d", &length);
for (i=1; i<length+1; i++)
{
p_new = (pNODE)malloc(sizeof(NODE));
if (NULL == p_new)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
printf("请输入第%d个元素的值：", i);
scanf("%d", &data);
p_new->data = data;
p_new->pNext = NULL;
p_new->pPre = pTail;
pTail->pNext = p_new;
pTail = p_new;
}
return pHead;
}
//打印链表
void TraverseDbLinkList(pNODE pHead)
{
pNODE pt = pHead->pNext;
printf("打印链表如：");
while (pt != NULL)
{
printf("%d ", pt->data);
pt = pt->pNext;
}
putchar('\n');
}
//判断链表是否为空
int IsEmptyDbLinkList(pNODE pHead)
{
pNODE pt = pHead->pNext;
if (pt == NULL)
return 1;
else
return 0;
}
//计算链表的长度
int GetLengthDbLinkList(pNODE pHead)
{
int length = 0;
pNODE pt = pHead->pNext;
while (pt != NULL)
{
length++;
pt = pt->pNext;
}
return length;
}
//向双向链表中插入节点
int InsertEleDbLinkList(pNODE pHead, int pos, int data)
{
pNODE pt = NULL, p_new = NULL;
if (pos > 0 && pos < GetLengthDbLinkList(pHead)+2)
{
p_new = (pNODE)malloc(sizeof(NODE));
if (NULL == p_new)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
while (1)
{
pos--;
if (0 == pos)
break;
pHead = pHead->pNext;
}
pt = pHead->pNext;
p_new->data = data;
p_new->pNext = pt;
if (NULL != pt)
pt->pPre = p_new;
p_new->pPre = pHead;
pHead->pNext = p_new;
return 1;
}
else
return 0;
}
//从链表中删除节点
int DeleteEleDbLinkList(pNODE pHead, int pos)
{
pNODE pt = NULL;
if (pos > 0 && pos < GetLengthDbLinkList(pHead) + 1)
{
while (1)
{
pos--;
if (0 == pos)
break;
pHead = pHead->pNext;
}
pt = pHead->pNext->pNext;
free(pHead->pNext);
pHead->pNext = pt;
if (NULL != pt)
pt->pPre = pHead;
return 1;
}
else
return 0;
}
//删除整个链表，释放内存
void FreeMemory(pNODE *ppHead)
{
pNODE pt = NULL;
while (*ppHead != NULL)
{
pt = (*ppHead)->pNext;
free(*ppHead);
if (NULL != pt)
pt->pPre = NULL;
*ppHead = pt;
}
}
输出结果：
请输入想要创建链表的长度：5
请输入第1个元素的值：1
请输入第2个元素的值：2
请输入第3个元素的值：3
请输入第4个元素的值：4
请输入第5个元素的值：5
双向链表的长度为：5
打印链表如：1 2 3 4 5
请输入要插入节点的位置和元素值(两个数用空格隔开)：2 6
插入节点成功！
打印链表如：1 6 2 3 4 5
请输入要删除节点的位置：2
删除节点成功！
打印链表如：1 2 3 4 5
已成功删除双向链表，释放内存完成！
2、自写双向线性链表
代码实现说明：
插入节点时，首先判断要插入的节点的位置是否正确，然后创建节点。最后，插入节点，插入时分两种情况处理，一种是插入到第一个节点前面，另一种是插入到链表中间。
创建持有待插入元素的新节点，令其前指针指向给定节点的前节点，令其后指针指向给定节点。
若新建节点存在前节点，则令其前节点的后指针指向新建节点，否则新建节点为新的首节点。
令新建节点的后节点的前指针指向新建节点。
删除节点时，首先判断要删除的结点位置是否正确。然后，删除结点，删除时分两种情况处理：一种是删除第一个结点，另一种是删除链表的中间结点。最后，释放被删除结点所占有的存储空间。
若将亡节点存在前节点，则令其前节点的后指针指向将亡节点的后节点，否则将亡节点的后节点为新的首节点。
若将亡节点存在后节点，则令其后节点的前指针指向将亡节点的前节点，否则将亡节点的前节点为新的尾节点。
销毁将亡节点。
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int DataType;
struct Node{
DataType data;
struct Node *pre, *next;
};
void init(struct Node** head)
{
*head = NULL;
}
int getSize(struct Node* head)
{
struct Node* p = head;
int count = 0;
while(p)
{
count ++;
p = p->next;
}
return count;
}
//找到指定位置 元素地址
struct Node* getptr(struct Node* head, int pos) {
struct Node *p = head;
if (p == 0 || pos == 0) {
return head;
}
int i = 0;
for(i = 0; p && i < pos; i++) {
p = p->next;
}
return p;
}
//指定位置 插入元素
bool insert(struct Node** head, int position, DataType d) {
if (position < 0 || position > getSize(*head)) {
return false;
}
//创建 节点
struct Node *node = (struct Node*)malloc(sizeof(struct Node));
node->data = d;
node->pre = NULL;
node->next = NULL;
//插入到第一个节点的前面
if (position == 0) {
node->next = *head;
if (*head != NULL)
(*head)->pre = node;
*head = node;
return true;
}
//插入到链表的中间
struct Node *p = getptr(*head, position - 1);
struct Node* r = p->next;
node->next = r;
r->pre = node;
p->next = node;
node->pre = p;
return true;
}
//删除指定位置元素
bool erases(struct Node** head, int pos) {
if (pos < 0 || pos >= getSize(*head))
return false;
//删除第一个结点
struct Node *p = *head;
if (pos == 0) {
*head = (*head)->next;
if (*head != NULL)
(*head)->pre = NULL;
free(p);
p = NULL;
return true;
}
//删除链表的中间结点
p = getptr(*head, pos - 1);
struct Node *q = p->next;
p->next = q->next;
q->next->pre = p;
free(q);
q = NULL;
return true;
}
//修改指定位置 元素
bool set(struct Node* head, int pos, DataType d) {
if (pos < 0 || pos >= getSize(head)) {
return false;
}
struct Node *p = getptr(head, pos);
p->data = d;
return true;
}
//清理 链表
void clears(struct Node* head) {
while (head) {
struct Node *p = head->next;
free(head);
head = p;
}
}
//打印
void print(struct Node* head) {
struct Node *p = head;
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
int main()
{
//头指针
struct Node *headList;
init(&headList);
insert(&headList, 0, 10);
insert(&headList, 0, 20);
insert(&headList, 0, 30);
insert(&headList, 2, 40);
insert(&headList, 2, 50);
insert(&headList, 0, 60);
insert(&headList, 0, 80);
print(headList);
erases(&headList, 1);
print(headList);
set(headList, 0, 100);
set(headList, 0, 110);
print(headList);
return 0;
}
输出结果：
80 60 30 20 50 40 10
80 30 20 50 40 10
110 30 20 50 40 10
3、双向线性链表总结
每个节点除了存放元素数据之外，还需要保存指向下一个节点的指针，即所谓后指针，以及指向前一个节点的指针，即所谓前指针。
链表首节点的前指针和尾节点的后指针俱为空指针。
五、双向循环链表
1、双向循环链表
参看：（C语言版）链表（四）——实现双向循环链表创建、插入、删除、释放内存等简单操作
#include <stdio.h>
#include <stdlib.h>
typedef struct Node
{
int data;
struct Node *pNext;
struct Node *pPre;
}NODE, *pNODE;
//创建双向循环链表
pNODE CreateDbCcLinkList(void);
//打印链表
void TraverseDbCcLinkList(pNODE pHead);
//判断链表是否为空
int IsEmptyDbCcLinkList(pNODE pHead);
//计算链表的长度
int GetLengthDbCcLinkList(pNODE pHead);
//向链表中插入节点
int InsertEleDbCcLinkList(pNODE pHead, int pos, int data);
//从链表中删除节点
int DeleteEleDbCcLinkList(pNODE pHead, int pos);
//删除整个链表，释放内存
void FreeMemory(pNODE *ppHead);
int main(void)
{
int flag = 0, length = 0;
int position = 0, value = 0;
pNODE head = NULL;
head = CreateDbCcLinkList();
flag = IsEmptyDbCcLinkList(head);
if (flag)
printf("双向循环链表为空！\n");
else
{
length = GetLengthDbCcLinkList(head);
printf("双向循环链表的长度为：%d\n", length);
TraverseDbCcLinkList(head);
}
printf("请输入要插入节点的位置和元素值(两个数用空格隔开)：");
scanf("%d %d", &position, &value);
flag = InsertEleDbCcLinkList(head, position, value);
if (flag)
{
printf("插入节点成功！\n");
TraverseDbCcLinkList(head);
}
else
printf("插入节点失败！\n");
flag = IsEmptyDbCcLinkList(head);
if (flag)
printf("双向循环链表为空，不能进行删除操作！\n");
else
{
printf("请输入要删除节点的位置：");
scanf("%d", &position);
flag = DeleteEleDbCcLinkList(head, position);
if (flag)
{
printf("删除节点成功！\n");
TraverseDbCcLinkList(head);
}
else
printf("删除节点失败！\n");
}
FreeMemory(&head);
if (NULL == head)
printf("已成功删除双向循环链表，释放内存完成！\n");
else
printf("删除双向循环链表失败，释放内存未完成！\n");
return 0;
}
//创建双向循环链表
pNODE CreateDbCcLinkList(void)
{
int i, length = 0, data = 0;
pNODE p_new = NULL, pTail = NULL;
pNODE pHead = (pNODE)malloc(sizeof(NODE));
if (NULL == pHead)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
pHead->data = 0;
pHead->pNext = pHead;
pHead->pPre = pHead;
pTail = pHead;
printf("请输入想要创建链表的长度：");
scanf("%d", &length);
for (i=1; i<length+1; i++)
{
p_new = (pNODE)malloc(sizeof(NODE));
if (NULL == p_new)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
printf("请输入第%d个节点元素值：", i);
scanf("%d", &data);
p_new->data = data;
p_new->pPre = pTail;
p_new->pNext = pHead;
pTail->pNext = p_new;
pHead->pPre = p_new;
pTail = p_new;
}
return pHead;
}
//打印链表
void TraverseDbCcLinkList(pNODE pHead)
{
pNODE pt = pHead->pNext;
printf("链表打印如：");
while (pt != pHead)
{
printf("%d ", pt->data);
pt = pt->pNext;
}
putchar('\n');
}
//判断链表是否为空
int IsEmptyDbCcLinkList(pNODE pHead)
{
pNODE pt = pHead->pNext;
if (pt == pHead)
return 1;
else
return 0;
}
//计算链表的长度
int GetLengthDbCcLinkList(pNODE pHead)
{
int length = 0;
pNODE pt = pHead->pNext;
while (pt != pHead)
{
length++;
pt = pt->pNext;
}
return length;
}
//向链表中插入节点
int InsertEleDbCcLinkList(pNODE pHead, int pos, int data)
{
pNODE p_new = NULL, pt = NULL;
if (pos > 0 && pos < GetLengthDbCcLinkList(pHead) + 2)
{
p_new = (pNODE)malloc(sizeof(NODE));
if (NULL == p_new)
{
printf("内存分配失败！\n");
exit(EXIT_FAILURE);
}
while (1)
{
pos--;
if (0 == pos)
break;
pHead = pHead->pNext;
}
p_new->data = data;
pt = pHead->pNext;
p_new->pNext = pt;
p_new->pPre = pHead;
pHead->pNext = p_new;
pt->pPre = p_new;
return 1;
}
else
return 0;
}
//从链表中删除节点
int DeleteEleDbCcLinkList(pNODE pHead, int pos)
{
pNODE pt = NULL;
if (pos > 0 && pos < GetLengthDbCcLinkList(pHead) + 1)
{
while (1)
{
pos--;
if (0 == pos)
break;
pHead = pHead->pNext;
}
pt = pHead->pNext->pNext;
free(pHead->pNext);
pHead->pNext = pt;
pt->pPre = pHead;
return 1;
}
else
return 0;
}
//删除整个链表，释放内存空间
void FreeMemory(pNODE *ppHead)
{
pNODE pt = NULL;
while (*ppHead != NULL)
{
pt = (*ppHead)->pNext->pNext;
if ((*ppHead)->pNext == *ppHead)
{
free(*ppHead);
*ppHead = NULL;
}
else
{
free((*ppHead)->pNext);
(*ppHead)->pNext = pt;
pt->pPre = *ppHead;
}
}
}
输出结果：
请输入想要创建链表的长度：5
请输入第1个节点元素值：1
请输入第2个节点元素值：2
请输入第3个节点元素值：3
请输入第4个节点元素值：4
请输入第5个节点元素值：5
双向循环链表的长度为：5
链表打印如：1 2 3 4 5
请输入要插入节点的位置和元素值(两个数用空格隔开)：2
6
插入节点成功！
链表打印如：1 6 2 3 4 5
请输入要删除节点的位置：2
删除节点成功！
链表打印如：1 2 3 4 5
已成功删除双向循环链表，释放内存完成！
2、双向循环链表
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
typedef int ElemType;
/* 线性表的双向链表存储结构 */
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
/* 双链循环线性表的基本操作(14个) */
Status InitList(DuLinkList *L)
{ /* 产生空的双向循环链表L */
*L=(DuLinkList)malloc(sizeof(DuLNode));
if(*L)
{
(*L)->next=(*L)->prior=*L;
return OK;
}
else
return OVERFLOW;
}
Status DestroyList(DuLinkList *L)
{ /* 操作结果：销毁双向循环链表L */
DuLinkList q,p=(*L)->next; /* p指向第一个结点 */
while(p!=*L) /* p没到表头 */
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
return OK;
}
Status ClearList(DuLinkList L) /* 不改变L */
{ /* 初始条件：L已存在。操作结果：将L重置为空表 */
DuLinkList q,p=L->next; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L; /* 头结点的两个指针域均指向自身 */
return OK;
}
Status ListEmpty(DuLinkList L)
{ /* 初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE */
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{ /* 初始条件：L已存在。操作结果：返回L中数据元素个数 */
int i=0;
DuLinkList p=L->next; /* p指向第一个结点 */
while(p!=L) /* p没到表头 */
{
i++;
p=p->next;
}
return i;
}
Status GetElem(DuLinkList L,int i,ElemType *e)
{ /* 当第i个元素存在时,其值赋给e并返回OK,否则返回ERROR */
int j=1; /* j为计数器 */
DuLinkList p=L->next; /* p指向第一个结点 */
while(p!=L&&j<i) /* 顺指针向后查找,直到p指向第i个元素或p指向头结点 */
{
p=p->next;
j++;
}
if(p==L||j>i) /* 第i个元素不存在 */
return ERROR;
*e=p->data; /* 取第i个元素 */
return OK;
}
int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{ /* 初始条件：L已存在，compare()是数据元素判定函数 */
/* 操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。 */
/* 若这样的数据元素不存在，则返回值为0 */
int i=0;
DuLinkList p=L->next; /* p指向第1个元素 */
while(p!=L)
{
i++;
if(compare(p->data,e)) /* 找到这样的数据元素 */
return i;
p=p->next;
}
return 0;
}
Status PriorElem(DuLinkList L,ElemType cur_e,ElemType *pre_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱， */
/* 否则操作失败，pre_e无定义 */
DuLinkList p=L->next->next; /* p指向第2个元素 */
while(p!=L) /* p没到表头 */
{
if(p->data==cur_e)
{
*pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status NextElem(DuLinkList L,ElemType cur_e,ElemType *next_e)
{ /* 操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继， */
/* 否则操作失败，next_e无定义 */
DuLinkList p=L->next->next; /* p指向第2个元素 */
while(p!=L) /* p没到表头 */
{
if(p->prior->data==cur_e)
{
*next_e=p->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
DuLinkList GetElemP(DuLinkList L,int i) /* 另加 */
{ /* 在双向链表L中返回第i个元素的位置指针(算法2.18、2.19要调用的函数) */
int j;
DuLinkList p=L;
for(j=1;j<=i;j++)
p=p->next;
return p;
}
Status ListInsert(DuLinkList L,int i,ElemType e) /* 改进算法2.18 */
{ /* 在带头结点的双链循环线性表L中第i个位置之前插入元素e，i的合法值为1≤i≤表长+1 */
DuLinkList p,s;
if(i<1||i>ListLength(L)+1) /* i值不合法 */
return ERROR;
p=GetElemP(L,i-1); /* 在L中确定第i-1个元素的位置指针p */
if(!p) /* p=NULL,即第i-1个元素不存在 */
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e; /* 在第i-1个元素之后插入 */
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
Status ListDelete(DuLinkList L,int i,ElemType *e) /* 算法2.19 */
{ /* 删除带头结点的双链循环线性表L的第i个元素,i的合法值为1≤i≤表长+1 */
DuLinkList p;
if(i<1||i>ListLength(L)) /* i值不合法 */
return ERROR;
p=GetElemP(L,i); /* 在L中确定第i个元素的位置指针p */
if(!p) /* p=NULL,即第i个元素不存在 */
return ERROR;
*e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
void visit(ElemType c)
{
printf("%d ",c);
}
void ListTraverse(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发,正序对每个数据元素调用函数visit() */
DuLinkList p=L->next; /* p指向头结点 */
while(p!=L)
{
visit(p->data);
p=p->next;
}
printf("\n");
}
void ListTraverseBack(DuLinkList L,void(*visit)(ElemType))
{ /* 由双链循环线性表L的头结点出发,逆序对每个数据元素调用函数visit()。另加 */
DuLinkList p=L->prior; /* p指向尾结点 */
while(p!=L)
{
visit(p->data);
p=p->prior;
}
printf("\n");
}
Status compare(ElemType c1,ElemType c2)
{
if(c1==c2)
return TRUE;
else
return FALSE;
}
int main(int argc, const char * argv[]) {
// insert code here...
DuLinkList L;
ElemType e;
int j;
Status i;
i = InitList(&L); /* 初始化单循环链表L */
printf("初始化双向循环链表L i=%d(1:初始化成功)\n", i);
i=ListEmpty(L);
printf("L是否空 i=%d(1:空 0:否)\n",i);
ListInsert(L, 1, 15);
ListInsert(L, 2, 25);
ListInsert(L, 3, 35);
ListInsert(L, 4, 45);
i=GetElem(L,1,&e);
j=ListLength(L);
printf("L中数据元素个数=%d,第1个元素的值为%d。\n",j,e);
printf("L中的数据元素依次为：");
ListTraverse(L,visit);
PriorElem(L,25,&e); /* 求元素5的前驱 */
printf("25前面的元素的值为%d。\n",e);
NextElem(L,35,&e); /* 求元素3的后继 */
printf("35后面的元素的值为%d。\n",e);
printf("L是否空 %d(1:空 0:否)\n",ListEmpty(L));
j=LocateElem(L,45,compare);
if(j)
printf("L的第%d个元素为45。\n",j);
else
printf("不存在值为45的元素\n");
//删除第二个元素
ListDelete(L, 2, &e);
printf("删除L的第2个元素：\n");
if(i)
{
printf("删除的元素值为%d,现在L中的数据元素依次为：",e);
ListTraverse(L,visit);
}
else
printf("删除不成功！\n");
j=ListLength(L);
printf("L中数据元素个数=%d\n",j);
ListTraverse(L,visit);
ListTraverseBack (L,visit);
printf("清空L：%d(1: 成功)\n",ClearList(L));
printf("清空L后，L是否空：%d(1:空 0:否)\n",ListEmpty(L));
printf("销毁L：%d(1: 成功)\n",DestroyList(&L));
return 0;
}
输出结果：
初始化双向循环链表L i=1(1:初始化成功)
L是否空 i=1(1:空 0:否)
L中数据元素个数=4,第1个元素的值为15。
L中的数据元素依次为：15 25 35 45
25前面的元素的值为15。
35后面的元素的值为45。
L是否空 0(1:空 0:否)
L的第4个元素为45。
删除L的第2个元素：
删除的元素值为25,现在L中的数据元素依次为：15 35 45
L中数据元素个数=3
15 35 45
45 35 15
清空L：1(1: 成功)
清空L后，L是否空：1(1:空 0:否)
销毁L：1(1: 成功)
3、双向循环链表总结
每个节点除了存放元素数据之外，还需要保存指向下一个节点的指针，即所谓后指针，以及指向前一个节点的指针，即所谓前指针。
链表首节点的前指针和尾节点的后指针分别指向链表的尾节点和首节点。
六、数组链表
这部分只做了解好了，使用数组链表效率不高。
1、数组链表
参看：用数组实现链表（C++）
参看：数组作链表
#include<iostream>
using namespace std;
class List{
private:
int maxSize;
int n;
int *list;
public:
List(int max);
~List(){delete []list;}
bool isEmpty(){return n==0;}
int length(){return n;}
int locate(int &x);//返回表中元素x的位置
bool retrieve(int k, int &x);//返回表中位置k，将之放入元素x
List& insert(int k,int x);//在位置k插入元素x
List& Delete(int k,int &x);//删除位置k的元素，将之存在x中]
void printList();
};
List::List(int max){
maxSize = max;
n = 0;
list = new int[maxSize];
}
int List::locate(int &x){
for(int i=0;i<n;i++)
if(list[i]==x) return i;
return -1;
}
bool List::retrieve(int k, int &x){
if(k<1||k>n) return false;
x = list[k];
return true;
}
List& List::insert(int k, int x){
//if(k<0||k>n) 此处应抛出异常
//if(n==maxSize) 此处应抛出异常
for(int i = n-1; i >= k; i++)
list[i+1] = list[i];
list[k] = x;
n++;
return *this;
}
List& List::Delete(int k, int &x){
if(retrieve(k, x)){
for(int i = k; i < n; i++)
list[i] = list[i+1];
n--;
return *this;
}
//else 在此抛出异常
}
void List::printList() {
for(int i=0; i < n; i++)
cout<<list[i]<<" ";
cout<<endl;
}
int main() {
List list(10);
list.insert(0,1);
list.insert(1,2);
list.insert(2,3);
int listLength = list.length();
list.printList();
cout<<"数组链表的长度为"<<listLength<<endl;
int delElement = 0;
list.Delete(1, delElement);
list.printList();
cout<<"删除元素后数组链表的长度为"<<list.length()<<" "
<<"删除的元素是"<<" "<<delElement<<endl;
return 0;
}
输出结果：
1 2 3
数组链表的长度为3
1 3
删除元素后数组链表的长度为2 删除的元素是 2
2、数组链表总结
（1）数组链表
链表中的每个元素都是数组，即由数组构成的链表
（2）链表数组
数组中的每个元素都是链表，即由链表构成的数组
（3）二维链表
链表中的每个元素都是链表，即由链表构成的链表
好博客就要一起分享哦！分享海报
此处可发布评论
评论（0）展开评论
暂无评论，快来写一下吧
展开评论
您可能感兴趣的博客
