数据结构笔记（c++，顺序表和链表的基本操作代码）

大二上学数据结构方法20min理解概念30min写代码考伪代码手写不能用vector库20min刷课后题考试考选择题应用题代码题。学完能应付考试写代码知道用什么容器知道程序为什么慢会手写底层代码懂内部原理干活用库考试造库。知识点看书做笔记思维导图上网搜错题及时回顾下面是作业代码。c版,除了能运行的代码外其余为c,c混用的伪代码一、线性表1、顺序表随机存取结构占用连续存储空间静态分配1顺序表定义//简洁定义 int A[maxSize];//顺序表为整形 int n;//长度为n //结构体定义 typedef struct{ int data[maxSize]; int length; }SqList;2)初始化void InitList(SqList L){ L.length0; }3顺序表查找返回下标int LocatedElem(SqList L,int e){ int i; for(i1;iL.length;i){ if(eL.data[i])return i; } return 0; }返回元素int GetElem(SqList L,int p,int e){ if(p1||pL.length)return 0; eL.data[p]; return 1; }4)顺序表插入int ListInsert(SqList L,int p,int e){ int i; if(p1||pL.length1||L.lengthmaxSize)return 0; for(iL.length;ip;i--){ L.data[i1]L.data[i]; } L.data[p]e; L.length; return 1; }5)顺序表删除int ListDelete(SqList L,int p,int e){ int i; if(p1||pL.length)return 0; eL.data[p]; for(ip;iL.length;i){ L.data[i]L.data[i1]; } L.length--; return 1; }6)顺序表修改int ListModify(SqList L,int p,int x){ if(p1||pL.length)return 0; L.data[p]x; return 1; }能运行的代码#include bits/stdc.h #includewindows.h using namespace std; #define maxSize 100 typedef int ElemType; //顺序表定义 typedef struct{ int data[maxSize]; int length; }SqList; //顺序表初始化 void InitList(SqList L){ L.length0; } //顺序表插入 int ListInsert(SqList L,int p,int e){ int i; if(p1||pL.length1||L.lengthmaxSize-1)return 0; for(iL.length;ip;i--){ L.data[i1]L.data[i]; } L.data[p]e; L.length; return 1; } //顺序表删除 int ListDelete(SqList L,int p,int e){ int i; if(p1||pL.length)return 0; eL.data[p]; for(ip;iL.length;i){ L.data[i]L.data[i1]; } L.length--; return 1; } //顺序表修改 int ListModify(SqList L,int p,int x){ if(p1||pL.length)return 0; L.data[p]x; return 1; } //打印顺序表 void PrintList(SqList L){ for(int i1;iL.length;i){ coutL.data[i] ; } coutendl; } int main(){ SetConsoleOutputCP(65001); SqList L; InitList(L); int op; int pos,val,e; while(true){ cout\n菜单endl; cout1 插入\n2 删除\n3 修改\n4 打印\n0 退出endl; cout请输入操作号; cinop; if(op0){ cout程序结束endl; break; } else if(op1){ cout输入插入位置(从1开始)和数值:endl; cinposval; if(ListInsert(L,pos,val)){ cout插入成功\n; }else{ cout插入失效位置非法\n; } } else if(op2){ cout输入要删除的位置; cinpos; if(ListDelete(L,pos,e)){ cout删除成功\n; }else{ cout删除失败位置非法\n; } } else if(op3){ cout输入修改的位置和新数值; cinposval; if(ListModify(L,pos,val)){ cout修改成功; }else{ cout修改失败位置非法\n; } } else if(op4){ cout当前顺序表; PrintList(L); } else{ cout输入错误重新选:); } } return 0; }2、单链表顺序存储结构不支持随机访问动态分配1单链表结点定义typedef struct LNode{ int data;//数据域 struct LNode *next;//指针域 }LNode;2单链表初始化(408要用malloc就不用new了)int InitList(LNode *L){ L(LNode *)malloc(sizeof(LNode)); if(LNULL)return 0; L-nextNULL; return 1; }3)单链表查找按位查找int GetElem(LNode *L,int i,int e){ if(i1)return 0; LNode *pL-next; int j1; while(p!NULLji){ pp-next; jj1; } if(pNULL)return 0; ep-data; return 1; }按值查找int LocatedElem(LNode *L,int x){ LNode *pL-next; int j1; while(p!NULLp-data!x){ pp-next; j; } if(pNULL)return 0; return j; }4)单链表插入按位插入int ListInsert(LNode *L,int i,int e){ LNode *pL: int j0; while(p!nullptrji-1){ pp-next; j; } if(pnullptr)return 0; LNode *s (LNode *)malloc(sizeof(LNode()); s-datae; s-nextp-next; p-nexts; return 1; }头front插法链表都有头结点void CreatListF(LNode *C,int a[],int n){ LNode *s; int i; C(LNode *)malloc(sizeof(LNode)); C-nextNULL; for(i1;in;i){ s(LNode *)malloc(sizeof(LNode)); s-dataa[i]; //关键步骤 s-nextC-next; C-nexts; } }尾rear插法void CreatListR(LNode *C,int a[],int n){ LNode *s,*r; int i; C(LNode *)malloc(sizeof(LNode()); C-nextNULL; rC; for(i1;in;i){ s(LNode *)malloc(sizeof(LNode)); s-dataa[i]; r-nexts; rr-next; } r-nextNULL; }5)单链表删除按位删除int ListDelete(LNode *L,int i,int e){ if(LNULL)return 0; if(i1)return 0; LNode *pL: int j0; while(p!NULLji-1){ PP-next; j; } if(pNULL||p-nextNULL)return 0; LNode *qp-next; eq-data; p-nextq-next; free(q); return 1; }按值删除int ListDeleteByVal(LNode *L,int x,int e){ LNode *pL: while(p-next!NULLp-next-data!x){ pp-next; } if(p-nextNULL)return 0; LNode *qp-next; eq-data; p-nextq-next; free(q); return 1; }6)单链表修改int ListModify(LNode L,int x){ LNode *p; pL-next; j1; while(p!NULLji){ pp-next; jj1; } if(pNULL)return 0; p-datax; return 1; }能运行的代码#includebits/stdc.h using namespace std; typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; int InitList(LinkList L){ //L(LNode *)malloc(sizeof(LNode)); Lnew LNode; if(LNULL)return 0; L-nextNULL; return 1; } int ListInsert(LinkList L,int i,int e){ LNode *pL; int j0; while(p!NULL ji-1){ pp-next; j; } if(pNULL)return 0; LNode *snew LNode; s-datae; s-nextp-next; p-nexts; return 1; } int ListDelete(LinkList L,int i,int e){ if(LNULL)return 0; if(i1)return 0; LNode *pL; int j0; while(p!NULLji-1){ pp-next; j; } if(pNULL||p-nextNULL)return 0; LNode *qp-next; eq-data; p-nextq-next; delete q; return 1; } int ListModify(LinkList L,int i,int x){ LNode *p; pL-next; int j1; while(p!NULLji){ pp-next; j; } if(pNULL)return 0; p-datax; return 1; } //遍历打印 void ListTraverse(LinkList L){ LNode *pL-next; while(p!NULL){ coutp-data ; pp-next; } coutendl; } //销毁链表释放全部内存 void DestroyList(LinkList L){ LNode *p; while(L!NULL){ pL; LL-next; delete p; } } int main(){ LinkList L; InitList(L); ListInsert(L,1,1); ListInsert(L,2,2); ListInsert(L,3,3); cout插入之后; ListTraverse(L); ListModify(L,2,99); cout修改第二位为99:; ListTraverse(L); int del_e; ListDelete(L,1,del_e); cout删除第一位删除值del_e:; ListTraverse(L); DestroyList(L); return 0; }ADT基本操作操作结果InitList(L)构造一个空的线性表 LGetElem(L,i,e)按值查找用 e 返回L 中第i 个数据元素的值LocateElem(L,e)按位查找返回L 中第 1 个值与e 相同的元素在 L 中的位置。若这样的数据元素不存在则返回值为0ListInsert(L,i,e)在 L 中第i 个位置之前插入新的数据元素eL 的长度加1ListDelete(L,i)按位删除 L 的第i 个数据元素L的长度减 1ListModify(L,p,x)按位修改