一、链表
一、线性表的顺序实现--顺序表
存储方式
随机存取的本质
loc(ai)=loc(ai-1)+d=loc(a1)+(i-1)*d
（1）定义
#define LIST_INIT_SIZE 100 初始容量
#define LIST_INCREMENT 10 追加内存时的增量
typedef int ElemType;
typedef struct{ElemType *elem; 连续内存的首地址int length;表长int size；表容量（最多存放的个数）
}Sqlist；
Sqlist L；
L.elem;首地址
L.elem[0]
L.length
L.size
（2）初始化
void init（Sqlist &L）{L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType);if(!L.elem){exit(-1);}L.length=0;L.size=LIST_INIT_SIZE;
}
(3)得到第i个元素
void getElem（Sqlist L，int i，ElemType &e）{if（i<1||i>L.length){return;}e=L.elem[i-1](随机存取）}
时间复杂度：o（1）
（4）在第i个元素前插入e
// 在顺序表L的第i个位置插入元素e（i从1开始计数）
// 插入逻辑：将位置i及其之后的所有元素依次后移一位，再在位置i插入e
void insert(Sqlist &L, int i, ElemType e) {// 1. 检查插入位置i的合法性// 若i小于1（小于首位置）或大于当前表长（超过表尾后一个位置），则插入位置无效if (i < 1 || i > L.length) {return; // 位置不合法，直接返回}// 2. 若当前顺序表已满，需扩容（增大存储空间）if (L.length == L.size) { // 表长等于容量，说明空间已满// 重新分配内存：在原有容量基础上增加LIST_INCREMENT个存储单元ElemType *base = (ElemType*)realloc(L.elem, (L.size + LIST_INCREMENT) * sizeof(ElemType));if (!base) { // 内存分配失败exit(-1); // 异常退出程序}L.elem = base; // 更新顺序表的基地址为新分配的内存L.size += LIST_INCREMENT; // 更新容量为原容量+增量}
// 3. 将位置i及其后的所有元素依次向后移动一位（从最后一个元素开始移）
// m从最后一个元素的索引（L.length-1）开始，直到i-1（第i个位置的索引）
for (int m = L.length - 1; m >= i - 1; --m) {L.elem[m + 1] = L.elem[m]; // 元素后移
}// 4. 在第i个位置（索引i-1）插入新元素e
L.elem[i - 1] = e;// 5. 表长加1，更新顺序表长度
L.length++;
}
时间复杂度：
n/2 —— o（n）
（5）删除第i个元素
// 函数功能：从顺序表L中删除第i个位置的元素，并将该元素值存入e中
// （注：函数名"insert"与实际功能不符，更适合命名为"delete"或"remove"）
void insert(Sqlist &L, int i, ElemType e) {
// 1. 检查删除位置i的合法性
// 顺序表元素位置从1开始计数，i需满足1≤i≤当前表长（L.length）
// 若i小于1或大于表长，则位置无效，直接返回
if (i < 1 || i > L.length) {
return;
}
// 2. 保存第i个位置的元素值到e中
// 顺序表底层数组为0基索引，第i个位置对应数组下标i-1
e = L.elem[i - 1];// 3. 将第i个位置之后的所有元素依次向前移动一位
// （注：原代码中"L.lenght"为拼写错误，正确应为"L.length"）
// 循环从第i个位置的索引（i-1）开始，直到表中最后一个元素
for (int m = i - 1; m < L.length; ++m) {// 当前位置的前一位（m-1）接收当前位置（m）的元素值，实现前移L.elem[m - 1] = L.elem[m];
}// 注：原代码缺少关键步骤——删除元素后表长应减1，补充后应为：
// L.length--;
}
时间复杂度：o(n)
二、栈
特点：后进先出
（1）存储特点
地址连续的存储单元依次存放栈元素
（2）顺序栈的定义
#define Stack_Init_Size 100
#define Stack_Increment 10;
typedef xxx Elemtype;
typedef struct{Elemtype *base;栈底指针Elemtype *top;栈顶指针int size;当前最大容量
}SqStack
规定栈顶元素：*（s.top-1)
练习代码
#include <stdio.h>
#include <string.h>
char st[100001];
int top=0;
int main(){char s[100000];scanf("%s",s);for(int i=0;s[i];i++){if(s[i]=='('||s[i]=='['||s[i]=='{'){st[top++]=s[i];}else{if(top==0||(st[top-1]=='('&&s[i]!=')')||(st[top-1]=='['&&s[i]!=']')||(st[i]=='{'&&s[i]!='}')){printf("N");return 0;}else{top--;}}}printf("%s\n", top == 0 ? "Y" : "N");}
三、队列
特性：先进先出
（1）定义
> define size 100;
> typedef struct{
> Elemtype *base;（连续的存储空间）
> int front;
> int rear;
> }SqQueue;
SqQueue Q;
Q.base[Q.front]队头元素
Q.base[Q.rear-1]队尾元素
（2）存储特点
利用地址连续的存储单元依次存放队列各元素
设置两个指示器front，rear表示队头和队尾元素下标
#include <iostream>
#include <cstring>
#include <cstdlib>using namespace std;#define MAX_QUEUE 1001 // 队列最大容量（适配M≤1000）
#define NAME_LEN 20 // 姓名最大长度// 定义队列元素类型（存储姓名）
typedef char Elemtype[NAME_LEN];// 指定的顺序队列结构体（保留 *base 指针）
typedef struct {Elemtype *base; // 指向队列的连续存储空间int front; // 队头下标int rear; // 队尾下标
} SqQueue;// 初始化队列（C++ 引用传参 SqQueue &q）
int InitQueue(SqQueue &q) {// 动态分配连续存储空间q.base = (Elemtype *)malloc(MAX_QUEUE * sizeof(Elemtype));if (!q.base) return 0; // 内存分配失败q.front = 0;q.rear = 0;return 1;
}// 入队操作（引用传参）
int EnQueue(SqQueue &q, Elemtype name) {// 队列满则返回0（题目中M≤1000，不会触发）if ((q.rear + 1) % MAX_QUEUE == q.front) return 0;strcpy(q.base[q.rear], name); // 复制姓名到队尾q.rear = (q.rear + 1) % MAX_QUEUE; // 队尾后移return 1;
}// 出队操作（引用传参）
int DeQueue(SqQueue &q) {// 队列为空则返回0if (q.front == q.rear) return 0;q.front = (q.front + 1) % MAX_QUEUE; // 队头后移return 1;
}int main() {int M;cin >> M;cin.ignore(); // 吸收换行符（替代C的getchar()）// 初始化VIP队列和普通队列SqQueue vip_q, normal_q;InitQueue(vip_q); // 直接传变量（C++引用自动绑定）InitQueue(normal_q);// 处理M次操作for (int i = 0; i < M; i++) {char op[10], name[NAME_LEN], type[2];cin >> op; // 读取操作类型（IN/OUT）if (strcmp(op, "IN") == 0) {// IN操作：IN name V/Ncin >> name >> type;if (strcmp(type, "V") == 0) {EnQueue(vip_q, name); // 引用传参} else {EnQueue(normal_q, name);}} else if (strcmp(op, "OUT") == 0) {// OUT操作：OUT V/Ncin >> type;if (strcmp(type, "V") == 0) {DeQueue(vip_q); // 引用传参} else {DeQueue(normal_q);}}}// 输出VIP队列（从头到尾）int i = vip_q.front;while (i != vip_q.rear) {cout << vip_q.base[i] << endl;i = (i + 1) % MAX_QUEUE;}// 输出普通队列（从头到尾）i = normal_q.front;while (i != normal_q.rear) {cout << normal_q.base[i] << endl;i = (i + 1) % MAX_QUEUE;}// 释放动态内存free(vip_q.base);free(normal_q.base);return 0;
}