顺序表，链表，顺序栈，链栈，顺序队列，链栈

目录

• • 顺序表，链表，顺序栈，链栈，顺序队列，链栈
• 一、顺序表
• • 1.1 顺序表定义
  • 1.2 在顺序表第i个位置插入元素e
  • 1.3 在顺序表删除第i个元素
  • 1.4 在顺序表查找第1个值为e的元素
  • 1.5 在顺序表获取第i个元素的值赋值给e
• 二、链表
• • 2.1 单链表
  • • 2.1.1 单链表定义
    • 2.1.2 单链表初始化
    • 2.1.3 单链表头插法建表
    • 2.1.4 单链表尾插法建表
    • 2.1.5 单链表查找第i个位置元素
    • 2.1.6 单链表第i个位置前插入元素
    • 2.1.7 单链表第i个位置后插入元素
    • 2.1.8 单链表删除第i个元素
    • 2.1.9 单链表查找第1个与e相等的值
    • 2.1.10 单链表的长度
  • 2.2 双链表
  • • 2.2.1 双链表的定义
    • 2.2.2 双链表初始化
    • 2.2.3 双链表头插法建表
    • 2.2.4 双链表尾插法建表
    • 2.2.5 双链表查找第i个元素（等同单链表）
    • 2.2.6 双链表第i个元素后插入元素
    • 2.2.7 双链表删除第i个元素
• 三、栈
• • 3.1 顺序栈
  • • 3.1.1 顺序栈的定义
    • 3.1.2 顺序栈初始化
    • 3.1.3 顺序栈判断栈空
    • 3.1.4 顺序栈进栈
    • 3.1.5 顺序栈出栈
    • 3.1.6 顺序栈取栈顶元素
  • 3.2 链栈
  • • 3.2.1 链栈定义
    • 3.2.2 链栈初始化
    • 3.2.3 链栈判空
    • 3.2.4 链栈进栈
    • 3.2.5 链栈出栈
    • 3.2.6 链栈取栈顶元素
• 四、队列
• • 4.1 顺序队列
  • • 4.1.1 顺序队列的定义
    • 4.1.2 顺序队列的初始化
    • 4.1.3 顺序队列判空
    • 4.1.4 顺序（循环）队列入队
    • 4.1.5 顺序（循环）队列出队
    • 4.1.6 顺序队列取队头元素
  • 4.2 链队
  • • 4.2.1 链队定义
    • 4.2.2 链队初始化
    • 4.2.3 链队判空
    • 4.2.4 链队入队
    • 4.2.5 链队出队
    • 4.2.6 链队取队头元素

一、顺序表

1.1 顺序表定义

#include
#include #define MAX_SIZE 100
typedef struct
{int data[MAX_SIZE];int length;
}SqList;

1.2 在顺序表第i个位置插入元素e

//在顺序表的第i个位置插入一个元素e
void ListInsert(SqList *L, int i, int e)
{if (i < 1 || i > L->length + 1){return;}if (L->length >= MAX_size){return;}for (int j = L->length; j >= i; j--){L->data[j] = L->data[j - 1];}L->data[i - 1] = e;L->length++;
}

1.3 在顺序表删除第i个元素

//删除顺序表中第i个位置的元素
void ListDelete(SqList *L, int i, int *e)
{if (i < 1 || i > L->length){return;}(*e) = L->data[i - 1];for (int j = i; j < L->length; j++){L->data[j - 1] = L->data[j];}L->length--;
}

1.4 在顺序表查找第1个值为e的元素

//查找顺序表中第一个值为e的元素
int LocateElem(SqList L, int e)
{for (int i = 0; i < L.length; i++){if (L.data[i] == e){return i + 1;}}return 0;
}

1.5 在顺序表获取第i个元素的值赋值给e

//获取顺序表中第i个位置的元素
int GetElem(SqList L, int i, int *e)
{if (i < 1 || i > L.length){return 0;}(*e) = L.data[i - 1];return 1;
}

二、链表

2.1 单链表

2.1.1 单链表定义

typedef struct LNode {int data;struct LNode *next;
}LNode, *LinkList;

2.1.2 单链表初始化

//链表初始化
void InitList(LinkList *L)
{(*L) = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;
}

2.1.3 单链表头插法建表

//采用头插法建立单链表
void CreateListHead(LinkList *L)
{LinkList p;int n,x;printf("请输入链表的长度：");scanf("%d", &n);int i;for (i = 0; i < n; i++){p = (LinkList)malloc(sizeof(LNode));printf("请输入第%d个元素：", i + 1);scanf("%d", &x);p->data = x;p->next = (*L)->next;(*L)->next = p;}
}

2.1.4 单链表尾插法建表

//采用尾插法建立单链表
void CreateListTail(LinkList *L)
{LinkList p, r;int n, x;printf("请输入链表的长度：");scanf("%d", &n);int i;r = (*L);for (i = 0; i < n; i++){p = (LinkList)malloc(sizeof(LNode));printf("请输入第%d个元素：", i + 1);scanf("%d", &x);p->data = x;r->next = p;r = p;}r->next = NULL;
}

2.1.5 单链表查找第i个位置元素

//查找单链表中第i个位置的元素赋值给e
void ListGet(LinkList *L, int i, int *e)
{LinkList p;          //p指向第i个位置int j;p = (*L);               //p指向头节点j = 0;                  //j为计数器，从0开始while (p && j < i)      //寻找第i个位置{p = p->next;        //p指向下一个节点j++;                //计数器加1}if (!p || j > i)        //i小于1或者大于表长加1{return;}(*e) = p->data;             //将p的数据赋值给e
}

2.1.6 单链表第i个位置前插入元素

//在单链表中第i个位置前插入一个元素e
void ListPreInsert(LinkList *L, int i, int e)
{LinkList p, s;          //p指向第i个位置的前一个位置，s指向新插入的节点int j;p = (*L);               //p指向头节点j = 1;                  //j为计数器while (p && j < i)      //寻找第i个位置的前一个位置{p = p->next;        //p指向下一个节点j++;                //计数器加1}if (!p || j > i)        //i小于1或者大于表长加1{return;}s = (LinkList)malloc(sizeof(LNode));    //生成新节点s->data = e;                                //将e赋值给新节点s->next = p->next;                        //将p的后继赋值给s的后继p->next = s;                            //将s赋值给p的后继
}

2.1.7 单链表第i个位置后插入元素

//在单链表第i个位置后插入一个元素e
void ListPostInsert(LinkList *L, int i, int e)
{LinkList p, s;          //p指向第i个位置，s指向新插入的节点int j;p = (*L);               //p指向头节点j = 0;                  //j为计数器，从0开始while (p && j < i)      //寻找第i个位置{p = p->next;        //p指向下一个节点j++;                //计数器加1}if (!p || j > i)        //i小于1或者大于表长加1{return;}s = (LinkList)malloc(sizeof(LNode));    //生成新节点s->data = e;                                //将e赋值给新节点s->next = p->next;                        //将p的后继赋值给s的后继p->next = s;                            //将s赋值给p的后继
}

2.1.8 单链表删除第i个元素

//删除单链表中第i个位置的元素
void ListDelete(LinkList *L, int i, int *e)
{LinkList p, q;          //p指向第i个位置的前一个位置，q指向第i个位置int j;p = (*L);               //p指向头节点j = 1;                  //j为计数器while (p->next && j < i)      //寻找第i个位置的前一个位置{p = p->next;        //p指向下一个节点j++;                //计数器加1}if (!(p->next) || j > i)        //i小于1或者大于表长加1{return;						//删除位置不在链表范围内}q = p->next;                //q指向第i个位置p->next = q->next;          //将q的后继赋值给p的后继(*e) = q->data;             //将q的数据赋值给efree(q);            //释放q所指向的内存
}

2.1.9 单链表查找第1个与e相等的值

//查找单链表中第一个与e相等的元素
int ListLocate(LinkList *L, int e)
{LinkList p;          //p指向第i个位置int j;p = (*L);               //p指向头节点j = 0;                  //j为计数器，从0开始while (p && p->data != e)      //寻找第一个与e相等的元素{p = p->next;        //p指向下一个节点j++;                //计数器加1}if (!p)        //未找到{return -1;}return j;             //返回元素的位置
}

2.1.10 单链表的长度

//求单链表的长度
int ListLength(LinkList *L)
{LinkList p;          //p指向第i个位置int j;p = (*L);               //p指向头节点j = 0;                  //j为计数器，从0开始while (p){p = p->next;        //p指向下一个节点j++;                //计数器加1}return j;
}

2.2 双链表

2.2.1 双链表的定义

typedef struct DNode {int data;struct DNode *prior;struct DNode *next;
}DNode, *DLinkList;

2.2.2 双链表初始化

//初始化双链表
void InitDList(DLinkList *L)
{(*L) = (DLinkList)malloc(sizeof(DNode));(*L)->prior = NULL;(*L)->next = NULL;
}

2.2.3 双链表头插法建表

//头插法建立双链表
void CreateDListF(DLinkList *L)
{DLinkList p;int i,n,x;printf("请输入双链表的长度：");scanf("%d", &n);for (i = 0; i < n; i++){p = (DLinkList)malloc(sizeof(DNode));   //创建新节点printf("请输入第%d个元素：", i + 1);scanf("%d", &x);p->data = x;                                //将x赋值给新节点的数据域p->next = (*L)->next;                       //将头节点的后继赋值给新节点的后继if ((*L)->next){(*L)->next->prior = p;}(*L)->next = p;p->prior = (*L);}
}

2.2.4 双链表尾插法建表

//尾插法建立双链表
void CreateDListR(DLinkList *L)
{DLinkList p, r;int i, n, x;printf("请输入双链表的长度：");scanf("%d", &n);(*L) = (DLinkList)malloc(sizeof(DNode));(*L)->prior = NULL;(*L)->next = NULL;r = (*L);for (i = 0; i < n; i++){p = (DLinkList)malloc(sizeof(DNode));printf("请输入第%d个元素：", i + 1);scanf("%d", &x);p->data = x;r->next = p;p->prior = r;r = p;}r->next = NULL;
}

2.2.5 双链表查找第i个元素（等同单链表）

2.2.6 双链表第i个元素后插入元素

//在双链表的第i个位置后插入元素e
void DListInsert(DLinkList *L, int i, int e)
{DLinkList p, s;int j;p = (*L);j = 0;while (p && j < i){p = p->next;j++;}if (!p || j > i){return;}s = (DLinkList)malloc(sizeof(DNode));s->data = e;s->next = p->next;if (p->next){p->next->prior = s;}p->next = s;s->prior = p;
}

2.2.7 双链表删除第i个元素

//删除双链表的第i个位置的元素
void DListDelete(DLinkList *L, int i)
{DLinkList p;int j;p = (*L);j = 0;while (p && j < i){p = p->next;j++;}if (!p || j > i){return;}p->prior->next = p->next;if (p->next){p->next->prior = p->prior;}free(p);
}

三、栈

3.1 顺序栈

3.1.1 顺序栈的定义

#include
#include #define MAX_SIZE 100
//顺序栈
typedef struct {int data[MAX_SIZE];int top;
}SqStack;

3.1.2 顺序栈初始化

//初始化栈
void InitStack(SqStack *S)
{S->top = -1;
}

3.1.3 顺序栈判断栈空

//判断栈是否为空
int StackEmpty(SqStack S)
{if (S.top == -1){return 1;}else{return 0;}
}

3.1.4 顺序栈进栈

//进栈
int Push(SqStack *S, int x)
{if (S->top == MAX_SIZE - 1){return 0;}S->top++;S->data[S->top] = x;return 1;
}

3.1.5 顺序栈出栈

//出栈
int Pop(SqStack *S, int *x)
{if (S->top == -1){return 0;}*x = S->data[S->top];S->top--;return 1;
}

3.1.6 顺序栈取栈顶元素

//取栈顶元素
int GetTop(SqStack S, int *x)
{if (S.top == -1){return 0;}*x = S.data[S.top];return 1;
}

3.2 链栈

3.2.1 链栈定义

typedef struct StackNode {int data;struct StackNode *next;
}StackNode, *LinkStackPtr;

3.2.2 链栈初始化

//初始化
void InitStack(LinkStackPtr *S)
{*S = (LinkStackPtr)malloc(sizeof(StackNode));(*S)->next = NULL;
}

3.2.3 链栈判空

int StackEmpty(LinkStackPtr S)
{if (S->next== NULL){return 1;}else{return 0;}
}

3.2.4 链栈进栈

//进栈
int Push(LinkStackPtr *S, int x)
{LinkStackPtr p;p = (LinkStackPtr)malloc(sizeof(StackNode));p->data = x;p->next = (*S)->next;*S = p;return 1;
}

3.2.5 链栈出栈

//出栈
int Pop(LinkStackPtr *S, int *x)
{LinkStackPtr p;if (*S == NULL){return 0;}p = (*S)->next;*S = (*S)->next;*x = p->data;free(p);return 1;
}

3.2.6 链栈取栈顶元素

//取栈顶元素
int GetTop(LinkStackPtr S, int *x)
{if (S->next == NULL){return 0;}*x = S->next->data;return 1;
}

四、队列

4.1 顺序队列

4.1.1 顺序队列的定义

//顺序队列
typedef struct {int data[MAX_SIZE];int front;int rear;
}SqQueue;

4.1.2 顺序队列的初始化

//初始化队列
void InitQueue(SqQueue *Q)
{Q->front = Q->rear = 0;
}

4.1.3 顺序队列判空

//判断队列是否为空
int QueueEmpty(SqQueue Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}

4.1.4 顺序（循环）队列入队

//入队
int EnQueue(SqQueue *Q, int x)
{if ((Q->rear + 1) % MAX_SIZE == Q->front){return 0;}Q->data[Q->rear] = x;Q->rear = (Q->rear + 1) % MAX_SIZE;return 1;
}

4.1.5 顺序（循环）队列出队

//出队
int DeQueue(SqQueue *Q, int *x)
{if (Q->front == Q->rear){return 0;}*x = Q->data[Q->front];Q->front = (Q->front + 1) % MAX_SIZE;return 1;
}

4.1.6 顺序队列取队头元素

//取队头元素
int GetHead(SqQueue Q, int *x)
{if (Q.front == Q.rear){return 0;}*x = Q.data[Q.front];return 1;
}

4.2 链队

4.2.1 链队定义

//链队列
typedef struct QNode {int data;struct QNode *next;
}QNode, *QueuePtr;
typedef struct {QNode *front;QNode *rear;
}LinkQueue;

4.2.2 链队初始化

//初始化
void InitQueue(LinkQueue *Q)
{Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode));Q->front->next = NULL;
}

4.2.3 链队判空

//判断是否为空
int QueueEmpty(LinkQueue Q)
{if (Q.front == Q.rear){return 1;}else{return 0;}
}

4.2.4 链队入队

//入队
int EnQueue(LinkQueue *Q, int x)
{QueuePtr p;p = (QueuePtr)malloc(sizeof(QNode));p->data = x;p->next = NULL;Q->rear->next = p;Q->rear = p;return 1;
}

4.2.5 链队出队

//出队
int DeQueue(LinkQueue *Q, int *x)
{QueuePtr p;if (Q->front == Q->rear){return 0;}p = Q->front->next;*x = p->data;Q->front->next = p->next;if (Q->rear == p){Q->rear = Q->front;}free(p);return 1;
}

4.2.6 链队取队头元素

//取队头元素
int GetHead(LinkQueue Q, int *x)
{if (Q.front == Q.rear){return 0;}*x = Q.front->next->data;return 1;
}