首先给出一些宏定义
#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef char ElemType;1. 线性表的顺序存储（顺序表）
1.静态顺序表与动态顺序表
// 定义静态顺序表的最大容量 #define MAXSIZE 100 // 静态顺序表结构体 typedef struct { ElemType elem[MAXSIZE]; // 存储数据元素的数组，ElemType为char（来自之前的定义） int length; // 记录顺序表当前的实际长度（注意：length ≤ MAXSIZE） } SqList;// 动态顺序表结构体 typedef struct { ElemType *elem; // 指向动态分配内存的指针，用于存储数据元素 int length; // 顺序表当前的实际长度 int capacity; // 顺序表当前的最大容量（已分配的内存大小） } SqList;2.初始化顺序表
Status InitSqList(DynamicSqList *L, int initCapacity) { // 合法性校验 if (initCapacity <= 0) { return ERROR; } // 动态分配内存 L->elem = (ElemType *)malloc(initCapacity * sizeof(ElemType)); //或者L->elem = new ElemType[initCapacity] // 内存分配失败 if (L->elem == NULL) { return OVERFLOW; // OVERFLOW=-2（来自宏定义），表示内存溢出 } // 初始化参数 L->length = 0; // 初始实际长度为0 L->capacity = initCapacity; // 初始容量为指定值 return OK; }3.向顺序表指定位置插入元素
Status InsertSqList(SqList &L, int pos, ElemType e){ // 1. 合法性校验：L不为空、pos位置合法、顺序表未满 if (L == NULL || pos < 1 || pos > L->length + 1 || L->length >= L->capacity) { return ERROR; } //2.移动元素，将pos后的元素向后移动一位 for(int i = L->length; i >= pos; i--){ L->elem[i] = L->elem[i--}; } //3.插入新元素 L->elem[pos - 1] = e; //4.更新数组长度 L->length++; return Ok; }4.删除顺序表指定位置元素
Status DeleteSqList(SqList &L, int pos){ // 1. 合法性校验：L不为空、pos位置合法、顺序表未满 if (L == NULL || pos < 1 || pos > L->length || L->length == 0) { return ERROR; } //2.将pos后的元素向前移动一位 for(int i = pos-1; i < L->length; i++){ L->elem[i] = L->elem[i + 1}; } //3.更新数组长度 L->length--; return Ok; }5.查找顺序表中指定元素
Status LocateSqList(SqList &L, ElemType e){ // 1. 合法性校验：L不为空 if (L == NULL || L->length == 0) { return ERROR; } //2.顺序遍历查找 for(int i = 0; i < L->length; i++){ if(L->elem[i] = e){ return i + 1; } //3.未找到指定元素 return 0; }2.线性表的链式存储
1. 写出结构体定义
typedef struct student{ char num[8]; //学号 char num[8]; //姓名 int sore; //分数 struct student *next; //指针域 } Lnode, *LinkList;或者一般分开写
typedef Struct student{ char num[8]; //学号 char num[8]; //姓名 int sore; //分数 } ElemType; typedef Struct Lnode{ ElemType data; //数据域 Struct Lnode *next; //指针域 } Lnode, *LinkList;2.初始化链表
LinkList InitList(LinkList &L){ LinkList L = new Lnode; //或者 LinkList L = (LinkList)malloc(sizeof(Lnode)); if(L == NULL){ cout << "内存分配失败" << endl; return NULL: } L->next = NULL; //头结点的 指针域初始化为空 return L; }3.判断链表是否为空
Status ListEmpty(LinkList &L){ if(L->next != NULL) return 0; else return 1; }4.销毁单链表
Status DestoryList_L(LinkList &L){ Lnode *p; //或者LinkList p; while (L != NULL){ p = L; L = L->next; //头节点后移 delete P; } return OK; }5.清空链表
Status ClearList(LinkList &L){ Lnode *p, *q; p = L->next; while(p){ q = p->next; delete p; p = q; } L->next = NULL; return OK; }6. 链表表长
int Listlength(LinkList &L){ Lnode *p; p = L->next; int i = 0; while(p){ i++; p = p->next; } return 0; }7.获取链表中某个位置的元素
Status GetElem(LinkList &L, int i, ElemType &e){ Lnode *p = L->next; int j = 1; while( p && j < i){ p = p->next; j++; } if(!p || j >i) return ERROR; e = p->data; return OK; } //或者(这个不如上一个优） Status GetElem(LinkList &L, int i, ElemType &e){ Lnode *p = L->next; if(i < 1) return ERROR; for(int j = 1; j < i && p; j++){ p = p->next; } if(!p) return ERROR; e = p->data; return OK; }8.查找链表中的某个元素
\\返回地址 Lnode* LocateElem(LinkList &L, ElemType e){ Lnode *p = L->next; while(p->data != e && p){ p = p->next; } return p; } \\返回位置序号 int LocateElem(LinkList &L, ElemType e){ Lnode *p = L->next; int j = 1; while(p->data != e && p){ p = p->next; j++; } if(p) return j; return 0; }9.在链表中某个位置插入元素
Status ListInsert(LinkList &L, int i, ElemType e){ int j = 0; Lnode *p = L; while(p && j < i-1){ p = p->next; j++; } if(!p || j > i-1) return ERROR; Lnode *s = new Lnode; s->next = p->next; p->next = s; return OK; }
