溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本篇文章給大家分享的是有關在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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
