链表（单链表、双链表、循环链表、静态链表）入门
目录单链表
什么是单链表？
代码界说单链表
初始化单链表
单链表的插入与删除
双链表
循环链表
静态链表
界说
静态链表的插入
单链表
什么是单链表？
顺序表中每个结点只存放数据元素，而单链表中每个节点除了要存放数据元素之外，还要存储指向下一个结点的指针。
单链表与顺序表相比，优点是不要求大片的一连空间，改变容量方便，缺点是不可随机存取，要耗费一定空间存放指针。
代码界说单链表
两种方法一样
typedef struct LNode {//定义单链表结点类型
ElemType data;//每个节点存放一个数据元素
struct LNode* next;//指针指向下一个节点
}LNode, * LinkList;
struct LNode {
ElemType data;
struct LNode* next;
};
typedef struct LNode LNode;
typedef struct LNode* LinkList; 要表示一个单链表时，只需要声明一个头指针L，指向单链表的第一个结点
初始化单链表
不带头结点
typedef struct LNode {//定义单链表结点类型
ElemType data;//每个节点存放一个数据元素
struct LNode* next;//指针指向下一个节点
}LNode, * LinkList;
bool InitList(LinkList& L) { L = NULL;//空表，暂时没有任何节点 return true;}void test() { LinkList L;//声明一个指向单链表的指针 InitList(L);//初始化一个空表} 带头结点
//定义单链表结点类型
typedef struct LNode {
ElemType data;
struct LNode* next;
}LNode, * LinkList;
//初始化单链表（带头结点）
bool InitList(LinkList& L) {
L = (LNode*)malloc(sizeof(LNode));
if (L == NULL)return false;
L->next = NULL;
return true;
} 单链表的插入与删除
插入
Status ListInsert(LinkList* L, int i, ElemType e) {
int j;
LinkList p, s;
p = *L;
j = 1;
//寻找第i个结点
while (p && j < i) {
p = p->next;
++j;
}
if (!p || j > i)return ERROR;
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
} 删除
Status ListInsert(LinkList* L, int i, ElemType *e) {
int j;
LinkList p, q;
p = *L;
j = 1;
while (p->next && j < i) {//遍历寻找第i个元素
p = p->next;
++j;
}
if (!(p->next) || j > i)return ERROR;
q = p->next;
p->next = q->next;
*e = q->data;
free(q);
return OK;
}
双链表
单链表的每个结点都有指向后继的指针域，如今再加上一个指向前驱的指针域，这样的链表称为双链表。
typedef struct DulNode {
ElemType data;
struct DuLNode* prior;//直接前驱指针
struct DuLNode* next;//直接后继指针
}DulNode, * DuLinkList; 循环链表
将单链表中终端结点的指针端由空指针改为指向头结点,使整个单链表形成—个环，此时这个环叫循环链表。
在循环的判定上，单链表是判定p->next是否为空，循环链表是判定p->next是否等于头节点。
用尾指针来表示循环链表时，查找开始节点和终端节点都很方便。
如归并两个循环链表，它们的尾指针分别是rearA和rearB
p = rearA->next;//保存A表的头节点
rearA->next = rearB->next->next;//将本是指向B表的第一个节点（不是头节点）赋值给rearA->next
q = rearB->next;
rearB->next = p;
free(q); 静态链表
界说
用数组代替指针描述单链表，这种链表叫静态链表。
为了方便插入数据，通常会把数组创建得大一些。
#define MAXSIZE 1000
//静态链表
typedef struct {
ElemType date;
int cur;
}Component, StaticLinkList; 静态链表的插入
在动态链表中，结点的申请和开释分别借用malloc()和free()两个函数来实现。在静态链表中，我们需要自己实现这两个函数。
//若备用空间链表非空，则返回分配的结点下标，否则返回0
int Malloc_SSL(StaticLinkList space) {
int i = space.cur;//当前数组第一个元素的cur存的值就是返回的第一个备用空间的下标
if (space.cur) {//由于要拿出一个分量来使用，所以要把下一个分量用来做备用
space.cur = space.cur;
}
return i;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]