欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C、C++線性表基本操作的詳細介紹

 更新時間：2020年11月05日 11:40:35   作者：zhen-yu  
這篇文章主要給大家介紹了關(guān)于C、C++線性表基本操作的相關(guān)資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧

前言

線性表包括兩部分順序表和鏈表，是數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)，在此主要就算法進行分析和總結(jié)，作為記憶了解，未做具體實現(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; //當前順序表長度
			int listsize; //當前分配的大小
			}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、算法解釋

  1. 檢查i的合法性
  2. 檢查儲存空間
  3. 標記插入位置
  4. 將插入位置后面的元素依次向下移動一位（注意從后往前依次移動，以移動位置小于插入位置結(jié)束循環(huán)）

2、算法實現(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、算法解釋

  1. 檢查i的合法性
  2. 記錄刪除的位子
  3. 找到刪除元素并賦值給e
  4. 被刪除元素后面的元素都想上移動一位（找到表尾元素，以移動位子地址大于表尾地址結(jié)束循環(huán)）

2、算法實現(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、算法解釋

  1. 記錄La、Lb的操作地址
  2. 計算Lc的長度并為其分配空間
  3. 記錄La、Lb的表尾位置
  4. 合并-比較兩個表的元素，值較小的存入Lc（注意：以任意一表完全存入Lc結(jié)束循環(huán)）
  5. 檢查La、Lb是否還有剩余元素，如果有剩余依次存入Lc

2、算法實現(xiàn)

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、插入

在帶頭結(jié)點L中的第i個位置之前插入e

1、算法解釋

  1. 找到第i-1個結(jié)點記錄為P
  2. 判斷是否找到該結(jié)點
  3. 生成新結(jié)點S賦值進行插入L中

2、算法實現(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é)點
	S=(LinkList)malloc(sizeof(LNode));
	S->date=e;
	S->next=p->next;
	p->next=S;
	return OK;
	}

3、刪除

在帶頭結(jié)點的單鏈表L中刪除第i個元素，并返回e

1、算法解釋

  1. 記錄頭結(jié)點的位置
  2. 尋找第i個結(jié)點，并用p記錄其前驅(qū)
  3. 檢查刪除位置的合理性
  4. 記錄第i個結(jié)點，取其值賦值給e
  5. 將第i-1個結(jié)點指向i+1
  6. 釋放第i個結(jié)點

2、算法實現(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é)點
  • 尋找第i個結(jié)點（以p為空或者j>i結(jié)束循環(huán)）
  • 判斷是否找到結(jié)點i
  • 取結(jié)點i的元素值

2、算法實現(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é)點）

1、算法解釋

  1. 更新Pa、Pb、Pc的初始化位置都指向第一個結(jié)點
  2. 以Pa、Pb都非空為條件，比較其存儲數(shù)據(jù)，較小的連接在Lc上，更新Pc和Pa（Pb）
  3. 插入剩余結(jié)點
  4. 釋放未使用的空頭結(jié)點

2、算法實現(xiàn)

void MergeList_L(LinkList &La,LinkList &Lb,LinkList &Lc){
//記錄結(jié)點
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é)點的單鏈表L

1、逆位序（頭插法）

算法思路

  1. 創(chuàng)建頭結(jié)點
  2. 循環(huán)插入結(jié)點
  3. 將新結(jié)點插入表頭的后面
  4. 更新表頭的next ##### 算法實現(xiàn)

算法實現(xiàn)

void GreateList_L(LinkList &L,int n){
//建立頭結(jié)點
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、順位序（尾插法）

算法思路

  1. 創(chuàng)建頭結(jié)點
  2. 循環(huán)插入結(jié)點
  3. 將新結(jié)點插入表尾
  4. 記錄表尾位置并更新

算法實現(xiàn)

void GreateList_L(LinkList &L,int n){
//建立頭結(jié)點
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é)點的next指向了頭結(jié)點，循環(huán)條件為是否等于表頭元素，不再具體敘述！

3.雙向鏈表

1、定義

//定義一個雙向鏈表
typedef struct DuLNode{
	ELemType data;//數(shù)據(jù)元素
	struct DuLNode *prior;//前驅(qū)指針
	struct DuLNode *next;//后繼指針
}DuLNode,*DuLinkList;

2、插入

在帶頭結(jié)點的雙向循環(huán)鏈表L中的第i個結(jié)點（P）之前插入結(jié)點S的元素e

算法思路

  1. 檢查i的合法性（1<=i<=表長+1）
  2. 插入

算法實現(xiàn)

S->data=e;//賦值
S-prior=p->prior；
P->prior->next=S;
S->next=P;
P->prior=S;

3、刪除

在帶頭結(jié)點的雙向循環(huán)鏈表L中刪除第i個結(jié)點（P）并將其數(shù)據(jù)復(fù)制給元素e

算法思路

  1. 檢查i的合法性（1<=i<=表長）
  2. 刪除

算法實現(xiàn)

e=P->data;
q=P;
P->prior->next=P->next;
P->next->prior=P->prior;
free(q);//釋放結(jié)點P

總結(jié)

到此順序表和鏈表的基本操作算法基本介紹完成，希望能對初學者有所幫助，后續(xù)會對數(shù)據(jù)結(jié)構(gòu)后面的內(nèi)容進行更新。更多相關(guān)C、C++線性表基本操作內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論