WilliamsT
2022/05/19阅读:23主题:默认主题
考研数据结构之--手撕链表(1)
考研数据结构之--手撕链表(1)
序言:作为一个科班出身的学生,不会手写链表的话,那可就太嘿嘿嘿了😏😏😏😏😏😏,全部函数名字 取自《王道考研数据结构》
本内容及以后全部代码由c,c++,java这三种语言。代码可以复制粘贴到自己电脑的编译器上调试运行,可能会有bug,那就看你们的眼力见了。哈哈哈哈
首先从最简单的单链表开始讲起:
1.0单链表(c++/c)
线性表的链式存储,普通的数组是每个元素都挨着的,在内存中也是相邻的,而链表只是逻辑上的先后顺序,在内存地址中并不一定是相邻的哦。
顺序存储(数组)的缺点:在我们需要删除或者插入元素的时候,需要移动元素,来补充或者腾出位置来。看下图:
如果数组原来元素就非常多了,元素移位的操作,就会带来极大的时间消耗,这是我们不想看到的!!!
所以,对于需要进行频繁插入,删除元素的操作的时候,我们的单链表应运而生。
链表就引出了指针的内容,重点在于理解理解理解,始终给我记着,指针---地址 , 指针--指向某个位置的东西
1.1结点定义
前提:结构体的基本语法
单链表的结点是分为两个部分的: 1.数据域(存放元素的位置) 2.指针域(指向下一个结点的位置)
不要告诉我,上面这都看不懂啊。。。
有了这个,我们就可以写出结点的定义代码了
typedef struct LNode{
int data; //这里可以是任意类型的, 书上是ElementType
struct LNode *next;
}Node; //这里书上是LNode
这就定义完了嘞。
每个结点类型我们清楚了,那么整个单链表我们就画得出来了,如下图:
思考一下:单链表能随机存取吗?
1.2 关于带头指针和不带头指针的问题
通过上图可以看出,上面的单链表是没有头指针的,那么,何为头指针呢?头指针就是,我们在单链表中额外申请一个结点,此结点的next指针指向单链表的第一个元素。
看下图带头指针的:

==这样做有什么好处呢?==问题提在这里,后面来分析。记着这个问题啊!!!(可能在后序文章)
接下来的全部这操作都是在 有头指针的 单链表下进行的。
1.3 基本操作的实现
知道了结点定义,一个单链表就是一个一个结点串起来的而已嘛。so easy啦
①创建单链表
问题:给定一个序列(1 3 4 5 9 ),创建链表
有两种方法,第一种是头插法,第二种是尾插法!
先说头插法:顾名思义,每次插入结点都是从头部插入的;看下图过程:

后面的步骤一模一样。我就不画了。
可以发现,创建的链表是逆序的!!
代码部分:(跟着代码,画图,就看的懂了)
//c++
#include <iostream>
using namespace std;
typedef struct LNode {
int data;
struct LNode *next;
}Node;
//头插法
//num是创建链表的序列,n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n) {
head = new Node;
head->next = NULL;
for ( int i = 0; i < n; ++i ) {
Node *s = new Node;
s->data = num[i];
s->next = head->next;
head->next = s;
}
}
int main()
{
Node *head;
int num[] = {1,3,4,5,9};
List_HeadInsert(head, num, 5);
Node *p = head->next; // p指针指向head->next,也就是第一个结点
while ( p ) { //当p不为NULL时
cout << p->data << ' '; //输出p的数据库
p = p->next; //p = p->next =号是从右往左赋值的
}
delete head;
return 0;
}
//c
//为了方便,以后就是c++,毕竟一个new就行了
#include <stdio.h>
#include <stdlib.h>
typedef struct LNode {
int data;
struct LNode *next;
}Node;
int main()
{
Node *head = (Node*)malloc(sizeof(Node));
head->next = NULL;
int num[] = {1,3,4,5,9}, i;
for ( i = 0; i < 5; ++i ) {
Node *s = (Node*)malloc(sizeof(Node));
s->data = num[i];
s->next = head->next;
head->next = s;
}
Node *p = head->next;
while ( p ) {
printf("%d ", p->data);
p = p->next;
}
return 0;
}
再来看,尾插法:(每次都是从尾部插入元素)
我就直接放代码了,图请读者跟着代码,自己画着看看。
//尾插法
void List_TailInsert(Node* &head, int num[], int n) {
head = new Node;
head->next = NULL;
Node *p = head;
for ( int i = 0; i < n; ++i ) {
Node *s = new Node;
s->data = num[i];
s->next = NULL;
p->next = s;
p = s;
}
}
//创建的序列是顺序的
②查找
==画图,跟着画图==
按序号查找元素
//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index ) {
Node *p = list->next;
int i = 1;
//index 无效,即<1
if ( index < 1 ) return list;
while ( p ) {
if ( i == index) {
return p;
}
++i; p =p->next;
}
//index大于表长
return p;
}
按值查找元素
//按值查找
Node* GetElemByValue(Node* list, int v ) {
Node* p = list->next;
while ( p && p->data != v) {
p = p->next;
}
return p;
}
//思考:找不到返回值是什么? NULL
③插入元素
按位置插入
思路就是,找到前一个位置,为什么是前一个位置呢?因为目前我们的单链表是只有next指针,找到结点的前驱结点不方便。

//指定index插入结点
bool Insert( Node* &list, int data, int index ) {
Node *p = list;
int i = 1;
if ( i < 1 ) return false; //index无效
while ( p && i < index ) {
p = p->next; i++;
}
if ( !p ) return false; //index > 链表长度+1
Node *s = new Node;
s->data = data;
s->next = p->next;
p->next = s;
return true;
}
思考:上图中的第一步,和第二步先后顺序能交换吗?
上面是找到指定位置的前一个位置,然后插入。这样是主流的,既方便又方便。然而,假如有一些阴间的要求,我们定义的指针p必须先定位到指定位置index上呢?我们该怎么做呢?
思路:我们仍然是在p指针所指的结点后面插入元素,然后交换这两个结点的data不就行了吗?
我艹。。。。。茅塞顿开
//指定index插入结点
bool Insert2( Node* &list, int data, int index ) {
Node *p = list;
int i = 1;
if ( i < 1 ) return false; //index无效
while ( p && i <= index ) {
p = p->next; i++;
}
if ( !p ) return false; //index > 链表长度+1
Node *s = new Node;
s->data = data;
s->next = p->next;
p->next = s;
//交换值
int temp = p->data;
p->data = s->data;
s->data = temp;
return true;
}
//在最后一个位置插入需要读者自行修改一下
拓展,插入到指定元素data的前面,请读者自行实现
可以先查找,返回的就是Node*,再插入元素!!
③删除元素
先孤立它,再删除掉!
删除指定位置的元素
请看下图:(删除第二个位置的元素)

//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index) {
if ( index < 1 ) return false;
Node *p = list, *q;
int i = 1;
while (p && i < index ) {
p = p->next;
++i;
}
if ( p == NULL ) return false; //想想为什么
q = p->next;
p->next = q->next;
delete q;
return true;
}
删除指定元素
请读者自行实现,
④求表长度
这还用我来写????
1.4完整代码
//c++
#include <iostream>
using namespace std;
typedef struct LNode {
int data;
struct LNode *next;
}Node;
//头插法
//num是创建链表的序列,n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n);
//尾插法
void List_TailInsert(Node* &head, int num[], int n);
//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index );
//按值查找
Node* GetElemByValue(Node* list, int v );
//指定index插入结点(定位到前一个位置)
bool Insert( Node* &list, int data, int index );
//指定index插入结点(定位到目标位置)
bool Insert2( Node* &list, int data, int index );
//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index);
//输出链表
void outPut(Node *list);
//主函数
int main()
{
Node *head;
int num[] = {1,3,4,5,9};
// List_HeadInsert(head, num, 5);
List_TailInsert(head, num, 5);
Node *f = GetElemByIndex(head, 1);
if ( f )
cout << f->data << endl;
f = GetElemByValue(head, 10);
if ( f ) cout << f->data << endl;
else cout << "No!\n";
Insert2(head, 99, 1);
outPut(head);
// Insert2(head, 99, 6);
// outPut(head);
deleteData(head, 2);
outPut(head);
delete head;
return 0;
}
//头插法
//num是创建链表的序列,n是序列的大小
void List_HeadInsert(Node* &head, int num[], int n) {
head = new Node;
head->next = NULL;
for ( int i = 0; i < n; ++i ) {
Node *s = new Node;
s->data = num[i];
s->next = head->next;
head->next = s;
}
}
//尾插法
void List_TailInsert(Node* &head, int num[], int n) {
head = new Node;
head->next = NULL;
Node *p = head;
for ( int i = 0; i < n; ++i ) {
Node *s = new Node;
s->data = num[i];
s->next = NULL;
p->next = s;
p = s;
}
}
//按序号查找元素(从1开始)
Node* GetElemByIndex(Node* list, int index ) {
Node *p = list->next;
int i = 1;
//index 无效,即<1
if ( index < 1 ) return list;
while ( p ) {
if ( i == index) {
return p;
}
++i; p =p->next;
}
//index大于表长
return p;
}
//按值查找
Node* GetElemByValue(Node* list, int v ) {
Node* p = list->next;
while ( p && p->data != v) {
p = p->next;
}
return p;
}
//指定index插入结点(定位到前一个位置)
bool Insert( Node* &list, int data, int index ) {
Node *p = list;
int i = 1;
if ( i < 1 ) return false; //index无效
while ( p && i < index ) {
p = p->next; i++;
}
if ( !p ) return false; //index > 链表长度+1
Node *s = new Node;
s->data = data;
s->next = p->next;
p->next = s;
return true;
}
//指定index插入结点(定位到目标位置)
bool Insert2( Node* &list, int data, int index ) {
Node *p = list;
int i = 1;
if ( i < 1 ) return false; //index无效
while ( p && i <= index ) {
p = p->next; i++;
}
if ( !p ) return false; //index > 链表长度+1
Node *s = new Node;
s->data = data;
s->next = p->next;
p->next = s;
//交换值
int temp = p->data;
p->data = s->data;
s->data = temp;
return true;
}
//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &list, int index) {
if ( index < 1 ) return false;
Node *p = list, *q;
int i = 1;
while (p && i < index ) {
p = p->next;
++i;
}
if ( p == NULL ) return false; //想想为什么
q = p->next;
p->next = q->next;
delete q;
return true;
}
//输出链表
void outPut(Node *list){
Node* p = list->next;
while ( p ) {
cout << p->data << ' ';
p =p->next;
}
cout << endl;
}
1.5 思考题?
1.清空链表怎么写?
2.插入元素,删除元素,的时间复杂度怎么分析?
提示:分为两步分析,第一步找,第二步插入/删除,二者的时间复杂度都要分析出来。
作者介绍