C++单链表创建、插入和删除
1.头节点插入和删除结果
2.中间节点插入和删除结果
3.尾结点插入和删除结果
C++单链表（带头结点）
总结归纳
代码实现
C++单链表创建、插入和删除这里仅提供一种思路。
#include <iostream>
#include <stdio.h>
#include <string>
#include <conio.h>
/**
* cstdio是将stdio.h的内容用C++头文件的形式表示出来。
*stdio.h是C标准函数库中的头文件，即：standard buffered input&output。
*提供基本的文字的输入输出流操作（包括屏幕和文件等）。
*/
/**
*conio是Console Input/Output（控制台输入输出）的简写，其中定义了通过控制台进行数据输入和数据输出的函数，
*主要是一些用户通过按键盘产生的对应操作，比如getch()()函数等等。
*/
using namespace std;
struct node
{
int data;
node *next;
};
typedef struct node node, *list;
// 创建单链表
node *creat()
{
node *head, *p;
head = new node;
p = head;
int x, cycle = 1;
while (cycle)
{
cout << "Please input the data for single linker : ";
cin >> x;
if (x != 0)
{
node *s = new node;
s->data = x;
cout << "Input data : " << x << endl;
p->next = s;
p = s;
}
else
{
cycle = 0;
cout << "Input done! " << endl;
}
}
head = head->next;
p->next = NULL;
//cout << "\nFirst data of single linker is " << head->data << endl;
return head;
}
// 单链表测长
int length(node *head)
{
int n = 0;
node *p = head;
while (p != NULL)
{
p = p->next;
n++;
}
return n;
}
// 单链表打印
void printL(node *head)
{
node *p = head;
while (p != NULL)
{
cout << "Single Linker data is " << p->data << endl;
p = p->next;
}
}
// 单链表插入
node *insert(node *head, int num)
{
node *p0, *p1, *p2;
p1 = head;
p2 = new node;
p0 = new node; // 插入节点
p0->data = num;// 插入数据
while (p0->data > p1->data && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;// p0,p1和p2位置: p2->p1->p0
}
if (p0->data <= p1->data)
{
if (p1 == head)
{// 头部前段插入 p0和p1位置: p0->p1->...
head = p0;
p0->next = p1;
}
else
{// 插入中间节点 p0,p1和p2位置: p2-> p0 -> p1
p2->next = p0;
p0->next = p1;
}
}
else
{ // 尾部插入节点 p0,p1和p2位置: p2->p1->p0->NULL
p1->next = p0;
p0->next = NULL;
}
return head;
}
// 单链表删除
node *del(node *head, int num)
{
node *p1, *p2;
p2 = new node;
p1 = head;
while (num != p1->data && p1->next != NULL)
{
p2 = p1;
p1 = p1->next;// p1和p2位置: p2->p1
}
if (num == p1->data)
{
if (p1 == head)// 删除头节点
{
head = p1->next;
delete p1;
}
else
{
p2->next = p1->next;
delete p1;
}
}
else
{
cout << num << " could not been found in the current single linker!" << endl;
}
return head;
}
//=============插入排序====================
node *insertSort( node *head )
{
node *p1, *prep1, *p2, *prep2, *temp;
prep1 = head->next;
p1 = prep1->next;
//prep1和p1是否需要手动后移
bool flag;
while (p1 != NULL)
{
flag = true;
temp = p1;
//由于是单向链表，所以只能从头部开始检索
for (prep2 = head, p2 = head->next; p2 != p1; prep2 = prep2->next, p2 = p2->next)
{
//发现第一个较大值
if (p2->data > p1->data)
{
p1 = p1->next;
prep1->next = p1;
prep2->next = temp;
temp->next = p2;
flag = false;
break;
}
}
//手动后移prep1和p1
if (flag)
{
prep1 = prep1->next;
p1 = p1->next;
}
}
return head;
}
int main()
{
cout << "***创建单链表***" << endl;
node *head = creat();
cout << endl;
cout << "***计算链表长***" << endl;
int n = length(head);
cout << "The length of input single linker is " << n << "." << endl;
cout << endl;
cout << "***打印单链表***" << endl;
printL(head);
cout << endl;
cout << "****插入节点****" << endl;
cout << "Please input the data for inserting operate : ";
int inData;
cin >> inData;
head = insert(head, inData);
printL(head);
cout << endl;
cout << "****删除节点****" << endl;
cout << "Please input the data for deleting operate : ";
int outData;
cin >> outData;
head = del(head, outData);
printL(head);
cout << endl;
cout << "****进行排序****" << endl;
//第一位地址可以存放指示器，从第二位开始保存数据
node *mylist = new node[sizeof(node)];
mylist->data = 0;
mylist->next = NULL;
int len = length(head);
int i = 0;
node * cur = mylist;
node *headcopy = head;
while (len--)
{
//node * newNode = (node *)malloc(sizeof(node));
node *newNode = new node[sizeof(node)];
newNode->data = headcopy->data;
newNode->next = NULL;
cur->next = newNode;
cur = cur->next;
headcopy=headcopy->next;
}
head = insertSort(mylist);
head = del(head, 0);
printL(head);
return 0;
}
1.头节点插入和删除结果
头结点可以没有，头指针必须有。访问整个链表，是用过遍历头指针来进行的。
这里没有特别的设置一个头指针，因为当指针指向整个链表 L 时，该指针的实现效果就是头指针。
关于函数中引用的问题，实际上对于带头结点的绝大部分操作，是不需要引用的，因为对于链表的任何操作，传入的实际上都是头指针（头结点），通过头指针的遍历访问后继结点。所以，无论是插入删除还是修改，都不涉及头指针的改变。但如果是不带头指针的单链表操作，就需要添加引用，因为当插入或删除第一个位置的元素时，会涉及头指针的修改，此时的头指针就是链表的第一个元素。
不带头结点的单链表，即单链表的第一个结点就存储数据，头指针也指向第一个结点；带头结点的单链表，第一个结点是头结点，不存储数据，从头结点的 next 开始存储，头指针可以从头结点的 next 开始遍历。
对于结点的前插操作，找到对应位置的结点，设新结点为该节点的后继结点，将该结点的 data 后移至新结点的 data，以此来模拟结点的后移，并且时间复杂度为 O(1)，我愿称之为“偷天换日”。
如果采用尾插法创建单链表，可以设置一个尾指针，指向单链表末尾，这样就不用每次都通过遍历找到最后一个结点，但每插入一个都要更新尾指针。这样的时间复杂度为O(1)。
在 DeleteNode 函数中（删除指定结点），存在一处 bug ，当删除结点为最后一个结点时，由于该结点没有后继结点，该函数会报错，初步认为只能通过 DeleteNextLNode函数（删除p结点的后继结点）来实现删除最后一个结点的操作。
大多数情况下，单链表的查询、插入、删除的平均时间复杂度都是O(n)，因为要遍历头结点开始查找。但如果对指定结点进行插入和删除，则时间复杂度为O(1)，因为不需要再通过遍历找到指定的结点。要具体分析。
如果不带头结点的单链表，则对表头的操作（插入和删除）要特殊处理，例如 List_HeadInsert（头插法创建单链表）、ListInsert（按位序插入）。每次插入后都要更新头指针，而对于带头结点的单链表，它的头指针指向永远是头结点，只需要修改头结点的后继就可以完成插入。
代码实现#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
// 单链表结点
struct LNode {
int data; // 数据域
LNode *next; // 指针域
};
typedef LNode LNode; // LNode表示单链表的一个结点
typedef LNode *LinkList; // LinkList表示一个单链表
// 初始化单链表
void InitList(LinkList &L) {
L = new LNode;
// L = (LNode *)malloc(sizeof(LNode));
L->next = NULL;
}
// 判断单链表是否为空
bool Empty(LinkList &L) {
if (L->next == NULL) {
return true;
} else {
return false;
}
}
// 获取单链表长度
int GetLength(LinkList &L) {
LNode *p = L->next;
int length = 0;
while (p != NULL) {
p = p->next;
length++;
}
return length;
}
// 按位查找：查找第i个结点
LNode *GetElem(LinkList &L, int i) {
if (i < 0) {
return NULL; // i值不合法
}
LNode *p = L;
int j = 0;
while (p != NULL && j < i) {
p = p->next;
j++;
}
return p;
}
// 按值查找：查找数据域为e的结点
LNode *GetLNode(LinkList &L, int e) {
LNode *p = L->next;
while (p != NULL && p->data != e) {
p = p->next;
}
return p;
}
// 头插法建立单链表
LinkList List_HeadInsert(LinkList &L) {
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->data = e;
s->next = L->next;
L->next = s;
cin >> e;
}
return L;
}
// 尾插法建立单链表
LinkList List_TailInsert(LinkList &L) {
LNode *r = L; // r为尾指针
int e;
cin >> e;
while (e != 9999) {
LNode *s = new LNode;
s->next = r->next;
s->data = e;
r->next = s;
r = s; // 将r置为新的尾指针
cin >> e;
}
r->next = NULL; // 尾指针的next置为NULL
return L;
}
// 前插操作：在p结点之前插入数据e
bool InsertPriorNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *s = new LNode;
s->next = p->next;
s->data = p->data; // 数据后移，模拟结点后移
p->next = s;
p->data = e; // 将前结点置为新插入的结点
return true;
}
// 后插操作：在p结点之后插入数据e
bool InsertNextNode(LNode *p, int e) {
if (p == NULL) {
return false;
}
LNode *q = new LNode;
q->data = e;
q->next = p->next;
p->next = q;
return true;
}
// 按位序插入
bool InserstList(LinkList &L, int i, int e) {
if (i < 1) { // i值不合法
return false;
}
LNode *p = GetElem(L, i - 1); // 遍历查找i-1个结点
InsertNextNode(p, 5244); // 使用后插法
/* // 使用前插法，达到同样效果
LNode *p = GetElem(L, i);
InsertPriorNode(p, 5244);
*/
return true;
}
// 删除p结点的后继结点
bool DeleteNextDNode(LNode *p) {
if (p == NULL || p->next == NULL) {
return false;
}
LNode *s = new LNode;
s = p->next;
p->next = s->next;
delete s;
return true;
}
// 删除指定结点
bool DeleteNode(LNode *p) {
if (p == NULL) {
return false;
}
LNode *s = new LNode;
s = p->next; // q指向被删除结点
p->data = s->data; // 数据前移，模拟结点前移
p->next = s->next; // 断开与被删除结点的联系
delete s;
return true;
}
// 按位序删除
bool ListDelte(LinkList &L, int i, int &e) {
if (i < 1) {
return false;
}
/* // 按结点删除，实现同样效果
LNode *p = GetElem(L, i); // 被删除结点
e = p->data;
DeleteNode(p);
*/
LNode *p = GetElem(L, i - 1);
e = p->next->data;
DeleteNextDNode(p); // 删除前一结点的后继结点
return true;
}
// 遍历单链表
void TraverseList(LinkList &L) {
if (L->next == NULL) {
return;
}
LNode *p = L->next; // 指向头指针
while (p != NULL) {
cout << p->data << " ";
p = p->next;
}
cout << endl;
}
int main() {
LinkList L;
InitList(L);
L = List_TailInsert(L); // 尾插法
// L = List_HeadInsert(L); // 头插法
TraverseList(L);
InserstList(L, 1, 5244);
TraverseList(L);
int e = -1;
ListDelte(L, 3, e);
cout << "被删除的值：" << e << endl;
TraverseList(L);
cout << "长度：" << GetLength(L) << endl;
return 0;
}
以上为个人经验，希望能给大家一个参考，也希望大家多多支持易知道(ezd.cc)。
