在粗略學習一遍資料結構之后，壓根就沒有搞懂其中的邏輯，后來了明白學習資料結構的重要性，打算再利用一大段空閑時間重新拾起資料結構的學習，還站在IT行業門口的我，打算一步一步爬進去，跪著欣賞大佬的筆記和心得，對于資料結構初學者們來說，可能對你們有所幫助，如果有幸得到大佬的指點，也是在下吉人天相啊，
線性表的一些基本操作（同時補充下部分功能實作的邏輯和原理）：
- 構造線性表結構 相當于C語言中的結構體，把實體的結構抽取、打框、定義型別、限制范圍，最后取上別名
- 初始化線性表 對定義的值賦初值
- 銷毀和清空線性表 銷毀直接用到C++中的delete方法，快準狠；清空就是把線性表的長度直接賦值為0，長度為0，即是沒有資料記錄
- 求線性表長度 結構中就有存放長度的引數，直接訪問就行了
- 判斷線性表是否為空 即是判斷長度為不為0，0就是空，非0就是表中有值
- 取值、查找、插入、洗掉 （下面代碼直接體現邏輯）
代碼采用的是C語言和一點C++語法，只展示了功能代碼（有部分注釋），main()就不再展示，
#include <stdio.h>
#include <stdlib.h> // 給表分配記憶體，所需該頭檔案
#define MAXSIZE 100 線性表最大長度
補充：下面的宏定義是操作演算法中用到的預定義常量和型別
表示函式結果狀態
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0 // 錯誤
#define INFEASIBLE -1 // 不可行
#define OVERFLOW -2 // 溢位
typedef int Status; // Status是函式的型別，其值是函式回傳結果的型別，此處定義為int型（后面用來回傳地址下標）
typedef char ElemType; // 定義線性表中存放資料的型別為 char型
// 構造線性表的存盤結構
typedef struct{
ElemType elme[MAXSIZE]; // ElemType上面定義的型別 elem可看做線性表基地址（首地址）
int length; // 存放長度
}SqList; //結構名
// 構造一個空的線性表 -> 初始化線性表 在此實體化了L
Status InitList_Sq(SqList &L)
{
L.elme = new ElemType[MAXSIZE]; // 給L分配記憶體空間（C++方法）
if(!L.elme) exit(OVERFLOW); // 此處為例外處理，分配成功，L為空表，分配不成功，L非空，OVERFLOW存盤分配失敗
L.length = 0; // 賦初值，空表長度為0
return OK; // 回傳結果 對應該函式體的回傳型別Status -> int型
}// InitList_Sq
// 銷毀線性表
void DestroyList(SqList &L)
{
if(L.elme) delete L.elme; // C++方法 delete
}//DestroyList
// 將L重置為空表
void ClearList(SqList &L)
{
L.length = 0; // 長度設為0
}//ClearList
// 回傳線性表的長度
int GetLength(SqList L)
{
return (L.length); // 取長度引數值
}// GetLength
// 判斷線性表是否為空
int IsEmpty(SqList L)
{
if(L.length == 1) return 1;
else return 0; // 取出表長度值進行判斷
}//IsEmpty
// 取值
int GetElem(SqList L,int i,ElemType &e)
{
if(i<1 || i>L.length) return ERROR; // 判斷位置i是否合法，由于線性表是有限序列，所以只能去存在的值，即第1個元素到最后1個元素之間的值，否則無效
e = L.length[i-1]; // 將位置i的值賦給存放結果的e
return OK; // 回傳操作結果（是否成功）
}//GetElem
// 查找
int LocateElem(SqList L,ElemType e)
{
for(i=0;i<L.length;i++)
if(L.elme[i] == e) return i+1; // 對應下標的值進行判斷，回傳下標對應的值 i是物理地址（下標），i+1是邏輯地址（值）
return 0;
}//LocateElem
// 插入
Status ListInsert_Sq(SqList &L,int i,ElemType e)
{
if(i<1 || i>L.length+1) return ERROR; // 判斷合法性
if(L.length == MAXSIZE) return OVERFLOW; // 判斷表中是否滿了，由于線性表的大小是不可更改的，所以在滿了的情況下是不能再插入其他值，否則溢位
for(j=L.length-1;j>=i-1;j--) // 從最后一個元素開始，一個個往后移，直至空出待插入的位置
L.elme[j+1] = L.elme[j]; // 將前面1個元素移到后面的位置
L.elme[i-1]=e; // 空出的位置給e
L.length++; // 插入后長度+1
return OK;
}//ListInsert_Sq
// 洗掉
Ststus ListDelete_Sq(SqList &L,int i)
{
if(i<1 || i>L.length) return ERROR;
for(j=i;j<=L.length-1;j++) // 從待洗掉元素后面1個開始到最后，一個個往前移
L.elme[j-1] = L.elme[j]; // 直接擠掉待洗掉元素
L.length--; // 洗掉1個元素后，長度-1
return OK;
}//ListDelete_Sq
補充1：
有人可能有疑問了，為什么形參中，有的是&L，而有的是L呢？
&在C++中表示參考，所以&L使用的是參考傳參，參考傳參是直接把線性表的地址傳過去進行操作，可直接修改線性表L的值，在初始化清空、銷毀、插入、洗掉等操作中，都得對L進行修改（即重新賦值、添加洗掉元素），在函式沒有用到&L（即傳參采用L）時，表示我只要線性表L當中的值，我并不需要線性表L為我修改任何值，呼叫時L是怎樣的，回傳到main函式就還是什么樣的，
那為什么不采用指標而是采用參考方法呢？C語言中的指標，只要是接觸過的都知道，指標指來指去的看著容易亂邏輯，且不易閱讀、除錯難、容錯高，所以有更好用、更方便的，為啥不用呢，
補充2：
上述演算法中，時間復雜度O(n)，空間復雜度O(1)
補充3：
用C語言分配記憶體
SqList L;
L.elem=(ElemType *)malloc(sizeof(ElemType)*MAXSIZE);
malloc()分配記憶體 free()釋放記憶體
用C++分配、釋放記憶體
分配：int *L = new int; 或 int *L = new int(10)
釋放：delete L;
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/412976.html
標籤：其他