这篇文章主要给大家介绍了关于C、C++线性表基本操作的相关资料，文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值，需要的朋友们下面随着小编来一起学习学习吧
前言
线性表包括两部分顺序表和链表，是数据结构的基础，在此主要就算法进行分析和总结，作为记忆了解，未做具体实现。
提示：以下是本篇文章正文内容，下面案例可供参考
一、顺序表
#define LISST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 0 #define OVERFLOW 1 typedef int ElemType; typedef int Status;
1、定义
typedef struct{ int* elem; //定义存储基地址 int length; //当前顺序表长度 int listsize; //当前分配的大小 }SqList;<mark style="color:transparent">来源gaodaimacom搞#^代%!码网</mark>
2、初始化构建
Status InitList_Sq(SqList &l){ L.elem =(ElemType *)malloc(LISST_INIT_SIZE*sizeof(ElemType)); if(!L.elem) exit(OVERFLOW); L.length=0; L.listsize=LISST_INIT_SIZE; return OK;
3、插入操作
在第i的位置插入元素e
1、算法解释
- 检查i的合法性
- 检查储存空间
- 标记插入位置
- 将插入位置后面的元素依次向下移动一位（注意从后往前依次移动，以移动位置小于插入位置结束循环）
2、算法实现
Status LIstInsert_Sq(Sqlist &L,int i, ElemType e){ SqList *newbase,*p,*q; //在第i个位子插入元素e if(iL.length+1) return ERROR; //分配存储空间 if(L.length>L.listsize){ newbase=(ElemType *)realloc(l.elem, (Listsize+LISTINCREMENT)*sizeof(ELemType); if(!newbase) exit(OVERFLOW); L.elem=newbase; L.listsize+=LISTINCREMENT; } //记录插入位置 q=&L.elem[i-1]; for(p=L.elem[length-1];q<=p;p--) { *(p+1)=*p } *p=e; L.length++;//更新表长 return OK; }
4、删除操作
在第i的位置插入元素e
1、算法解释
- 检查i的合法性
- 记录删除的位子
- 找到删除元素并赋值给e
- 被删除元素后面的元素都想上移动一位（找到表尾元素，以移动位子地址大于表尾地址结束循环）
2、算法实现
Status LIstDelete_Sq(Sqlist &L,int i, ElemType &e){ SqList *p,*q; //在第i个位子删除元素 if(iL.length+1) return ERROR; //记录删除位置 p=&L.elem[i-1]; e=*p; //表尾元素 q=&L.elem[L.length-1]; for(++p;p<=q;p++) { *(p-1)=*p; } L.length--;//更新表长 return OK; }
5、合并操作
已知La和Lb的元素按照非递减的顺序排列归并为Lc也为按值非递减排列
1、算法解释
- 记录La、Lb的操作地址
- 计算Lc的长度并为其分配空间
- 记录La、Lb的表尾位置
- 合并-比较两个表的元素，值较小的存入Lc（注意：以任意一表完全存入Lc结束循环）
- 检查La、Lb是否还有剩余元素，如果有剩余依次存入Lc
2、算法实现
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){ //分别记录La、Lb的当前操作地址 SqList *pa,*pb,*pc,*pa_last,*pb_last; pa=La.elem; pb=Lb.elem; Lc.listsize=La.length+Lb.length; pc=Lc.elem=(ElemType *)mallod(Lc.listsize*sizeof(ElemType); if(!pc){ exit(OVERFLOW);//分配失败 } //记录顺序表尾的地址 pa_last=La.elem+La.length-1; pb_last=Lb.elem+Lb.length-1; while(pa<pa_last&&pb<pb_last){ if(*pa<*pb) { //*pc++=*pa++; *pc=*pa pc++; pa++; } else { //*pc++=*pb++; *pc=*pb; pc++; pb++; } while(pa<pa_last) { *pc++=*pa++; } while(pb<pb_last) { *pc++=*pb++; } }
二、链表
#define OK 0 #define OVERFLOW 1 typedef int ElemType; typedef int Status;
1.单链表
1、定义
typedef int ElemType; typedef struct LNode{ ElemType date; struct LNode *next; }LNode,*LinkList;
2、插入
在带头结点L中的第i个位置之前插入e
1、算法解释
- 找到第i-1个结点记录为P
- 判断是否找到该结点
- 生成新结点S赋值进行插入L中
2、算法实现
status ListInsert(LinkList &l,int i;ElemType e){ LinkList p=L,S; int j=0; while(p&&jnext; j++; } if(!p||j>i-1) return ERROR; //生成新节点 S=(LinkList)malloc(sizeof(LNode)); S->date=e; S->next=p->next; p->next=S; return OK; }
3、删除
在带头结点的单链表L中删除第i个元素，并返回e
1、算法解释
- 记录头结点的位置
- 寻找第i个结点，并用p记录其前驱
- 检查删除位置的合理性
- 记录第i个结点，取其值赋值给e
- 将第i-1个结点指向i+1
- 释放第i个结点
2、算法实现
status ListDelete_L(LinkList &L,int i,ElemType &e){ LinkList p=L,q; int j=0; while(p->next&&jnext; j++; } if(!(p-next)||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->date; free(q); return OK;
4、查找
代码如下（示例）：找到第i个位置的元素，并赋值给e
1、算法解释
- 将p指向第一个结点
- 寻找第i个结点（以p为空或者j>i结束循环）
- 判断是否找到结点i
- 取结点i的元素值
2、算法实现
status GetElem_L(LinkList L,int i,ElemType &e){ LinkList p; int j=1; p=L->next; while(p&&j<i>next; j++; } if(!p||j>i) return ERROR; e=p->data; return OK; }
5、合并有序链表
已知La、Lb按值非递减 Lc也是按值非递减（带头结点）
1、算法解释
- 更新Pa、Pb、Pc的初始化位置都指向第一个结点
- 以Pa、Pb都非空为条件，比较其存储数据，较小的连接在Lc上，更新Pc和Pa（Pb）
- 插入剩余结点
- 释放未使用的空头结点
2、算法实现
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){ //记录结点 LinkList Pa,Pb,Pc; Pa=La->next; Pb=Lb->next; Pc=Lc=La; while(Pa&&Pb){ if(Pa->datadata){ Pc->next=Pa; Pc++; Pa++; } else{ Pc->next=Pb; Pc++; Pb++; } } Pc->next=pa? Pa:Pb; free(Lb); }
6、创建链表
输入n个元素的值，建立带头结点的单链表L
1、逆位序（头插法）
算法思路
- 创建头结点
- 循环插入结点
- 将新结点插入表头的后面
- 更新表头的next ##### 算法实现
算法实现
void GreateList_L(LinkList &L,int n){ //建立头结点 LinkList L,P; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; for(i=0;idata);//以整型为例 P->next=L->next; L->next=P; } }
2、顺位序（尾插法）
算法思路
- 创建头结点
- 循环插入结点
- 将新结点插入表尾
- 记录表尾位置并更新
算法实现
void GreateList_L(LinkList &L,int n){ //建立头结点 LinkList L,P; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; Q=L; for(i=0;idata);//以整型为例 Q->next=P Q=P; } q->next=NULL; }
2.循环链表
与单链表类似，只是表尾结点的next指向了头结点，循环条件为是否等于表头元素，不再具体叙述！
3.双向链表
1、定义
//定义一个双向链表 typedef struct DuLNode{ ELemType data;//数据元素 struct DuLNode *prior;//前驱指针 struct DuLNode *next;//后继指针 }DuLNode,*DuLinkList;
2、插入
在带头结点的双向循环链表L中的第i个结点（P）之前插入结点S的元素e
算法思路
- 检查i的合法性（1<=i<=表长+1）
- 插入
算法实现
S->data=e;//赋值 S-prior=p->prior； P->prior->next=S; S->next=P; P->prior=S;
3、删除
在带头结点的双向循环链表L中删除第i个结点（P）并将其数据复制给元素e
算法思路
- 检查i的合法性（1<=i<=表长）
- 删除
算法实现
e=P->data; q=P; P->prior->next=P->next; P->next->prior=P->prior; free(q);//释放结点P
总结
以上就是C、C++线性表基本操作的详细介绍的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：C、C++线性表基本操作的详细介绍
转载请注明原文链接：C、C++线性表基本操作的详细介绍
