CC ++循环链接数据结构

示例3.1？有一个单个链表L（至少一个节点），头节点的指针为head，编写一个函数以求L的反转，即最后一个节点成为第一个节点，原始倒数第二个节点成为第二个节点. .. 等等. 解决方案: 此问题中使用的算法是从头到尾遍历单链列表L，并设置3个附加指针p，q，r，p指向当前正在处理的节点，q指向p的下一个节点和r到q. 设置下一个节点q，r的作用是防止指针反转时丢失下一个节点. 使用这三个指针，可以轻松实现指针的反转. 最后，第一个节点的下一个字段设置为NULL，并且头指针指向最后一个节点，这符合此问题的要求. typedef struct node {数据类型数据； struct node * next;} *链接列表； void invert（linklist head）{linklist p，q，r; p =头q = p->接下来； while（q！= NULL）/ *当没有后继者时停止* / {r = q-> next; q->下一步= p; p = q; q = r;} head-> next = NULL; head = p;}表示方法使用一维数组. 为了形象起见，堆栈通常在图中垂直绘制.

？将该数组命名为data，下标的下限为0，上限为n. ？一般需要使用变量top来记录当前栈顶的下标值，top也称为栈指针. 6吗在C中，通常以以下方式定义5顺序堆栈结构: 4 #define N 30 3 Typedef结构堆栈2 {datatype data [N]; 1个int顶部； 0} sqstack;在此示例中，top = 4D CBA datatop#define N 30 1.推入Typedef结构堆栈推入堆栈的主要操作是首先将堆栈指向{datatype data [N];引脚加1；然后将推入的元素放在堆栈Int顶部；指针指示的位置. } sqstack; void push（sqstack * p，数据类型x）假定指针P用于表示堆栈，并且堆栈上元素的值为x，则可以按如下方式获得堆栈函数{if: （p-> top = = N-1）printf（“堆栈溢出！\ n”）； / *显示堆栈的完整信息* /否则{{p-> top）++;第二，堆栈的操作#define N 30 Typedef struct stack {数据类型数据[N]; Int top;} sqstack; void pop（sqstack * p）{if（p-> top == -1）printf（“ empty stack！\ n”）; / *堆栈为空以显示相应的信息* /否则{x = p-> data [p-> top]; （p->顶部）-; / *将堆栈顶部向下移动* /}返回x;} 2 .Pop（Pop）弹出堆栈时，首先将堆栈顶部元素的值分配给变量，以供以后计算；然后将顶部指针递减1，以向下移动堆栈的顶部.

假设指定的变量是x，则弹出堆栈的函数如下: chain stack？链堆栈是堆栈的链接存储表示. 它是一个单链接列表，仅允许在表头进行插入和删除操作. 它与普通的单链表没有什么不同，除了头指针头被重命名为堆栈上的顶部指针. top∧堆栈堆叠算法？用于将值x的节点插入顶部指针为top的链堆栈中的算法: void push（链接列表top，数据类型x）{linklist s; s =新节点； //创建一个节点指针* / s-> data = x; s-> next = top;链堆栈的弹出算法int pop（链接列表顶部）{int x;链接列表p; if（top = = NULL）cout <<“堆栈为空！”;其他{x = top->数据； p =顶部；顶部=顶部->下一步;删除p; return x;}} 3.3循环和双向链表？循环链表（循环链表）是一种链表，单链表表末尾的原始空指针指向头节点，它成为循环链表.

？循环链表不占用很多存储单元c/c++链表，但是可以从循环链表的任何节点访问此链表的每个节点，因为在访问列表的尾节点后，它可以返回到头节点. . 头例3.2？有两个循环单链接列表. 头指针分为head1和head2. 在编写了将链接列表head2链接到链接列表head1的函数之后，链接列表保持为循环链接列表的形式. head1head2a1b1a2b2anbn？解决方案: 首先找到两个链表的尾部c/c++链表，将head2放入链表head1的尾部，链接两个链表，然后将head1放入原始head2链表的尾部，以形成新的圆形链表. 例3.2 2算法链接（linklist head1，head2）{linklist p，q; p = head1;而（p-> next！= Head1）p = p-> next; q = head2;而（q-> next！= head2）q = q-> next; p-> next = head2; q-> next = head1;} 1.带有指针的圆形链表？通常，在循环链表的头节点之前添加一个空节点，也称为空头节点. ？时空表的头部的指针指向自身，如下图所示是一个空的循环链表.

？除了指向空标头节点的指针以外的数据字段都是无用的，但是为了将此节点与常规节点区分开，通常会为其分配一个特殊数据以将其与常规节点进行比较. 区别. 头2. 带尾指针的圆形链表？另一种方法是设置尾指针而不是头指针，因此查找头节点或尾节点非常方便. 因为尾节点由尾指针后方指示，所以头节点的位置为后->下一个->下一个. Rearrear第二，双向链表？除了双向链接列表中的每个节点之外，还有指向上一个节点的指针. 链表中有两个方向不同的链接，因此从某个节点可以双向访问. 双向链表的节点形式为: prioritydatanext，其中链域的priority和next分别指向该节点的直接前任和直接后任. ？如果循环链表的节点再次使用双指针，则它将变为双循环链表. 虽然头？双链表比单链表占用更多的存储单元，插入和删除操作以及查找节点的前任和后任非常方便. 双向链表结构是对称结构. 如果指针p指向双向链表中的一个节点，则双向链表的对称性可以用以下公式表示: p =（p->上一个）-> next =（p->上一个）- >优先级节点* p的地址既存储在其前任节点*的后继指针字段中（p->优先级），又存储在其后继节点*之前（p->下一个）趋势指针字段中.

1. 插入双链表？假设您要在p指向的节点前面插入新节点* q，则需要修改4个指针: q-> prior = p-> prior； q->下一步= p; （p->上一个）->下一个= q; p->先验= q; p①q③④②2.删除双链表？如果p指向要删除的节点，则删除该节点的步骤为: （p->上一个）->下一个= p->下一个； （p->下一个）->优先级= p->优先级;？这两个语句的执行顺序可以颠倒. 执行完这两个语句后，可以调用delete p，* p节点释放. p①②返回3.4表示稀疏矩阵的交联列表. 在交叉链接列表中，矩阵的每个非零元素都对应于包含五个字段的节点，这五个字段是稀疏矩阵中非零元素的行号. ，列号，元素值和两个指针，其中之一指向同一列中下一个非零元素的节点，另一个指针指向同一行右侧的非零元素的节点. 行号列号值向下指针右指针？每行的非零元素节点被链接到一个圆形链接列表中，而每一列的非零元素节点被链接到一个圆形链接列表中，形成一个十字形的链接结构. ？对于循环链表的每一行和每一列，都有一个空的头节点，以方便元素的插入和删除.

这些空标题节点的行号和列号标记为零，以使其与其他节点区分开. 整个交叉链接列表的总头节点为空. 在通用节点上标有行号和列号的地方，此节点用于指示矩阵的行数m和列数n. ？有一个指针HM指向此总空标题节点. 示例: 稀疏矩阵M及其对应的交联列表如图所示. ？ 8？ 0？ M ?? 4？ 0 ??? 0 0 0 7 00？ 3 0？ 5 09 ？？ 0？ 0 ?? 0 ?? 6 ?? 5 4 HMH1 0 0H2 0 0H3 0 0H4 0 0H5 0 00 0 H11 1 81 4 90 0 H22 3 -30 0 H33 1 40 0 H44 2 74 3 -50 0 H55 4 -6空标头节点的结构？由于每一列和每一行的空标题节点中的行数和列号均为零，并且空标题的每一列仅使用向下指针，而空标题的每一行仅使用右指针，因此这组空标题节点可以一起使用. 由于值字段也无用，因此可以将空头节点的值字段更改为指针字段，并且每个空头节点也可以链接到循环链接列表中. 自链接行号列号向下的指针指向右汇总的指针？单链表？循环链表？双向链表？双向链接链表？交叉链接列表返回

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-154517-1.html