線性表，即線性存儲結構，將具有“一對一”關係的數據“線性”地存儲到物理空間中，這種存儲結構就稱為線性存儲結構，簡稱線性表。 註意：使用線性表存儲的數據，要求數據類型必須一致，線性表存儲的數據，要麼全不都是整形，要麼全部都是字元串。一半是整形，另一半是字元串的一組數據無法使用線性表存儲。 線性表存儲數 ...
線性表，即線性存儲結構，將具有“一對一”關係的數據“線性”地存儲到物理空間中，這種存儲結構就稱為線性存儲結構，簡稱線性表。
註意：使用線性表存儲的數據，要求數據類型必須一致，線性表存儲的數據，要麼全不都是整形，要麼全部都是字元串。一半是整形，另一半是字元串的一組數據無法使用線性表存儲。
線性表存儲數據可以分為：
順序存儲結構和鏈式存儲結構
數據結構中，一組數據中的某一元素的左側相鄰元素稱為“直接前驅”，位於此元素左側的所有元素都統稱為“前驅元素”；某一元素的右側相鄰元素稱為“直接後繼”，位於此元素右側的所有元素都統稱為“後繼元素”；
先介紹順序表
順序表全名順序存儲結構，順序表存儲數據時，會提前申請一整塊足夠大小的物理空間，然後將數據依次存儲起來，存儲時做到數據元素之間是不間斷的。
順序表的初始化
順序表除了要申請足夠大小的物理空間還需要申請順序表的存儲容量，順序表的長
度，也就是順序表中元素的個數。
註意：順序表申請的存儲容量要大於順序表的長度。
首先我們得自定義順序表
1 typedef struct SeqList{ 2 int * head;//聲明瞭一個名為head的長度不確定的數組，也叫“動態數組” 3 int length;//記錄當前順序表的長度 4 int size;//記錄順序表分配的存儲容量 5 }sqlt;
接著初始化順序表的主要工作：
給 head 動態數據申請足夠大小的物理空間
給 size 和 length 賦初值
1 #define Size 5 2 sqlt init_SeqList(){ 3 sqlt s; 4 s.head=(int*)malloc(sizeof(int)*Size); 5 //構造一個空的順序表，動態申請存儲空間 6 if(!s.head)//如果申請失敗，作出提示並直接退出程式 7 { 8 printf("初始化失敗\n"); 9 exit(0); 10 } 11 s.length=0;//空表的長度初始化為0 12 s.size=Size;//空表的初始存儲空間為Size 13 return s; 14 }
順序表插入元素
通過遍歷，找到數據元素要插入的位置
將要插入位置元素以及後續的元素整體向後移動一個位置；
將元素放到騰出來的位置上
1 //插入函數，其中，elem為插入的元素，p為插入到順序表的位置 2 sqlt insert_SeqList(sqlt s,int elem,int p) 3 { 4 //判斷插入本身是否存在問題（如果插入元素位置比整張表的長度+1還大（如果相等，是尾隨的情況），或者插入的位置本身不存在，程式作為提示並自動退出） 5 if(p>s.length+1||p<1){ 6 printf("插入的位置有問題\n"); 7 return s; 8 } 9 //做插入操作時，首先需要看順序表是否有多餘的存儲空間提供給插入的元素，如果沒有，需要申請 10 if(s.length>=s.size){ 11 s.head=(int *)realloc(s.head,(s.size+1)*sizeof(int)); 12 if(!s.head){ 13 printf("存儲分配失敗\n"); 14 } 15 } 16 //插入操作，需要將從插入位置開始的後續元素，逐個後移 17 for(int i=s.length-1;i>=p-1;i--){ 18 s.head[i+1]=s.head[i]; 19 } 20 //後移完成後，直接將所需插入元素，添加到順序表的相應位置 21 s.head[p-1]=elem; 22 s.length++;//由於添加了元素，所以長度+1 23 return s; 24 }
註意，動態數組額外申請更多物理空間使用的是 realloc 函數。並且，在實現後續元素整體後移的過程，目標位置其實是有數據的，還是原來的數字，只是下一步新插入元素時會把舊元素直接覆蓋。
順序表刪除元素
只需找到目標元素，並將其後續所有元素整體前移 1 個位置即可。（後續元素整體前移一個位置，會直接將目標元素刪除，可間接實現刪除元素的目的。）
1 sqlt del_SeqList(sqlt s,int p){ 2 if(p>s.length||p<1){ 3 printf("被刪除的元素有誤\n"); 4 return s; 5 } 6 //刪除操作 7 for(int i=p;i<s.length;i++){ 8 s.head[i-1]=s.head[i]; 9 } 10 s.length--;//刪除一個元素表的長度要減1 11 return s; 12 }
順序表查找元素
在這裡只選擇簡單的順序查找演算法
1 //查找函數，其中，elem表示要查找的數據元素的值 2 int select_SeqList(sqlt s, int elem){ 3 for(int i=0;i<s.length;i++){ 4 if(s.head[i]==elem){ 5 return i+1; 6 } 7 } 8 return -1;//如果查找失敗，返回-1 9 }
順序表更改元素
找到目標元素；
直接修改該元素的值；
1 //更改函數，其中，elem為要更改的元素，newElem為新的數據元素 2 sqlt amend_SeqList(sqlt s, int elem, int newElem){ 3 int p=select_SeqList(s,elem); 4 s.head[p-1]=newElem; 5 //由於返回的是元素在順序表中的位置，所以p-1就是該元素在數組中的下標 6 return s; 7 }
以下實現增刪改查的整體順序存儲結構線性表
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 #define Size 5 5 typedef struct SeqList{ 6 int * head;//聲明瞭一個名為head的長度不確定的數組，也叫“動態數組” 7 int length;//記錄當前順序表的長度 8 int size;//記錄順序表分配的存儲容量 9 }sqlt; 10 sqlt init_SeqList(){ 11 sqlt s; 12 s.head=(int*)malloc(sizeof(int)*Size); 13 //構造一個空的順序表，動態申請存儲空間 14 if(!s.head)//如果申請失敗，作出提示並直接退出程式 15 { 16 printf("初始化失敗\n"); 17 exit(0); 18 } 19 s.length=0;//空表的長度初始化為0 20 s.size=Size;//空表的初始存儲空間為Size 21 return s; 22 } 23 //插入函數，其中，elem為插入的元素，p為插入到順序表的位置 24 sqlt insert_SeqList(sqlt s,int elem,int p) 25 { 26 //判斷插入本身是否存在問題（如果插入元素位置比整張表的長度+1還大（如果相等，是尾隨的情況），或者插入的位置本身不存在，程式作為提示並自動退出） 27 if(p>s.length+1||p<1){ 28 printf("插入的位置有問題\n"); 29 return s; 30 } 31 //做插入操作時，首先需要看順序表是否有多餘的存儲空間提供給插入的元素，如果沒有，需要申請 32 if(s.length>=s.size){ 33 s.head=(int *)realloc(s.head,(s.size+1)*sizeof(int)); 34 if(!s.head){ 35 printf("存儲分配失敗\n"); 36 } 37 } 38 //插入操作，需要將從插入位置開始的後續元素，逐個後移 39 for(int i=s.length-1;i>=p-1;i--){ 40 s.head[i+1]=s.head[i]; 41 } 42 //後移完成後，直接將所需插入元素，添加到順序表的相應位置 43 s.head[p-1]=elem; 44 s.length++;//由於添加了元素，所以長度+1 45 return s; 46 } 47 sqlt del_SeqList(sqlt s,int p){ 48 if(p>s.length||p<1){ 49 printf("被刪除的元素有誤\n"); 50 return s; 51 } 52 //刪除操作 53 for(int i=p;i<s.length;i++){ 54 s.head[i-1]=s.head[i]; 55 } 56 s.length--;//刪除一個元素表的長度要減1 57 return s; 58 } 59 //查找函數，其中，elem表示要查找的數據元素的值 60 int select_SeqList(sqlt s, int elem){ 61 for(int i=0;i<s.length;i++){ 62 if(s.head[i]==elem){ 63 return i+1; 64 } 65 } 66 return -1;//如果查找失敗，返回-1 67 } 68 //更改函數，其中，elem為要更改的元素，newElem為新的數據元素 69 sqlt amend_SeqList(sqlt s, int elem, int newElem){ 70 int p=select_SeqList(s,elem); 71 s.head[p-1]=newElem; 72 //由於返回的是元素在順序表中的位置，所以p-1就是該元素在數組中的下標 73 return s; 74 } 75 //輸出順序表中元素的函數 76 void display_SeqList(sqlt s){ 77 for(int i=0; i<s.length; i++){ 78 printf("%d",s.head[i]); 79 } 80 printf("\n"); 81 } 82 83 int main(){ 84 sqlt s1=init_SeqList(); 85 //向順序表中添加元素 86 for(int i=1;i<=Size;i++){ 87 s1.head[i-1]=i; 88 s1.length++; 89 } 90 printf("原順序表：\n"); 91 display_SeqList(s1); 92 93 printf("刪除元素2：\n"); 94 s1=del_SeqList(s1,2); 95 display_SeqList(s1); 96 97 printf("在第3的位置插入元素5：\n"); 98 s1=insert_SeqList(s1,5,3); 99 s1=insert_SeqList(s1,5,3); 100 s1=insert_SeqList(s1,5,3); 101 s1=insert_SeqList(s1,5,3); 102 display_SeqList(s1); 103 104 printf("查找元素3的位置:\n"); 105 int p=select_SeqList(s1,3); 106 printf("%d\n",p); 107 108 printf("將元素3改為6:\n"); 109 s1=amend_SeqList(s1,3,6); 110 display_SeqList(s1); 111 return 0; 112 }
