第十天：循环链表，栈与队列

瓶子的跋涉 2023-01-19

314

循环链表：是一种首尾相连的链表（表中最后一个结点的指针域指向头结点，整个链表形成一个环）。判断循环链表终止条件从单链表的判断为空到判断是否等于头指针

优点：从表中任一结点出发均可找到表中其他结点

双向链表：在单链表的每个结点里再添加一个指向其直接前驱的指针域prior，这样链表中就形成了有两个方向不同的链，故称为双向链表

//结构体
typedef struct DulNode
{
  ElemType data;
  struct DulNode* prior, * next;
}DulNode,*DuLinklist;

双向循环链表：和单链的循环表类似，双向链表也可以有循环表

让头结点的前驱指针指向链表的最后一个结点
让最后一个结点的后继指针指向头结点
双向链表具有对称性

双向链表的插入：

DulNode* GetElem_Dul(DuLinklist L, int i)
{
  DulNode* p;
  p = L->next;
  int j = 1;
  while (p && j < i) 向后扫描，直到p指向第i个元素或p为空
  {
    p = p->next;
    ++j;
  }
  if (!p || j > i) 第i个元素不存在
    return ERROR;
  return p;
}
//双向循环链表的插入
int ListInsert_Dul(DuLinklist& L, int i, ElemType e)
{
  ElemType m;
  DulNode* p;
  if(!(p=GetElem_Dul(L,i)))
    return ERROR;
  DulNode* s;
  s = (DulNode*)malloc(sizeof(DulNode));
  s->prior = p->prior;
  p->prior->next = s;
  s->next = p;
  p->next = s;
  return OK;
}

双向链表的删除;

//双向链表的删除,删除带头结点的双向循环链表L的第i个元素，并用e返回
int ListDelete_Dul(DuLinklist& L, int i, ElemType& e)
{
  DulNode* p;
  if (!(p = GetElem_Dul(L, i)))
    return ERROR;
  e = p->data;
  p->prior->next = p->next;
  p->next->prior = p->prior;
  free(p);
  return OK;
}

顺序表和链表的比较

链式存储结构的优点：

结点空间可以动态申请和释放
数据元素的逻辑次序靠结点的指针来表示，插入和删除不需要移动数据元素

链式存储结构的缺点

存储密度小，每个结点的指针域需额外占用存储空间，当每个结点的数据域所占字节不多时，指针域所占存储空间的比重显得很大。（存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比）
链式存储结构是非随机存取结构，对任一结点的操作都要从头指针依托指针链查找到该结点，增加了算法复杂度。

线性表的合并

// 在单链表的编码环境
void Union(LinkList& la, LinkList lb)
{
  int e;
  int la_len =ListLength(la);
  int lb_len = ListLength(lb);
  for (int i = 1; i < lb_len; i++)
  {
    GetElem_L(lb, i, e);
    if (!LocateElem(la, e))
    {
      ListInsert_L(la, ++la_len, e);
    }
  }
}

有序表的合并

有序表的合并:已知线性表la和lb中的数据元素按值非递减有序排列，现要求将la和lb归并为一个新的线性表lc，且lc中的数据元素仍按值非递减有序排列

算法步骤：

创建一个空表lc
依次从la到lb中“摘取”元素值较小的结点插入到lc表的最后，直至其中一个表边空为止
继续将la或lb其中一个表的剩余结点插入在lc表的最后

顺序表的实现:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>


#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define List_INIT_SIZE 10  顺序表的大小
typedef int Status;
typedef int ElemType;
typedef struct SqList
{
  ElemType* elem;
  int length;
};
Status InitList_Sq(struct SqList& L)
{
  L.elem = (ElemType*)malloc(sizeof(ElemType) * List_INIT_SIZE);
  if (!L.elem)
    exit(OVERFLOW); 退出程序函数，为1异常退出，0正常退出
  L.length = 0;
  return OK;
}
//返回线性表的长度
int GetLength(struct SqList L)
{
  return L.length;
}
Status List_voluation(struct SqList& L, ElemType e)
{
  L.elem[L.length] = e;
  L.length++;      表长+1
  return OK;
}
void MergeList_sq(SqList LA, SqList LB, SqList& LC)
{
  ElemType* pa = LA.elem;
  ElemType* pb = LB.elem;
  LC.length = LA.length + LB.length;
  LC.elem = (ElemType*)malloc(sizeof(ElemType) * LC.length);
  ElemType* pc = LC.elem;
  ElemType* pa_last = LA.elem + LA.length - 1;
  ElemType* pb_last = LB.elem + LB.length - 1;
  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++;
  }


}






int main(void)
{
  int n;    存储用户输入的值
  int i;
  SqList LA;  合并表1
  SqList LB;  合并表2
  InitList_Sq(LA);
  InitList_Sq(LB);
  printf("请问顺序表LA赋值：");
  for (i = 0; i < 5; i++)
  {
    scanf("%d", &n);
    List_voluation(LA, n);
  }
  printf("\n");
  printf("请问顺序表LB赋值：");
  for (i = 0; i < 3; i++)
  {
    scanf("%d", &n);
    List_voluation(LB, n);
  }
  printf("\n");
  SqList LC; 合并空间
  MergeList_sq(LA, LB, LC);
  int j;
  for (j = 0; j < LC.length; j++)
  {
    printf("%d ", LC.elem[j]);
  }
  printf("\n");
  return 0;
}

输入与输出结果

请问顺序表LA赋值：1 5 9 25 64 
请问顺序表LB赋值：7 9 99
1 5 7 9 9 25 64 99

顺序链表的实现:

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#define List_INIT_SIZE 100  顺序表的大小
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;   函数的类型，其值是函数结果的状态代码
typedef int ElemType;


typedef struct Lnode  声明单链表的结构类型
{
  ElemType data;    数据域
  struct Lnode* next;    下一个结点的指针域，嵌套定义
}Lnode, * LinkList;  LinkList为指向结构体Lnode的指针类型


//单链表初始化
Status InitList(LinkList& L)
{
  L = (LinkList)malloc(sizeof(Lnode)); 或者用C++: new Lnode
  L->next = NULL;  /下一个结点为空
  return OK;
}






//返回长度值
int ListLength(Lnode* L)
{
  LinkList p;
  p = L->next;
  int length = 0;
  while (p)
  {
    length++;
    p = p->next;
  }
  return length;
}






//尾插法
void CreateList_R(LinkList& L, int n)
{
  Lnode* r;
  L = (Lnode*)malloc(sizeof(Lnode));
  L->next = NULL;
  r = L;
  for (int i = 0; i < n; i++)
  {
    Lnode* p;
    p = (Lnode*)malloc(sizeof(Lnode));
    scanf("%d", &p->data);
    p->next = NULL;
    r->next = p;
    r = p;
  }
}


//顺序链表的合并
void seq_uion(LinkList la, LinkList lb,LinkList &lc)
{
  LinkList p = la->next; //存入p
  LinkList q = lb->next; 
  LinkList c = lc;
  while(p&&q) //当任何一个链表变为空
  {
    if (p->data <= q->data)    //先将小的值插入，尾插
    {
      c->next = p;
      c = p;
      p = p->next;
    }
    else  
    {
      c->next = q;
      c = q;
      q = q->next;
    }
  }
  c->next = p ? p : q; //将最后的为输入完毕的全部加入链表
}
void Print_seq(LinkList L)
{
  printf("输出合并后的顺序链表:\n");
  L = L->next;
  for (int i = 0; i < ListLength(L); i++)
  {
    printf("%d ", L->data);
    L = L->next;
  }
}


int main(void)
{
  LinkList la;  //相当于Lnode* L;
  LinkList lb;
  LinkList lc;
  printf("la数据5个，用空格隔开:");
  CreateList_R(la, 5); //头插法
  printf("lb数据4个，用空格隔开:");
  CreateList_R(lb, 4);
  InitList(lc);
  seq_uion(la, lb, lc);
  Print_seq(lc);
  return 0;
}

栈和队列是限定插入和删除只能在表的“端点"进行的线性表。

栈

栈：后进先出,插入和删除限定在一端(通常为表尾)

后进先出LIFO

表尾即an端称为栈顶Top

表头即a1端称为栈底Base

插入元素到栈顶（即表尾)的操作称为入栈或压入 PUSH

从栈顶（即表尾)删除最后一个元素的操作，称为出栈或弹出 POP

InitStack(&S) //初始化操作
DestoryStack(&S) //销毁栈操作
StackEmpty(S) //判定S是否为空栈,若存在返回TRUE，否则FALSE
StackLength(S) 求栈的长度，返回S的元素个数
GetTop(S,&e)取栈顶元素用e返回栈顶元素
ClearStack(&S) 栈置空操作
Push(&S,e) 入栈操作，插入元素e为新的栈顶元素
Pop(&S,&e) 删除栈顶元素an，并用e返回其值

顺序栈

使用数组作为顺序栈存储方式的特点：

简单，方便，但易产生溢出

上溢（overflow）:栈已经满，又要压入元素
下溢（underflow）:栈已经满，还要弹出元素

栈的相关操作：

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100  //顺序表的大小
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;   //函数的类型，其值是函数结果的状态代码
typedef int ElemType;


typedef struct 
{
  ElemType* base;
  ElemType* top;
  int stacksize;  //栈可用最大容量
}SqStack;
Status InitStack(SqStack* &S)
{
  S->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
  if (!S->base)
    exit(OVERFLOW);
  S->top = S->base;
  S->stacksize = MAXSIZE;
}
Status StackEmpty(SqStack* S)
{
  if (S->top == S->base)
    return TRUE;
  else
    return FALSE;
}
int StackLength(SqStack* S)
{
  return S->top - S->base;
}
//销毁顺序栈
Status DestoryStack(SqStack*& S)
{
  if (S->base)
  {
    free(S->base);
    S->stacksize = 0;
    S->base = S->top = NULL;
  }
  return OK;
}
//入栈
Status Push(SqStack* &S, ElemType e)
{
  if (S->top - S->base == S->stacksize)
    return ERROR;
  *S->top++ = e;
  /*相当于
  *S->top=e;
  S->top++*/
  return OK;
}
//出栈
Status Pop(SqStack*& S, ElemType& e)
{
  //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
  if (S->top == S->base)
    return ERROR;
  e = *--S->top;
  //相当于
  //--S->top;
  //e=*S->top;


  return OK;
}
void Print_Stack(SqStack* S)
{
  while (S->base != S->top)
  {
    S->top--;
    printf("%d\n", *S->top);


  }




}
int main(void)
{
  SqStack* S;
  int e;
  int n;
  char ch;
  S = (SqStack*)malloc(sizeof(SqStack));
  InitStack(S);
  //StackEmpty(S);
  //DestoryStack(S);
  printf("入栈操作：请输入你要入栈的个数：");
  scanf("%d", &n);
  for (int j = 0; j < n; j++)
  {
    printf("请输入%d个栈", j + 1);
    scanf("%d", &e);
    Push(S, e);
    scanf("%c", &ch);
  }
  Print_Stack(S);
  printf("栈输出完毕！\n");
  return 0;
}

链栈

链栈：运算受限的单链表，只能在链表头部进行操作

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100  //顺序表的大小
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;   //函数的类型，其值是函数结果的状态代码
typedef int ElemType;
//链栈的结构体---受限的单链表
typedef struct StackNode
{
  ElemType data;
  struct StackNode* next;
}StackNode,*LinkStack;


Status InitStack(LinkStack& S)
{
  //构造空战
  S = NULL;
  return OK;
}
//判断链栈是否为空
Status StackEmpty(LinkStack S)
{
  if (S == NULL)
    return TRUE;
  else
    return FALSE;
}
//链栈的入栈
Status Push(LinkStack& S, ElemType e)
{
  LinkStack p;
  p = (StackNode*)malloc(sizeof(StackNode));  //生成新结点p
  p->data = e;      //将新结点数据置为e
  p->next = S;      //将新结点插入栈顶
  S = p;          //修改栈顶指针
  return OK;


}


//链栈的出栈
Status Pop(LinkStack& S, ElemType& e)
{
  LinkStack p;
  if (S == NULL)
    return ERROR;
  e = S->data;
  p = S;
  S = S->next;
  free(p);
  return OK;


}
//去栈顶元素
ElemType GetTop(LinkStack S)
{
  if (S != NULL)
    return S->data;
}


int main(void)
{
  LinkStack S;
  InitStack(S);
  StackEmpty(S);


  return 0;
}

队列

队列：仅在表尾进行插入操作，在表头进行删除操作的线性表

先进先出FIFO，解决排队问题

存储方式：以循环队列最为常见

脱机打印输出：按申请的先后顺序依次输出
多用户系统中，多个用户排成队，分时地循环使用CPU和主存
按用户的优先级排成多个队，每个优先级一个队列
实时控制系统中，信号按接收的先后顺序依次处理
网络电文传输，按到达的时间先后顺序依次进行

队空:front == rear;
队满: (rear+1)%MAXSIZA ==front;

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <malloc.h>
#define MAXSIZE 100  //顺序表的大小
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;   //函数的类型，其值是函数结果的状态代码
typedef int ElemType;


typedef struct SqQueue
{
  ElemType* base;//初始化动态分配存储空间
  int front;  //头指针
  int rear;   //尾指针
}SqQueue;
Status InitQueue(SqQueue* &Q)
{
  Q->base = (ElemType*)malloc(sizeof(ElemType) * MAXSIZE);
  if (!Q->base)
    exit(OVERFLOW);
  Q->front = Q->rear = 0;  //头指针，尾指针置为空，队列为空
  return OK;
}
//求队列的长度
int QueueLength(SqQueue* Q)
{
  return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;  //循环队列
}
//循环队列的入队
Status EnQueue(SqQueue*& Q, ElemType e)
{
  if ((Q->rear + 1) % MAXSIZE == Q->front)
    return ERROR;//堆满
  Q->base[Q->rear] = e;
  Q->rear = (Q->rear + 1) % MAXSIZE;
  return OK;
}
//出队
Status DeQueue(SqQueue*& Q, ElemType& e)
{
  if (Q->front == Q->rear)
    return ERROR;//队空
  e = Q->base[Q->front];    //保存队头元素
  Q->front = (Q->front + 1) % MAXSIZE;  //队头指针+1
  return OK;
}
ElemType GetHead(SqQueue* Q)
{
  if (Q->front != Q->rear)   //队列不为空
    return Q->base[Q->front];  //返回队头指针元素的值，队头指针不变
}




int main(void)
{
  SqQueue* S;


  return 0;
}

链表顺序表循环链表 printf next

文章转载自瓶子的跋涉，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

第十天：循环链表，栈与队列

评论