天天看點
傳回

二、線性表

線性表:零個或若幹個資料元素構成的線性序列，令線性表長度為n，線性表記為( a 0 a_{0} a0​, a 1 a_{1} a1​,…, a n − 1 a_{n-1} an−1​)，當n=0時，表為空。

線上性表中， a i a_{i} ai​(0<i<n-1)表示下标為i的元素， a i − 1 a_{i-1} ai−1​為 a i a_{i} ai​的直接前驅元素， a i + 1 a_{i+1} ai+1​為 a i a_{i} ai​的直接後繼元素。第一個元素 a 0 a_{0} a0​無直接前驅元素，最後一個元素 a n − 1 a_{n-1} an−1​無直接後繼元素，其它資料元素均有唯一直接前驅元素和直接後繼元素。可以簡成直接前驅元素為前驅，直接後繼元素為後繼。

線性表是一種非常靈活的資料結構，可以執行任意位置插入、删除元素的運算，也可執行搜尋、修改等運算。

ADT List	//線性表
{
	資料:n個元素，下标範圍0~n-1，資料元素之間關系為一對一。
	運算:
		Init(L):初始化運算，構造一個空線性表。
		Destory(L):撤銷運算。判斷線性表L是否存在，存在則撤銷。
		IsEmpty(L):判空運算。判斷線性表是否為空。
		Length(L):長度運算。若線性表存在，傳回線性表L元素個數。
		Find(L,i):查找運算。若線性表存在且i為下标範圍之内，傳回ai的值。
		Insert(L,i,x):插入運算。若線性表存在且i為下标範圍之内，則在ai後插入元素x，當i=-1時，元素x插入頭部位置。
		Delete(L,i):删除運算。若線性表非空且i為下标範圍之内，删除元素ai。
		Update(L,i,x):更新運算。若線性表存在且i為下标範圍之内，将ai值修改為x。
		Output(L):輸出運算。若線性表存在，則輸出線性表中所有元素。
}

1、線性表的順序存儲:使用連續的存儲空間，采用順序存儲線性表稱為順序表。順序表借助元素在存儲空間中的位置來表示元素之間的邏輯關系:邏輯上相鄰的資料元素，其實體存儲位址也相鄰。

▲定義n為線性表長度，maxlength為線性表最大允許長度。在處理實際問題時，線性表長度會随問題不同而不同，故采用動态配置設定的一維數組。

typedef struct seqList{
	int n;//線性表目前長度
	int maxlength;//線性表允許最大長度 
	ElemType *element;//線性表元素
}SeqList;

ElemType為自定義資料類型，為統一描述資料結構中資料類型而設定，在實際使用時，使用者可以根據自己所需具體定義資料類型，例如:typedef int ElemType，将ElemType定義為整型。指針element訓示順序表的存儲空間的首位址。

#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;//預設定義ElemType為整型 
typedef struct seqList{
	int n;//線性表目前長度
	int maxlength;//線性表允許最大長度 
	ElemType *element;//線性表元素 
}SeqList;
int Init(SeqList *L,int maxsize){//初始化運算 
	L->maxlength=maxsize;
	L->n=0;//初始長度為0 
	L->element=(ElemType*)malloc(sizeof(ElemType)*maxsize);//開辟允許最大長度的空間 
	if(!L->element)
		return 0;
	return 1;
}
int Find(SeqList *L,int i,ElemType *x){//查找運算
	if(i<0||i>L->n-1)//待查下标不合法 
		return 0;
	else{
		*x=L->element[i];
		return 1;
	} 
}
int Insert(SeqList *L,int i,ElemType x){//插入運算 
	if(i<-1||i>L->n-1||L->n==L->maxlength)//待插入下标不合法 
		return 0;
	else{
		for(int j=L->n-1;j>i;j--)
			L->element[j+1]=L->element[j];
	}
	L->element[i+1]=x;//插入 
	L->n++;//目前長度加1 
	return 1;
}
int Delete(SeqList *L,int i){//删除操作 
	if(i<0||i>L->n-1||!L->n)//待删下标不合法 
		return 0;
	else{
		for(int j=i+1;j<L->n;j++)
			L->element[j-1]=L->element[j];
		L->n--;//目前長度減1 
		return 1;
	}
}
int Output(SeqList *L){//輸出運算 
	for(int i=0;i<L->n;i++)
		cout<<L->element[i]<<" ";
	cout<<endl;
}
void Destory(SeqList *L){//撤銷操作 
	L->n=0;
	L->maxlength=0;
	free(L->element);
}
int main(int argc, char** argv) {
	SeqList L;
	int N,x;//N為使用者輸入目前長度 x為查找結果值 
	cin>>N; 
	Init(&L,N);
	for(int i=0;i<N;i++)
		Insert(&L,i-1,i);
	Output(&L);
	int i;//待查元素下标
	cin>>i;
	Find(&L,i,&x);
	cout<<x<<endl;
	Delete(&L,0);//删除下标為0的元素 
	Output(&L);
	Destory(&L);
	return 0;
}
二、線性表

2、線性表的鍊式存儲:簡成連結清單，連結清單有單連結清單、帶頭結點的連結清單、循環連結清單、雙向連結清單等多種類型。相比于順序存儲，鍊式存儲可以随機存取，存儲利用空間高。連結清單中，不僅需要存儲每個資料元素，還需要存儲其直接後繼的存儲位址，兩部分資料資訊結合起來稱為結點。每個結點隻包含一個指針域的連結清單，稱為單連結清單。記資料域為element，指針域為link。

①單連結清單:線性表以單連結清單形式存儲時，第一個元素 a 0 a_{0} a0​所在的結點稱為頭結點。存儲頭結點位址指針稱為頭指針，記為first。若單連結清單中沒有資料元素，那麼單連結清單為空，first指針的值為NULL，記為ʌ；單連結清單最後一個元素 a n − 1 a_{n-1} an−1​所在結點稱為尾結點，由于此結點沒有後繼結點，其指針域值為NULL。

二、線性表

▲定義Node表示單連結清單的結點結構類型，element表示結點的資料域，link表示結點的指針域，以存放後繼結點的位址；SingleList表示單連結清單類型，first表示頭指針，n表示單連結清單元素個數(有效長度)。

typedef struct node{
	ElemType element;//資料域
	struct node *link;//指針域
}Node;
typedef struct singleList{
	Node *first;//頭指針 結構體指針,指向頭結點a0
	int n;//有效長度
}SingleList;

Ⅰ單連結清單的插入(Insert):插入運算分兩種情況:新結點q插入至頭結點之前；新結點q插入至連結清單中間。是以我們需要開辟一個Node型空間以存放待插入元素的資料和下個結點的位址。

Node *q;
q=(Node*)malloc(sizeof(Node));

若i=-1，表示将新結點插入至單連結清單頭結點之前，成為新的頭結點。

二、線性表
q->link=first;
first=q;

若-1<i<n-1，表示将新結點插入單連結清單，新結點成為 a i + 1 a_{i+1} ai+1​的直接前驅， a i a_{i} ai​的直接後繼。

二、線性表
q->link=p->link;
p->link=q;

Ⅱ單連結清單的删除(Delete):删除運算分兩種情況:删除頭結點；删除中間結點。

若i=0，表示删除頭結點。

二、線性表

若0<i<n，表示删除中間結點。

二、線性表
q->link=p->link;
free(p);

Ⅲ單連結清單的撤銷(Destory):釋放單連結清單中動态配置設定的資料存儲空間，防止記憶體洩漏。

二、線性表
while(first!=NULL){
	p=first->link;
	free(first);
	first=p;
}
           
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;//預設定義ElemType為整型 
typedef struct node{ 
	ElemType element;//資料域 
	struct node *link;//指針域 
}Node;
typedef struct singlelist{
	int n;//有效長度 
	Node *first;//頭指針 
}SingleList;
int Init(SingleList *L){//初始化運算 
	L->first=NULL;
	L->n=0;
	return 1;
}
int Find(SingleList *L,int i,ElemType *x){//查找運算 
	if(i<0||i>L->n-1)//待查下标不合法 
		return 0;
	else{
		Node *p=L->first;
		for(int j=0;j<i;j++)
			p=p->link;//從頭結點開始查找 
		*x=p->element;
		return 1;
	} 
}
int Insert(SingleList *L,int i,ElemType x){//插入運算 
	if(i<-1||i>L->n-1)//待插入下标不合法 
		return 0;
	else{
		Node *p,*q;
		p=L->first;
		for(int j=0;j<i;j++)
			p=p->link;//p指向元素ai 
		q=(Node*)malloc(sizeof(Node));//生成新結點q 
		q->element=x;
		if(i>-1){//新結點插在非頭結點之前 
			q->link=p->link;
			p->link=q;
		}
		else{//新結點插入頭結點之前 成為新的頭結點 
			q->link=L->first;
			L->first=q;
		}
		L->n++;//表長加1 
		return 1;
	}
}
int Delete(SingleList *L,int i){//删除運算 
	if(!L->n||i<0||i>L->n-1)//待删下标不合法 
		return 0;
	else{
		Node *p,*q;
		p=L->first;
		q=L->first;
		for(int j=0;j<i-1;j++)
			q=q->link;//q指向元素ai-1 
		if(i==0)//待删元素為頭結點 
			L->first=L->first->link;
		else{//待删元素不是頭結點 
			p=q->link;
			q->link=p->link;
		}
		free(p);
		L->n--;//表長減1 
		return 1;
	}
}
int Output(SingleList *L){//輸出運算
	if(!L->n)//表為空則不輸出 
		return 0;
	else{
		Node *p;
		for(p=L->first;p!=NULL;p=p->link)
			cout<<p->element<<" ";
		cout<<endl;
		return 1;
	}
}
void Destory(SingleList *L){//撤銷運算
	Node *p;
	for(;L->first!=NULL;L->first=p){
		p=L->first->link;
		free(L->first);
	}
}
int main(int argc, char** argv) {
	int N;
	ElemType x;
	SingleList list;
	cin>>N;
	Init(&list);
	for(int i=0;i<N;i++)
		Insert(&list,i-1,i);
	Output(&list);
	Find(&list,0,&x);
	cout<<x<<endl;
	Delete(&list,1);
	Output(&list);
	Destory(&list);
	return 0;
}
二、線性表

②帶頭結點的單連結清單:單連結清單中，由頭結點沒有直接前驅，進行插入和删除運算時，需要把頭結點的插入和删除運算與中間結點的插入和删除運算分情況處理。為簡化算法，在單連結清單的頭結點前插入一個表頭結點，稱為帶頭結點的單連結清單。

二、線性表

注意頭結點和表頭結點的差別:元素 a 0 a_{0} a0​所在結點為頭結點，頭結點之前的結點稱為表頭結點。表頭結點的資料域中不存放元素。當表為空時，也存在表頭結點，其指針域指向空(NULL)。

typedef struct node{
	ElemType element;//資料域
	struct node *link;//指針域
}Node;
typedef struct headerList{
	Node *head;//表頭指針 結構體指針,指向表頭結點
	int n;//有效長度
}HeaderList;
           
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;
typedef struct node{
	ElemType element;//資料域 
	struct node *link;//指針域 
}Node;
typedef struct headerList{
	Node *head;//頭指針 
	int n;//有效長度 
}HeaderList;
int Init(HeaderList *h){//初始化運算 
	h->head=(Node*)malloc(sizeof(Node));//生成表頭結點 
	if(!h->head)
		return 0;
	else{
		h->head->link=NULL;
		h->n=0;
		return 1;
	}
}
int Find(HeaderList *h,int i,ElemType *x){//查找運算 
	if(i<0||i>h->n-1)//待查下标不合法 
		return 0;
	else{
		Node *p=h->head;
		for(int j=0;j<i+1;j++)
			p=p->link;
		*x=p->element;
		return 1; 
	}
}
int Insert(HeaderList *h,int i,ElemType x){//插入運算 
	if(i<-1||i>h->n-1)//待插下标不合法 
		return 0;
	else{
		Node *p,*q;
		p=h->head;
		q=(Node*)malloc(sizeof(Node));//生成新結點q 
		for(int j=0;j<i+1;j++)//進行i+1次移動 
			p=p->link;
		q->element=x;
		q->link=p->link;
		p->link=q;
		h->n++;//表長加1 
		return 1;
	}
}
int Delete(HeaderList *h,int i){//删除運算 
	if(i<0||i>h->n-1)//待删下标不合法 
		return 0;
	else{
		Node *p,*q;
		p=h->head;
		for(int j=0;j<i;j++)
			p=p->link;
		q=p->link;
		p->link=q->link;
		free(q);
		h->n--;//表長減1 
		return 1;
	}
}
int Output(HeaderList *h){//輸出運算 
	if(!h->n)//表為空 
		return 0;
	else{
		Node *p=h->head->link;
		for(;p!=NULL;p=p->link)
			cout<<p->element<<" ";
		cout<<endl;
		return 1;
	}
}
void Destory(HeaderList *h){//撤銷運算 
	Node *p;
	while(h->head->link!=NULL){
		p=h->head->link->link;
		free(h->head->link);
		h->head->link=p;
	}
}
int main(int argc, char** argv) {
	HeaderList list;
	int N;
	ElemType x;
	cin>>N;
	Init(&list);
	for(int i=0;i<N;i++)
		Insert(&list,i-1,i);
	Output(&list);
	Find(&list,1,&x);
	cout<<x<<endl;
	Delete(&list,2);
	Output(&list);
	Destory(&list);
	return 0;
}
二、線性表

③單循環連結清單:是另一種線性表鍊式存儲方式，其最後一個結點的指針域存儲頭結點的位址，使得整個單連結清單形成一個環，頭尾相接的連結清單稱為單循環連結清單。

Ⅰ單循環連結清單

二、線性表
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;
typedef struct node{
	ElemType element;//資料域 
	struct node *link;//指針域 
}Node;
typedef struct singleList{
	Node *first;//頭指針 
	int n;//有效長度 
}SingleList;
int Init(SingleList *L){//初始化運算 
	L->first=NULL;
	L->n=0;
	return 1;
}
int Insert(SingleList *L,int i,ElemType x){//插入運算 
	if(i<-1||i>L->n)//待插下标不合法 
		return 0;
	else{
		Node *p,*q;
		q=(Node*)malloc(sizeof(Node));//生成新結點q 
		q->element=x;
		p=L->first;
		for(int j=0;j<i;j++)
			p=p->link;
		if(i>-1){
			q->link=p->link;
			p->link=q;
		}
		else{
			q->link=L->first;
			L->first=q;
		}
		L->n++;
		return 1;
	}
}
void flag(SingleList *L){//連結清單循環 
	Node *p=L->first;
	for(int i=0;i<L->n-1;i++)
		p=p->link;
	p->link=L->first;
}
int Find(SingleList *L,int i,ElemType *x){//查找運算 
	if(i<0||i>L->n-1)//待查下标不合法 
		return 0;
	else{
		Node *p=L->first;
		for(int j=0;j<i;j++)
			p=p->link;
		*x=p->element;
		return 1;
	}
}
int Delete(SingleList *L,int i){//删除運算 
	if(i<0||i>L->n-1)//待删下标不合法 
		return 0;
	else{
		Node *p,*q;
		p=L->first;
		q=L->first;
		for(int j=0;j<i-1;j++)
			q=q->link;
		if(i>0){
			p=q->link;
			q->link=p->link;
		}
		else{
			p=p->link;
		}
		free(p);
		L->n--;
		return 1;
	}
}
int Output(SingleList *L){//輸出運算 
	if(!L->n)//表為空 
		return 0;
	else{
		int T;
		cin>>T;
		Node *p=L->first;
		for(int i=0;i<L->n*T;i++){//T為周期,使用者輸入T,輸出周遊連結清單T次 
			cout<<p->element<<" ";
			p=p->link;
		}
		cout<<endl;
		return 1;
	}
}
void Destory(SingleList *L){//撤銷運算 
	Node *p,*q=L->first;
	for(int i=0;i<L->n-1;i++)
		q=q->link;
	q->link=NULL; 
	while(L->first!=NULL){
		p=L->first->link;
		free(L->first);
		L->first=p;
	}
}
int main(int argc, char** argv) {
	SingleList list;
	int N;
	ElemType x;
	cin>>N;
	Init(&list);
	for(int i=0;i<N;i++)
		Insert(&list,i-1,i);
	flag(&list);//頭尾連接配接 
	Output(&list);
	Find(&list,3,&x);
	cout<<x<<endl;
	Delete(&list,3);
	Output(&list);
	Destory(&list); 
	return 0;
}
二、線性表

說明:撤銷運算(Destory)中，若按照單連結清單的撤銷運算實作，由于末尾元素 a n − 1 a_{n-1} an−1​指針域指向第一個元素 a 0 a_{0} a0​的指針域，那麼在撤銷運算中，第一步就釋放了 a 0 a_{0} a0​的指針域，導緻末尾元素 a n − 1 a_{n-1} an−1​指針域沒有指向，可能會出現警告。那麼就需要在第一步時就使得末尾元素指針指向空(NULL)，再執行單連結清單的撤銷運算。

void Destory(SingleList *L){//撤銷運算 
	Node *p,*q=L->first;
	for(int i=0;i<L->n-1;i++)//q指向an-1 
		q=q->link;
	q->link=NULL; //末尾元素指空 
	while(L->first!=NULL){
		p=L->first->link;
		free(L->first);
		L->first=p;
	}
}
二、線性表

Ⅱ帶表頭結點的單循環連結清單

二、線性表
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;
typedef struct node{
	ElemType element;//資料域 
	struct node *link;//指針域 
}Node;
typedef struct headerList{
	int n;//有效長度 
	Node *head;//頭指針 
}HeaderList;
int Init(HeaderList *h){//初始化運算 
	h->n=0;
	h->head=(Node*)malloc(sizeof(Node));//生成表頭結點 
	h->head->link=h->head;//循環 
	return 1;
}
int Insert(HeaderList *h,int i,ElemType x){//插入運算 
	if(i<-1||i>h->n-1)//待插下标不合法 
		return 0;
	else{
		Node *p,*q;
		q=(Node*)malloc(sizeof(Node));
		q->element=x;
		p=h->head;
		for(int j=0;j<i+1;j++)
			p=p->link;
		q->link=p->link;
		p->link=q;
		h->n++;
		return 1;
	}
}
int Output(HeaderList *h){//輸出運算 
	if(!h->n)//表為空 
		return 0;
	else{
		Node *p=h->head->link;
		for(int i=0;i<h->n;i++){
			cout<<p->element<<" ";
			p=p->link;
		}
		cout<<endl;
		return 1;
	}	
}
int Find(HeaderList *h,int i,ElemType *x){//查找運算 
	if(i<0||i>h->n-1)//待查下标不合法 
		return 0;
	else{
		Node *p=h->head->link;
		for(int j=0;j<i;j++)
			p=p->link;
		*x=p->element;
		return 1;
	}
}
int Delete(HeaderList *h,int i){//删除運算 
	if(i<0||i>h->n-1)//待删下标不合法 
		return 0;
	else{
		Node *p=h->head;
		for(int j=0;j<i;j++)
			p=p->link;
		Node *q=p->link;
		p->link=q->link;
		free(q);
		h->n--;
		return 1;
	}
} 
void Destory(HeaderList *h){//撤銷運算 
	Node *p=h->head,*q;
	for(int i=0;i<h->n;i++)
		p=p->link;
	p->link=NULL;//末尾元素指空 
	while(h->head->link!=NULL){
		q=h->head->link->link;
		free(h->head->link);
		h->head->link=q;
	}
}
int main(int argc, char** argv) {
	HeaderList list;
	int N;
	ElemType x;
	cin>>N;
	Init(&list);
	for(int i=0;i<N;i++)
		Insert(&list,i-1,i);
	Output(&list);
	Find(&list,2,&x);
	cout<<x<<endl;//查找下标為2的元素并輸出 
	Delete(&list,1);//删除下标為1的元素 
	Delete(&list,0);//删除下标為0的元素 
	Output(&list);//删除後輸出
	Destory(&list); 
	return 0;
}
二、線性表

④雙向連結清單:上述線性表的鍊式存儲結構中，每個結點隻有一個指針域，從某個結點出發隻能順着指針域向後查找尋找後繼結點；若要向前查找前驅結點，則需要從頭結點開始再次查找，那麼就引入雙向連結清單。

二、線性表

存儲資料元素的域稱為資料域，記為element；左指針域是存儲直接前驅結點位址的域，記為llink；右指針域是存儲直接後繼結點位址的域，記為rlink。

二、線性表
typedef struct duNode{
	ElemType element;//資料域
	struct duNode *llink;//左指針域
	struct duNode *rlink;//右指針域
}DuNode;
typedef struct duList{
	int n;//有效長度
	DuNode *first;//頭指針
}DuList;

Ⅰ雙向連結清單的插入:在下标為i的元素之後插入元素x。雙向連結清單與單連結清單不同，由于單連結清單的末尾元素的指針域指向空且沒有後繼元素，插入後的後繼結點中沒有儲存前驅元素位址，是以單連結清單的插入隻需要讨論頭部插入和中間插入兩種情況(尾部插入屬于中間插入情況)；但由于雙向連結清單的末尾元素的右指針域指向空且沒有後繼結點(後繼結點認為為空，不存在左指針域指向上一個元素)，故雙向連結清單的尾部插入運算與中間插入運算不同，即雙向連結清單的插入有三種情況:頭部插入、中間插入、尾部插入。

二、線性表
//頭部插入
q->rlink=L->first;
L->first->llink=q;
L->first=q;
//中間插入
q->llink=p;
q->rlink=p->rlink;
p->rlink->llink=q;
p->rlink=q;
//尾部插入
p->rlink=q;
q->llink=p;

說明:上述示範中單連結清單、循環連結清單均可以通過Insert函數對連結清單進行初始化。但由于雙向連結清單的特殊性(插入元素由于不存在後繼結點，後繼結點的左指針域無法指向待插元素)，調試時會出現異常，故無法通過Insert函數對雙向連結清單初始化。

二、線性表

Ⅱ雙向連結清單的初始化:調試發現，通過Insert函數對連結清單插入初始化會異常退出，是以需要再通過Init_Insert函數對連結清單初始化插入。

二、線性表
//插入第一個元素
q->rlink=L->first;
L->first=q;
//插入後繼元素
q->rlink=p->rlink; 
q->llink=p;
p->rlink=q;
           
#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef int ElemType;
typedef struct duNode{
	ElemType element;//資料域 
	struct duNode *llink;//左指針域 
	struct duNode *rlink;//右指針域 
}DuNode;
typedef struct duList{
	int n;//有效長度 
	DuNode *first;//頭指針 
}DuList;
int Init(DuList *L){//表初始化操作 
	L->first=NULL;
	L->n=0;
	return 1;
} 
int Init_Insert(DuList *L,int i,ElemType x){//初始化插入操作 
	if(i<-1||i>L->n-1)//待插下标不合法 
		return 0;
	else{
		DuNode *p,*q;
		q=(DuNode*)malloc(sizeof(DuNode));
		q->element=x;   
		p=L->first;
		if(i>-1){//插入後繼元素
			for(int j=0;j<i;j++)
				p=p->rlink; 
			q->rlink=p->rlink; 
			q->llink=p;
			p->rlink=q;
		}
		else{//插入第一個元素
			q->rlink=L->first;
			L->first=q;
		}
		L->n++;
		return 1;
	}
}
int Insert(DuList *L,int i,ElemType x){//普通插入操作 
	if(i<-1||i>L->n-1)//待插下标不合法 
		return 0;
	else{
		DuNode *p,*q;
		p=L->first;
		q=(DuNode*)malloc(sizeof(DuNode));
		q->element=x;
		if(i==L->n-1){//尾部插入 
			for(int j=0;j<i;j++)
				p=p->rlink;
			p->rlink=q;
			q->llink=p;
		}
		else if(i>-1){//中間插入 
			for(int j=0;j<i;j++)
				p=p->rlink;
			q->llink=p;
			q->rlink=p->rlink;
			p->rlink->llink=q;
			p->rlink=q;
		}
		else{//頭部插入 
			q->rlink=L->first;
			L->first->llink=q;
			L->first=q; 
		}
		L->n++;
		return 1;
	}
}
int Find(DuList *L,int i,ElemType *x){//查找操作 
	if(i<0||i>L->n-1)//待查下标不合法 
		return 0;
	else{
		DuNode *p=L->first;
		for(int j=0;j<i;j++)
			p=p->rlink;
		*x=p->element;
		return 1;
	}
}
int Delete(DuList *L,int i){//删除操作 
	if(i<0||i>L->n-1)//待删下标不合法 
		return 0;
	else{
		DuNode *p,*q;
		p=L->first;
		q=L->first;
		if(i==L->n-1){//尾部删除 
			for(int j=0;j<i;j++)
				q=q->rlink;
			free(q);
		}
		else if(i>0){//中間删除 
			for(int j=0;j<i;j++)
				q=q->rlink;
			p=q->llink;
			p->rlink=q->rlink;
			q->rlink->llink=p;
		}
		else{//頭部删除 
			L->first=L->first->rlink;
			free(p); 
		}
		L->n--;
		return 1;
	}
}
int Output(DuList *L){//輸出操作
	if(!L->n)//表空
		return 0;
	else{
		DuNode *p=L->first;
		for(int i=0;i<L->n;i++){
			cout<<p->element<<" ";
			p=p->rlink;
		}
		cout<<endl; 
		return 1;
	}
}
void Destory(DuList *L){//撤銷操作
/*下面展示的是從尾向頭的撤銷操作
目的是檢驗此連結清單是否實作了可以由後繼元素查找前驅元素的功能*/
	DuNode *p=L->first;
	p->llink=NULL;//首元素左指針指空 
	for(int i=0;i<L->n-1;i++)
		p=p->rlink;
	DuNode *q=p->llink;
	while(q!=NULL){
		free(p);
		p=q;
		q=q->llink;
	}
}
int main(int argc, char** argv) {
	DuList list;
	Init(&list);//表初始化 
	int N;
	ElemType x;
	cin>>N;//輸入5 
	for(int i=0;i<N;i++)
		Init_Insert(&list,i-1,i);//初始化
	Output(&list);//0 1 2 3 4
	Insert(&list,2,100);//下标為2的元素後插入100 
	Output(&list);//0 1 2 100 3 4
	Insert(&list,5,500);//下标為5的元素後插入500 
	Output(&list);//0 1 2 100 3 4 500
	Find(&list,3,&x);
	cout<<x<<endl;//查找下标為3的元素并輸出
	Delete(&list,3);
	Output(&list);//删除下标為3的元素并輸出 
	Delete(&list,5);
	Output(&list);//删除下标為5的元素并輸出
	Destory(&list);
	return 0;
}
二、線性表

3、線性表的應用:線性表作為最基本的資料結構，應用廣泛。其中，一進制整系數多項式的算數運算就是線性表的一種應用。

設一進制整系數多項式:p(x)= a 1 a_{1} a1​ x m x^m xm+ a 2 a_{2} a2​ x m − 1 x^{m-1} xm−1+…+ a n − 1 a_{n-1} an−1​ x 2 x^{2} x2+ a n a_{n} an​ x x x+C。其每一項可抽象成 c o e f coef coef· x e x p x^{exp} xexp形式，其中 c o e f coef coef為項的系數， e x p exp exp為指數。這樣一個多項式可看成n個項組成的線性表。為友善描述，令多項式均按降幂表示。

例如:将p(x)= 7 7 7 x 12 x^{12} x12- 5 5 5 x 6 x^{6} x6+ 6 6 6 x 3 x^{3} x3+ 9 9 9與q(x)= 2 2 2 x 10 x^{10} x10+ 4 4 4 x 6 x^{6} x6- 6 6 6 x 3 x^{3} x3+ 5 5 5相加，為節省空間，将結果存儲在q(x)上，并仍保持降幂排列，以上兩個多項式相加結果為q(x)= 7 7 7 x 12 x^{12} x12+ 2 2 2 x 10 x^{10} x10- x 6 x^{6} x6+ 14 14 14。由此看出，在進行加法運算時，多項式中的項會被頻繁插入删除，是以，鍊式存儲結構更适合表示多項式。其每個結點有三個域，系數域記為 c o f cof cof，指數域記為 e x p exp exp，指針域記為link。為便于建立，采用帶表頭結點的單循環連結清單表示多項式。其核心運算為建立與加法運算。

typedef struct pNode{
	int coef;//系數域
	int exp;//指數域
	struct pNode *link;//指針域
}PNode;

Ⅰ多項式的建立:初始狀态為空的帶表頭結點的單循環連結清單，逐個插入各項，保證多項式的各項降幂排列。建立新結點*pn，輸入其系數和指數，以負指數輸入終止，将新結點的指數和多項式各結點的指數比較，找到第一個指數小于新結點指數的結點，将新結點插入此結點之前。

Ⅱ多項式的加法:将多項式p(x)與q(x)相加，其結果存儲至q(x)中。初始化指針p、q，分别周遊p(x)和q(x)的結點。若p->exp＜q->exp，說明q目前所指結點的指數相較于p目前所指結點的指數大，q指針右移，直到找到相等指數或第一個q所指結點指數小于p所指結點指數；若p->exp==q->exp，當其系數相加為結果為0，則删除，否則将其系數相加附加于q的系數域上；若p->exp＞q->exp，即q(x)中沒有與目前p所指結點的指數相比對的項，即找到了第一個q所指結點指數小于p所指結點指數，直接複制目前p所指向的結點，并将其插在目前q所指結點之前。

#include <bits/stdc++.h>
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
using namespace std;
typedef struct pNode{
	int coef;//系數域 
	int exp;//指數域 
	struct pNode *link;//指針域 
}PNode;
typedef struct polynominal{
	int n;//有效長度 
	PNode *head;//頭指針 
}Polynominal;
void Init(Polynominal *p){//初始化運算 
	p->head=(PNode*)malloc(sizeof(PNode));
	p->head->exp=-1;
	p->head->coef=0;
	p->head->link=p->head;
	p->n=0;
}
void Create(Polynominal *p){//建立多項式運算 
	PNode *pn,*qn,*pre;
	for(;;){
		pn=(PNode*)malloc(sizeof(PNode));
		cout<<"cof:";
		cin>>pn->coef;
		cout<<"exp:";
		cin>>pn->exp;
		if(pn->exp<0)
			break;
		pre=p->head;
		qn=pre->link;
		while(qn&&qn->exp>pn->exp){
			pre=qn;
			qn=qn->link;
		}
		pn->link=qn;
		pre->link=pn;
		p->n++;
	}
}
void Output(Polynominal *p){//輸出運算 
	PNode *pn=p->head->link;
	for(;pn!=p->head;pn=pn->link)
		cout<<pn->coef<<" "<<pn->exp<<endl;
}
void Add(Polynominal *px,Polynominal *qx){//多項式相加運算 
	PNode *q,*q1=qx->head,*p,*temp;
	p=px->head->link;
	q=q1->link;
	while(p!=px->head){//從頭開始周遊p(x) 
		while(p->exp<q->exp){//跳過q->exp大的項 
			q1=q;
			q=q->link; 
		}
		if(p->exp==q->exp){//指數相等 
			q->coef=q->coef+p->coef;//系數相加 
			if(q->coef==0){//系數相加後為0 
				q1->link=q->link;
				free(q);
				q=q1->link;
				p=p->link;
			}
			else{//系數相加後不為0 
				q1=q;
				q=q->link;
				p=p->link;
			}
		}
		else{//沒有與p(x)目前項相等的指數 
			temp=(PNode*)malloc(sizeof(PNode));
			temp->coef=p->coef;
			temp->exp=p->exp;
			temp->link=q1->link;
			q1->link=temp;
			q1=q1->link;
			p=p->link;
		}
	}
}
int main(int argc, char** argv) {
	Polynominal poly1,poly2;
	Init(&poly1);Init(&poly2);
	Create(&poly1);Create(&poly2);
	cout<<"The first polynominal:"<<endl;
	Output(&poly1);
	cout<<"The second polynominal:"<<endl;
	Output(&poly2);
	Add(&poly1,&poly2);
	cout<<"The sum of two polynominal:"<<endl;
	Output(&poly2);
	return 0;
}
二、線性表
資料結構(C++) 資料結構
上一篇: 深度學習！豐田現場裝置的管理方法
下一篇: 線性表操作二刷總結

繼續閱讀