W

WilliamsT

V1

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* listint 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* listint v ) {
 Node* p = list->next;
 while ( p && p->data != v) {
  p = p->next;
 }
 return p;
}
//思考:找不到返回值是什么?   NULL

③插入元素

按位置插入

思路就是,找到前一个位置,为什么是前一个位置呢?因为目前我们的单链表是只有next指针,找到结点的前驱结点不方便。

//指定index插入结点
bool Insert( Node* &listint 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* &listint 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* &listint 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* listint index );
//按值查找
Node* GetElemByValue(Node* listint v );
//指定index插入结点(定位到前一个位置)
bool Insert( Node* &listint data, int index );
//指定index插入结点(定位到目标位置)
bool Insert2( Node* &listint data, int index );
//删除指定位置的元素(从位置一开始计数)
bool deleteData(Node* &listint 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, 991);
 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* listint 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* listint v ) {
 Node* p = list->next;
 while ( p && p->data != v) {
  p = p->next;
 }
 return p;
}
//指定index插入结点(定位到前一个位置)
bool Insert( Node* &listint 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* &listint 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* &listint 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.插入元素,删除元素,的时间复杂度怎么分析?

提示:分为两步分析,第一步找,第二步插入/删除,二者的时间复杂度都要分析出来。

分类:

后端

标签:

数据结构与算法

作者介绍

W
WilliamsT
V1