文章目录
- 一、单链表
- 1.单链表的定义
- 1.1概念介绍
- 2.如何用代码来定义一个单链表
- *知识点
- 3.单链表的插入删除
- 未完待续...
一、单链表
1.单链表的定义
- 单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
1.1概念介绍
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。
2.如何用代码来定义一个单链表
struct LNode{ //定义单链表节点类型ElemType data; //每个节点存放一个数据元素struct LNode *next; //指针指向下一个节点
};
struct Lnode *p = (struct LNode *)malloc(sizeof(struct LNode));
//添加一个新的节点,在内存中申请一个节点所需空间,并用指针p指向这个节点
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,指向单链表的第一个节点
LNode *L; //声明一个指向单链表第一个节点的指针;
LinkList L; //声明一个指向单链表第一个节点的指针;
typedef struct LNode{ElemType data;struct LNode *next;
}LNode,*LinkList;
LNode * GetElem(LinkList L,int i){itn j = 1;LNode *p = L -> next;if(i == 0)return L;if(i < 1)return NULL;while(p != NULL && j < i){p = p -> next;j++;
}
return p;}
- 不带头结点和带头结点他们之间的区别:
*知识点
本章知识点回顾:
3.单链表的插入删除
单链表的常用操作:
- 1.按位序插入(带头结点)
Listlnsert(&L,i,e):插入操作。在表中的第i个位置上插入指定元素e。
代码实现:
bool ListInsert(LinkList &L, int i, ElemType e){if(i< 1)return false;Lnode *p; //指针p指向当前扫描到的节点int j = 0; //当前p指向的事第几个节点p = L; //L指向头结点 头结点是第0个节点(不存在数据)while(p != NULL && j < i - 1){ //循环找到第i-1个节点p = p -> next;j++;}if(p == NULL) //i值不合法return false;LNode *s = (LNode *)malloc(sizeof(LNode));s -> data = e;s -> next = p -> next;p -> next = s; //将节点s链接到p后return true; //插入成功
}