顺序表的初始化查找插入删除

#include<iostream> #include<malloc.h> using namespace std; #define MAXSIZE 10 typedef int ElementType; typedef int Position; typedef struct LNode *List; struct LNode { ElementType Data[MAXSIZE]; Position Last; }; List MakeEmpty() { List L; L=(List)malloc(sizeof(LNode)); L->Last=-1; return L; } /* 查找 */ #define Error -1 Position Find(List L,ElementType X) { Position i=0; while(i<=L->Last&&L->Data[i]!=X) i++; if(i>L->Last) return Error;/* 如果没找到，返回错误信息 */ else return i;/* 找到后返回的是存储位置 */ } /* 插入 */ /*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/ bool Insert(List L,ElementType X,Position P) { Position i; if(L->Last==MAXSIZE-1) { /* 表空间已满，不能插入 */ printf("表满"); return false; } else if(P<0||P>L->Last+1) {/* 检查插入位置的合法性 */ printf("位置不合法"); return false; } for(i=L->Last;i>=P;i--) { L->Data[i+1]=L->Data[i];/* 将位置P及以后的元素顺序向后移动 */ } L->Data[P]=X;/* 新元素插入 */ L->Last++; /*※ Last仍指向最后元素 */ return true; } /* 删除 */ /*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是存储下标位置（从0开始），两者差1*/ bool Delete(List L,Position P) {/* 从L中删除指定位置P的元素 */ Position i; if(P<0||P>L->Last) {/* 检查空表及删除位置的合法性 */ printf("位置%d不存在元素",P); return false; } for(i=P+1;i<=L->Last;i++) { L->Data[i-1]=L->Data[i];/* 将位置P+1及以后的元素顺序向前移动 */ } L->Last--;/* Last仍指向最后元素 */ return true; } int main() { }

基本理解的情况下自己敲了一遍代码。 这里使用了 malloc() 函数，需要使用#include<malloc.h>头文件，作用是分配一块内存空间。函数原型为　void malloc(int size); 即返回的类型是void , 表示未确定类型的指针,因此在返回后强制转换为实际类型的指针，在此处为(List)malloc(sizeof(LNode))**，*List为struct LNode 类型的指针。

链式表的查找插入删除

#include<iostream> #include<malloc.h> using namespace std; #define Error NULL typedef int ElementType; typedef struct LNode *PtrToNode; struct LNode { ElementType Data; PtrToNode Next; }; typedef PtrToNode Position; typedef PtrToNode List; Position Find(List L,ElementType X) { Position P=L;/* p指向L的第1个结点 */ while(P&&P->Data!=X) P=P->Next; /* 下列语句可以用 return p; 替换 */ if(P) return P; else return Error; } /* 带头结点的插入 */ /*注意:在插入位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是链表结点指针，在P之前插入新结点 */ bool Insert(List L,ElementType X,Position P) {/* 这里默认L有头结点 */ Position pre,tmp; /* 查找P的前一个结点 */ for(pre=L;pre&&pre->Next!=P;pre=pre->Next) if(pre==NULL) { printf("插入位置参数错误/n"); return false; } else {/* 找到了P的前一个结点pre */ /* 在P前插入新结点 */ tmp=(Position)malloc(sizeof(LNode));/* 申请、填装结点 */ tmp->Data=X; tmp->Next=pre->Next; pre->Next=tmp; return true; } } /* 带头结点的删除 */ /*注意:在删除位置参数P上与课程视频有所不同，课程视频中i是序列位序（从1开始），这里P是拟删除结点指针 */ bool Delete(List L,Position P) {/* 这里默认L有头结点 */ Position pre; /* 查找P的前一个结点 */ for(pre=L;pre&&pre->Next!=P;pre=pre->Next) if(pre==NULL||P==NULL) {/* P所指的结点不在L中 */ printf("删除位置参数错误/n"); return false; } else {/* 找到了P的前一个结点pre */ /* 将P位置的结点删除 */ pre->Next=P->Next; free(P); return true; } } int main() { }

不得不说复制代码真的好麻烦…一次复制多了直接瘫掉…也是服了

堆栈的定义与存储-顺序存储

#include<iostream> using namespace std; #define MAXSIZE 10 typedef int ElementType; typedef struct SNode *Stack; struct SNode { ElementType Data[MAXSIZE]; int top; }; void Push(Stack Ptrs,ElementType item) { if(Ptrs->top==MAXSIZE-1) { printf("堆栈满"); } else { Ptrs->Data[++(Ptrs->top)]=item; } } #define Error -1 ElementType Pop(Stack Ptrs) { if(Ptrs->top==-1) { printf("堆栈为空"); return Error; } else return Ptrs->Data[(Ptrs->top)--]; } int main() { }

Push时需要判断堆栈是否已满，Pop时需判断堆栈是否为空，同时Pop应返回ElementType类型的数据，因此定义函数Pop时，类型为ElementType，而Push不需要返回数据，所以为void。 Push时应先栈顶指针向上移动一个，再放入数据，即为++(Ptrs->top)。 Pop时应先弹出数据，栈顶指针再向下移动，即为(Ptrs->top)–。

堆栈的定义与存储-链式存储

#include<iostream> #include<malloc.h> using namespace std; typedef int ElementType; typedef struct SNode *PtrToSNode; struct SNode { ElementType Data; PtrToSNode Next; }; typedef PtrToSNode Stack; bool IsEmpty(Stack S) {/* 判断堆栈S是否为空，若是返回true；否则返回false */ return (S->Next==NULL); } Stack CreateStack() {/* 构建一个堆栈的头结点，返回该结点指针 */ Stack S; S=(Stack)malloc(sizeof(SNode)); S->Next=NULL; return S; } #define Error -1 bool Push(Stack S,ElementType X) {/* 将元素X压入堆栈S */ PtrToSNode TmpCell; TmpCell=(Stack)malloc(sizeof(SNode)); TmpCell->Data=X; TmpCell->Next=S->Next; S->Next=TmpCell; } ElementType Pop(Stack S) {/* 删除并返回堆栈S的栈顶元素 */ PtrToSNode FirstCell; ElementType TopElem; if(IsEmpty(S)) { printf("堆栈为空"); return Error; } else { FirstCell=S->Next; TopElem=FirstCell->Data; S->Next=FirstCell->Next; free(FirstCell); return TopElem; } } int main() { }

需要注意的是头节点S是不含数据的，仅作为堆栈的入口 链式结构的堆栈Push操作则不需判断是否栈满，因为可以一直Push数据，Push时要注意修改对应的两个指针，且顺序不能出错。 Pop时需要判断堆栈是否为空，根据前面定义的IsEmpty()函数来判断，同样需要注意修改指针的顺序，返回弹出的值，并释放该节点。 看代码真的是理智疯狂-1，又是没有理智的刀客特的一天呢…