数据结构【链表】_已知有以下的静态链表,问: 1)该链表表达的数据序列是怎样的?(3 分)

链表

• 1.单链表
• • 1.1概念与结构
  • • 1.1.1结点
    • 1.1.2链表的性质
    • 1.1.3链表的打印
  • 1.2实现单链表
  • 1.3链表的分类
• 2.双向链表
• • 2.1概念与结构
  • 2.2实现双链表
• 3.顺序表与链表的分析

1.单链表

1.1概念与结构

概念：链表是⼀种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.1.1结点

结点的组成主要有两个部分：当前结点要保存的数据和保存下⼀个结点的地址（指针变量）。

1.1.2链表的性质

• 链式机构在逻辑上是连续的，在物理结构上不⼀定连续。
• 结点⼀般是从堆上申请的。
• 从堆上申请来的空间，每次申请的空间可能连续，可能不连续。

struct SlistNode{int date; //结点数据struct SlistNode* next; //指针变量用保存下一个结点的地址};

1.1.3链表的打印

给定的链表的结构，实现链表从头到尾的打印

void SLTPrint(SLTNode* phead){SLTNode* pcur = phead;while (pcur){printf(\"%d\", pcur->data);pcur = pcur->next;}printf(\"\\n\");}

1.2实现单链表

typedef int SLTDataType;typedef struct SListNode{SLTDataType data; //结点数据struct SListNode* next; //指针保存下⼀个结点的地址}SLTNode;void SLTPrint(SLTNode* phead);//头部插⼊删除/尾部插⼊删除void SLTPushBack(SLTNode** pphead, SLTDataType x);void SLTPushFront(SLTNode** pphead, SLTDataType x);void SLTPopBack(SLTNode** pphead);void SLTPopFront(SLTNode** pphead);//查找SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插⼊数据void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//删除pos结点void SLTErase(SLTNode** pphead, SLTNode* pos);//在指定位置之后插⼊数据void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos之后的结点void SLTEraseAfter(SLTNode* pos);//销毁链表void SListDestroy(SLTNode** pphead);

1.3链表的分类

链表的结构非常多样，以下情况组合起来就有8种链表结构：

• 单向或者双向
• 带头或不带头
• 循环或不循环
  （2 x 2 x 2）=8种

2.双向链表

2.1概念与结构

2.2实现双链表

typedef int LTDataType;typedef struct ListNode{struct ListNode* next; //指针保存下⼀个结点的地址struct ListNode* prev; //指针保存前⼀个结点的地址LTDataType data;}LTNode;//void LTInit(LTNode** pphead);LTNode* LTInit();void LTDestroy(LTNode* phead);void LTPrint(LTNode* phead);bool LTEmpty(LTNode* phead);void LTPushBack(LTNode* phead, LTDataType x);void LTPopBack(LTNode* phead);void LTPushFront(LTNode* phead, LTDataType x);void LTPopFront(LTNode* phead);//在pos位置之后插⼊数据void LTInsert(LTNode* pos, LTDataType x);void LTErase(LTNode* pos);LTNode* LTFind(LTNode* phead, LTDataType x);

3.顺序表与链表的分析