数据结构--单链表C/C++

本文主要是介绍数据结构--单链表C/C++，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最近在学习数据结构，其中有介绍单链表跟单循环链表的，现在复习一下。首先要定义一下数据结构（节点），如下：

typedef int DataType; //方便后面修改数据类型，有点像C++/JAVA中的泛型
typedef struct Node 
{DataType data;struct Node *next;
}Node;

单链表：

接下来是定义一个获取链表某个位置节点的函数，如下：

Node* getptr(Node* head, int pos)
{Node *p = head;if (p == NULL || pos == 0){return head;}for (int i = 0; p && i < pos; i++){p = p->next;}return p;
}

获取链表有几个节点，如下：

int getSize(Node* head)
{int size = 0;Node *p = head;while(p){size++;p = p->next;}return size;
}

向链表中添加新的节点数据，如下：

bool insert(Node** head, int position, DataType d)
{if (position < 0 || position > getSize(*head)){return false;}Node *node = (Node*)malloc(sizeof(Node));node->data = d;node->next = NULL;if (position == 0){node->next = *head;*head = node;return true;}Node *p = getptr(*head, position - 1);Node *r = p->next;node->next = r;p->next = node;return true;
}

这里head使用了指针的指针，使用指针的指针是因为调用处需要带回head的改变，即实参需要改变；形参head执行完函数insert后是会被释放掉的。来张内存分配图：

将两个链表拼接到一起，如下:

void unionList(Node *a, Node *b)
{Node *p = a;while(p->next)p = p->next;p->next = b;
}

将链表数据打印出来，如下：

void print(DataType d)
{printf("%d\t", d);
}void trave(Node *head, void(*fun)(DataType))
{Node *p = head;while(p){fun(p->data);p = p->next;}
}

删除某个位置的链表节点，如下：

bool erase(Node **head, int pos)
{if (pos < 0 || pos >= getSize(*head)){return false;}Node *p = *head;if (pos == 0){*head = (*head)->next;free(p);p = NULL;return true;}p = getptr(*head, pos - 1);Node *q = p->next;p->next = q->next;free(q);q = NULL;return true;
}

将链表倒置，如下：

bool erase(Node **head, int pos)
{if (pos < 0 || pos >= getSize(*head)){return false;}Node *p = *head;if (pos == 0){*head = (*head)->next;free(p);p = NULL;return true;}p = getptr(*head, pos - 1);Node *q = p->next;p->next = q->next;free(q);q = NULL;return true;
}

删除链表，如果节点中的data开辟了内存，也需要释放，这个没有开辟内存，所以不需要释放，如下：

void deleteAll(Node **head)
{Node *tmp, *n, *h;if (head == NULL)return;h = *head;for (tmp = h->next; tmp != NULL; tmp = n){n = tmp->next;free(tmp);		}free(h);*head = NULL;
}

函数测试代码如下：

#include "SingleList.h"
#include <stdio.h>int main()
{Node *head = NULL;insert(&head, 0, 9);	insert(&head, 0, 8);insert(&head, 0, 3);insert(&head, 0, 11);printf("init------------>\n");trave(head, print);int len = getSize(head);printf("\n getSize = %d\n", len);bool b = erase(&head, 2);if (b){printf("erase--------->\n");trave(head, print);}printf("\n reverse------------->\n");reverse(&head);trave(head, print);printf("\n head2-------init-->\n");Node *head2 = NULL;insert(&head2, 0, 20);	insert(&head2, 0, 22);insert(&head2, 0, 14);insert(&head2, 0, 19);trave(head2, print);printf("\n unionList--------->\n");unionList(head, head2);trave(head, print);printf("\n deleteAll--------->\n");deleteAll(&head);trave(head, print);printf("\n----main end -----\n");return 0;
}

编译运行结果如下：

单循环链表：

获取链表长度，rear是尾指针，指向最后一个节点，如下：

int getSize(Node *rear)
{int size = 0;if (rear){Node *p = rear->next;while (p != rear){size++;p = p->next;}size++;}return size;
}

跟位置获取对应链表节点，如下：

Node *getptr(Node *rear, int pos)
{if (rear == NULL){return rear;}if (pos >= getSize(rear)){return NULL;	}Node *p = rear->next;for(int i = 0; i < pos; i++){p = p->next;}return p;
}

向链表中添加节点，如下：

bool insert(Node **rear, int position, DataType d)
{if (position < 0 || position > getSize(*rear)){return false;}Node *node = (Node *)malloc(sizeof(Node));node->data = d;node->next = NULL;if (position == 0){if (*rear == NULL){node->next = node;*rear = node;}else{node->next = (*rear)->next;(*rear)->next = node;}return true;}	Node *p = getptr(*rear, position - 1);Node *r = p->next;node->next = r;p->next = node;if (*rear == p){*rear = node;	}return true;
}

删除链表中某个节点，如下：

bool erase(Node **rear, int pos)
{if (*rear == NULL || pos < 0 || pos >= getSize(*rear)){return false;}Node *p = (*rear)->next;if (pos == 0){(*rear)->next = p->next;free(p);p = NULL;return true;}p = getptr(*rear, pos - 1);Node *q = p->next;p->next = q->next;if (q == *rear){*rear = p;}free(q);q = NULL;return true;
}

链表数据打印，如下：

void print(DataType d)
{printf("%d\t", d);
}void trave(Node *rear, void(*fun)(DataType))
{if (rear == NULL)return;Node *p = rear->next;while(p != rear){fun(p->data);p = p->next;}fun(p->data);
}

测试代码如下：

#include "cycleList.h"int main()
{Node *rear = NULL;insert(&rear, 0, 8);insert(&rear, 0, 3);insert(&rear, 0, 19);insert(&rear, 0, 6);printf("\n==============main init=============\n");trave(rear, print);printf("\n==============erase init=============\n");erase(&rear, 1);trave(rear, print);printf("\n==============main end=============\n");return 0;
}

测试结果如下：