本篇文章给大家分享的是有关在C和C++中如何使用线性表，小编觉得挺实用的，因此分享给大家学习，希望大家阅读完这篇文章后可以有所收获，话不多说，跟着小编一起来看看吧。
线性表包括两部分顺序表和链表，是数据结构的基础，在此主要就算法进行分析和总结，作为记忆了解，未做具体实现。
提示：以下是本篇文章正文内容，下面案例可供参考
#define LISST_INIT_SIZE 100 #define LISTINCREMENT 10 #define OK 0 #define OVERFLOW 1 typedef int ElemType; typedef int Status;
typedef struct{ int* elem; //定义存储基地址 int length; //当前顺序表长度 int listsize; //当前分配的大小 }SqList;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;在第i的位置插入元素e
Status LIstInsert_Sq(Sqlist &L,int i, ElemType e){ SqList *newbase,*p,*q; //在第i个位子插入元素e if(i<1||i>L.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; }在第i的位置插入元素e
Status LIstDelete_Sq(Sqlist &L,int i, ElemType &e){ SqList *p,*q; //在第i个位子删除元素 if(i<1||i>L.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; }已知La和Lb的元素按照非递减的顺序排列归并为Lc也为按值非递减排列
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;
typedef int ElemType; typedef struct LNode{ ElemType date; struct LNode *next; }LNode,*LinkList;在带头结点L中的第i个位置之前插入e
1、算法解释
2、算法实现
status ListInsert(LinkList &l,int i;ElemType e){ LinkList p=L,S; int j=0; while(p&&j<i-1){ p=p->next; 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; }在带头结点的单链表L中删除第i个元素，并返回e
1、算法解释
2、算法实现
status ListDelete_L(LinkList &L,int i,ElemType &e){ LinkList p=L,q; int j=0; while(p->next&&j<i-1){ p=p->next; j++; } if(!(p-next)||j>i-1) return ERROR; q=p->next; p->next=q->next; e=q->date; free(q); return OK;代码如下（示例）：找到第i个位置的元素，并赋值给e
1、算法解释
2、算法实现
status GetElem_L(LinkList L,int i,ElemType &e){ LinkList p; int j=1; p=L->next; while(p&&j<i）{ p=p->next; j++; } if(!p||j>i) return ERROR; e=p->data; return OK; }已知La、Lb按值非递减 Lc也是按值非递减（带头结点）
1、算法解释
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->data<=Pb->data){ Pc->next=Pa; Pc++; Pa++; } else{ Pc->next=Pb; Pc++; Pb++; } } Pc->next=pa? Pa:Pb; free(Lb); }输入n个元素的值，建立带头结点的单链表L
1、逆位序（头插法）
算法思路
算法实现
void GreateList_L(LinkList &L,int n){ //建立头结点 LinkList L,P; L=(LinkList)malloc(sizeof(LNode); L->next=NULL; for(i=0;i<n;i++){ P=(LinkList)malloc(sizeof(LNode); scanf("%d",&P->data);//以整型为例 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;i<n;i++){ P=(LinkList)malloc(sizeof(LNode); scanf("%d",&P->data);//以整型为例 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
算法思路
算法实现
S->data=e;//赋值 S-prior=p->prior； P->prior->next=S; S->next=P; P->prior=S;
3、删除
在带头结点的双向循环链表L中删除第i个结点（P）并将其数据复制给元素e
算法思路
算法实现
e=P->data; q=P; P->prior->next=P->next; P->next->prior=P->prior; free(q);//释放结点P
以上就是在C和C++中如何使用线性表，小编相信有部分知识点可能是我们日常工作会见到或用到的。希望你能通过这篇文章学到更多知识。更多详情敬请关注亿速云行业资讯频道。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
