title: 06-數(shù)據(jù)結(jié)構(gòu)及算法-線性表
date: 2019-11-17 20:34:00
tags: 數(shù)據(jù)結(jié)構(gòu)及算法
記錄線性表相關(guān)知識
線性表的類型及定義
什么是線性表
線性表：一個線性表是n個數(shù)據(jù)特性相同的數(shù)據(jù)元素的有序序列甫贯。
在稍微復(fù)雜的線性表中，一個數(shù)據(jù)元素可以由多個數(shù)據(jù)項構(gòu)成蒸苇。
線性表中元素的個數(shù)n(n大于等于0)定義為線性表的長度，n=0時成為空表。
線性表是一個相當(dāng)靈活的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)需要增長或縮短。
對于非空的線性表或者線性結(jié)構(gòu)的特點：
- 第一個數(shù)據(jù)元素沒有前驅(qū)津函，這個數(shù)據(jù)元素被稱為開始節(jié)點。
- 最后一個元素沒有后繼孤页，這個元素被稱為終端節(jié)點纺弊。
- 除了第一個和最后一個數(shù)據(jù)元素外卷仑，其他數(shù)據(jù)元素有且僅有一個前驅(qū)和一個后繼秩伞。
線性表的順序表示及實現(xiàn)
順序表的定義
- 線性表的順序表示指的是用一組地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素待讳。
順序表的特點
- 用元素在計算機內(nèi)“物理位置相鄰”來表示線性表中數(shù)據(jù)元素之間的相鄰蛤售。
- 存儲密度高寻狂，但要預(yù)先分配“足夠應(yīng)用”的存儲空間访娶，這可能會造成存儲空間的浪費又固。
- 便于隨機存儲
- 插入刪除操作繁瑣
線性表的順序存儲
線性表的順序存儲結(jié)構(gòu)
// 線性表的順序存儲結(jié)構(gòu)
#include <iostream>
#include<stdio.h>
#include<stdlib.h>
#define Max 80
#define Increment 10
typedef struct
{
int* elem;
int length;
int size;
}SqList;
線性表的初始化
// 線性表的初始化
// 為順序表分配一個預(yù)定大小的數(shù)組空間冰寻，并將順序表的長度設(shè)為0
void InitList(SqList& L)
{
L.elem = (int*)malloc(Max * sizeof(int));
if (!L.elem) {
printf("存儲空間分配失斝虢獭！");
return;
}
L.length = 0; //空表長度為0
L.size = Max; //初始存儲容量
printf("初始化成功");
}
獲取指定位置元素
// 獲取元素
// 將線性表中的第i個位置元素值返回
int GetElem(SqList& L, int i, int *e)
{
if (i<1 || i>L.length) {
printf("位置信息錯誤");
return 0;
}
*e = L.elem[i-1];
printf("獲取成功");
return 1;
}
線性表的插入操作
// 插入元素
// 在指定位置插入元素
int ListInsert(SqList& L, int i,int e)
{
int* _new;
if (i<1 || i>L.length)
{
printf("插入位置不合法斩芭！\n");
return -1;
}
if (L.length >= L.size)
{
_new = (int*)realloc(L.elem,(L.length + Increment) * sizeof(int));
if (!_new)exit(0);
L.elem = _new;
L.size += Increment;
}
for (int k = L.length - 1; k >= i - 1; k--)
{
L.elem[k + 1] = L.elem[k];
}
L.elem[i - 1] = e;
L.length++;
}
順序存儲結(jié)構(gòu)的優(yōu)缺點
優(yōu)點：
- 無需為表示表中元素之間的邏輯關(guān)系而增加額外的存儲空間
- 可以快速地存取表中任一位置的元素
缺點：
- 插入和刪除需要移動大量元素
- 線性表長度變化較大時轻腺，不容易確定存儲空間的容量
- 造成存儲空間的“碎片”
線性表的鏈式存儲
順序存儲中，插入和刪除時需要移動大量元素划乖，這會耗費大量的時間贬养，導(dǎo)致這些問題的原因是相鄰兩個元素的存儲位置也相鄰，中間沒有空隙琴庵。
為解決上述問題误算，我們不再考慮相鄰元素存儲位置的相鄰關(guān)系，只要做到讓當(dāng)前位置的元素知道下一個元素的位置即可迷殿。
線性表的鏈式存儲：
鏈式存儲示意.png
為了表示每個數(shù)據(jù)與其后繼元素之間的邏輯關(guān)系儿礼，數(shù)據(jù)元素除了存儲本身的信息外，還需要存儲其直接后繼的信息庆寺。
這兩部分信息組成數(shù)據(jù)元素a的存儲映像蚊夫，稱為結(jié)點；它包含兩個域：其中存儲數(shù)據(jù)元素信息的稱為數(shù)據(jù)域懦尝；存儲直接后繼存儲位置的域稱為指針域知纷，指針域中存儲的信息稱作指針或鏈。
注意：
- 整個鏈表的存取必須從頭指針開始進行陵霉。
- 最后一個元素沒有直接后繼屈扎，則線性鏈表中最后一個結(jié)點的指針為“空”(NULL);
線性表的鏈式存儲結(jié)構(gòu)
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#define OK 1
#define ERROR 0
typedef struct LNode {
int data;
struct LNode* next;
}LNode,*LinkList;
未完待續(xù)。撩匕。鹰晨。。。
