程序构思:
单链表的建立
(1) 先建立头结点head，将头结点的指针域置为空。
(2) 新建一个指向头结点的指针m，即Node *m = head;（首端插入方式不需要该步骤）。
(3) 新建一个结点p，把此新结点链接到单链表的尾端（p->next设为空）或者始端。
1⃣️首端插入方式
①p->next指向头结点指向的下一个结点head->next。
②head->next指向p。
2⃣️尾端插入方式。
①m->next指向p，即m->next = p;
②把指针p赋值给m，也就是说每次m都要最终指向新插入的结点。m = p;
单链表的插入
(1) 新建一个结点p，指定插入位置。
(2) 从单链表开始查找结点位置。
①找到该位置，则p->next指向当前位置的下一个结点，当前位置结点指向新建结点p。
②没有找到该位置，插入操作失败。
单链表的删除
(1) 指定删除位置。
(2) 链表头开始找到结点位置。
①找到该位置，则删除该位置的结点。
②没有找到该位置，删除操作失败。
示例代码
#include <iostream>
#include <stdlib.h>
#include <cstdio>
using namespace std;
typedef int ElementType; //指定单链表中数据类型
//单链表存储结构定义
typedef struct Node
{
ElementType data; //数据域
struct Node *next; //指针域
}*LinkList;
#pragma mark - 建立一个空线性表/单链表(方法一)
/****----------------------------------------------****/
//单链表建立方法一(函数用返回值得到表头指针)
//函数名: CreateOne(int n)
//参数: (传入)int n, 传入线性表结点数量
//作用: 建立一个空线性表
//返回值:Node *型返回结构体指针,即得到建立的线性表头指针
/****---------------------------------------------****/
Node* CreateOne(int n)
{
int i;
Node *head; //定义头结点指针
Node *p; //定义新结点指针
//建立带头结点的线性链表
head = (Node*)malloc(sizeof(Node));
head->next = NULL;
cout << "Please input the data for LinkList Nodes:" << endl;
/** 该链表创建并初始化采用的是从表尾插入n个元素,比如如果输入的是:1 2 3,那么输出链表时会输出3 2 1 */
/*
for (i = n; i > 0; i--) {
p = (Node*)malloc(sizeof(Node)); //为新结点申请空间,即创建一个新结点
scanf("%d", &p->data); //新结点赋值
//新结点插入到表头
p->next = head->next;
head->next = p;
}
*/
/** 该链表创建并初始化采用的是从表头插入n个元素,比如输入的是:1 2 3, 那么输出的顺序也是会: 1 2 3 */
Node *tempNode = head;
for (i = n; i > 0; i--) {
p = (Node*)malloc(sizeof(Node)); //为新结点申请空间,即创建一个新结点
scanf("%d", &p->data); //新结点赋值
//新结点插入到表尾
tempNode->next = p;
tempNode = p;
}
tempNode->next = NULL;
return head; //返回头结点指针,即可以得到单链表的地址
}
#pragma mark - 建立一个空线性表/单链表(方法二)
/****----------------------------------------------****/
//单链表建立方法二(函数无返回值)
//函数名: CreateTwo(Node* head, int n)
//参数: (传入)Node* head传入一个链表指针
// (传入)int n,传入线性表结点数量
//作用: 建立一个空线性表
//返回值: 无
/****---------------------------------------------****/
void CreateTwo(Node *head, int n)
{
int i;
Node *p; //定义新结点指针
//建立带头结点的线性链表
head = (LinkList)malloc(sizeof(Node));
head->next = NULL;
cout << "Please input the data for LinkList Nodes:" << endl;
for (i = n; i > 0; i--) {
p = (Node*)malloc(sizeof(Node)); //为新结点申请空间,即创建一新结点
scanf("%d", &p->data); //为新结点赋值
//新结点插入到表头
p->next = head->next;
head->next = p;
}
}
#pragma mark - 向单链表中插入一个元素
/****----------------------------------------------****/
//函数名: InsertNode(Node *L, int i, ELementType e)
//参数: (传入)Node *L,传入线性表头指针L
// (传入)int i插入位置
// (传入)ELementType e插入元素
//作用: 线性表中插入一个元素
//返回值: int型,返回1表示操作成功,0表示失败
/****---------------------------------------------****/
int InsertNode(Node *L, int i, ElementType e)
{
Node *p = L; //定义一个指向第一个结点的指针
int j = 0;
//顺指针向后查找, 直到p指向第一个结点
while (p && j < i) {
p = p->next;
j++;
}
//插入位置合法性判断
if (!p || j > i) {
cout << "Error! The location is illegal!" << endl;
return 0;
}
Node *s;
s = (Node*)malloc(sizeof(Node)); //建立新结点
s->data = e; //新结点赋值
//插入结点
s->next = p->next;
p->next = s;
return 1;
}
#pragma mark - 删除单链表中的一个元素
/****----------------------------------------------****/
//函数名: DeleteNode(LinkList &L, int i, ELementType &e)
//参数: (传入)LinkList &L,线性表头指针L的地址
// (传入)int i删除位置
// (传出)ElementType &e 存储删除节点元素的值
//作用: 线性表中删除一个元素
//返回值: ElementType型返回删除结点元素的值
/****---------------------------------------------****/
ElementType DeleteNode(LinkList &L, int i, int &e)
{
Node *p;
p = L; //定义一个指向第i个结点的指针p
Node *q; //暂时存放待删除结点
int j = 0;
//顺指针向后查找,直到p指向第i个结点
while (p->next && j < i) {
p = p->next;
j++;
}
//删除位置合法性判断
if (!p || j > i) {
cout << "element is not exist!";
return 0;
}
q = p->next;
p->next = q->next; //删除第i个结点
e = q->data;
free(q);
return e; //返回删除结点元素的值
}
#pragma mark - 显示线性表中的所有元素
/****----------------------------------------------****/
//函数名: DisplayList(LinkList &L)
//参数: (传入)LinkList &L,线性表头指针L的地址
//作用: 显示线性表中所有元素
//返回值: 无
/****---------------------------------------------****/
void DisplayList(LinkList &L)
{
Node *p;
p = L->next; //定义一个指向表头结点的指针p
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("
");
}
#pragma mark - 主函数
int main(int argc, const char * argv[]) {
Node *L1;
int NodeNum;
printf("Please input the Init LinkNode Number:
");
scanf("%d", &NodeNum);
L1 = CreateOne(NodeNum);
//Node *L2;
//CreateTwo(L2, NodeNum); //也可以这样生成L2链表
//输出当前链表内容
printf("the current L1 is:");
DisplayList(L1);
//调用
int result; //为了判断调用成功与否,可以定义result以备检查
result = InsertNode(L1, 3, 88);
if (result) {
printf("success to insert!
");
}
ElementType deleteNumber;
DeleteNode(L1, 0, deleteNumber);
printf("被删除的元素为: %d
", deleteNumber);
//输出当前链表的内容
printf("the curent L1 is:");
DisplayList(L1);
return 0;
}