目录
前言
1.链表的定义
2.单链表
1.单链表的定义
2.单链表初始化
3.单链表的销毁
4.完整代码
前言
记录下链表的表示和实现。
1.链表的定义
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。线性链表的数据元素除了存储本身存储的信息之外,还保存下一个数据元素的地址。其中存储数据元素信息的域称为数据域,存储直接后继存储位置的域称为指针域名。
2.单链表
1.单链表的定义
#pragma mark -- 定义
// 定义节点结构
typedef struct Node {
int data; // 节点数据
Node* next; // 指向下一个节点的指针
}LNode,*LinkList;
2.单链表初始化
#pragma mark -- 链表初始化
int initLinkList(LinkList &linkList){
linkList = (LinkList) malloc(sizeof(LNode));
linkList->next = nullptr;
return 1;
}
3.单链表的销毁
#pragma mark -- 单链表的销毁
void destroyLinkList(LinkList &head){
free(head);
}
4.单链表插入操作
#pragma mark -- 头结点插入
/// 单链表的插入操作
/// - Parameters:
/// - head: 要操作的单链表
/// - i: 插入的位置
/// - element: 要插入的元素
int insertLinkList(LinkList&head,int i,int element){
LinkList p;
p=head;
int j = 0;
while (p->next && j<i - 1) {
p = p->next;
j++;
}
if (p&&j>i) {
return 0;
}
LinkList q = (LinkList) malloc(sizeof(LNode));//生成新节点
q -> data = element;
q->next = p->next;
p->next = q;
return 1;
}
4.完整代码
#include <iostream>
using namespace::std;
#pragma mark -- 定义
// 定义节点结构
typedef struct Node {
int data; // 节点数据
Node* next; // 指向下一个节点的指针
}LNode,*LinkList;
#pragma mark -- 链表初始化
int initLinkList(LinkList &linkList){
linkList = (LinkList) malloc(sizeof(LNode));
linkList->next = nullptr;
return 1;
}
#pragma mark -- 头结点插入
/// 单链表的插入操作
/// - Parameters:
/// - head: 要操作的单链表
/// - i: 插入的位置
/// - element: 要插入的元素
int insertLinkList(LinkList&head,int i,int element){
LinkList p;
p=head;
int j = 0;
while (p->next && j<i - 1) {
p = p->next;
j++;
}
if (p&&j>i) {
return 0;
}
LinkList q = (LinkList) malloc(sizeof(LNode));//生成新节点
q -> data = element;
q->next = p->next;
p->next = q;
return 1;
}
#pragma mark -- 单链表删除操作
int deleteLinkList(LinkList &head,int i){
LinkList p = head;
int j = 0;
while (p && j < i- 1) {//找到前置节点
p = p->next;
++j;
}
if (j >= i-1 ||(p->next)) {
return 0;
}
LinkList q = p->next;
p->next = q->next;
free(q);
return 1;
}
#pragma mark -- 创建测试的数据
int createLinkList(LinkList& linkList,int values[],int size){
LinkList newNode = (LinkList)malloc(sizeof(LNode));//头节点
newNode->next = nullptr;//创建头节点
newNode->data = 0;
LinkList p = linkList;//此时头节点为空指针
p->next = newNode;
for (int j = 0; j < size; j++) {
LinkList newNode = (LinkList)malloc(sizeof(LNode));//生成一个新节点
newNode->data = values[j];
newNode->next = nullptr;
p->next = newNode;
p= newNode;
}
return 1;
}
#pragma mark -- 打印
void printLinkList(LinkList &head){
cout<<"**********单链表打印开始**********"<<endl;
LinkList p = head->next;
while (p!=nullptr) {
cout<<p->data<<"\t";
p = p->next;
}
cout<<endl;
cout<<"**********单链表打印结束**********"<<endl;
}
int main() {
int values[] = {1, 2, 3, 4, 5};
int size = sizeof(values) / sizeof(values[0]);
LinkList linkList;
cout<<endl;
if (initLinkList(linkList)) {
// cout<<"单链表初始化成功"<<endl;
if (createLinkList(linkList, values, size)) {
// cout<<"测试的单链表创建成功"<<endl;
if (insertLinkList(linkList, 6, 11)) {
printLinkList(linkList);
if (deleteLinkList(linkList,7)) {
cout<<"测试的单链表删除成功"<<endl;
}
}
printLinkList(linkList);
}
}else{
cout<<"单链表初始化失败"<<endl;
}
return 0;
}