<>2.5 链式结构的表示和实现

* 头指针,头结点和首元结点:

* 头结点的好处:①便于首元结点的处理;②便于空表和非空表的处理;
* 链式存储的特点:①结点在存储器中的位置是任意的,即逻辑上相邻的数据元素在物理上不一定相邻;②访问时只能通过头指针进入链表,并通过每个结点的指针域
依次向后顺序扫描其余结点,所以寻找第一个结点和最后一个结点所花费的时间不等;

* 带头结点的单链表

<>2.5.1 单链表的表示

* 单链表的存储结构: typedef struct { int num; char name[20]; int score; }ElemType;
typedef struct LNode//声明结点的类型和指向结点的指针类型 { ElemType data;//结点的数据域 struct LNode*
next;//结点的指针域 }LNode, * LinkList;//LinkList 为指向结构体Lnode的指针类型 /*解释:定义了一个结构体类型
利用typedef重新起名字为Lnode 然后定义指针LinkList指向Lnode*/ /*定义结点指针p:Lnode *p; <==> LinkList
P;*/
<>2.5.2 单链表的实现

[ 算法2.6 ] 单链表的初始化(带头结点的单链表)
Status InitList(LinkList& L) { L = (LinkList)malloc(sizeof(LNode)); /*L=new
LNode;*/ L->next = NULL; return OK; }
[ 补充算法 1 ] 判断链表是否为空
int ListEmpty(LinkList L) { if (L->next)//非空 { return 0; } else { return 1; } }
[ 补充算法 2 ] 单链表的销毁
[ 算法思路 ]从头指针开始,依次释放所有结点;

Status DestroyList(LinkList& L) { LNode* p;//LinkList p; while (L) { p = L; L =
L->next; free(p); } return 0; }
[ 补充算法 3 ] 清空链表(链表仍然存在,但链表中无元素,成为空链表)
[ 算法思路 ]依次释放所有结点,并将头结点的指针域设置为空;

Status ClearList(LinkList& L) { LNode* p, * q; p = L->next; while (p) { q = p->
next; free(p); p = q; } L->next = NULL;//头结点的指针域为空 return OK; }
[ 算法补充 4 ] 求单链表的表长
[ 算法思路 ]从首元结点开始,依次计数所有结点;
int ListLength(LinkList L) { int count = 0;//链表长度 LNode* p; p = L->next; while
(p) { count++; p = p->next; } return count; }
[ 算法 2.7 ] 查找第 i 个元素
Status GetElem(LinkList L, int i, ElemType& e) { LNode* p; int j = 1; p = L->
next; while (p && j < i) { p = p->next; j++; } if (!p || j > i) { return ERROR;
} e = p->data; return OK; }
[ 算法 2.8 ] 按值查找
//O(n) LNode* LocateElem(LinkList L, ElemType e)/*返回地址*/ { LNode* p; p = L->
next; while (p && p->data != e) { p = p->next; } return p; } int LocateElem(
LinkList L, ElemType e)/*返回元素的下标*/ { LNode* p; int j = 1; p = L->next; while (p
&& p->data != e) { p = p->next; j++; } if (p) { return j; } else { return 0; } }
[ 算法 2.9 ] 插入(在第 i 个结点前插入值为 e 的新结点)
Status ListInsert(LinkList& L, int i, ElemType e) { LNode *s, *p; int j = 0; s
->data = e; p = L; while (p && j < i-1)//寻找i-1个结点 p指向i-1结点 { p = p->next; j++; }
if (!p || j > i-1) { return ERROR; } s->next = p->next; p->next = s; return OK;
}
[ 算法 2.10 ] 删除(删除第 i 个结点)
Status ListDelete(LinkList& L, int i,ElemType &e) { LNode* p, * q; int j = 0; p
= L; while (p && j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) { return
ERROR; } q = p->next; p->next = q->next;//修改指针 e = q->data; free(q); return OK;
}
[ 算法 2.11 ] 建立单链表—头插法(元素插入在链表头部 )

/*倒位序插入n个元素的值*/ void CreateList(LinkList& L, int n) { LNode* p; int i; for (i =
n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &p->data); p
->next = L->next; L->next = p; } }
[ 算法 2.12 ] 建立单链表–尾插法(元素插入在链表尾部)
/*正位序输入n个元素的值*/ void CreateList(LinkList& L, int n) { LNode* p, *r; int i; r =
L; for (i = n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p
->data); p->next = NULL; r->next = p; r = p;//尾指针指向新结点 } }
<>2.5.3 循环链表

循环链表:是一种 头尾相接的链表(即:表中最后一个结点的指针域指向头结点,整个链表形成一个环);

[ 算法 2.13 ] 循环链表的建立
void CreateList(LinkList& L, int n) { LNode* p, *r; int i; r = L; for (i = n; i
> 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d",&p->data); p->next =
NULL; r->next = p; r = p; } r->next = L; }
[ 算法 2.14 ] 带尾指针循环链表的合并
LinkList Connect(LinkList Ta, LinkList Tb)//假设Ta,Tb都是非空的单循环链表 { LNode p; p = (
LinkList)malloc(sizeof(LNode)); p = Ta->next; Ta->next = Tb->next->next; free(Tb
->next); Tb->next = p;//修改指针 return Tb; }
<>线性表的链式表示和实现完整参考代码
/*先看主函数了解 2021.1.17*/ #include<stdio.h> #include<stdlib.h> #define ERROR 0 #
define OK 1 typedef int Status; typedef int ElemType; typedef struct LNode {
ElemType data; struct LNode* next; }LNode, * LinkList; Status InitList(LinkList&
L) { L = (LinkList)malloc(sizeof(LNode)); L->next = NULL; return OK; } /* void
CreateList(LinkList& L, int n) { LNode* p; for (int i = n; i > 0; i--) { p =
(LNode *)malloc(sizeof(LNode)); scanf("%d", &p->data); p->next = L->next;
L->next = p; } } */ void CreateList(LinkList& L, int n) { LNode* p, * r; r = L;
for (int i = n; i > 0; i--) { p = (LinkList)malloc(sizeof(LNode)); scanf("%d", &
p->data); p->next = NULL; r->next = p; r = p; } } int ListLength(LinkList L) {
int count = 0;//用于计数 LNode* p; p = L->next; while (p) { count++; p = p->next; }
return count; } Status GetElem(LinkList L, int i, ElemType& e) { int j = 1;
LNode* p; p = L->next; while (p && j < i) { p = p->next; j++; } if (!p || j > i)
{ return ERROR; } e = p->data; return OK; } int LocateElem(LinkList L, ElemType
e) { LNode* p; int j = 1; p = L->next; while (p && p->data != e) { p = p->next;
j++; } if (p) { return j; } else { return ERROR; } } Status ListInsert(LinkList&
L, int i, ElemType e) { LNode* s, * p; s = (LinkList)malloc(sizeof(LNode)); int
j= 0; p = L; s->data = e; while(p && j < i - 1) { p = p->next; j++; } if (!p ||
j> i - 1) { return ERROR; } s->next = p->next; p->next = s; return OK; } void
print(LinkList L) { LNode* p; p = L->next; while (p) { printf("%d ", p->data); p
= p->next; } printf("\n"); } Status ListDelete(LinkList& L, int i, ElemType& e)
{ LNode* p, * q; p = L; q = (LinkList)malloc(sizeof(LNode)); int j = 0; while (p
&& j < i - 1) { p = p->next; j++; } if (!p || j > i - 1) { return ERROR; } q = p
->next; e = q->data; p->next = q->next; free(q); return OK; } void ListEmpty(
LinkList L) { if (L->next) { printf("链表非空\n"); } else { printf("链表为空\n"); } }
StatusClearList(LinkList& L) { LNode* p, * q; p = L->next; while (p) { q = p->
next; free(p); p = q; } L->next = NULL; return OK; } Status DestroyList(LinkList
& L) { LNode* p; while (L) { p = L; L = L->next; free(p); } printf("销毁完毕\n");
return OK; } int main() { int n; int i; LinkList L; ElemType e; InitList(L);
/*带头结点的链表初始化*/ printf("输入元素的个数:"); scanf("%d", &n);//要输入的元素个数 printf("输入元素:");
//CreateList(L, n);/*头插法输入元素-倒叙状态*/ CreateList(L, n);/*尾插法输入元素-顺序*/ printf(
"单链表的长度:%d\n", ListLength(L));/*求单链表的表长*/ printf("输入查找的i位置:"); scanf("%d", &i);
GetElem(L, i, e);/*查找第i个元素*/ printf("查找的第i个元素是:%d\n", e); printf("输入要查找得值:");
scanf("%d", &e); printf("查找到的元素的下标为:%d\n", LocateElem(L, e));/*按值查找*/ printf(
"插入的位置:"); scanf("%d",&i); printf("要插入的元素:"); scanf("%d", &e); ListInsert(L, i,
e);/*第i个位置之前插入元素e*/ printf("插入元素后的链表:"); print(L);//输出链表 printf("输入删除元素的位置:");
scanf("%d", &i); ListDelete(L, i, e);/*删除第i个元素*/ printf("删除的元素%d\n",e); printf(
"删除元素后的链表:"); print(L); ListEmpty(L);/*判断链表是否为空*/ ClearList(L);/*清空单链表*/ printf(
"清空单链表后:"); ListEmpty(L);/*判断链表是否为空*/ DestroyList(L);/*销毁单链表*/ return 0; }

技术
下载桌面版
GitHub
百度网盘(提取码:draw)
Gitee
云服务器优惠
阿里云优惠券
腾讯云优惠券
华为云优惠券
站点信息
问题反馈
邮箱:ixiaoyang8@qq.com
QQ群:766591547
关注微信