数据结构与算法笔记第2章 线性表 链式表示

<>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; }

• « 上一篇：崮德好文连载 - 活该你是工程师（个人如何成长?）
• » 下一篇：比特币站上5.2万美元 美团CEO王兴：理论上中本聪已经是世界首富了