线性表的物理结构分为顺序存储和链式存储。以下分别是对顺序表和链表的相关操作的代码表示。
顺序表
一、顺序表的分配
1.、顺序表的静态分配
//对顺序表的静态分配 #define MaxSize 100 typedef struct{ int data[MaxSize]; //使用静态分配的方式 int length; //顺序表的当前长度 }SqList;//初始化一个顺序表 void InitList(SqList &L){ for(int i = 0; i < MaxSize; i++){ //对数组中的所有元素进行初始化,虽然不初始化，编译器会自动给数据复制为0， //但是存在数组中的元素是系统留下来的脏数据 //注意for循环里面是MaxSize而不是length L.data[i] = 0; } L.length = 0; }#include<iostream> int main(){ //在主函数里面检查顺序表是否初始化成功 SqList L; InitList(L); for(int i = 0; i < MaxSize; i++){ cout<<L.data[i]; } }
2.顺序表的动态分配
//对顺序表的动态分配 #define InitSize 100; //默认的最大长度 typedef struct{ int *data; //指示动态分配数组的指针 int MaxSize; //顺序表的最大容量 int length; //顺序表的当前长度 }SqList;//动态增加数组的长度 void IncreaseSize(SqList &L,int len){ //这里用了引用传递参数 int *p = L.data; //建立一个指向数组的指针 L.MaxSize = InitSize + len; L.data = (int *)malloc((L.MaxSize+len)*sizeof(int)); //L.data重新指向了一个新的地址 for(int i = 0; i < L.length; i++){ L.data[i] = p[i]; //将数据复制到新的区域 } free(q); //释放原来的内存空间 }
二、顺序表的基本操作--插入
//顺序表的基本操作--插入 bool ListInsert(SeqList &L,int i, int e){ //在位序i的位置插入e（位序不同于数组下标，数组下标为”位序-1“） if(i <1 || i > L.length){ //对于位序是否在合理的范围内进行检查 //元素要么插在位序为1的位置，要么插入在位序为L.length+1的位置 return false; } for(int j = L.length; j>= i; j--){ L.data[j] = L.data[j-1]; } L.data[i-1] = e; L.length ++; } return true;
三、顺序表的基本操作--删除
//顺序表的基本操作--删除 bool ListDelete(SqList &L,int i,int &e){ //首先检查删除元素的位序是否合理 if(i < 1 || i > L.length){ return false; } e = L.data[i-1]; //对数组元素进行前移 for(int j = i-1; j < L.length-1; j++){ L.data[j] = L.data[j+1]; } L.length--; return true; }
四、顺序表的基本操作--查找
1.按位查找 (i 表示数据的位置)
int GetElem(SqList &L, int i){ return L.data[i-1]; }
2.按值查找
//顺序表的按值查找 int LocateElme(SqList L,int e){ for(int i = 0;i < L.length; i++){ if(L.data[i] == e){ return i+1; } } return 0; }
链表
一、链表的定义
typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; //简单说明，LNnode用在定义节点时，LinkList用在定义链表时，功能都差不多，仅仅是为了增加可读性
二、带头节点的链表的初始化
//初始化一个带头节点的单链表 bool InitList1(LinkList &L){ L = (LinkList)malloc(sizeof(LinkList)); //分配一个头节点 if(L == NULL){ //内存不足，分配失败 return false; } L->next= NULL; //头节点之后暂时还没有节点 return true; }
三、带头节点的链表的判空
//判断单链表是否为空 bool Empty(LinkList L){ return (L->next == NULL); }
四、单链表的建立
1.用头插法建立单链表
注：很多单链表的逆置问题都可以用到头插法
//头插法建立单链表（逆向建立单链表） LinkList ListHeadInsert(LinkList &L){ LNode *s; int x; L->next = NULL; //只要是初始化单链表都要将头指针指向空，否则L可能 //会指向一片不知道的内存空间，产生错误 scanf("%d",&x); while(x != -1){ //取一个特殊值结束循环，如-1 s = (LNode *)malloc(sizeof(LNode)); s->data = x; s->next = L->next; //如果前面没有初始化L，L指向了一个未知的区域 //则此时s也会指向一个未知的区域 L->next =s; scanf("%d",&x); } return L; }
2.尾插法建立单链表
LinkList ListTailInsert(LinkList &L){ LNode *s; LNode *r; //表尾指针 int x; L->next = NULL; r = L; scanf("%d",&x); while(x != -1){ s = (LNode *)malloc(sizeof(LNode)); if(s == NULL){ printf("内存空间不足！"); } s->data = x; s->next = r->next; r = s; scanf("%d",&x); } r->next = NULL; return L; }
五、带头节点的单链表的基本操作--插入
1.按位插入
//单链表的插入操作--按位序插入 bool ListInsert(LinkList &L,int i,int e){ if(i < 1){ return false; } LNode *p; //指针p指向当前扫描到的节点 int j = 0; //记录p指向的是第几个节点（找到插入位置的前一个节点） p = L; //p指向L，头节点认为是第0个节点 while(p != NULL && j< i-1){ j++; p = p->next; } if(p == NULL){ return false; //i的值不合适 } LNode *s = (LNode *)malloc(sizeof(LNode)); //申请一个节点放置e s->data = e; //将s节点放在p节点之后 s->next = p->next; p->next = s; return true; }
2.指定节点的后插操作--在p节点之后插入元素e
//指定节点的后插操作(在p节点之后插入元素e) bool InsertNextNode(LNode *p,int e){ if(p == NULL){ return false; } LNode *s = (LNode *)malloc(sizeof(LNode)); //检查内存是否分配成功 if(s == NULL){ return false; } s->data = e; //插入操作 s->next = p->next; p->next = s; return true; }
3.在指定节点的前插操作--在p节点之前插入数据元素e
bool InsertPriorNode(LNode *p,int e){ //这一部分的思想比较巧妙：申请一个节点s，这个节点链接在p节点之后， //然后对换节点s和节点p的数据域即可达到前插的效果 LNode *s = (LNode *)malloc(sizeof(LNode)); if(s == NULL){ //内存分配失败 return false; } s->next = p->next; p->next = s; s->data = p->data; p->data = e; return true; }
六、单链表的删除操作
1。按位序删除（带头节点）
//按位序删除（带头节点） bool ListDelete(LinkList &L,int i,int &e){ if(i < 1){ //位序不合法 return false; } LNode *p; int j = 0; p = L; while(p != NULL && j < i-1){ p = p->next; j++; } if(p == NULL){ return false; } if(p->next == NULL){ return false; } LNode *q = p->next; p = q->next; e = q->data; free(q); return true; }
2.指定节点的删除（可以使用双指针，找到前驱节点）
//指定节点的删除，可以使用双指针 bool ListDelete2(LinkList &L,LNode *p){ LNode *t,*r; t = L; if(L->next == NULL){ return false; } r = L->next; if(p == NULL){ return false; } while(r != p){ t = r; r = r->next; } t = r->next; free(p); r->next = NULL; return true; }