C 链表模板及笔记

标签：Status return LNode int 笔记 next 链表 data 模板

文章目录

Intro
理解线性表的基本概念（逻辑特性、术语及物理存储）

基本概念

n (n>=0)个数据特性相同的元素构成的有限序列称为线性表

逻辑特性

存在唯一的一个被称作 "第一个" 的数据元素
存在唯一的一个被称作 "最后一个" 的数据元素
除第一个之外,结构中每个元素只有一个前驱
除最后一个之外,结构中每个元素只有一个后驱

术语
物理存储

一片连续的存储地址 -> 顺序表
可非连续的存储地址 -> 链式

单链表
双向链表
双向循环链表
顺序表
循环链表
一元多项式的表示与相加
有序表的合并
DevLog

Intro

理解线性表的基本概念（逻辑特性、术语及物理存储）

基本概念

n (n>=0)个数据特性相同的元素构成的有限序列称为线性表

逻辑特性

存在唯一的一个被称作 “第一个” 的数据元素

存在唯一的一个被称作 “最后一个” 的数据元素

除第一个之外,结构中每个元素只有一个前驱

除最后一个之外,结构中每个元素只有一个后驱

术语

物理存储

一片连续的存储地址 -> 顺序表

可非连续的存储地址 -> 链式

单链表

/*
 * @Author: 
 * @data: 2019-12-02 14:49:03
 * @Last Modified by: 
 * @Last Modified time: 2019-12-02 15:54:49
 */

#include <iostream>
#include <cstdio>

using namespace std;

typedef int Status;
typedef int Elem;

typedef struct LNode
{
  /* data */
  Elem data;
  struct LNode *next; //想起 (数据结构是递归的 LNode 结点 由 data  next 组成，而next本身是一种指向LNode 的指针 即LNode定义中调用了自身， 所以连表示一种递归的数据结构 这句台词在栈里 你说操蛋不操蛋
} LNode, *LinkList; //理解成 LNode头 *LinkList 除了头以外的？ 大概

//初始化
Status InitList(LinkList &L)
{
  L = new LNode; //申请一手内存 指向一片空空如也
  L->next = NULL;
  return 1;
}

//取值
Status GetElemList(LinkList &L, int i, Elem &e) //提一提这个e 很蛋疼 说老实话我不明白为什么要返回它出来看看你丢了啥
{
  LNode *p = L->next; //你好 头节点
  int j = 1;

  while (p && j < i)
  {
    p = p->next; //常规遍历
    ++j;
  }
  if (!p || j > i)
    return -1;
  e = p->data;
  return 1;
}

//插入
Status InsertList(LinkList &L, int i, Elem e)
{
  LNode *p = L;
  int j = 0;

  while (p && j < i - 1)
  {
    p = p->next;
    j++;
  }
  if (!p || j > i - 1)
    return -1;

  LNode *s = new LNode;
  s->data = e;
  s->next = p->next; //指向头节点指向的 看视频比较好理解
  p->next = s; //头节点又指向这个新的

  return 1;
}

//长度
Status LenList(LinkList &L, Elem &e)
{
  LNode *p = L->next;
  int j = 0;

  while (p)
  {
    p = p->next;
    ++j;
  }

  if (p)
    return -1;

  e = j; //有一说一 遍历计数

  return 1;
}

//删除
Status DelList(LinkList &L, int i)
{
  LNode *p = L->next;
  int j = 0;

  while ((p->next) && (j < i - 1))
  {
    p = p->next;
    ++j;
  }

  if (!p->next || j > i - 1)
    return -1;

  LNode *q = p->next;
  p->next = q->next;
  delete q;//其实这里 q才是目标 因为之前循环都只到i-1  P直接指向下下个 删了Q Q太难了

  return 1;
}

//排序
Status SortList(LinkList &L)
{
  LNode *p = L->next;
  LNode *TmpNode;
  int tmp = 0;

  while (p)
  {
    TmpNode = p;
    while (TmpNode) //有一说一 我正常冒泡不知道为什么挂球了 
    {
      if (p->data > TmpNode->data)
      {
        tmp = p->data;
        p->data = TmpNode->data;
        TmpNode->data = tmp;
      }
      TmpNode = TmpNode->next;
    }
    p = p->next;
  }

  return 1;
}

//遍历
Status ShowList(LinkList &L)
{
  LNode *p = L->next;
  while (p)
  {
    cout << p->data << " ";
    p = p->next; //直接遍历
  }

  return 1;
}

//头插
Status CreatList_H(LinkList &L, int num)
{
  L = new LNode;
  L->next = NULL;

  for (int i = 0; i < num; i++)
  {
    LNode *p = new LNode;
    cin >> p->data;

    p->next = L->next; //上面我写了
    L->next = p;
  }

  return 1;
}

//尾插
Status CreatList_L(LinkList &L, int num)
{
  L = new LNode;
  L->next = NULL;
  LNode *r = L;

  for (int i = 0; i < num; i++)
  {
    LNode *p = new LNode;
    cin >> p->data;

    p->next = NULL;
    r->next = p;
    r = p;//重点就是这个啊 r指向了P 一直走下去
  }

  return 1;
}

int main()
{
  LinkList L;

  //1
  InitList(L);
  //1
  int num;
  cin >> num;
  //CreatList_H(L, num);

  //1
  CreatList_L(L, num);
  //1
  //cout << InsertList(L, 1, 1);

  //1
  int e;
  GetElemList(L, 1, e);
  cout << "Elem 1 " << e << " ";

  //1
  int len;
  LenList(L, len);
  cout << "len:" << len << " ";

  //1
  int len2;
  //DelList(L, 1);
  //LenList(L, len2);
  //cout << "AfterDellen " << len2<<" ";

  //1
  SortList(L);

  //cout<<L->next->data;
  //1
  ShowList(L);
}

双向链表

#include <iostream>
#include <cstdio>

using namespace std;

typedef int Elem;
typedef int Status;

typedef struct DulList //我猜是 doubole list...
{
  /* data */
  Elem data;
  struct DulList *prior;
  struct DulList *next; // 前 后 指针
} DulList, *DulLinkList;

Status InitDulList(DulLinkList &L)
{
  L = new DulList;
  L->next = NULL;
  L->prior = NULL;

  return 1;
}

Status CreatDulList_H(DulLinkList &L, int num)
{
  L = new DulList;
  L->next = NULL;

  for (int i = 1; i <= num; i++)
  {
    DulList *p = new DulList;
    cin >> p->data;

    p->next = L->next;
    if (L->next) L->next->prior = p;
    L->next = p;
    p->prior = L;
  }

  return 1;
}

DulList* GetElemDulList(DulLinkList &L, int i) //这个真就 DulList* ...
{
  DulList *p = L;
  int j = 0;

  while (p && j < i)
  {
    p = p->next;
    ++j;
  }

  if (i<1 || j>i)
    ;//这个不该这么写 其实

  return p;
}

Status InsertDulList(DulLinkList &L, int i, Elem e)
{
  DulList *p = L;

  if (!(p = GetElemDulList(L, i))) //P的位置其实被改了 不会出现 插在头的情况
    return -1;

  DulList *s = new DulList;

  s->data = e;
  s->prior = p->prior;
  p->prior->next = s;

  s->next = p;
  p->prior = s;

  return 1;
}

Status DelDulList(DulLinkList &L, int i) //Delete
{
  DulList *p = L->next;
  if (!(p = GetElemDulList(L, i)))
    return -1;

  DulList *s = new DulList;

  p->prior->next = p->next;
  p->next->prior = p->prior; //前后跳着指 中间就空一格了

  return 1;
}

Status ShowDulList(DulLinkList &L) {

  DulList *p = L->next;

  while (p)
  {
    cout << p->data<<" ";
    p = p->next;
  }

  return 1;
}

int main()
{
  DulLinkList L;

  //1
  InitDulList(L);

  //1
  CreatDulList_H(L, 3);

  //1
  InsertDulList(L, 2, 1);

  //1
  ShowDulList(L);

  //1
  DelDulList(L, 2);

  //1
  ShowDulList(L);
}

双向循环链表

#include <iostream>
#include <cstdio>

using namespace std;

typedef int Elem;
typedef int Status;

typedef struct DulList
{
  /* data */
  Elem data;
  struct DulList *prior;
  struct DulList *next;
} DulList, *DulLinkList;

Status InitDulList(DulLinkList &L)
{
  L = new DulList;
  L->next = NULL;
  L->prior = NULL;

  return 1;
}

Status CreatDulList_H(DulLinkList &L, int num)
{
  L = new DulList;
  L->next = NULL;

  for (int i = 1; i <= num; i++)
  {
    DulList *p = new DulList;
    cin >> p->data;

    p->next = L->next;
    if (L->next)
      L->next->prior = p;
    L->next = p;
    p->prior = L;
  }

  return 1;
}

Status ShowDulList(DulLinkList &L)
{

  DulList *q = L->next;
  while (q->next)
    q = q->next;
  q->next = L->next;//怎么双向没写 我试了一下 把尾巴指向头 就循环了...

  DulList *p = L->next;

  while (p)
  {
    cout << p->data << " ";
    p = p->next;
  }

  return 1;
}

int main()
{
  DulLinkList L;

  //1
  InitDulList(L);

  //1
  CreatDulList_H(L, 3);

  //1
  ShowDulList(L);
}

顺序表

/*
 * @Author: 
 * @data: 2019-12-02 13:46:20
 * @Last Modified by:
 * @Last Modified time: 2019-12-03 20:18:30
 */

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef int Elem;

typedef struct
{
  /* data */
  Elem *data; //这里其实是整了个数组
  int len;
} SqList;//Sq 是 Squence的意思

//初始化
Status InitList(SqList &L)
{
  L.data = new Elem[MAXSIZE]; //申请 内存
  L.len = 0;
  if (L.data)
    return -1;

  return 1;
}

//取值
Status GetList(SqList &L, int i, Elem &e)
{
  if (i < 1 || i > L.len)
    return -1;
  e = L.data[i - 1];

  return e;
}

//按值查找
Status Locatedata(SqList L, Elem e) //你可能要问了 为什么 这里没有&？ 因为我查找不需要改它本身...
{
  for (int i = 0; i < L.len; i++)
    if (L.data[i] == e)
      return i + 1;

  return 1;
}

//插入
Status InsertList(SqList &L, int i, Elem e)
{
  if (i < 1 || i > L.len + 1)
    return -1;

  if (L.len == MAXSIZE)
    return -1;

  for (int j = L.len; j >= i - 1; j--)
    L.data[j + 1] = L.data[j]; //从后往前 覆盖

  L.data[i - 1] = e; //猜猜为什么 是i-1? 因为 赋值那里 是从i=0开始的..
  ++L.len;

  return 1;
}

//删除
Status DelList(SqList &L, int i)
{
  if (i < 1 || i > L.len)
    return -1;

  for (int j = i; j < L.len - 1; j++)
    L.data[j - 1] = L.data[j]; //依旧是覆盖 减总长

  --L.len;

  return 1;
}

//清空
Status DelAlList(SqList &L) //随便写的 应该成?...
{
  L.data = NULL;

  L.len = 0;

  return 1;
}
int main()
{
  SqList List;

  //1
  InitList(List);
  
  int num;
  cin >> num;
  for (int i = 1; i <= num; i++)
  {
    Elem OBJ;
    cin >> OBJ;
    //1
    InsertList(List, i, OBJ);
  }

  for (int i = 0; i < List.len; i++)
    cout << List.data[i];

  //1
  DelAlList(List);

  //Locatedata(List, 1);
  ///DelList(List, 1);
  for (int i = 0; i < List.len; i++)
    cout << List.data[i];
}

循环链表

/*
 * @Author: 
 * @data: 2019-12-03 19:47:29 
 * @Last Modified by: 
 * @Last Modified time: 2019-12-03 20:00:06
 */

#include <iostream>
#include <cstdio>

using namespace std;

typedef int Status;
typedef int Elem;

typedef struct LNode
{
  /* data */
  Elem data;
  struct LNode *next;
} LNode, *LinkList;

//初始化
Status InitList(LinkList &L)
{
  L = new LNode;
  L->next = NULL;
  return 1;
}

//遍历
Status ShowList(LinkList &L)
{
  //循环链表 特征！
  LNode *q = L->next;
  while(q->next)
  {
    q = q->next;
  }
  q->next = L->next; 
 
  LNode *p = L->next;
  while (p)
  {
    cout << p->data << " ";
    p = p->next;
  }

  return 1;
}

//创建
Status CreatList_H(LinkList &L, int num)
{
  L = new LNode;
  L->next = NULL;

  for (int i = 0; i < num; i++)
  {
    LNode *p = new LNode;
    cin >> p->data;

    p->next = L->next;
    L->next = p;
  }

  return 1;
}

int main()
{
  LinkList L;

  int num;
  cin >> num;
  CreatList_H(L, num);

  //1
  ShowList(L);
}

一元多项式的表示与相加

/*
 * @Author: 
 * @Date: 2019-12-03 20:48:51
 * @Last Modified by: 
 * @Last Modified time: 2019-12-03 21:05:06
 */

#include <iostream>

#include <cstdio>

using namespace std;

typedef int Status;
typedef int Elem;

typedef struct PNode
{
  float coef; //系数
  int expn;   //指数
  struct PNode *next;
} PNode, *Polynomial;

Status CreatPolyn(Polynomial &P, int n)
{
  P = new PNode;
  P->next = NULL;

  for (int i = 1; i <= n; ++i)
  {
    PNode *s = new PNode;
    cin >> s->coef >> s->expn;

    PNode *pre = P;
    PNode *q = P->next;

    while (q&&q->expn < s->expn) //尾插 看指数大小然后就往后面走
    {
      pre = q;
      q = q->next;
    }
    s->next = q;
    pre->next = s;//找到位子 插入
  }

  return 1;
}

Status AddPolyn(Polynomial &Pa, Polynomial &Pb) //合并
{
  PNode *p1, *p2, *p3 = Pa;
  p1 = Pa->next, p2 = Pb->next;
  p3 = Pa;

  while (p1&&p2)
  {
    int sum = 0;
    PNode *r;
    if (p1->expn == p2->expn) //如果指数一样大 P1增大 p3负责在路上链接
    {
      sum = p1->coef + p2->coef;
      if (sum)
      {
        p1->coef = sum;
        p3->next = p1;
        p3 = p1;

        p1 = p1->next;
        p2 = p2->next;

      }

      else {// 空的话 就看后面的
        r = p1, p1 = p1->next;  
        r = p2, p2 = p2->next;
      }
    }
    else if (p1->expn < p2->expn)
    {
      //连接 p1 后移
      p3->next = p1;
      p3 = p1;
      p1 = p1->next;
    }
    else
    {
      //连接p2 后移
      p3->next = p2;
      p3 = p2;
      p2 = p2->next;
    }
    p3->next = p1 ? p1 : p2; //三元操作符 p1还有就连接p1 否则连接p2
    delete Pb;
  }
  return 1;
}

int main()
{

  Polynomial P1, p2;
- 
  //1
  CreatPolyn(P1, 1);
  CreatPolyn(p2, 1);
  
  //1
  AddPolyn(P1, p2);

  cout <<P1->next->coef << " " << P1->next->expn << " ";
}

有序表的合并

/*
 * @Author: 
 * @Date: 2019-12-03 20:18:46
 * @Last Modified by: 
 * @Last Modified time: 2019-12-03 20:44:28
 */

#include <iostream>
#include <cstdio>
using namespace std;

#define MAXSIZE 100

typedef int Status;
typedef int Elem;

typedef struct
{
  /* data */
  Elem *date;
  int len;
} SqList;

//初始化
Status InitList(SqList &L)
{
  L.date = new Elem[MAXSIZE];
  L.len = 0;
  if (L.date)
    return -1;
  return 1;
}

//插入
Status InsertList(SqList &L, int i, Elem e)
{
  if (i < 1 || i > L.len + 1)
    return -1;
  if (L.len == MAXSIZE)
    return -1;
  for (int j = L.len; j >= i - 1; j--)
    L.date[j + 1] = L.date[j];
  L.date[i - 1] = e;
  ++L.len;
  return 1;
}

Status MergeList_Sq(SqList LA, SqList LB, SqList &LC)
{
  LC.len = LA.len + LB.len;
  LC.date = new Elem[LC.len];

  Elem *pa, *pb, *pc;
  Elem *pa_last, *pb_last;
  pc = LC.date, pa = LA.date, pb = LB.date;
  pa_last = LA.date + LA.len - 1;
  pb_last = LB.date + LB.len - 1;

  //逻辑上好理解 LA LB 一起找 小的就塞到LC 如果都其中一个空了 另一个就全塞进去

  while (pa <= pa_last && pb <= pb_last)
  {
    if (*pa <= *pb) *pc++ = *pa++;
    else *pc++ = *pb++;
  }
  while (pa <= pa_last) *pc++ = *pa++;
  while (pb <= pb_last) *pc++ = *pb++;

  return 1;
}

int main()
{
  SqList LA, LB, LC;
  InitList(LA);
  InitList(LB);
  InitList(LC);
  int num_A, num_B;
  cin >> num_A;
  cin >> num_B;

  for (int i = 1; i <= num_A; i++)
  {
    Elem OBJ;
    cin >> OBJ;
    //1
    InsertList(LA, i, OBJ);
  }

  for (int i = 1; i <= num_B; i++)
  {
    Elem OBJ_B;
    cin >> OBJ_B;
    InsertList(LB, i, OBJ_B);
  }

  //1
  MergeList_Sq(LA, LB, LC);

  for (int i = 0; i < LC.len; i++)
    cout << LC.date[i];

}

DevLog

1
ypedef是类型定义的意思。typedef struct 是为了使用这个结构体方便。
若struct node{ }这样来定义结构体的话。在定义 node 的结构体变量时，需要这样写:struct node n;
若用typedef，可以这样写：`

typedef struct node{}NODE;

` 。在申请变量时就可以这样写：NODE n;其实就相当于 NODE 是node 的别名。区别就在于使用时，是否可以省去struct这个关键字。

2
线性表与链表中多存在的&符号是为了给外部变量赋值直接给到外部的地址中！

3
单链表排序部分出错冒泡出问题
已改为选择排序成功

4
*LinkList 其实从始至终都是拿来指向自己的

在这里修改是直接修改的 LIST本身!

*date 可以表示为直接申请一个数组空间

5
双向链表过程中
漏看了 P40 的 if(!(p=GetElem_Dul(L,i))) 内的L
且书中缺少该模块

在 InsertDulList 中 p 出现内存错误
因此发现返回为指针属性

依据经验增添 GetElemDulList 如下

DulList* GetElemDulList(DulLinkList &L, int i)
{
  DulList *p = L;
  int j = 0;

  while (p && j < i)
  {
    p = p->next;
    ++j;
  }

  if (i<1 || j>i)
    ;

  return p;
}

p->prior 出现内存错误
依据经验添加 CreatDulList_H 模块

P 持续在 InsertDulList 出现内存错误
推断为 GetElemDulList 中指针p 移动到了 NULL
更改 while (p && j < i)
无效

排查后发现是 CreatDulList_H 中 prior 的缺失

尴尬巨尴尬

6
循环链表看了半天都不知道哪里有
看了看说尾巴指向头

然后我就试了一下在遍历部分把尾巴指向头如下：

LNode *q = L->next;
while(q->next)
{
  q = q->next;
}
q->next = L->next;

然后就好像成功了… 可以说是极快了…

7
有序表的合并部分
不得不吐槽一下
这他妈？
书上的代码是垃圾吗？
啊重要是理解算法思维自己做
关键是你写的太繁杂不如自己写啊喂
MMP 开玩笑吧我们这个学校的老师教学也跟开玩笑一样
天大的玩笑哦
存在部分问题

8
一元多项式的表示与相加
哇真实
书上写的这么多
说白了也就一点点东西
MMP 这部分该老师教的我教了尼玛个锤子
P48的 P3 不知道应该是指向那里的
后来想了想 *p3 = Pa;
对了
笑死我了

7.2
改完了我看指针下意识以为是结点
重新写了一遍半途发现是尼玛的ELEM*指针
赣

标签：Status,return,LNode,int,笔记,next,链表,data,模板
From： https://blog.51cto.com/u_16014765/6132918

文章目录

Intro

理解线性表的基本概念（逻辑特性、术语及物理存储）

基本概念

n (n>=0)个数据特性相同的元素构成的有限序列称为线性表

逻辑特性

存在唯一的一个被称作 “第一个” 的数据元素

存在唯一的一个被称作 “最后一个” 的数据元素

除第一个之外,结构中每个元素只有一个前驱

除最后一个之外,结构中每个元素只有一个后驱

术语

物理存储

一片连续的存储地址 -> 顺序表

可非连续的存储地址 -> 链式

单链表

双向链表

双向循环链表

顺序表

循环链表

一元多项式的表示与相加

有序表的合并

DevLog

相关文章

赞助商

阅读排行

C 链表模板及笔记

文章目录

Intro

理解线性表的基本概念（逻辑特性、术语及物理存储）

基本概念

n (n>=0)个数据特性相同的元素构成的有限序列称为 线性表

逻辑特性

存在 唯一的一个 被称作 “第一个” 的 数据元素

存在 唯一的一个 被称作 “最后一个” 的 数据元素

除第一个之外,结构中 每个元素 只有一个前驱

除最后一个之外,结构中 每个元素 只有一个后驱

术语

物理存储

一片连续的 存储地址 -> 顺序表

可非连续的 存储地址 -> 链式

单链表

双向链表

双向循环链表

顺序表

循环链表

一元多项式的表示与相加

有序表的合并

DevLog

相关文章

赞助商

阅读排行

n (n>=0)个数据特性相同的元素构成的有限序列称为线性表

存在唯一的一个被称作 “第一个” 的数据元素

存在唯一的一个被称作 “最后一个” 的数据元素

除第一个之外,结构中每个元素只有一个前驱

除最后一个之外,结构中每个元素只有一个后驱

一片连续的存储地址 -> 顺序表

可非连续的存储地址 -> 链式