數據結構簡單話（一）線性表
前言
本菜鳥筆者打算入門一下數據結構，在學習過程中通過自己簡單話術總結相關基礎知識要點，希望能幫助同樣在入門的小夥伴們快速了解相關基礎知識的輪廓，然後根據知識點再進一步的學習和理解。整個系列採用c語言來實現，程式碼會提供注釋，方便理解實現思路。
邏輯結構
線性表是0個或多個的有窮序列，\(k_0\) 是\(k_1\)的前驅，\(k_1\)是\(k_0\)的後繼，除了首尾結點以外每個結點元素都有且只有一個前驅和一個後繼（類似於現實生活中排隊）。
物理存儲結構
一、順序表
-
概念：採用一組相鄰且連續的存儲空間存儲元素。即：存儲一個元素需要2個單位地址空間，從1號開始存儲，則第二個元素存儲首地址為3號，以此類推。程式碼實現中常用數組作為順序表元素的存儲。
-
優缺點
- 優點：方便查找，確定首地址就可以查找任意下標的元素。由此可以隨機存取。
- 缺點：不易於插入刪除，由於順序表中元素地址是相鄰的，當插入或者刪除一個元素後，修改位置之後的所有元素都需要移動，空間開銷大（類比排隊中一個人出或者插入到隊伍中，後面的所有人都需要向前或向後移動）
-
程式碼實現（初始化增刪改查）
#include<stdlib.h> #include<stdio.h> #define MAXMIUM 100 //定義數組容量最大值 /*結構體*/ typedef struct SeqList { int element[MAXMIUM];//存放整型數據的數組 int n;//數組元素個數 }SeqList; /*初始化，創建一個順序表*/ SeqList *createNullSeq() { SeqList *list = (SeqList *)malloc(sizeof(SeqList)); if (list == NULL) { printf("wrong"); } else { list->n = 0;//初始化的數組內沒有元素，所以n=0 } return list; } /*在指定下標位置插入元素*/ int insert(SeqList* list , int data,int index){ if(list->n < MAXMIUM && index<=list->n){//插入前數組個數不能達到上限，下標需要在有效範圍內 int i; for(i=list->n-1;i>=index;i--){//當前插入元素的位置和位置後的元素都需要往後移動一位 list->element[i+1] = list->element[i]; } i++; list->element[i] = data; list->n++; return 1; } return 0; } /*刪除指定位置的元素*/ int delete(SeqList* list,int index){ if(index<=list->n-1&&index>=0){//跟插入類似，判斷有效條件 for(int i=index;i<list->n-1;i++){//刪除的位置以及後面的元素都需要往前移動一格 list->element[i] = list->element[i+1]; } list->n--; return 1; } return 0; } /*簡單線性表判空*/ int isNull(SeqList* list){ return list->n==0?1:0; } /*查找元素*/ int locate_seq(SeqList* list,int data){ if(list->n==0){ return -1; } for(int i=0;i<list->n;i++){ if(list->element[i]==data){ return i; } } return -1; } /*獲得指定下標的元素*/ int find(SeqList* list,int x){ if(x>=0||x<list->n){ return list->element[x]; } return -1; }
二、鏈表
-
原理
順序表插入刪除需要大量空間損耗（因為需要移動），所以可以採用鏈表的方式減少損耗。每個結點元素在存儲元素資訊時（數據域），還需要額外存儲一個指針域，用於存儲指向下一個結點的地址。這樣相鄰結點之間的地址無需相鄰。插入刪除時只需要修改相關指針域即可。
-
優缺點
- 優點：插入刪除空間代價小，只需要直接修改指針域。
- 缺點：查找麻煩，每次查找都需要從頭結點遍歷。
-
程式碼實現（初始化增刪改查）
#include <stdio.h> #include <stdlib.h> typedef struct PNode { struct PNode *next; int data; } PNode; PNode *createNullNode() { PNode *node = (PNode *)malloc(sizeof(PNode)); if (node == NULL) { printf("wrong"); return NULL; } node->next = NULL; node->data = 0; return node; } /*帶頭結點插入*/ int insertNode(PNode *list, int i, int data) { if (list == NULL) { printf("null"); return 0; } int p = 0; while (list->next != NULL) { if (p != i) { list = list->next; p++; }else{ break; } } if (p == i) { PNode *temp = list->next; PNode *node = createNullNode(); node->next = temp; node->data = data; list->next = node; return 1; } printf("out of range"); return 0; } /*帶頭結點刪除第一個值為x的結點*/ int delete(PNode *list,int x){ if(list==NULL){ printf("list is null"); return 0; } while(list->next!=NULL&&list->next->data!=x){ list = list->next; } if(list->next!=NULL&&list->next->data==x){ PNode* temp = list->next; list->next = temp->next; temp->next = NULL; free(temp); return 1; } printf("no found %d",x); return 0; } /*通過下標查找元素，帶頭結點*/ PNode *find(PNode* list,int i){ if(list==NULL){ printf("null list "); return NULL; } int cursor = 0; while(list->next!=NULL&&cursor!=i){ list = list->next; cursor++; } if(cursor==i){ printf("find %d",list->next->data); return list->next; } printf("out of range"); return NULL; } /*判空*/ int isNull(PNode* list){ return list==NULL?1:list->next==NULL?1:0; } int main() { PNode *head = createNullNode(); int flag = isNull(head); printf("%d\n",isNull(head)); insertNode(head,0,1); insertNode(head,1,2); insertNode(head,2,3); insertNode(head,3,4); insertNode(head,2,77); // find(head,2); printf("%d",isNull(head)); }
總結
- 鏈表方便增刪，順序表方便查找
- 鏈表的增刪主要通過修改指針，順序表增刪主要通過移動元素。
- 歡迎前往我的個人空間 菜鳥小白的個人空間 查看其他技術內容，留下友好評論和點贊，共同進步。
