資料結構基礎—線性表
線性表是一種順序存盤結構其特點有：
- 存在唯一的一個被成為”第一個”的資料元素
- 存在唯一的一個被成為”最后一個”的資料元素
- 除第一個之外，集合中的每個元素均只有一個前驅，除最后一個元素哇，集合中每一個元素均只有一個后繼
一、線性表型別定義
一個線性表是n個具有相同特征的資料元素的有限集合，可記作(a1,a2,a3...an),當n = 0時為空表
線性表是相當靈活的資料結構，不僅長度可變，還可以對其中的元素進行訪問，插入和洗掉...具體的操作我會在后面解釋
二、順序表的表示與實作
順序表指的是用一組地址連續的存盤單元依次存盤線性表的資料結構（類比陣列），也稱作順序存盤結構或是順序映像是一種隨機存取的存盤結構
邏輯上相鄰的兩個元素在物理位置上也相鄰
1.順序表的表示
//順序表的結構
//型別自己換吧
typedef struct List{
int *elem;
int length;
int MaxSize;
}SqList;
//可以把它比作開門的要是或是抽屜，通過這東西就就可以找到這個順序表中的任意一元素
elem：表示順序表的首地址，和陣列一樣
length：表示順序表的當前長度
MaxSize：表示當前順序表的最大容量(使用順序表一般大開小用，當使用的范圍超過最大容量后可以進行動態分配記憶體，之后會說)
2.一些相關的操作
//空表
length = 0; //長度為零
//初始化
void Set(SqList &L,int n){
L.elem = (int*)malloc(Size * sizeof(int)); //開辟空間 Size:宏定義，最大容量
if(! L.elem) {printf("創建失敗") return；}
L.MaxSize = Size;
L.length = 0;
printf("創建成功\n");
}
//增表
void AddList(SqList &L){
if(L.length>= L.MaxSize){
int *bnew;
bnew = (int*)malloc(L.elem,(L.MaxSize+ADD) * sizeof(int));
L.elem = bnew;
L.MaxSize = L.MaxSize+ADD;
}
printf("順序表增加成功\n");
}
//在n個位置上插入數值為k的元素
//這里可以再加入順序表是否滿的操作
void Add(SqList &L,int n,int k){
int j = L.length;
if(n<=0 ||n>L.length+1){
printf("插入的位置不合理\n");
} else{
int *p = L.elem+L.length-1;
for(;p>=L.elem+n-1;p--){
*(p+1) = *(p);
}
L.elem[n-1] = k;
L.length++;
}
printf("添加成功\n");
}
//洗掉第n個位置的元素
void Delete(SqList &L,int n){
int j = L.length;
if(n <=0 || n > L.length){
printf("要洗掉的位置不合理\n");
}else{
int *p = L.elem+n-1;
for(;p < L.elem+L.length-1;p++){
*p = *(p+1);
}
L.length--;
}
printf("洗掉成功\n");
}
//輸出
void Get(SqList &L){
for(int i = 1;i <=L.length;i++){
printf("%d\t",L.elem[i-1]);
}
三、鏈表的表示與實作
上一節中的順序表有個很大的缺點，就是在插入和洗掉元素時需要移動大量的元素，本節的鏈表就克服了這個不足，因為它不要求邏輯上相鄰的元素在物理位置上也相鄰，但是，失去了順序表隨機存取的優點
鏈表都是由一個一個節點相連形成的，像下圖一樣，一般一個資料域，一個指標域(放下一個節點的地址，這樣就連起來啦)，當然在雙向鏈表中有兩個指標域...
1.線性鏈表
就是像上圖那樣一個一個節點連接起來的鏈表，不過一般情況下會有一個頭指標，它不存放資料，起到一個總領全鏈的作用(總領全文？)，他它的最后一個節點的指標是指向空的(NULL)
a.線性鏈表的表示
//結構體
typedef struct LNode
{
ElemType data; //存盤鏈表的元素空間
struct LNode *next; //后繼結點
}LinkList;//單鏈表結點型別定義
//類
class Lnode{//節點類
friend class List;
private:
int data;
Lnode *next;
};
class List{
}；//其他的操作
b.一些基本操作
//創建鏈表,初始化
void Set(Lnode *L,int n,int k){//尾插
if(n ==0){
L->next =NULL;
cout << "鏈表為空";
}else{
Lnode *r =NULL,*p = NULL;
p = L;
for(int j = 1;j <n&&p != NULL;j++){
p = p->next;
}
if(p != NULL){
r = (Lnode *)malloc(sizeof(Lnode));
r->data = https://www.cnblogs.com/wht-de-bk/archive/2022/10/08/k;
r->next = NULL;
p->next = r;
p = r;
}
r->next = NULL;
}
}
//在第n個位置插入元素的數值為k
void Add(Lnode *L,int n,int k){
if(n <= 0||n>n+1){
cout <<"要插入的位置不合理";
}else{
Lnode *p = L,*q;
for(int i = 1;i!= n;i++){
p = p->next; //p是插入位置的直接前驅
}
if(p != NULL){
q = (Lnode*)malloc(sizeof(Lnode));
q->data = https://www.cnblogs.com/wht-de-bk/archive/2022/10/08/k;
q->next = p->next; //看著里，關鍵操作
p->next = q;
}
}
cout <<"添加成功\n";
}
//洗掉第n個元素
void Delete(Lnode *L,int n){
if(n <= 0||n>n+1){
cout << "要插入的位置不合理";
}else{
Lnode *p =NULL,*q =NULL;
p = L;
q =L->next;
for(int i = 1;i!= n;i++){
p = p->next; //p是插入位置的直接前驅
q = p->next; //Q是要洗掉的
}
if(p->next != NULL){
p->next = q->next; //看著里，關鍵操作
q = q->next;
//或是p->next = p->next->next
free(p);//記得free掉
}
}
cout << "洗掉成功\n";
}
//輸出鏈表
void GetList(Lnode *L){
Lnode *r =NULL,*p = NULL;
p = L->next;
for(;p != NULL;p = p->next){
cout << p->data << "\t";
}
2.回圈鏈表
與上述的纖細鏈表差不多只是最后一個元素的指標指回頭指標
一些基本操作
//判空
p->next == p;//判斷節點的next是否等于頭指標
//其余操作和線性單鏈表基本相同
3.雙向鏈表（一般都回圈了）
之前的鏈表只能單向的查詢和遍歷，雙向鏈表可以在鏈表的兩個方向移動
a.雙向鏈表的表示
typedef struct LNode
{
ElemType data; //存盤鏈表的元素空間
struct LNode *prior; //前驅結點
struct LNode *next; //后繼結點
}LinkList;//雙向回圈鏈表結點型別定義
b.一些基本的操作
//判空
first->prior == first;
first->next == first;
//構造一個空的雙向回圈鏈表L
void InitLinkList(LinkList *L)
{
L->prior=L->next=L;//空的雙向回圈鏈表L的prior域和next域均回指
}
//頭插法建立雙向回圈鏈表L
void CreateLinkListF(LinkList *L,ElemType d[],int n)
{
LinkList *r;
int i;
L->next=NULL;
for(i=0;i<n;i++)
{
r=(LinkList *)malloc(sizeof(LinkList));//創建新結點r
r->data=https://www.cnblogs.com/wht-de-bk/archive/2022/10/08/d[i];//為新結點賦值
//將新結點r加入到頭結點之后
r->next=L->next;
if(L->next!=NULL)
L->next->prior=r;
L->next=r;
r->prior=L;
}
r=L->next;
while(r->next!=NULL)
r=r->next;
r->next=L;
L->prior=r;
}
void CreateLinkListR(LinkList *L,ElemType d[],int n)//尾插法建立雙向回圈鏈表L
{
int i;
LinkList *p,*q;
L->next=NULL;
q=L;//q指向尾結點
for(i=0;idata=d[i];//為新結點賦值
//將新結點r加入到頭結點之后
q->next=p;
p->prior=q;
q=p;//q重新指向尾結點
}
q->next=L;//尾結點的next域回指
L->prior=q;
}
//在雙向回圈鏈表L中將e插入到第i個位置
void LinkListInsert(LinkList *L,int i,ElemType e)
{
LinkList *p=L;//p指向頭結點
LinkList *r;//r指向新結點，即值域為e的結點
int j;
if(i==1)//插入到第1個位置
{
r=(LinkList *)malloc(sizeof(LinkList));//創建新結點
r->data=e;//為其賦值
//將新結點根據雙向回圈鏈表的特性插入到雙向回圈鏈表中
r->next=p->next;
p->next=r;
r->next->prior=r;
r->prior=p;
}
else if(p->next==L)//原單鏈表為空表或者只有一個元素
{
r=(LinkList *)malloc(sizeof(LinkList));//創建新結點r
r->data=e;//為其賦值
p->next=r;
r->next=p; //看這里，關鍵操作
p->prior=r;
r->prior=p;
}
else
{
p=L->next;
for(j=1;jnext;//指向下一個結點
}
if(p==L)
printf("無\n");//若未找到，則給出適當的提示
else
{
r=(LinkList *)malloc(sizeof(LinkList));//創建新結點r，其值域為e，將其插入第i-1個位置之后
r->data=https://www.cnblogs.com/wht-de-bk/archive/2022/10/08/e;//為其賦值
//將新結點根據雙向回圈鏈表的特性插入到雙向回圈鏈表中
r->next=p->next;
if(p->next!=NULL)p->next->prior=r;
r->prior=p;
p->next=r;
}
}
}
//在雙向回圈鏈表L中洗掉第i個元素
//關鍵操作找到要洗掉的節點后，假設是p
p->prior->next = p->next;
p->next->prior = p->prior;
void LinkListDelete(LinkList *L,int i)
{
LinkList *p=L;
LinkList *q;
int j;
if(i!=1)
{
p=L->next;
for(j=1;jnext;//指向下一個結點
if(p==NULL)//若未找到第i-1個結點，則給出適當的提示
printf("無\n");
else
{
q=p->next;
if(q==NULL)
printf("無\n");//若未找到第i-1個結點，則給出適當的提示
p->next=q->next;//從鏈表中洗掉該結點
if(p->next!=NULL)
p->next->prior=p;
free(q);//成功洗掉該結點
}
}
else//i等于1時
{
q=L->next;
L->next=q->next;
q->next->prior=L;
free(q);
}
}
//輸出顯示雙向回圈鏈表L的各個元素值
void DispLinkList(LinkList *L)
{
LinkList *p;
p=L->next;//p指向頭結點后的第一個結點
while(p!=L)//判斷是否結束，注意雙向回圈鏈表的判斷結束的條件
{
printf("%c ",p->data);//依次顯示輸出元素值
p=p->next;//指向下一個結點
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/511070.html
標籤：其他