C、C++線性表基本操作的詳細(xì)介紹
更新時間：2020年11月05日 11:40:35 作者：zhen-yu
這篇文章主要給大家介紹了關(guān)于C、C++線性表基本操作的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
前言
線性表包括兩部分順序表和鏈表，是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，在此主要就算法進(jìn)行分析和總結(jié)，作為記憶了解，未做具體實(shí)現(xiàn)。
提示：以下是本篇文章正文內(nèi)容，下面案例可供參考
一、順序表
#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; //當(dāng)前順序表長度
int listsize; //當(dāng)前分配的大小
}SqList;
2、初始化構(gòu)建
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的合法性
- 檢查儲存空間
- 標(biāo)記插入位置
- 將插入位置后面的元素依次向下移動一位（注意從后往前依次移動，以移動位置小于插入位置結(jié)束循環(huán)）
2、算法實(shí)現(xiàn)
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;
}
4、刪除操作
在第i的位置插入元素e
1、算法解釋
- 檢查i的合法性
- 記錄刪除的位子
- 找到刪除元素并賦值給e
- 被刪除元素后面的元素都想上移動一位（找到表尾元素，以移動位子地址大于表尾地址結(jié)束循環(huán)）
2、算法實(shí)現(xiàn)
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;
}
5、合并操作
已知La和Lb的元素按照非遞減的順序排列歸并為Lc也為按值非遞減排列
1、算法解釋
- 記錄La、Lb的操作地址
- 計(jì)算Lc的長度并為其分配空間
- 記錄La、Lb的表尾位置
- 合并-比較兩個表的元素，值較小的存入Lc（注意：以任意一表完全存入Lc結(jié)束循環(huán)）
- 檢查La、Lb是否還有剩余元素，如果有剩余依次存入Lc
2、算法實(shí)現(xiàn)
void MergeList_Sq(SqList La,SqList Lb,SqList &Lc){
//分別記錄La、Lb的當(dāng)前操作地址
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、插入
在帶頭結(jié)點(diǎn)L中的第i個位置之前插入e
1、算法解釋
- 找到第i-1個結(jié)點(diǎn)記錄為P
- 判斷是否找到該結(jié)點(diǎn)
- 生成新結(jié)點(diǎn)S賦值進(jìn)行插入L中
2、算法實(shí)現(xiàn)
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;
//生成新節(jié)點(diǎn)
S=(LinkList)malloc(sizeof(LNode));
S->date=e;
S->next=p->next;
p->next=S;
return OK;
}
3、刪除
在帶頭結(jié)點(diǎn)的單鏈表L中刪除第i個元素，并返回e
1、算法解釋
- 記錄頭結(jié)點(diǎn)的位置
- 尋找第i個結(jié)點(diǎn)，并用p記錄其前驅(qū)
- 檢查刪除位置的合理性
- 記錄第i個結(jié)點(diǎn)，取其值賦值給e
- 將第i-1個結(jié)點(diǎn)指向i+1
- 釋放第i個結(jié)點(diǎn)
2、算法實(shí)現(xiàn)
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;
4、查找
代碼如下（示例）：找到第i個位置的元素，并賦值給e
1、算法解釋
- 將p指向第一個結(jié)點(diǎn)
- 尋找第i個結(jié)點(diǎn)（以p為空或者j>i結(jié)束循環(huán)）
- 判斷是否找到結(jié)點(diǎn)i
- 取結(jié)點(diǎn)i的元素值
2、算法實(shí)現(xiàn)
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;
}
5、合并有序鏈表
已知La、Lb按值非遞減 Lc也是按值非遞減（帶頭結(jié)點(diǎn)）
1、算法解釋
- 更新Pa、Pb、Pc的初始化位置都指向第一個結(jié)點(diǎn)
- 以Pa、Pb都非空為條件，比較其存儲數(shù)據(jù)，較小的連接在Lc上，更新Pc和Pa（Pb）
- 插入剩余結(jié)點(diǎn)
- 釋放未使用的空頭結(jié)點(diǎn)
2、算法實(shí)現(xiàn)
void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//記錄結(jié)點(diǎn)
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);
}
6、創(chuàng)建鏈表
輸入n個元素的值，建立帶頭結(jié)點(diǎn)的單鏈表L
1、逆位序（頭插法）
算法思路
- 創(chuàng)建頭結(jié)點(diǎn)
- 循環(huán)插入結(jié)點(diǎn)
- 將新結(jié)點(diǎn)插入表頭的后面
- 更新表頭的next ##### 算法實(shí)現(xiàn)
算法實(shí)現(xiàn)
void GreateList_L(LinkList &L,int n){
//建立頭結(jié)點(diǎ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、順位序（尾插法）
算法思路
- 創(chuàng)建頭結(jié)點(diǎn)
- 循環(huán)插入結(jié)點(diǎn)
- 將新結(jié)點(diǎn)插入表尾
- 記錄表尾位置并更新
算法實(shí)現(xiàn)
void GreateList_L(LinkList &L,int n){
//建立頭結(jié)點(diǎ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.循環(huán)鏈表
與單鏈表類似，只是表尾結(jié)點(diǎn)的next指向了頭結(jié)點(diǎn)，循環(huán)條件為是否等于表頭元素，不再具體敘述！
3.雙向鏈表
1、定義
//定義一個雙向鏈表
typedef struct DuLNode{
ELemType data;//數(shù)據(jù)元素
struct DuLNode *prior;//前驅(qū)指針
struct DuLNode *next;//后繼指針
}DuLNode,*DuLinkList;
2、插入
在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中的第i個結(jié)點(diǎn)（P）之前插入結(jié)點(diǎn)S的元素e
算法思路
- 檢查i的合法性（1<=i<=表長+1）
- 插入
算法實(shí)現(xiàn)
S->data=e;//賦值 S-prior=p->prior； P->prior->next=S; S->next=P; P->prior=S;
3、刪除
在帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L中刪除第i個結(jié)點(diǎn)（P）并將其數(shù)據(jù)復(fù)制給元素e
算法思路
- 檢查i的合法性（1<=i<=表長）
- 刪除
算法實(shí)現(xiàn)
e=P->data; q=P; P->prior->next=P->next; P->next->prior=P->prior; free(q);//釋放結(jié)點(diǎn)P
總結(jié)
到此順序表和鏈表的基本操作算法基本介紹完成，希望能對初學(xué)者有所幫助，后續(xù)會對數(shù)據(jù)結(jié)構(gòu)后面的內(nèi)容進(jìn)行更新。更多相關(guān)C、C++線性表基本操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語言實(shí)現(xiàn)的順序表功能完整實(shí)例
這篇文章主要介紹了C語言實(shí)現(xiàn)的順序表功能,結(jié)合完整實(shí)例形式分析了C語言順序表的創(chuàng)建、添加、刪除、排序、合并等相關(guān)操作技巧,需要的朋友可以參考下2018-04-04
關(guān)于C++中的友元函數(shù)的一些總結(jié)
以下是對C++中的友元函數(shù)進(jìn)行了詳細(xì)的總結(jié)介紹，需要的朋友可以過來參考下2013-09-09
這篇文章主要是探討常見的臨時對象產(chǎn)生的情況，及其如何避免和解決這種臨時對象產(chǎn)生的方式。具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
QT調(diào)用vs2019生成的c++動態(tài)庫的方法實(shí)現(xiàn)
本文主要介紹了QT調(diào)用vs2019生成的c++動態(tài)庫的方法實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-06-06
這篇文章主要介紹了C語言程序的預(yù)處理,小編覺得這篇文章寫的還不錯,需要的朋友可以參考下，希望能夠給你帶來幫助2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)2048小游戲，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-07-07
這篇文章主要介紹了C語言指針及占據(jù)內(nèi)存空間的相關(guān)知識，非常不錯，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2020-02-02
Dom（Document Object Model，即文檔對象模型）能把XML文檔轉(zhuǎn)換成應(yīng)用程序可遍歷的樹形結(jié)構(gòu)，這樣便可以隨機(jī)訪問其中的節(jié)點(diǎn)。本文將詳細(xì)講講實(shí)現(xiàn)的方法，需要的可以參考一下2022-06-06
Objective-C中常用的結(jié)構(gòu)體NSRange,NSPoint,NSSize(CGSize),NSRect實(shí)例分析
這篇文章主要介紹了Objective-C中常用的結(jié)構(gòu)體NSRange,NSPoint,NSSize(CGSize),NSRect實(shí)例分析,有助于更加直觀的理解Object-C常用的結(jié)構(gòu)體,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)掃雷游戲，含注釋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06