我要评论
c语言单链表
单链表的认识
单链表的定义
它是通过一组任意的储存单元来存储线性表中的数据元素。为建立线性关系，每个结点需要一个指针域以及指向下一结点的指针域。带头结点链表头节点不存储数据。
结点结构:
带头结点链表结构:
typedef struct lnode {
elemtype data;
struct lnode* next;
}lnode, * linklist;
带头结点优点
- 保证了每个结点都有前驱结点，因此在链表上第一个结点的操作与其他结点操作一致，无需特殊处理
- 无论链表是否为空，其头指针都是指向头结点的非空指针。可以对空表，非空表的情况进行统一处理。
单链表特点
- 单链表不要求逻辑上相邻的两个元素在物理位置上也相邻，因此不需要连续的存储空间。
- 单链表是非随机的存储结构，即不能直接找到表中某个特定的结点。
单链表的操作
初始化
通常会用头指针来标识一个单链表，头指针为null时表示一个空表。但是，为了操作方便，会在单链表的第一个结点之前附加一个结点，称为头结点。头结点的数据域可以不设任何信息，也可以记录表长等信息。头结点的指针域指向线性表的第一个元素结点。
bool initlist(linklist& l) {
l = (lnode*)malloc(sizeof(lnode));
if (l == null)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
l->next = null;
return true;
}
建立单链表
头插法
头插法顾名思义就是将新结点插入头结点之后，先让新结点的指针指向头结点的下一个结点地址，再让头结点的指针指向新结点地址。注意先后顺序，否则会断链。
linklist list_headinsert(linklist& l) { //逆序创建链表
initlist(l); //初始化链表
lnode* headnode = l;
lnode* newnode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) { //输入0表示结束
newnode = (lnode*)malloc(sizeof(lnode)); //创建新结点
newnode->data = x;
newnode->next = headnode->next; //头插核心
headnode->next = newnode;
scanf_s("%d", &x);
}
return l;
}
头插法的特点：读入数据的顺序和输出的顺序是相反的，是逆序输出，时间复杂度是o(n)。
- tips：如果没有头结点，要特殊处理第一个结点。
尾插法
尾插法简单来说，就是把新加入的节点插入到上一个节点的尾部（头插法是把新加入的节点插入到上一个节点的头部），next存储下一个节点位置的地址，把尾指针指向尾结点地址，最后尾结点指向null。再简化语言就是，把新结点连上，让它成为尾结点。
注意：tailnode = newnode 不要写成 newnode = tailnode
交换顺序后图解
由此可看出交换顺序会导致插入不了结点
linklist list_tailinsert(linklist& l) { //顺序创建链表
initlist(l);
lnode* newnode, * tailnode = l;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) { //输入0结束
newnode = (lnode*)malloc(sizeof(lnode)); //创建新结点
newnode->data = x;
tailnode->next = newnode; //尾插核心
tailnode = newnode;
scanf_s("%d", &x);
}
tailnode->next = null; //尾指针指向null
return l;
}
遍历单链表
这是带头结点的链表，所以先找到第一个结点p，p为空则为空链表，然后遍历到尾结点就行。
void printlist(linklist l) {
lnode* p = l->next;
if (!p) printf("空链表");
else
{
printf("遍历链表:");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
单链表的长度
思路就是遍历链表，记录遍历次数就是长度。
int length(linklist l) {
lnode* p = l->next;
int len = 0;
while (p) {
p = p->next;
len++;
}
return len;
}
查找操作
按值查找
从单链表的第一个结点开始，依次比较表中各个结点的数据域的值，若某结点数据域的值等于x，则返回该结点的指针；若整个单链表中没有这样的结点，则返回空。
lnode* locateelem(linklist l, int x) {
lnode* p = l->next;
while (p && p->data != x) {
p = p->next;
}
return p;
}
按位查找
从单链表的头结点开始，顺着指针域逐个往下搜索，直到找到第 i 个结点为止，否则返回最后一个结点的指针域null。
lnode* getelem(linklist l, int i) {
lnode* p = l;
int j = 0;
if (i<0 || i>length(l))
return null;
else {
while (j < i)
{
p = p->next;
j++;
}
}
return p;
}
当然你也可以从第一个结点开始，往下搜索。我为了方便后续操作找到头结点，所以是从头结点往下搜索。
插入操作
将值为x的新结点插入到单链表l的第i个位置上。从表头开始遍历，查找第 i-1个结点，即插入位置的前驱结点为p，然后利用前插操作，令新结点s的指针域指向p的后继结点，再令结点p的指针域指向新结点*s。
bool insert(linklist& l, int i, int x) {
if (i < 1 || i>length(l))
{
printf("输入位序不合法");
return false;
}
lnode* p = getelem(l, i - 1);
lnode* s = (lnode*)malloc(sizeof(lnode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
从插入操作就能体现出getelem函数从头结点往下搜索的好处，它能找到第一个结点的前驱结点(头结点)，因此就不用特殊处理第一个结点了。
删除操作
将单链表的第 i 个结点删除。先检查删除位置的合法性，然后从头开始遍历，找到i的前驱结点p，被删除结点为s，修改p的指针域，将其指向s的下一个结点，最后再释放结点s的存储空间。
bool delete(linklist& l, int i)
{
if (i < 1 || i>length(l))
{
printf("输入位序不合法");
return false;
}
lnode* p = getelem(l, i - 1);
lnode* s = p->next;
p->next = s->next;
free(s);
return true;
}
完整代码及实例
完整代码
#include<stdio.h>
#include<stdlib.h>
typedef int elemtype;
typedef struct lnode {
elemtype data;
struct lnode* next;
}lnode, * linklist;
bool initlist(linklist& l) {
l = (lnode*)malloc(sizeof(lnode));
if (l == null)
{
printf("内存空间不足，分配空间失败\n");
return false;
}
l->next = null;
return true;
}
linklist list_headinsert(linklist& l) { //逆序创建链表
initlist(l); //初始化链表
lnode* headnode = l;
lnode* newnode;
int x;
printf("输入链表元素（以0结束）：\n");
scanf_s("%d", &x);
while (x != 0) { //输入0表示结束
newnode = (lnode*)malloc(sizeof(lnode)); //创建新结点
newnode->data = x;
newnode->next = headnode->next; //头插核心
headnode->next = newnode;
scanf_s("%d", &x);
}
return l;
}
linklist list_tailinsert(linklist& l) { //顺序创建链表
initlist(l);
lnode* newnode, * tailnode = l;
int x;
printf("输入链表元素（以0结束）:\n");
scanf_s("%d", &x);
while (x != 0) { //输入0结束
newnode = (lnode*)malloc(sizeof(lnode)); //创建新结点
newnode->data = x;
tailnode->next = newnode; //尾插核心
tailnode = newnode;
scanf_s("%d", &x);
}
tailnode->next = null; //尾指针指向null
return l;
}
//遍历操作
void printlist(linklist l) {
lnode* p = l->next;
if (!p) printf("空链表");
else
{
printf("遍历链表:");
while (p) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
}
int length(linklist l) {
lnode* p = l->next;
int len = 0;
while (p) {
p = p->next;
len++;
}
return len;
}
lnode* locateelem(linklist l, int x) {
lnode* p = l->next;
while (p && p->data != x) {
p = p->next;
}
return p;
}
lnode* getelem(linklist l, int i) {
lnode* p = l;
int j = 0;
if (i<0 || i>length(l))
return null;
else {
while (j < i)
{
p = p->next;
j++;
}
}
return p;
}
bool insert(linklist& l, int i, int x) {
if (i < 1 || i>length(l))
{
printf("输入位序不合法");
return false;
}
lnode* p = getelem(l, i - 1);
lnode* s = (lnode*)malloc(sizeof(lnode));
s->data = x;
s->next = p->next;
p->next = s;
return true;
}
bool delete(linklist& l, int i)
{
if (i < 1 || i>length(l))
{
printf("输入位序不合法");
return false;
}
lnode* p = getelem(l, i - 1);
lnode* s = p->next;
p->next = s->next;
free(s);
return true;
}
int main()
{
linklist l;
initlist(l);
printf("头插建立链表\n");
list_headinsert(l);
printlist(l);
printf("插入99到第2位\n");
insert(l, 2, 99);
printlist(l);
printf("删除第1位\n");
delete(l, 1);
printlist(l);
printf("\n\n尾插建立链表\n");
list_tailinsert(l);
printlist(l);
printf("插入99到第1位\n");
insert(l, 1, 99);
printlist(l);
printf("删除第1位\n");
delete(l, 1);
printlist(l);
}
测试结果
头插建立链表
输入链表元素（以0结束）：
1 2 3 4 5 6 7 0
遍历链表:7 6 5 4 3 2 1
插入99到第2位
遍历链表:7 99 6 5 4 3 2 1
删除第1位
遍历链表:99 6 5 4 3 2 1
尾插建立链表
输入链表元素（以0结束）:
1 2 3 4 5 6 7 0
遍历链表:1 2 3 4 5 6 7
插入99到第1位
遍历链表:99 1 2 3 4 5 6 7
删除第1位
遍历链表:1 2 3 4 5 6 7
发表评论