数据结构与算法（C语言严蔚敏）二

标签：结点 C语言 int next 链表严蔚敏数据结构节点线性表

前言

有误的地方还请大家指出来，我会一一改正，也会在评论区置顶更正的记录；
如果是因为不同的教材导致的错误，请把教材名、著作者、版次一并提供，供大家一起督促一起学习，本篇参考的教材是《数据结构与算法 (C语言) 严蔚敏》，这也是我大学教材。
程序的逻辑大同小异，本篇只是针对参考的教材做出的记录，不具有代表性。
保持良好的网络教学环境，请不要随意断章取义、复制粘贴。

第二章线性表

1. 线性表的概念、顺序表、线性表的链式存储

线性表（Linear List）的概念

线性表是 n 个数据元素的有限序列，可表示为：（a1, a2, …, an）。
线性表的特征：

n 个元素必须具有相同特性（同一类型），相邻元素之间存在序偶关系。
元素个数 n 为表长度，n = 0 为空表。
1<i<n时：⚫ai的直接前驱是ai-1，（a1无直接前驱）；⚫ai的直接后继是ai+1，（an无直接后继）
元素同构，且不能出现缺项

线性表的顺序存储结构（顺序表）

线性表的顺序存储结构（顺序表）：是一组地址连续的存储单元，依次存储其数据元素的结构。

顺序表的特点：逻辑上相邻；物理地址上相邻；随机存取。
顺序表的特点：可用一维数组实现。
顺序表元素地址的计算方法：

线性表的链式结构

线性表的链式存储结构：是一组地址不连续的存储单元，存储其数据元素及数据元素地址的结构。

头指针：指链表中第一个结点的存储位置的指针；其具有标识作用，是链表的必要元素。
头结点：放在第一个元素结点之前，其数据域一般无意义（也可存放链表的长度，或用做监视哨）；注意：头结点不是链表所必需的。
首元结点：是第一个元素的结点。

2. 线性表的顺序结构

线性表定义

#include "stdio.h"
#include "stdlib.h"
#define OK 1
#define ERROR 0
#define OVERFLOW -1
const MAXSIZE =3; //初始分配量
const INCREMENT=2; //分配的增加量
typedef int ElemType; //自定义元素类型
typedef int Status; //自定义返回值

typedef struct { //空间、长度、容量三个要素
  ElemType *elem; //存储元素数组(线性表的基地址，即动态分配数组的指针）
  int length; //线性表当前长度
  int listsize; //当前分配的数组容量
}SqList;

基操一：初始化操作：配置表空间、长度和容量

Status InitList(SqList* L) {
  L->elem = (int*)malloc(MAXSIZE * sizeof(ElemType));
  if (L->elem == NULL)
    exit(OVERFLOW);
  L->length = 0;
  L->listsize = MAXSIZE;
  return OK;
}

基操二：查找操作 T(n)=O(n)

逻辑：略

int LocateElem(SqList L, ElemType e)
{
  int i;
  for (i = 0; i < L.length; i++)
    if (L.elem[i] == e)
      return i;
  return ERROR;
}

基操三：插入操作 T(n)=O(n)

插入逻辑：先判断表状态，比如表是否已经满了，满的话进行扩容，不满的话先依次后移元素把插入位置，到插入位置后进行插入操作。

数据结构与算法（C语言严蔚敏）二_链表

Status InsertList(SqList* L, int i, ElemType e) {
  //将新元素e插入到顺序表L的第i个位置上
  ElemType* p;
  int j;
  if (i < 1 || i > L->length + 1) return ERROR;
  if (L->length >= L->listsize) {//若顺序表已满，则需扩充空间
    p = (ElemType*)realloc(L->elem, (L->listsize + INCREMENT) *
      sizeof(ElemType));
    if (!p) exit(OVERFLOW);
    L->elem = p;
    L->listsize += INCREMENT;
  }
  for (j = L->length - 1; j >= i - 1; --j)
    L->elem[j + 1] = L->elem[j];
  L->elem[j + 1] = e; //插入新元素
  L->length++;
  return OK;
}//InsertList

基操四：删除操作 T(n)=O(n)

逻辑：被删除元素拿出来后，从 i-1 开始把 i-1 后的表元素前移。

数据结构与算法（C语言严蔚敏）二_链表_02

Status Del_List2(SqList* L, int i, ElemType* e)
// 在顺序表L中删除第i个元素，被删元素用参数e带回 （P24）
{
  int j;
  //printf("准备删除，顺序表长度为：%4d\n",L->length);
  if (i<1 || i>L->length) return ERROR;
  *e = L->elem[i - 1]; //被删元素用参数e带回
  for (j = i; j < L->length; j++)
    L->elem[j - 1] = L->elem[j];
  --L->length;
  return OK;
}

3. 单链表

链式结构的定义

typedef struct LNode {
  ElemType data; //数据域
  struct LNode* next; //指针域
}LNode, * LinkList;

单链表的初始化

//单链表的初始化
Status InitLinkL(LinkList* Head) {
  //建立头结点，next指针为空
  *Head = (LinkList)malloc(sizeof(LNode));
  if (!Head) return ERROR;
  (*Head)->next = NULL;
  return OK;
}

创建单链表（头插法、尾插法）

头插法：在链表的头部插入结点建立单链表，数据读入顺序和线性表中的逻辑顺序正好相反。

s 是新结点指针，L 是头结点指针

s->next = L->next;
L->next = s;

尾插法：在链表的尾部插入结点建立单链表，数据读入顺序和线性表中的逻辑顺序正好相同。

//找到尾节点P
p = L;
while (p->next != NULL)
  p = p->next;
p->next = s;
s->next = NULL；

销毁单链表

Status DestroyL(LinkList L) {
  LinkList pre = L, p = L->next; //pre指向p的前驱节点
  while (p != NULL) //扫描单链表L
  {
    free(pre); //释放pre节点
    pre = p; // pre、p同步后移一个节点
    p = pre->next;
  }
  free(pre); //循环结束,p为null, pre指向尾节点,释放它
  return OK;
}

求链表长度

int Length_L(LinkList *L)
{ // L 为链表的头指针，本函数返回 L 所指链表的长度
  LNode* p;
  int  k;
  p = L; k = 0;
  while (p != NULL)
  {
    k++; // k 计非空结点数
    p = p->next;
  }//while
  return k;
}

单链表的查找

LNode* Locate_L(LinkList *L, ElemType e)
{
  LNode* p;
  p = L;
  while (p && p->data != e)
    p = p->next;
  return p;
}

按元素值 e 查找

int LocateElemL(LinkList L, ElemType e)
{

  LinkList p = L->next; //p指向开始节点，i为1
  int j = 1,i=0;
  while (p != NULL && p->data != e) {
    p = p->next; //查找data值为e的节点，序号为i
    i++;
  }
  if (p == NULL) //不存在元素为e的节点,返回0
    return 0;
  else //存在元素值为e的节点，返回i
    return i;
}

单链表的插入

在带头结点的链表节点P之前插入结点 s 的算法思路。

q=L
while(q->next!=p)
  q=q->next
q->next=s
s->next=p

在不带头节点的链表节点P之前插入节点 s 的算法思路。

输入：链表L，节点P，节点s; 在节点p之前插入节点s
 输出：插入节点后的链表
 算法思路：
  ◼ 判断p是否是首节点 if (P == L)
  ◼ 如果p是首节点
    s->next = L; L = s;
  ◼ 如果p不是首节点
    寻找节点p的前驱（从首节点开始找）
      q = L; while (q->next != p) q = q->next;
    在节点p之前插入s
      q->next = s; s->next = p;

单链表的插入

Status InsertLinkL(LinkList L, int i, ElemType e) {
  //在带头结点的单链表L中第i个位置之前插入元素e
  LinkList s, p = L;
  int k = 0; //初始化，p指向头结点，k为计数器
  while (p->next != NULL && k < i - 1) { //定位过程
    //定位指针p指向第i-1个元素或p为空
    p = p->next;
    ++k;
  }
  if ((!p->next && k < i - 1) || k > i - 1) return ERROR; //定位插入点失败
  if (!(s = (LinkList)malloc(sizeof(LNode)))) //申请元素e的结点空间
    return OVERFLOW; //内存无空闲单元，无法申请到空间
  s->data = e;
  s->next = p->next; // 将新结点s插入到链表中
  p->next = s; // 能与上句交换位置么？
  return OK;
} // InsertList1

单链表的删除结点

删除值为e的节点

Status Del_LinkL1(LinkList L, int i, ElemType* e) {
  //在带头结点的单链表L中，删除第i个元素，并由e返回其值
  int k = 0; //初始化，p指向头结点，k为计数器
  LinkList q, p = L;
  while (p->next != NULL && k < i - 1) {
    p = p->next; ++k;
    //逐一移动指针p，直到p指向第i-1个结点或p为空
  }
  if (!p->next || k > i - 1) return ERROR; //无法删除
  q = p->next; // 令q指向待删除的元素结点；
  p->next = q->next; // 将q结点从链表中删除
  *e = q->data;
  free(q);
  return OK;
}

单链表的遍历输出所有结点

void PrintLinkL(LinkList L)
// 输出带头结点的单链表中所有结点的键值
{
  LinkList p;
  p = L->next;
  printf("Head→");
  while (p) {
    printf("%d→", p->data);
    p = p->next; // 遍历下一个结点
  }
  printf("∧\n");
}

单链表的获取第 i 个元素的值

#include <stdbool.h>
bool GetElemL(LinkList L, int i, ElemType e)
{
  LinkList p = L;
  int j = 0;
  while (j < i && p != NULL) {
    j++;
    p = p->next; // 遍历下一个结点
  }
  if (p == NULL) //不存在第i个数据节点，返回false
    return false;
  else
  {
    e = p->data;
    return true;
  }
}

4. 循环链表

循环链表的定义

/*声明一个链表节点*/
typedef struct Node
{
  int number;//数据域，存储编号数值
  struct Node* next;//指针域，指向下一个节点
}Node;

创建循环链表

创建

/*创建链表节点的函数*/
Node * CreatNode(int x)
{
  Node* p;
  p = (Node*)malloc(sizeof(Node));
  p->number = x;//将链表节点的数据域赋值为编号
  p->next = NULL;
  return p;
}

创建环形链表，存放整数1到 n

Node* CreatJoseph(int n)
{
  Node* head, * p, * q;
  int i;
  for (i = 1; i <= n; i++)
  {
    p = CreatNode(i); //创建链表节点，并完成赋值
    if (i == 1) //如果是头结点
      head = p;
    else //不是头结点，则指向下一个节点
      q->next = p;
    q = p;
  }
  q->next = head;//末尾节点指向头结点，构成循环链表
  return head;
}

模拟约瑟夫环

每到一个数，从环形链表中删除，并打印出来

void RunJoseph(int n, int m)
{
  Node* p, * q;
  p = CreatJoseph(n);//创建循环链表形式的约瑟夫环
  int i, count = 0; //记录次数
  while (p->next != p)//循环条件，当前链表数目大于1
  {
    for (i = 1; i < m - 1; i++)//开始计数
      p = p->next;
    //第m个人出圈
    q = p->next;
    p->next = q->next;
    p = p->next;
    count++;
    printf("第%d次出圈的元素为%d--\n", count, q->number);//输出序号
    free(q);
  }
  printf("\n最后剩下的数为：%d\n", p->number);
}

5. 双向链表

定义双向链表

typedef struct Dlnode {
  ElemType element;
  Dlnode* prior, * next;
} Dlnode, * Dlinklist;

双向链表中结点的插入

算法思路：
① s->prior=p->prior; ② p->prior->next=s;
③ s->next=p; ④ p->prior=s;

结点的删除

void delete_DL(Dlnode* p)
{
  p->prior->next = p->next;
  p->next->prior = p->prior;
  delete p;
}

结束
Thanks♪(･ω･)ﾉ感谢支持！！！

标签：结点,C语言,int,next,链表,严蔚敏,数据结构,节点,线性表
From： https://blog.51cto.com/u_15151327/5981908

数据结构与算法（C语言严蔚敏）二

前言

目录

第二章线性表

1. 线性表的概念、顺序表、线性表的链式存储

线性表（Linear List）的概念

线性表的顺序存储结构（顺序表）

线性表的链式结构

2. 线性表的顺序结构

线性表定义

基操一：初始化操作：配置表空间、长度和容量

基操二：查找操作 T(n)=O(n)

基操三：插入操作 T(n)=O(n)

基操四：删除操作 T(n)=O(n)

3. 单链表

链式结构的定义

单链表的初始化

创建单链表（头插法、尾插法）

销毁单链表

求链表长度

单链表的查找

单链表的插入

单链表的删除结点

单链表的遍历输出所有结点

单链表的获取第 i 个元素的值

4. 循环链表

循环链表的定义

创建循环链表

模拟约瑟夫环

5. 双向链表

定义双向链表

双向链表中结点的插入

结点的删除

相关文章

赞助商

阅读排行

数据结构与算法（C语言 严蔚敏）二

前言

目录

第二章 线性表

1. 线性表的概念、顺序表、线性表的链式存储

线性表（Linear List）的概念

线性表的顺序存储结构（顺序表）

线性表的链式结构

2. 线性表的顺序结构

线性表定义

基操一：初始化操作：配置表空间、长度和容量

基操二：查找操作 T(n)=O(n)

基操三：插入操作 T(n)=O(n)

基操四：删除操作 T(n)=O(n)

3. 单链表

链式结构的定义

单链表的初始化

创建单链表（头插法、尾插法）

销毁单链表

求链表长度

单链表的查找

单链表的插入

单链表的删除结点

单链表的遍历输出所有结点

单链表的获取第 i 个元素的值

4. 循环链表

循环链表的定义

创建循环链表

模拟约瑟夫环

5. 双向链表

定义双向链表

双向链表中结点的插入

结点的删除

相关文章

赞助商

阅读排行

数据结构与算法（C语言严蔚敏）二

第二章线性表