数据结构与算法

首先给出一些宏定义

#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; }